Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding

By Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner. Symposium on Combinatorial Search, 2011

349 citations recorded by the source corpus.

We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f2c03a38bd6fd672d305221cc56179fe7ae888ee

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 Signal Processing

Citations in the corpus

ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding (2015, neutral): “(4) ICTS+p (Sharon et al. 2013), the best ICTS variant.”
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses (2020, background): “2014; Wagner 2015), and dedicated search-based solvers (Sharon et al. 2013; Barer et al. 2014).”
Searching with Consistent Prioritization for Multi-Agent Path Finding (2018, methodology): “…(Surynek 2015; Yu and LaValle 2013a; Erdem et al. 2013) and dedicated MAPF algorithms (Standley and Korf 2011; Luna and Bekris 2011; Goldenberg et al. 2014; Sharon et al. 2013; Wagner and Choset 2015; Sharon et al. 2015), as described in several surveys (Ma et al. 2016a; Felner et al. 2017).”
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, methodology): “This is a known phenomenon for MAPF on optimal solvers too (Sharon et al. 2013; 2012a; 2012b).”
Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics (2015, background): “recently, increasing cost tree search (ICTS [45]) and conflictbased search (CBS [46]) have further pushed the performance on cycle-free MPP.”
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks (2017, methodology): “Optimal dedicated MAPF algorithms include Independence Detection with Operator Decomposition [22], Enhanced Partial Expansion A* [7], Increasing Cost Tree Search [20], M* [29], and Conﬂict-Based Search [19, 1, 3].”
Subdimensional expansion for multirobot path planning (2015, methodology): “The multirobot path planning problem can be recast as a SAT problem by creating a set of Boolean variables to track the location of each robot, and adding terms to the Boolean formula to enforce collision avoidance, defining a logical formula for which the solver tries to find a valid assignment of ”