Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search

1 Introduction

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for a given set of agents on a given graph. Although MAPF is NP-hard to solve optimally [Yu and LaValle, 2013b], many optimal MAPF algorithms have been developed in recent years, including reduction-based algorithms [Yu and LaValle, 2013a; Erdem et al., 2013; Surynek et al., 2016; Bart´ak et al., 2017], A*- based algorithms [Standley, 2010; Wagner and Choset, 2011; Goldenberg et al., 2014] and dedicated search-based algorithms [Sharon et al., 2013; Sharon et al., 2015].

Conflict-Based Search (CBS) [Sharon et al., 2015] is a popular two-level search-based MAPF algorithm which resolves collisions by adding constraints at a high level and computing paths consistent with those constraints at a low level. It is widely used in many real-world applications, such as warehouse robots [Ma et al., 2017a; H¨onig et al., 2019], quadrotor swarms [H¨onig et al., 2018] and computer game characters [Ma et al., 2017b].

A number of enhancements to CBS have been introduced [Barer et al., 2014; Boyarski et al., 2015; Cohen et al., 2016; Cohen et al., 2018; Li et al., 2019a; Li et al., 2019b; Gange et al., 2019]. CBSH [Felner et al., 2018] was the first work that introduced an admissible heuristic (called here CG) for the high-level search of CBS by reasoning about a special type of collisions in the current solution (i.e., the paths in the current high-level node). In this paper, we further develop this direction. We first prove that CG can offer only a limited amount of information. We then introduce two new admissible heuristics, DG and WDG, by considering potential collisions in future solutions (i.e., the paths in the descendant high-level nodes) and reasoning about the pairwise dependencies between agents. WDG strictly dominates DG, which in turn strictly dominates CG. Empirically, the runtime overhead of calculating the new heuristics is reasonable, and WDG improves the success rate of CBS significantly compared to CG and reduces the number of expanded nodes and runtime by up to a factor of 50.

2 Background

2.1 ProblemDefinition

The Multi-Agent Path Finding (MAPF) problem is specified by an undirected unweighted graph G = (V,E) and a set of k agents {a1 . . . ak}, where ai has start vertex si ∈ V and goal vertex gi ∈ V . Time is discretized into timesteps. Between successive timesteps, every agent can either move to an adjacent vertex or wait at its current vertex. Both move and wait actions have unit cost unless the agent terminally waits at its goal vertex, which has zero cost. A path of ai is a sequence of move and wait actions that lead ai from si to gi. A tuple 〈ai, aj, v, t〉 is a vertex conflict iff ai and aj are at the same vertex v at timestep t, and a tuple 〈ai, aj, u, v, t〉 is an edge conflict iff ai and aj traverse the same edge (u, v) in opposite directions between timesteps t and t + 1. The objective that we focus on in this paper is to find a set of conflict-free paths which move all agents from their start vertices to their goal vertices while minimizing the sum of the costs of these paths.

2.2 Conflict-Based Search (CBS)

CBS has two levels. The high level of CBS searches the binary constraint tree (CT) in a best-first manner according to the costs of the CT nodes. Each CT node N contains:

1. a set of constraints N.constraints, where a constraint is either a vertex constraint 〈ai, v, t〉 that prohibits agent ai from being at vertex v at timestep t or an edge constraint 〈ai, u, v, t〉 that prohibits agent ai from moving from vertex u to vertex v between timesteps t and t + 1;
2. a solution N.solution, that consists of a set of k cost-minimal paths, one for each agent, that satisfy N.constraints; and
3. a cost N.cost, that is equal to the sum of the costs of the paths in N.solution.

The root CT node contains an empty set of constraints.

