Carnegie Mellon University
Time-extended Multi-robot Coordination for Domains with Intra-path constraints

Edward Jones, M Bernardine Dias, and Anthony (Tony) Stentz
Robotics: Science and Systems (RSS), July, 2009.

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

Many applications require teams of robots to cooperatively execute complex tasks. Among these domains are those where successful coordination solutions must respect constraints that occur on the intra-path level. This work focuses on multi-agent coordination for disaster response with intra-path constraints, a compelling application that is not well addressed by current coordination methods. In this domain a group of fire trucks agents attempt to address a number of fires spread throughout a city in the wake of a large-scale disaster. The disaster has also caused many city roads to be blocked by impassable debris, which can be cleared by bulldozer robots. A high-quality coordination solution must determine not only a task allocation but also what routes the fire trucks should take given the intra-path precedence constraints and which bulldozers should be assigned to clear debris along those routes. This work presents two methods for generating time-extended coordination solutions -- solutions where more than one task is assigned to each agent -- for domains with intra-path constraints. While a number of approaches have employed time-extended coordination for domains with independent tasks, few approaches have used time-extended coordination in domains where agents'schedules are interdependent at the path planning level. Our first approach uses tiered auctions and two heuristic techniques, clustering and opportunistic path planning, to perform a bounded search of possible time-extended schedules and allocations. Our second method uses a centralized, non-heuristic, genetic algorithm-based approach that provides higher quality solutions but at substantially greater computational cost. We compare our time-extended approaches with a range of single task allocation approaches in a simulated disaster response domain.

multi-robot coordination, scheduling, path-planning

Sponsor: U.S. Army Research Laboratory
Associated Center(s) / Consortia: Vision and Autonomous Systems Center and Field Robotics Center
Associated Lab(s) / Group(s): rCommerce
Associated Project(s): CTA Robotics

Text Reference
Edward Jones, M Bernardine Dias, and Anthony (Tony) Stentz , "Time-extended Multi-robot Coordination for Domains with Intra-path constraints," Robotics: Science and Systems (RSS), July, 2009.

BibTeX Reference
   author = "Edward Jones and M Bernardine Dias and Anthony (Tony) {Stentz }",
   title = "Time-extended Multi-robot Coordination for Domains with Intra-path constraints",
   booktitle = "Robotics: Science and Systems (RSS)",
   month = "July",
   year = "2009",