Robust Multi-Agent Pathfinding with Continuous Time

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 07:18:27

Abstract: Multi-Agent Pathfinding (MAPF) is the problem of finding plans for multiple agents such that every agent moves from its start location to its goal location without collisions.
If unexpected events delay some agents during plan execution, it may not be possible for the agents to continue following their plans without causing any collision.
We define and solve a $T$-robust MAPF problem that seeks plans that can be followed even if some delays occur, under the generalized MAPF$_R$ setting with continuous time notions. 
The proposed approach is complete and provides provably optimal solutions.
We also develop an exact method for collision detection among agents that can be delayed.
We experimentally evaluate our proposed approach in terms of efficiency and plan cost.

Main paper: 
 introduction: 
 Multi-Agent Pathfinding (MAPF) is the problem of finding plans for multiple agents such that every agent moves from its start location to its goal location without any collision. MAPF can be applied to autonomous vehicles (Morris et al. 2016) , robotics (Veloso et al. 2015) , video games (Ma et al. 2017) , warehouse management (Wurman, D'Andrea, and Mountz 2008) , etc. Solving MAPF optimally for common objective functions is NP-hard (Yu and LaValle 2013a; Surynek 2010 ). Nonetheless, practically efficient algorithms have been developed (Wagner and Choset 2015; Surynek 2012; Boyarski et al. 2015; Yu and LaValle 2013b) .Most prior works on MAPF assumed that time is discretized into time steps and each action executes in one time step (Andreychuk et al. 2022 ). However, these simplified assumptions restrict the applicability of MAPF algorithms in real-world scenarios. In addition, unexpected events may delay some of the agents during the execution of a MAPF plan, preventing them from following their plans on time. In this case, we may need to replan for the agents to avoid collisions. Such re-planning may not always be practical, as it requires resources (e.g., computing and communication), or time that the agents may not have. Thus, it is often desirable to generate plans that can tolerate unexpected delays.In this paper, we explore a continuous-time form of robustness for MAPF called T -robust MAPF (T R-MAPF), which is designed to generate MAPF plans for continuoustime scenarios that can be followed even if unforeseen delays occur. In T R-MAPF, we seek a plan that is robust to a total time delay of T per agent during plan execution, i.e., each agent may be delayed up to T and the plan remains safe (collision-free). In the continuous-time form, the time delay T can be any non-negative real number.Our contributions can be summarized as follows:• T -Robust Continuous-time Conflict-based Search (T R-CCBS): We present sufficient and required conditions for a MAPF solution to be T -robust and develop an extension to CCBS to find T R-MAPF plans in a state space that grows exponentially with T . • Closed-form formulas for Collision Detection under T -delay: We propose a collision detection mechanism under T -delay, which is also used to compute unsafe intervals under T -delay. To improve accuracy and reduce computational complexity, closed-form formulas for collision detection under T -delay are developed.The rest of the paper is organized as follows: First, we summarize some closely related work. Next, T R-MAPF is introduced, and we propose our T R-CCBS approach to solve T R-MAPF. After that, the closed-form formulation for collision detection under T -delay is presented. Finally, the paper finishes with empirical evaluation and conclusions.Related Work Ma, Kumar, and Koenig (2017) proposed a MAPF algorithm based on conflict-based search (CBS) (Sharon et al. 2015) to minimize the expected makespan as part of their work on execution policies for MAPF with delays. However, they assumed prior knowledge of delay probabilities and did not provide any robustness guarantee on the plan constructed. Atzmon et al. (2018) proposed k-robust CBS that can find k-robust plans, where each agent can tolerate up to k time steps of delay while executing the plan without collisions. They also extended the work to develop several robust execution policies guaranteeing that the agents reach their goals even if they encounter unexpected delays (Atzmon et al. 2020) . However, they focused on discrete time notions with unit time steps and did not support continuous time notions. Walker, Sturtevant, and Felner (2018) introduced a MAPF formulation with non-unit duration actions and extended the increasing cost tree search algorithm for it. Cohen et al. (2019) enhanced CBS to reason with continuous time and developed a bounded-suboptimal extension of Safe Interval Path Planning (SIPP). Andreychuk et al. (2022) proposed continuous-time conflict-based search (CCBS), a MAPF algorithm that handles continuous time notions and is sound, complete, and optimal. They also adapted successful CBS improvements, including prioritizing conflicts, disjoint splitting, and high-level heuristics, to CCBS (Andreychuk et al. 2021) . However, all the above algorithms do not support robustness or tolerate any delays experienced by the agents.We consider MAPF in 2D environments. For ease of exposition, all agents are assumed to have the same (1) shape and size, and (2) constant speed. The environment is defined as a graph G = (V, E) whose vertices correspond to locations that agents can occupy (and wait in them) and edges correspond to straight-line trajectories for agents to move from one location to the other. We ignore the inertia and assume that the agents start or stop moving instantaneously. The duration of a move action is the length of the edge divided by the speed, while the duration of a wait action can be any positive real number. Prior work referred to this setting as MAPF R (Walker, Sturtevant, and Felner 2018) .There are n agents. Each agent i has a start vertex s i ∈ V and a goal vertex g i ∈ V . A plan π i for an agent i is a sequence of actions that moves the agent from its start vertex to its goal vertex. Each action in the plan is a pair (a i , t i ) representing that action a i (either move or wait) starts execution at time t i . The end time of an action is the start time of the next action in the sequence. After finishing the plan, the agent stays at the last location (its goal vertex) forever.A set of plans, one for each agent, is called a joint plan, denoted by π = {π 1 , ..., π n }. A solution to a MAPF R problem is a joint plan such that if all agents start to execute their plans concurrently, they will reach their goal vertices without any collision. The cost of a joint plan is defined by an objective function. Common objective functions include makespan and sum of costs, which refer to the maximum and total times for agents to reach their goal vertices.A conflict is defined between two timed actions. Definition 1 (Conflict). A conflict is a tuple ⟨a i , t i , a j , t j ⟩, such that if agent i executes action a i at time t i and agent j executes action a j at time t j , they will collide (i.e., their geometry shapes will overlap at some time during the actions).A joint plan π is said valid if it is conflict-free. A MAPF solver is sound if it outputs a valid plan. A delay in a plan π is defined by a tuple ⟨i, t D , ∆ D ⟩, representing that agent i experiences a delay ∆ D starting from time t D . This means that for each action (a i , t i ) after t D (t i ≥ t D ) in the plan, agent i will not perform action a i at the intended time t i and instead will perform a i at time t i + ∆ D . A plan is robust to a delay if the delayed agent can continue to execute its remaining plan after the delay without causing any collision.Formally, for a plan π and a delay D = ⟨i, t D , ∆ D ⟩, let D(π) be the plan that is equivalent to π, except for replacing each timed action (a i , t i ) in π i with (a i , t i + ∆ D ) if t i ≥ t D . A plan π is robust to a delay D if D(π) is valid. π is robust to a series of delays D if applying all the delays in D to π will yield a valid plan, i.e., assumingD = {D 1 , D 2 , . . . , D m } where t D1 ≤ t D2 ≤ • • • ≤ t Dm ,the plan D m (. . . D 2 (D 1 (π)) . . . ) is valid. Note that there could be multiple delays in D on the same agent.Definition 2 (T -robust Plan). A plan is T -robust if it is valid and it is robust to any series of delays that contains at most a total delay of T for each agent.We extend the definition of a conflict between two timed actions to a T -delay conflict to facilitate checking if a plan is T -robust.Definition 3 (T -delay Conflict). A T -delay conflict is a tuple ⟨a i , t i , a j , t j ⟩, such that there exists a value ∆ ∈ [0, T ] so that if agent i executes action a i at time t i and agent j executes action a j at time t j + ∆, they will collide.Lemma 1. A plan is T -robust if and only if it does not contain any T -delay conflict.Due to space limitations, we omit the formal proof of Lemma 1. There can be more than one T -robust plan for a given MAPF R problem. A T -robust plan is optimal if there is no other T -robust plan with a lower cost.Review of CBS CBS (Sharon et al. 2015 ) is a widely used MAPF solver which is complete and optimal. It is designed for classical MAPF with discrete time notions and unit-duration actions. It solves a given MAPF problem by building a plan for each agent separately, detecting conflicts between these plans, and resolving them by replanning for involved agents with additional constraints that they cannot occupy certain vertices or traverse certain edges at particular time steps.CBS searches in a Constraint Tree (CT) for a set of constraints that an optimal plan should satisfy. The CT is a binary tree, where each node N represents a set of constraints imposed on the agents (N.constraints) and a joint plan satisfying these constraints (N.π). The root node has an empty set of constraints. A successor node inherits the constraints of the parent node and adds a new constraint for one agent.Next, we describe how CBS identifies conflicts in a node N and chooses the constraint to add when expanding N and generating its successors.Identifying conflicts For each node N , a low-level solver is used to find a plan N.π for each agent, subject to the constraints for the agent in N.constraints. The plan is validated by simulating the movement of the agents along their planned paths. N is a goal node if N.π does not contain any conflict. N is a non-goal node if a conflict is found in N.π.Resolving conflicts CBS performs a best-first search of the CT. In each iteration, the CT node with the lowest-cost joint plan is selected. When a goal node N is selected, CBS stops searching and outputs its plan N.π. When a non-goal node N is selected, CBS chooses a conflict in N.π and resolves it by generating two successor nodes of N . Specifically, if the conflict chosen involves two agents i and j at x (either a vertex or an edge) at time step t, two successor nodes N i and N j are generated by inheriting N.constraints and adding a new constraint that prohibits agents i and j respectively from occupying or traversing x at t. After that, CBS continues searching the CT in a best-first manner.Next, we introduce T -robust CCBS (T R-CCBS), an adaptation of CCBS designed to return optimal T -robust plans.CCBS (Andreychuk et al. 2022) extends CBS for MAPF R by using a geometry-aware collision detection mechanism. To avoid collisions, CCBS computes constraints according to the unsafe intervals of each action, i.e., the time interval in which performing the action will cause the agent to collide with another agent. The constraints in CCBS are represented by pairs of actions and unsafe intervals, meaning that an action cannot be executed in its unsafe interval. For the low-level solver, CCBS uses a version of SIPP (Phillips and Likhachev 2011) adapted to handle CCBS constraints.Our T R-CCBS differs from CCBS in how it identifies and resolves conflicts. T R-CCBS identifies T -delay conflicts. To resolve T -delay conflicts, a simple idea is to add T to the unsafe interval found by CCBS. However, if two agents do not collide when they are not delayed, there will not be any unsafe interval by CCBS. Therefore, a new collision detection mechanism is required to handle T -delay conflicts.Identifying T -delay conflicts For each node N in the CT, T R-CCBS scans its joint plan N.π for T -delay conflicts, which is further described in the next section.Resolving T -delay conflicts Similar to CBS, T R-CCBS runs a best-first search of the CT, expanding in every iteration the CT node N that has the joint plan with the lowest cost (if N is a non-goal node). T R-CCBS chooses a T -delay conflict in N.π and generates successor nodes of N to resolve it. To resolve a T -delay conflict ⟨a i , t i , a j , t j ⟩, T R-CCBS computes the unsafe interval of each action the other action. The unsafe interval of action a i with respect to a j is the maximal time interval [t i , t u i ) such that for each t ∈ [t i , t u i ), there exists a value ∆ ∈ [0, T ] so that executing a i at time t will lead to a collision with executing a j at time t j + ∆. The unsafe interval of action a j with respect to a i is the maximal time interval [t j , t u j ) such that for each t ∈ [t j , t u j ), there exists a value ∆ ∈ [0, T ] so that executing a j at time t + ∆ will cause a collision with executing a i at time t i . T R-CCBS generates two successor nodes N i and N j for N , and adds toN i (resp. N j ) a new constraint that agent i (resp. j) cannot execute a i (resp. a j ) in its unsafe in- terval [t i , t u i ) (resp. [t j , t u j )).Then, the low-level solver runs the adapted SIPP to find new plans for agents i and j in N i and N j respectively that satisfy the additional constraints.T R-CCBS uses a similar method to CCBS for computing unsafe intervals based on collision detection results: it iteratively carries out collision detection by shifting the start time of a i or a j until no collision is found (Andreychuk et al. 2022) .Theoretical properties T R-CCBS is sound, complete, and optimal. Soundness follows from performing conflict detection for the joint plan of every CT node and Lemma 1. Our proof of completeness and optimality is based on the following lemma from Andreychuk et al. (2022) and the sound pair of constraints defined by Atzmon et al. (2018) . Lemma 2. Running the adapted SIPP from (Andreychuk et al. 2022 ) with a set of CCBS (or T R-CCBS) constraints returns the lowest-cost path that satisfies these constraints. Definition 4 (Sound Pair of Constraints). A pair of constraints is sound if every T -robust plan satisfies at least one of these constraints. Lemma 3. For a T -delay conflict ⟨a i , t i , a j , t j ⟩ and corresponding unsafe intervals [t i , t u i ) and [t j , t u j ), the pair of constraints forbidding agents i and j to execute actions a i and a j in [t i , t u i ) and [t j , t u j ) respectively is a sound pair of constraints.Proof. Assume on the contrary that there exists a T -robust plan in which agent i executes a i at time t i + δ i for someδ i ∈ [0, t u i -t i ), and agent j executes a j at time t j + δ j for someδ j ∈ [0, t u j -t j ). By Lemma 1, ⟨a i , t i + δ i , a j , t j + δ j ⟩ is not a T -delay conflict.By the definition of t u j , for each t ∈ [t j , t u j ), there exists a value ∆ ∈ [0, T ] such that executing a j at time t + ∆ will cause a collision with executing a i at time t i , i.e., ⟨a i , t i , a j , t⟩ is a T -delay conflict by Definition 3. This implies that for each δ ∈ [0, δ j ] and each t ∈ [t j + δ, t u j + δ), ⟨a i , t i + δ, a j , t⟩ is also a T -delay conflict. It follows fromt j + δ j ∈ [t j + δ, t u j + δ) that ⟨a i , t i + δ, a j , t j + δ j ⟩ is a T - delay conflict. Since ⟨a i , t i + δ i , a j , t j + δ j ⟩ is not a T -delay conflict, we must have δ i / ∈ [0, δ j ], which indicates δ i > δ j . By the definition of t u i , for each t ∈ [t i , t u i ), there exists a value ∆ ∈ [0, T ] such that executing a i at time t will lead to a collision with executing a j at time t j +∆, i.e., ⟨a i , t, a j , t j ⟩ is a T -delay conflict by Definition 3. This implies that for each δ ∈ [0, δ i ] and for each t ∈ [t i +δ, t u i +δ), ⟨a i , t, a j , t j + δ⟩ is also a T -delay conflict. It follows fromt i + δ i ∈ [t i + δ, t u i + δ) that ⟨a i , t i + δ i , a j , t j + δ⟩ is a T -delay conflict. Since ⟨a i , t i + δ i , a j , t j + δ j ⟩ is not a T -delay conflict, we must have δ j / ∈ [0, δ i ],which indicates δ j > δ i . As a result, a contradiction arises.Theorem 1. T R-CCBS is guaranteed to return an optimal T -robust plan if there exists one.Proof. The proof, based on Lemma 2 and Lemma 3, is similar to Andreychuk et al. (2022) 's proof for CCBS. Consider any CT node N . Let N 1 and N 2 be the successors of N , generated by a sound pair of constraints C 1 and C 2 respectively (Lemma 3). Let π(N ) denote all T -robust plans that satisfy N.constraints. By the definition of a sound pair of constraints (Definition 4), it holds that π(N ) = π(N 1 ) ∪ π(N 2 ). Thus, splitting a CT node does not cause it to lose any Trobust plan. Due to (1) Lemma 2, (2) the best-first search of the CT in terms of the cost, and (3) the fact that adding constraints can never reduce the cost, T R-CCBS is guaranteed to return an optimal T -robust plan if there exists one.The goal of collision detection is to find out whether the geometry shapes of two agents will overlap when performing their actions. Recall that to solve T -robust MAPF, actions are timed. Our general approach is to first derive the time interval in which the shapes of two moving agents overlap (we call it the collision interval) and then check if the collision interval intersects the time intervals of the actions to infer whether collisions will occur during the actions.To check for T -delay conflicts, we first present a discretized sampling approach that proceeds by sampling for possible delays in each agent and checking if the agents collide. Consider two timed actions (a i , t i ) and (a j , t j ) of two circular agents i and j respectively. Let T be the set of discretized delay samples in [0, T ]. For each ∆ i ∈ T and each ∆ j ∈ T, we derive the collision interval [τ -, τ + ) in which the geometry shapes of agents i and j overlap, if they start performing actions a i and a j at times t i + ∆ i and t j + ∆ j respectively. The detailed derivation will be given later in the section titled "Collision detection between two moving circles". Assume that the durations of actions a i and a j are d i and d j respectively. Under delays ∆ i and ∆ j , the time intervals of the actions are [t i +∆ i , t i +d i +∆ i ) and [t j +∆ j , t j +d j +∆ j ). Hence, a collision would really occur if and only if these two intervals and the collision interval found intersect:[t i +∆ i , t i +∆ i +d i )∩[t j +∆ j , t j +∆ j +d j )∩[τ -, τ + ) ̸ = ∅.A drawback of the sampling approach is that it has an increasing computational complexity with respect to the number of delay samples and hence T assuming a constant sampling size per unit delay. Next, we propose to solve for the exact collision interval between two agents that may be delayed. The key benefit of this method is that the computational complexity of the collision detection is constant to T .We propose to use Constructive Solid Geometry (CSG) for collision detection under T -delay. CSG forms objects from primitives by combining them with set-theoretic operations (Requicha and Rossignac 1992) . By treating the time domain as an additional polygonal dimension, the polygons can be extruded into the time dimension, after which a static polygonal intersection check is applied (Walker and Sturtevant 2019) . To check for T -delay conflicts, we extrude the agent shapes into the time-delay dimension and perform dynamic collision detection between extruded geometries.Assume that the agents have circular shapes and move with constant velocities, and each action is a linear motion from the start location to the target location. We can extrude the circular agents into a stadium, which is a twodimensional geometric shape composed of a rectangle with semicircles at a pair of opposite sides. The stadium represents all possible areas occupied by the agent under the delay. In general, assuming the center point of the agent without delay is p, the maximum delayed center point of the agent is p d = p -vT , where v is the velocity of the agent. Figure 1 shows a stadium formed from two circles centered at p and p d . 1 We can then perform collision detection be-1 If it is a wait action, then v = 0, p and p d are the same, so that the stadium degenerates to the circular shape of the agent. tween the stadium geometry formed by each agent. Figure 2 illustrates the collision detection for (a) agents that are not delayed and (b) agents that can be delayed (by extruding the circular geometry into a stadium geometry). Special considerations, however, need to be taken at the beginning and end of an action, because both p and p d cannot go beyond the start and target locations of the action. Consider a timed action (a i , t i ) of agent i. Let d i be the duration of the action, v be the velocity of the agent, and p 0 be the start center point of the agent (then the target center point of the agent is p 0 + vd i ). Figure 3 illustrates the evolution of the stadium for the action.(1) Initially, both center points p and p d are at the start location p 0 , so the stadium degenerates to a circle. (2) During the initial T duration of the action, the length of the rectangle in the stadium gradually grows from 0 to vT , i.e., for each t ∈ [t i , t i + min{T, d i }), the center point without delay will be p = p 0 + v(t -t i ) and the maximum delayed center point will remain at p d = p 0 . (3) There are two cases for the time interval[t i + min{T, d i }, t i + max{T, d i }): d i ≥ T : In this case, [t i + min{T, d i }, t i + max{T, d i }) = [t i + T, t i + d i ).During this time interval, the stadium stops growing (with the rectangle reaching the maximum length of vT ) and continues to move towards the target location, i.e., for each t ∈ [t i + T, t i + d i ), the center point without delay will be p = p 0 + v(t -t i ) and the maximum delayed center point will bep d = p -vT = p 0 + v(t -t i -T ). d i < T : In this case, [t i + min{T, d i }, t i + max{T, d i }) = [t i + d i , t i + T ).During this time interval, the stadium stops growing (with the rectangle reaching the maximum length of vd i ) because the agent has reached the target location, i.e., for each t ∈ [t i +d i , t i +T ), the center point without delay will remain at p = p 0 + vd i and the maximum delayed center point will remain at p d = p 0 . (4) Beyond the action completion without delay, the length of the rectangle in the stadium gradually shrinks from vTEQUATION(3) (4)(5) to 0, i.e., for each t ∈ [t i + max{T, d i }, t i + d i + T ), the center point without delay will remain at p = p 0 + vd i and the maximum delayed center point will betp d = p - v(t i + d i + T -t) = p 0 -v(t i + T -t).(5) Finally, both center points p and p d will be at the target location p 0 + vd i , so the stadium again degenerates to a circle.Conceptually, a stadium is constructed from a set union of two circles and a rectangle. Let us represent the stadium geometry of agent i as G i = {c i , r i , c d i }, consisting of a circle c i (centered at p), a rectangle r i , and another circle c d i (centered at p d ). Based on the above evolution, we can partition the time interval[t i , t i + d i + T ) into three sub-intervals [t i , t i + min{T, d i }), [t i + min{T, d i }, t i + max{T, d i }) and [t i + max{T, d i }, t i + d i + T ).In each sub-interval, the circles c i and c d i move with constant velocities. The rectangle r i also moves with constant velocity, in the sense that all four vertices move along the same direction with constant velocities. In the second sub-interval, since stadium has grown to its maximum length, all four vertices move at the same velocity. In the first and last sub-intervals, due to the growing or shrinking of the stadium, a pair of vertices move at a different velocity from the other pair of vertices at the opposite side.To check for T -delay conflicts between two timed actions (a i , t i ) and (a j , t j ) of agents i and j with durations d i and d j , we perform collision detection between their stadium geometries G i = {c i , r i , c d i } and G j = {c j , r j , c d j }, focusing on the intersection between the time intervals [t i , t i +d i +T ) and [t j , t j +d j +T ). Figure 4 shows the combination of partitioning of [t i , t i +d i +T ) and [t j , t j +d j +T ), which divides the intersection [t i , t i +d i +T )∩[t j , t j +d j +T ) into smaller sub-intervals in which all the geometric primitives in G i and G j move at constant velocities. In each sub-interval, we can break down the collision detection into that between moving geometric primitives, i.e., among moving circles and rectangles. A collision only occurs if any collision interval found (1) Collision detection between two moving circles The collision detection between two moving circles is based on Guy and Karamouzas (2019)'s descriptions. Given two circular agents i and j, the distance between their centers at time t is given by:dist(t) = ||(p i + v i t) -(p j + v j t)||,where p i and p j are the center points of the circles at time 0, and v i and v j are the velocities of the agents. Squaring and expanding leads to the following quadratic equation for t:EQUATIONwhere p ∆ = p j -p i , v ∆ = v j -v i and • is the dot product of vectors. Via substitution, equation ( 1) can be rewritten as:dist 2 (t) = at 2 + bt + c 0 , where a = v ∆ • v ∆ , b = 2(p ∆ • v ∆ ) and c 0 = p ∆ • p ∆ .A collision occurs when the squared distance between the agents is less than or equal to the squared sum of their radii, r:dist 2 (t) ≤ (2r) 2 .Thus, we have the following equation for collision detection:at 2 + bt + c ≤ 0, where c = p ∆ • p ∆ -(2r) 2. We can solve it using the quadratic formula to determine the start and end times of the collision interval between two agents:-b - √ b 2 -4ac 2a , -b + √ b 2 -4ac 2a .The above formulation assumes that the two agents start their actions at the same time while at positions p i and p j . If they start their actions at different times t i and t j , we need to align their positions to the same time instant before performing the collision detection. Specifically, if t i < t j , the center point of agent i is first moved to p ′ i = p i + v i (t j -t i ) and collision detection is then performed with p ′ i and p j .(2) Collision detection between a moving circle and a moving rectangle First, we study the collision detection between a circle and an axis-aligned rectangle. Next, we extend it to consider a moving circle and a moving rectangle.For an axis-aligned rectangle, we first find the point on the rectangle edges that is the closest to the circle's center and then check whether the point is located in the circle. The former can be done by clamping the coordinates of the circle's center p i to the coordinates of the rectangle's vertices (let p j be the lower-left vertex of the rectangle, w and l be its width and length):p ∆ [x] = p i [x] -max(p j [x], min(p i [x], p j [x] + w)), p ∆ [y] = p i [y] -max(p j [y], min(p i [y], p j [y] + l)).A collision occurs if p ∆ • p ∆ ≤ r 2 , where r is the radius of the circle.To extend this formulation to derive the collision interval between the moving circle and rectangle, we form a set of positions by combining the elements in p ∆ [x] and p ∆ [y]:P x = {p j [x], p i [x], p j [x] + w}, P y = {p j [y], p i [y], p j [y] + l}, P ′ = {p ′ |p ′ = ⟨p ′ [x], p ′ [y]⟩, p ′ [x] ∈ P x , p ′ [y] ∈ P y }.For each position p ′ ∈ P ′ , we find its the corresponding velocity v ′ . Then, we substitute p ∆ = p i -p ′ and v ∆ = v iv ′ into equation ( 1) and solve the equation dist 2 (τ ) ≤ r 2 to get a collision interval. Then, we combine these intervals by taking the minimum start time and the maximum end time to obtain the complete collision interval between a moving circle and a moving axis-aligned rectangle.If the rectangle is not axis-aligned, we can rotate the rectangle vertices to align with the axis, and rotate the rectangle and circle velocities accordingly, before applying the above formulation to derive the collision interval.(3) Collision detection between two moving rectangles We can utilize the Separating Axis Theorem (SAT) to perform collision detection between two moving rectangles (Boyd and Vandenberghe 2004) . The velocities of the rectangles are used to determine the separating axes as the moving directions of the rectangles decide where two rectangles will collide first. The separating axes, A, are a set consisting of the normalized vectors of the velocities, ||v i || and ||v j ||, their orthogonals, ⊥ ||v i || and ⊥ ||v j ||, and the sum of the velocities, ||v i + v j || and ⊥ ||v i + v j ||. The sum of the velocities is required for the case where v i is orthogonal to v j .A = {||v i + v j ||, ⊥ ||v i + v j ||} if v i ⊥ v j , {||v i ||, ⊥ ||v i ||, ||v j ||, ⊥ ||v j ||} otherwise.Let P i and P j be the sets of vertices of two rectangles. For each pair of vertices p i ∈ P i and p j ∈ P j , we find their corresponding velocities v i and v j . Then, we project the vertices and velocities onto each separating axis, a ∈ A:p ′ i = p i • a, v ′ i = v i • a, p ′ j = p j • a, v ′ j = v j • a.After that, for each pair of projected vertices p ′ i and p ′ j , we find the time instants when the moving points overlap (i.e., the distance between the points is equal to zero) to derive a collision interval. Specifically, we substitute 1) and solve the equation dist 2 (τ ) = 0 to get a collision interval. Then, we combine these intervals by taking the minimum start time and the maximum end time to obtain the complete collision interval between two moving rectangles.p ∆ = p ′ i -p ′ j and v ∆ = v ′ i -v ′ j into equation (We implemented T R-CCBS on top of CCBS (https://github.com/pathplanning/continuous-cbs) and conducted experiments using the same experimental settings of Andreychuk et al. (2022) . Agents move in 2 k -neighborhood grids. In a move action, agents can move from the center of one grid cell to the center of any grid cell located in their 2 k neighborhood, where k is a parameter (Rivera, Hernández, and Baier 2017) . The size of every cell is 1 × 1, and the shape of every agent is a circle of radius √ 2/4. Moves are allowed only if the agent can move safely to the target cell without colliding with other agents or obstacles, considering the geometry shapes of the agents and obstacles. The moving speeds of agents are 1 per unit time, so the duration of a move action corresponds to the Euclidean distance between the centers of the start and target cells. We used the makespan as the objective function in pathfinding. Constructive Solid Geometry (CSG) was used for collision detection, unless stated otherwise. The experiments were run on an Intel i9-12900K 5.6GHz processor with 32GB memory.In the first set of experiments, we used a 10 × 10 open grid. For every number of agents, we created 250 different problems by placing agents' start and goal locations randomly.Increasing number of agents We performed experiments with 2 ∼ 24 agents. Each problem was solved with T R-CCBS for k = 2, 3, 4, 5, and T -delay = 0, 0.5, 1, 1.5, 2. Note that T = 0 is the standard CCBS.The top half of Table 1 presents the success rate, i.e., the ratio of problems solved by T R-CCBS within a time limit of 60 seconds. Every row shows the results for a distinct number of agents, as indicated in the left-most column. Every five columns show the results for a 2 k -neighborhood ranging from k = 2 ∼ 5. Each of the five columns shows the success rate for a distinct T -delay. Data points marked by "-" indicate settings where the success rate is 0. The bottom half of Table 1 presents the cost (makespan) of the output plan for one particular problem (of 250 problems tested), where data points marked by "-" indicate that no solution was found within the time limit.It can be seen from Table 1 that increasing the number of agents leads to a lower success rate, which was also shown for the original CCBS (Andreychuk et al. 2022) . A larger number of agents result in a denser environment, which is more difficult to solve as more potential conflicts need to be resolved. Increasing the number of agents under a higher Tdelay exhibits a sharper decrease in the success rate. This is especially prominent for T = 2, where no solution was found within the time limit for more than 12 ∼ 17 agents. Due to the higher delay, agents need to reserve more space to avoid conflicts, which increases the hardness of pathfinding.Table 1 also shows that increasing k yields a lower success rate. For example, for T = 0 and 24 agents, the success rate for k = 2 is 0.688, while that for k = 5 is only 0.12. A larger k increases the branching factor (more paths available), making the optimal plan harder to find. 10 191.00 191.00 191.00 191.00 191.00 155.40 155.40 155.40 155.40 155.40 149.34 149.34 149.34 149.34 149.34 15 195.00 195.00 195.00 195.00 195.00 157.87 157.87 157.87 157.87 157.87 154.49 154.49 154.49 154.49 154.49 20 236.00 236.00 236.00 254.00 254.00 200.85 200.85 200.85 200.85 200.85 196.75 196.75 196.75 196.75 220.20 25 236.00 236.00 236.00 255.00 255.00 200.85 200.85 200.85 229.74 229.74 196.75 205.33 219.76 219.76 233.69 Table 3 : Results for den520d map.success rate for a 2 k -neighborhood ranging from k = 2 to 4. Each of the three columns shows the success rate for a distinct number of agents. The bottom half of the table shows the plan cost for one particular problem. Similar to the results in Table 1 , increasing the T -delay reduces the success rate due to the increased hardness of pathfinding. In general, increasing the T -delay does not significantly increase the cost of the plan found. When the number of agents is small, the likelihood of them colliding with each other is low as the environment is sparse. Hence, it is possible that even increasing the T -delay, the agents may still not interact with each other. Thus, increasing the Tdelay may not have a significant effect on the cost.Further experiments were also performed on a larger grid, den520d, from the Dragon Age: Origin (DAO) game (available in the movingai repository (Sturtevant 2012) ). The start and goal locations of agents were chosen randomly to create 250 different problems for every number of agents.Table 3 presents the results, which are tabulated in a similar manner to Table 1 . In general, the same overall trends are observed: increasing the number of agents or T -delay reduces the success rate and increases the plan cost; increasing k reduces the success rate and the plan cost. However, when the number of agents is small, the optimal T -robust plan often has the same cost as the optimal 0-robust plan as the map is very large. For example, for 10 agents, there is no increase in the plan cost with increasing T -delay.Lastly, we compare the runtime performance of collision detection using CSG and the sampling approach. We repeated the Open Grids experiments for k = 4 using the the influence the number of CT nodes explored, affecting the overall runtime of the search. In Figure 5 , the collision detection time (CDT) is plotted against the T -delay for different numbers of agents a = 5, 10, 15 and different sample sizes per unit delay s = 10, 20, 30. Some lines end before the maximum delay of 7, because the success rate (within a time limit of 60 seconds) drops to 0.As seen from Figure 5 , the CDT for CSG remains quite similar as the T -delay increases. This implies that the mag- nitude of T -delay has little impact on the computational complexity of CSG. However, the CDT for the sampling approach increases with the T -delay. This is because the number of samples increases proportionally to the T -delay. For a sample size of 10, if T -delay is below 2, it is possible that sampling has a lower CDT compared to CSG. Other than that, when the T -delay is above 1, sampling has a higher CDT compared to CSG. A larger sample size also leads to higher CDT, especially when the T -delay is large. The setting of the sample size yields a tradeoff between the computational complexity and the accuracy of collision detection. A larger sample size will increase the computational time of collision detection, whereas a smaller sample size will reduce the accuracy of collision detection.In this paper, we have proposed T R-CCBS, a sound, complete, and optimal MAPF algorithm that supports continuous time and produces plans that can tolerate a total delay up to T for each agent. T R-CCBS extends CCBS by identifying T -delay conflicts and resolving them by finding the unsafe intervals for the T -delay conflict. We have also presented an exact method for finding the collision interval between agents under the T -delay conflict. Our experimental results demonstrate the impact of increasing T -delay and agent number on the success rate and plan cost. 
 
 Appendix:  


Decision: The paper studies T-robust MAPF, a combination of k-robust MAPF with continuous-time MAPF. It is well-written and well-organized. It proposes a CBS-based algorithm for solving T-robust MAPF optimally. While the proposed algorithm is a straightforward combination of the algorithms for k-robust MAPF and continuous-time MAPF, it studies the unique challenge posed by this combination, namely collision detection, in-depth and provides an exact method for solving it. The significance of the paper could be strengthened if it includes some strawman algorithms for empirical comparison.

Reviews: review: strength_weakness: strength_weakness: In my opinion, there are two main weaknesses (presented below). However, I liked the paper and, with minor modifications (specifically regarding the first weakness), the paper will be ready for publication.

1) Related work - while some relevant related work is not mentioned in the paper and should be mentioned, none of these directly impacts the proposed methods. Moreover, a few citations are missing in the paper. The related work that is relevant to the paper and the missing citations are:
- In the introduction, a few papers are cited as "efficient algorithms have been developed". However, recent papers are not mentioned there, such as: (1) Li et al. "Pairwise symmetry reasoning for multi-agent path finding search". Artificial Intelligence (2021). (2) Gange et al. "Lazy cbs: implicit conflict-based search using lazy clause generation". ICAPS (2019). (3) Lam et al. "Branch-and-cut-and-price for multi-agent path finding". Computers and Operations Research (2022).
- In the related work section, citations for the increasing cost tree search algorithm and for SIPP are missing.
- In the related work section, the following papers should also be mentioned: (1) Chen et al. "Symmetry Breaking for k-Robust Multi-Agent Path Finding". AAAI (2021). (2) Shahar et al. "Safe multi-agent pathfinding with time uncertainty". JAIR (2021). (3) Wagner and Choset. "Path Planning for Multiple Agents under Uncertainty". ICAPS (2017). (4) Atzmon et al. "Probabilistic robust multi-agent path finding". ICAPS (2020).

2) Experimental study - while I find the experiments sufficient for a conference paper, I think it would have been nice if there were results comparing the proposed method with a similar method for a discretized environment. This may show the benefit of keeping the problem continuous.

