Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding

1 Introduction

In systems using physical moving agents, it is essential to allow agents to reach their own destinations smoothly without collisions, by providing valid paths while minimizing excess travel time. This problem, known as Multi-agent Path Finding (MAPF), is however computationally difficult due to the search space growing exponentially as the number of agents increases. MAPF is an important problem due to its applications in various domains, e.g., traffic control [Dresner and Stone, 2008], automated warehouse [Wurman et al., 2008], or airport surface operation [Morris et al., 2016], etc.

Previous research on MAPF focuses on solving a "oneshot" version of the problem, i.e., to make agents reach their goal from their initial position only once. In practical applications, such as conveying packages in a warehouse [Ma et al., 2017], MAPF must however be solved iteratively.

That is, whenever an agent reaches a goal, it receives a new one. This rules out any simple adaptation of offline and computationally-intensive optimal solutions due to prohibitive computations, and new goals typically appearing at runtime. Furthermore, centralized solutions being inherently problematic for systems with many agents due to scalability concerns, decoupled algorithms such as prioritized route planning are adequate, especially if fully decentralized. Decentralized solutions are highly attractive to multi-agent/robot systems for many reasons, including a higher potential for robustness and fault-tolerance, better scalability, and lower production cost [Yan et al., 2013]. Finally, implementations without global communication are preferable since they provide better potential for scalability and concurrency.

In this paper, we present a novel algorithm for iterative Multi-agent Path Finding (iterative MAPF), called Priority Inheritance with Backtracking (PIBT), which focuses on the adjacent movements of multiple agents based on prioritized planning in a short time window. Priority inheritance is a well-known approach to deal effectively with priority inversion in real-time systems [Sha et al., 1990], and is applied here to path adjustment. When a low-priority agent X impedes the movement of a higher-priority agent Y, agent X temporarily inherits the higher-priority of Y. To avoid a situation where agents are stuck waiting, priority inheritance is executed in combination with a backtracking protocol. Since PIBT assumes that agents can only communicate when located within two hops of each other (e.g., Manhattan distance 2 in a grid environment), it can be implemented in a fully decentralized way and inherits the above characteristics.

Our main contributions are two-folds: 1) we propose an algorithm ensuring that every agent always reaches its destination within finite time as long as the environment satisfies the condition that all pairs of adjacent nodes belong to a simple cycle of length 3 or more (includes undirected biconnected graphs); and 2) we evaluate that algorithm in various environments, showing its practicality. In particular, experimental results over various scenarios confirm its adequateness both for finding paths in large environments with many agents, as well as for conveying packages in an automated warehouse.

The paper is organized as follows. Section 2 reviews existing algorithms for MAPF and a variant called Multi-agent Pickup and Delivery (MAPD). Section 3 defines iterative MAPF, which provides an abstract framework for multiple moving agents. Section 4 presents the PIBT algorithm and its theoretical analysis. Section 5 presents empirical results on both path finding (MAPF) and pickup and delivery (MAPD). Section 6 concludes the paper and discusses future work.

2 RelatedWork

Many complete MAPF algorithms exist, such as A∗ with Operator Decomposition [Standley, 2010], Enhanced Partial Expansion A∗ [Goldenberg et al., 2014], Increasing Cost Tree Search [Sharon et al., 2013], Conflict-based Search [Sharon et al., 2015], M∗ [Wagner and Choset, 2015], etc.

Finding an optimal solution is however NP-hard [Yu and LaValle, 2013], and optimal algorithms do not scale in the number of agents and are too costly for iterative use, hence the need for sub-optimal solvers, e.g., FAR [Wang et al., 2008], MAPP [Wang and Botea, 2011], Tree-based Agent Swapping Strategy [Khorshid et al., 2011], BIBOX [Surynek, 2009], CBS variants [Barer et al., 2014; Cohen et al., 2016].

Push and Swap/Rotate [Luna and Bekris, 2011; de Wilde et al., 2013], which partly inspired our proposal, are suboptimal centralized approaches that allow one agent to push another away from its path. However, they only allow a single agent or a pair of agents to move at each timestep. Enhanced Push and Swap include Parallel Push and Swap [Sajid et al., 2012] where all agents can move simultaneously, or Push-Swap-Wait [Wiktor et al., 2014] which takes a decentralized approach in narrow passages. DisCoF [Zhang et al., 2016] combines decoupled prioritized planning with fallback to coupled push and swap in case of conflicts. PIBT, the proposed method, can be seen as a combination of safe "push" operations, thanks to backtracking and dynamic priorities.