When CBS chooses a CT node N for expansion, it checks for conflicts in N.solution. If there are none, CBS terminates and returns N.solution. Otherwise, CBS chooses one of the conflicts (by default, arbitrarily) and resolves it by splitting N into two child CT nodes. In each child CT node, one agent from the conflict is prohibited from using the contested vertex or edge by way of an additional constraint. The path of this agent then no longer satisfies the constraints of the child CT node and must be replanned by a low-level search (e.g., a time-space A* search [Silver, 2005]). All other paths remain unchanged. If the low-level search cannot find any path that satisfies the constraints, this child CT node does not have any solution and therefore is pruned. With two child CT nodes per conflict, CBS guarantees optimality by exploring both ways of resolving each conflict.

2.3 Improved CBS (ICBS)

CBS arbitrarily chooses conflicts to split on. However, poor choices can substantially increase the size of its CT and thus its runtime. Improved CBS (ICBS) [Boyarski et al., 2015] addresses this issue by prioritizing conflicts at each CT node N. It classifies conflicts into three types. A conflict is cardinal iff, when CBS uses it to split N, the cost of each of the two resulting child CT nodes is larger than N.cost. (i.e., a conflict is cardinal iff all shortest paths of the two conflicting agents traverse the conflicting vertex/edge at the conflicting timestep). It is semi-cardinal iff the cost of one child CT node is larger than N.cost, but the cost of the other child CT node is equal to N.cost. Finally, it is non-cardinal iff the cost of each of the two child nodes is equal to N.cost. ICBS must first choose a cardinal conflict (if one exists) when splitting N. For example, in Figure 1(left), the conflict 〈a1, a2,B2, 1〉 at the root CT node is non-cardinal as both agents have bypasses that reach their goal vertices at timestep 4 without being at B2 at timestep 1. However, if cells C1 and A3 are blocked, the conflict becomes cardinal because, when a1 or a2 is prohibited from being at B2 at timestep 1, it has to wait at its start vertex for 1 timestep and thus reaches its goal vertex only at timestep 5.

ICBS uses MDDs to classify conflicts. A Multi-Valued Decision Diagram (MDD) [Sharon et al., 2013] for ai at N is a directed acyclic graph that consists of all cost-minimal paths of ai fromsi to gi that satisfyN.constraints. Nodes at depth t of the MDD for ai correspond to all vertices where ai can be at timestep t along one of its cost-minimal paths. A conflict between ai and aj at timestep t is cardinal iff the contested vertex (or edge) is the only vertex (or edge) at level t of the MDDs for both agents. Figure 1(middle) shows the MDDs for a1 and a2 at the root CT node, respectively. Since both MDDs have 2 nodes at timestep 1, the conflict 〈a1, a2, B2, 1〉 is non-cardinal.

2.4 CBSH

The high level of CBS always chooses to expand the CT node N with the smallest N.cost. CBSH [Felner et al., 2018] speeds up the high-level search through the addition of an admissible heuristic. The idea is simple: If N.solution contains one cardinal conflict, then an h-value of 1 is admissible for N because the cost of any of its descendant CT nodes with a conflict-free solution is at least N.cost + 1. If N.solution contains multiple cardinal conflicts, then CBSH builds a conflict graph, whose vertices represent agents and edges represent cardinal conflicts in N.solution. The cost of the path of at least one agent from each cardinal conflict has to increase by at least 1. Thus, the size of a minimum vertex cover (MVC) of the conflict graph (i.e., a set of vertices such that each edge is incident on at least one vertex in the set) is an admissible h-value for N. We refer to this heuristic as the CG heuristic.

3 Limitation of the CGHeuristic

We have just seen that an h-value of 1 for a cardinal conflict is admissible. However, is it possible to find a larger h-value for a cardinal conflict? The following theorem answers the question. The proof of this theorem is given in the appendix.

Theorem 1. Suppose that CBS chooses to resolve a conflict between ai and aj at timestep t at a CT node N and both child CT nodes of N, N1 (with an additional constraint imposed on ai) and N2 (with an additional constraint imposed on aj) have solutions. If the conflict occurs after one of the agents, say ai, reaches its goal vertex (i.e., t ≥ µi, where µi is the cost of the path of ai in N.solution), then N1.cost = N.cost + t + 1 - µi and N2.cost ∈ {N.cost, N.cost + 1}. Otherwise (i.e., it occurs before both agents reach their goal vertices), N1.cost, N2.cost ∈ {N.cost, N.cost + 1}.

