Conflict-based search for optimal multi-agent pathfinding

By Guni Sharon, Roni Stern, Ariel Felner, Nathan R Sturtevant. Artificial Intelligence, 2012

1,271 citations recorded by the source corpus.

In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/8a439c7149148925c6fe4991636986d3d6647b11

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

Citations in the corpus

Subdimensional expansion for multirobot path planning (2015, background): “…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 truth values [22, 23, 24, 25, 26].”
Graph Neural Networks for Decentralized Multi-Robot Path Planning (2019, methodology): “Towards this end, we run an expert algorithm: Conflict-Based Search (CBS) [12] (which is a similar approach as taken in [7]).”
Lifelong Multi-Agent Path Finding in Large-Scale Warehouses (2020, methodology): “We evaluate RHCR with various MAPF solvers, namely CA* (Silver 2005) (incomplete and suboptimal), PBS (Ma et al. 2019) (incomplete and suboptimal), ECBS (Barer et al. 2014) (complete and bounded suboptimal), and CBS (Sharon et al. 2015) (complete and optimal).”
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, methodology): “(2) The conflict based search (CBS) (Sharon et al. 2012a) and its extension meta-agent CBS (MA-CBS)(Sharon et al.”
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).”
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 ConflictBased Search [19, 1, 3].”
Trajectory Planning for Quadrotor Swarms (2018, background): “ECBS can be used to solve an unlabeled problem approximately, by finding a goal assignment first.”
Distributed multi-robot collision avoidance via deep reinforcement learning for navigation in complex scenarios (2020, background): “In this way, they can guarantee a safe, optimal, and complete solution for navigation (Luna and Bekris, 2011; Sharon et al., 2015; Tang et al., 2018; Yu and LaValle, 2016).”