Enhanced Negotiation and Opportunistic Optimization for Market-Based Multirobot Coordination

Abstract

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.