# multiagent_path_finding_for_large_agents__4b03e680.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Multi-Agent Path Finding for Large Agents

Jiaoyang Li CS Department Univ. of Southern California jiaoyanl@usc.edu

Pavel Surynek Faculty of Information Technology Czech Technical University pavel.surynek@ﬁt.cvut.cz

Ariel Felner SISE Department Ben-Gurion University felner@bgu.ac.il

Hang Ma T. K. Satish Kumar Sven Koenig CS Department Univ. of Southern California

Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conﬂict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a twolevel tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as large agents because they can occupy multiple points at the same time. In this paper, we formalize and study LAMAPF, i.e., MAPF for large agents. We ﬁrst show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MCCBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases.

1 Introduction In robotics and computer games, one has to ﬁnd collisionfree paths for multiple agents operating in a common environment. This has led to the study of Multi-Agent Path Finding (MAPF) in the AI community, where we are required to ﬁnd a path for each agent from its given start vertex to its given goal vertex on a given graph such that no two agents collide with each other at any given time. MAPF can be applied to warehouse robots (Wurman, D Andrea, and Mountz

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 and the Czech Science Foundation (GACR) under grant number 19-17966S. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the ofﬁcial policies, either expressed or implied, of the sponsoring organizations, agencies or the U.S. government. Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

2008), ofﬁce robots (Veloso et al. 2015), aircraft-towing vehicles (Morris et al. 2016), video game characters (Ma et al. 2017) and many other domains. Numerous optimal MAPF algorithms have been developed in recent years, including reduction-based algorithms (Yu and La Valle 2013a; Erdem et al. 2013; Surynek et al. 2016), A*-based algorithms (Standley 2010; Wagner and Choset 2011; Goldenberg et al. 2014) and dedicated search-based algorithms (Sharon et al. 2013; 2015; Boyarski et al. 2015; Felner et al. 2018). See (Ma et al. 2016a; Felner et al. 2017) for complete surveys. Although previous MAPF algorithms have found some real-world applications (H onig et al. 2016), they are based on one simplistic assumption that limits their applicability. This assumption is to ignore the shape of agents and consider them as point agents, which occupy exactly one point at any time. In reality, agents are geometric in nature with deﬁnite shapes. Therefore, they typically occupy a set of points at any time. We refer to such agents as large agents. MAPF algorithms can be applied to large agents by lowering the resolution of discretization of the environment. However, this degrades their performance and thus their practical applicability. To address these concerns, we formally study Multi-Agent Path Finding for Large Agents (LA-MAPF) which takes into consideration the shapes of agents. This consideration also addresses the case where agents have to maintain a safety distance from each other since a virtual boundary can now be deﬁned for each agent. Intuitively, LA-MAPF is harder to solve than MAPF since it is a generalization of MAPF and agents are more likely to collide with each other. The remainder of the paper is organized as follows. In Section 2, we formalize the LA-MAPF problem. In Section 3, we solve LA-MAPF by a straightforward adaption of a state-of-the-art search-based MAPF solver, Conﬂict Based Search (CBS) (Sharon et al. 2015), and analyze its poor performance. In Section 4, we present a new algorithm, called Multi-Constraint CBS (MC-CBS), that improves CBS by adding multiple constraints in a high-level node expansion. We propose three different approaches to choose such constraints as well as a special constraint representation for regular shaped agents. In Section 5, we explain how to compute heuristics for the high-level search of MC-CBS. In Section 6, we compare the performances of adapted CBS, vari-

Figure 1: Shows two examples of two agents colliding with each other. (a) shows a 4-neighbor 2D grid with squareshaped agents, where lines represent edges, intersection points represent vertices, and black cells represent obstacles. (b) shows a 3D roadmap with sphere-shaped agents.

ants of MC-CBS, adapted EPEA* and adapted MDD-SAT.1 EPEA* (Goldenberg et al. 2014) is a state-of-the-art A*- based MAPF solver, and MDD-SAT (Surynek et al. 2016) is a start-of-the-art reduction-based MAPF solver. All MCCBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* in all cases and MDD-SAT in some cases.

2 Problem Deﬁnition and Related Concepts

We formalize LA-MAPF as follows: We are given an undirected graph G = (V, E) embedded in a d-dimensional Euclidean space (usually d = 2, 3). Each vertex v V is a point in the Euclidean space that is speciﬁed by its coordinates (v(1), . . . , v(d)). We are also given a set of k agents {a1 . . . ak} with unique start and goal vertices, and each agent has a ﬁxed geometric shape around a reference point that cannot undergo transformations like rotations. We say that an agent is at a vertex v when its reference point is at vertex v, and we say that an agent traverses an edge (u, v) when its reference point moves along edge (u, v). If ai is at vertex v, then the set of points occupied by ai is denoted by Si(v). Figure 1(a) shows an example of two square-shaped agents on a 2D grid. Their reference points are the top-left corners. a1 (blue) is at vertex v = (3, 3) with an 1.5 1.5 square shape S1(v) = {(x(1), x(2)) | 0 x(j) v(j) 1.5, j = 1, 2}, and a2 (red) is at vertex u = (3, 1) with a 2.5 2.5 square shape S2(u) = {(x(1), x(2)) | 0 x(j) u(j) 2.5, j = 1, 2}. Figure 1(b) shows another example on a 3D roadmap where two sphere-shaped agents a1 (blue) and a2 (red) are at vertices F and E, respectively. Their reference points are the sphere centers. On the same graph G, different agents have different traversable subgraphs because of their different shapes (e.g., in Figure 1(a), a1 can be at (0, 0) while a2 cannot). This subgraph Gi = (Vi, Ei) is called the conﬁguration space of ai. We assume that the start and goal vertices of each agent are in the same connected component of its conﬁgu-