Prioritized planning is computationally cheap and hence attractive for MAPF. Hierarchical Cooperative A∗ (HCA∗ ) and Windowed HCA∗ (WHCA∗ ) [Silver, 2005] are decoupled approaches in that they plan a path for each agent one after the other while avoiding collisions with previously computed paths. WHCA∗ uses a limited lookahead window. Our proposal, PIBT, is based on WHCA∗ with a window size of one. Decentralized solutions, i.e., where each agent computes its own path based on information from other agents, are inherently decoupled. Decentralized solutions for MAPF [Velagapudi et al., 2010; ˇC´ap et al., 2015; Chouhan and Niyogi, 2015] are hence usually prioritized. The negotiation process for ordering priorities studied by Azarm et al. [Azarm and Schmidt, 1997] solves conflicts by having involved robots try all priority orderings, and deals with congestion by limiting negotiation to at most 3 robots and letting others wait. A recent theoretical analysis of prioritized planning [Ma et al., 2018] identifies instances that fail for any order of static priorities. That study, which also presents a centralized approach called Priority-Based Search, actually provides a very strong case for planning based on dynamic priorities, such as the approach taken with PIBT.

The problem of Multi-agent Pickup and Delivery (MAPD) [Ma et al., 2017] abstracts real scenarios such as an automated warehouse, and consists of both allocation and route planning. Agents are assigned to a task from a stream of delivery tasks and must consecutively visit both a pickup and a delivery location. The paper proposes two decoupled algorithms based on HCA∗ for MAPD, called respectively Token Passing (TP) and Token Passing with Task Swap. These algorithms can easily be adapted to be decentralized but require a certain amount of non-task endpoints where agents do not block other agents' motion.

3 ProblemDefinition

The problem of iterative Multi-agent Path Finding (iterative MAPF) is a generalization of problems addressing multiple moving agents, including both Multi-agent Path Finding (MAPF) and Multi-agent Pickup and Delivery (MAPD). Since iterative MAPF is an abstract model we do not intend to solve it directly, rather, it is necessary to embody task creation according to target domains.

The system consists of a set of agents, A = {a1, . . . , an}, and an environment given as a graph G = (V,E), where agents occupy nodes in V and move along edges in E. Considering practical situations, G must be a simple (neither loops nor multi-edges) and strongly-connected (every node is reachable from every other node) directed graph. This includes all simple undirected graphs that are connected.

Let vi(t) denote the node occupied by agent ai at discrete time t. The initial position of agent ai is vi(0) and given as input. At each timestep, ai selects one node vi(t + 1) ∈ {v|v ∈ V, (vi(t), v) ∈ E} ∪ {vi(t)} as its location for the next timestep. Agents must avoid 1) collision: vi(t) ̸= vj(t); and 2) intersection with others: vi(t) ̸= vj(t + 1) ∨ vj(t + 1) ̸= vj(t). We do not prohibit rotations, so vi(t + 1) = vj(t)∧vj(t+1) = vk(t)∧· · ·∧vl(t+1) = vi(t) is possible.

Let Γ = {τ1, τ2, . . . } be a dynamic set of tasks with new tasks being added over time, i.e., not all tasks are known initially. A task is defined as a finite set of goals τj = {g1, g2, . . . , gm} where gk ∈ V , possibly with dependencies as a partial order on gk. Let tj be the timestep when τj is added to Γ. An agent is free when it has no assigned task. A task τj ∈ Γ can only be assigned to free agents. When τj is assigned to ai, ai starts visiting goals in τj. When all goals have been visited, τj is completed and ai becomes free.

Let now π(ai, τj) = (vi(t), vi(t + 1), . . . ) be the path of ai when τj is assigned at timestep t until ai completes τj. When ai is free, it is assigned a dummy task ¯ τl with path π(ai, ¯ τl), where index l is for the uniqueness of π. The path must ensure no collision and no intersection, with the following additional condition; gk ∈ π(ai, τj), ∀gk ∈ τj. The service time λ(π(ai, τj), tj) is defined as the time elapsed from start (tj) to the completion of τj by ai. Note that λ(π(ai, τj), tj) does not usually equal to |π(ai, τj)| because τj is not always assigned immediately.

