cs.AIMar 19, 2026

Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions

Authors: Xuemian Wu, Shizhe Zhao, Zhongqiang Ren

Organizations: Shanghai Jiao Tong University, Shanghai, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective start locations to their respective goal locations while minimizing path costs. Most existing MAPF algorithms rely on a common assumption of synchronized actions, where the actions of all agents start at the same time and always take a time unit, which may limit the use of MAPF planners in practice. To get rid of this assumption, Continuous-time Conflict-Based Search (CCBS) is a popular approach that can find optimal solutions for MAPF with asynchronous actions (MAPF-AA). However, CCBS has recently been identified to be incomplete due to an uncountably infinite state space created by continuous wait durations. This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue and can solve MAPF-AA with completeness and solution optimality guarantees. Based on CBS-AA, we also develop conflict resolution techniques to improve the scalability of CBS-AA further. Our test results show that our method can reduce the number of branches by up to 90%.

Figures & tables

Figure 1. A motivating example of MAPF-AA where the yellow car moves fast and the green truck moves slowly in continuous time. The circled numbers show the time points: e.g., in (a), the truck moves from B1 to B2 during the time range [0.0,2.3][0.0,2.3] . This work considers the agent to occupy both ends of an edge when the agent goes through it. As a result, a constraint (as shown in (d)) at B2 with time range [0.0,4.6][0.0,4.6] is imposed on the yellow car to avoid collision as shown in (c).
Figure 2. Toy example for the issues of CCBS.
Figure 3. Three Conflict Types. (a): IN-IN ; (b): OUT-IN ; (c): WAIT-IN
Figure 4. Changes in the search space of low-level after adding constraints. Duration time from AA to BB and from BB to CC are abbreviated as τAB\tau_{AB} and τBC\tau_{BC} . (a) MC ⟨i,A→B,[l,r)⟩m\langle{i},A\rightarrow B,[l,r)\rangle_{m} : before time ll , the interval at which moving from AA to BB can be started is [0,l)[0,l) ; after time rr , the interval is [r,∞)[r,\infty) . (b) WC ⟨i,B,[l,r)⟩w\langle{i},B,[l,r)\rangle_{w} : before time ll , the interval at which an IN in BB can be started is [0,l−τAB)[0,l-\tau_{AB}) and the interval at which an OUT in BB can be started is [τAB,l)[\tau_{AB},l) ; after time rr , the interval about IN in BB is [r−τAB,∞)[r-\tau_{AB},\infty) and the interval about OUT in BB is [r,∞)[r,\infty) ; the safe interval of BB is [0,l)[0,l) and [r,∞)[r,\infty) . (c) OC ⟨i,B,t⟩o\langle{i},B,t\rangle_{o} : before time tt , the interval at which an IN in BB can be started is [0,t−τAB−τBC][0,t-\tau_{AB}-\tau_{BC}] (by Def. 1 , t−τAB−τBCt-\tau_{AB}-\tau_{BC} is included) and the interval at which an OUT in BB can be started is [τAB,t−τBC][\tau_{AB},t-\tau_{BC}] ; after time tt , the interval about IN in BB is [t,∞)[t,\infty) and the interval about OUT in BB is [t+τAB,∞)[t+\tau_{AB},\infty) ; the safe interval of BB is [0,t−τBC)[0,t-\tau_{BC}) and [t+τAB,∞)[t+\tau_{AB},\infty) .
Figure 5. Expanding states in SIPPS-WC. The parent state sps_{p} at vertex vv with safe interval [0,8.29)[0,8.29) can get two child states sc1s_{c1} and sc2s_{c2} at vertex v′v^{\prime} . State sc1s_{c1} has safe interval [1,∞)[1,\infty) (starts moving at t=0t=0 , arrives at v′v^{\prime} at t=1t=1 ) and sc1.cvw=2s_{c1}.c^{w}_{v}=2 . State sc2s_{c2} has safe interval [6.37,∞)[6.37,\infty) (waits at vv , starts moving at t=5.37t=5.37 , arrives at v′v^{\prime} at t=6.37t=6.37 ) and sc2.cvws_{c2}.c^{w}_{v} = 1
Figure 6. Resolve WAIT( jj )-IN( ii ). Rectangular strips are conflicts. Arrows are corresponding constraints. (a) Case 1: t2j<rjt^{j}_{2}<r^{j} . (b) Case 2: t2j≥rjt^{j}_{2}\geq r^{j} .
Figure 7. Search process of CMA for Ex. 1
Figure 8. (a) An example where CMA generates an invalid constraint. (b) By inserting intermediate vertices into the longer edges, the constraint generated by CMA can be valid.
Figure 9. (a)-(d): Success rates of the algorithms. NN is the number of agents. (e)-(h): Min., Avg., and Max. number of high-level nodes expanded by the algorithms, which only counts the cases where all four methods succeed. NN is the number of agents.
Figure 10. Runtime in empty 32×3232\times 32 . NN is the number of agents.
N1015202530
SIPP0.8030.9300.9020.9991.03
SIPPS-WC0.8451.201.371.621.95
Table 1. Comparison of SIPP with SIPPS-WC in terms of average runtime per call (ms).
N2468
SR1.0/1.0/1.01.0/0.96/1.01.0/0.2/0.41.0/0.0/0.0
RT (s)0.009/0.895/0.8950.002/1.52/4.440.082/19.0/49.6-/-
Table 2. Comparison of CMAS with LS-M* in terms of Success Rate (SR) and Avg. Run Time (RT) under different Time Limit (TL). The data are shown in format (CMAS/ LS-M* under TL=30sTL=30s / LS-M* under TL=120sTL=120s ).

Explore similar work

CardsList

  1. AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

    Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianRobust MAPFConflict-Based Search

    Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

  2. Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

    Feb 12, 2026Jiarui Li, Federico Pecora, Runyu Zhang +1Conflict-Based SearchMulti-Agent Path Finding

    Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA, USA · independent contributor

  3. The Cost of Classical Multi-Agent Path Finding

    Oct 7, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path FindingGraph-Based Planning

    Chalmers University of Technology Gothenburg, Sweden