Cooperative Pathfinding

By David Silver. Artificial Intelligence and Interactive Digital Entertainment Conference, 2005

850 citations recorded by the source corpus.

Cooperative Pathfinding is a multi-agent path planning problem where agents must find non-colliding routes to separate destinations, given full information about the routes of other agents. This paper presents three new algorithms for efficiently solving this problem, suitable for use in Real-Time Strategy games and other real-time environments. The algorithms are decoupled approaches that break down the problem into a series of single-agent searches. Cooperative A* (CA*) searches space-time for a non-colliding route. Hierarchical Cooperative A* (HCA*) uses an abstract heuristic to boost performance. Finally, Windowed Hierarchical Cooperative A* (WHCA*) limits the space-time search depth to a dynamic window, spreading computation over the duration of the route. The algorithms are applied to a series of challenging, maze-like environments, and compared to A* with Local Repair (the current video-games industry standard). The results show that the new algorithms, especially WHCA*, are robust and efficient solutions to the Cooperative Pathfinding problem, finding more successful routes and following better paths than Local Repair A*

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering

View Paper: https://www.semanticscholar.org/paper/03ef7f3a962319a8d97cacb6afa5380948eba1be

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

Citations in the corpus

Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding (2011, background): “MAPF has practical applications in robotics, video games, vehicle routing etc. (Silver 2005; Dresner and Stone 2008).”
Mobile Robot Path Planning in Dynamic Environments Through Globally Guided Reinforcement Learning (2020, methodology): “ECBS andHCA∗ achieve the best performance overall, since they are both centralized approaches that have access to all robots’ trajectory information.”
Finding Optimal Solutions to Cooperative Pathfinding Problems (2010, methodology): “One could also use Reverse Resumable A* (RRA*) (Silver 2005) to fill in the table values, which improved the efficiency of the breadth-first search option by a small additive constant for each agent in our preliminary experiments.”
Subdimensional expansion for multirobot path planning (2015, methodology): “In this paper, we introduce a new framework for multirobot path planning called subdimensional expansion, which initially plans for each robot individually, and then coordinates motion among the robots as needed.”
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, methodology): “A prominent example is the Cooperative A* (CA*) algorithm and its variants HCA* and WHCA* (Silver 2005).”
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks (2017, methodology): “Token Passing (TP) is based on an idea similar to Cooperative A* [21], where agents plan their paths one after the other.”
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses (2020, methodology): “Silver (2005) has already applied this idea to regular MAPF with CA*.”
Graph Neural Networks for Decentralized Multi-Robot Path Planning (2019, methodology): “While coupled approaches are able to ensure the optimality and completeness of the solution, they involve centralized components, and tend to scale poorly with the number of robots [1], [2].”
Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics (2015, methodology): “32 × 32 grids with 20% obstacles are used for evaluation in Silver (2005); Standley and Korf (2011).”
Conflict-based search for optimal multi-agent pathfinding (2012, neutral): “(Silver 2005; Dresner and Stone 2008).”
Searching with Consistent Prioritization for Multi-Agent Path Finding (2018, methodology): “We consider the following algorithms: CBS-H (labeled CBS) is a state-of-theart implementation of CBS (Felner et al. 2018); FIX is a PBS variant with a total priority ordering specified by the order of the agents in the MAPF instances, which simulates CA* (Silver 2005); LH is a PBS variant with a fix”