Abstract
When a complex mission must be undertaken, it often can be simplified by dividing it into a sequence of smaller subtasks, which are then completed in order. This strategy implicitly requires a system to recognize the completion of each subtask and make the decision to begin work on the next one. Decentralized multiple-robot systems can tackle many tasks, but their behavior is typified by continuous responses to stimuli. Task sequencing, however, demands a controlled, self-induced phase change in collective behavior—working on one task one moment and then on a different task the next—which is nontrivial for an emergent system. The main contribution of this study is a collective decision-making framework for decentralized multiple-robot systems that enables such a system to cooperatively decide that a current task has been completed and thus focus its attention on the next one in a sequence using only anonymous local communication. Central to the framework is the use of consensus, whereby task sequencing is delayed until a prespecified proportion of a system’s robots agree that the current task is complete, reducing the likelihood of premature decisions. Two low-cost consensus estimation strategies are presented, both of which are practical for the extremely simple robots that are expected to compose large decentralized systems. Experiments in simulation and with real robots demonstrate that the proposed decision-making framework performs as predicted. Although the specific application of collective decision-making in this work is the cooperative task-sequencing problem, the proposed decision-making framework potentially has many additional applications.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Anderson, C., & Franks, N. R. (2001). Teams in animal societies. Behavioral Ecology, 12(5), 534–540.
Badgerow, J. P. (1988). An analysis of function in the formation flight of geese. The Auk, 105, 749–755.
Bowling, M., Browning, B., & Veloso, M. (2004). Plays as effective multiagent plans enabling opponent-adaptive play selection. In Proceedings of the fourteenth international conference on automated planning and scheduling (pp. 376–383). Menlo Park: AAAI Press.
Brooks, R. A. (1991). Intelligence without reason. In J. Myopoulos, R. Reiter (Eds.), Proceedings of the 12th international joint conference on artificial intelligence (IJCAI-91) (pp. 569–595). San Mateo: Morgan Kaufmann.
Campbell, J. D., Pillai, P., & Goldstein, S. C. (2005). The robot is the tether: Active, adaptive power routing for modular robots with unary inter-robot connectors. In IEEE/RSJ international conference on intelligent robots and systems (IROS 2005) (pp. 4108–4115). Piscataway: IEEE Press.
Cao, YU, Fukunaga, A. S., & Kahng, A. B. (1997). Cooperative mobile robotics: Antecedents and directions. Autonomous Robots, 4, 1–23.
Chaimowicz, L., Campos, M. F. M., & Kumar, V. (2002). Dynamic role assignment for cooperative robots. In Proc. of the IEEE intl. conf. on robotics and automation (ICRA 2002) (pp. 293–298). Piscataway: IEEE Press.
Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94(7), 1257–1270.
Franks, N. R., & Deneubourg, J. L. (1997). Self-organising nest construction in ants: Individual worker behaviour and the nest’s dynamics. Animal Behaviour, 54, 779–796.
Franks, N. R., Pratt, S. C., Mallon, B. Eamonn, Britton, N. F., & Sumpter, D. J. T. (2002). Information flow, opinion polling and collective intelligence in house-hunting social insects. Philosophical Transactions of the Royal Society of London Series B, 357, 1567–1583.
Garnier, S., Jost, C., Jeanson, R., Gautrais, J., Asadpour, M., Caprari, G., & Theraulaz, G. (2005). Collective decision-making by a group of cockroach-like robots. In Proceedings of the 2nd IEEE swarm intelligence symposium (pp. 233–240). Piscataway: IEEE Press.
Goldberg, D., & Matarić, M. J. (1997). Interference as a tool for designing and evaluating multi-robot controllers. In Proceedings of AAAI 1997 (pp. 637–642). Menlo Park: AAAI Press.
Holland, O. E. (1997). Grey Walter: The pioneery of real artificial life. In C. Langton (Ed.), Proceedings of the 5th international workshop on artificial life (pp. 34–44). Cambridge: MIT Press.
Huntsberger, T., Rodriguez, G., & Schenker, P. S. (2000). Robotics challenges for robotic and human mars exploration. In Proceedings of the fourth international conference and exposition on robotics for challenging situations and environment (ROBOTICS 2000) (pp. 340–346). Reston: ASCE Publications.
Ijspeert, A. J., Martinoli, A., & Billard, A. (2001). Collaboration through the exploitation of local interactions in autonomous collective robotics: the stick pulling experiment. Autonomous Robots, 11(2), 149–171.
Kempe, D., Kleinberg, J., & Demers, A. (2001). Spatial gossip and resource location protocols. In Proceedings of the thirty-third annual ACM symposium on theory of computing (pp. 163–172). New York: ACM.
Krause, J., & Ruxton, G. D. (2002). Living in groups. New York: Oxford University Press. Chap. Spatial heterogeneity of costs and benefits within groups (pp. 73–86).
Kube, C. R., & Zhang, H. (1996). The use of perceptual cues in multi-robot box pushing. In Proceedings of the 1996 IEEE international conference on robotics and automation (pp. 2085–2090). Piscataway: IEEE Press.
Miller, M. B., & Bassler, B. L. (2001). Quorum sensing in bacteria. Annual Review of Microbiology, 55, 165–199.
Nouyan, S., Groß, R., Bonani, M., Mondada, F., & Dorigo, M. (2009). Teamwork in self-organized robot colonies. IEEE Transactions on Evolutionary Computation, 13(4), 695–711.
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007). Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1), 215–233.
Parker, C. A. C. (2009). Collective decision-making in decentralized multiple-robot systems: A biologically inspired approach to making up all of your minds. Ph.D. thesis, University of Alberta, Canada.
Parker, C. A. C., & Zhang, H. (2004). Biologically inspired decision making for collective robotic systems. In Proceedings of the 2004 IEEE/RSJ international conference on intelligent robots and systems (IROS 2004) (pp. 375–380). Piscataway: IEEE Press.
Parker, C. A. C., & Zhang, H. (2006). Collective robotic site preparation. Adaptive Behavior, 14(1), 5–19.
Parker, C. A. C., & 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) (pp. 3730–3735). Piscataway: IEEE Press.
Parker, C. A. C., & Zhang, H. (2008). Consensus-based task sequencing in decentralized multiple-robot systems using local communication. In Proceedings of the 2008 IEEE/RSJ international conference on intelligent robots and systems (IROS 2008) (pp. 1421–1426). Piscataway: IEEE Press.
Parker, C. A. C., & Zhang, H. (2009). Cooperative decision-making in decentralized multiple-robot systems: the best-of-n problem. IEEE/ASME Transactions on Mechatronics, 14(2), 240–251.
Peysakhov, M., Dugan, C., Jodi, P. J., & 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) (pp. 1104–1106). New York: ACM.
Pratt, S. C. (2005). Quorum sensing by encounter rates in the ant Temnothorax albipennis. Behavioral Ecology, 16(2), 488–496.
Schmickl, T., Thenius, R., Moeslinger, C., Radspieler, G., Kernbach, S., Szymanski, M., & Crailsheim (2009). Get in touch: cooperative decision making based on robot-to-robot collisions. Autonomous Agents and Multi-Agent Systems, 18(1), 133–155.
Seeley, T. D., & Visscher, P. K. (2003). Choosing a home: How the scouts in a honey bee swarm perceive the completion of their group decision making. Behavioral Ecology and Sociobiology, 54, 511–520.
TeamBots (2005). TeamBots home page. http://www.teambots.org.
Vlassis, N., Elhorst, R., & Kok, J. R. (2004). Anytime algorithms for multiagent decision making using coordination graphs. In Proceedings of international conference on systems, man and cybernetics (pp. 953–957). Piscataway: IEEE Press.
Waters, C. M., & Bassler, B. L. (2005). Quorum sensing: Cell-to-cell communication in bacteria. Annual Review of Cell and Developmental Biology, 21, 319–346.
Wessnitzer, J., & Melhuish, C. (2003). Collective decision-making and behaviour transitions in distributed ad hoc wireless networks of mobile robots: Target hunting. In Lecture notes in computer science (LNCS) (Vol. 2801, pp. 893–902). Berlin: Springer.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Parker, C.A.C., Zhang, H. Collective unary decision-making by decentralized multiple-robot systems applied to the task-sequencing problem. Swarm Intell 4, 199–220 (2010). https://doi.org/10.1007/s11721-010-0042-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11721-010-0042-8