Therefore, if both child CT nodes of N have solutions (which is always true in practice), a conflict can be regarded as an admissible h-value of at most 1. Then the size of the MVC is the best admissible heuristic for N that can be obtained from the conflict graph. So, if we want to obtain better heuristics, new directions need to be explored.

4 The DGHeuristic

The CG heuristic considers only cardinal conflicts in N.solution. To improve on that we also need to consider conflicts in future solutions, i.e., solutions of N's descendant CT nodes. For example, in Figure 1(left), if CBS resolves the non-cardinal conflict 〈a1, a2,B2, 1〉 by adding a constraint for one of the agents, a new conflict will occur no matter what new cost-minimal path the agent picks. In fact, any two costminimal paths of the two agents conflict in one of the 4 cells in the middle (B2,B3,C2,C3). Therefore, an h-value of 1 is admissible here. This is not captured by CG because the conflicts are initially non-cardinal. Inspired by this example, we generalize the conflict graph described above to a pairwise dependency graph, whose edges reflect that all cost-minimal paths of the corresponding two agents have conflicts.

4.1 Pairwise Dependency GraphGD

Formally, we define a pairwise dependency graph GD = (VD,ED) for each CT node N. Each agent ai induces a vertex vi ∈ VD. An edge (vi, vj) ∈ ED iff ai and aj are dependent, i.e., all their cost-minimal paths that satisfy N.constraints have conflicts. Similarly to the conflict graph, for each edge (vi, vj) ∈ ED, the cost of the path of at least one agent, ai or aj, has to increase by at least 1. Hence, the size of the MVC of GD is an admissible h-value for N. We refer to this heuristic as the DG heuristic. DG strictly dominates CG because the conflict graph is a sub-graph of GD. We use the same algorithm as in [Felner et al., 2018] to determine an MVC. Its complexity is O(2q |VD|), where q is the size of the MVC.

4.2 Constructing GD

To construct GD for N, we need to analyze the dependencies between every pair of agents. Let µi denote the cost of the path of ai in N.solution. We first classify all pairs of agents into three categories based on their conflicts in N.solution:

1. The two agents do not have any conflicts.
2. They have at least one cardinal conflict.
3. They have only semi-cardinal or non-cardinal conflicts.

If ai and aj are in Category (1), they are independent as their paths in N.solution are conflict-free. Hence, (vi, vj) /∈ ED. If they are in Category (2), by the definition of cardinal conflicts, they are surely dependent. Hence, (vi, vj) ∈ ED. If they are in Category (3), we do not know whether they are dependent or independent. To provide an answer, we try to merge the MDDs for the two agents into a joint MDD using the method described in [Sharon et al., 2013]. The two agents are dependent iff their joint MDD is empty. Details of the merging are given in Section 4.3.

Since each CT node has an additional constraint imposed on only one agent, we only need to look at the dependencies between this agent and all other agents and can copy the edges for the other pairs of agents from the GD for the parent CT node. Of course, at the root CT node, we still need to look at the dependencies for all pairs of agents. CG already build MDDs to classify conflicts. So, for DG, we get these MDDs for free. The only overhead of DG over CG comes from merging the MDDs.

4.3 Merging the MDDs

The joint MDD of the MDDs for ai and aj at N consists of all combinations of cost-minimal conflict-free paths of ai and aj that satisfy N.constraints. Nodes at depth t of the joint MDD correspond to all joint states where ai and aj can be at timestep t along such a pair of paths without conflicts. Let µk (k = i, j) denote the depth of the MDD for ak. If µi ̸= µj, a path of |µi - µj| dummy goal vertices is added to the sink node of the shallower MDD (representing the agent sitting at its goal vertex) so that both MDDs have the same depth. The joint MDD is built level by level. The merging procedure starts at the joint state (si, sj) at level 0. Suppose that we already have a joint state (vi, vj) at level t and want to add its child nodes at level t+1. Each pair in the cross product of the child nodes of vi at level t in the MDD for ai and the child nodes of vj at level t in the MDD for aj should be examined. Only conflict-free pairs are added. ai and aj are dependent iff the joint MDD is empty, i.e., does not contain state (gi, gj) at level max{µi, µj}.