1We refer to the adapted versions of CBS, EPEA* and MDDSAT also as CBS, EPEA* and MDD-SAT, respectively.

ration space. At each discrete timestep t, ai can either wait at its current vertex v Vi, or move to an adjacent vertex u, where (v, u) Ei. Both wait and move actions have unit costs unless ai terminally waits at its goal vertex. In MAPF, a conﬂict between two agents is either a vertex conﬂict, where two agents are at the same vertex at the same timestep, or an edge conﬂict, where two agents traverse the same edge in opposite directions at the same timestep. In LA-MAPF, however, agents could collide when they are in close proximity with each other. Therefore, we generalize the deﬁnitions of conﬂicts. We deﬁne a vertex conﬂict as a ﬁve-element tuple ai, aj, u, v, t , where the shapes of ai and aj overlap if ai is at vertex u and aj is at vertex v at the same timestep t. Similarly, we deﬁne an edge conﬂict as a seven-element tuple ai, aj, u1, u2, v1, v2, t , where the shapes of ai and aj overlap if ai moves from vertex u1 to u2 and aj moves from vertex v1 to v2 at the same timestep t. We assume that there exists a conﬂict detection function that checks entire paths and returns all vertex conﬂicts and edge conﬂicts. Our task is to ﬁnd a set of conﬂict-free paths that move all agents from their start vertices to their goal vertices with minimum sum of costs of all paths. Previous research has also used generalized conﬂicts. H onig et al. (2018) considered the shape of large agents like quadrotors and deﬁned three new types of generalized conﬂicts: vertex-vertex conﬂicts, vertex-edge conﬂicts and edge-edge conﬂicts, where the ﬁrst one is a special case of our vertex conﬂicts and the two other ones are special cases of our edge conﬂicts. They solved the problem by adapting ECBS (Barer et al. 2014), a suboptimal version of CBS, to their problem in a way similar to the adapted CBS that we introduce in Section 3.2. We show in Section 3.2 that this kind of direct adaptation is inefﬁcient in many cases. Using a different perspective, Atzmon et al. (2018) generalized the deﬁnition of a conﬂict from a timestep to a time range in order to obtain robust plans.

3 Conﬂict-Based Search (CBS)

LA-MAPF is NP-hard, since it generalizes MAPF, which is NP-hard (Yu and La Valle 2013b; Ma et al. 2016b). In this section, we review Conﬂict-Based Search for MAPF and introduce its direct adaption to LA-MAPF.

3.1 CBS for MAPF

Conﬂict-Based Search (CBS) (Sharon et al. 2015) is a twolevel search-based algorithm that is complete and optimal for MAPF. Its high level performs a best-ﬁrst search on a binary constraint tree (CT). Each CT node contains a set of constraints, where a constraint is either a vertex constraint ai, u, t that prohibits agent ai from being at vertex u at timestep t or an edge constraint ai, u1, u2, t that prohibits ai from moving from u1 to u2 at timestep t, and a set of paths for all agents that satisfy all constraints. The cost of the CT node is the sum of costs of all paths. The CT root node contains an empty set of constraints and a set of individual shortest paths. When the high level expands a CT node N, it ﬁrst runs a conﬂict detection function to ﬁnd conﬂicts among all of its

paths. If they are conﬂict-free, then N is a goal node and CBS returns its paths. Otherwise, the high level arbitrarily chooses and resolves a vertex conﬂict ai, aj, u, v, t (u = v in MAPF) or an edge conﬂict ai, aj, u1, u2, v1, v2, t (u1 = v2 and u2 = v1 in MAPF) by splitting N into two child CT nodes, N1 and N2, that inherit all constraints and paths from N. The high level also adds a new vertex constraint ai, u, t or edge constraint ai, u1, u2, t to N1 and a new vertex constraint aj, v, t or edge constraint aj, v1, v2, t to N2 and then runs a low-level search for both child nodes to ﬁnd shortest paths for all agents that satisfy the new set of constraints in each of them. Since each child node has one additional constraint imposed on only one agent, the lowlevel search needs to re-plan the path for only that one agent. Improved CBS (ICBS) (Boyarski et al. 2015) improves CBS by classifying conﬂicts and choosing to resolve cardinal conﬂicts ﬁrst. A conﬂict is cardinal if, when CBS uses this conﬂict to split a CT node, the cost of each one of the two resulting child nodes is larger than the cost of the CT node. CBSH (Felner et al. 2018) improves it further by aggregating cardinal conﬂicts and computing admissible heuristics to guide the high-level search.

3.2 CBS for LA-MAPF

