This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Zlot, R. Articles by Stentz, A. Search for Related Content Social Bookmarking                         What's this?

Market-based Multirobot Coordination for Complex Tasks

The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA, robz{at}ri.cmu.edu

Anthony Stentz

The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA, tonyt{at}cmu.edu

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.

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.

Key Words: market-based • multirobot coordination • complex tasks • auctions • task allocation

The International Journal of Robotics Research, Vol. 25, No. 1, 73-101 (2006)
DOI: 10.1177/0278364906061160


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?