We say that iterative MAPF has a solution if and only if the service times of all tasks are finite. Iterative MAPF is a generic problem which, depending on its concrete instance, can rely on an objective function of the following general form.

where Γi is the set of tasks allocated to ai. Concrete instances of iterative MAPF include route planning and task allocation, for which objective functions are described in Section 5.

Depending on context, Γi is determined a priori. For instance, in the literature on MAPF, Γi is provided as {τi = {gi}} where gi is a goal node of ai. A start node is defined by vi(0). In the basic definition of MAPF, termination is achieved once all agents are at their goal in the same timestep. To satisfy this requirement, when ai that once reached gi leaves it, a new task τ = {gi} is added to Γi.

MAPD is an instance of iterative MAPF, where every task is a tuple of two nodes (pickup and delivery) instead of a set.

4 Priority Inheritance with Backtracking

This section introduces the concept of Priority Inheritance with Backtracking (PIBT), describes the algorithm and its properties, as well as how to apply PIBT to specific problems such as MAPF and MAPD. To avoid unnecessarily complex explanations, we introduce PIBT as a centralized algorithm and focus on the analysis of the prioritization scheme itself. PIBT relies on a decoupled approach making it easily amenable to decentralization. We briefly discuss later how to adapt it to a decentralized case.

4.1 Basic Concept

Prioritized approaches are effective for iterative use, so PIBT essentially implements WHCA∗ [Silver, 2005] with a time window of one. At every timestep, each agent updates its own unique priority. Paths are computed one by one while avoiding collisions with previously computed paths.

Priority Inheritance

Priorities alone can still result in a deadlock (see Fig. 1a) resulting from a case of priority inversion. Priority inversion occurs when a low-priority agent (a0) fails to obtain a resource held by a medium-priority agent (a1), even though it holds a second resource claimed by a higher-priority agent (a2). This is typically addressed by priority inheritance [Sha et al., 1990] (Fig. 1b). The rationale is that, a low-priority agent (a0) temporarily inherits the higher priority of agents (a2) claiming resources it holds, thus forcing medium-priority agents (a1) out of the way (Fig. 1c).

Backtracking

Priority inheritance deals effectively with priority inversion, but it does not completely ensure deadlock-freedom. For instance, as shown in Fig. 2a, agent a2 finds no escape as a result of consecutive priority inheritance (a6→a5→a4→a3).

The solution relies on backtracking: i.e., any agent a that gives its priority must wait for an outcome (valid or invalid). If valid, a successfully moves to the desired node. Otherwise, it must change its target, excluding 1) nodes requested from higher priority agents, and 2) nodes denied from inherited agents. Upon finding no valid or unoccupied nodes, a sends back an invalid outcome to the agent from which it inherited its priority. In Fig. 2b, a2 first sends invalid back to a3, which in turn sends invalid to a4. Since a0 has lower priority, a4 can let a0 inherit its priority as an alternative, which leads to a valid outcome (Fig. 2c), and agents can move (Fig. 2d).

4.2 Algorithm

We begin by defining the notion of groups of interacting agents, since the algorithm and its proofs rely on it. When two agents located within two hops of each other move, they might collide in the next step, and they are said to be directly interacting in that step. For an agent ai, a group of interacting agents Ai(t) ⊆ A is then defined by transitivity over direct interactions in a timestep t. Note that, given ai and Ai(t), then for any other agent aj ∈ Ai(t) we have Ai(t) = Aj(t). Whenever obvious from context, we use A(t) or A.

Since agents belonging to different groups cannot affect each other, path planning can effectively occur in parallel. As a result, PIBT is decentralized and only relies on local communication, i.e., it is sufficient that two agents in close proximity can talk directly and utilize multi-hop communication.

Algorithm 1 PIBT (code at timestep t)

