Fast and Memory-Efficient Multi-Agent Pathfinding

All Papers

Multi-agent path planning has been shown to be a PSPACE-hard problem. Running a complete search such as A* at the global level often is intractable in practice, since both the number of states and the branching factor blow up as the number of mobile units increases. Existing approaches to this problem include manually abstracting the search space, when the actual topology allows it, or decomposing the global search into a series of smaller searches, at the price of giving up the completeness and solution optimality. In addition to the inherent difficulty of the problem, in many real-life applications such as computer games, solutions have to be computed in real time, using limited CPU and memory resources. In this paper we introduce FAR, a method for multi-agent path planning on grid maps. When building a search graph from a grid map, FAR implements a flow restriction idea inspired from a real-life two-way road. The movement along a given row (or column) is restricted to only one direction, avoiding head-to-head collisions. The movement direction is flipped from one row (or column) to the next. In effect, the entire map is covered with virtual criss-crossing roads. The flow annotated search graphs that we build are complete in the sense that two locations reachable from each other on the original map remain connected (in both directions) in the graph. After building the search graph, an A* search is independently run for each mobile unit. During plan execution, deadlocks are detected as cycles of units that wait for each other to move. A heuristic procedure for deadlock breaking attempts to repair plans locally, instead of running a larger scale, more expensive replanning step. Experiments are run on a collection of maps extracted from Baldur's Gate, a popular commercial video game. We compare FAR with WHCA*, a recent successful algorithm for multi-agent path planning on grid maps. FAR is shown to run significantly faster, use much less memory, and scale up to problems with more mobile units.