Minor comments and suggestions -
- In the related work section, what the "expected makespan" is should be explained.
- In the T-Robust MAPF section, the term "timed action" is used, but the first time an action is mentioned in this section, it is just called "action". This was a bit confusing as I thought that this was a different type of action.
- In the last line of "Resolving conflicts", "searching the CT in a best-first manner" - according to what value? the cost?
- In T-Robust CCBS, "However, if two agents do not collide when they are not delayed, there will not be any unsafe interval by CCBS." - I find this sentence very confusing. There are too many negations in this sentence.
- "TR-CCBS computes the unsafe interval of each action the other action." - I could not understand this sentence.
- "number of agents result in a denser environment" -> "number of agents results in a denser environment".
- In Table 1, the headline should be "Success Rate" and not "Success Ratio", as in other places.
- In "Comparison between CSG and Sampling", "different numbers of agents a=" - there are "n" agents and not "a" agents.
questions: questions: 1) According to the paper, "A plan is robust to a delay if the delayed agent can continue to execute its remaining plan after the delay without causing any collision". However, assume we have an agent that has been delayed T time and, according to its plan, the agent waits T time at some future vertex. This agent may be able to reduce the future waiting time while keeping the plan robust. Is that correct? Did you think about such a scenario?
2) While the proof of Lemma 1 is missing, I guess it should be almost identical to the similar proof from Atzmon et al., 2020 (Observation 1). Is that correct?
3) TR-CCBS is complete, optimal, and sound. However, what happens if the algorithm is executed on an instance that doesn't have a solution?
4) I couldn't understand how the cost, presented in the experiments section, was computed. Was it averaged out of instances solved for all k values and all delays? For instance, in Table 1, for k=2, t=2.0, and 5 agents, the success rate was 0.772. Why is there no cost value for that setting?

