Fast and memory-efficient multi-agent pathfinding

Ko Hsin Cindy Wang, Adi Botea

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

    112 Citations (Scopus)

    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 Gate 1, 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.

    Original languageEnglish
    Title of host publicationICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling
    Pages380-387
    Number of pages8
    Publication statusPublished - 2008
    Event18th International Conference on Automated Planning and Scheduling, ICAPS 2008 - Sydney, NSW, Australia
    Duration: 14 Sept 200818 Sept 2008

    Publication series

    NameICAPS 2008 - Proceedings of the 18th International Conference on Automated Planning and Scheduling

    Conference

    Conference18th International Conference on Automated Planning and Scheduling, ICAPS 2008
    Country/TerritoryAustralia
    CitySydney, NSW
    Period14/09/0818/09/08

    Fingerprint

    Dive into the research topics of 'Fast and memory-efficient multi-agent pathfinding'. Together they form a unique fingerprint.

    Cite this