Market-based multirobot coordination for complex tasks

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.