Market-based Multirobot Coordination for Complex Tasks

Robert Michael Zlot and Anthony (Tony) Stentz
International Journal of Robotics Research, Special Issue on the 4th International Conference on Field and Service Robotics, Vol. 25, No. 1, January, 2006, pp. 73-101.


Download
  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Current technological developments and application-driven demands are bringing us closer to the realization of autonomous multirobot 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.

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.


Keywords
multirobot coordination, market-based, complex tasks

Notes
Sponsor: Army Research Lab
Grant ID: DAAD19-01-2-0012
Associated Center(s) / Consortia: Field Robotics Center
Number of pages: 26

Text Reference
Robert Michael Zlot and Anthony (Tony) Stentz, "Market-based Multirobot Coordination for Complex Tasks," International Journal of Robotics Research, Special Issue on the 4th International Conference on Field and Service Robotics, Vol. 25, No. 1, January, 2006, pp. 73-101.

BibTeX Reference
@article{Zlot_2006_5315,
   author = "Robert Michael Zlot and Anthony (Tony) Stentz",
   editor = "Hajime Asama, Erwin Prassler, Sebastian Thrun, Alex Zelinsky",
   title = "Market-based Multirobot Coordination for Complex Tasks",
   journal = "International Journal of Robotics Research, Special Issue on the 4th International Conference on Field and Service Robotics",
   pages = "73-101",
   publisher = "Sage Publications Ltd.",
   address = "London",
   month = "January",
   year = "2006",
   volume = "25",
   number = "1",
}