Carnegie Mellon University
Market-based Coordination of Coupled Robot Systems

Ling Xu and Anthony (Tony) Stentz
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), September, 2011.

  • Adobe portable document format (pdf) (387KB)
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.

Tasks such as street mapping and security surveillance seek a route that traverses a given pace to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for an object. In many cases, the use of multiple robots can greatly improve the performance of these tasks. We assume a prior map is available, but it may be inaccurate due to factors such as occlusion, age, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of environmental coverage with incomplete prior map information using multiple robots.

To utilize related algorithms in graph theory, we represent the environment as a graph and model the coverage problem as a k-Rural Postman Problem where k represents the number of robots. Using this representation, the problem can be solved using a branch-and-bound approach to find an optimal route, and a route division heuristic to separate the route into k pieces. Since the branch-and-bound technique is exponential time, we present an approach to decompose the search problem into subtasks that are distributed among the robots. Using ideas from market-based approaches, we allow the robots to auction particular sections of the problem space to other robots as a way to more evenly divide the work and focus the search. Finally, we evaluate these methods on test graphs in simulation.

Sponsor: Sponsored by the U.S Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement W911NF-10-2-0016 and ONR Contract Number N00014-09-1-1031.
Number of pages: 6

Text Reference
Ling Xu and Anthony (Tony) Stentz , "Market-based Coordination of Coupled Robot Systems," IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), September, 2011.

BibTeX Reference
   author = "Ling Xu and Anthony (Tony) {Stentz }",
   title = "Market-based Coordination of Coupled Robot Systems",
   booktitle = "IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)",
   month = "September",
   year = "2011",
   number= "CMU-RI-TR-",