Small robots have limited perception and processing power. This is an inconvenient truth that we have to deal with. With swarm intelligence, however, we can unlock their potential by enabling them to work together.
A novel algorithm for emergent behavior
In a recently published work, available (open access) on the Swarm Intelligence Journal, we proposed a new way to enable swarms of robots with limited knowledge and no communication to arrange into a larger pattern.
How limited were the robots? They were anonymous, without memory, reactive, homogeneous, could not communicate, could not plan ahead, and had no global positioning (no GPS). They did not know anything except the current relative position of their closest neighbors and a knowledge of North. How, then, could we make them form patterns together?
The three rules of swarming
We developed an algorithm that follows three simple and intuitive rules:
- Be safe (avoid collisions)
- Be social (avoid moving away from peers)
- Be happy (stay in desired local states)
The first two rules allow the swarm to reshuffle freely while never separating in multiple groups or experiencing collisions. The third rule tells robots to remain in “desired” states. These are local state observations whereby the agent is “happy”, and thus does not move. The global goal (in this case a pattern) is achieved once all robots are “happy”. They form the pattern by self-organizing into the correct “puzzle-piece” that forms the “puzzle”.
Additionally, the paper introduces a novel verification procedure to check whether the swarm will always achieve its goal when starting from arbitrary initial conditions. The novelty of this procedure is that it analyzes the local state and action space of an agent, meaning that we can verify a global property by a local inspection of the behavior of a single robot, rather than looking at the swarm as a whole.
You can see the algorithm in action in the video below.
What’s next?
With this development, we know that it is possible for the robots to form certain pattern reliably. From here, we can proceed to optimize their behavior further, so as to give them an “instinct” of the best actions to take within the swarm.
Preliminary work in this direction was already presented at the Swarm Intelligence Conference (ANTS), which took place in Rome in October 2018. The conference proceedings can found here, but new developments are already in the making.
Papers
If you are interested to find out more, you can see the full paper below:
Provable self-organizing pattern Formation by a swarm of robots with limited knowledge
Mario Coppola, Jian Guo, Eberhard Gill, Guido C. H. E. de Croon
Swarm Intelligence, February 2019, Springer
Link: https://link.springer.com/article/10.1007/s11721-019-00163-0
Optimization of swarm behavior assisted by an automatic local proof for a pattern formation task
Mario Coppola, Guido C. H. E. de Croon
In: Dorigo M., Birattari M., Blum C., Christensen A., Reina A., Trianni V. (eds) Swarm Intelligence. ANTS 2018. Lecture Notes in Computer Science, vol 11172. Springer, Cham
Link: https://link.springer.com/chapter/10.1007/978-3-030-00533-7_10