Similar to techniques used in (H onig et al. 2018), CBS can be directly adapted to LA-MAPF by considering generalized conﬂicts and changing the conﬂict detection function to the one discussed in Section 2. However, the resulting version of CBS is very inefﬁcient for large agents. For example, in Figure 1(a), a1 tries to move from (3, 0) to (3, 4), and a2 tries to move from (0, 1) to (3, 1). In the CT root node, both agents follow their individual shortest paths and have vertex conﬂicts at timesteps 1, 2 and 3. The drawing is a snapshot that shows their vertex conﬂict at timestep 3. If CBS chooses to resolve this vertex conﬂict, then the right child node has a new constraint a2, (3, 1), 3 . a2 is forced to wait for one timestep and thus stays at vertex (2, 1) at timestep 3. However, a2 then still conﬂicts with a1 at timestep 3 in this child node. The conﬂict between a1 and a2 at timestep 3 is therefore not resolved by this split. Although it will be resolved eventually, many intermediate CT nodes are generated.

4 Multi-Constraint CBS (MC-CBS)

The above observations motivate the idea of adding multiple constraints in a single CT node expansion. We present a new algorithm, MC-CBS, which adds multiple constraints for the same timestep to child nodes in order to resolve multiple related conﬂicts in a single CT node expansion, which resembles lookahead reasoning at the high level and can result in smaller CTs, thus making the search more efﬁcient. We say that two vertex or edge constraints for ai and aj respectively are mutually disjunctive iff any pair of conﬂictfree paths for ai and aj satisﬁes at least one of the two constraints, i.e., there do not exist two conﬂict-free paths such that both constraints are violated. In particular, the constraints that CBS adds to two child nodes are always mutually disjunctive. We say that two sets of constraints are mutually disjunctive iff each constraint in one set is mutually

disjunctive with each constraint in the other set. Intuitively, working with mutually disjunctive constraint sets gives us the power of constraint propagation. When MC-CBS resolves a conﬂict ai, aj, u, v, t (or ai, aj, u1, u2, v1, v2, t ) in a CT node N, it generates two child nodes with N s current constraint set and additional constraint sets, C1 and C2, respectively:

1. C1 and C2 include the core constraints that CBS uses to resolve the conﬂict, i.e., ai, u, t C1 and aj, v, t C2 (or ai, u1, u2, t C1 and aj, v1, v2, t C2).

2. C1 and C2 are enhanced with other constraints that ensure that C1 and C2 remain mutually disjunctive.

Different strategies for choosing C1 and C2 are discussed in Sections 4.1 and 4.2. Here, we show that MC-CBS is complete and optimal.

Lemma 1 (Optimality). If MC-CBS terminates, it returns a set of conﬂict-free paths with the minimum sum of costs.

Proof. The proof has two parts. We ﬁrst show that, for a given CT node N with constraint set C, any set of conﬂictfree paths that satisfy C also satisfy at least one of the constraint sets C S C1 and C S C2. This is true because, otherwise, there would exist two conﬂict-free paths such that both of them are consistent with C but one path violates a constraint c1 C1 and the other one violates a constraint c2 C2. Then, c1 and c2 are not mutually disjunctive, contradicting the assumption. Therefore, the expansion of a CT node does not lose any set of conﬂict-free paths. The second part is the same as the proof of optimality for CBS (Sharon et al. 2015). The cost of a CT node is a lower bound on the sum of costs of conﬂict-free paths that satisfy its constraint set. The high-level search chooses to expand a CT node with minimum cost and the expansion does not lose any conﬂict-free paths. So the cost of the chosen CT node is always a lower bound on the sum of costs of all conﬂict-free paths. Therefore, the set of paths of the ﬁrst CT node chosen for expansion whose paths are conﬂict-free is indeed a set of conﬂict-free paths with the minimum sum of costs.

Lemma 2 (Completeness). MC-CBS terminates if there exists a set of conﬂict-free paths.

Proof. The costs of CT nodes are non-decreasing in expansion order because MC-CBS runs a best-ﬁrst search and the costs of child nodes are at least as large as the costs of their parents. In addition, there are a ﬁnite number of CT nodes for a given cost c, because there are only a ﬁnite number of possible conﬂicts within c timesteps and, once a conﬂict is resolved at CT node N, it does not reappear in the subtree of N. Therefore, a set of conﬂict-free paths must be found after expanding a ﬁnite number of CT nodes.

There are numerous ways to generalize the core constraints to two mutually disjunctive constraint sets for MCCBS. For example, in Figure 1(a), the two sets ﬁrst include the core constraints, i.e., C1 = { a1, (3, 3), 3 } and C2 = { a2, (3, 1), 3 }. We can add constraints for other vertices to C1 and C2, such as a2, (2, 1), 3 to C2 (because a1 being at (3, 3) conﬂicts with a2 being at (2, 1)). We can also

add constraints for other timesteps, such as a2, (3, 2), 4 to C2 (because, no matter where a1 moves from (3, 3) at timestep 3, it conﬂicts with a2 being at (3, 2) at timestep 4). In this paper, we only add constraints for the same timestep to keep MC-CBS simple. In general, it is hard to determine whether two constraints for different timesteps are mutually disjunctive. Moreover, we can often ﬁnd equivalent (e.g., block the same set of paths) or better (e.g., block a larger set of paths) constraint sets to add for the same timestep. In Figure 1(a), the pair of constraint sets { a1, (3, 3), 3 } and { a2, (3, 1), 3 , a2, (3, 2), 4 } is no better than the pair of constraint sets { a1, (3, 3), 3 } and { a2, (x, y), 3 | 2 x 4, 1 y 3} because a2 can only be at vertex (x, y), 2 x 4, 1 y 3, at timestep 3 to reach vertex (3, 2) at timestep 4. In Sections 4.1 and 4.2, we introduce three approaches for choosing constraint sets for MC-CBS. In Section 4.3, we present a new representation of constraint sets to speed up MC-CBS for regular shaped agents. We only discuss the constraint sets for vertex conﬂicts since the constraint sets for edge conﬂicts can be derived analogously.

