Paper deep dive
Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions
Xuemian Wu, Shizhe Zhao, Zhongqiang Ren
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/22/2026, 6:09:55 AM
Summary
The paper introduces Conflict-Based Search with Asynchronous Actions (CBS-AA), an exact algorithm for Multi-Agent Path Finding with Asynchronous Actions (MAPF-AA). It addresses the incompleteness issues found in Continuous-time Conflict-Based Search (CCBS) by implementing new constraint propagation techniques (CSA and CMA) and adapting Safe Interval Path Planning (SIPP) for continuous time, achieving up to 90% reduction in high-level search branches.
Entities (5)
Relation Signals (3)
CBS-AA → solves → MAPF-AA
confidence 100% · CBS-AA... can solve MAPF-AA with completeness and solution optimality guarantees.
CBS-AA → improvesupon → CCBS
confidence 95% · This paper proposes a new method, Conflict-Based Search with Asynchronous Actions (CBS-AA), which bypasses this theoretical issue [of CCBS]
CBS-AA → utilizes → SIPP
confidence 90% · LowLevelPlan adapts Safe Interval Path Planning (SIPP) phillips2011sipp to handle continuous-time.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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%.
Tags
Links
- Source: https://arxiv.org/abs/2603.18866v1
- Canonical: https://arxiv.org/abs/2603.18866v1
Trouble viewing inline? Open PDF directly →
Full Text
49,498 characters extracted from source content.
Expand or collapse full text
ifaamas =false [AAMAS ’26]Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)May 25 – 29, 2026 Paphos, CyprusC. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.) 2026 2026 615 Jiao Tong University Jiao Tong University Jiao Tong University Conflict-Based Search for Multi Agent Path Finding with Asynchronous Actions Xuemian Wu xuemian.wu@sjtu.edu.cn , Shizhe Zhao shizhe.zhao@sjtu.edu.cn and Zhongqiang Ren† zhongqiang.ren@sjtu.edu.cn 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-A). 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-A), which bypasses this theoretical issue and can solve MAPF-A with completeness and solution optimality guarantees. Based on CBS-A, we also develop conflict resolution techniques to improve the scalability of CBS-A further. Our test results show that our method can reduce the number of branches by up to 90%. Key words and phrases: Conflict-based Search; Multi Agent Path Finding; Asynchronous Actions 1. Introduction 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. The environment is often represented by a graph, where vertices represent the locations that the agent can reach, and edges represent actions that transit the agent between two locations. MAPF is NP-hard to solve optimally yu2013structure, and a variety of MAPF planners were developed, ranging from optimal planners sharon2015conflict; wagner2015subdimensional, bounded sub-optimal planners barer2014suboptimal; li2021eecbs, to unbounded sub-optimal planners okumura2022priority; de2013push. A common underlying assumption in these planners is that each action of an agent, either waiting in place or moving to an adjacent vertex, takes the same duration, i.e., a time unit, and the actions of all agents are synchronized, i.e., the action of each agent starts at the same discrete time step. This assumption limits the application of MAPF planners, especially when the agent speeds are different or an agent has to vary its speed when going through different edges (Fig. 1). Figure 1. A motivating example of MAPF-A 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). To bypass this synchronous action assumption, MAPF variants such as Continuous-Time MAPF ANDREYCHUK2022103662, MAPF with Asynchronous Actions (MAPF-A) ren2021loosely, MAPFR walker2018extended were proposed. The major idea in those variants is that, the actions of agents can take different amounts of time, and as a result, the agents may not start and end each of their actions at the same discrete time steps. Among the exact algorithms that can find optimal solutions, Continuous-time Conflict-Based Search (CCBS) ANDREYCHUK2022103662 is a leading approach that extends CBS to handle various action durations. This paper focuses on exact algorithms for MAPF-A, which considers duration conflict ren2021loosely; okumura2021time in the sense that when an agent traverses an edge within a time range, the agent occupies both end vertices of the edge during that time range and no two agents can occupy the same vertex at the same time. CCBS ANDREYCHUK2022103662 can be applied to solve MAPF-A. However, a naive application can lead to incompleteness due to the infinite number of possible durations for the wait action li2025cbs, and may not be able to find a solution even if the instance is solvable. Although the reason for such incompleteness is analyzed li2025cbs, we are not aware of any fix in the literature yet, and this paper provides a possible fix by developing a new exact algorithm called Conflict-Based Search with Asynchronous Actions (CBS-A) for MAPF-A. Besides CCBS ANDREYCHUK2022103662, our prior work has studied scalable yet unbounded sub-optimal algorithms for MAPF-A zhou2025loosely; 2025_SOCS_LSRPstar_ShuaiZhou. In terms of exact algorithms, our prior work developed an A*/M*-based exact algorithm for MAPF-A called Loosely Synchronized M* (LS-M*) ren2021loosely, which often runs slower than CCBS ANDREYCHUK2022103662. Additionally, in MAPF-A, it takes a different amount of time when different agents go through the same edge, or the same agent goes through different edges. Such heterogeneous duration tends to complicate the collision avoidance among the agents, and disables many conflict resolution techniques in CBS for MAPF, which limits the scalability of the exact algorithms for MAPF-A. To improve scalability, we develop constraint propagation techniques based on the agents’ action duration within CBS-A. The intuition behind these techniques is that when two agents collide, we add constraints to the agents to forbid as many actions as possible, and forbid each action as long as possible, so that CBS-A can resolve collisions in fewer iterations. We compare different variants of our CBS-A with the existing CCBS. The results show that with the proposed constraint propagation techniques, the success rate of CBS-A is significantly higher than that of CCBS ANDREYCHUK2022103662, and the number of iterations in high-level is reduced by up to 90%. We also compare our CBS-A with LS-M* ren2021loosely. The results show that CBS-A can find the optimal solution faster, and the costs of the optimal solutions are the same as those of LS-M*. 2. Problem Formulation Let I=1,2,…,NI=\1,2,…,N\ be the index set of N agents, where each i∈Ii∈ I corresponds to a specific agent. The workspace is represented by an undirected graph G=(V,E)G=(V,E), where V is the set of traversable vertices, and E⊂V×VE⊂ V× V. Each edge e=(u,v)∈Ee=(u,v)∈ E represents an action that moves an agent from u to an adjacent vertex v. The travel time of each edge may vary for each agent. Let τi(u,v)∈ℝ≥0τ^i(u,v) _≥ 0 denote the travel time for agent i moving from u to v. All agents can wait at a vertex for an arbitrary amount of time. Let si=(v,t)s^i=(v,t) denote the space-time state of agent i, and let Ai=(s1i,s2i)A^i=(s^i_1,s^i_2) denote a state transition from s1is^i_1 to s2is^i_2. Given Ai=((v1i,t1i),(v2i,t2i))A^i=((v^i_1,t^i_1),(v^i_2,t^i_2)), let vf(Ai),tf(Ai)v_f(A^i),t_f(A^i) and vt(Ai),t(Ai)v_t(A^i),t_t(A^i) denote the space and time components for s1is^i_1 and s2is^i_2, respectively, and let τ(Ai)τ(A^i) denote the duration of AiA^i. For any action, t2i=t1i+τ(Ai)t^i_2=t^i_1+τ(A^i). For a move action, v2iv^i_2 is adjacent to v1iv^i_1, and τ(Ai)=τi(v1i,v2i)τ(A^i)=τ^i(v^i_1,v^i_2) is given by input. For a wait action, we have v1i=v2iv^i_1=v^i_2, and the duration τ(Ai)∈ℝ≥0τ(A^i) _≥ 0 is determined by the planner. We use the same conflict model from existing work ren2021loosely; okumura2021time, as illustrated below. Definition 0 (Duration Occupancy). When agent i performs an action ((v1i,t1i),(v2i,t2i))((v^i_1,t^i_1),(v^i_2,t^i_2)), both v1iv^i_1 and v2iv^i_2 are occupied by i during the action, which is called Duration Occupancy (DO). Specifically, v1iv^i_1 is occupied at time t1it^i_1, v2iv^i_2 is occupied at time t2it^i_2, and both v1i,v2iv^i_1,v^i_2 are occupied during (t1i,t2i)(t^i_1,t^i_2). At any time point, a vertex can only be occupied by at most one agent. Multiple agents are in conflict if they both occupy the same vertex for a non-empty time interval, which is referred to as Duration Conflict (DC). Let πi(vs,vg)=(a0i=(vs,0),a1i,…,aki=(vg,tk))π^i(v_s,v_g)=(a^i_0=(v_s,0),a^i_1,…,a^i_k=(v_g,t_k)) denote a path from vsv_s to vgv_g. The cost of πiπ^i is tkt_k, denoted as g(πi)g(π^i), which is the time point it reaches vgv_g and can permanently stay after tkt_k without conflict. Let Vs,VgV_s,V_g denote the set of start and goal locations of all agents, and vsi∈Vs,vgi∈Vgv_s^i∈ V_s,v_g^i∈ V_g denote the start and goal location of agent i respectively. We assume there is no conflict when all agents stay at their start or goal locations. Multi Agent Path Finding with Asynchronous Action (MAPF-A) P=⟨V,E,Vs,Vg⟩P= V,E,V_s,V_g seeks to find a set of conflict-free paths such that (1) each agent i∈Ii∈ I starts at vsiv_s^i and ends at vgiv_g^i; and (2) minimize the sum of costs (SoC) of all agents’ paths, i.e., min∑i∈Ig(πi) _i∈ Ig(π^i). 3. Preliminaries CBS Conflict-Based Search (CBS) sharon2015conflict is a two-level search algorithm that finds an optimal joint path for MAPF. At the high-level, CBS constructs a search tree and starts with a root node which consists of all agents’ individually optimal path ignoring any conflict. And then CBS selects a specific node that has the smallest g-value (sum of costs), and detects conflicts along the paths of any pair of agents. According to the detected conflict, two constraints are generated corresponding to the two sub-trees. For each of those two constraints, CBS runs a low-level search to find a new path satisfying the constraints. At the low-level, a single-agent planner is invoked to plan an optimal path that satisfies all constraints related to a specific agent. CBS guarantees finding a conflict-free joint path with the minimal sum of costs. CCBS Continue Conflict-Based Search (CCBS) ANDREYCHUK2022103662 is a CBS-based method and can solve the MAPFR problem to optimality. It assumes the travel time for an edge is real-valued and non-uniform, and different edges have different travel times. Therefore, the time is continue and the action of agents is asynchronous. To detect conflicts, CCBS assumes that all agents move in a straight line at a constant speed and detects collisions based on agents’ geometry, such as circles. To resolve conflicts, CCBS adds constraints over pairs of actions and time ranges, instead of location-time pairs. Specifically, for a conflict ⟨(ai,ti),(aj,tj)⟩ (a^i,t^i),(a^j,t^j) , which means that agent i performs action aia^i at tit^i and agent j performs action aja^j at tjt^j, and they collide, CCBS computes for each action an unsafe intervals w.r.t the other’s action. The unsafe interval [ti,tui)[t^i,t_u^i) of (ai,ti)(a^i,t^i) w.r.t. (aj,tj)(a^j,t^j) is the maximal time interval starting from tit^i in which if agent i performs aia^i then it is in conflict with the action (aj,tj)(a^j,t^j). CCBS adds to agent i the constraint ⟨i,ai,[ti,tui)⟩ i,a^i,[t^i,t_u^i) , which means agent i cannot perform action aia^i in the range [ti,tui)[t^i,t_u^i)), and adds to agent j the constraint ⟨j,aj,[tj,tuj)⟩ j,a^j,[t^j,t_u^j) . The low-level solver of CCBS is Constrained Safe Interval Path Planning (CSIPP), where safe intervals for a vertex are computed based on CCBS constraints. In detail, a CCBS constraint ⟨i,awi,[ti,tui)⟩ i,a^i_w,[t^i,t_u^i) about a wait action awia^i_w of vertex v will divide the safe interval of v to two parts: one that ends at tit^i and another that starts at tuit_u^i. If the action amia^i_m is a move action related to edge e=(v,v′)e=(v,v ), CCBS replaces the action amia^i_m with action am′ia^i_m that starts by waiting in v for duration tui−tit_u^i-t^i before moving to v′v^ . CCBS has issues as reported in li2025cbs. CCBS fails to resolve conflicts for wait actions, since the time is continue, there are infinitely many wait actions with duration time τw∈ℝ≥0 _w _≥ 0. The constraint added by branching each time in CCBS only focuses on a specific duration of the wait action, which can lead to infinite number of branching when resolving conflict caused by wait actions. For example, wait action awi=(B,B,2.0)a_w^i=(B,B,2.0) means waiting at vertex B for a duration of 2.02.0, and CCBS adds a constraint ⟨i,awi,[ti,tui)⟩ i,a_w^i,[t^i,t_u^i) to prohibit agent i from performing awia_w^i at time t∈[ti,tui)t∈[t^i,t_u^i). But agent i still can preform wait action aw1i=(B,B,2.01),aw2i=(B,B,2.001),aw3i=(B,B,2.0001)…a_w1^i=(B,B,2.01),a_w2^i=(B,B,2.001),a_w3^i=(B,B,2.0001)... at time t∈[ti,tui)t∈[t^i,t_u^i). So, CCBS may not terminate when there is a wait action. In the open-sourced implementation111https://github.com/PathPlanning/Continuous-CBS, CCBS makes a change when transferring constraints about wait action to low-level solver. For the previous constraint ⟨i,awi,[ti,tui)⟩ i,a^i_w,[t^i,t_u^i) , CSIPP divides the safe interval of B to two parts: [0,ti)[0,t^i) and [tui,∞)[t_u^i,∞), which means that agent i can not perform any wait action a=(B,B,τw),τw∈ℝ≥0a=(B,B, _w), _w _≥ 0 in [ti,tui)[t^i,t_u^i). However, “not perform any wait action a=(B,B,τw),τw∈ℝ≥0a=(B,B, _w), _w _≥ 0 in [ti,tui)[t^i,t_u^i)” is not equivalent to “not perform wait action awi=(B,B,2.0)a^i_w=(B,B,2.0) in [ti,tui)[t^i,t_u^i)”. This inconsistency may miss feasible solutions during branching and can not guarantee completeness and optimality. For the rest of the paper, we refer to this implemented version as CCBS. Figure 2. Toy example for the issues of CCBS. Example 0. As shown in Fig. 2, there are three agents I=1,2,3I=\1,2,3\. The duration of all move actions of agent 11, 22 and 33 is τ1=1τ^1=1, τ2=2τ^2=2 and τ3=3τ^3=3, respectively. In the root node of high-level, agent 22 and 33 have a conflict ⟨(a2,t2=0),(a3,t3=0)⟩ (a^2,t^2=0),(a^3,t^3=0) where a2=(D,D,∞)a^2=(D,D,∞) is a wait action with ∞ duration time, a3=(C,D,3)a^3=(C,D,3) is a move action from C to D. By Def. 1, the unsafe interval of (a2,t2=0)(a^2,t^2=0) w.r.t. (a3,t3=0)(a^3,t^3=0) is [0,3)[0,3) and the unsafe interval of (a3,t3=0)(a^3,t^3=0) w.r.t. (a2,t2=0)(a^2,t^2=0) is [0,∞)[0,∞). By the implementation of CCBS, two constraints are generated, (3,C→D,[0,∞)])(3,C→ D,[0,∞)]) forbids agent 33 to perform action a3a^3 in the range [0,∞)[0,∞) and (2,waitatD,[0,3))(2,wait\;at\;D,[0,3)) forbids agent 22 to perform any wait action a=(D,D,τw),τw∈ℝ≥0a=(D,D, _w), _w _≥ 0 in the range [0,3)[0,3). The sub-trees of both branches do not contain the optimal solution. LS-M* Loosely Synchronized M* (LS-M*) ren2021loosely solves MAPF-A by introducing new search states that include both the locations and the action times of the agents. Similar to A*, LSS iteratively selects states from an open list, expands them to generate successors, prunes those that are either conflicting or less promising, and inserts the remaining ones into the open list for future expansion. This process continues until a conflict-free joint path from the start locations to the goal locations is found for all agents. LS-M* further introduce the idea of subdimensional expansion wagner2015subdimensional into LSS and can handle more agents than LSS. LS-M* is complete and finds an optimal solution for MAPF-A, but can only handle a relatively small number of agents. 4. Method This section proposes Conflict Based Search with Asynchronous Action (CBS-A), which finds an optimal solution for MAPF-A. We first modify CCBS to effectively resolve conflicts and call this modified method Constraint on Single Action (CSA). Then, we use DO to propagate constraints and resolve conflicts efficiently, which we call Constraint on Multiple Actions (CMA). Overview CBS-A (Alg. 1) is similar to CBS with three processes modified: LowLevelPlan, DetectConflict and GenerateConstraints. LowLevelPlan adapts Safe Interval Path Planning (SIPP) phillips2011sipp to handle continuous-time. The numbers associated with safe intervals and constraints are all positive real numbers. We cut safe intervals into continuous time intervals according to the constraints, rather than a set of discrete time steps. DetectConflict detects conflicts in the continuous time range. When there is overlap in the time intervals for two agents to occupy a same vertex, a conflict is returned. In GenerateConstraints, we propose two different conflict resolution methods for MAPF-A, CSA and CMA, as detailed later. Algorithm 1 CBS-A 1:INPUT: G=(V,E)G=(V,E) 2:OUTPUT: a conflict-free joint path π in G. 3:Ωc←∅ _c← , π,g←π,g← LowLevelPlan(Ωc _c) 4:Add Proot,1=(π,g,Ωc)P_root,1=(π,g, _c) to OPEN 5:while OPEN≠∅OPEN≠ do 6: P=(π,g,Ωc)←P=(π,g, _c)← OPEN.pop() 7: cft←cft← DetectConflict(π) 8: if cft=NULLcft=NULL then return π 9: Ω← ← GenerateConstraints(cftcft) 10: for all ωi∈Ωω^i∈ do 11: Ω′=Ωc∪ωi = _c∪\ω^i\ 12: π′,g′←π ,g ← LowLevelPlan(Ω′ ) 13: Add P′=(π′,g′,Ω′)P =(π ,g , ) to OPEN 14: end for 15:end while 16:return failure 4.1. Conflict Detection and Classification For a vertex v, there are three types of actions: IN:Ai|vt(Ai)=vOUT:Ai|vf(Ai)=vWAIT:Ai|vf(Ai)=vt(Ai)=v cases IN:&\A^i|v_t(A^i)=v\\\ OUT:&\A^i|v_f(A^i)=v\\\ WAIT:&\A^i|v_f(A^i)=v_t(A^i)=v\ cases (1) If agent i wants to go through v, it must perform these three actions AIi∈INA^i_I∈ IN, AWi∈WAITA^i_W∈ WAIT and AOi∈OUTA^i_O∈ OUT at v in sequence. Let τ(Ai,v)τ(A^i,v) denote the time interval during which the transition of i occupies vertex v based on Def. 1. If agent i performs AIiA^i_I at t, τ(AIi,v)=(t,t+τ(AIi)]τ(A^i_I,v)=(t,t+τ(A^i_I)], τ(AWi,v)=[t+τ(AIi),t+τ(AIi)+τ(AWi)]τ(A^i_W,v)=[t+τ(A^i_I),t+τ(A^i_I)+τ(A^i_W)] and τ(AOi,v)=[t+τ(AIi)+τ(AWi),t+τ(AIi)+τ(AWi)+τ(AOi)]τ(A^i_O,v)=[t+τ(A^i_I)+τ(A^i_W),t+τ(A^i_I)+τ(A^i_W)+τ(A^i_O)]. If i does not need to wait at v, the duration τ(AWi)τ(A^i_W) is 0 and the wait action AWiA^i_W occupies v only at one time point t+τ(AIi)t+τ(A^i_I). Two agent i and j are in conflict if there is a v such that τ(Ai,v)∩τ(Aj,v)≠∅τ(A^i,v)∩τ(A^j,v)≠ . Let ⟨Ai,Aj,v⟩ A^i,A^j,v denote a duration conflict between agents i and j that both occupy the same vertex v during their actions Ai,AjA^i,A^j. For two agent i and j, we always detect and resolve the earliest conflict between them. We classify all conflicts to be resolved into three types (Fig. 3): • IN-IN: ⟨Ai,Aj,v⟩I A^i,A^j,v _I, where v=vt(Ai)=vt(Aj)v=v_t(A^i)=v_t(A^j); • OUT-IN: ⟨Ai,Aj,v⟩O A^i,A^j,v _O, where v=vt(Ai)=vf(Aj)v=v_t(A^i)=v_f(A^j); • WAIT-IN: ⟨Ai,Aj,v⟩W A^i,A^j,v _W, where v=vt(Ai)=vf(Aj)=vt(Aj)v=v_t(A^i)=v_f(A^j)=v_t(A^j). While there are nine possible combinations of two agents’ actions IN,OUT,WAIT×IN,OUT,WAIT\IN,OUT,WAIT\×\IN,OUT,WAIT\, we only need to consider the combinations that involve IN. Since for any other conflicts OUT,WAIT×OUT,WAIT\OUT,WAIT\×\OUT,WAIT\, an IN must be involved prior to WAIT or OUT and cause a conflict at the same vertex due to DO. From now on, for any conflict between i and j, let i be the agent who performs the IN action, and j may or may not perform IN. Figure 3. Three Conflict Types. (a): IN-IN; (b): OUT-IN; (c): WAIT-IN 4.2. Constraint and Low-level Planner Safe Interval Path Planning (SIPP) phillips2011sipp is often used as the low-level planner in CBS. It constructs a search space with states defined by their vertex and safe time interval, resulting in a graph that generally only has a few states per vertex. SIPP is more efficient than A* in the presence of wait durations and finds an optimal path that avoids any unsafe time intervals. We adapt SIPP to MAPF-A setting by using the following constraints for an agent i, let Ai=((v1i,t1i),(v2i,t2i))A^i=((v^i_1,t^i_1),(v^i_2,t^i_2)): • Motion Constraint (MC) ⟨i,u→v,[l,r)⟩m i,u→ v,[l,r) _m: forbids all move actions AiA^i where v1i=u,v2i=v^i_1=u,v^i_2=v and t1i∈[l,r)t^i_1∈[l,r); • Wait Constraint (WC) ⟨i,v,[l,r)⟩w i,v,[l,r) _w: forbids all wait actions AiA^i where v1i=v^i_1=v and τ(Ai,v)∩[l,r)≠∅τ(A^i,v)∩[l,r)≠ • Occupancy Constraint (OC) ⟨i,v,t⟩o i,v,t _o: forbids all actions (IN, OUT and WAIT) AiA^i where t∈τ(Ai,v)t∈τ(A^i,v); Fig. 4 illustrates how the constraints affect the search space of the low-level planner. Figure 4. Changes in the search space of low-level after adding constraints. Duration time from A to B and from B to C are abbreviated as τAB _AB and τBC _BC. (a) MC ⟨i,A→B,[l,r)⟩m i,A→ B,[l,r) _m: before time l, the interval at which moving from A to B can be started is [0,l)[0,l); after time r, the interval is [r,∞)[r,∞). (b) WC ⟨i,B,[l,r)⟩w i,B,[l,r) _w: before time l, the interval at which an IN in B can be started is [0,l−τAB)[0,l- _AB) and the interval at which an OUT in B can be started is [τAB,l)[ _AB,l); after time r, the interval about IN in B is [r−τAB,∞)[r- _AB,∞) and the interval about OUT in B is [r,∞)[r,∞); the safe interval of B is [0,l)[0,l) and [r,∞)[r,∞). (c) OC ⟨i,B,t⟩o i,B,t _o: before time t, the interval at which an IN in B can be started is [0,t−τAB−τBC][0,t- _AB- _BC] (by Def. 1, t−τAB−τBCt- _AB- _BC is included) and the interval at which an OUT in B can be started is [τAB,t−τBC][ _AB,t- _BC]; after time t, the interval about IN in B is [t,∞)[t,∞) and the interval about OUT in B is [t+τAB,∞)[t+ _AB,∞); the safe interval of B is [0,t−τBC)[0,t- _BC) and [t+τAB,∞)[t+ _AB,∞). In the low-level planner of CBS sharon2015conflict, tie-breaking is a useful method to find conflict-free solutions faster. It can find an optimal path for agent i that satisfies the constraints added by high-level and has fewer conflicts with the planned paths of other agents. SIPPS li2022mapf extends SIPP to consider other paths as soft constraints and breaks ties by preferring the path that has fewer soft conflicts (i.e., conflicts with soft constraints). But SIPPS ignores the cases where an agent may encounter multiple soft conflicts if it waits within a safe interval. To consider these cases, we propose SIPPS with Waiting Conflict (SIPPS-WC) to consider the soft conflicts when waiting. Specifically, a state s=(v,t,th,cvw)s=(v,t,t_h,c_v^w) in SIPPS-WC consists of a vertex v, an arrival time t, an end time of the corresponding safe interval tht_h, and an integer number cvwc_v^w indicating the number of soft conflicts if waiting at v from t to tht_h. As shown in Fig. 5, cvwc_v^w can help distinguish between a path that moves from v to v′v and then waits at v′v and another path that waits at v and then moves to v′v . To prune states, if two states s1s_1 and s2s_2 have the same v, tht_h and cvwc_v^w, then s1s_1 dominants s2s_2 if the arrival time s1.t≤s2.ts_1.t≤ s_2.t and the number of soft conflicts along the path from the start vertex to v c(s1)≤c(s2)c(s_1)≤ c(s_2). Our low-level planner adapts SIPPS-WC to continuous time and the three types of constraints as aforementioned (Fig. 5). Figure 5. Expanding states in SIPPS-WC. The parent state sps_p at vertex v with safe interval [0,8.29)[0,8.29) can get two child states sc1s_c1 and sc2s_c2 at vertex v′v . State sc1s_c1 has safe interval [1,∞)[1,∞) (starts moving at t=0t=0, arrives at v′v at t=1t=1) and sc1.cvw=2s_c1.c^w_v=2. State sc2s_c2 has safe interval [6.37,∞)[6.37,∞) (waits at v, starts moving at t=5.37t=5.37, arrives at v′v at t=6.37t=6.37) and sc2.cvws_c2.c^w_v = 1 4.3. Constraints on Single Action (CSA) Let Ai=((v1i,t1i),(v2i,t2i))A^i=((v^i_1,t^i_1),(v^i_2,t^i_2)) and Aj=((v1j,t1j),(v2j,t2j))A^j=((v^j_1,t^j_1),(v^j_2,t^j_2)). In an IN-IN conflict ⟨Ai,Aj,v⟩I A^i,A^j,v _I, if we permit j’s current action, then i cannot perform its action during the time interval [li=t1i,ri=t2j)[l^i=t^i_1,r^i=t^j_2). Here, setting li=t1il^i=t^i_1 eliminates the current action of i, as the conflict has been detected. Let ri=t2jr^i=t^j_2, since j occupies v in (t1j,t2j](t^j_1,t^j_2] and i occupies v in (t2j,t2j+τ(Ai)](t^j_2,t^j_2+τ(A^i)] (Def. 1). Similar reasoning applies to an OUT-IN conflict. Constraints for both IN-IN and OUT-IN conflicts are denoted as Eq. 2. In a WAIT-IN conflict ⟨Ai,Aj,v⟩W A^i,A^j,v _W, we simply add constraints to forbid agents to occupy v at a time point tr=min(t2i,t2j)t_r= (t^i_2,t^j_2). All constraints are denoted as Eq. 3. ⟨i,v1i→v2i,[t1i,t2j)⟩m⟨j,v1j→v2j,[t1j,t2i)⟩m cases i,v^i_1→ v^i_2,[t^i_1,t^j_2) _m\\ j,v^j_1→ v^j_2,[t^j_1,t^i_2) _m\\ cases (2) ⟨i,v,tr⟩o⟨j,v,tr⟩o cases i,v,t_r _o\\ j,v,t_r _o\\ cases (3) Remark 0. The difference between CSA and CCBS lies in the constraints on WAIT actions. CCBS adds a constraint to a specific WAIT action, while CSA adds a constraint to a vertex v, which forbids all actions that occupy v. The constraints in CSA avoid the problem about infinitely many wait actions. 4.4. Constraints on Multiple Actions (CMA) For a specific vertex v, e1=(u1,v)∈Ee_1=(u_1,v)∈ E and e2=(u2,v)∈Ee_2=(u_2,v)∈ E, the travel time for agent i, τi(u1,v)τ^i(u_1,v), can be different from τi(u2,v)τ^i(u_2,v). Let τini(v),τouti(v) _in^i(v), _out^i(v) denote the minimum travel time of i’s IN and OUT at v, i.e., τini(v)=mine=(u,v)∈E(τi(u,v)) _in^i(v)= _e=(u,v)∈ E(τ^i(u,v)) and τouti(v)=mine=(v,u)∈E(τi(v,u)) _out^i(v)= _e=(v,u)∈ E(τ^i(v,u)). If agent i starts to perform an IN in v at t, it occupies v at least (t,t+τini(v)+τouti(v))(t,t+ _in^i(v)+ _out^i(v)). If agent i starts to perform a WAIT or OUT in v at t, it occupies v at least (t−τini(v),t+τouti(v))(t- _in^i(v),t+ _out^i(v)). CMA uses such DO to propagate constraints to multiple actions and time intervals. Resolve IN(j)-IN(i) To permit j’s action, we add a constraint on i to forbid all IN actions starting within the time interval [t1i,t1j+τinj+τoutj)[t^i_1,t^j_1+ _in^j+ _out^j), where t1j+τinj+τoutjt^j_1+ _in^j+ _out^j represents the earliest time point for j to leave v if starting to perform an IN in v at t1jt^j_1. The same strategy is applicable for i: ⟨i,∗→v2i,[t1i,t1j+τinj+τoutj)⟩m⟨j,∗→v2j,[t1j,t1i+τini+τouti)⟩m cases i,*→ v^i_2,[t^i_1,t^j_1+ _in^j+ _out^j) _m\\ j,*→ v^j_2,[t^j_1,t^i_1+ _in^i+ _out^i) _m\\ cases (4) Resolve OUT(j)-IN(i) To permit j’s action, we add a constraint on i to forbid all IN actions starting within the time interval [t1i,t1j+τoutj)[t^i_1,t^j_1+ _out^j). To permit i’s action, multiple constraints on j are added to forbid all OUT actions starting within the time interval T=[t1j,t1i+τini+τouti+τinj)T=[t^j_1,t^i_1+ _in^i+ _out^i+ _in^j), and forbid WAIT actions that occupy v at any time point in T. ⟨i,∗→v,[t1i,t1j+τoutj)⟩m i,*→ v,[t^i_1,t^j_1+ _out^j) _m (5) ⟨j,v,[t1j,t1i+τini+τouti+τinj)⟩w∪⟨j,v→∗,[t1j,t1i+τini+τouti+τinj)⟩m array[]c j,v,[t^j_1,t^i_1+ _in^i+ _out^i+ _in^j) _w&∪\\ j,v→*,[t^j_1,t^i_1+ _in^i+ _out^i+ _in^j) _m& array (6) Here, [t1i,t1j+τoutj)[t^i_1,t^j_1+ _out^j) allows i to either start the IN earlier than t1it^i_1, or after the earliest time when j’s OUT finishes (≥t1j+τoutj≥ t^j_1+ _out^j). t1i+τini+τoutit^i_1+ _in^i+ _out^i is the earliest time point that i finishes an OUT action to leave v, and t1i+τini+τouti+τinjt^i_1+ _in^i+ _out^i+ _in^j is the earliest time point that j finishes the IN to reach v, so that j can start to perform a WAIT or OUT afterwards. Resolve WAIT(j)-IN(i) Due to the existence of WAIT action and the variable duration of WAIT action, this case requires extra care on the time interval of constraints. We first show the form of constraints, then we discuss how to properly set the time interval of constraints. Overall, we add a constraint on i to forbid all IN actions starting within the time interval Ti=[li,ri)T^i=[l^i,r^i), or to forbid j’s WAIT to occupy v for at any time point in Tj=[lj,rj)T^j=[l^j,r^j), where Ti,TjT^i,T^j depend on the duration of j’s WAIT action. Similar to Eq. 6, to permit i’s action, t1i+τini+τouti+τinjt^i_1+ _in^i+ _out^i+ _in^j is a critical time point. t1i+τini+τoutit^i_1+ _in^i+ _out^i is the earliest time point at which agent i leaves the conflict vertex v. Then agent j can start the IN action, arriving at t1i+τini+τouti+τinjt^i_1+ _in^i+ _out^i+ _in^j, and performs a WAIT. Therefore, t1i+τini+τouti+τinjt^i_1+ _in^i+ _out^i+ _in^j is the earliest time point that j can start to perform a WAIT without conflicting with i. We set rj=t1i+τini+τouti+τinjr^j=t^i_1+ _in^i+ _out^i+ _in^j. To permit j’s action, t2j+τoutjt^j_2+ _out^j is a critical time point. t2j+τoutjt^j_2+ _out^j is the earliest time point at which agent j leaves the conflict vertex v. Therefore, t2j+τoutjt^j_2+ _out^j is the earliest time point that i can start to perform a IN without conflicting with j. rir^i should be equal to t2j+τoutjt^j_2+ _out^j. As illustrated in Fig. 4, we can set li=t1il^i=t^i_1 and lj∈[t1j,t2j]l^j∈[t^j_1,t^j_2] to make the constraints affect the relevant actions. To resolve conflicts efficiently without eliminating potential solutions and impacting completeness, we set lj=t2jl^j=t^j_2. Now, we have lj=t2jl^j=t^j_2, rj=t1i+τini+τouti+τinjr^j=t^i_1+ _in^i+ _out^i+ _in^j, li=t1il^i=t^i_1 and ri=t2j+τoutjr^i=t^j_2+ _out^j, where t1it^i_1 is the start time of the IN action and t2jt^j_2 is the end time of the WAIT action. However, due to the uncertain duration of WAIT action, the end time point t2jt^j_2 may be very large, which can result in lj>rjl^j>r^j and thus invalidate the interval TjT^j. When t2jt^j_2 is large, special care is needed. If t2j≥t1i+τini+τouti+τinjt^j_2≥ t^i_1+ _in^i+ _out^i+ _in^j, j performs a long WAIT. The long wait action is divided into two consecutive short WAIT actions. The start and end times of the first short WAIT action are t1j′=t1jt^j_1 =t^j_1 and t2j′=t1i+τini+τoutit^j_2 =t^i_1+ _in^i+ _out^i respectively. The start and end times of the second short WAIT action are t1j′=t1i+τini+τoutit^j_1 =t^i_1+ _in^i+ _out^i and t2j′=t2jt^j_2 =t^j_2 respectively. We first resolve the conflict between j’s first short WAIT action and i’s IN action, using the above idea. Therefore, we have lj=t2j′l^j=t^j_2 , rj=t1i+τini+τouti+τinjr^j=t^i_1+ _in^i+ _out^i+ _in^j, li=t1il^i=t^i_1 and ri=t2j′+τoutjr^i=t^j_2 + _out^j, where t1it^i_1 is the start time of the IN action and t2j′t^j_2 is the end time of the first short WAIT action. Figure 6. Resolve WAIT(j)-IN(i). Rectangular strips are conflicts. Arrows are corresponding constraints. (a) Case 1: t2j<rjt^j_2<r^j. (b) Case 2: t2j≥rjt^j_2≥ r^j. In summary, there are two cases: Case 1 (Fig. 6 (a)): t2j<rjt^j_2<r^j ⟨i,∗→v,[t1i,t2j+τoutj)⟩m⟨j,v,[t2j,t1i+τini+τouti+τinj)⟩w cases i,*→ v,[t^i_1,t^j_2+ _out^j) _m\\ j,v,[t^j_2,t^i_1+ _in^i+ _out^i+ _in^j) _w cases (7) Case 2 (Fig. 6 (b)): t2j≥rjt^j_2≥ r^j ⟨i,∗→v,[t1i,t1i+τini+τouti+τoutj)⟩m⟨j,v,[t1i+τini+τouti,t1i+τini+τouti+τinj)⟩w cases i,*→ v,[t^i_1,t^i_1+ _in^i+ _out^i+ _out^j) _m\\ j,v,[t^i_1+ _in^i+ _out^i,t^i_1+ _in^i+ _out^i+ _in^j) _w cases (8) Note that conflict resolution in Case 2 needs multiple iterations to permit j’s long WAIT action. In the first iteration, after adding the constraint of case 2, the start time of i’s IN action is delayed to permit j’s first short WAIT action. Then in the second iteration, we have a conflict between j’s second short WAIT action and i’s delayed IN action. After a finite number of iterations, case 2 will return to case 1, and finally the entire long WAIT action of j is permitted. Figure 7. Search process of CMA for Ex. 2 Example 0. Following Ex. 2, Fig. 7 shows the search process of CMA. CMA can eventually find an optimal solution. Four key conflicts need to be resolved. The first conflict is ⟨Ai,Aj,v⟩W A^i,A^j,v _W, where i=3i=3, j=2j=2, Ai=((C,0),(D,3))A^i=((C,0),(D,3)) and Aj=((D,0),(D,∞))A^j=((D,0),(D,∞)). The second conflict is ⟨Ai,Aj,v⟩O A^i,A^j,v _O, where i=2i=2, j=1j=1, Ai=((D,0),(E,2))A^i=((D,0),(E,2)) and Aj=((E,0),(B,1))A^j=((E,0),(B,1)). The third conflict is ⟨Ai,Aj,v⟩W A^i,A^j,v _W, where i=3i=3, j=2j=2, Ai=((C,0),(D,3))A^i=((C,0),(D,3)) and Aj=((D,0),(D,1))A^j=((D,0),(D,1)). The fourth conflict is ⟨Ai,Aj,v⟩O A^i,A^j,v _O, where i=2i=2, j=3j=3, Ai=((E,6),(D,8))A^i=((E,6),(D,8)) and Aj=((D,6),(A,9))A^j=((D,6),(A,9)). 4.5. Discussion on CMA and CSA For each constraint generated in CMA and CSA, the end time r of the time interval in that constraint must be no smaller than the start time l of the time interval. Otherwise, the interval and the constraint are invalid. It is easy to verify that r is not smaller than l in the constraints of CSA. But Eq. 4, Eq. 5 and Eq. 6 of CMA may result in r being smaller than l due to the differences in travel time. Example 0. As shown in Fig. 8 (a), the conflict is ⟨Ai,Aj,v⟩I A^i,A^j,v _I, where i=1i=1, j=2j=2, Ai=((A,5),(B,11))A^i=((A,5),(B,11)) and Aj=((D,10.5),(B,11.5))A^j=((D,10.5),(B,11.5)). According to Eq. 4, the constraint added to agent j is ⟨j,∗→B,[10.5,9)⟩m j,*→ B,[10.5,9) _m, which is invalid. 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. If the following assumption holds, then r is always greater than l for any generated constraint in CMA. Assumption 1. For each agent i∈Ii∈ I, the duration for i to traverse any edge e∈Ee∈ E is the same constant real number. This constant can be different for different agents. In practice, Assumption 1 can be satisfied by inserting intermediate vertexes into the longer edges (as shown in Fig. 8 (b)) and Keeping agents moving at constant speeds. The grid world used for path planning in an automated warehouse is a common example. By Assumption 1, all edges linked to v have the same travel time for agent i. The time intervals in Eq. 4 are changed to [t1i,t2j+τj)[t^i_1,t^j_2+τ^j) and [t1j,t2i+τi)[t^j_1,t^i_2+τ^i) where τiτ^i, τjτ^j denote the travel time of agent i, j. It is easy to verify that r is not smaller than l in these new time intervals. The same is true for Eq. 5 and Eq. 6. 4.6. Analysis In this subsection, we show that CBS-A is optimal and complete. We begin by showing that the constraints introduced by CBS-A are mutually disjunctive, a property essential for proving optimality. Next, we demonstrate that CBS-A always terminates within a finite number of steps. Finally, we prove the optimality and completeness of CBS-A. Definition 0. Two constraints are Mutually Disjunctive (MD) li2019multi if a set of conflict-free paths cannot simultaneously violate them. In other words, if a set of paths simultaneously violates these two constraints, then it must have a conflict. Lemma 0. Constraints in CSA (Eq. (2), (3)) are MD. Proof. In Eq (2), the end time r of the time interval added to i (j) is t(Aj)t_t(A^j) (t(Ai)t_t(A^i)). Therefore, simultaneously violating these two constraints necessarily leads to a conflict. In Eq (3), violating both constraints will obviously result in a conflict at time point trt_r. ∎ Assumption 1 allows us to use τi,τjτ^i,τ^j to denote the travel time of agent i,j∈Ii,j∈ I for any edge in G, which greatly simplifies the notation. This section thus uses this assumption to show the ideas in the proofs. The proof can be extended to the general case without relying on Assumption 1 by using τini(v),τouti(v)τ^i_in(v),τ^i_out(v). Given ⟨Ai,Aj,v⟩ A^i,A^j,v , let Ai=((v1i,t1i),(v2i,t2i))A^i=((v^i_1,t^i_1),(v^i_2,t^i_2)) and Aj=((v1j,t1j),(v2j,t2j))A^j=((v^j_1,t^j_1),(v^j_2,t^j_2)). Lemma 0. IN-IN constraints (Eq. (4)) in CMA are MD. Proof. Assume agent i performs IN at time x, occupying v over τxi=(x,x+2τi)τ^i_x=(x,x+2τ^i), and agent j performs IN at time y, occupying v over τyj=(y,y+2τj)τ^j_y=(y,y+2τ^j). If both agents violate the constraint, then x∈[t1i,t2j+τj)x∈[t_1^i,t_2^j+τ^j) and y∈[t1j,t2i+τi)y∈[t_1^j,t_2^i+τ^i). We show the intervals must intersect. By contradiction, suppose they do not. (i) If x≥y+2τjx≥ y+2τ^j, then x<t2j+τjx<t_2^j+τ^j while y+2τj≥t1j+2τj=t2j+τjy+2τ^j≥ t_1^j+2τ^j=t_2^j+τ^j, a contradiction. (i) If y≥x+2τiy≥ x+2τ^i, then y<t2i+τiy<t_2^i+τ^i while x+2τi≥t1i+2τi=t2i+τix+2τ^i≥ t_1^i+2τ^i=t_2^i+τ^i, a contradiction. Hence, the intervals intersect, implying a conflict. Without Assumption 1, replacing 2τ2τ by τin+τout _in+ _out yields the same conclusion. Therefore, constraints in Eq. (4) are MD. ∎ With the same idea, it can be proved that OUT-IN constraints (Eq. (5), (6)) and WAIT-IN constraints (Eq. (7) and (8)) are MD. Lemma 0. CBS-A can terminate within a finite number of steps on a solvable MAPF-A problem. Proof. Due to space limits, we sketch the main idea, similar to the one in combrink2025sound. If the method does not terminate, there exists an infinite sequence of high-level nodes whose costs are all below the optimal solution and all contain conflicts. Let a trajectory σ be a finite sequence of move actions with cost g(σ)g(σ) equal to the sum of their durations. If a path π contains all actions of σ in order, we write π∼σπ σ. For any finite c∈ℝc , the set σ∣g(σ)<c\σ g(σ)<c\ is finite. Hence, infinitely many constraints must be added to paths mapping to a specific trajectory σ∞σ^∞. Non-termination requires that, despite infinitely many constraints, there still exists a path π′∼σ∞π σ^∞ satisfying all constraints with g(π′)<cg(π )<c. However, each constraint introduced by CBS-A reduces the feasible execution time of actions in σ∞σ^∞ by a non-zero amount. After finitely many branchings, no such π′π can exist. Therefore, CBS-A must terminate in finite steps. ∎ Theorem 10. CBS-A is optimal and solution complete. Proof. Because all constraints added by CBS-A are MD (Lem. 7 and Lem. 8), all solutions are reachable from the root of search tree. And CBS-A always expands the high-level node with minimum objective value. Thus, CBS-A is optimal. If a feasible solution exists, CBS-A is solution complete because it can terminate within a finite number of steps (Lem. 9). ∎ 5. Experimental Results Figure 9. (a)-(d): Success rates of the algorithms. N 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. N is the number of agents. In the previous section, we proposed CSA to correct the errors of CCBS, and further proposed CMA to resolve conflicts efficiently. In order to find conflict-free solutions faster, we proposed a new low-level planner, SIPPS-WC. In this section, we compare our CSA, CMA and CMAS (CMA with SIPPS-WC) with CCBS ANDREYCHUK2022103662, to show the gradual improvement of the methods. Among them, CSA and CMA use SIPP at the low-level, CMAS uses SIPPS-WC at the low-level. Besides, to verify the optimality, we compare CMAS with LS-M* ren2021loosely. We use four maps of different sizes from an online data set stern2019multi: “empty-32-32”, “random-32-32-20”, “den312d” and “warehouse-10-20-10-2-2”. We test the algorithms by varying the number of agents N from 10 to 50.For testing purposes, we consider that the edges in each map have fixed-length edges of a unit, and each agent has a random speed between 1 and 20. In other words, it takes the same amount of time to traverse any edge for the same agent, and it takes different amount of time to traverse the same edge for different agents. When agents reach their goals, they will stay there permanently. The runtime limit of each instance is 30 seconds. We implement all algorithms in C++ and run all tests on a computer with an Intel Core i7-11800H CPU. 5.1. Comparison with CCBS Success Rates Fig. 9 (a)-(d) show the success rates of the methods. We observe that CSA has a slightly higher success rate than CCBS, mainly due to the changes in the wait action. Different from CCBS, the constraint added by CSA for wait actions (Fig. 4 (c)) may affect all of IN, OUT, WAIT actions, and therefore resolve conflicts more efficiently and improve the success rates a bit. Since CCBS’s constraints on wait actions are not mutually disjunctive, it is possible that CCBS overlooks feasible solutions and fails within the time limit, resulting in a lower success rate. Additionally, the success rates of CMA are obviously higher than CSA and CCBS, especially when the number of agents increases. The reason is that, CMA add constraints that affect multiple actions and add constraints at a time interval for WAIT actions, which makes CMA resolve conflicts more efficiently than CSA and CCBS. Finally, SIPPS-WC can help find an optimal path and avoid collisions with other agents as much as possible, especially for cases involving waiting at a safe interval. With the help of SIPPS-WC, the success rates of CMAS are further improved and can handle up to 50 agents in the warehouse map, which is otherwise hard to achieve by the other three algorithms. Number of Expansions Fig. 9 (e)-(f) shows the number of high-level nodes expanded. CMA has the least number of expansions, which means it can resolve more conflicts with one branching, which reduces the number of expansions to find a solution. Compared with CSA, CMA reduces the number of expansions by up to 90%: When the number of agents is 25 in the empty map, the average number of expansions in CSA is 8286 while the one for CMA is 617. By considering paths of other agents in the low-level planner, CMAS can find an optimal solution with even fewer expansions, which thus enhances the success rates. Figure 10. Runtime in empty 32×3232× 32. N is the number of agents. Runtime We further extend the runtime limit to 120 seconds and analyze the runtime of different algorithms in empty 32×3232× 32. As shown in Fig. 10, when the number of agents N≥25N≥ 25, the success rates of CCBS and CSA are low, while the success rate of CMA drops rapidly. However, the success rate of CMAS remains above 60%. When the number of agents N=30N=30, CMAS can find solutions in 68% of instances within 60 seconds. SIPP v.s. SIPPS-WC We compare the average runtime per call of SIPP in CMA with that of SIPPS-WC in CMAS in empty 32×3232× 32. As shown in Table. 1, the runtime of SIPPS-WC increases with the number of agents. The increase in the number of agents leads to an increase in the number of soft constraints contained in SIPPS-WC. Multiple child nodes can be generated for the same safe interval (depending on the number of soft constraints involved), thus increasing the number of nodes to explore. However, due to the consideration of other agents’ paths, CMAS can find conflict-free solutions faster. Table 1. Comparison of SIPP with SIPPS-WC in terms of average runtime per call (ms). N 10 15 20 25 30 SIPP 0.803 0.930 0.902 0.999 1.03 SIPPS-WC 0.845 1.20 1.37 1.62 1.95 5.2. Comparison with LS-M* 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). N 2 4 6 8 SR 1.0/1.0/1.0 1.0/0.96/1.0 1.0/0.2/0.4 1.0/0.0/0.0 RT (s) 0.009/0.895/0.895 0.002/1.52/4.44 0.082/19.0/49.6 -/- LS-M* ren2021loosely is an A*-based MAPF planner and can find an optimal solution in MAPF-A. We compare CMAS with it in order to verify the optimality of CMAS. The experimental setup is the same as above. We fix the map to random-32-32-20 and the number of agents is N=2,4,6,8N=2,4,6,8. And considering that LS-M* needs a long time to search for an optimal solution, we add an additional experiment to extend the runtime limit to 120 seconds. As shown in Table. 2, when the number of agents increases to more than 4, the success rate of LS-M* begins to decline. When the number of agents reaches 8, the success rate of LS-M* is 0%. However, CMAS can always maintain a 100% success rate, and handle more agents than LS-M*. The cost of the solution found by CMAS is the same as LS-M*, while CMAS can find the solution in less run time. The results show that CMAS can find the same optimal solution as LS-M* in a shorter time. 6. Conclusion and Future Work This paper focuses on MAPF-A, and develops a new exact algorithm CBS-A for MAPF-A with solution optimality guarantees, based on the popular CBS framework. CBS-A introduces new conflict resolution techniques for agents with asynchronous actions, which improves the runtime efficiency of the algorithm. Experimental results demonstrate the advantages of our new approaches in different settings against several baseline methods. For future work, one can also consider speed and uncertainty in MAPF-A or combine MAPF-A with target allocation and sequencing ren23cbssTRO; 2025_IROS_MCPFTT_XuemianWu. acks This work was supported by the Natural Science Foundation of China under Grant 62403313, and the Natural Science Foundation of Shanghai under Grant 24ZR1435900. References