----- Post Rebuttal ----
Thank you for answering my questions in your feedback.
Please add a clarification on the plan cost in the paper (question 4).
strength_weakness: strength_weakness: I recognize that there may not be any "apple to apples" work to compare to here, but with results that don't scale particularly well (which is totally to be expected), it's hard to know how really important these results are in this space. It would really strengthen the paper if there was, at the least, a straw man comparison. There is other work, on the discrete side, that used to compare (in the early times) to "resynchronizing" the plan when a delay occurs (which implies a level of centralization admittedly). Or, another straw man could be planning without the delay robustness (CCBS) and then doing replanning when a collision "is about to happen". I do not expect that any of these suggested approaches will work well, but they would provide a helpful context to what you've accomplished.

I really like what you've done with CSG. In your contributions, you suggest you've provided a closed form solution for this problem, but I don't see how this would extend with your derivation beyond simple circular agents? Naturally, you could use this method to identify possible conflicts and then refine that possibility, but that doesn't seem to be addressed in the paper. For this two dimensional case, would there be additional primitives required beyond a circle and a rectangle? Triangles and semi-circles, off the top of my head?

As I said, I think the paper is really well written and quite clear, but it is missing a few things I think are necessary to tell the story you want.
questions: questions: I'll ask some of the questions I'm pointing out above.

1) For this two dimensional case, would there be additional primitives required beyond a circle and a rectangle to represent a wider assortment of agent shapes?

2) Have you thought about taking the results section in a different direction and using this on a set of physical robots? 

3) Are there any applications for this work that you have in mind? It's really neat work, but talking about where you'd see delay at that scale or applications with that many robots would also help to motivate the utility of this great work.
strength_weakness: strength_weakness: A *very minor* weakness is that one can view the TR-CCBS algorithm as incremental as it builds on top of (and has a significant overlap with) CCBS. The key differences are in the collision conflict detection and resolution of those conflicts. But the collision detection approaches also strongly adapts findings from the literature.
questions: questions: Is there a reason to ever use the sampling approach in detecting collisions? It seems that applications where robustness is important will also require guarantees on the robustness properties, and sampling approaches are unable to provide such guarantees.