SPP 1183 - Smart Teams: Local, Distributed Strategies for Self-Organizing Robotic Exploration Teams (Subproject)

„During the second phase, we have extended our work from the first phase in several directions: We have developed the first asymptotically optimal strategy - the Hopper Strategy - for keeping an exploring robot connected to its base camp with the help of mobile relays. In addition, we have designed first strategies dealing with multiple explorers. Thanks to the development ofthe Smart Teams Simulator in the second phase, we will be able to experiment with geographic exploration strategies in the third phase. We have furthermore extended and wrapped up our work on collective graph exploration and presented first models and complexity theoretic characterizations for the problem of assigning tasks to robots under locality constraints. Another restraint for autonomous robot movement are energy limitations. We have introduced algorithms to find a path minimizing the energy consumption of movement and communication. Finally, we have started to investigate the localization of mobile targets using only local information. In the new phase, we plan to extend, evaluate, and unify our work. More specifically, we will tackle the following problems: • Exploration: We plan to figure out how to adapt our insights into graph exploration to geographic exploration. This work will partly be experimental, using our Smart Teams Simulator. • Maintaining Communication and Formations: We plan to further investigate how to keep multiple explorer robots connected using mobile relay robots in terrains with obstacles. In addition, we plan to develop new, more realistic cost models for maintaining communication. We have observed that our communication problem for many explorers is closely connected to maintaining formations in flocks of moving objects. We will therefore extend our work in this direction. • Assignment: We plan to develop local algorithms that are able to assign groups of robots to tasks such that the robots are collectively able to solve them. Our complexity theoretic insights show that these problems are hard. Therefore we will try to develop local approximations and will employ new variants of locality models to describe our assignments problems. • Energy Consumption: We plan to further study the optimization of the joint cost for communication and motion that involves multiple mobile relays. Moreover, we want to develop local algorithms that exploit controllable mobility of robots to achieve an overall energy-optimal configuration in Smart Teams. • Unification: In the last phase we will work on combining our results on exploration, communication, assignment, and energy efficiency. E.g., we plan to figure out how far the knowledge about specific movement pattems, as they are given for example by (geographic) exploration strategies, can be used to simplify strategies for maintaining a communication network.“

DFG-Verfahren Schwerpunktprogramme

Teilprojekt zu SPP 1183: Organic Computing

Antragsteller Professor Dr. Friedhelm Meyer auf der Heide; Professor Dr. Christian Schindelhauer