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

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.