This paper presents a solution to the problem of self-organized aggregation of embodied robots that requires no arithmetic computation. The robots have no memory and 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. With this controller, robots rotate on the spot when they perceive another robot, and move backwards along a circular trajectory otherwise. 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. Moreover, 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 at scales where conventional approaches to sensing and information processing are no longer applicable.
AndoHOasaYSuzukiI. (1999) Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation15: 818–828.
2.
Ashley-RollmanMPPillaiPGoodsteinML (2011) Simulating multi-million-robot ensembles. In: Proceedings of 2011 IEEE International conference on robotics and automation, Shanghai, China, 9–13 May 2011, pp. 1006–1013.
3.
BahceciEŞahinE (2005) Evolving aggregation behaviors for swarm robotic systems: A systematic case study. In: Proceedings of 2005 IEEE swarm intelligence symposium, Pasadena, CA, USA, 8–10 June 2005, pp. 333–340.
4.
BayindirLŞahinE (2009) Modeling self-organized aggregation in swarm robotic systems. In: Proceedings of 2009 IEEE swarm intelligence symposium, Nashville, TN, USA, 30 March–2 April 2009, pp. 88–95.
5.
BrambillaMFerranteEBirattariM. (2013) Swarm robotics: A review from the swarm engineering perspective. Swarm Intelligence7: 1–41.
6.
BrooksRA (1991) Intelligence without representation. Artificial Intelligence47: 139–159.
7.
CamazineSFranksNRSneydJ. (2001) Self-Organization in Biological Systems. Princeton, NJ: Princeton University Press.
8.
ChowTY (1995) Penny-packings with minimal second moments. Combinatorica15: 151–158.
9.
CieliebakMFlocchiniPPrencipeG. (2003) Solving the robots gathering problem. In: BaetenJLenstraJParrowJ. (eds) Automata, Languages and Programming (Lecture Notes in Computer Science, Vol. 2719). Berlin; Heidelberg: Springer-Verlag, pp. 192–192.
10.
CorrellNMartinoliA (2011) Modeling and designing self-organized aggregation in a swarm of miniature robots. International Journal of Robotics Research30: 615–626.
11.
CortésJMartinezSBulloF (2006) Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Transactions on Automation and Control51: 1289–1298.
12.
DamascenoPFEngelMGlotzerSC (2012) Predictive self-assembly of polyhedra into complex structures. Science337: 453–457.
13.
DeneubourgJLGregoireJCFortEL (1990) Kinetics of larval gregarious behavior in the bark beetle Dendroctonus micans (Coleoptera: Scolytidae). Journal of Insect Behavior3: 169–182.
14.
DorigoMTrianniVŞahinE. (2004) Evolving self-organizing behaviors for a swarm-bot. Autonomous Robots17: 223–245.
15.
DudekGJenkinM (2010) Computational Principles of Mobile Robotics. 2nd edition. New York, NY: Cambridge University Press.
16.
FatèsN (2010) Solving the decentralised gathering problem with a reaction–diffusion–chemotaxis scheme. Swarm Intelligence4: 91–115.
17.
FitchRButlerZ (2008) Million module march: Scalable locomotion for large self-reconfiguring robots. International Journal of Robotics Research27: 331–343.
18.
FlocchiniPPrencipeGSantoroN. (2005) Gathering of asynchronous robots with limited visibility. Theoretical Computer Science337: 147–168.
19.
GarnierSJostCGautraisJ. (2008) The embodiment of cockroach aggregation behavior in a group of micro-robots. Artificial Life14(4): 387–408.
20.
GasparriAOrioloGPrioloA. (2012a) A swarm aggregation algorithm based on local interaction for multi-robot systems with actuator saturations. In: Proceedings of 2012 IEEE/RSJ International conference on intelligent robots and systems, Algarve, Portugal, 7–12 October 2012, pp. 539–544.
21.
GasparriAPrioloAUliviG (2012b) A swarm aggregation algorithm for multi-robot systems based on local interaction. In: Proceedings of 2012 IEEE International conference on control applications, Dubrovnik, Croatia, 3–5 October 2012, pp. 1497–1502.
22.
GauciMChenJDoddTJ. (2012) Evolving aggregation behaviors in multi-robot systems with binary sensors. In: Proceedings of 2012 International symposium on distributed autonomous robotic systems, Baltimore, MD, USA, 8–11 November 2012.
23.
GauciMChenJLiW. (2014) Clustering objects with robots that do not compute. In: Proceedings of 13th International conference on autonomous agents and multiagent systems, Paris, France, 5–9 May 2014.
GazyVPassinoKM (2003) Stability analysis of swarms. IEEE Transactions on Automation and Control48: 692–697.
26.
GennaroMDJadbabieA (2006) Decentralized control of connectivity for multi-agent systems. In: Proceedings of 45th IEEE conference on decision and control, San Diego, CA, USA, 13–15 December 2006, pp. 3628–3633.
GordonNElorYBrucksteinAM (2008) Gathering multiple robotic agents with crude distance sensing capabilities. In: Proceedings of 6th International conference on ant colony optimization and swarm intelligence (Lecture Notes in Computer Science, volume 5217). Berlin; Heidelberg: Springer-Verlag, pp. 72–83.
29.
GordonNWagnerIABrucksteinAM (2004) Gathering multiple robotic a(ge)nts with limited sensing capabilities. In: Proceedings of 4th International Conference on ant colony optimization and Swarm Intelligence (Lecture Notes in Computer Science, Volume 3172). Berlin; Heidelberg: Springer-Verlag, pp. 142–153.
30.
GrahamRLSloaneNJA (1990) Penny-packing and two-dimensional codes. Discrete Computational Geometry5: 1–11.
31.
GroßRDorigoM (2008) Self-assembly at the macroscopic scale. Proceedings of the IEEE96: 1490–1508.
32.
HalloyJSempoGCaprariG. (2007) Social integration of robots into groups of cockroaches to control self-organized choices. Science318: 1155–1158.
33.
JakobiN (1997) Half-baked, ad-hoc and noisy: Minimal simulations for evolutionary robotics. In: Proceedings of the 4th European conference on artificial life. Cambridge, MA: MIT Press, pp. 348–357.
34.
JeansonRRivaultCDeneubourgJL. (2005) Self-organized aggregation in cockroaches. Animal Behavior69: 169–180.
35.
KernbachSHäbeDKernbachO. (2013) Adaptive collective decision-making in limited robot swarms without communication. International Journal of Robotics Research32: 35–55.
36.
KernbachSTheniusRKernbachO. (2009) Re-embodiment of honeybee aggregation behavior in an artificial micro-robotic system. Adaptive Behavior17: 237–259.
37.
KlavinsE (2007) Programmable self-assembly. IEEE Control Systems Magazine27(4): 43–56.
38.
KnuthDE (1997) The Art of Computer Programming. Volume 1: Fundamental Algorithms. 3rd edition. Redwood City, CA: Addison Wesley Longman Publishing Co.
39.
LecceseAGasparriAPrioloA. (2012) A swarm aggregation algorithm based on local interaction with actuator saturations and integrated obstacle avoidance. In: Proceedings of 2013 IEEE/RSJ International conference on intelligent robots and systems, Karlsruhe, Germany, 6–10 May 2013, pp. 1857–1862.
40.
LiW (2008) Stability analysis of swarms with general topology. IEEE Transactions on Systems, Man, and Cybernetics—A: Systems and Humans38: 1084–1097.
41.
LitovskyIMéivierYZielonkaW (1993) The power and limitations of local computations on graphs. In: Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science, Volume 657). Berlin; Heidelberg: Springer-Verlag, pp. 333–345.
42.
MagnenatSWaibelMBeyelerA (2011) Enki: The fast 2D robot simulator. Available at: http://home.gna.org/enki/.
43.
MichelO (2008) Webots: Professional mobile robot simulation. International Journal of Advanced Robotic Systems1(1): 39–42.
44.
MondadaFBonaniMRaemyX. (2009) The e-puck, a robot designed for education in engineering. In: Proceedings of 9th conference on autonomous robot systems and competitions, Volume 1, Castelo Branco, Portugal, 7 May 2009, pp. 59–65.
45.
NolfiSFloreanoD (2000) Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines. Cambridge, MA: MIT Press.
46.
ParkerLE (2008) Multiple mobile robot systems. In: SicilianoBKhatibO (eds) Springer Handbook of Robotics (Springer Handbooks). Berlin; Heidelberg: Springer-Verlag, pp. 921–941.
47.
ParrishJKEdelstein-KeshetL (1999) Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science284: 99–101.
48.
RequichaA (2003) Nanorobots, NEMS, and nanoassembly. Proceedings of the IEEE91: 1922–1933.
49.
SittiM (2007) Microscale and nanoscale robotics systems [grand challenges of robotics]. IEEE Robotics and Automation Magazine14: 53–60.
50.
SoysalOŞahinE (2005) Probabilistic aggregation strategies in swarm robotic systems. In: Proceedings of 2005 IEEE swarm intelligence symposium, Pasadena, CA, USA, 8–10 June 2005, pp. 325–332.
YuJLaValleSLiberzonD (2012) Rendezvous without coordinates. IEEE Transactions on Automation and Control57: 421–434.
53.
ZebrowskiPLitusYVaughanRT (2007) Energy efficient robot rendezvous. In: Proceedings of 4th Canadian conference on computer and robot vision, Montreal, QC, Canada, pp. 139–148.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
