{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:59:15Z","timestamp":1776106755832,"version":"3.50.1"},"reference-count":68,"publisher":"SAGE Publications","issue":"9","license":[{"start":{"date-parts":[[2004,9,1]],"date-time":"2004-09-01T00:00:00Z","timestamp":1093996800000},"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":[[2004,9]]},"abstract":"<jats:p> Despite more than a decade of experimental work in multi-robot systems, important theoretical aspects of multi-robot coordination mechanisms have, to date, been largely untreated. To address this issue, we focus on the problem of multi-robot task allocation (MRTA). Most work on MRTA has been ad hoc and empirical, with many coordination architectures having been proposed and validated in a proof-of-concept fashion, but infrequently analyzed. With the goal of bringing objective grounding to this important area of research, we present a formal study of MRTA problems. A domain-independent taxonomy of MRTA problems is given, and it is shown how many such problems can be viewed as instances of other, well-studied, optimization problems. We demonstrate how relevant theory from operations research and combinatorial optimization can be used for analysis and greater understanding of existing approaches to task allocation, and to show how the same theory can be used in the synthesis of new approaches. <\/jats:p>","DOI":"10.1177\/0278364904045564","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T23:08:30Z","timestamp":1094512110000},"page":"939-954","source":"Crossref","is-referenced-by-count":1302,"title":["A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems"],"prefix":"10.1177","volume":"23","author":[{"given":"Brian P.","family":"Gerkey","sequence":"first","affiliation":[{"name":"Artificial Intelligence Lab, Stanford University, Stanford, CA                         94305-9010, 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":[[2004,9,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Agassounon, W. and Martinoli, A. 2002. Amacroscopicmodel of an aggregation experiment using embodied agents in groups of time-varying sizes . Proceedings of the IEEE Conference on System, Man and Cybernetics (SMC), Hammamet, Tunisia, pp. 250\u2013255 .","DOI":"10.1109\/ICSMC.2002.1173419"},{"key":"atypb2","unstructured":"Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Upper Saddle River, NJ ."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00202-T"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"Atamt\u00fcrk, A., Nemhauser, G., and Savelsbergh, M. 1995. A combined lagrangian, linear programming and implication heuristic for large-scale set partitioning problems . Journal of Heuristics 1: 247\u2013259 .","DOI":"10.1007\/BF00127080"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130404"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.20.6.1152"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/1018115"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1287\/inte.20.4.133"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Botelho, S.C. and Alami, R. 1999. M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Detroit, MI, pp. 1234\u20131239 .","DOI":"10.1109\/ROBOT.1999.772530"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1986.1087032"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Brucker, P. 1998. Scheduling Algorithms, 2nd edition. Springer-Verlag, Berlin .","DOI":"10.1007\/978-3-662-03612-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/361011.361064"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199803)45:2<231::AID-NAV7>3.0.CO;2-9"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008855018923"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Castelpietra, C., Iocchi, L., Nardi, D., Piaggio, M., Scalzo,A., and Sgorbissa, A. 2001. Communication and coordination among heterogeneous mid-size players: ART99. Robo Cup 2000, LNAI Vol. 2019, P. Stone, T. Balch, and G. Kraetzschmar, editors. Springer-Verlag, Berlin , pp. 86\u201395.","DOI":"10.1007\/3-540-45324-5_7"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"Chaimowicz, L., Campos, M.F.M., and Kumar, V. 2002. Dynamic role assignment for cooperative robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315, pp. 293\u2013298 .","DOI":"10.1109\/ROBOT.2002.1013376"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Chien, S., Barrett, A., Estlin, T., and Rabideau, G. 2000. A comparison of coordinated planning methods for cooperating rovers . Proceedings of Autonomous Agents, Barcelona, Spain, pp. 100\u2013101 .","DOI":"10.1145\/336595.337057"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"atypb20","unstructured":"Cormen, T.H., Leiserson, C.E., and Rivest, R.L. 1997. Introduction to Algorithms. MIT Press, Cambridge, MA ."},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"Dahl, T.S., Matari\u0107, M.J., and Sukhatme, G.S. 2002. Adaptive spatio-temporal organization in groups of robots . Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Lausanne, Switzerland, September 30\u2013October 4, pp. 1044\u20131049 .","DOI":"10.1109\/IRDS.2002.1041529"},{"key":"atypb22","unstructured":"Deneubourg, J.L., Theraulaz, G., and Beckers, R. 1991. Swarm-made architectures . Proceedings of the European Conference on Artificial Life (ECAL), Paris, France, pp. 123\u2013133 ."},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Dertouzos, M.L. and Mok,A.K. 1983. Multiprocessor on-line scheduling of hard-real-time tasks . IEEE Transactions on Software Engineering 15(12): 1497\u20131506 .","DOI":"10.1109\/32.58762"},{"key":"atypb24","unstructured":"Dias, M.B. and Stentz, A. 2001. A market approach to multi-robot coordination. Technical Report CMU-RI-TR-01-26, The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA ."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"Dias, M.B. and Stentz, A. 2002. Opportunistic optimization for market-based multirobot control . Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Lausanne, Switzerland, September 30\u2013October 4, pp. 2714\u20132720 .","DOI":"10.1109\/IRDS.2002.1041680"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600506"},{"key":"atypb27","unstructured":"Dudek, G., Jenkin, M., and Milios, E. 2002. A taxonomy of multirobot systems. Robot Teams: From Diversity to Polymorphism, T. Balch and L. Parker, editors. A.K. Peters, Natick, MA , pp. 3\u201322."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Emery, R., Sikorski, K., and Balch, T. 2002. Protocols for Collaboration, Coordination, and Dynamic Role Assignment in a Robot Team . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315, pp. 3008\u20133015 .","DOI":"10.1109\/ROBOT.2002.1013689"},{"key":"atypb29","unstructured":"Fukuda, T., Nakagawa, S., Kawauchi, Y., and Buss, M. 1988. Self-organizing robots based on cell structures \u2013 CEBOT . Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Victoria, BC, Canada, pp. 145\u2013150 ."},{"key":"atypb30","unstructured":"Gale, D. 1960. The Theory of Linear Economic Models. McGraw-Hill, New York ."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322090"},{"key":"atypb32","unstructured":"Gat, E. 1998. Three-layer architectures. Artificial Intelligence and Mobile Robots: Case Studies of Successful Robot Systems, D. Kortenkamp, R. P. Bonasso, and R. Murphy, editors. AAAI Press, Menlo Park, CA , pp. 195\u2013210."},{"key":"atypb33","unstructured":"Gerkey, B.P. and Matari\u0107, M.J. 2002a. A market-based formulation of sensor-actuator network coordination . Proceedings of the AAAI Spring Symposium on Intelligent Embedded and Distributed Systems, Palo Alto, CA, pp. 21\u201326 ."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2002.803462"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"Gerkey, B.P. and Matari\u0107, M.J. 2003. Multi-Robot Task Allocation: Analyzing the Complexity and Optimality of Key Architectures . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, pp. 3862\u20133868 .","DOI":"10.1109\/ROBOT.2003.1242189"},{"key":"atypb36","unstructured":"Guestrin, C., Koller, D., and Parr, R. 2001. Multi-agent planning with factored MDPs . Proceedings of Advances in Neural Information Processing Systems (NIPS), Vancouver, Canada, pp. 1523\u20131530 ."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.39.6.657"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90012-4"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"Jennings, J.S. and Kirkwood-Watts, C. 1998. Distributed mobile robotics by the method of dynamic teams. Distributed Autonomous Robotic Systems 3, T. Luth, P. Dario, and H. Worn, editors. Springer-Verlag, New York , pp. 47\u201356.","DOI":"10.1007\/978-3-642-72198-4_5"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"atypb42","doi-asserted-by":"crossref","unstructured":"Klavins, E. 2003. Communication Complexity of Multi-Robot Systems. Algorithmic Foundations of Robotics V, J.D. Boissonnat, J. Burdick, S. Hutchinson, and K. Goldberg, editors. Springer-Verlag, New York , pp. 275\u2013292.","DOI":"10.1007\/978-3-540-45058-0_17"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"Korte, B. and Vygen, J. 2000. Combinatorial Optimization: Theory and Algorithms. Springer-Verlag, Berlin .","DOI":"10.1007\/978-3-662-21708-5"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1177\/105971239300200204"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019633424543"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110208"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500303"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"Matari\u0107, M.J. 1992. Designing emergent behaviors: from local interactions to collective intelligence. From Animals to Animats 2, 2nd International Conference on Simulation of Adaptive Behavior (SAB-92), J.A. Meyer, H. Roitblat, and S. Wilson, editors. MIT Press, Cambridge, MA , pp. 432\u2013441.","DOI":"10.7551\/mitpress\/3116.003.0059"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"Modi, J., Jung, H., Tambe, M., Shen, W.M., and Kulkarni, S. 2001. A dynamic distributed constraint satisfaction approach to resource allocation. Principles and Practice of Constraint Programming\u2014CP 2001, T. Walsh, editor. Springer-Verlag, New York , pp. 685\u2013700.","DOI":"10.1007\/3-540-45578-7_56"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1109\/5.24143"},{"key":"atypb52","doi-asserted-by":"crossref","unstructured":"\u00d8sterg\u00e5rd, E.H., Matari\u0107, M.J., and Sukhatme, G.S. 2001. Distributed multi-robot task allocation for emergency handling . Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Wailea, Hawaii, pp. 821\u2013826 .","DOI":"10.1109\/IROS.2001.976270"},{"key":"atypb53","unstructured":"Parker, L.E. 1994. Heterogeneous Multi-Robot Cooperation, PhD thesis, MIT EECS Department."},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"Parker, L.E. 1995. L-ALLIANCE: A mechanism for adaptive action selection in heterogeneous multi-robot teams. Technical Report ORNL\/TM-13000, Oak Ridge National Laboratory, Knoxville, TN .","DOI":"10.2172\/211400"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1109\/70.681242"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1080\/10798587.1999.10750747"},{"key":"atypb57","unstructured":"Pearce, D.W., editor. 1999. The MIT Dictionary of Modern Economics, 4th edition. MIT Press, Cambridge, MA ."},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00030-1"},{"key":"atypb59","unstructured":"Shehory, O. and Kraus, S. 1996. Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents . Proceedings of the International Conference on Multi-Agent Systems (ICMAS), Kyoto, Japan, pp. 330\u2013337 ."},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00045-9"},{"key":"atypb61","unstructured":"Simon, H.A. 2001. The Sciences of the Artificial, 3rd edition. MIT Press, Cambridge, MA ."},{"key":"atypb62","doi-asserted-by":"crossref","unstructured":"Spletzer, J.R. and Taylor, C.J. 2001. A framework for sensor planning and control with applications to vision guided multi-robot systems . Proceedings of the Computer Vision and Pattern Recognition Conference (CVPR), Kauai, Hawaii, pp. 378\u2013383 .","DOI":"10.1109\/CVPR.2001.990500"},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00025-9"},{"key":"atypb64","unstructured":"Vail, D. and Veloso, M. 2003. Dynamic multi-robot coordination. Multi-Robot Systems: From Swarms to Intelligent Automata, Vol. II, A. Schultz et al., editors. Kluwer Academic, Dordrecht , pp. 87\u201398."},{"key":"atypb65","doi-asserted-by":"crossref","unstructured":"Weigel, T., Auerback, W., Dietl, M., D\u00fcmler, B., Gutmann, J.S., Marko, K., M\u00fcller, K., Nebel, B., Szerbakowski, B., and Thiel, M. 2001. CS Freiburg: Doing the right thing in a group. Robo Cup 2000, LNAI Vol. 2019, P. Stone, T. Balch, and G. Kraetzschmar, editors. Springer-Verlag, Berlin , pp. 52\u201363.","DOI":"10.1007\/3-540-45324-5_4"},{"key":"atypb66","doi-asserted-by":"crossref","unstructured":"Werger, B.B. and Matari\u0107, M.J. 2001. Broadcast of local eligibility for multi-target observation. Distributed Autonomous Robotic Systems 4, L.E. Parker, G. Bekey, and J. Barhen, editors. Springer-Verlag, New York , pp. 347\u2013356.","DOI":"10.1007\/978-4-431-67919-6_33"},{"key":"atypb67","doi-asserted-by":"crossref","unstructured":"Yamauchi, B. 1998. Frontier-based exploration using multiple robots . Proceedings of Autonomous Agents, Minneapolis, MN, pp. 47\u201353 .","DOI":"10.1145\/280765.280773"},{"key":"atypb68","doi-asserted-by":"crossref","unstructured":"Zlot, R., Stentz, A., Dias, M.B., and Thayer, S. 2002. Multi-robot exploration controlled by a market economy . Proceedings of the IEEE International Conferenceon Robotics and Automation (ICRA), Washington, DC, May 11\u201315, pp. 3016\u20133023 .","DOI":"10.1109\/ROBOT.2002.1013690"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045564","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045564","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T08:18:49Z","timestamp":1740989929000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364904045564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":68,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["10.1177\/0278364904045564"],"URL":"https:\/\/doi.org\/10.1177\/0278364904045564","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}