Self-organised aggregation without computation

Abstract

This paper presents a solution to the problem of self-organised aggregation of embodied robots that requires no arithmetic computation.

The robots have no memory. They are equipped with one binary sensor, which informs them whether or not there is another robot in their line of sight. It is proven that the sensor needs to have a sufficiently long range; otherwise aggregation cannot be guaranteed, irrespective of the controller used.

The optimal controller is found by performing a grid search over the space of all possible controllers. This controller is proven to always aggregate two simultaneously-moving robots in finite time, an upper bound for which is provided. Simulations show that the controller also aggregates at least 1000 robots into a single cluster consistently.

In 30 experiments with 40 physical e-puck robots, 98.6% of the robots aggregated into one cluster. The results obtained have profound implications for the implementation of multi-robot systems. A violation of the 'principle of locality' may be the best way to solve problems when the robots are too small to compute.

---

Highlight video

---

Additional analyses

---

Extensions to other behaviours

At the time of writing, we have been able to extend the framework introduced in this work to other collective robotic tasks in simulation.

These are results for circle formation and object clustering. These behaviours are with robots that are memoryless and unable to compute.

Circle formation

Object clustering

---

Videos of physical experiments

Videos of the 30 trials with physical e-puck robots, accelerated to 15 times real time.

Trial 1

Trial 2

Trial 3

Trial 4

Trial 5

Trial 6

Trial 7

Trial 8

Trial 9

Trial 10

Trial 11

Trial 12

Trial 13

Trial 14

Trial 15

Trial 16

Trial 17

Trial 18

Trial 19

Trial 20

Trial 21

Trial 22

Trial 23

Trial 24

Trial 25

Trial 26

Trial 27

Trial 28

Trial 29

Trial 30