4.1 Asymmetric and Symmetric Approaches Consider the resolution of a vertex conﬂict ai, aj, u, v, t . Two mutually disjunctive constraint sets can be built asymmetrically or symmetrically.2

1. The asymmetric approach (ASYM) adds a constraint set of size one { ai, u, t } to the left child node that prohibits agent ai from being at its current vertex v at timestep t and a large constraint set { aj, v , t | ai, aj, u, v , t is a vertex conﬂict} to the right child node that prohibits agent aj from being at any vertex at timestep t where it could collide with ai.

2. The symmetric approach (SYM) chooses a point p in the Euclidean space that is inside the overlap area Si(u) Sj(v), and then adds one constraint set to each child node. The constraint set blocks all vertices that the agent could be at while including p in its shape, i.e., C1 = { ai, v , t | p Si(v ), v V } and C2 = { aj, v , t | p Sj(v ), v V }. Unlike ASYM, that adds a constraint set of size one to one child node and a large constraint set to the other child node, SYM adds constraint sets of similar cardinalities to both child nodes.

For example, in Figure 1(a), ASYM adds { a1, (3, 3), 3 } to one child node and { a2, (x, y), 3 | 1 x, y 4} to the other child node. But SYM adds { a1, (x, y), 3 | 2 x, y 3} to one child node and { a2, (x, y), 3 | 1 x, y 3} to the other child node when the chosen point p is (3.25, 3.25). Thus, ASYM adds 17 constraints in total while SYM adds only 13 constraints in total. However, we empirically show in Section 6.1 that SYM usually outperforms ASYM, perhaps because SYM usually has more pairs of mutually disjunctive constraints, e.g., 36 pairs in this

2Atzmon et al. (2018) introduced similar asymmetric and symmetric approaches to add multiple constraints, although they studied a different problem and added constraints for the same vertex at different timesteps.

example. Since each such pair may block some conﬂicting paths, SYM usually results in smaller search spaces. Another important observation is that not all constraints generated by SYM or ASYM are relevant. Some constraints are irrelevant because they block vertices that are not reachable by the agents at the given timestep, such as a2, (4, 1), 3 given that the start vertex of ai is (0, 1), and some constraints are less relevant because they block the vertices that can be reached only when paths are very long, such as a2, (1, 4), 3 given that the start vertex and the goal vertex of a2 are (0, 1) and (3, 1), respectively. Therefore, we present a more intelligent approach that aims to add more relevant constraints in the next section.

4.2 Maximizing the Costs of Child Nodes When splitting a CT node, large costs of both child nodes mean more progress for the high-level search. Thus, the costs of the child nodes can be used to measure the relevance of a constraint set. ICBS (Boyarski et al. 2015) utilizes this insight by choosing cardinal conﬂicts whenever available, where both child nodes have higher costs than their parent node. Here, we try to ﬁnd a pair of constraint sets where the child nodes have the highest possible costs.

Calculating the weights of constraint sets. A Multi Valued Decision Diagram (MDD) (Sharon et al. 2013) MDDµ i is a directed acyclic graph that consists of all paths of cost µ for agent ai from its start vertex to its goal vertex. All nodes at depth t of MDDµ i correspond to all vertices where ai can be at timestep t en route such a path. Therefore, if a constraint set for timestep t blocks all vertices of MDDµ i at depth t, the cost of the agent s new path is at least µ + 1 after adding it. Conversely, if a constraint set for timestep t does not block all vertices of MDDµ i at depth t, the cost of the agent s new path is at most µ after adding it. ICBS uses MDDµ i to predict whether the cost of ai s path is µ or higher after adding a constraint. Here, we generalize this idea and use MDDµ+d i to predict whether the cost of ai s path is µ, . . . , µ + d or at least µ + d + 1 after adding a constraint set. d N is called the lookahead depth, and the predicted cost increment in {0, 1, . . . , d + 1} is called the weight of the constraint set. Given a CT node N and an agent ai whose path is of cost µ, we build MDDµ+d i . During this construction, we also assign a weight w to each MDD node (v, t) such that µ + w equals the cost of ai s shortest path moving from its start vertex to its goal vertex via vertex v at timestep t, i.e., (v, t) MDDµ+w i and (v, t) / MDDµ+w 1 i . The weight of a constraint set C for ai at timestep t is calculated as follows. Consider all MDD nodes at depth t: (1) If C does not block all MDD nodes with weight 0, then the cost of ai s path after adding C does not change, and thus the weight of C is 0. (2) Otherwise, if C blocks all MDD nodes with weights no more than w (0 w < d) but does not block all MDD nodes with weight w + 1, then the cost of ai s path after adding C increases by exactly w + 1, and thus the weight of C is w + 1. (3) Otherwise, C blocks all MDD nodes, the cost of ai s path after adding C increases by at least d + 1, and thus the weight of C is d + 1.

Algorithm 1: A template for Max Weight-d.

Input: Vertex conﬂict ai, aj, u, v, t , and depth d. Output: Constraint sets, C1 and C2, and weights, w1 and w2.

