Enhanced Negotiation and Opportunistic Optimization for Market-Based Multirobot Coordination

M Bernardine Dias and Anthony (Tony) Stentz
tech. report CMU-RI -TR-02-18, Robotics Institute, Carnegie Mellon University, August, 2002


Download
  • Adobe portable document format (pdf) (138KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.


Keywords
multi-robot, market-based, coordination

Notes
Associated Center(s) / Consortia: Field Robotics Center
Associated Project(s): Cognitive Colonies

Text Reference
M Bernardine Dias and Anthony (Tony) Stentz, "Enhanced Negotiation and Opportunistic Optimization for Market-Based Multirobot Coordination," tech. report CMU-RI -TR-02-18, Robotics Institute, Carnegie Mellon University, August, 2002

BibTeX Reference
@techreport{Dias_2002_4055,
   author = "M Bernardine Dias and Anthony (Tony) Stentz",
   title = "Enhanced Negotiation and Opportunistic Optimization for Market-Based Multirobot Coordination",
   booktitle = "",
   institution = "Robotics Institute",
   month = "August",
   year = "2002",
   number= "CMU-RI -TR-02-18",
   address= "Pittsburgh, PA",
}