I started to get interested in swarm robotics while searching for a topic for my bachelor’s thesis. In swarm robotics the control of a massive amount of simple agents is considered. Each agent can only act on limited local perception and gains power on cooperation with other agents.
All work has been performed at the Algorithms Group and thus from a rather theoretical point of view. On the other hand, it is no theoretical work as the evaluation mainly focuses on simulation experiments.
Testing swarm algorithms on real hardware is not only expensive in terms of money but also very inefficient. An swarm algorithm has to be tested and tuned very often as the results are often not intuitive. Running an experiment of real hardware does not only involve low level programming and the setup of a huge amount of pieces, but also makes it nearly impossible to analyse bugs that appear not on agent level but on swarm level.
As a part of our bachelor’s thesis, Maximilian Ernestus and I developed the swarm robotic simulator Platypus3000. It is made for rapid prototyping and simple debugging by providing simple visualisation tools. It builds upon the physics engine JBox2D and visualization by Processing. Unfortunately, the simulator is badly documented but has shown to be an efficient tool for us. All further work has been implemented and tested in this simulator.
Assume you have a large swarm of robots with only local communication. The robots are simple such that once they have lost contact to the swarm, they can only find back to the swarm by chance. In this swarm there is a small set of special robots controlled by external forces (or by own goals). E.g. they can be special exploration units. These special robots shall be able to perform their tasks without loosing connection. Thus, all other robots have to make sure the connection between this special robots is preserved even if the environment is dangerous and a high loss of robots is expected. The desired result is somehow a thick steiner tree as can be seen in the figure below.
The main results have been achieved in the bachelor’s thesis by Maximilian Ernestus and me. The thesis can be found on Bachelor’s Thesis - Distributed, scalable algorithmic methods for swarms with multiple leader robots. For this thesis we have been awarded a prize. The following abstract and paper contain a subset of thesis and additional ideas.
A 4-page abstract has been published on the EuroCG 2015.
The actual paper can be found here: Distributed cohesive control for robot swarms: Maintaining good connectivity in the presence of exterior forces - D. Krupke, M. Ernestus, M. Hemmer, S. Fekete - IROS2015
One of the first algorithmic tasks a computer science students is faced with is sorting. A well known result is that classical sorting can be performed in time, e.g. via merge-sort, and this is the best upper bound any sorting algorithm can have. Now assume you have a swarm of scattered robots with limited vision range (e.g. 1m) and you want them to array themselves on a straight line ordered by some intrinsic value (e.g. their ID). How good can you do?
In the paper below we present an approach that achieves a time complexity of , a message (local broadcast) complexity of , and traveled distance per robot (assuming unit-range) for a theoretically perfect robot model (i.e. no collisions (radius zero), no sensing errors, etc.). It is also designed to work with less perfect robots, i.e. positive radius (collisions) and delays. This has been tested in simulation. The range in the experiments in the paper has accidentally been chosen too large. It works also for smaller radii. The approach is not self-stabilizing and thus not practical for unreliable robots. However, we have ideas for a successive approach that is self-stabilizing. Due to the low importance of this problem, a continuation of research for this problem is uncertain.
Triangulation and Networks
My latest work considered robots that can only sense the distance to their neighbors and collisions. By building a triangulation, an artificial structure can be provided that allows the robots to localize themselves. From this triangulation also robots can be removed such that a street network of specific density remains.