Time-extended multi-robot coordination for domains with intra-path constraints

• Published in: Autonomous robots 2011-01, Vol.30 (1), p.41-56
• Main Authors: Jones, E. Gil, Dias, M. Bernardine, Stentz, Anthony
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Bulldozers; Computer Imaging; Control; Debris; Disasters; Engineering; Fires; Mechatronics; Pattern Recognition and Graphics; Precedence constraints; Robotics; Robotics and Automation; Robots; Tasks; Trucks; Vision
• ISSN: 0929-5593; 1573-7527
• DOI: 10.1007/s10514-010-9202-3

Many applications require teams of robots to cooperatively execute tasks. Among these domains are those in which successful coordination must respect intra-path constraints, which are constraints that occur on the paths of agents and affect route planning. This work focuses on multi-agent coordination for disaster response with intra-path precedence constraints, a compelling application that is not well addressed by current coordination methods. In this domain a group of fire truck agents attempt to address 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. 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.