Figure 1(right) shows an example of merging the MDDs. The joint MDD starts at (B1, A2) at level 0. At level 1, we try all combinations of vertices at level 1 in both MDDs and add all of them to the joint MDD except for the pair (B2, B2), which represents a conflict space. We repeat this procedure at levels 2 and 3 until all branches of the joint MDD reach conflicting states and cannot be further developed. Therefore, in this example, the joint MDD is empty, and thus a1 and a2 are dependent.

5 The WDGHeuristic

For a CT node N and two agents ai and aj, we refer to the difference between the minimum sum of the costs of their conflict-free paths that satisfy N.constraints and the sum of the costs of their paths in N.solution as ∆ij (∆ij ≥ 0). ai and aj are dependent iff ∆ij > 0.

Although GD captures the information whether ∆ij > 0 for any pair of agents, it does not capture the information how large the value of ∆ij is. When ∆ij > 0, the DG heuristic only uses 1 (a lower bound on ∆ij ) as an admissible h-value. However, in some cases, ∆ij could be larger than 1. For instance, in Figure 2, ∆12 = 4 because one of the agents must wait 4 timesteps at its start vertex. Therefore, we introduce the WDG heuristic, which captures not only the pairwise dependencies between agents but also the extra cost that each pair of dependent agents will contribute to the total cost.

5.1 Weighted Pairwise Dependency GraphGWD

We generalize the pairwise dependency graph to a weighted pairwise dependency graph GWD = (VD,ED,WD) for N. It uses the same vertices and edges as GD. The weight on each edge (vi, vj) ∈ ED equals ∆ij at N. Here, ∆ij is always larger than 0 as ai and aj are dependent. We also generalize the MVC to an edge-weighted minimum vertex cover (EWMVC), which is an assignment of non-negative integers x1, . . . , xk, one for each vertex, which minimizes the sum of the xi subject to the constraints that xi + xj ≥ ∆ij for all (vi, vj) ∈ ED. xi can be interpreted as the increase in the cost of the path of ai. The sum of xi of the EWMVC of GWD is an admissible h-value for N since, for each edge (vi, vj) ∈ ED, the sum of the costs of the paths of agents ai and aj has to increase by at least ∆ij. We refer to this heuristic as the WDG heuristic. It strictly dominates the DG heuristic. Calculating the EWMVC is NP-hard since calculating the MVC is NP-hard and a special case of calculating EWMVC where the weights of all edges are 1. To calculate the EWMVC, we divide GWD into multiple connected components and calcualte the EWMVC on each component with a branch-and-bound algorithm that branches on the possible values of each xi in the component and prunes nodes using the cost of the best result so far. The EWMVC of GWD is the union of the EWMVCs of all components. Similar dependency graphs and EWMVCs for heuristic search were used in the context of MAPF for large agents [Li et al., 2019c], sliding tile puzzles [Felner et al., 2004] and cost-optimal planning [Pommerening et al., 2013].

5.2 Constructing GWD

We first construct the vertices and edges in GWD for N using the same method as in Section 4. To calculate the weight ∆ij for each edge (vi, vj) ∈ ED, we run a MAPF algorithm to find the minimum sum of the costs of the conflict-free paths of ai and aj that satisfy N.constraints (ignoring the other agents). Here, the pathfinding problem is a two-agent problem with the constraints from N.constraints imposed on the two agents. Most optimal MAPF algorithms can be adapted to satisfy these constraints.

