# multiagent_path_finding_on_strongly_biconnected_digraphs__26d34fdf.pdf

Multi-Agent Path Finding on Strongly Biconnected Digraphs

Adi Botea IBM Research Dublin, Ireland

Pavel Surynek Faculty of Mathematics and Physics Charles University Prague Malostransk e n amˇest ı 25, 11 800, Praha 1

Much of the literature on multi-agent path ﬁnding focuses on undirected graphs, where motion is permitted in both directions along a graph edge. Despite this, travelling on directed graphs is relevant in navigation domains, such as pathﬁnding in games, and asymmetric communication networks. We consider multi-agent path ﬁnding on strongly biconnected directed graphs. We show that all instances with at least two unoccupied positions can be solved or proven unsolvable. We present a polynomial-time algorithm for this class of problems, and analyze its complexity. Our work may be the ﬁrst formal study of multi-agent path ﬁnding on directed graphs.

Introduction Multi-agent path ﬁnding (MAPF) is an important computational problem, with applications in areas such as robotics and computer games. Not surprisingly, the problem has received a considerable attention in computer science areas such as artiﬁcial intelligence, robotics and graph theory. In a common problem formulation, coined as cooperative path ﬁnding, the purpose is to navigate every agent from its original location to its target location, while avoiding collisions and deadlocks. The navigation environment is typically represented as a graph. Current sub-optimal, scalable approaches work under the key assumption that the underlying graph is undirected. For instance, algorithms Push and Swap (Luna and Bekris 2011) and Push and Rotate (de Wilde, ter Mors, and Witteveen 2013) implement a core primitive, called swap, where agents must move in both directions along some graph edges. Among other moves, the swap primitive involves moving an agent to an adjacent node, to allow another agent to pass through, after which the ﬁrst agent comes back to its former location, traversing the graph edge in the opposite direction. The MAPP algorithm (Wang and Botea 2011) relies on reverting part of the recently performed moves, after an agent reaches its target. The similar use of edges in both directions appears in the BIBOX algorithm (Surynek 2009) where robots in cycles are rotated in order to relocate a selected robot and eventually rotated back after the robot gets out of the cycle to restore the situation.

Copyright c 2015, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Figure 1: An example of uni-directional road network and its abstraction as a digraph. The elliptic road is uni-directional as a rule. Other roads are uni-directional, as the centrifugal force does not allow making sharp turns.

In navigation domains, uni-directional edges can arise from the properties of the environment, such as the existence of one-way entrances, exits, escalators, bridges and roads. Some agents could be able to travel down the hill or ﬂoat down the river, but not the other way around. Furthermore, the literature shows approaches where unidirectional trafﬁc is imposed on purpose on a game map, with the goal of avoiding head-to-head collisions between mobile agents (Wang and Botea 2008). Motion in directed graphs is also important in asymmetric communication networks (Marina and Das 2002; Jetcheva and Johnson 2006; Wu and Grumbach 2010). Uni-directional networks also appear in trafﬁc domains such as highways and railways. Connection lanes in highway system impose one way routing, as vehicles cannot make sharp turns when traveling at high speeds (see Figure 1). Similar situations arise at railway switches, which can switch a train to another track in one direction only (Bauer and Delling 2008). We contribute the ﬁrst tractability analysis of multi-agent path ﬁnding on directed graphs (digraphs). We focus on strongly biconnected digraphs, i.e., strongly connected digraphs where the undirected graphs obtained by ignoring the edge orientations have no cutting vertices. We demonstrate that all instances with at least two unocuppied vertices can be solved or proven unsolvable in polynomial time. We introduce di BOX, a sub-optimal algorithm, and formally discuss its completeness, correctness, and complexity. Previous formal studies of multi-agent pathﬁnding, sometimes also called coordinated pebble motion in graphs, ap-

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