1: UNDECIDED←A(t) ▷ agents list 2: OCCUPIED← ∅ ▷ nodes list 3: update all priorities pi(t) 4: while UNDECIDED ̸= ∅ do 5: let a be the agent with highest priority in UNDECIDED 6: PIBT(a,⊥) 7: end while 8: 9: function PIBT(ai, aj) 10: UNDECIDED←UNDECIDED \ {ai} 11: Ci ← ({v | (v, vi(t)) ∈ E} ∪ {vi(t)}) \({vj (t)} ∪ OCCUPIED) 12: while Ci ̸= ∅ do 13: v∗ i ← arg max v∈Ci fi(v) 14: OCCUPIED ← OCCUPIED ∪ {v∗ i } 15: if ∃ak ∈ UNDECIDED such that v∗ i = vk(t) then 16: if PIBT(ak, ai) is valid then 17: vi(t + 1) ← v∗ i 18: return valid 19: else 20: Ci ← Ci \ OCCUPIED 21: end if 22: else 23: vi(t + 1) ← v∗ i 24: return valid 25: end if 26: end while 27: vi(t + 1) ← vi(t) 28: return invalid 29: end function

Algorithm 1 describes PIBT, where pi(t) ∈ R is the priority of agent ai at timestep t. fi(v), v ∈ V is the valuation function of nodes for ai at the current timestep, where a larger value of fi(v) means that ai has a higher preference to move to node v at the next timestep. PIBT can be described recursively, especially with respect to priority inheritance and backtracking. We assume that the groups of interacting agents A(t) are fully identified prior to starting the algorithm. UNDECIDED is the set of agents that have not manifested an intention (initially A(t)). At each timestep, agents update their priorities in the way mentioned later [Line 3]. Subsequently, select the agent with highest priority in UNDECIDED and call function PIBT [Lines 5,6]. This loops until all agents in A determines their nodes for next timestep.

The function PIBT takes two arguments: the agent ai making a decision and an agent aj from which ai inherits its priority, or ⊥ if there is none. ai must select a node for vi(t+1) from the set of candidates nodes Ci. Here, Ci consists of vi(t) and its neighbors while excluding 1) nodes requested from higher priority agents, 2) nodes denied from inherited agents, and 3) vj(t) for avoiding intersection [Line 11].

If Ci is empty [Line 12], this means that ai is stuck like a2 in Fig. 2b. In that case, ai selects vi(t) as vi(t + 1) and returns invalid as outcome [Lines 27,28]. Otherwise (Ci nonempty), ai selects the most valuable node v∗ i [Line 13]. If v∗ i is occupied by an agent ak in UNDECIDED [Line 15], ai applies priority inheritance and waits for the result of backtracking [Line 16], otherwise, v∗ i is set to vi(t+1) and returns valid [Lines 23,24]. Upon a valid outcome, ai can move to v∗ i [Line 17]. Otherwise, ai updates Ci to exclude prohibited nodes [Line 20] and repeats the process [Lines 12-26].

We now prove that the agent with highest priority can always move. The intuition is that it can always move along a simple cycle.

Lemma 1. Let a1 denote the agent with highest priority at timestep t and v∗ 1 an arbitrary neighbor node of v1(t). If there exists a simple cycle C = (v1(t), v∗ 1 , . . . ) and |C| ≥ 3, Algorithm 1 makes a1 move to v∗ 1 in the next timestep.

Proof. After deciding v∗ 1 , it is added to OCCUPIED [Line 13,14]. From the definition of Ci, ∀i ̸= 1 [Line 11], no other agent can select v∗ 1 .

Consider first the case when v∗ 1 is unoccupied. No other agent can enter v∗ 1 and a1 is guaranteed to move to v∗ 1 .

Consider now that v∗ 1 is occupied by some agent a2. a2 inherits a1's priority which is highest. The existence of cycle C ensures that C2 is not initially empty (|C| ≥ 3, C contains v1(t) and v2(t)). From the definition of C2, collision and intersection with a1 are implicitly prevented. If a2 selects v∗ 2 ∈ C2 such that v∗ 2 is unoccupied by another agent, then a2 is guaranteed to move to v∗ 2 according to the same logic as for a1. Consequently, a1 successfully moves to v∗ 1 . This forms the basis and the remaining now proves the induction step.

Following this, suppose that ai grants its priority to aj (ai, aj ∈ A1(t), 2 ≤ i < j). From the definition of Cj, collision and intersection with other agents are implicitly prevented. If aj selects an unoccupied node v∗ j ∈ Cj, aj can move to v∗ j and a series of agents that will receive the result of backtracking as valid, including ai and a2, can move to its current target node based on the same argument.

