Cooperative Multi-Agent Path Planning
Boris de Wilde · Research Repository (Delft University of Technology) · 2012
Multi-Agent Path Planning is the problem of finding routes between pairs of start and destination vertices in a graph such that these routes are conflict-free in space and time. Application domains usually feature automated vehicles, for example in areas like warehouse management, aircraft taxiing and video games. Finding an optimal set of routes is an NP-hard problem; sub-optimal approaches usually decouple the problem into the problems of finding the individual routes sequentially, where each consecutive problem is constrained by previously determined routes. One of these approaches is the Push and Swap algorithm. The Push and Swap algorithm has been presented as complete for the class of problems in which at least two vertices in the graph do not contain an agent. We demonstrate, however, that there exist instances of this type in which a solution exists, but the Push and Swap algorithm fails to find one. By combining our analysis of the Push and Swap algorithm with results from the literature on the feasibility of finding solutions in the problem of moving `pebbles' over graphs, we present the Push and Rotate algorithm, which is complete for the class of problems in which at least two vertices are unoccupied. The algorithm runs in polynomial time and is presented with a proof of completeness. Furthermore, we present a revised version of an important post-processing operation that makes the algorithm practically usable on large instances.