Home > Research

My research focuses on multirobot coordination. I've been working on this for most of the five years or so that I've been at CMU. Specifically, I've been working on distributed market-based coordination. Humans are generally good at distributing work amongst themselves in an efficient manner without much central control over this process. So if we want robots to take over the world any time soon (or at least be more useful), it follows that we could get them to cooperate in a similar manner.

In a market-based approach to multirobot coordination, the robots operate within a virtual economy. The team has a limited set of resources from which to complete a set of tasks. For each task, robots are able to determine the expected costs and revenues and use this information to negotiate (typically through auctions) with one another. For example, a robot can offer a task to some other team members, and if any of them can perform the task at a lower price the task can be subcontracted to the lowest bidder. Each trade therefore not only acts to increase robots' individual profits, but also improves the efficiency of the overall solution.

[ We are organizing a tutorial on auction-based coordination for AAMAS 2006 in May as well as a tutorial and workshop for AAAI in July.]

Our group at CMU has been actively working in this area for several years, starting with the work of Bernardine Dias and my advisor, Tony Stentz [StentzDias99]. Since then, our work has matured into the TraderBots multirobot coordination architecture which has been used on several projects including Cognitive Colonies, FIRE, CTA Robotics, and Treasure Hunt. TraderBots has been used on multiple platforms including ActivMedia Pioneers, E-Gators, and Segways. (A little more history on TraderBots is available on Tony's website, or in Bernardine's thesis).

My thesis research looks at how to efficiently allocate and execute complex tasks within a team. These are tasks that can potentially have multiple solution strategies. Often, this means that a task can be decomposed into subtasks that can be executed by one or more robots on the team. This makes the task allocation problem harder because the robots' costs are now dependent on how tasks are decomposed. Other approaches typically do one of two things when faced with complex tasks: either the complex tasks are allocated to individual robots who then decompose and execute them (allocate-then-decompose); or the tasks are decomposed centrally, and the resulting simple subtasks are then allocated (decompose-then-allocate). Both of these two-stage approaches have their drawbacks in terms of solution quality. In an allocate-then-decompose approach, the robots cannot usually share the execution of a complex task (i.e. multiple robots coordinate by executing different subtasks). Or, if they can, the option of sharing subtasks was not taken into consideration when the task was initially decomposed and assigned, thus some more efficient solutions may not be taken into account. In a decompose-then-allocate approach, the individual costs of the robots is not taken into account when choosing how each task is decomposed since the allocation of the tasks has not been decided yet.

To solve this problem, we have extended TraderBots to incorporate the trading of complex tasks. Tasks can be modeled as task trees, and these trees can be exchanged on the market. When bidding on a tree, robots can place bids at multiple levels of task abstraction. So, as usual, a bid on a simple task is computed by estimating the expected cost of performing it. However, when considering a complex task, a robot has the option of either performing it as decomposed by the auctioneer or decomposing it in some other way. If the robot's own decomposition is more efficient than the auctioneer's, then its bid can reflect the expected cost of its new decomposition. If that robot wins the task, it can perform the task according to the more efficient plan. By having multiple rounds of auctions, the team can explore different plans that require different levels of coordination and choose those that are most efficient. Essentially, the task tree auction mechanism enables a market where both more efficient allocations and more efficient plans can be simultaneously exploited to improve the overall team solution. Our latest paper on this topic can be found here, and a complete list of my publications is here. Movies, animations, and photographs can be found in the multimedia section (coming soon).