Time-extended Multi-robot Coordination for Domains with Intra-path Constraints

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.