Finding Optimal Solutions to Cooperative Pathfinding Problems

By Trevor Scott Standley. AAAI Conference on Artificial Intelligence, 2010

447 citations recorded by the source corpus.

In cooperative pathfinding problems, non-interfering paths that bring each agent from its current state to its goal state must be planned for multiple agents. We present the first practical, admissible, and complete algorithm for solving problems of this kind. First, we propose a technique called operator decomposition, which can be used to reduce the branching factors of many search algorithms, including algorithms for cooperative pathfinding. We then show how a type of independence common in instances of cooperative pathfinding problems can be exploited. Next, we take the idea of exploiting independent subproblems further by adding improvements that allow the algorithm to recognize many more cases of such independence. Finally, we show empirically that these techniques drastically improve the performance of the standard admissible algorithm for the cooperative pathfinding problem, and that their combination results in a complete algorithm capable of optimally solving relatively large problems in milliseconds.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Mechanical Engineering

View Paper: https://www.semanticscholar.org/paper/2529f40c4f79ef24165dbb1a8327770e37cced2d

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 Mechanical Engineering

Citations in the corpus

Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks (2019, methodology): “Consequently, this problem has received attention in recent years from various research groups and academic communities (Standley 2010; Felner et al. 2017; Surynek et al. 2016; Bart´ak, ˇSvancara, and Vlk 2018; Cohen et al. 2018a; Li et al. 2019; Ma et al. 2019a).”
Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding (2011, background): “We suggest to store these paths in a special compact data structure called multi-value decision diagram (MDD) (Srinivasan et al. 1990).”
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, methodology): “Standley (Standley 2010) presented the independence detection (ID) framework.”
Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics (2015, background): “Such a formulation, more appropriate for multi-robot applications, has not been widely studied (except, e.g. , Standley (2010); Standley and Korf (2011)).”
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (2018, background): “(ODrM*) [22] can further reduce the set of agents for which joint planning is necessary, by breaking it down into independent collision sets, combined with Operator Decomposition (OD) [23] to keep the branching factor small during search.”
Subdimensional expansion for multirobot path planning (2015, methodology): “The limited neighbors V nbhk are the set of neighbors of vk which can be reached from vk when each robot not in the collision set Ck of vk moves according to its individual policy.”
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses (2020, methodology): “Svancara et al. (2019) use the framework of Independence Detection (Standley 2010) to reuse the paths from the previous iteration.”