pear to be focused on undirected graphs (Wilson 1974; Kornhauser, Miller, and Spirakis 1984). For instance, Wilson (1974) explicitly requires that the adjacency relation between agent conﬁgurations (called labellings ) is symmetric, which is equivalent to stating that the graph is undirected. All graphs considered in these two works appear to have undirected edges, with no mention about if/how parts of the study, such as the considered permutation groups, would be applicable to directed graphs. We see our work as complementary to previous work on undirected graphs, being a step towards achieving a similar level of understanding for directed graphs.

Related Work Motion planning problems related to MAPF assume the existence of one mobile robot and several mobile obstacles (Papadimitriou et al. 1994). This could be seen as a multi-agent pathﬁnding problem where only one agent has a speciﬁc target to achieve. Wu and Grumbach (2010) studied motion planning with one agent and several mobile obstacles on directed graphs, showing cases where the feasability can be decided in linear time. Much of the MAPF literature, including algorithms named in the introduction, focuses on undirected graphs. Part of the existing methods, however, can be applied to both directed and undirected graphs, even though they are typically evaluated on undirected graphs, such as grid maps. Examples include sub-optimal, incomplete methods (Silver 2006), as well as optimal algorithms (Standley 2010; Sharon et al. 2013). The latter are less scalable, which is not surprising, given that solving MAPF optimally has been shown to be NP-hard (Ratner and Warmuth 1986; Surynek 2010). A major focus in these contributions (Standley 2010; Sharon et al. 2013) is an improved speed performance in practice. Our contributions are substantially different, focusing on a theoretical analysis of MAPF on directed graphs, as explained in the last part of the introduction.

Background In this section we overview a few concepts and results from the literature that form a starting point to our approach. Deﬁnition 1. Having a digraph D = (V, E) and a set of agents A, a conﬁguration of agents over D is a placement of agents in vertices of the graph, with at most one agent in each vertex. Formally, the conﬁguration is a uniquely invertible assignment of agents to vertices α : A V . If we need to know what agent is placed in a given vertex we may use inverse conﬁguration α 1 : V A {blank} which is well deﬁned due to unique invertibility of α (blank is used for unoccupied vertices). A conﬁguration can be transformed to another by a move of agent. An agent can be moved in discrete time steps to the neighboring vertex provided the target vertex is unoccupied. The move is possible only along positive orientation of edges. For simplicity, in this theoretical study we assume that agents move one at a time. Deﬁnition 2. The instance of multi-agent path ﬁnding over directed graphs (d MAPF) consists of a digraph D = (V, E),

Figure 2: An example of a strongly biconnected digraph and its ear decomposition. Dashed edges are trivial derived ears (not explicitly labelled to avoid clutter).

a set of agents A, an initial conﬁguration α0 : A V , and a goal conﬁguration α+ : A V . The task is to ﬁnd a sequence of moves over D that transform α0 to α+. Deﬁnition 3. An ear decomposition of a digraph D = (V, E) is an ordered sequence of sub-digraphs of D, say [L0, L1, . . . , Lr], such that: L0 is a cycle; and i {1 . . . r}, Li is a path whose two endpoints belong to Di = 0 j<i Lj, but no other vertices or edges of Li belong to Di. Each sub-digraph Li is called an ear (see Figure 2). An ear is trivial if it has exactly one edge (Bang-Jensen and Gutin 2008). An ear is cyclic if its endpoints are represented by a single vertex. We say that L0 is the basic cycle and all other ears are derived ears. Given an ear L, |L| denotes its number of vertices. The interior of a derived ear L, denoted as int(L), refers to the contained vertices different from its endpoints. Its number of vertices is denoted as |int(L)|. The endpoints are called the entrance and the exit point, respectively. A digraph is said to be trivial iff it has only one vertex. In this paper, we work with non-trivial digraphs. Given an ear decomposition O = [L0, L1, . . . , Lr], we call the k-preﬁx subgraph the subgraph restricted to the ﬁrst k ears, Ok = [L0, L1, . . . , Lk]. Deﬁnition 4. An open ear decomposition of a digraph D is an ear decomposition with no cyclic derived ears. An undirected graph G is biconnected if G is connected and there are no cut vertices in G. A digraph D is strongly connected if for any two distinct vertices v and w, there are both a path from v to w and a path from w to v in D. Given a digraph D, G(D) is the underlying graph of D, i.e., the undirected graph obtained by ignoring the orientation of the arcs (Wu and Grumbach 2010). Deﬁnition 5 (Wu and Grumbach 2010). Let D be a digraph. D is said to be strongly biconnected if D is strongly connected and G(D) is biconnected. Theorem 1 (Wu and Grumbach 2010). Let D be a nontrivial digraph. D is strongly biconnected iff D has an open ear decomposition. Moreover, any cycle can be the starting point of an open ear decomposition.