Now, by contradiction, suppose that a2 fails to move to any node, i.e. a2 receives invalid as the result of backtracking and C2 becomes empty. Let DECIDED denote A1(t) \ {UNDECIDED ∪ {a1}}. The assumption says all agents in DECIDED failed to move. Since ai ∈ DECIDED (∀i ≥ 2) tried to move other nodes until Ci became empty, neighbor nodes of v2(t) exclusive of v1(t) are in OCCUPIED, and all nodes adjacent to vj(t) (∀j ≥ 3) are in OCCUPIED. Incidentally, the existence of C indicates at least one agent a∗ ̸= a2 on C had initially at least one free neighbor node including v1(t). At the beginning of the original priority inheritance from a1, even though all nodes in C is occupied of someone, the agent on the last node of C has a free neighbor node, i.e., v1(t), otherwise, it is obviously there exists a∗ . Considering the mechanism of priority inheritance, DECIDED must contain all agents on C exclusive of a1 because C contains v2(t). This is contradiction; a∗ should be in DECIDED but a∗ initially had an free neighbor node. Therefore, a2 can finally move to a node not v1(t) or v2(t) (equals to v∗ 1 ). Thus, a1 can move to v∗ 1 .

Prioritization

Let τi denote the task currently assigned to ai, and gi the current goal in τi. Let ηi(t) ∈ N be the number of timesteps elapsed since ai last updated gi and until time t. Note that ηi(0) = 0 or when ai is free. Let ϵi ∈ [0, 1) be a value unique to each agent ai. At every timestep, pi(t) ∈ R is computed as follows; pi(t) ← ηi(t) + ϵi. Obviously, pi(t) is unique among agents at every timestep.

This prioritization leads to the following theorem.

Theorem 2. If G has a simple cycle C for all pairs of adjacent nodes and |C| ≥ 3 then, with PIBT, all agents reach their own destination within diam(G) · |A| timesteps after being given.

Proof. From Lemma 1, the agent with highest priority reaches its own goal within diam(G) timesteps. Based on the definition of ηi(t), once some agent ai has reached its goal, pi(t) is reset and is lower than that of all other agents that have not reached their goal yet. Those agents see their priority increase by one. As long as such agents remain, exactly one of them must have highest priority. In turn, that agent reaches its own goal after at most diam(G) timesteps. This repeats until all agents have reached their goal at least once, which takes at most diam(G) · |A| timesteps in total.

A typical example that satisfies the above condition is any biconnected undirected graph. The opposite is not true however, and Theorem 2 is expressed more generally to account for directed graphs. For instance, a directed ring satisfies the condition even though it is not biconnected. Note that we neither ensure nor require that all agents be on their goal simultaneously.

Complexity Analysis

Now we consider the computational complexity of PIBT. To simplify, assume that PIBT performs in a centralized way. Let ∆(G) denote the maximum degree of G, and F be the maximum time required to compute the most valuable node for the next timestep [Line 13]. F depends on both G and the node evaluation function fi.

Proposition 3. The computational complexity of PIBT in one timestep is O(|A| · ∆(G) · F).

Proof. For an agent ai, the function PIBT(ai, ·) is called once in one timestep because PIBT(ai, ·) is called if and only if ai ∈ UNDECIDED [Line 5 and Line 15,16], and ai is removed from UNDECIDED after calling [Line 10]. The main loop in Line 12 is repeated at most ∆(G) + 1 times. If priority inheritance occurs and succeeds [Line 16], the loop is broken [Line 18], otherwise |Ci| decreases [Lines 14 and 20]. If the absence of priority inheritance, the loop is also broken [Line 24]. At each iteration of the loop, the node selection [Line 13] occurs and is itself of complexity F. Thus, we derive the complexity of PIBT as O(|A| · ∆(G) · F).

Communication

Since PIBT is based on priorities and assumes only local interactions, it is easily adapted to a decentralized context. The part of priority inheritance and backtracking is done by propagation of information. In a decentralized context, PIBT requires agents to know others' priorities before they decide their next nodes. Usually, this requires |A|2 communication between agents, however, updating rule of pi relaxes this effort, e.g., stores other agents priories and communicates only when ηi becomes zero. Therefore, the communication cost of PIBT mainly depends on the information propagation phase.