Similar to Section 4.2, for each non-root CT node, we need to find the edges and calculate the weights for only one agent (the one that has the new constraint) and can copy the rest of the edges and their weights from the parent CT node.

5.3 The Two-Agent Problem

We tried three search-based MAPF algorithms to solve the two-agent problem in our experiments: CBSH [Felner et al., 2018] (i.e., CBS with the CG heuristic), EPEA* [Goldenberg et al., 2014] and ICTS [Sharon et al., 2013], and CBSH is significantly faster than the other two.

One enhancement that we use in CBSH for the two-agent problem is that we set the h-value of the root CT node to 1. One is admissible because ∆ij is at least 1. This can help CBSH to resolve cardinal rectangle conflicts [Li et al., 2019b] or other symmetric conflicts efficiently. Figure 1(left) shows an example of a cardinal rectangle conflict. The cost of the optimal solution is 9. As CBSH searches in a best-first manner, it has to expand all CT nodes of cost 8, even if it has already generated a CT node of cost 9 with an optimal solution. However, if the h-value of the root CT node is 1, with a good tie-breaking rule (such as depth-first), CBSH can quickly generate a CT node of cost 9 with an optimal solution and return this solution immediately. In our experiments, this speeds up CBSH for the two-agent problem by up to 3 orders of magnitude.

6 Runtime Reduction Techniques

DG and WDG usually have larger h-values than CG. However, computing these heuristics incurs overhead per CT node. In this section, we introduce a number of simple techniques to reduce the runtime overhead for the calculation of the heuristics.

LazyComputation of Heuristics. The high-level search of CBSH resembles an A* search, so techniques to speed up A* can also be applied here. Lazy A* [Tolpin et al., 2013] improves A* by evaluating expensive heuristics lazily. Instead of computing the expensive h-value h2(N) immediately after generating a new node N, lazy A* first computes a cheaper but less informed h-value h1(N) (or even uses zero) and inserts N into OPEN. Only when N emerges from OPEN, it computes h2(N) for it and re-inserts it into OPEN.

Here, for simplicity, we view both the conflict graph and the pairwise dependency graph as an edge-weighted pairwise dependency graph whose edges all have weight one. Each of the CG, DG or WDG heuristics is treated as h2, and we define h1 for a child CT node N ′ of N as max{N.h - maxj:(i,j)∈ED ∆ij , N.cost + N.h - N ′ .cost, 0}, where i is the index of the agent whose path gets re-planned at N ′ . The first term N.h -maxj:(i,j)∈ED ∆ij is a lower bound on the sum of xi of the EWMVC of the sub-graph of GWD of N without edges incident on vertex vi. It is admissible because the sum of xi of the EWMVC of GWD of N ′ should be no smaller than the sum of xi of the EWMVC of this sub-graph. The second term N.cost + N.h - N ′ .cost is admissible because the f-value (i.e., N.cost+N.h) is non-decreasing. Empirically, the runtime overhead of OPEN operations (e.g., insert or pop a node) is negligible.

Memoization. Memoization is an optimization technique to speed up algorithms by caching the results of expensive function calls and returning the cached results when the same inputs occur again. Here, we use memoization to store the results of merging the MDDs and solving the two-agent problems. The inputs are the indices of two agents and the set of constraints imposed on them. The output is the existence of the corresponding edge and, if its exists, its edge weight. Empirically, the memory overhead of caching and the runtime overhead of storing and retrieving results are both negligible, and the cached results are used frequently. This is because CBS often repeatedly resolves the same conflict in different branches, and many CT nodes thus have the same set of constraints imposed on the same agent. Memoization can also be used to save runtime for building MDDs.

7 Experimental Results

We experiment with CBS, ICBS and CBSH with the CG, DG and WDG heuristics on 4-neighbor grids. All CBSH solvers use the two improvements discussed in Section 6, and the WDG heuristic uses the CBSH algorithm discussed in Section 5.3 to solve the two-agent problem. We generate 50 instances with random start and goal vertices for each map and each number of agents. Our code is written in C++, and our experiments are conducted on a 2.80 GHz Intel Core i7-7700 laptop with 8 GB RAM.

