An Auction-Based Approach to Complex Task Allocation for Multirobot Teams

Robert Michael Zlot
doctoral dissertation, tech. report CMU-RI-TR-06-52, Robotics Institute, Carnegie Mellon University, December, 2006


Download
  • Adobe portable document format (pdf) (6MB)
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 advances and application-driven demands are leading to the development of autonomous multirobot systems able to perform increasingly complex missions. However, existing methods of distributing mission subcomponents among multirobot teams do not explicitly handle this complexity and instead treat tasks as simple indivisible entities, ignoring any inherent structure and semantics that such complex tasks might have. The information contained within task specifications can be exploited to produce more efficient team plans by giving individual robots the ability to come up with innovative and more localized ways to perform a task or enabling multiple robots to cooperate by sharing the subcomponents of a task. In this thesis, we address a generalization of the task allocation problem we call the complex task allocation problem, and present a distributed solution for efficiently allocating a set of complex tasks among a robot team.

Our solution to multirobot coordination for complex tasks extends market-based approaches by generalizing task descriptions into task trees, thereby allowing tasks to be traded in a market setting dynamically at multiple levels of abstraction. In order to incorporate these task structures into a market mechanism, novel and efficient bidding and auction clearing algorithms are required.

Explicitly reasoning about complex tasks presents a tradeoff between solution efficiency and computation time. We analyze that tradeoff for task tree auctions and further introduce a method for dramatically reducing the bidding time without significantly affecting solution quality.

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. We explore this problem in the context of two different team objectives: minimizing the sum of costs and minimizing the makespan. 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 solution quality and computation times of these algorithms. Implementations on teams of indoor and outdoor robots further validate our approach. Finally, we consider additional applications including search and rescue, multirobot object pushing, and area monitoring.


Keywords
multirobot coordination, multiagent coordination, complex tasks, task allocation, task decomposition, auctions, market-based

Notes
Number of pages: 187

Text Reference
Robert Michael Zlot, "An Auction-Based Approach to Complex Task Allocation for Multirobot Teams," doctoral dissertation, tech. report CMU-RI-TR-06-52, Robotics Institute, Carnegie Mellon University, December, 2006

BibTeX Reference
@phdthesis{Zlot_2006_5678,
   author = "Robert Michael Zlot",
   title = "An Auction-Based Approach to Complex Task Allocation for Multirobot Teams",
   booktitle = "",
   school = "Robotics Institute, Carnegie Mellon University",
   address = "5000 Forbes Ave",
   month = "December",
   year = "2006",
   number= "CMU-RI-TR-06-52",
   address= "Pittsburgh, PA",
}