Home > Research Groups > Algorithms and Complexity > Teaching > Topics about Bachelor, Master Theses > Local Algorithms for Swarm Formations (Smart Teams)

Local Algorithms for Swarm Formations (Smart Teams)

Research > Local Strategies for Global Tasks

Strategies for Building Formations with Robot Swarms

The Scenario

We consider a team of autonomous mobile robots that are deployed in unknown terrain, such as a previously unexplored planet, or even an ocean. Our research aims at developing strategies for the robots in order to cope with the different requirements of a robot team’s mission. A typical task is to explore the environment. Here the question is how the robot team should act in order to explore a terrain with several obstacles. We want the robots to achieve this as quickly as possible. Moreover, the distances traveled by the robots should be as evenly distributed between the robots as possible, in order to have the energy consumption evenly distributed among the robots. Unknown environments typically have no infrastructure which the robots could use to communicate with each other. Therefore the robots need to build their own communication infrastructure, so that the robots communicate directly with each other. The aim is to maintain a communication network between the robots and the base station so that relevant information can be forworded to the base station quickly. Relay robots can be used for this. They place themselves on good positions, so that a short communication network between the robots and the base station is created. If one robot moves, the positions of the relay robots must also be adjusted.

Robots (grey) form a communication network (indicated in red) between fixed stations (black).

Algorithmic Challenge

The major algorithmic challenge is that each robot knows only a very limited area of its environment and therefore is only able to communicate with other robots in its immediate vicinity. Although each robot makes its decisions solely on the basis of incomplete information, the solutions reached on a whole, should be provably good. In addition, these solutions should be reached efficiently, that is either fast or with as little energy consumption as possible.

In the past year we have particularly focused on the question of whether and under which conditions the robots can build formations, given that they only have a local view on their surroundings. We have particularly investigated how fast the robots can gather at one point or build a line between two given points. Additionally, we have analyzed the distance the robots have to cover. The results are highly dependent on the capabilities of the robots that are used. We have focused on investigating algorithms that need as few robot skills as possible.

Strategy of a robot (black) for gathering in one point, based on the relative positions of its neighbors (red). The grey robots cannot be seen from its

An Example

We have for example developed a strategy that allows the mobile robots, of which each can only see neighbors within a fixed circle surrounding their location, to gather at a (not specified) point. They need O(n²) synchronous rounds and no robot moves more than O(n²).

Outlook

For the future we plan to investigate robot formations under dynamics. The question is to what extent formations can be maintained, when certain robots follow a predefined trajectory. An example is a square, with all robots positioned inside the square. If the vertices of the square move along the same trajectory, so that the shape of the square is kept, can the other robots remain within the square while ensuring that the robot network is connected? Furthermore, we want to investigate whether the robots can learn how to behave in certain situations. It is our purpose to guarantee certain quality criteria.