Solving Strongly Biconnected Digraphs In this section we focus on solving multi-agent path ﬁnding instances on strongly biconnected digraphs. We will

Figure 3: An example of a partially bidirectional cycle.

show that all instances with two or more unoccupied vertices (blanks) can be solved (or proven unsolvable) in polynomial time, and will present algorithms suitable for this problem.

Deﬁnition 6. A digraph is a partially-bidirectional cycle if it consists of a simple cycle C, plus zero or more edges of the type (u, v), where (v, u) C (i.e., edges obtained by swapping the direction of an edge from C - see Figure 3).

Deﬁnition 7. We say that an open ear decomposition of a strongly biconnected digraph is regular if the basic cycle L0 has three or more vertices, and there exists a non-trivial derived ear with both ends attached to the basic cycle.

Proposition 1. For every strongly biconnected digraph D = (V, E), exactly one of the following two cases holds:

1. D has a regular open ear decomposition; or 2. D is a partially-bidirectional cycle.

Proof. Part A: Showing that at least one case holds. We start by noting that any strongly biconnected digraph with three or fewer vertices satisﬁes case 2. Thus, in the rest of Part A, we assume that |V | 4. Let [L0, . . . , Lr] be an open ear decomposition for D. Unless L0 already has three or more vertices, we modify the open ear decomposition slightly to obtain a basic cycle with that property. Indeed, when L0 has two vertices, there must exist a derived non-trivial ear L, since the graph has 4 or more vertices. Ear L, together with one edge from L0, become the new basic cycle in the decomposition. The other edge from L0 becomes a trivial derived ear. In the rest of the analysis in Part A we can assume that |L0| 3. At this point we distinguish between two scenarios. First, we consider the case when L0 contains every vertex in V . If there exists an edge e E \ L0 that connects two vertices p and q that are not next to each other in the basic cycle L0, then the edge e = (p, q) and part of L0 s edges create a new basic cycle L 0. The remaining edges of L0 create a nontrivial derived ear. We are now in case 1 of the proposition. If no such an edge e exists, we are in case 2. Consider now the scenario when L0 contains only a subset of the vertices in V . It remains to show that a non-trivial derived ear exists. Consider a vertex w / L0 and a path from some vertex p L0 to w. (Such a path always exists, as the digraph is strongly biconnected.) The ﬁrst edge (r, s) on that path that does not belong to L0 is the beginning of an ear with at least one interior vertex, namely s. It follows that one or more non-trivial derived ears exist. The ﬁrst one

in the ordering of the decomposition has both its endpoints on L0. This corresponds to case 1 of the proposition. Part B: Showing that at most one case holds. This can be proven by contradiction. Assume a given strongly biconnected digraph D is a partially-bidirectional cycle, and it has a regular open ear decomposition. As D is a partiallybidirectional cycle, the only options for the basic cycle L0 that could occur in an open ear decomposition are: i) L0 has two vertices; or ii) L0 contains all vertices. Option i) contradicts the requirement that L0 has at least three vertices. Option ii) contradicts the requirement that there exists at least one non-trivial derived ear.