1 C1 { ai, u, t };

2 C2 { aj, v , t | ai, aj, u, v , t is a vertex conﬂict};

3 w1 get Weight(C1); w2 get Weight(C2);

4 for w 1 = w1 + 1 : d + 1 do

5 C 1 { ai, u , t | (u , t) MDDµ+d i and its weight < w 1}// µ is the cost of ai s shortest path.

6 C 2 { aj, v , t | aj, v , t is mutually disjunctive with every constraint in C 1};

7 if aj, v, t / C 2 then

9 w 2 get Weight(C 2);

10 if {w 1, w 2} is better than {w1, w2} then

11 C1, C2, w1, w2 C 1, C 2, w 1, w 2;

12 return C1, C2, w1 and w2;

Maximizing the weights of constraint sets. We can now design a new approach for choosing constraint sets for MCCBS based on maximizing their weights. We refer to this approach as Max Weight-d (MAX-d or MAX for short). It builds MDDs for both agents with lookahead depth d and chooses the best pair of constraint sets, i.e, the pair that maximizes the smaller weight of the two. It breaks ties by preferring the pair with the maximum sum of weights.

Algorithm 1 shows the pseudo-code for MAX. It enumerates all possible weights of C1 and, for each possible weight, computes the maximum weight of C2 such that C2 includes the core constraint and is mutually disjunctive with C1. Initially, it regards the pair of constraint sets generated by ASYM as the best pair seen so far (Lines 1-3). It then iteratively increases the weight w 1 of the ﬁrst constraint set (Line 4). In each iteration, it ﬁrst chooses C 1 to be of minimum size for the given weight w 1 (Line 5), i.e., C 1 only blocks those MDD nodes whose weights are smaller than w 1. It then builds C 2 of maximum size to be mutually disjunctive with C 1 (Line 6). If the core constraint aj, v, t / C 2, indicating that C 1 cannot have a weight equal to or larger than w 1, it just returns the best constraint sets and weights found so far (Lines 7-8). Otherwise, it computes the weight of C 2 (Line 9) and updates the best constraint sets and weights if necessary (Lines 10-11).

Algorithm 1 is shown only for vertex conﬂicts for ease of explanation. When expanding a CT node in MC-CBS, we run Algorithm 1 for all vertex conﬂicts and edge conﬂicts and choose to resolve the conﬂict with the best constraint sets. Particularly, the smaller weight of two constraint sets for cardinal conﬂicts is always at least one, and the smaller weight of two constraint sets for other conﬂicts is always zero. Therefore, cardinal conﬂicts still have higher priority than other conﬂicts, which is consistent with the conﬂicts prioritization of ICBS.

4.3 Constraints for Regular Shaped Agents Agents often have regular shapes, such as rectangles and circles in a 2D space or cuboids and spheres in a 3D space. In such cases, two mutually disjunctive constraint sets have geometric representations that can be leveraged for computational beneﬁts. For example, when all agents are rectangular, an agent ai of size si = (s(1) i , s(2) i ) whose reference point is the point with minimum coordinates has Si(v) = { p | v p v + si}. Here, v is the vector representation of vertex v and the vector inequalities indicate that the inequalities hold for both dimensions. The tuple ai, aj, u, v, t is a vertex conﬂict iff Si(u) Sj(v) = or, equivalently,

sj v u si. (1)

A rectangle constraint of the form ai, umin, umax, t can be used to represent a constraint set that prohibits agent ai from being in the rectangular area {v | umin v umax} at timestep t. We say that two rectangle constraints ai, umin, umax, t and aj, vmin, vmax, t are mutually disjunctive iff their corresponding constraint sets are mutually disjunctive or, equivalently, sj vmin umax and vmax umin si. We can replace the constraint sets C1 and C2 for MC-CBS by two rectangle constraints. Instead of checking for each pair of constraints in C1 and C2 whether they are mutually disjunctive we need to only check two diagonal vertices, and all approaches in Sections 4.1 and 4.2 can thus be simpliﬁed. For some other regular shaped agents, such as circle, cuboid or sphere shaped agents, we can use similar representations and thus simplify MC-CBS as well.

5 Adding Heuristics to MC-CBS Felner et al. (2018) improve CBS by adding heuristics to the high-level search. A CT node s g-value is its cost, and its admissible heuristic is the cost of the minimum vertex cover of an unweighted conﬂict graph. The conﬂict graph has vertices representing agents and edges representing cardinal conﬂicts between agents. Here, we generalize this model to a weighted conﬂict graph GCF = (VCF , ECF ), where each vertex vi VCF represents an agent ai, each edge (vi, vj) ECF represents cardinal conﬂicts between agents ai and aj, and each pair of weights wij and wji for edge (vi, vj) represents that either ai has to increase its cost by at least wij or aj has to increase its cost by at least wji in order to resolve this conﬂict. In MC-CBS, we use the weights of C1 and C2 for wij and wji, respectively. Then, the optimal solution of the following Integer Linear Program (ILP) is an admissible heuristic:

s.t. ci wijxij, 1 i, j k, i = j xij + xji 1, 1 i < j k xij {0, 1}, 1 i, j k, i = j,

where ci is a variable that represents the minimum cost that ai s path has to increase, and xij is a Boolean variable that represents whether the conﬂict between ai and aj is resolved by increasing the cost of ai s path. The minimum vertex

