{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T18:50:55Z","timestamp":1775587855195,"version":"3.50.1"},"reference-count":33,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p> Dynamic task allocation is an essential requirement for multi-robot systems operating in unknown dynamic environments. It allows robots to change their behavior in response to environmental changes or actions of other robots in order to improve overall system performance. Emergent coordination algorithms for task allocation that use only local sensing and no direct communication between robots are attractive because they are robust and scalable. However, a lack of formal analysis tools makes emergent coordination algorithms difficult to design. In this paper we present a mathematical model of a general dynamic task allocation mechanism. Robots using this mechanism have to choose between two types of tasks, and the goal is to achieve a desired task division in the absence of explicit communication and global knowledge. Robots estimate the state of the environment from repeated local observations and decide which task to choose based on these observations. We model the robots and observations as stochastic processes and study the dynamics of the collective behavior. Specifically, we analyze the effect that the number of observations and the choice of the decision function have on the performance of the system. The mathematical models are validated in a multi-robot multi-foraging scenario. The model's predictions agree very closely with results of embodied simulations. <\/jats:p>","DOI":"10.1177\/0278364906063426","type":"journal-article","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T13:42:43Z","timestamp":1141134163000},"page":"225-241","source":"Crossref","is-referenced-by-count":199,"title":["Analysis of Dynamic Task Allocation in Multi-Robot Systems"],"prefix":"10.1177","volume":"25","author":[{"given":"Kristina","family":"Lerman","sequence":"first","affiliation":[{"name":"Information Sciences Institute University of Southern California Los                         Angeles, CA 90089-0781, USA"}]},{"given":"Chris","family":"Jones","sequence":"additional","affiliation":[{"name":"iRobot Corporation 63 South Ave Burlington, MA 01803"}]},{"given":"Aram","family":"Galstyan","sequence":"additional","affiliation":[{"name":"Information Sciences Institute University of Southern California Los                         Angeles, CA 90089-0781, USA"}]},{"given":"Maja J","family":"Matari\u0107","sequence":"additional","affiliation":[{"name":"Computer Science Department University of Southern California Los                         Angeles, CA 90089-0781, USA"}]}],"member":"179","published-online":{"date-parts":[[2006,3,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Agassounon, W. and Martinoli,A. 2002. Amacroscopic model of an aggregation experiment using embodied agents in groups of time-varying sizes . Proceedings of the IEEE Conference on System, Man and Cybernetics SMC-02, Hammamet, Tunisia, October, pp. 250\u2013255 .","DOI":"10.1109\/ICSMC.2002.1173419"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"Balch, T. 1999. The impact of diversity on performance in multi-robot foraging . Oren Etzioni, J\u00f6rg P.M\u00fcller, and Jeffrey M. Bradshaw (Eds.), Proceedings of the Third International Conference on Autonomous Agents (Agents'99), Seattle, WA, ACM, New York, pp. 92\u201399 , ACM, New York.","DOI":"10.1145\/301136.301170"},{"key":"atypb3","unstructured":"Bojinov, H., Casal, A., and Hogg, T. 2000. Emergent structures in modular self-reconfigurable robots . Proceedings of the International Conference on Robotics and Automation, San Francisco, April 2000, IEEE, Piscataway, NJ."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Dahl, T. S., Matari\u0107, M. J., and Sukhatme, G. S. 2003. Multirobot task-allocation through vacancy chains . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA'03), Taipei, Taiwan, May 2003, pp. 2293\u20132298 .","DOI":"10.1109\/ROBOT.2003.1241935"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"Gerkey, B., Vaughan, R., Stoey, K., Howard, A., Sukhatme, G. and Matari\u0107, M. J. 2001. Most valuable player: A robot device server for distributed control . Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Maui, Hawaii, Oct 2001, pp. 1226\u20131231 .","DOI":"10.1109\/IROS.2001.977150"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045564"},{"key":"atypb7","unstructured":"Goldberg, D., and Matari\u0107, M. J. 2002. Design and evaluation of robust behavior-based controllers for distributed multi-robot collection tasks. Tucker Balch and Lynne E. Parker (Eds.), Robot Teams: From Diversity to Polymorphism, pp. 315\u2013344. A. K. Peters, Wellesley, MA ."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"Haberman, R. 1998. Mathematical Models: Mechanical Vibrations, Population Dynamics, and Traffic Flow. SIAM, Philadelphia, PA .","DOI":"10.1137\/1.9781611971156"},{"key":"atypb9","unstructured":"Huberman, B. A., and Hogg, T. 1988. The behavior of computational ecologies. B. A. Huberman (Ed.), The Ecology of Computation, pp. 77\u2013115, Elsevier (North-Holland), Amsterdam ."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011227210047"},{"key":"atypb11","unstructured":"Jones, C. V., and Matari\u0107, M. J. 2003a. Adaptive task allocation in large-scale multi-robot systems . Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS'03), Las Vegas, NV, October 2003, pp. 1969\u20131974 ."},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Jones, C. V., and Matari\u0107, M. J. 2003b. From local to global behavior in intelligent self-assembly . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA'03), Taipei, Taiwan, September 2003, pp. 721\u2013726 .","DOI":"10.1109\/ROBOT.2003.1241679"},{"key":"atypb13","unstructured":"Kaelbling, L. P. 1990. Learning in embedded systems. Ph.D. Thesis, Stanford University."},{"key":"atypb14","unstructured":"Van Kampen, N. G. 1992. Stochastic Processes in Physics and Chemistry. Elsevier Science, Amsterdam , revised and enlarged edition."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(01)00171-3"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Koenig, N. and Howard, A. 2004. Design and use paradigms for gazebo, an open-source multi-robot simulator . IEEE\/RSJ International Conference on Intelligent Robots and Systems, Sendai, Japan, September 2004, pp. 2149\u20132154 .","DOI":"10.1109\/IROS.2004.1389727"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019633424543"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Lerman, K. and Galstyan, A. 2003a. Agent memory and adaptation in multi-agent systems . In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-2003), Melbourne, Australia, July 2003, pp. 797\u2013803 .","DOI":"10.1145\/860575.860703"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"Lerman, K. and Galstyan, A. 2003b. Macroscopic analysis of adaptive task allocation in robots . In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS-2003), Las Vegas, NV, October 2003, pp. 1951\u20131956 .","DOI":"10.1109\/IROS.2003.1248930"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Lerman, K. and Galstyan, A. 2004. Collectives and design of complex systems. Chapter Two of Paradigms for the Design of Artificial Collectives, pp. 231\u2013256, Springer, New York .","DOI":"10.1007\/978-1-4419-8909-3_10"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1162\/106454601317297013"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"Lerman, K., Martinoli, A., and Galstyan, A. 2005. A review of probabilistic macroscopic models for swarm robotic systems. E. Sahin and W. Spears (Eds.), Swarm Robotics Workshop: State-of-the-Art Survey, Lecture Notes in Computer Science, Vol. 3342, pp. 143\u2013152, Springer, Berlin .","DOI":"10.1007\/978-3-540-30552-1_12"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Li, L., Martinoli, A., and Abu-Mostafa, Y. 2002. Emergent Specialization in Swarm Systems, Lecture Notes in Computer Science, Vol. 2412, pp. 261\u2013266, Springer, Berlin .","DOI":"10.1007\/3-540-45675-9_43"},{"key":"atypb24","unstructured":"Martinoli, A. 1999. Swarm intelligence in autonomous collective robotics: from tools to the analysis and synthesis of distributed control strategies. Ph.D. Thesis No 2069, EPFL."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Martinoli, A., Ijspeert, A. J., and Gambardella, L. M. 1999. A probabilistic model for understanding and comparing collective aggregation mechanisms. D. Floreano, J.D. Nicoud, and F. Mondada (Eds.), Proceedings of the 5th European Conference on Advances in Artificial Life (EC AL-99), September 13\u201317, Lecture Notes in Artificial Intelligence, Vol. 1674, pp. 575\u2013584, Springer, Berlin .","DOI":"10.1007\/3-540-48304-7_77"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008819414322"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/70.681242"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Rus, D. and Vona, M. 1999. Self-reconfiguration planning with compressible unit modules. IEEE International Conference on Robotics and Automation (ICRA99), pp. 2513\u20132520.","DOI":"10.1109\/ROBOT.1999.773975"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"Salemi, B., Shen, W.M., and Will, P. 2001. Hormonecontrolled metamorphic robots. IEEE Transactions on Robotics and Automation (ICRA01), October 2001, pp. 4194\u20134199.","DOI":"10.1109\/ROBOT.2001.933273"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"Sato, Y., and Crutchfield, J. P. 2003. Coupled replicator equations for the dynamics of learning in multiagent systems . Physical Review E67:015206.","DOI":"10.1103\/PhysRevE.67.015206"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"Sugawara, K. and Sano, M. 1997. Cooperative acceleration of task performance: Foraging behavior of interacting multirobots system . Physica D100: 343\u2013354 .","DOI":"10.1016\/S0167-2789(96)00195-9"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02471156"},{"key":"atypb33","unstructured":"Wolpert, D. and Tumer, K. 1999. An introduction to collective intelligence. Technical Report NASA-ARC-IC-99-63, NASA Ames Research Center."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906063426","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906063426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T13:16:43Z","timestamp":1741007803000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906063426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1177\/0278364906063426"],"URL":"https:\/\/doi.org\/10.1177\/0278364906063426","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,3]]}}}