Partially-bidirectional cycles

In discussing multi-agent path ﬁnding on strongly biconnected digraphs, we start with the easy case of partiallybidirectional cycles. Then, in the next section, we discuss the complementary, more involved case of strongly biconnected digraphs with regular open ear decompositions.

Proposition 2. An instance on a partially-bidirectional cycle, with at least one blank, has a solution if and only if the ordering of the agents in the initial state is identical with the ordering in the goal state.

Proof. The proof is obvious, as no swapping between agents is possible: an instance is solvable if and only if the agents come in the right order in the ﬁrst place.

Digraphs with regular open ear decompositions

In this section we show that, on digraphs with a regular open ear decomposition, every instance with two or more blanks has a solution. For simplicity, assume that exactly two blanks are available. We present an algorithm capable of computing solutions in polynomial time. Similarly to Surynek s (2009; 2014) strategy for undirected graphs, our algorithm solves the ears one by one, in the reverse order, solving L0 at the end. When solving a derived ear, we never touch the interior of previously solved ears. A derived ear is solved if all interior positions labelled as goals are occupied by the corresponding agents, and all other interior positions (if any) are blank.

Borrowing blanks for L0. With no loss of generality, we assume that, in the goal conﬁguration, the two blanks are inside the basic cycle L0. When this doesn t hold, the instance is converted into another instance as follows. Identify a node g that must be blank in the goal, and a directed path from g to a location n L0. Shift all goal positions backwards by one step along this path, resulting in a goal state where the blank is at n L0. We call this procedure Borrow Blanks. At the end, agents are pushed along this path by one step each, reaching the original goal (method Return Blanks).

Solving derived ears. Solving a derived ear Li, i > 0, with a goal conﬁguration q1, . . . qz, pushes agents inside the ear in order, starting with qz, the agent whose goal is the farthest away from the ear s entrance.

Assume that the agents ql+1, . . . qz have been pushed inside, on the ﬁrst z l interior positions of Li, and we need to insert the next agent ql. For simplicity, and without any loss of generality, assume that all interior positions of Li are occupied, and the two available blanks are located elsewhere. We distinguish between two cases. In case 1, the next agent ql to insert is outside the ear Li. First, we bring one blank to the last interior position of Li. As blanks travel backwards in a directed graph, the positions of ql+1, . . . qz are not impacted. Then, agent ql is brought to the entrance of the ear, without touching S j i int(Lj). This is possible with one remaining blank in use, according to Theorem 14 in (Wu and Grumbach 2010). We call the method that can move an agent within a k-preﬁx subgraph Move Agent In Subgraph. Then agent ql is pushed inside Li, reaching a conﬁguration where the ﬁrst z l + 1 interior positions of Li are occupied with agents ql, ql+1, . . . , qz. This completes case 1. Let us recall that agent relocation as suggested in (Wu and Grumbach 2010) can be implemented with the worst case time complexity O(|V |2) and it produces O(|V |2) moves. Deﬁnition 8. Let π be a simple path (chain) and let n be node in the path. An edge (n, m) is an escape door for π if either m does not belong to π, or m is in π, being at least two positions earlier than n in π. Intuitively, an escape door allows an agent to avoid moving forward on a given path π. Proposition 3. Let O = [L0, L1, . . . , Lr] be a regular open ear decomposition of a strongly biconnected digraph. For any derived ear Li, i > 0, there exist a path π in Oi 1, from the exit to the entrance of Li, such that π has an escape door (n, m).

Proof sketch. Let a and b be the entrance and the exit of Li. As Oi 1 is strongly biconnected, it has a path from a to b and a path π from b to a. Assumming there is no escape door along π, it follows that Oi is in fact a chain of nodes (between a and b) with every two adjacent nodes linked in both directions. This contradicts the requirement that the basic cycle has 3 or more nodes.