(a) Success rate.

(b) Expanded CT nodes.

Figure 2: Experimental results for CBS and variants of MCCBS on a 20 20 grid with 10% blocked cells.

cover problem in (Felner et al. 2018) is a special case where all wij = 1. Similar conﬂict graphs and ILP models are used in the context of cost-optimal planning (Pommerening et al. 2015).

6 Experimental Results We implemented and experimented with CBS, all MC-CBS variants (i.e., ASYM, SYM and MAX), EPEA* and MDDSAT on grids with square agents. We also tested CBS and some MC-CBS variants on a 3D roadmap with ellipsoid agents. All CBS-based algorithms used the conﬂict prioritization of ICBS. All algorithms were written in C++ and ran on a 2.80 GHz Intel Core i7-7700 laptop with 8 GB RAM and a runtime limit of 5 minutes. We tried both brute force search and an off-the-shelf ILP solver to solve the ILP in Equation (2) for calculating heuristics. Brute force search ran faster on small graphs while the ILP solver ran faster on large graphs. In both cases, the overhead of computing the heuristics was very small since the conﬂict graphs were sparse. Therefore, we simply use brute force search in our experiments.

6.1 Square Agents on a 2D Grid We ﬁrst compare the performances of CBS and all MC-CBS variants on a 4-neighbor 20 20 2D grid with 10% random blocked cells. Each agent is a 2.5 2.5 square whose reference point is its top-left corner. All algorithms use Equation (1) to detect conﬂicts. All MC-CBS variants use the rectangle constraints discussed in Section 4.3. For MAX, we tested lookahead depths d from 0 to 4. We used 50 instances with randomly generated start vertices and goal vertices for each number of agents.

Overall performances. Figure 2(a) shows the success rate, i.e., number of instances solved within 5 minutes, of each algorithm. The success rates of MAX with d = 1, 2, 3, 4 are quite close to each other, so we only plotted MAX-2. Overall, CBS performs the worst since it repeatedly resolves related conﬂicts between the same agents. SYM, ASYM and MAX-0 perform better since they resolve a set of related conﬂicts in a single expansion. MAX-2 performs the best since it looks ahead several steps and takes into consideration the costs of child nodes. Table 1 shows the runtime

Table 1: Average runtime and number of expanded CT nodes for CBS, SYM and MAX-2 on instances solved by SYM. Cutoff time of 5 minutes is included in the average for unsolved instances. k is the number of agents.

Runtime (ms) Expanded CT nodes k Ins. CBS SYM MAX-2 CBS SYM MAX-2 2 50 8,907 7 2 25,924 20 3 3 50 52,876 903 24 218,136 2,214 36 4 43 >98,056 22,057 2,100 >376,921 43,904 2,958 5 33 >138,875 72,703 3,056 >320,928 125,593 2,683 6 25 >199,285 116,613 6,373 >802,317 244,991 8,324

Table 2: Average runtime (ms) of MAX with different lookahead depths d. Cutoff time of 5 minutes is included in the average for unsolved instances. k is the number of agents.

k d = 0 d = 1 d = 2 d = 3 d = 4 2 6.6 1.8 1.9 1.7 2.1 3 551.1 24.0 23.6 31.6 49.3 4 43,747.1 31,612.9 29,544.7 27,391.2 28,539.8 5 104,597.3 56,336.4 51,225.3 49,273.0 55,912.9 6 152,360.1 70,675.5 61,283.5 66,329.4 68,116.7

and number of expanded CT nodes of CBS, SYM and MAX2 on instances solved by SYM. SYM outperforms CBS by up to three orders of magnitude on both metrics, indicating that the overhead per expanded CT node is negligible for SYM. MAX-2 outperforms SYM by factors of up to 60 and 20 with respect to the number of expanded CT nodes and the runtime, respectively, indicating that it has more overhead per expanded CT node but is still beneﬁcial overall.

Comparing ASYM and SYM. Figure 2(b) shows the number of expanded CT nodes for ASYM and SYM on instances solved by both algorithms. With a few exceptions, SYM outperforms ASYM not only on the success rate but also on the number of expanded CT nodes (and thus the runtime).

Comparing MAX with different lookahead depths. Table 2 compares the runtime of MAX with d ranging from 0 to 4. We observe that MAX with d = 0 (no lookahead) is signiﬁcantly slower than the others. As d increases, the runtime ﬁrst decreases and then increases because a larger lookahead depth has more pruning power but also incurs more overhead. d = 2 or 3 works best in our experiments.

MAX with heuristics. Adding heuristics to MAX decreases both the number of expanded CT nodes and the runtime, although it does not improve its success rate. For instance, adding heuristics to MAX-4 decreases the number of expanded CT nodes by 30.1% and the runtime by 21.5% on 8-agent instances. Similar observations have been made in (Felner et al. 2018) on sparse grids, but in the next subsection we discuss cases where adding heuristics provides a much larger speedup.

6.2 Ellipsoid Agents on a 3D Roadmap We also tested our algorithms on the Swap50 instance from (H onig et al. 2018), that is used to plan paths for quadrotor swarms in a dense 3D space. The environment is

(a) Success rate on small map

(b) Runtime on small map

(c) Success rate on large map

(d) Runtime on large map

Figure 3: Experimental results on 2D grids.