Let us now consider this phase. In Algorithm 1, communication between agents corresponds to calling function PIBT [Line 6,16] and backtracking [Line 18,24,28]. PIBT(ai, ·) is never called twice in each timestep, as discussed in the previous section. Moreover, each agent sends a backtracking message at most once in each timestep. Overall, the communication cost for PIBT at each timestep is linear w.r.t. the number of agents, that is, O(|A|). In reality, this can be even less because the figures depend on the number of interacting agents |A| which can be much smaller than |A|.

4.3 Applying to Specific Problems

The valuation function of nodes, fi(v), must be defined based on the concrete problem. In the two scenarios introduced later, we use -cost(v, gi) as fi, where cost(u, u′ ) is the length of the shortest path from u to u′ , and gi is the current destination if ai has a task. 1 To avoid unnecessary priority inheritance, the presence (or not) of an agent is used as a tiebreaking rule. If ai is free, make vi(t) to be the highest and use the same tie-breaking rule.

Multi-agent Path Finding (MAPF)

In any graph G, PIBT with above fi does not ensure that all agents are located on their goals simultaneously, which MAPF requires. We confirmed a certain kind of livelock situations in our experiment. It might be possible to ensure completeness for some classes of graphs through a more complex fi, e.g., akin to "swap" operation [Luna and Bekris, 2011], but we do not address this issue here. Note that PIBT is aimed at iterative use rather than one-shot use.

Multi-agent Pickup and Delivery (MAPD)

The MAPD problem is a typical example of iterative MAPF. Since PIBT only provides coordinated movements of agents, we need to complement the method of task allocation.

Different from the proposed algorithms by Ma et al. [Ma et al., 2017], deadlocks never occur with PIBT even without non-task endpoints, as long as G follows the condition stated in Theorem 2. Moreover, PIBT does not require wellformed instances which guarantees that for any two endpoints including pickup and delivery locations, a path exists between them that traverses no other endpoints. Practically, MAPD is performed in orderly environments, i.e., the assumption we stated of a graph is adequate. Therefore, there is no need to care about the behavior of free agents.

From the above reasons, we propose a simple allocation process; at every timestep, each free agent moves to the nearest pickup location of the non-assigned task, ignoring the behavior of other agents, and is assigned to a task if and only if it reaches the pickup location and the task remains. The following theorem directly follows from Theorem 2.

1 Experiments on MAPF rely on A∗ to obtain the shortest paths. Those on MAPD used the Floyd-Warshal algorithm, to build the allpairs distance matrix, during a preprocessing phase. The comparison (TP) also utilized the matrix.

Theorem 4. If G has a simple cycle C for all pairs of adjacent nodes and |C| ≥ 3, then PIBT with the above-mentioned allocation process solves MAPD.

5 Evaluation

This section assesses the effectiveness of PIBT quantitatively, through computer simulation. The simulator was developed in C++, 2 and all experiments were run on a laptop with Intel Core i7 2.2GHz CPU and 8GB RAM. The experiments address both the MAPF and MAPD problems.

5.1 Multi-agent Path Finding (MAPF)

We carefully chose four undirected graphs, shown in Table 1, as testbeds for MAPF. Three of them (lak105d, arena, ost003d) come from the game Dragon Age: Origins [Sturtevant, 2012] and are commonly used to evaluate multi-agent algorithms. For comparison with PIBT, we also experimented using two sub-optimal MAPF solvers, namely WHCA∗ [Silver, 2005] and Parallel Push and Swap (PPS) [Sajid et al., 2012]. The window size of WHCA∗ was set to 5 on the simple map, and to 10 otherwise. All solvers were executed on the same set of 100 settings with random initial positions and goal locations for each configuration while changing the number of agents. An execution was considered failed if the solver yielded a failure or failed to provide a result after a timeout of 5 minutes. The evaluation metrics are the following four, referring to other MAPF studies: 1) path cost, i.e., the timestep when each agent reaches its given goals and never move from then; 2) makespan, i.e., the timestep when all agents reach their given goals; 3) runtime; and 4) success rate over 100 instances. Note that the sum of service time for one agent defined in Section 3 is different from path cost, e.g., assume that an agent reaches its goal and apart there. The service time does not augment when the agent is on the goal since the task is not issued, whereas the path cost does count that time. Stated in section 3, the typical objective function of iterative MAPF is service time and path cost is the specific metric of the one-shot version. However, following the literature on one-shot MAPF, we address here path cost and makespan, which is also indirect criteria of service time.