In case 2, the agent ql is inside the ear. It has to be brought out ﬁrst, after which the agents ql+1, . . . qz, if any, will be reinserted. This method is called Take Agent Outside Ear. Here it is how it works. We build a simple cycle C by putting together Li and π, and bring two blanks to nodes m and n mentioned in Proposition 3. Agents are pushed forward (rotated) repeatedly, in the cycle C , until 1) all agents ql+1, . . . qz (if any) reach again their positions inside Li; and 2) ql is outside the interior of Li. Besides forward moves along C , there is one exception that applies whenever ql is at node n. Instead of pushing ql forward along C , ql is pushed through the escape door to m. Even if m C , recall that m is not the node right before n in the cycle. This ensures that pushing ql from n to m does not cause a deadlock (i.e., there is no repetition of the previous global agent conﬁguration). After applying method Take Agent Outside Ear, ql is outside int(Li) and agents ql+1, . . . qz, if any, are inside Li. This ﬁts case 1 and the processing continues as in that case.

Figure 4: Bringing u (Mickey) next to v (Minnie) as part of solving the basic cycle. Mickey travels along L in such a way that, at the end, L preserves its goal conﬁguration. Apart from relocating u, all other ordering relations in L0 are preserved.

Solving the basic cycle. When ordering agents inside the cycle L0, we make use of a non-trivial derived ear L with both ends connected to L0. Such an ear L always exists in a regular decomposition. All agents belonging to interior positions of L are already solved, as described earlier. Let q1, . . . qz be these agents in the order they are arranged on their goal positions in the ear L. Recall that there are two blanks available in L0. Assume that two agents u (Mickey) and v (Minnie) need to be brought next to each other in L0, in the order u, v in the direction L0. This process, described in detail below, is referred to as method Bring Agents Next To Each Other. A high-level overview of the process is shown in Figure 4. As highlighted in Figure 5, this is split into several stages: Mickey s departure: Rotate agents in the basic cycle L0 until u is at the entrance of the ear L, and a blank is available at the exit of the ear. Mickey s admission into the bubble ride: Push all agents in L one step further, so that agent u is on the ﬁrst interior position of L, and qz is in L0. Mickey s bubble ride: Bring u along the ear L, until u reaches the last interior position of L. The bubble ride needs to be more sophisticated than simply pushing all agents forward along L until agent u is on the last position. The reason is that L s internal conﬁguration has to be kept in such a way that, at the end of the bubble ride, L s goal conﬁguration is very easy to restore. A bubble ride is a series of macro-steps. Each macro step progresses u along L by one position, and also re-inserts back into L an agent temporarily removed from L. Agents are re-inserted in the same order in which they left the ear L, reconstructing L s goal conﬁguration step by step. The dashed box in Figure 5 illustrates one macro, changing the conﬁguration of int(L) from u, 1, 2, 3 into 4, u, 1, 2 (listing agents from the ﬁrst to the last, in the direction of travel along L). More generally, the k-th macro step starts from a conﬁguration of int(L) such as qz k+2, . . . , qz, u, q1, . . . , qz k.1 Agent qz k+1 is in L0.

1When l > l , sequence ql . . . ql is deﬁned as the empty set.

Bubble ride macro-step

Figure 5: Top: Mickey s departure (left) and admission into the bubble ride (right). In the dashed box, one macro-step as part of a bubble ride: rotation inside L0 (right), followed by progress along L (left). Bottom: Minnie s trip (left) and reuniﬁcation (right). Clean-up not shown.

