posted on 2002-08-01, 00:00authored byM. Bernardine Dias, Anthony Stentz
Multirobot coordination, if made efficient and robust, promises high impact on automation. The
challenge is to enable robots to work together in an intelligent manner to execute a global task. The market
approach has had considerable success in the multirobot coordination domain. However the implementation
of this approach to date restricts the negotiations to two-party, single-task deals which often forces the task
allocation solution into a local minimum. This report investigates the effects of introducing multi-party and
multi-task negotiations to enhance the market-based approach to multirobot coordination. Multi-party
negotiations are enabled by implementing a combinatorial exchange mechanism, while multi-task
negotiations are accomplished via clustering of tasks in cost space. Presented results show that global costs
can be considerably reduced (on average to within 10% of the optimal solution for the tested scenarios),
and hence task allocation can be considerably improved, by enhancing the negotiation capabilities of the
robots.
This report also investigates the effects of introducing opportunistic optimization with leaders to enhance
market-based multirobot coordination. Leaders are able to optimize within subgroups of robots by
collecting information about their tasks and status, and re-allocating the tasks within the subgroup in a more
profitable manner. The presented work also considers the effects of introducing pockets of centralized
optimization into an otherwise distributed system. The implementations were tested on a variation of the
traveling salesman problem. Presented results show that global costs can be reduced, and hence, task
allocation can be improved, utilizing leaders. Note the presented work only addresses scenarios where
leaders run exchanges to optimize task allocation within a group of robots. Some leaders are also capable
of clustering tasks and hence can conduct combinatorial exchanges. But these are not the only opportunities
for leaders to optimize within the market. It is also possible to have combinatorial exchanges and leaders
as distinct entities within the economy. Leaders could also use other approaches to generate plans for a
subgroup of robots. Finally, a leader could simply act as a means of enabling trade between subgroups of
robots who are otherwise unable to communicate, thus enriching the set of possible trades. Thus, leaders
can enhance the market-based approach by several means including optimizing task-allocation, generating
plans, optimizing plans, and enabling better trade opportunities between groups of traders.