Figure 4: Shape of agents (left), reproduced from (H onig et al. 2018), and the structure of the roadmap (right).

Table 3: The runtime and number of expanded CT nodes on Swap50 with a 3D roadmap. k is the number of agents. MAX+h is MAX-1 with heuristics.

Runtime (ms) Expanded CT nodes k CBS ASYM MAX-1 MAX+h CBS ASYM MAX-1 MAX+h 5 38 61 23 13 18 26 9 7 6 124 122 126 40 28 25 20 11 7 1,175 549 735 290 188 93 100 52 8 253,550 15,829 10,570 5,221 30,411 2,408 1,289 747

a 7.5 m 6.5 m 2.5 m space with ellipsoid agents. The ellipsoids model quadrotors and their downwash effects. The ellipsoids have radii (0.15 m, 0.15 m, 0.3 m) with central reference points, as in Figure 4(left). Agents are required to ﬂy through windows in a wall in opposite directions. The roadmap, generated by the SPARS algorithms (Dobson and Bekris 2014), has 869 vertices and 3,371 edges, as in Figure 4(right). In a preprocessing step, we identify all possible vertex and edge conﬂicts using the swept collision model (H onig et al. 2018). On average, there exist 1.75 different vertex conﬂicts per vertex, and 24.08 different edge conﬂicts per edge. The original instance has 50 agents and was solved by suboptimal solvers in (H onig et al. 2018). We randomly chose a small subset of agents and solved the resulting instance with our optimal algorithms CBS, ASYM, MAX-1, and MAX-1 with heuristics. Table 3 shows the runtime and number of expanded CT nodes. ASYM, MAX-1 and MAX-1 with heuristics decrease the runtime of CBS by factors of up to 16, 24 and 49, respectively. Unlike the results in Section 6.1, adding heuris-

tics here signiﬁcantly reduces the number of expanded CT nodes and runtime because agents traverse narrow corridors in opposite directions, which results in more cardinal conﬂicts.

6.3 Comparing with Other Solvers on 2D Grids

We now compare CBS and two MC-CBS variants, namely SYM and MAX-2, with an A*-based solver, EPEA*, and a reduction-based solver, MDD-SAT, on the same instances as in Section 6.1. We also test them on larger instances with square agents of different sizes randomly chosen from {2.5, 3.5, 4.5}. We used a large 4-neighbor 194 194 2D grid with 51.3% blocked cells, namely the benchmark game map lak503d from (Sturtevant 2012). We used 50 instances with randomly generated start vertices and goal vertices for each number of agents.

EPEA*. A*-based MAPF solvers conduct search in the joint multi-agent state space. EPEA* (Goldenberg et al. 2014) is a lazy version which delays the generation of nodes whose costs are larger than the costs of their parents and thus avoid generating unnecessary nodes. It can be adapted to LA-MAPF by using Equation (1) to identify conﬂict-free actions as legal operators. This adaptation is promising since the branching factor could be smaller than the one for MAPF instances. CBS-based solvers, on the other hand, have more conﬂicts to resolve for LA-MAPF than for MAPF.

MDD-SAT. MDD-SAT (Surynek et al. 2016) is a SATbased MAPF solver. It relies on the construction of a propositional formula that is satisﬁable iff the given MAPF instance has a set of conﬂict-free paths of a certain cost. It introduces a propositional variable X t v(ai) for each agent ai and node (v, t) in ai s MDD that is true iff agent ai is at vertex v at timestep t. MDD-SAT can be modiﬁed for LAMAPF by introducing additional variables Yt u(ai) and constraints involving them to reﬂect the shapes of agents. Here, Yt u(ai) is true iff there exists vertex v such that X t v(ai) is true and vertex u Si(v). In other words, implications X t v(ai) Yt u(ai) added for each vertex u Si(v) ensure that the entire shape of the agent moves in tandem with the reference point. In addition to MDD-SAT s constraints that encode movement rules for reference points, at-most-one

constraints Pk i=1 Yt v(ai) 1 are used to disallow collisions between agents.

Results. Figure 3(a), Figure 3(b) present the success rates and runtimes on the small map. MAD-SAT dominates all other algorithms in terms of success rates within 5 minutes. When we vary the runtime limit, MAX-2 has the highest success rate when the runtime limit is less than 10 s (where instances are relatively easy), while MDD-SAT has the highest success rate when the runtime limit is more than 10 s (where instances are more difﬁcult). Figure 3(c), Figure 3(d) present the success rates and runtimes on the large game map. MAX-2 signiﬁcantly outperforms all other algorithms in all cases except when the runtime limit is less than 0.1 s. Although it is hard to predict the performances of the algorithms in all domains, we can give some guidance based on these observations and analysis. MDD-SAT is strong for difﬁcult problems in small domains. MAX is strong for easy problems or in large domains, despite the fact that its lookahead depth needs to be set appropriately.