2 The code is available at https://kei18.github.io/pibt/

The results, shown in Table 1, indicate, for each solver, both an average over the instances successful with that solver (no decoration), and an average over only the instances that were successfully solved by all three solvers (in parentheses). In summary, PIBT compares well with other methods; Path efficiency is reasonable with a high success rate in most cases, moreover, PIBT is comparable with PPS in terms of runtime cost. In general, PIBT appears to have an advantage in huge fields with many agents since it relies only on local communication, and here, the experimental results support the strength of our proposal (see ost003d in Table 1). Conversely, PIBT suffers from a somewhat low success rate in dense situations (see the simple map). PIBT fails on MAPF either because the graph property mentioned before is not met or due to livelock situations.

Experimental results in arena show drastic improvements in both runtime and makespan for PPS and WHCA∗ when compared to the original paper of PPS [Sajid et al., 2012].

The improvement in runtime is easily explained by heavy optimization of our implementation and, in particular, of the underlying A∗ algorithm and its use (aggressive caching, elimination of redundant computations across agents, ...).

The improvement in makespan is difficult to isolate but is likely to come as a side-effect of the aggressive caching mentioned above. The rationale is that, when many agents need to move in the same direction, the caching helps create one-way flows of agents and hence reduce interactions and contention between groups of agents moving in opposite directions. In contrast, since A∗ is a stochastic algorithm, this could result in increased contention. This is interesting but largely beyond the scope of this paper.

All three solvers determine paths one at a time, but PPS and PIBT differ from WHCA∗ in that the former two have a look ahead of a single step, whereas the WHCA∗ computes paths multi-steps ahead. Due to this, WHCA∗ is naturally expected to compute better paths than PIBT and PPS. We however observe that PIBT sometimes results in a better makespan than WHCA∗ , which can be explained by the fairness provided by dynamic prioritization (i.e., more uniformity in path lengths among agents). In PIBT, once an agent a reaches its goal, its priority drops below other agents that have yet to reach their goal, letting them push a away rather than taking a detour. This likely contributes to reducing makespan over WHCA∗ , in which agents hold their priority. Further, the "Swap" operation in Push and Swap [Luna and Bekris, 2011] solvers, while effective in narrow passages, produces unnecessary steps in open spaces such as arena.

5.2 Multi-agent Pickup and Delivery (MAPD)

Following the experimental setup of the original study [Ma et al., 2017], we used the same undirected graph as testbed, as shown in Table 2. We generated a sequence of 500 tasks by randomly choosing their pickup and delivery locations from all task endpoints. We used 6 different task frequencies, which numbers of tasks are added to the task set Γ: 0.2 (one task every 5 timestep), 0.5, 1, 2, 5 and 10 where the number of agents increases from 10 to 50. TP algorithm [Ma et al., 2017] was also tested for comparison. All experimental settings were performed in 100 instances which initial positions of agents were set randomly. We evaluated following three: 1) makespan which is the timestep when all tasks are completed; 2) service times, i.e., terms from issue to completion of tasks; and 3) runtime.

The results are shown in Table 2. Clearly, PIBT significantly outperforms TP in the view from all three metrics. PIBT is efficient because 1) it ignores the positions of free agents; 2) the computational cost of planning a path is cheap.

6 Conclusion

This paper introduces PIBT, an algorithm for iterative MAPF. PIBT focuses on the adjacent movements of multiple agents, and hence can be applied to many domains. Intuitively, PIBT is well-suited to large environments because such environments result in intensive communication and path efficiency improves with a lower density of agents. Empirical results support this aspect, moreover, PIBT outperforms current solutions to pickup and delivery (MAPD).

Future research include the following: 1) relaxing conditions on the graph environment; 2) finding the effective valuation function of nodes for each domain; 3) adapting the model to asynchronous communication and movements; 4) expanding the time window; and 5) applying PIBT to applications other than MAPF and MAPD.

Acknowledgments

Research partly supported by JSPS KAKENHI Grants No. 17K00019 and 17K12734, and by Japan Science and Technology Agency (JST) SICORP.