{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T08:36:13Z","timestamp":1775118973427,"version":"3.50.1"},"reference-count":56,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"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,1]]},"abstract":"<jats:p> Current technological developments and application-driven demands are bringing us closer to the realization of autonomous multi-robot systems performing increasingly complex missions. However, existing methods of distributing mission subcomponents among multirobot teams do not explicitly handle the required complexity and instead treat tasks as simple indivisible entities, ignoring any inherent structure and semantics that such complex tasks might have. These task properties can be exploited to produce more efficient team plans by giving individual robots the ability to come up with new, more localized ways to perform a task; by allowing multiple robots to cooperate by sharing the subcomponents of a task; or both. In this paper, we describe the complex task allocation problem and present a distributed solution for efficiently allocating a set of complex tasks among a robot team. <\/jats:p><jats:p> Complex tasks are tasks that can be solved in many possible ways. In contrast, simple tasks can be accomplished in a straightforward, prescriptive manner. The current scope of our work is currently limited to complex tasks that can be decomposed into multiple subtasks related by Boolean logic operators. Our solution to multirobot coordination for complex tasks extends market-based approaches by generalizing task descriptions into task trees, which allows tasks to be traded in a market setting at variable levels of abstraction. In order to incorporate these task structures into a market mechanism, novel and efficient bidding and auction clearing algorithms are required. As an example scenario, we focus on an area reconnaissance problem which requires sensor coverage by a team of robots over a set of defined areas of interest. The advantages of explicitly modeling complex tasks during the allocation process is demonstrated by a comparison of our approach with existing task allocation algorithms in this application domain. In simulation we compare the quality of solution and the computation times of these different approaches. Implementations on two separate teams of indoor and outdoor robots further validates our approach. <\/jats:p>","DOI":"10.1177\/0278364906061160","type":"journal-article","created":{"date-parts":[[2006,2,2]],"date-time":"2006-02-02T10:03:20Z","timestamp":1138874600000},"page":"73-101","source":"Crossref","is-referenced-by-count":155,"title":["Market-based Multirobot Coordination for Complex Tasks"],"prefix":"10.1177","volume":"25","author":[{"given":"Robert","family":"Zlot","sequence":"first","affiliation":[{"name":"The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213,                         USA,"}]},{"given":"Anthony","family":"Stentz","sequence":"additional","affiliation":[{"name":"The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213,                         USA,"}]}],"member":"179","published-online":{"date-parts":[[2006,1,1]]},"reference":[{"key":"atypb1","volume-title":"Proceedings of the International Conference on Distributed Computing Systems","author":"Andersson, M."},{"key":"atypb2","volume-title":"Proceedings of the 5th ESA Workshop on Advanced Space Technologies for Robotics and Automation","author":"Aylett, R."},{"key":"atypb3","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Berhault, M."},{"key":"atypb4","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Botelho, S. S. C."},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/978-4-431-67919-6_6"},{"key":"atypb6","volume-title":"Proceedings of the IEEE\/RSJ International Workshop on Intelligent Robotics and Systems (IROS)","author":"Caloud, P."},{"key":"atypb7","volume-title":"Proceedings of the AIAA Guidance, Navigation, and Control Conference","author":"Chandler, P."},{"key":"atypb8","first-page":"371","volume":"13","author":"Chao, I.-M.","year":"1993","journal-title":"American Journal of Mathematical and Management Science"},{"key":"atypb9","volume-title":"Proceedings of the 1st International Conference on Autonomous Agents","author":"Chavez, A."},{"key":"atypb10","volume-title":"Introduction to Algorithms","author":"Cormen, T. H.","year":"2001","edition":"2"},{"key":"atypb11","unstructured":"Dias, M. B. 2004. TraderBots: a new paradigm for robust and                 efficient multirobot coordination in dynamic environments. Ph.D. Thesis, Robotics                 Institute, Carnegie Mellon University, January."},{"key":"atypb12","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent RobotsandSystems(IROS)","author":"Dias, M. B."},{"key":"atypb13","volume-title":"Proceedings of the 8th International Conference on Intelligent Autonomous Systems (IAS-8)","author":"Dias, M. B."},{"key":"atypb14","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Dias, M. B."},{"key":"atypb15","author":"Dias, M. B.","year":"2006","journal-title":"Proceedings of the IEEE (Special Issue on Multirobot Coordination)"},{"key":"atypb16","volume-title":"Proceedings of the Symposium on Computer-Communications Networks and Teletraffic","author":"Farber, D. J."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0207017"},{"key":"atypb18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey, M. R.","year":"1979"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2002.803462"},{"key":"atypb20","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Gerkey, B. P."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045564"},{"key":"atypb22","volume-title":"Multi-Robot Systems: From Swarms to Intelligent Automata: Proceedings of the International Workshop on Multi-Robot Systems","author":"Goldberg, D.","year":"2003"},{"key":"atypb23","volume-title":"A task-swap negotiation protocol based on the contract net paradigm","author":"Golfarelli, M.","year":"1997"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90016-I"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/ICMAS.2000.858447"},{"key":"atypb26","volume-title":"Proceedings of the IEEE Conference on Advanced Robotics","author":"Jennings, J."},{"key":"atypb27","volume-title":"Proceedings of the IEEE International Conference on Robotics andAutomation","author":"Kalra, N."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1026"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21708-5"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2005.I.045"},{"key":"atypb31","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Lemaire, T."},{"key":"atypb32","first-page":"367","volume":"40","author":"Laporte, G.","year":"1981","journal-title":"Methods of Operations Research"},{"key":"atypb33","volume-title":"An annotated bibliography of multi-objective combinatorial optimization","author":"Matthias Ehrgott, X. G.","year":"2000"},{"key":"atypb34","volume-title":"RoboCup-2001: The 5th Robot World Cup Games and Conferences","author":"Nair, R."},{"key":"atypb35","volume-title":"Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi-Agent Systems, Utrecht University","author":"Ortiz, C. Jr."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/70.681242"},{"key":"atypb37","volume-title":"Proceedings of the AIAA 1999 Space Technology Conference","author":"Rabideau, G."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1131"},{"key":"atypb39","volume-title":"Proceedings of the 12th International Workshop on Distributed Artificial Intelligence","author":"Sandholm, T."},{"key":"atypb40","volume-title":"AAAI Spring Symposium: Satisficing Models, Stanford University","author":"Sandholm, T."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00159-X"},{"key":"atypb42","volume-title":"Proceedings of the First International Conference on Multi-Agent Systems (ICMAS\u201995)","author":"Sandholm, T."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2000.895304"},{"key":"atypb44","volume-title":"Proceedings of the International Symposium on Experimental Robotics (ISER)","author":"Simmons, R."},{"key":"atypb45","volume-title":"Proceedings of the National Conference on Artificial Intelligence","author":"Simmons, R."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1980.1675516"},{"key":"atypb47","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Stentz, A."},{"key":"atypb48","volume-title":"Proceedings of the 11th International Conference on Advanced Robotics, University of Coimbra","author":"Stroupe, A. W."},{"key":"atypb49","volume-title":"Proceedings of the 3rd International Multi-Robot Systems Workshop, Naval Research Laboratory","author":"Tovey, C."},{"key":"atypb50","volume-title":"Multi-Robot Systems","author":"Vail, D.","year":"2003"},{"key":"atypb51","volume-title":"Approximation Algorithms","author":"Vazirani, V. V.","year":"2001"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(98)00026-8"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1007\/978-4-431-67919-6_33"},{"key":"atypb54","volume-title":"Proceedings of the International Conference on Field and Service Robotics","author":"Zlot, R."},{"key":"atypb55","volume-title":"ProceedingsoftheIEEEInternationalConferenceonRobotics and Automation","author":"Zlot, R."},{"key":"atypb56","volume-title":"Proceedings of the 13th International Joint Conference on Artificial Intelligence","author":"Zlotkin, G."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906061160","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906061160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T00:07:55Z","timestamp":1740960475000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906061160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1177\/0278364906061160"],"URL":"https:\/\/doi.org\/10.1177\/0278364906061160","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}