7.1 Small Maps

First, we test the solvers on 20 × 20 grids. We focus on an empty map, which is a 20 × 20 grid with no blocked cells, and a dense map, which is a 20 × 20 grid with 30% randomly blocked cells. We use a time limit of 1 minute for each solver on each instance.

h-values of the root CT node. Table 1 shows the h-values of the root CT node. On the empty map, DG is much larger than CG while WDG is only slightly larger than DG because agents on the empty map usually have many bypasses, and thus ∆ij is 0 or 1 in most cases. However, on the dense map, DG is only slightly larger than CG while WDG is much larger than both of them because most conflicts are cardinal and the map contains many narrow corridors, which induce a large ∆ij. The last four columns show the results for 20 agents on grids with increasing obstacle densities to provide more details on the transition from empty grids to dense grids.

Runtime overhead of heuristics calculation. Figure 3 shows the runtime breakdown per CT node. The CBS runtimes (yellow) of the three solvers are slightly different because the different heuristics cause CBS to expand different sets of CT nodes. The runtimes of constructing GD and GWD (blue) are small due to the memoization technique, which saves more than 90% of the edge and weight computation time. Although we use simple algorithms to solve the NPhard problems MVC and EWMVC, their runtimes (red) are also small due to the small sizes of GD and GWD. The lazy computation of heuristics also contributes to the reduction in the runtime overhead as the expensive heuristics are computed for only 65% of the generated CT nodes.

Overall performance. Figure 4 and Table 2 show the success rate, the average number of expanded CT nodes and the average runtime of the solvers. The number of expanded CT nodes is consistent with the computed h-value of the root CT node. That is, a larger h-value usually leads to a smaller number of expanded CT nodes. With respect to success rate and runtime, both DG and WDG outperform CG. In particular, DG runs slightly faster than WDG on the empty map as it has a smaller runtime overhead than WDG, while WDG runs much faster than DG on the dense map as it leads to a larger node reduction than DG. The usefulness of CG heavily depends on the particular instance. It has almost the same performance as ICBS (= CBSH with h-values that are always zero) on the empty map where cardinal conflicts are rare. However, our new heuristics are efficient on both maps and up to 9 times faster than CG (e.g., for 40 agents on the empty map) for the solved instances (which are relatively easy).

7.2 Large Maps

Next, we test the solvers on a large map. We use the benchmark game map lak503d from [Sturtevant, 2012], which is a 192 × 192 grid with 51% blocked cells (Figure 5).

Plugging in the rectangle reasoning technique. Li et al. [2019b] analyze the symmetries in grid-based MAPF and improve CBSH using a rectangle reasoning technique. This technique is able to find some (but not all) edges in GD, so it can save some of the effort of merging the MDDs. Therefore, we add the most advanced rectangle reasoning technique RM from [Li et al., 2019b] to all CBSH solvers. Figure 5 shows their success rates within 1 minute. In particular, CG+R is identical to CBSH-RM from [Li et al., 2019b] and is the state-of-the-art CBS-based solver in previous research. The results show that all new solvers beat the previous solvers. The rectangle reasoning technique slightly speeds up WDG in most cases. As a result, WDG+R is the strongest solver among them and therefore is the new state-of-the-art CBSbased solver.

Results with longer time limits. Figure 6(left) shows the success rates over 50 random instances of 100 agents on the large map with different time limits. As the time limit increases, the benefit of using WDG and DG over CG increases as well. In general, it is worth spending some extra time per CT node to obtain a better h-value, since a larger h-value usually leads to an exponential reduction in the number of CT nodes. Figure 6(right) shows the results with a time limit of 30 minutes. Although DG and WDG have a larger runtime

• (a) Empty map.

(b) Dense map.

