Intelligent entities must often make decisions by comparing several candidate alternatives and selecting the best one. This is just as true for autonomous swarms as it is for solitary robots, but to date there has been little work to propose efficient comparison behaviors for autonomous robotic swarms that are not tied to specific environments. In this work, we examine an elegant collective comparison strategy that is used by at least three different species of social insect and adapt it for artificial systems. The behavior is particularly attractive for robotic implementations because it relies only on short range explicit peer-to-peer communication, eliminating the need for chemical trails or other forms of stigmergy. The proposed comparison strategy is proven to converge, and a series of experiments using real robots with noisy sensors is presented that validates our theoretical analysis. Using the proposed behavior, a robotic swarm is able to compare alternatives collectively more accurately than its member robots would be able to individually.
Beckers R., Deneubourg JL and Goss S. ( 1992) Trail laying behaviour during food recruitment in the ant Lasius niger (L.). Insectes Sociaux39: 59-72.
2.
Beckers R., Goss S., Deneubourg JL and Pasteels JM ( 1989) Colony size, communication and ant foraging strategy . Psyche96: 239-256.
3.
Beckers R., Holland OE and Deneubourg J. ( 1994) From local actions to global tasks: Stigmergy and collective robotics. In: Brooks R and Maes P (eds.) Artificial Life IV. MIT Press, 181-189.
4.
Bodi M., Thenius R., Schmickl T. and Crailsheim K. ( 2009) How two cooperating robot swarms are affected by two conflictive aggregation spots. In: Proceedings of European Conference on Artificial Life.
5.
Brutschy A., Scheidler A., Merkle D. and Middendorf M. ( 2008) Learning from house-hunting ants: Collective decision-making in organic computing systems. Lecture Notes in Computer Science5217: 96-107.
6.
Cerny V. ( 1985) A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications45: 41-51.
7.
Deneubourg J. and Goss S. ( 1989) Collective patterns and decision-making. Ethology Ecology & Evolution1: 295-311.
8.
Deneubourg JL, Goss S., Franks NR, Sendova-Franks A., Detrain C. and Chrétien L. ( 1990) The dynamics of collective sorting: Robot-like ants and ant-like robots. In: Proceedings of First International Conference on Simulation of Adaptive Behavior 356-365.
9.
Dorigo M., Di Caro G. and Gambardella LM ( 1999) Ant algorithms for discrete optimization. Artificial Life5: 137-172.
10.
Franks NR, Pratt SC, Mallon B Eamonn, Britton NF and Sumpter DJT ( 2002) Information flow, opinion polling and collective intelligence in house-hunting social insects. Philosophical Transactions of the Royal Society of London Series B357: 1567-1583.
11.
Franks NR and Richardson T. ( 2006) Teaching in tandem-running ants. Nature439: 153.
12.
Fujisawa R., Dobata S., Imamura H. and Matsuno F. ( 2008) Dependency by concentration of pheromone trail for multiple robots. Lecture Notes in Computer Science5217: 283-290.
13.
Garnier S., Gautrais J., Asadpour M., Jost C and Theraulaz G (2009) Self-organized aggregation triggers collective decision making in a group of cockroach-like robots. Adaptive Behavior17: 109-133.
14.
Garnier S., Jost C., Jeanson R., Gautrais J., Asadour M., Caprari G. et al. (2005) Collective decision-making by a group of cockroach-like robots. In: Proceedings of IEEE Swarm Intelligence Symposium 233-240.
15.
Garnier S., Tâche F., Combe M., Grimal A. and Theraulaz G. ( 2007) Alice in pheromone land: An experimental setup for the study of ant-like robots. In: Proceedings of IEEE Swarm Intelligence Symposium 37-44.
16.
Gerkey BP and Mataric M. ( 2003) Multi-robot task allocation: Analyzing the complexity and optimality of key architectures. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2003) 3862-3868.
17.
Halloy J., Sempo G., Caprari G., Rivault C., Asadpour M., Tâche F. et al. (2007) Social integration of robots into groups of cockroaches to control self-organized choices. Science318: 1155-1158.
18.
Holland O. and Melhuish C. ( 1999) Stigmergy, self-organisation, and sorting in collective robotics. Journal of Adaptive Behaviour5: 173-202.
19.
Hseih MA, Halász A., Berman S. and Kumar V. ( 2008) Biologically inspired redistribution of a swarm of robots among multiple sites. Swarm Intelligence2: 121-141.
20.
Kennedy J. and Eberhart R. ( 1995) Particle swarm optimization. In: Proceedings of the 1995 IEEE International Conference on Neural Networks volume 4 1942-1947.
21.
Kernback S., Thenius R., Kernbach O and Schmickl T (2009) Re-embodiment of honeybee aggregation behavior in an artificial micro-robotic system. Adaptive Behavior17: 237-259.
22.
Kok JR, Spaan MTJ and Vlassis N. ( 2003) Multi-robot decision making using coordination graphs . In: Proceedings of the 11th International Conference on Advanced Robotics 1124-1129.
23.
Krieger MJB and Billeter JB ( 2000) The call of duty: Self-organized task allocation in a population of up to twelve mobile robots. Robotics and Autonomous Systems30: 65-84.
24.
Krieger MJB, Billeter JB and Keller L. ( 2000) Ant-like task allocation and recruitment in cooperative robotics. Nature406: 992-995.
25.
Kube CR and Bonabeau E. ( 2000) Cooperative transport by ants and robots. Robotics and Autonomous Systems30: 85-101.
26.
Mallon EB, Pratt SC and Franks NR ( 2001) Individual and collective decision-making during nest site selection by the ant Leptothorax albipennis. Behavioral Ecology and Sociobiology50: 352-359.
27.
Olfati-Saber R., Fax JA and Murray RM ( 2007) Consensus and cooperation in networked multi-agent system . Proceedings of the IEEE95: 215-233.
28.
Parker CAC ( 2009) Collective Decision-Making in Decentralized Multiple-Robot Systems: A Biologically Inspired Approach to Making Up All of Your Minds. PhD thesis, University of Alberta.
29.
Parker CAC and Zhang H. ( 2004a) Biologically inspired decision making for collective robotic systems. In: Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004) 375-380.
30.
Parker CAC and Zhang H. ( 2004b) Collective decision making: A biologically inspired approach to making up all of your minds. In: Proceedings of the 2004 IEEE International Conference on Robotics and Biomimetics (ROBIO 2004) 250-255.
31.
Parker CAC and Zhang H. ( 2006) Collective robotic site preparation. Adaptive Behavior14: 5-19.
32.
Parker CAC and Zhang H. ( 2007) A practical implementation of random peer-to-peer communication for a multiple-robot system. In: Proceedings of the 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2007) 3730-3735.
33.
Parker CAC and Zhang H.(2009) Cooperative decision-making in decentralized multiple-robot systems: the best-of-N problem. IEEE/ASME Transactions on Mechatronics14: 240-251.
34.
Peysakhov M., Dugan C., Jodi PJ and Regli W. ( 2006) Quorum sensing on mobile ad-hoc networks. In: Proceedings of the 5th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006) 1104-1106.
35.
Schmickl T., Thenius R., Moeslinger C., Radspieler G., Kernbach S., Szymanski M. et al. (2009) Get in touch: cooperative decision making based on robot-to-robot collisions. Autonomous Agents and Multi-Agent Systems18: 133-155.
36.
Seeley TD ( 2003) Consensus building during nest-site selection in honey bee swarms: The expiration of dissent. Behavioral Ecology and Sociobiology53: 417-424.
37.
Seeley TD and Buhrman SC ( 2001) Nest-site selection in honey bees: How well do swarms implement the "best-of-n" decision rule? Behavioral Ecology and Sociobiology49: 416-427.
38.
Seeley TD and Visscher PK ( 2003) Choosing a home: How the scouts in a honey bee swarm perceive the completion of their group decision making. Behavioral Ecology and Sociobiology54: 511-520.
39.
TeamBots (2005) Teambots home page. http://www.teambots.org.
40.
Theraulaz G. and Bonabeau E. ( 1995) Modelling the collective building of complex architectures in social insects with lattice swarms. Theoretical Biology177: 381-400.
41.
Vlassis N., Elhorst R. and Kok JR ( 2004) Anytime algorithms for multiagent decision making using coordination graphs. In: Proceedings of International Conference on Systems, Man and Cybernetics.
