A Real-Time Rescheduling Algorithm for Multi-robot Plan Execution

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-08 02:30:26

Abstract: One area of research in Multi-Agent Path Finding (MAPF) is to determine how re-planning can be efficiently achieved in the case of agents being delayed during execution. One option is to determine a new wait order, i.e., an ordering for multiple agents that are planned to visit the same location, to find the most optimal new solution that can be produced by re-ordering the wait order. We propose to use a Switchable Temporal Plan Graph and a heuristic search algorithm to approach finding a new optimal wait order. We prove the admissibility of our algorithm and experiment with its efficiency in a variety of conditions by measuring re-planning speed in different maps, with varying numbers of agents and randomized scenarios for agents' start and goal locations. Our algorithm shows a fast runtime in all experimental setups.

Main paper: 
 introduction: 
 Multi-Agent Path Finding (MAPF) is the problem of finding a collision-free plan that navigates a team of agents from their start locations to their goal locations. The problem is the core difficulty of numerous practical and industrial applications, such as automated fulfillment and sortation centers (Wurman, D'Andrea, and Mountz 2008; Kou et al. 2019) , computer games (Silver 2005; Li et al. 2020) , drone swarms (Hönig et al. 2018) , and so on. The field of MAPF has garnered considerable interest in recent years. Solving MAPF problems optimally is known to be NP-hard on both graphs and grids (Yu and LaValle 2013; Banfi, Basilico, and Amigoni 2017) , and numerous algorithms have been developed to address this challenge.Classic MAPF models assume flawless execution. However, in real-world scenarios, agents may encounter unexpected delays due to mechanical differences, unforeseen events, localization errors, and so on. To accommodate such delays, existing research suggests the use of a Temporal Plan Graph (TPG) (Hönig et al. 2016) . The TPG captures the precedence relationships within a MAPF solution and maintains these relationships during execution. In this model, an agent only advances to the next vertex in its plan if the corresponding precedence conditions are met. Consequently, if an agent experiences a delay, all other agents whose actions depend on the delayed agent will pause. Despite its advantages, the use of TPG can introduce a significant number of waits into the execution results due to the knock-on effect in the precedence relationship.In this paper, we introduce a variant of the Temporal Plan Graph, named as the Switchable TPG. This model allows for the modification of precedence relationships through two operations on switchable edges, resulting in a new standard TPG. With a Switchable TPG, in the event of a delay, we can generate a new standard TPG that minimizes the cost for all agents to reach their goal locations by executing the new TPG. Subsequently, we propose an optimal heuristic search algorithm to find the new TPG based on a Switchable TPG. We provide proof of the algorithm's optimality and evaluate its efficiency under a variety of experiments. Experimental results show that our approach always finds the optimal TPG with an average runtime faster than 1 second for various numbers of agents on the random-32-32-10 and the warehouse map. On more complicated maps (Paris and Lak303d), our algorithm also runs about 4 times faster than the existing replanning algorithm.We first introduce the formal definition of MAPF.Definition 1 (MAPF). Multi-Agent Path Finding (MAPF) is an optimization problem of finding collision-free paths for a team of agents A on a given graph. Each agent has a unique start location and a unique goal location. Time is discretized into unit-size steps. In each timestep, agents can move to an adjacent location or wait at the current location. A path specifies the actions of an agent at each timestep from its start location to its goal location. We say two agents i, j ∈ A collide if either of the following happens:1. i and j are at the same location at the same timestep. 2. i leaves a location l at a timestep t and j enters the same location l at the timestep t.A MAPF solution is a set of collision-free paths, one for each agent in A.Remark 1. The above definition of collision coincides with that in the setting of k-robust plan (Atzmon et al. 2018 ) with k set to 1. The motivation for disallowing the second type of collision above is that if agents follow each other and the front agent suddenly stops, the following agent may collide with the front agent. Thus this restriction guarantees better robustness when agents are subject to delays.For our discussion, we will stick to the following format for a MAPF solution, though our algorithm is not dependent on the specific format of the MAPF solution.Assumption 1. A MAPF solution takes the form of a set of paths P = {p i : i ∈ A}. Each path p i is an ordered sequence of location-timestep tuples(l i 0 , t i 0 ) → (l i 1 , t i 1 ) → • • • → (l i zi , t i zi )with the following properties:• t i 0 = 0. l i 0 is the start location of agent i, and l i zi is its goal location.• Each tuple (l i k , t i k ) in p i for k > 0 indicates that agent i is planned to perform a move action into the location l i k at timestep t i k . So t i zi records the time when agent i reaches its goal, i.e. the travel time of i.• We require a temporal ordering of the sequence:t i k < t i s for all 0 ≤ k < s ≤ zi.These properties force all consecutive pairs of locations l i k and l i k+1 to be adjacent on the graph. A wait action is implicitly defined between two consecutive tuples (l i k , t i k ) and (l i k+1 , t i k+1 ): if t i k+1 -t i k = ∆, then agent i is planned to wait at l i k for ∆ -1 timesteps before moving to l i k+1 . We also formalize some phrases related to MAPF: A MAPF solution is optimal if it minimizes the sum of travel time for all agents, i.e., i∈A t i zi . Agents are said to be executing a MAPF solution if they act as specified in their paths.In this paper, we consider the replanning problem when agents are subject to a delay during execution. We model this as Problem 1, parameterized by a delay probability p.Problem 1. Given a MAPF solution, at any timestep t during the execution a delay may happen, in which: at least one agent (that hasn't reached its goal) is forced to wait at its current location from timestep t to t + ∆, for some delay length ∆ that may be drawn from some distribution.When such a delay happens, the delayed agent might block the paths of other undelayed agents and thus hinder their execution. One naïve fix is that once a delay happens, we re-run a MAPF solver with this delay constraint to produce a new solution. However, this approach is usually expensive. Instead, we propose a fast replanning algorithm that lets agents stick to their original location-wise paths but with different move-or-wait sequences.The field of MAPF has attracted significant attention in recent years. In relation to this, numerous recent studies have explored strategies for managing unexpected delays during execution. A simple strategy to manage unexpected delays is to replan from the beginning. However, this approach is computationally intensive, leading to prolonged agent waiting time. To avoid the need for replanning, Atzmon et al. (2018) suggested the creation of a k-robust plan. The approach built robustness into the plan., allowing agents to adhere to their planned paths even if each agent is delayed by up to k timesteps. However, if an agent's delay exceeds k timesteps, replanning or alternative strategies are still required. Atzmon et al. (2020) then proposed a different approach, computing p-robust plans that ensure execution success with a probability of at least p, given an agent delay probability model. Nevertheless, planning a k-robust or p-robust plan is considerably more resource-intensive than computing a standard MAPF plan.Another strategy for managing delays involves the use of an execution policy to execute a plain MAPF solution, where dependencies or precedence relationships are preserved during execution (Hönig et al. 2016; Ma, Kumar, and Koenig 2017; Hönig et al. 2019 ). This approach is quick and eliminates the need for replanning. However, the execution results often leave room for improvement, as many unnecessary waits are introduced, and the solution lacks quality guarantees.Roughly, our algorithm optimizes the orderings for multiple agents that are planned to visit the same location. This is achieved using a graph-based abstraction called Temporal Plan Graph. Definition 2 (TPG, (Hönig et al. 2016)) . A Temporal Plan Graph (TPG) is a directed graph G = (V, E) that represents the precedence relationships of a MAPF solution. Given a MAPF solution P, the corresponding TPG is defined as follows:Each vertex represents a move action of an agent. The set of vertices isV = {v i k : i ∈ A, k ∈ [0, zi]},where each vertex v i k corresponds to the k th tuple in the path p i . Each edge encodes a precedence relationship between a pair of move actions. An edge (u, v) encodes that the movement u is planned to happen before the movement v. The set of edges E represents the is partitioned into two types of edges E 1 and E 2 .• Type 1 edges connect two vertices corresponding to consecutive tuples for the same agent. The set of Type 1 edges isE 1 = {(v i k , v i k+1 ) : ∀i ∈ A, k ∈ [0, zi)}.• Type 2 edges connect two vertices of distinct agents, as long as they correspond to tuples containing the same location. The set of Type 2 edges isE 2 = {(v j s+1 , v i k ) : ∀i ̸ = j ∈ A, s ∈ [0, zj), k ∈ [0, zi] satisfying l j s = l i k and t j s < t i k } Remark 2.Note that in the above description, we define Type 2 edge as (v j s+1 , v i k ) instead of (v j s , v i k ) in order to avoid the second type of collision in Definition 1. Example 1. Figure Figure 1 shows an example of converting a MAPF solution into a TPG. Both agents are planned to visit the same location D and the red agent is planned to visit D earlier than the blue agent. Therefore we have a Type 2 edge from v red 3 to v blue 2 .A TPG contains sufficient information for agents' execution. Procedure 1 describes how to execute a TPG in detail, which includes two helper functions INIT EXEC and STEP EXEC and a main function EXEC, along with two marks "satisfied" and "unsatisfied" for vertices.Intuitively, marking a vertex as satisfied corresponds to moving an agent to the corresponding location, and we do so if and only if all in-neighbors of this vertex have already been satisfied. The execution terminates when all vertices are satisfied, i.e. all agents have reached their goals. We now formally state some properties of a TPG. All missing proofs are delayed to the appendix due to the space limit.Definition 3 (Deadlock). When executing a TPG as Procedure 1, we say a deadlock is encountered iff in an iteration of the while-loop [line 17], the set S contains only NULL on line 21 yet there exists unsatisfied vertex in V.Lemma 1. Executing G encounters a deadlock if and only if there exists a cycle in G.Lemma 1 shows a correspondence between a cycle and a deadlock that holds for all TPG. Next, we focus on properties that are specific to a TPG that is constructed from a MAPF solution.Proposition 2 (Collision-Free). Let G be a TPG constructed from a MAPF solution as in Definition 2. Assuming G is executed as in Procedure 1 and an agent i is moved to its k th location l i k at timestep t iff vertex v i k is satisfied in the t th iteration of the while-loop on line 17, any two agents i, j never collide.One can also derive the following interesting corollary from the proof of Proposition 2, which is going to be useful later for our algorithm.Corollary 3. Let G be a collision-free TPG. If we replace an arbitrary Type 2 edge (v j s+1 , v i k ) in it with (v i k+1 , v j s ), the TPG remains to be collision-free.Next, we relate the cost of a TPG with the sum of travel timesteps of a MAPF solution.Proposition 4. Let G be a TPG constructed from a MAPF solution P, the cost of G is no greater than the sum of travel time for agents following P.Proposition 4 gives an immediate corollary that G is deadlock-free.Corollary 5 (Deadlock-Free). If a TPG G is constructed from a MAPF solution P, then it is deadlock-free. 9 cost ← cost + 1; 10 v ← v i k : v i k unsatisfied and ∀k ′ < k, v i k ′ satisfied; 11 forall (u, v) ∈ ETPG is a handy representation for precedence relationships. However, a standard TPG constructed as in Definition 2 is fixed and bound to a given set of paths. In contrast, our optimization algorithm will use the following extended notion of TPG, which enables flexible modifications of precedence relationships.Definition 4 (Switchable TPG). Given a TPG G 0 , let E 1 denote its set of Type 1 edges and E 2 denote its set of Type 2 edges, such thatEQUATION)), which partitions E 2 into two disjoint subsets S E2 (switchable Type 2 edges) and N E2 (non-switchable Type 2 edges), and allows two operations with respect to any switchable edge(v j s+1 , v i k ) ∈ S E2 : • f ix(v j s+1 , v i k )removes this edge from S E2 and add the same edge into N E2 . i.e., this operation fixes a switchable edge to be non-switchable.• reverse(v j s+1 , v i k ) removes this edge from S E2 and add (v i k+1 , v j s ) into N E2 . i.e., this operation switches the precedence relation and then fixes it to be non-switchable.Figure 2 shows a visualization for the reverse operation. For clarity, we may refer to a TPG satisfying Definition 2 as a non-switchable or a standard TPG. A switchable TPG degenerates into a standard TPG if S E2 is empty, in which case its cost can be determined using Procedure 1. We say a switchable TPG G produces a standard TPG G ′ if G ′ can be generated through a sequence of f ix or reverse operations on G. Note that by Corollary 3, all G ′ producible from G are simultaneously deadlock-free or not.Then the roadmap of our replanning algorithm is: (1) when a delay happens, construct a switchable TPG G corresponding to the current states of agents, and then (2) produces a standard TPG G ′ from G with the minimum possible cost (among all G-producible G ′ ), such that it represents an optimal ordering of precedence relationships, upon sticking to the original location-wise paths. We end this section by specifying the construction of a switchable TPG corresponding to a delay situation.Construction 1. Given a MAPF solution P, we execute it by running Procedure 1 on its corresponding standard TPG G 0 as constructed in Definition 2. Assume that at timestep t during the execution, agent i is delayed for ∆ timesteps. We construct a switchable TPG G for this situation as follows:1. Let G = (V, E 1 , E 2 ) be a copy of the standard TPG G 0 . 2. Convert it to a switchable TPG(V, E 1 , (S E2 , N E2 )) by defining N E2 = {(u, v) : either u or v is marked as satisfied in the execution of G 0 } and S E2 = (E 2 \ N E2 ). 3. Let v i k be the next unsatisfied vertex of i, i.e. v i k ← STEP EXEC (G 0 , i) from Procedure 1. Create ∆-many new dummy vertices: V new = {v 1 , v 2 , • • • , v ∆ } and (∆ + 1)- many new edges: E new = {(v i k-1 , v 1 ), (v 1 , v 2 ), • • • , (v ∆-1 , v ∆ ), (v ∆ , v i k )}. Modify G such that V ← V ∪V new and E 1 ← (E 1 ∪E new )\ {(v i k-1 , v i k )}.When executing this TPG, we interpret satisfying a dummy vertex as agent i waiting at location l i k-1 that corresponds to vertex v i k-1 . Construction 1 satisfies the following intuitive yet crucial theorem. The proof is again delayed to the appendix. Theorem 6. Let G be a switchable TPG constructed as in Construction 1, there always exists a finite-cost, collisionfree standard TPG that can be produced from G.We now describe our algorithm in a top-down modular manner, starting with a high-level heuristic search framework in Algorithm 2. We abuse the operators f ix and reverse to take a switchable TPG along with a switchable edge as inputs and return a new TPG after the operation.Algorithm 2: Replanning HEURISTIC, TERMINATE, CYCLEDETECTION, and BRANCH are modules that will be specified later. X denotes some auxiliary information accompanying a TPG, whose format is defined by the set of modules.Input:TPG G root = (V, E 1 , (S E2 , N E2 )) Output: TPG G result 1 Initialize an empty priority queue Q; 2 h root ← HEURISTIC(G root , X init ); 3 Q.push((G root , X init ), 0, h root ); 4 while Q is not empty do 5 ((G, X ), g, h) ← Q.pop(); 6 (g ′ , X ′ , (v i k , v j s )) ← BRANCH(G, X ); 7 if TERMINATE(G, X ′ ) then 8 f ix all edges in S E2 of G; 9 return G; 10 G f ← f ix(G ′ , (v i k , v j s )); 11 if not CYCLEDETECTION(G f , (v i k , v j s )) then 12 h f ← HEURISTIC(G f , X ′ ); 13 Q.push((G f , X ′ ), g + g ′ , h f ); 14 G r ← reverse(G ′ , (v i k , v j s )); 15 if not CYCLEDETECTION(G r , (v j s+1 , v i k )) then 16 h f ← HEURISTIC(G f , X ′ ); 17 Q.push(G r , X ′ ), g + g ′ , h r );18 throw exception "No solution found";Before analyzing Algorithm 2, we recall the notion of cost of a standard TPG and define a similar notion of partial cost for a switchable TPG as the cost of its reduced standard TPG, which contains only its non-switchable edges. Lemma 7. Let G switch be a switchable TPG and G be an arbitrary standard TPG produced from G switch . The partial cost of G switch is no greater than the cost of G.We prove Lemma 7 in the appendix. We now state and prove the correctness of our Algorithm 2, under some reasonable assumptions on the modules. Assumption 2. Let G root be a switchable TPG constructed as in Construction 1. We assume the modules in Algorithm 2 satisfy the following conditions: • CYCLEDETECTION(G, (u, v)) returns true iff G ′ contains a cycle involving edge (u, v), where G ′ is the reduced standard TPG of G containing only its non-switchable edges.• Given a TPG G:-HEURISTIC(G, X ) computes a value h.-BRANCH(G, X ) outputs a value g ′ , an updated auxiliary information X ′ , and an edge in S E2 if it is non-empty or NULL otherwise. Whenever we push ((G, X ), g, h) into Q, g + h is guaranteed to be the partial cost of G.• On line 7 of Algorithm 2, TERMINATE returns true iff the partial cost of G equals the cost of G ′ , where G ′ is produced from G by f ixing all switchable edges.We make the following observations from Assumption 2:1. Under the assumption on TERMINATE, when Algorithm 2 reaches line 10, G must contain switchable edges so (v i k , v j s ) returned by BRANCH is not NULL. This ensures that f ix and reverse on line 10 and 14 are well-defined. 2. As long as G root is acyclic, it holds inductively that CY-CLEDETECTION(G, (u, v)) on line 11 and 15 returns true iff the reduced standard TPG G ′ contains any cycle. This is because in each iteration, we introduce one new edge into G ′ , and any new cycle formed in this iteration has to contain this new edge.Theorem 8. Under Assumption 2, taking G root as an input, Algorithm 2 outputs a collision-free standard TPG G result with the minimum cost among all possible G root -producible standard TPG.Proof. Theorem 6 shows the existence of a solution (in particular, it is collision-free so by Corollary 3, any G rootproducible standard TPG is collision-free.) We now prove the completeness and then admissibility of Algorithm 2. Algorithm 2 always terminates because by assumption TERMINATE(G) returns true once G contains no switchable edge. There are only finitely many possible operation sequences from G root to any standard TPG, each corresponds to an element that can possibly be added to Q. Thus the algorithm must return a solution or report an exception when all possibilities are exhausted after a finite number of steps. We show the completeness using the following claim: Claim 9. Let G ′ be an arbitrary deadlock-free solution that can be produced from G root . At the beginning of each iteration of the while-loop on line 4, there exists some G ∈ Q such that G ′ can be produced from G.Proof (of Claim 9). This holds inductively: at the beginning of the first iteration, G root ∈ Q. During any iteration, if some G ∈ Q such that G can produce G ′ is popped on line 5, then one of the following must hold:• G = G ′ : G contains no switchable edge, thus the algorithm terminates in this iteration and the inductive step holds vacuously. • G f produces G ′ : since G ′ is acyclic, so is the reduced TPG of G f . Thus G f won't be pruned by CYCLEDETEC-TION and is added into Q. • G r produces G ′ : this is symmetric to the previous case.In any case, the claim remains true after this iteration.Claim 9 shows that Algorithm 2 is guaranteed to find a solution if one exists, otherwise the priority queue would remain to be non-empty and the algorithm cannot exit the loop to throw an exception.Finally, if G result is outputted, it must have the minimum cost. Assume towards contradiction that when G result is returned, there exists another G 0 in Q that can produce a standard G better with cost smaller than G result . Yet this is impossible since Lemma 7 implies that such G 0 must have a smaller g + h value and thus would be popped from Q before G result . On the other hand, Claim 9 shows that the existence of such a G 0 is the necessary condition for the existence of G better . Therefore G result has the minimum cost.In this and the subsequent section, we describe two sets of modules and prove that they satisfy Assumption 2. We start with describing a set of "execution-based" modules in Modules 3, which largely ensembles Procedure 1.Proposition 10. Module 3 satisfies Assumption 2.Proof. By the property of DFS, CYCLEDETECTION returns true iff there exists a cycle involving edge (u, v). We show by induction that whenever we push ((G, X ), g, h) into Q in Algorithm 2, g + h equals the partial cost of G.• In the base case, HEURISTIC computes h root by running exactly Procedure 1 on the reduced standard TPG of G root , so 0 + h root is the partial cost of G root . • Let ((G, X ), g, h) be popped from Q. Observe inductively that X records a state of execution of G, and g records the execution cost up to that timestep. On line 6 of Algorithm 2, BRANCH continues execution from that state X until we reach the next switchable edge (as indicated by the modifications on line 13 of Modules 3). BRANCH outputs the execution cost g ′ from X to a current state X ′ . Then line 10 or 14 of Algorithm 2 f ix or reverse this edge to get G f or G r , and HEURISTIC on line 12 or 16 of Algorithm 2 continues executing the reduced TPG of G f or G r from X ′ till termination to get h. Thus g + g ′ + h together sums to the total partial cost of G f or G r .Finally, if on line 7 of Algorithm 2, TERMINATE returns true, then the last BRANCH outputs a goal state for all agents, i.e. the modified execution on line 13 of Modules 3 does not encounter any switchable edge. So it must have been executed on a standard TPG, whose partial cost is exactly its cost after vacuously fixing all its switchable edges.In this section, we introduce an alternative set of modules, which departs from the execution-based ideology of Modules 3 and focus on the graph properties of a TPG. We will see later in our experiment that this shift of focus significantly improves the efficiency of our algorithm. We start by presenting the following crucial theorem that provides a graph-based approach to compute the cost of a TPG.Compute X ′ to be a topological sort of all vertices V in the reduced standard TPG of G (i.e. the sorting consider only the non-switchable edges We note that BRANCH and TERMINATE can be easily combined as a single function in the actual implementation. We define them as separate modules for the simplicity of description. We also remark that this set of modules does not use any g values -it completely depends on HEURISTIC to compute the partial cost of the TPG to determine the priority of node exploration.E 1 ∪ N E2 in G); 7 forall (u, v) ∈ S E2 do 8 if X ′ [u] > X ′ [v] then 9 return (0, X ′ , (u, v)); 10 return (0, X ′ , NULL); 11 Function TERMINATE(G = (V, E 1 , (S E2 , N E2 )), X ) 12 forall (u, v) ∈ S E2 do 13 if X [u] > X [v]Proposition 12. Module 4 satisfies Assumption 2.Proof. By the property of DFS, CYCLEDETECTION returns true iff there exists a cycle involving edge (u, v). It always holds that whenever we push ((G, X ), g, h) into Q in Algorithm 2, g + h = 0 + h equals the partial cost of G, because HEURISTIC computes the sum of longest paths for all agents, which by Theorem 11 equals the partial cost.Finally, if TERMINATE(G, X ) returns true, then it must be the case that all switchable edges in G obey the topological sort specified by X . Therefore after fixing all these edges, the cost of the resulting TPG can be computed as the same sum of longest path distance using X , which exactly equals the partial cost of G Experiment Proposition 10 and 12 justify using execution-based modules and graph-based modules to implement our algorithm framework. We refer to these two implementations as Execution-based Switchable-Edge Search (ESES) and Graph-based Switchable-Edge Search (GSES). We design a series of experiments to evaluate the efficiency of our algorithms and the quality of their solutions. Our algorithms are implemented in C++ and experiments were performed on a server with a 64-core AMD Ryzen Threadripper 3990X, 192 GB of RAM, and an Nvidia RTX 3090Ti GPU.We consider the performance of the algorithms on 4 different maps from the MAPF benchmark suite (Stern et al. 2019) , with 6 agent group sizes per map. The four maps are random-32-32-20, warehouse-10-20-10-2-1, Paris-1-256, and Lak303d. An visual illustration of them can be found in Figure 4 . Regarding each map and group size configuration, we run the algorithms on 25 different scenarios (start/goal locations) with 6 trials per scenario. We set a runtime limit of 90 seconds for each trial. In the experiments, we execute an optimal MAPF solution initially planned by a K-Robust MAPF solver K-Robust CBS (Chen et al. 2021) with k set to 1. At each timestep of the execution, each agent that hasn't reached its goal is subject to a constant probability p of delay. When a delay happens, we draw a delay length ∆ uniformly random from a range [10, 20] and construct a corresponding delay TPG as in Construction 1, and run both replan algorithm ESES and GSES on the TPG. We note that more than one agent may get delayed, in which case Construction 1 naturally generalizes.We compare the runtime of our replanning algorithms with replanning using K-Robust CBS. For each map, scenario, number of agents, and delay probability combination, we model 6 random trials for the delay situation and run all three algorithms (ESES, GSES, and K-Robust CBS) on the same situation. Figure 4 plots the resulting runtime. For trials that exceed the 90-second time limit, we count it as 90 seconds in our mean computation. We see that on all maps and delay configurations, GSES runs significantly faster than K-Robust CBS. Most remarkably, on random-32-32-10 and warehouse maps, the runtime of GSES is consistent below 1 second and does not increase significantly when the number of agents increases. This indicates that our algorithm may be of great practical use for real-time replanning applications.We observe from Figure 4 that although our two implementations ESES and GSES adopt the same framework, the graph-based approach (GSES) runs significantly faster than the execution-based approach (ESES). This is because the topological sort used in GSES defines a simple but extremely powerful early termination condition (see TERMINATE in Modules 4), which enables GSES to find an optimal solution after a very small number of explorations of the search nodes. We compare the number of search nodes of ESES and GSES on the Paris map with delay probability p = 0.2% in Figure 3 , where explored node means the number of TPG that are popped from the priority queue when running our search algorithm, and pruned node is the number of TPG that are discarded because CYCLEDETECTION returns true on it.We also measure the improvement of our replanned solution, in comparison to the original non-replanned MAPF solution and the replanned solution produced by K-Robust CBS. We stress that our solution is guaranteed to be optimal, as proven in previous sections, upon sticking to the original locationwise paths, while K-Robust CBS finds an optimal solution that is independent of the original paths in the non-replanned solution. Therefore the two algorithms are solving intrinsically different problems, and the results in this section serve primarily for a quantitative understanding of how much improvement we can get by changing only wait orders. Figure 5 plots the mean cost (from the locations where the delay happened to the goal locations) of the replanned-by-GSES, replanned-by-K-CBS, and non-replanned MAPF solutions on four maps with three different delay probabilities. The means are taken across all trials for all different numbers of agents.We see that the improvements of the solution depend heavily on the map that we operate on. For example, on the random-32-32-10 map, our solutions (which only change the wait orders) have similar costs as the globally optimal solution, while the difference is larger on the Lak303d map.This paper proposed a new algorithm framework to find the optimal wait orders for agents that are planned to visit the same location. We developed two implementations based on either execution (ESES) or graph presentation (GESE). On the random-32-32-10 and the warehouse maps, the average runtime of GSES is faster than 1 second for various num-bers of agents. On harder maps (Paris and Lak303d maps), GSES also runs significantly faster than replanning with a K-Robust CBS algorithm. 
 
 Appendix:  


Decision: This paper studies the dynamic version of the Multi-Agent Path Finding where the plan needs to be revised in response to delays. It proposes a novel way of reordering the wait orders of multiple agents visiting the same location. The paper introduces a new variant of Temporal Plan Graph, and utilizes it within the proposed optimal heuristic search algorithm. All reviewers agree that the paper is clearly written. In the final version of the paper, the authors should resolve the questions post by the reviewers, including the similarity of their approach with petri nets.

Reviews: review: strength_weakness: strength_weakness: Presentation: Would benefit from a running example to help communicate the contribution upfront.

The unit-size step assumption in the problem definition is a strong simplification of the problem in general. I understand this might be the traditional scope in the MAPF research, but in several applications (e.g. robotics, game, etc) the temporsl aspect of traversing an environment can't carry that simplification. The scheduling problem becomes much more challenging when travel time are more realistic and not that synced through unit-size steps.  In fact the use of the term 'rescheduling' might not reflect precisely the scope of the paper. The temporal aspect is not as aligned with temporal planning in the scheduling/OR line of research.

I would expect to see a larger variety of planners from the literature being used in the experiment section. Is the  K-Robust CBS the main baseline here, and representative of the state of the art?

The text should be read carefully to improve grammar and punctuation.
questions: questions: Intro says "The field of MAPF has garnered considerable interest in recent years." Can you elaborate why is this the case?

TPG reminds me about Petri Nets (PN) and its token simulation, property guarantees (e.g. deadlock, etc). What would you said is the relation of these two aspects and if you have a sense of PN applicability, benefits in this case.
strength_weakness: strength_weakness: The paper could be improved by focusing on the graph-based modules and then being able to add the proofs directly into the actual paper, instead of having to rely on the additional material. While the comparison between both sets of modules at first sight is convincing, focusing on the comparison to the state of the art is sufficient and more useful. It is clear that work was done for the execution-based modules, but eventually they seem to not help the paper as much.


Minor:
- Add reference to the maps that you evaluated this on, it’s not immediately clear to the reader what, e.g., “the warehouse map” is
- Def 1: “each agent has a unique start location and unique goal location”: that can be misinterpreted for the obvious fact that an agent has a single (thereby unique) start and goal location. Be more specific that it’s about no other agent being at the location at the same time on start and end.
- Def 2: “represents the is…” -> “represents the_n_ is”
- Example 1: Figure Figure
- Module 4: “from Module 3” (not modules 3)
- Figure 4 would benefit from a better explanation
questions: questions: - Would you consider making the paper more self-sufficient my replacing execution-based modules with the actual proofs?

- Have you run this on an actual multi-robot scenario, real robots or at least in a suitable simulation to move beyond purely theoretical results?
strength_weakness: strength_weakness: The main weakness of the paper is that the introduction of the ESES approach, i.e., the module that uses the Execution Algorithm (Algorithm 1) to implement the replanning algorithm's modules seems rather "artificial". It is truly no surprise that ESES performance is so bad, compared not only to GSES but also to the third competitor, K-Robust CBS (see Figure 4). The approach purely based on the TP Graph's properties is unsurprisingly more efficient than an approach that has to run the whole execution algorithm on the graph multiple times to realize the same behavior as its GSES competitor. To my perspective, the most significant comparison remains the one between GSES and K-Robust CBS, at least regarding runtime. On the other hand, I fully agree with the auhtors that the comparison regarding the solution cost between GSES and K-Robust CBS has little significance, given that the two approaches solve different problems.

MINOR ISSUES:
1) "Execution-based Modules" Section: "Module 3" is used before being introduced. The pseudocode of Module 3 is in the next page, and this leaves the reader a little puzzled.

2) "Execution-based Modules" Section, line 4:"... which largely ensembles Procedure 1". Maybe, Procedure 2 was meant here? 

3) In the caption of figure 5, ESES should be changed to GSES.
questions: questions: 1) Algorithm 2: It is not clear how a fix operation on the switchable TPG G' (line 10) may produce a cycle (deadlock) in the reduced TPG obtained from G', unless G' already contained the deadlock. Introducing a deadlock by reversing an edge (line 14) is instead clear. But in general, shouldn't all the TPGs pushed in the queue Q (and hence, all the TPGs popped out of it) be deadlock-free by construction, due to the controls in lines 11 and 15?

2) Page 5, 1st column, observation 2 ("This is because in each iteration, we introduce one new edge into G?"):  What is the new edge, and where is it introduced, exactly? Is it the edge returned by the BRANCH procedure at line 6? In the positive case, wasn't this edge already contained in S_{\epsilon 2}?