overhead compared to small maps, WDG significantly outperforms DG, which - in turn - significantly outperforms CG in terms of both success rate and runtime. For example, compared with CG, WDG improves the success rate by a factor of 2 and runs faster by a factor of 50.

7.3 Comparing with the Perfect Heuristic

Table 3 compares the average h-values of the root CT node by different CBSH solvers with the average h∗ -values of the root CT node (i.e., the optimal solution cost minus the cost of the root CT node). On the dense map, WDG is significantly smaller than h∗ because agents are deeply coupled and reasoning about the pairwise dependencies between agents is not enough. However, on the empty map or the large map, WDG is close to h∗ because agents are less coupled and reasoning about the pairwise dependencies between agents is enough in many cases. In other words, h/h∗ is closer to 1 on the empty map or the large map than on the dense map. This explains why, compared to CG, WDG has the largest h-value improvement on the dense map over all three maps (as shown in Table 1) but the smallest node reduction factor on the dense map over all three maps (as shown in Table 2 and Figure 6).

8 Conclusions and FutureWork

In this paper, we analyzed the limitations of the heuristic used to provide high-level guidance for CBS, a state-of-theart algorithm for multi-agent path finding. We proposed two new admissible heuristics by reasoning about the pairwise dependencies between agents. They always dominate the old heuristic and only incur a small runtime overhead per node. Empirically, they increase the success rates and speeds of CBS with the old heuristic by up to a factor of 50.

There are several interesting directions for future work. (1) Study admissible or inadmissible heuristics for sub-optimal CBS-based algorithms [Barer et al., 2014]. (2) Apply similar heuristics to other MAPF algorithms, such as ICTS [Sharon et al., 2013] or MDD-SAT [Surynek et al., 2016]. (3) Generalize these heuristics to groups larger than pairs of agents, e.g., to triples and quadruples.

Acknowledgments

The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1409987, 1724392, 1817189 and 1837779 as well as a gift from Amazon. The research was also supported by the United States-Israel Binational Science Foundation (BSF) under grant number 2017692.

A Proof of Theorem 1

In order to help explain the proof, we define another type of MDDs, called extended MDDs, that ignore constraints, i.e., they are allowed to include nodes prohibited by constraints. Formally, an extended MDD MDD µi for ai is a directed acyclic graph that consists of all paths of ai from si to gi within µ timesteps. In particular, MDD µi is empty iff µ is smaller than the minimum cost of the path of ai. All MDDs we discuss in this section are extended MDDs. We say that a node (x, t) ∈ MDD µi iff MDD µi has vertex x at level t, i.e., there is a path from si at timestep 0 to x at timestep t and then to gi by timestep µ. Let dist(x, y) denote the distance between vertices x and y and P(t) denote the vertex at timestep t on path P. Then, the extended MDDs have the following two properties:

Property (1) can be obtained from the definition. Property (2) holds because, by contradiction, if (P(t′ )), t′ ) ∈ MDD µi , then there is a sub-path P ′ in MDD µi from P(t′ ) at timestep t′ to gi at timestep µ. The path that follows a prefix of P from si at timestep 0 to P(t′ ) at timestep t′ and then follows P ′ to gi at timestep µ traverses P(t) at timestep t, i.e., (P(t), t) ∈ MDD µi . Property (2) tells us that, once a path leaves an extended MDD, it will never revisit this extended MDD later.

We say that MDD µi includes all nodes prohibited by a set of constraints C iff MDD µi has vertex v at level t for any vertex constraint 〈ai, v, t〉 ∈ C and edge (u, v) from level t to level t + 1 for any edge constraint 〈ai, u, v, t〉 ∈ C.

Lemma 2. Let C be a set of constraints and µ be a large enough integer such that MDDµ i is not empty and includes all nodes prohibited by C. If ai has a path that satisfies C, then ai has a path of cost no more than µ+1 that satisfies C.