A macro-step has two sub-macros . First, agents are rotated inside L0 until a blank is available at the exit from L, and qz k+1 is at the entrace of L. Then, all agents along L are pushed one step forward, pushing qz k into L0, and pushing agent qz k+1 onto the ﬁrst interior position of L. At the end of the k-th macro step, the conﬁguration of int(L) is qz k+1, . . . , qz, u, q1, . . . , qz k 1. Agent qz k is inside L0. All other agents inside L0 preserve their ordering as it existed before applying the macro at hand. At the end of the current bubble ride, after applying the last macro, the conﬁguration of int(L) is q2, . . . , qz, u. Agent q1 is inside L0. All other agents in L0 preserve their relative ordering that existed before starting the bubble ride. In the running example, the resulting conﬁguration of int(L) is 2, 3, 4, u (Figure 5, bottom left).

Minnie s trip (Figure 5, bottom left): Rotate agents in the

basic cycle L0 until v is placed right after the exit from L, and the exit is empty.

Reuniﬁcation (Figure 5, bottom right): Advance agents inside L one step further, placing u next to v, inside L0, and leaving a blank at the ﬁrst interior position of L.

Clean up: Rotate agents inside L0 until q1 is at the entrance of L, and then push q1 inside L.

After applying method Bring Agents Next To Each Other, L has preserved its goal conﬁguration. Agents u and v are next to each other in the desired order. Apart from repositioning u, no other ordering relationships were affected inside L0. The process is repeated until the basic cycle L0 is solved, which completes solving the entire instance. The solving strategy outlined in the previous paragraphs allows us to formulate the following result.

Proposition 4. On a strongly biconnected digraph with a regular open ear decomposition, all multi-agent path ﬁnding instances with two or more blanks have a solution.

In summary, a strongly biconnected digraph either is a partially bidirectional cycle, or it admits a regular open ear decomposition. On partially bidirectional cycles, all instances with at least one blank can be solved or proven unsolvable. On digraphs with a regular open ear decomposition, all instances with at least two blanks have a solution.

Algorithm Analysis We put together all pieces described in the previous section, obtaining an algorithm that we call di BOX. We show its pseudo-code in Algorithm 1 and analyze its complexity. Rotate is a one-step rotation of all the agents contained within a cycle C with at least one blank. It consumes |C| steps and produces |C| moves. Given a cycle C, a goal conﬁguration α+ and an agent u, the agent that should be next to u, in the positive orientation of C, is provided in constant time by the function Next Agent. As the conﬁguration in the basic cycle may be shifted with respect to the required goal conﬁguration after putting agents into the right order, several ﬁnal rotations of the basic cycle may be necessary. This ﬁnal correction is done with method Shift Agents In Cycle. The operation consumes a time of O(|C|2), where C is the cycle at hand, and produces the same number of moves. Indeed, O (|C|) rotations may be necessary, while one rotation needs |C| steps and moves. If the goal conﬁguration does not have two blanks in the basic cycle, the instance is transformed with procedure Borrow Blanks. At the end, the original goal conﬁguration is restored with procedure Return Blanks. These two methods can run in a time of O (|E|), producing O (|V |) moves.

Proposition 5. The worst-case time complexity of di BOX is within O(|V |3) and so is the number of moves.

Proof. Checking if D = (V, E) is a partially bidirectional cycle can be done in O (|V |) time steps. The key observation is that, in a partially bidirectional cycle, nodes have at most two outgoing edges each, one going forward and the other (if present) going backwards , to the previous node. This property allows to reduce the search for a Hamiltonian path

Algorithm 1 di BOX in pseudocode. input: a digraph D = (V, E) a set of agents A an initial conﬁguration α0 of agents over D a goal conﬁguration α+ of agents over D output: sequence of moves transforming α0 into α+ di BOX (D, A, α0, α+) 1: if D is a partially bidirectional cycle then 2: if α0 and α+ represent the same ordering in D then 3: Shift Agents In Cycle (D, α+) 4: else 5: return UNSOLVABLE 6: else 7: let [L0, L1, . . . , Lr] be a regular open ear decomp. with non-trivial ear L1 attached to L0 10: if |{x L0|α 1 + (x) = blank}| < 2 then 11: α + Borrow Blanks D, L0, α+