7 Conclusions and Future Work In this paper, we generalized MAPF to a practically viable version, called LA-MAPF, that takes into consideration the shapes of agents. We presented MC-CBS, a new algorithm that improves CBS by adding multiple constraints during the expansion of a CT node. Unlike CBS, the MC-CBS allows us to resolve multiple related conﬂicts in one shot, while also generalizing the use of the minimum vertex cover for heuristic guidance of the high-level search. We proposed three approaches for choosing the constraints as well as an approach for computing the heuristics. Empirically, we showed that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime, and the best variant also outperforms EPEA* in all cases and MDD-SAT in some cases. There are many directions for future work. For example, we could study the problem that allows the rotation of shapes and develop sub-optimal LA-MAPF solvers, with the expectation that they would be more scalable than optimal ones.

Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Bart ak, R.; and Zhou, N. 2018. Robust multi-agent path ﬁnding. In So CS, 2 9. Barer, M.; Sharon, G.; Stern, R.; and Felner, A. 2014. Suboptimal variants of the conﬂict-based search algorithm for the multi-agent pathﬁnding problem. In So CS, 19 27. Boyarski, E.; Felner, A.; Stern, R.; Sharon, G.; Tolpin, D.; Betzalel, O.; and Shimony, S. E. 2015. ICBS: Improved conﬂict-based search algorithm for multi-agent pathﬁnding. In IJCAI, 740 746. Dobson, A., and Bekris, K. E. 2014. Sparse roadmap spanners for asymptotically near-optimal motion planning. The International Journal of Robotics Research 33(1):18 47. Erdem, E.; Kisa, D. G.; Oztok, U.; and Schueller, P. 2013. A general formal framework for pathﬁnding problems with multiple agents. In AAAI, 290 296. Felner, A.; Stern, R.; Shimony, S. E.; Boyarski, E.; Goldenberg, M.; Sharon, G.; Sturtevant, N. R.; Wagner, G.; and Surynek, P. 2017. Search-based optimal solvers for the multi-agent pathﬁnding problem: Summary and challenges. In So CS, 29 37.

Felner, A.; Li, J.; Boyarski, E.; Ma, H.; Cohen, L.; Kumar, T. K. S.; and Koenig, S. 2018. Adding heuristics to conﬂict-based search for multi-agent path ﬁnding. In ICAPS, 83 87. Goldenberg, M.; Felner, A.; Stern, R.; Sharon, G.; Sturtevant, N. R.; Holte, R. C.; and Schaeffer, J. 2014. Enhanced Partial Expansion A*. Journal of Artiﬁcial Intelligence Research 50:141 187. H onig, W.; Kumar, T. K. S.; Cohen, L.; Ma, H.; Xu, H.; Ayanian, N.; and Koenig, S. 2016. Multi-agent path ﬁnding with kinematic constraints. In ICAPS, 477 485. H onig, W.; Preiss, J. A.; Kumar, T. K. S.; Sukhatme, G. S.; and Ayanian, N. 2018. Trajectory planning for quadrotor swarms. IEEE Transactions on Robotics 34(4):856 869. Ma, H.; Koenig, S.; Ayanian, N.; Cohen, L.; H onig, W.; Kumar, T. K. S.; Uras, T.; Xu, H.; Tovey, C.; and Sharon, G. 2016a. Overview: Generalizations of multi-agent path ﬁnding to realworld scenarios. In IJCAI-16 Workshop on Multi-Agent Path Finding. Ma, H.; Tovey, C.; Sharon, G.; Kumar, T. K. S.; and Koenig, S. 2016b. Multi-agent path ﬁnding with payload transfers and the package-exchange robot-routing problem. In AAAI, 3166 3173. Ma, H.; Yang, J.; Cohen, L.; Kumar, T. K. S.; and Koenig, S. 2017. Feasibility study: Moving non-homogeneous teams in congested video game environments. In AIIDE, 270 272. Morris, R.; Pasareanu, C.; Luckow, K.; Malik, W.; Ma, H.; Kumar, S.; and Koenig, S. 2016. Planning, scheduling and monitoring for airport surface operations. In AAAI-16 Workshop on Planning for Hybrid Systems. Pommerening, F.; R oger, G.; Helmert, M.; and Bonet, B. 2015. Heuristics for cost-optimal classical planning based on linear programming. In Proceedings of the IJCAI, 4303 4309. Sharon, G.; Stern, R.; Goldenberg, M.; and Felner, A. 2013. The increasing cost tree search for optimal multi-agent pathﬁnding. Artiﬁcial Intelligence 195:470 495. Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conﬂict-based search for optimal multi-agent pathﬁnding. Artiﬁcial Intelligence 219:40 66. Standley, T. S. 2010. Finding optimal solutions to cooperative pathﬁnding problems. In AAAI, 173 178. Sturtevant, N. R. 2012. Benchmarks for grid-based pathﬁnding. Transactions on Computational Intelligence and AI in Games 4(2):144 148. Surynek, P.; Felner, A.; Stern, R.; and Boyarski, E. 2016. Efﬁcient SAT approach to multi-agent path ﬁnding under the sum of costs objective. In ECAI, 810 818. Veloso, M. M.; Biswas, J.; Coltin, B.; and Rosenthal, S. 2015. Cobots: Robust symbiotic autonomous mobile service robots. In IJCAI, 4423 4429. Wagner, G., and Choset, H. 2011. M*: A complete multirobot path planning algorithm with performance bounds. In IROS, 3260 3267. Wurman, P. R.; D Andrea, R.; and Mountz, M. 2008. Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29(1):9 20. Yu, J., and La Valle, S. M. 2013a. Planning optimal paths for multiple robots on graphs. In ICRA, 3612 3617. Yu, J., and La Valle, S. M. 2013b. Structure and intractability of optimal multi-robot path planning on graphs. In AAAI, 1444 1449.