Proof. By assumption, ai has a path P that satisfies C. Let T be the cost of P. If T ≤ µ+1, then we are done. Otherwise, as shown in Figure 7, we will construct a path of cost µ + 1 by letting ai (1) first follow the prefix of P to the border of MDDµ i , (2) then cross the border to a node in MDDµ+1 i , and (3) last follow a path in MDDµ+1 i to gi at timestep µ+1. This new path satisfies C because P satisfies C and any nodes or edges outside MDDµ i also satisfy C. The existence of such a path is proved as follows.

Node (si, 0) (the first node of P) is in MDD µi . Node (gi, T) (the last node of P) is not inMDD µi (because T > µ). So, there is a timestep t < T such that (P(t), t) ∈ MDD µi and (P(t + 1), t + 1) /∈ MDD µi . Let x and y represent P(t) and P (t+1), respectively (Figure 7(left)). There are now two cases, and we show how to construct a path of cost µ+ 1 that satisfies C in each case.

Case 1: (y, t + 1) ∈ MDD µ+1 i (Figure 7(middle)). There is a sub-path P ′ in MDD µ+1 i from y at timestep t + 1 to gi at timestep µ + 1. By applying (y, t + 1) /∈ MDD µi to Property (2), P ′ does not traverse any MDD node in MDD µi , and thus does not violate any constraints. Therefore, a path that follows a prefix of P from si at timestep 0 to y at timestep t + 1 and then follows P ′ to gi at timestep µ + 1 is a path of cost µ + 1 that satisfies C.

Case 2: (y, t + 1) /∈ MDD µ+1 i (Figure 7(right)). Since node (y, t + 1) is on P, dist(si, y) ≤ t + 1. Then, from Property (1), dist(y, gi) > (µ + 1) - (t + 1). Rearranging the terms yields

Inequality (2) is based on the the triangle inequality. Inequality (3) is from dist(y, x) ≤ 1. Inequality (4) is obtained by applying (x, t) ∈ MDD µi to Property (1). By comparing the first line and the last line of these inequalities, all lines are actually equal. Specifically, for Inequality (4),

Since node (x, t) is on P, dist(si, x) ≤ t. From Equation (5) and Property (1), we know that (x, t + 1) /∈ MDD µi and (x, t + 1) ∈ MDD µ+1 i . Hence, there is a sub-path P ′′ in MDD µ+1 i from x at timestep t + 1 to gi at timestep µ + 1. From Property (2), P ′′ does not traverse any MDD node in MDD µi , and thus does not violate any constraints. Therefore, a path that follows a prefix of P from si at timestep 0 to x at timestep t, waits for one timestep and then follows P ′′ to gi at timestep µ + 1 is a path of cost µ + 1 that satisfies C.

Finally, we prove Theorem 1 based on Lemma 2.

Proof. Without loss of generality, we only focus on N1. Every constraint in N.constraints imposed on ai was generated due to a conflict that occurred on one of the old paths of ai, i.e., paths of ai in the solutions of any ancestor CT nodes of N. The cost of any old path of ai is no larger than µi. Therefore, MDD µi i includes all nodes prohibited by N.constraints.

If the chosen conflict occurs before ai reaches gi (i.e., t < µi), then MDD µi i includes all nodes prohibited by N1.constraints. From Lemma 2, we know that ai has a path of cost no more than µi + 1 that satisfies N1.constraints. So, the cost-minimal path of ai is of cost at most µi + 1, and N1.cost ∈ {N.cost, N.cost + 1}.

If the chosen conflict occurs after ai reaches gi (i.e., t ≥ µi), then the chosen conflict is 〈ai, aj, gi, t〉 and the additional constraint added to N1 is 〈ai, gi, t〉. MDD ti includes all nodes prohibited by N1.constraints, and thus, by Lemma 2, ai has a path of cost no more than t + 1 that satisfies N1.constraints. On the other hand, since ai is prohibited from being at gi at timestep t, its cost-minimal path is of cost at least t+1. Therefore, the cost-minimal path of ai is of cost t + 1, and N1.cost = N.cost + t + 1 - µi.