12: Solve Ears (D, [L0, L1, . . . , Lr] , α0, α +) 13: Return Blanks D, α+, α +

14: else 15: Solve Ears (D, [L0, L1, . . . , Lr] , α0, α+)

Solve Ears (D, [L0, L1, . . . , Lr] , α0, α+) 16: α α0 17: for i = r downto 1 do 18: Solve Derived Ear (D, Li, α+) 19: Solve Basic Cycle (L0, L1, α+)

Solve Derived Ear (D, Li, α+) 20: let Li = [x0, x1, x2, . . . , xz+1] 21: let C be a cycle containing Li in D \ S j>i int(Lj) 22: for l = z downto 1 do 23: ql α 1 + (xl) 24: if α 1(x0) = ql then 25: if ql {α 1 (xz) , . . . , α 1(xz l+1)} then 26: Take Agent Outside Ear (ql, Li, C ) 27: Move Agent In Subgraph (ql, x0, Si 1 j=1 Lj) 28: Rotate (C )

Solve Basic Cycle (L0, L1, α+) 29: let L0 = [x1, x2, . . . , xz] 30: let L1 be connected to L0 in xa and xb 31: for l = 1 to z 1 do 32: u α 1(xl) 33: if u = blank then 34: v Next Agent (xl, L0, α+) 35: Bring Agents Next To Each Other (L0, L1, u, v) 36: Shift Agents In Cycle (L0, α+)

to at most two deterministic walks, avoiding any branching and backtracking. Details are skipped to save room. A regular open ear decomposition [L0, L1, . . . , Lr] of required properties can be found in the worst-case time of O (|V | + |E|) (Schmidt 2013). Note that trivial derived ears

are skipped by the algorithm. Ignoring these does not affect the completeness of di BOX. The number of remaining edges is within O (|V |), since, in every non-trivial ear, the numbers of edges and interior vertices differ by 1. This observation enables ﬁnding a path or a cycle connecting two given vertices in O (|V |) steps with breadth ﬁrst search. Processing a single agent when solving a derived ear Li involves at most |C | rotations of the cycle C associated with Li, as well as at most two relocations of ql within a sub-graph. As a single rotation requires O (|C |) steps and produces the same number of moves, a single agent consumes O(|C |2) moves in rotations. The agent relocations add O(|V |2) moves and time (Wu and Grumbach 2010). Altogether, processing all the agents in derived ears requires a time of O(|V |3) and produces O(|V |3) moves. It remains to analyze the solving the basic cycle L0. Bringing agents next to each other requires O (|L0|) rotations of L0, to bring the ﬁrst agent to the entrance of the nontrivial ear L1; then the second agent needs to be brought to the exit of the ear; and ﬁnally an agent that got out of the ear into L0 needs to be put back. Rotations within L0 consume a time of O(|L0|2) and produce the same number of moves. For all the agents in L0, both the time and the number of moves are within O(|L0|3), which boils down to O(|V |3). A single bubble ride macro-step requires |L1| rotations of a cycle of a size bounded by |L0| + |L1|. This includes rotations necessary to make a movement of an agent inside and outside L1. Counting all the agents for which the bubble ride is done, we obtain both a time and a number of moves of |L0| |L1| (|L0| + |L1|), which boils down to O(|V |3). The time and the number of moves for remaining operations such as borrowing and returning blanks is dominated by O(|V |3). Altogether, both the worst-case time complexity and the number of moves are within O(|V |3).

Conclusion We have performed a formal study of multi-agent path ﬁnding on strongly biconnected digraphs. We found that instances with at least two blanks have a solution, except for the trivial case of badly ordered instances on partially biconnected cycles. We have presented a sub-optimal algorithm, called di BOX, whose worst-case time complexity and solution length are both within O(|V |3), where V is the set of vertices. Similarly to BIBOX (Surynek 2009), a method for undirected biconnected graphs, our algorithm solves ears in reverse order. However, the restriction to uni-directional movements makes our algorithm more involved than the case when bi-directional movement is possible. In future work, we plan to extend our analysis to other classes of digraphs, or to instances where rotations in a cycle do not require using a blank. We are also interested in implementing and evaluating the performance of our method.

