Fast and memory-efficient multi-agent pathfinding
Date
2008
Authors
Wang, Ko-Hsin
Botea, Adi
Journal Title
Journal ISSN
Volume Title
Publisher
AAAI Press
Abstract
Multi-agent path planning has been shown to be a PSPACE-hard problem. Running a complete search such as A* at the global level is often intractable in practice, since both the number of states and the branching factor grow exponentially as the number of mobile units increases. 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 (Flow Annotation Replannig), 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 by road networks. The movement along a given row (or column) is restricted to only one direction, avoiding head-to-head collisions. The movement direction alternates from one row (or column) to the next. Additional rules ensure 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 Gate1, a popular commercial computer 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.
Description
Keywords
Keywords: Branching factors; Complete searches; Computer games; Flow restrictions; Global levels; Grid maps; Hard problems; Heuristic procedures; Memory resources; Mobile units; Multi agents; Number of state; Path findings; Path-planning; Plan executions; Re-planni
Citation
Collections
Source
Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008)
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
DOI
Restricted until
2037-12-31
Downloads
File
Description