Acknowledgement Pavel Surynek is partially supported by the Czech Science Foundation (contract # 15-15873Y/P103). We thank Davide Bonusi for pointing out a case not covered in an earlier version. We thank the anonymous reviewers for their feedback.

References Bang-Jensen, J., and Gutin, G. Z. 2008. Digraphs: Theory, Algorithms and Applications. Springer Publishing Company, Incorporated, 2nd edition. Bauer, R., and Delling, D. 2008. SHARC: fast and robust unidirectional routing. In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments, ALENEX 2008, San Francisco, California, USA, January 19, 2008, 13 26. de Wilde, B.; ter Mors, A. W.; and Witteveen, C. 2013. Push and rotate: Cooperative multi-agent path planning. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems (AAMAS-13), 87 94. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. Jetcheva, J. G., and Johnson, D. B. 2006. Routing characteristics of ad hoc networks with unidirectional links. Ad Hoc Networks 4(3):303 325. Kornhauser, D.; Miller, G.; and Spirakis, P. 1984. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science (FOCS), 241 250. Luna, R., and Bekris, K. E. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In Proceedings of the International Joint Conference on Artiﬁcial Intellgience (IJCAI-11), 294 300. Marina, M. K., and Das, S. R. 2002. Routing performance in the presence of unidirectional links in multihop wireless networks. In Proceedings of ACM Mobi Hoc, 12 23. Papadimitriou, C. H.; Raghavan, P.; Sudan, M.; and Tamaki, H. 1994. Motion planning on a graph. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (SFCS-94), 511 520. Washington, DC, USA: IEEE Computer Society. Ratner, D., and Warmuth, M. 1986. Finding a shortest solution for the N N extension of the 15-puzzle is intractable. In Proceedings of AAAI National Conference on Artiﬁcial Intelligence (AAAI-86), 168 172. Schmidt, J. M. 2013. A simple test on 2-vertex and 2-edgeconnectivity. Information Processing Letters 113(7):241 244. Sharon, G.; Stern, R.; Goldenberg, M.; and Felner, A. 2013. The increasing cost tree search for optimal multiagent pathﬁnding. Artiﬁcial Intelligence 195:470 495. Silver, D. 2006. Cooperative pathﬁnding. AI Programming Wisdom. Standley, T. S. 2010. Finding optimal solutions to cooperative pathﬁnding problems. In Proceedings of the National Conference on Artiﬁcial Intelligence (AAAI-10), 28 29. Surynek, P. 2009. A novel approach to path planning for multiple robots in bi-connected graphs. In IEEE International Conference on Robotics and Automation (ICRA 2009), 3613 3619. Surynek, P. 2010. An optimization variant of multi-robot path planning is intractable. In Fox, M., and Poole, D., eds.,

Proceedings of the National Conference on Artiﬁcial Intelligenc (AAAI-10). AAAI Press. Surynek, P. 2014. Solving abstract cooperative path-ﬁnding in densely populated environments. Computational Intelligence 30(2):402 450. Wang, K.-H. C., and Botea, A. 2008. Fast and Memory Efﬁcient Multi-Agent Pathﬁnding. In Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-08), 380 387. Wang, K.-H. C., and Botea, A. 2011. MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. Journal of Artiﬁcial Intelligence Research JAIR 42:55 90. Wilson, R. M. 1974. Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, Series B 16(1):86 96. Wu, Z., and Grumbach, S. 2010. Feasibility of motion planning on acyclic and strongly connected directed graphs. Discrete Applied Mathematics 158(9):1017 1028.