Paper deep dive
Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni, Jiaoyang Li
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 3/26/2026, 1:47:13 AM
Summary
The paper introduces Multi-Dependency PIBT (MD-PIBT), a generalized framework for Multi-Agent Path Finding (MAPF) that plans over agent dependencies rather than simple one-step conflicts. By allowing agents to have multi-step paths and managing complex dependency graphs, MD-PIBT overcomes the limitations of standard PIBT and EPIBT, effectively scaling to 10,000 agents under various kinodynamic constraints.
Entities (5)
Relation Signals (3)
MD-PIBT → solves → MAPF
confidence 100% · In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies.
MD-PIBT → generalizes → PIBT
confidence 95% · MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT.
PIBT → isa → MAPF Algorithm
confidence 90% · PIBT is a popular algorithm capable of effectively planning in such situations.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that conflict with at most one other agent. This limitation also applies to Enhanced PIBT (EPIBT), a recent extension of PIBT. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations yield novel planning strategies that are not expressible by PIBT or EPIBT. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents.
Tags
Links
- Source: https://arxiv.org/abs/2603.23405v1
- Canonical: https://arxiv.org/abs/2603.23405v1
Trouble viewing inline? Open PDF directly →
Full Text
64,578 characters extracted from source content.
Expand or collapse full text
Planning over MAPF Agent Dependencies via Multi-Dependency PIBT Zixiang Jiang1∗, Yulun Zhang2∗, Rishi Veerapaneni2∗, Jiaoyang Li2 ∗These authors contributed equally.1Zixiang Jiang is with the University Of Melbourne. gmmichaeljiang@gmail.com2Yulun Zhang, Rishi Veerapaneni, and Jiaoyang Li are with the Robotics Institute, Carnegie Mellon University. yulunzhang,vrishi,jiaoyangli@cmu.edu Abstract Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that conflict with at most one other agent. This limitation also applies to Enhanced PIBT (EPIBT), a recent extension of PIBT. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT’s priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations yield novel planning strategies that are not expressible by PIBT or EPIBT. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents. I Introduction Multi-Agent Path Finding (MAPF) [20] aims to move agents from their corresponding start to goal locations without conflicts. Applications of MAPF such as autonomous warehouses [12] and robotic sorting systems [26] could involve up to 4,000 ground robots moving in a shared environment [2]. These systems require efficient algorithms that return collision-free paths in less than a second. Currently, most state-of-the-art methods for very fast and scalable planning leverage Priority Inheritance with Backtracking (PIBT) [14] due to its extreme speed and ability to find collision-free one-step solutions in congestion (e.g., LaCAM [16], WPPL [9], SILLM [8], EPIBT [25]). At its core, PIBT is a priority based one-step planner that is powerful due to its ability to handle dependencies between high-priority and low-priority agents. In particular, if a high-priority agent proposes a move that bumps into a low-priority agent, the low-priority agent inherits the high priority and can force other agents to make space for it. This behavior is critical in congestion and is the main difference between PIBT and regular prioritized planning. However, PIBT is fundamentally limited as it only reasons about one dependency at a time between a high-priority and low-priority agent. This means that PIBT cannot directly plan multi-step action sequences where one high-priority agent’s path could conflict with multiple low-priority agents. Existing work generalizing PIBT to multi-step planning (e.g., winPIBT [15], EPIBT [25]) retains this limitation and cannot handle multiple dependencies between agents. This contrasts with Conflict-Based Search (CBS) [18], which is a foundational method in MAPF that has been applied to a variety of different MAPF agent dynamic models. CBS’s core idea is to search over space-time constraints, which enables it to be a very general framework (since constraints can be applied to different domains easily). Ideally, we would like to generalize PIBT to be a similar general framework that can work with different MAPF variants. To that end, our contribution is designing Multi-Dependency PIBT (MD-PIBT), which formally introduces the idea of searching over agent dependencies (as opposed to space-time constraints). This perspective enables planning over multi-step paths that can conflict with multiple other agents, and can directly work with different MAPF models. MD-PIBT is a general algorithm with several hyper-parameters that can be optimized and can replicate PIBT and EPIBT with specific instantiations. We evaluate MD-PIBT on several MAPF variants and show that MD-PIBT significantly outperforms PIBT and EPIBT when planning with large agents. Interestingly, however, on other MAPF instances of one-shot, lifelong MAPF with/without rotations, both PIBT and EPIBT are surprisingly strong, and MD-PIBT is able to reproduce their performance. I Background I-A Multi-Agent Path Finding Multi-Agent Path Finding (MAPF) requires finding collision-free paths for a set of N agents, denoted as A=a1,…,aNA=\a_1,...,a_N\, where each agent must travel from its start location sis_i to its goal location gig_i. In the standard 2D MAPF setup, agents move on a 4-connected grid graph discretized into evenly spaced cells. A collision-free solution consists of a set of paths Π=a1.π,…,aN.π =\a_1.π,...,a_N.π\ satisfying ai.π0=sia_i.π^0=s_i, ai.πT=gia_i.π^T=g_i, where T is the maximum timestep of all agents’ paths. A collision-free solution must avoid vertex collisions (when two agents occupy the same cell at the same timestep) and edge collisions (when two agents swap positions between consecutive timesteps). In MAPF, agents can move according to different dynamic models. We consider three models: (1) Pebble Motion (PM) [20], where agents move omni-directionally, (2) Pebble Motion with Large Agents (PMLA) [11], where agents have different sizes and move identically to PM, and (3) Rotation Motion (RM) [9], where agents rotate in place or move forward. Additionally, planned paths can be executed using the Differential Drive Robots (DDR) [24] model, where agents rotate or move forward with speed and acceleration limits. In all models, agents can wait at their current cell. Our experiments evaluate on one-shot MAPF and lifelong MAPF. In one-shot MAPF the objective is to find a solution Π that minimizes the total cost |Π0:T|=∑i=1N|ai.π0:T|=∑i=1N∑t=0T−1c(ai.πt,ai.πt+1)| ^0:T|= _i=1^N|a_i.π^0:T|= _i=1^N _t=0^T-1c(a_i.π^t,a_i.π^t+1). In this work, we assume that every action has unit cost c(ai.πt,ai.πt+1)=1c(a_i.π^t,a_i.π^t+1)=1, except when an agent remains at its goal (in which case the cost is zero). Each agent has a single fixed goal. Lifelong MAPF is a variant of MAPF where agents are reassigned a new goal each time they reach their current assigned goals. The objective is to maximize throughput, the average number of goals reached per timestep summed over all agents. Lifelong MAPF is typically solved by decomposing it into a sequence of MAPF problems and solving them by searching for windowed paths [12]. I-B MAPF Algorithms Search-based methods for MAPF are powerful and popular. CBS [18] is a foundational method that decomposes the MAPF instance into repeated single-agent calls, and iteratively resolves collisions by searching over space-time constraints. CBS is popular both due to its generality; it can be applied in many different domains and also has several algorithmic extensions [1, 10]. Another popular paradigm are priority-based algorithms, such as Priority Planning (P) [6], plan each agent in a pre-defined priority, but can easily lead to deadlocks. Priority Based Search (PBS) [13] combines CBS and P to search for priority orders of the agents to improve success rates. Additionally, learning-based methods are getting increasingly popular. Methods leverage imitation learning [8], or reinforcement learning to train a shared policy [19, 17]. However, for certain real-world situations, having a planning time of less than one minute using search-based or priority-based algorithms is not sufficient, and learning-based methods struggle to generalize to unseen scenarios. For example, the Amazon-sponsored League of Robot Runners competition requires planning 10,000 agents in one second [5]. In such scenarios, most state-of-the-art MAPF methods leverage rule-based methods [23], which move agents by following a set of pre-defined rules. The state-of-the-art rule-based method is Priority Inheritance with Backtracking (PIBT) [14] due to its extreme speed. I-C PIBT and Its Variants PIBT is an extremely fast one-step priority-based planning algorithm that is capable of returning collision-free solutions for hundreds of agents in less than 200 milliseconds [9], making it the key component within several modern state-of-the-art MAPF methods [16, 9, 8, 25]. PIBT is a one-step rule-based planning algorithm. In each timestep, agents are assigned a priority. PIBT sequentially plans each agent starting from the highest priority agent. When planning, an agent is always required to avoid higher priority agents’ paths. If a high-priority agent aia_i plans a one-step path that bumps into (i.e. collides with) a lower priority agent aja_j’s start location, PIBT lets aja_j temporarily inherit the priority of aia_i and attempt to plan an action. If aja_j is able to find a collision-free path avoiding planned paths of higher priority agents, then aia_i can use its one-step plan. If not, aja_j is required to wait at its current location and aia_i is required to try a different action (the backtracking part of PIBT). When used for multi-step planning, PIBT plans sequential one-step plans. This retains PIBT’s speed but leads to instances where agents perform myopically. For example, when two agents enter the same corridor in opposite directions, the lower priority agent only knows to move backward once it meets the high-priority agent. Previous work on extending PIBT to plan for multiple steps, namely windowed PIBT (winPIBT) [15], performed worse than PIBT. To mitigate this issue, Enhanced PIBT (EPIBT) [25] improves PIBT by planning windowed w-step (w≥1w≥ 1) paths instead of one step. Given a planning window w≥1w≥ 1, EPIBT enumerates all w-step paths and runs PIBT where agents choose between these paths instead of their regular single-step action. PIBT and EPIBT also assume that the agents are identical in size. Heterogeneous PIBT (HetPIBT) [4] extends PIBT to work with heterogeneous agents that vary in both size and speed. It assumes that an agent’s velocity is proportional to its size and plans agents sequentially as PIBT does. It starts by finding a spatial path for each agent such that the lower priority agents will vacate the space required by the higher priority agents’ paths. It then backtracks to fill up the temporal information of the spatial paths. A core problem with EPIBT and PIBT is that w-step paths with w>1w>1 could result in a high-priority agent bumping into multiple low-priority agents. Even for HetPIBT, while it increases the length of each single-step path based on agents’ velocities, it cannot consider multi-step paths that collide with multiple agents. This poses a series of difficult questions. For example, how does priority inheritance work if we allow each agent to collide with multiple agents? Which low-priority agent gets planned next if there are multiple? What happens if one agent succeeds while the other fails? PIBT does not need to reason about this instance as it only deals with one-step planning where an agent can only bump into at most one other agent. EPIBT also explicitly avoids these questions by only considering operations that conflict with at most one other agent. Our objective is to remove the restriction of only considering paths with ≤ 1 collision by introducing Multi-Dependency PIBT. I Agent Dependency Perspective of PIBT Our main theoretical insight is reinterpreting PIBT as a method that reasons over agent dependencies. We define each agent aia_i to have a (tentative) path ai.πa_i.π that we are trying to compute. In addition, each agent aia_i also has a safe path ai.τa_i.τ, which has the property that the set of safe paths a1:N.τa_1:N.τ for all agents is collision-free. Note that, at every timestep t, all agents have a trivial safe path of waiting at their current locations, i.e., ai.πt+1←ai.πt,∀ai∈Aa_i.π^t+1← a_i.π^t,∀ a_i∈ A. With the concept of safe paths, we now describe PIBT as reasoning over agent dependencies between tentative paths and safe paths. PIBT initializes the safe paths with wait action and plans (tentative) paths for each agent one by one. Each PIBT call attempts to find tentative paths that are collision-free with each other and with the safe paths of the agents that do not have tentative paths yet. This requires PIBT to reason agent dependencies when a high-priority agent aia_i’s tentative path collides with a low-priority agent aja_j’s safe path. When this occurs, PIBT requires aja_j to find a path that does not collide with any high-priority agents. If aja_j cannot, then it chooses its safe path, which requires aia_i to try an alternative path. We now formally define dependencies. Definition 1 (Agent Dependencies) aia_i has an agent dependency on aja_j if aia_i’s path overlaps with aja_j’s safe path, i.e., ai.πa_i.π collides with aj.τa_j.τ. Conceptually, an agent dependency from aia_i to aja_j denotes that for aia_i to use ai.πa_i.π, aja_j must find a collision-free path aj.πa_j.π that is not the safe path. If aja_j cannot find such a path, it has to use its safe path, and aia_i needs to find a new path. We now define two types of dependencies, namely hard and soft dependencies, depending on if aja_j is planned or not. Definition 2 (Hard Dependencies) aia_i has a hard dependency on aja_j if aia_i’s path overlaps with aja_j’s safe path and aja_j is not planned, i.e., ai.πa_i.π collides with aj.τa_j.τ and aj.π=⟂a_j.π= . Definition 3 (Soft Dependencies) Agent aia_i has a soft dependency on aja_j if agent aia_i’s path overlaps with aja_j’s safe path and aja_j is planned, i.e., ai.πa_i.π collides with aj.τa_j.τ and aj.π≠⟂a_j.π≠ . PIBT only plans with hard dependencies, so we focus on that here and revisit soft dependencies later. Since aia_i has been planned and aja_j needs to be planned in the future, aja_j’s path is constrained from colliding with aia_i’s planned path. In the context of PIBT, given a hard dependency, instead of planning a different agent after planning aia_i, PIBT plans for aja_j next (thereby allowing aja_j to inherit aia_i’s priority). Using this definition of agent dependencies, we reinterpret PIBT as searching over an Agent Dependency Graph. Definition 4 (Agent Dependency Graph (AgDG)) An agent dependency graph is a directed graph where each agent is a node, and each edge denotes either a hard dependency (ai→aja_i→ a_j) or a soft dependency (ai⇢aja_i a_j). In PIBT, each ai.πa_i.π is a one-step path, so each agent can depend on at most one other agent. Thus, PIBT’s AgDG is a linked list. From the AgDG perspective, PIBT starts by planning the highest priority agent and then plans through all dependent agents until all of them have collision-free paths. Then, PIBT proceeds to the next-highest-priority unplanned agent and repeats this process until all agents are planned. 1Agent aka_k: π←⟂π← // Tentative path τ←τkτ← _k // Safe path p←ϕ(ak)p←φ(a_k) // Priority ←ρ(sk,gk,w)P←ρ(s_k,g_k, [rgb]0.7,0,0w) // All w-step paths, sorted by distance to goal d←0d← 0 // Path index r←0r← 0 // # of planning attempts Algorithm 1 Agent class 1 Input: Agents A=a1,…,anA=\a_1,...,a_n\ with initialized values according to the agent class; 2 3Initialize (=A,ℰ=∅)G(V=A,E= ), Aplan←A_plan←\\ 4 for ai∈sorted(A)a_i∈ sorted( A ) do 5 if ai.r=0a_i.r=0 then 6 MDPIBT(aia_i, A, G, AplanA_plan) 7 for ak∈A:ak.π≠⟂a_k∈ A:a_k.π≠ do 8 ak.τ←ak.πa_k.τ← a_k.π, ak.π←⟂a_k.π← 9 10 11 Algorithm 2 MD-PIBT: Outer Loop 1 2Function MDPIBT(aia_i, A, G, AplanA_plan): 3 q←q← Queue(aia_i) 4 while q≠∅q≠ do 5 ak←q.pop()a_k← q.pop() 6 ak.r←ak.r+1a_k.r← a_k.r+1 7 π′←π (ak,Aplan|m,Ca_k,A_plan [rgb]0.7,0,0~|~m,C) 8 if π′≠⟂π ≠ then // Section IV-B 9 ak.π←π′a_k.π←π , Aplan←Aplan∪akA_plan← A_plan∪\a_k\ 10 addDepend(G, aka_k, π′π , q, A) 11 12 else // Section IV-C 13 if fallToSafePath(ak|Ra_k [rgb]0.7,0,0~|~R) then 14 for ap:(ap→ak)∈ℰa_p:(a_p→ a_k) do 15 removeDepend(G, apa_p, q, AplanA_plan) 16 17 ak.π←ak.τa_k.π← a_k.τ, Aplan←Aplan∪akA_plan← A_plan∪\a_k\ 18 19 else 20 ap←chooseParent(δHARD−(ak))a_p← [rgb]0.7,0,0 chooseParent(δ^HARD-(a_k)) 21 removeDepend(G, apa_p, q, AplanA_plan) 22 q.push(ap)q.push(a_p) 23 24 25 26 Algorithm 3 MD-PIBT Function 1 2Function addDepend(G, aka_k, π′π , q, A): 3 for ai≠k∈Aa_i≠ k∈ A : hasCollision(ai.τa_i.τ, π′π ) do 4 if ai.π=⟂a_i.π= then 5 ℰ←ℰ∪(ak→ai)E ∪\(a_k→ a_i\) 6 q.push(ai)q.push(a_i) 7 8 else 9 ℰ←ℰ∪(ak⇢ai)E ∪\(a_k a_i)\ 10 11 12 13 14Function removeDepend(G, apa_p, q, AplanA_plan): 15 16 ap.π←⟂a_p.π← , Aplan←Aplan∖apA_plan← A_plan \a_p\ 17 convertSoftEdgesToHard(δSOFT−δ^SOFT-) 18 if |δHARD−(ap)|>0|δ^HARD-(a_p)|>0 and ap∉qa_p∉ q then 19 q.push(ap)q.push(a_p) 20 else if |δHARD−(ap)|=0|δ^HARD-(a_p)|=0 and ap∈qa_p∈ q then 21 q.erase(ap)q.erase(a_p) ℰ←ℰ∖δSOFT+(ap)E δ^SOFT+(a_p) // Remove out soft edges 22 for ac:(ap→ac)∈ℰa_c:(a_p→ a_c) do 23 ℰ←ℰ∖(ap→ac)E \(a_p→ a_c)\ 24 ac.d←0a_c.d← 0 25 removeDepend(G, aca_c, q, AplanA_plan) 26 27 Algorithm 4 Agent Dependency Graph Functions IV Multi-Dependence PIBT We describe MD-PIBT in Algorithms 1, 2, 3 and 4, where red codes refer to hyper-parameters. We first give an overview of MD-PIBT in Section IV-A and then discuss its key components in Sections IV-B and IV-C, with a summary of its hyper-parameters in Section IV-D. With certain choices of these hyperparameters, MD-PIBT can be reduced to standard PIBT or EPIBT. In addition to the explanations, we give a running example of MD-PIBT in Figure 1. IV-A Overview Unlike PIBT, which generates collision-free one-step paths, MD-PIBT aims to plan collision-free w-step paths (w≥1w≥ 1). Algorithm 1 shows the set of attributes for each agent. Importantly, each agent aka_k is initialized with the set of all w-step paths P starting at the start location sks_k, sorted by the distance from the end of the path to the goal location gkg_k. The agent can try different paths by iterating through this list via a path index d. We explain other attributes while diving into the algorithm. Algorithm 2 shows the outer loop. MD-PIBT initializes the agents with an AgDG G and a set of agents AplanA_plan to remember all agents that have a tentative path. It then calls the MDPIBT function on each agent aia_i in the priority order given by p (computed by a priority function ϕφ) in Algorithm 1 if aia_i has never been planned (line 3). After planning for aia_i and its potential descendants (line 4), we update the safe paths of all agents by replacing their current safe paths with the newly planned tentative paths, if there is one, and reset all tentative paths to ⟂ (line 5-6). Algorithm 3 presents the core logic of MD-PIBT. We maintain a priority queue q, initialized with the starting agent aia_i (line 2), which stores all agents whose dependencies require resolution and thus must be planned. Because the AgDG is a graph rather than a linked list, multiple agents may simultaneously become eligible for planning, and the order in which they should be processed is not uniquely determined. To accommodate this flexibility, we employ a priority queue that allows agents to be selected according to a configurable ordering policy. At each step, MD-PIBT selects the next agent from q, plans for that agent, and introduces additional dependencies when necessary. To manipulate AgDG G, we define functions δHARD+δ^HARD+, δHARD−δ^HARD-, δSOFT+δ^SOFT+, and δSOFT−δ^SOFT- to retrieve the hard and soft outgoing edges (++) and incoming edges (−-) of an agent in G. In addition, we define δ+δ^+ and δ−δ^- to denote the sets of all the incoming and outgoing edges, respectively. In each iteration, MD-PIBT pops the next agent aka_k from q and increments its planning attempt counter r (lines 3–5). MD-PIBT then leverages the findBestPath function (line 6), which uses a path index d and a sorted list of all w-step paths P in Algorithm 1 to find its next-best valid path. We define the valid path in Section IV-D. If a valid path π′π exists (line 7), it adds dependency edges based on whose safe paths π′π collides with (line 8), updates aka_k’s tentative path, and adds aka_k to AplanA_plan (line 9). More details are explained in Section IV-B. If aka_k cannot find a valid path π′π , aka_k needs to decide between taking its safe path ak.τa_k.τ (lines 12-14) and allowing itself to replan by first requesting its parent to replan (lines 16-18). More details are explained in Section IV-C. This process is repeated until the queue becomes empty. Figure 1: Multi-Dependence PIBT (MD-PIBT) builds and searches over an Agent Dependency Graph. Left shows an scenario for planning with a window size of 3, with initial path preferences drawn. Assume all agent’s safe paths are waiting at their current location. (1) Let MD-PIBT start planning with A. A’s path conflicts with B, D, and E’s safe path, causing A to have hard dependencies on them (Def. 2, they must find non-safe paths for A’s path to be valid). Thus, B,D,EB,D,E need to be planned next. Given multiple agents, we plan in alphabetical order. (2) When B plans, B’s path collides with C and A’s safe path. Since A is already planned, we record a soft dependency between B and A. (3-6) This logic continues until planning F. (7) F fails to find a collision-free path. When this occurs, F requires a parent (in this case C) to replan. The replan request unplans C which includes removing downstream dependencies and converting soft dependencies to C to hard dependencies. (8) Suppose that C replans by moving down, which does not intersect with F’s safe path. Then F is not included in the AgDG. (9) After planning all agents in the AgDG, we can move on to plan other agents not in the AgDG (not depicted). IV-B Accepting the Tentative Path When a valid path π′π exists for agent aka_k (line 7), we accept it as aka_k’s tentative path and add aka_k to AplanA_plan (line 8). Since this tentative path may collide with the safe paths of some agents, we call the addDepend function to update the dependencies (line 9). As shown in Algorithm 4, the addDepend function identifies all agents aia_i whose safe paths collide with π′π and adds hard or soft dependencies accordingly. IV-B1 Add Hard Dependencies Lines 3-5 add hard dependencies ak→aia_k→ a_i to G for all unplanned agents aia_i (i.e., aia_i does not have a tentative path ai.πa_i.π) whose safe paths collide with π′π . For example, in Figure 1(1), agent A bumps into safe paths of unplanned agents B, D, and E, so we add hard dependencies from A to all of them. IV-B2 Add Soft Dependencies Unlike PIBT, MD-PIBT requires soft dependencies. Lines 6-7 add soft dependencies ak⇢aia_k a_i for all planned agents aia_i (i.e., aia_i has a tentative path ai.πa_i.π) whose safe paths collide with π′π . For example, in Figure 1(4), agent aDa_D is planning and aD.πa_D.π overlaps with aC.τa_C.τ after aCa_C has a tentative path aC.πa_C.π. Later, it might be possible that aC.πa_C.π becomes infeasible. This could occur if aCa_C’s hard dependency descendants fail. If that occurs, aCa_C would need to replan. Now, when aCa_C replans, aD.πa_D.π collides with aC.τa_C.τ, resulting in a hard dependency aD→aCa_D→ a_C, according to Definition 2. To account for this possibility, we need soft dependency edges in Definition 3 and convert them to hard ones when necessary. IV-C Backtracking When no valid path exists for agent aka_k (Algorithm 3 line 10), some already-planned agents must be replanned. This generalizes the backtracking process of PIBT. PIBT forces agent aka_k to take its safe path ak.τa_k.τ and asks the agent whose tentative path collides with ak.τa_k.τ to replan. We generalize this idea as the falling-to-safe-path option, as described in Section IV-C1. Alternatively, EPIBT proposes a different option. If the agent whose tentative path collides with ak.τa_k.τ replans, aka_k may subsequently obtain a valid path that is better than its safe path. Therefore, instead of immediately committing to its safe path, EPIBT allows aka_k to be replanned again. We generalize this idea as the attempting-to-replan option, as described in Section IV-C2. To decide between these two options, we formulate the choice as a hyper-parameterized function fallToSafePath (line 11), which will be introduced in Section IV-D. IV-C1 Falling to Safe Paths If agent aka_k is forced to its safe path (Algorithm 3 lines 12-14), then all agents apa_p that have hard dependencies on aka_k (i.e., ap→aka_p→ a_k) need to be replanned. We use the removeDepend function to update each such apa_p. As shown in Algorithm 4, the removeDepend function first empties the tentative path of agent apa_p and removes it from the planned agent set (line 9). Since apa_p now no longer has a tentative path, by definition, all incoming soft edges become hard edges (line 10). Since any agent with hard dependencies (i.e., has incoming hard edges) must be replanned, we add apa_p to the queue if it is not already there (lines 11-12). On the other hand, since any agent with no hard dependencies does not need to be replanned, we remove apa_p from the queue if it is there (lines 13-14). Then, for outgoing edges of apa_p, all of them should be removed because apa_p no longer has a tentative path (lines 15 and 17). Moreover, replanning apa_p may change the replanning necessity of its children. For example, for a child agent aja_j of apa_p with ap→aja_p→ a_j, if apa_p’s new tentative path no longer collides with aj.τa_j.τ, then aja_j may no longer need to be replanned. Even if apa_p’s new path collides with aj.τa_j.τ, the new path would change the possible collision-free paths that aja_j could choose. Therefore, MD-PIBT recursively unplans all child agents of apa_p (line 19). It also resets the path index (line 18) of each child agent aca_c since previously invalid paths for aca_c may become valid due to the potential change of ap.πa_p.π. Resetting the path index thus allows the agents to retry those options. IV-C2 Attempting to Replan The second option for dealing with the case where no valid paths exist for agent aka_k is to ask one of aka_k’s parent to replan and then retry aka_k (Algorithm 3 lines 16-18). Thus, instead of forcing aka_k to pick the safe path after failing, we choose some parent apa_p (elaborated in Section IV-D) and ask it to replan by reusing the same removeDepend function. We then add apa_p to the queue. Figure 1(6)-(8) shows an example of attempting to replan. An important note is that with replanning, agents can be planned more than once (as compared to PIBT where each agent is planned only once). In the worst case, each agent can be bumped into by a parent an exponential number of times, resulting in intractable runtime. Thus, the fallToSafePath function (elaborated in the next section) is necessary for reasonable runtimes. We additionally conduct theoretical analysis of MD-PIBT in Appendix A1. MAPF Map |V||V| Agent Model w h R C m p One-shot random-32-32-20 819 PM 1,2,3,4\1,2,3,4\ 1,w\1,w\ 100 1,∞\1,∞\ PIBT,EPIBT\PIBT,EPIBT\ LET warehouse-10-20-10-2-1 5,699 PM random-128-128-PMLA 15,580 / 10,862 (S/L) PMLA 3,4\3,4\ 1 100 1,2,4,8,∞\1,2,4,8,∞\ EPIBT LET,SD empty-64-64-PMLA 4,096 / 3,600 (S/L) PMLA maze-128-128-PMLA 14,818 / 8,574 (S/L) PMLA room-128-128-PMLA 14,716 / 11,843 (S/L) PMLA Lifelong random-32-32-20 819 PM, RM PM:1,2,3\1,2,3\ RM:3,4,5\3,4,5\ DDR:3,6\3,6\ 1,w\1,w\ 1,000 1,∞\1,∞\ PIBT,EPIBT\PIBT,EPIBT\ PM/RM:LET,SD DDR: SD warehouse-10-20-10-2-1 5,699 PM, RM TABLE I: Summary of MAPF model, maps, and agent models used in the experiments. |V||V| is the number of vertices in the maps. For PMLA model, the number of vertices is different for large and small agents. We report the number of vertices for small and large agents with the format of “x / y (S/L)”, where x and y are the numbers of vertices for small and large agents, respectively. For agent priority strategies (p), we consider Longer Elapsed Time (LTE) and Shorter Dist (SD). IV-D MD-PIBT Hyperparameters MD-PIBT as described has several possible hyper-parameters (highlighted in red in the algorithms). Queue: The queue may have multiple unplanned agents. Thus, it is a hyper-parameter to decide which agent to plan next. We choose to use a stack, yielding DFS ordering. findBestPath(ak,Aplan,|m,Ca_k,A_plan, [rgb]0.7,0,0~|~m,C): An agent has multiple options when trying to pick the next path. Such paths are defined differently for PIBT and EPIBT. For PIBT [14], a tentative path is valid if it does not collide with the tentative paths of the other planned agents (i.e., agents in AplanA_plan). For EPIBT, a tentative path is valid if it does not collide with the tentative paths of higher priority agents that obtained a new tentative path in the current call. In our experiments, to capture this parameterization, we vary a hyper-parameter Find Path Mode m∈PIBT,EPIBTm∈\PIBT,EPIBT\. We also have a parameter C that controls the maximum number of agents each agent can reach. For PIBT and EPIBT, C=1C=1, while for MD-PIBT, C∈ℤ+C ^+. A valid path shall only collide with at most C other agents. We highlight that these are just hyper-parameters we choose (hence highlighted in red) and that other versions of findBestPath are possible (e.g., outputted by a ML policy). Appendix A2 shows our implementation of findBestPath. fallToSafePath(ak|Ra_k [rgb]0.7,0,0~|~R): Agents can choose when to fall to their safe path or not. Our implementation sets a maximum replan limit R and have each aka_k attempt at most R times before choosing their safe path. Without R, it is possible to bump into an agent an exponential number of times. chooseParent(aka_k): When aka_k cannot find a path, it needs to pick a parent to replan. Note that the picked parent’s descendant agents will be cleared when it replans. Thus, we pick the most recently added parent as that should have fewer descendants than other parents. V Experimental Evaluation (a) random-32-32-20 (b) warehouse-10-20-10-2-1 Figure 2: Success rate and runtime for different numbers of agents for one-shot MAPF with PM agents. (a) random-128-128-PMLA (b) empty-64-64-PMLA (c) maze-128-128-PMLA (d) room-128-128-PMLA Figure 3: Success rate and runtime for different numbers of agents for one-shot MAPF with PMLA agents. (a) random-128-128-PMLA (b) empty-64-64-PMLA (c) maze-128-128-PMLA (d) room-128-128-PMLA Figure 4: Distribution of the number of agent dependencies generated per agent per successful planning attempt, under different agent densities, with w=3w=3. S and L refers to the number of small and large agents, respectively. We compare MD-PIBT with PIBT [14] and EPIBT [25]. We do not compare with winPIBT [15], as it has been shown to perform worse than PIBT or EPIBT. V-A Experiment Setup MAPF Problems, Maps, and Agent Models. Table I columns 1-4 summarize the MAPF problems, maps, and agent models used in the experiments. We conduct experiments with both one-shot and lifelong MAPF with various agent models, including PM, PMLA, RM, and DDR, defined in Section I-A. For maps, we select two maps from the MAPF benchmark [20] for PM, RM, and DDR, while creating maps by emulating patterns of the MAPF benchmark for PMLA. because there are no established benchmarks for it. We visualize the agent models in Appendix A3-A and summarize compute resources in Appendix A3-B. MD-PIBT Hyper-Parameters. Since MD-PIBT is a general framework with many hyper-parameters, we perform an exhaustive evaluation over different combinations of a predefined set of hyperparameters. Table I columns 5-10 summarize the set of hyper-parameters with which we have conducted experiments. A prior work [27] finds that the agent priority ordering strategy in PIBT plays an important role in resolving deadlocks for PIBT in lifelong MAPF. Therefore, in lifelong MAPF experiments, we additionally vary the priority ordering: (1) Longer Elapsed Time (LET) [14], where the agents’ priorities are sorted in ascending order by the number of timesteps elapsed from the point where they reached the last goal, and (2) Shorter Distance (SD) to the goal [9, 25], where they are sorted in ascending order by the distance to the next goal. For one-shot experiments, we always use LET to prevent agents from not blocking other agents by staying at their goal. Following previous work [25, 12], all algorithms plan a w-step path and execute the first h steps (simulation window) (w≥h≥1w≥ h≥ 1). For EPIBT and MD-PIBT, if w>hw>h, we initialize the safe paths to be the unexecuted paths from the previous run. For example, in the timestep t, the algorithms plan collision-free paths a1:N.πt:t+wa_1:N.π^t:t+w and executes a1:N.πt:t+ha_1:N.π^t:t+h. Then the remaining paths (i.e., a1:N.πt+h:t+wa_1:N.π^t+h:t+w) plus h wait actions can be used as the initial safe paths at timestep t+ht+h [25]. For PIBT, we always set w=h=1w=h=1. V-B One-Shot MAPF For one-shot experiments, we report the success rate (when all agents reach their goals) and runtime. We set a time limit of 1,800 seconds for PM and 3,600 seconds for PMLA. For each number of agents, we run 25 instances and plot the average (solid lines) and the 95% confidence interval (shaded areas). We conduct all one-shot experiments in Python. V-B1 Pebble Motion Agents In Figure 2, we show (1) a line that, for each number of agents, demonstrates the MD-PIBT variant with the highest success rate, (2) the configuration that replicates EPIBT in MD-PIBT, and (3) the baseline PIBT and EPIBT. The result shows that (1) the best MD-PIBT configuration always achieves a better or similar success rate with EPIBT, and (2) specific configurations of MD-PIBT are able to replicate EPIBT, despite longer run time due to overhead of manipulating the AgDG. In general, w=3w=3 or 44 with h=1h=1 and m=m= EPIBT performs better. V-B2 Pebble Motion with Large Agents MD-PIBT allows an agent to bump into multiple agents. For homogeneous agents, multiple bumps occur only when w>1w>1. In heterogeneous settings with agents of different sizes, larger agents may simultaneously bump into multiple smaller agents within a single planning step. We evaluate this setting on four maps constructed by emulating those in the MAPF benchmark [20]. Each map is designed so that the largest agent can traverse the narrowest corridor. In empty-64-64-PMLA and maze-128-128-PMLA, agents have sizes 1×11× 1 and 5×55× 5, while in random-128-128-PMLA and room-128-128-PMLA, agent sizes are 1×11× 1 and 4×44× 4. Figure 3 compares MD-PIBT with EPIBT. MD-PIBT with C>1C>1 significantly outperforms EPIBT in terms of success rate. Because EPIBT is strictly limited to C=1C=1, large agents are easily trapped by livelocks or deadlocks when surrounded by multiple small agents, leading to deadlock. However, a larger value of C allows large agents to push away the surrounding small agents. In addition, increasing the window size also increases the success rate. Because larger agents occupy more space and thus take longer to clear corridors, smaller agents are heavily punished for myopic planning. Interestingly, in these scenarios, increasing C generally does not increase runtime. Figure 4 shows the average number of dependencies in AgDG that each agent has in a successful plan. Each line represents a scenario with different numbers of small and large agents. As the scenarios become more congested, the number of dependencies increases. Thus, it is crucial to be able to resolve multi-dependencies in scenarios with different agent sizes, especially in dense scenarios. (a) random-32-32-20 (b) warehouse-10-20-10-2-1 Figure 5: Throughput and runtime with different numbers of agents for LMAPF with PM agents. (a) random-32-32-20 (b) warehouse-10-20-10-2-1 Figure 6: Throughput and runtime with different numbers of agents for LMAPF with RM agents. (a) random-32-32-20 (b) warehouse-10-20-10-2-1 Figure 7: Throughput and runtime with different numbers of agents for LMAPF with DDR agents. V-C Lifelong MAPF For lifelong experiments with PM and RM, we set a time limit of 1 second for each timestep and run 1000 timesteps for each simulation. In case of timeout, we run a rule-based backup planner with negligible runtime [12]. For DDR, we use LSMART [24], a tool for evaluating MAPF algorithms with DDRs in continuous time. We use planners to plan paths every 1 second and execute paths using ADG [7]. Due to limit in compute, we do not perform a hyper-parameter search for DDR agents but rather plotted representation configurations of MD-PIBT. For all lifelong experiments, we report throughput (the number of goals reached per timestep or per second) and runtime. For each number of agents, we run 10 simulations and plot the average as solid lines and the 95% confidence interval as shaded areas. We conduct all lifelong experiments in C++. Figures 5 and 6 shows the results of lifelong MAPF with PM and RM. We show the same lines as one-shot MAPF. In random-32-32-20, with PM agents, planning with a longer window of 33 is helpful to achieve the maximum throughput with 300 agents. However, with more agents, PIBT with SD priority surprisingly outperforms other methods, followed by MD-PIBT replication of it. Similarly, in warehouse-10-20-10-2-1, PIBT with LET priority achieves the best performance. With RM agents, EPIBT remains the best, with the MD-PIBT variant that replicates EPIBT closely following. Figure 7 shows the results of lifelong MAPF with DDR. The trend is similar to RM, where EPIBT and the variant of MD-PIBT that replicate EPIBT outperform other variants. V-D Additional Experiments We show additional experiment results in Appendix A3, including (1) one-shot and lifelong MAPF results with PM and RM agents in the den312d and Paris-1-256 maps [20], (2) one-shot MAPF results with PMLA agents with w=4w=4, and (3) a summary of best MD-PIBT hyper-parameterization in all maps. VI Conclusion We propose MD-PIBT as a general MAPF framework that searches over agent dependencies. MD-PIBT enables more effective multi-step planning that removes the restrictions of PIBT/EPIBT (which can only reason about paths that conflict with at most one other agent). We demonstrate how MD-PIBT can replicate the behavior of PIBT/EPIBT as well as other variants. We show that the best of MD-PIBT performs similar to the best of PIBT/EPIBT in one-shot and lifelong MAPF settings while significantly outperforming them in MAPF with large agents. There are exciting opportunities for future work on MD-PIBT. MD-PIBT’s ability to work with multi-step paths enables future research that can try to incorporate kinematic constraints within this framework. Further optimizations for large agents (e.g., similarly motivated with Het-PIBT [4]) would be promising. Additionally, MD-PIBT could be used as a collision-shield for future learned multi-step MAPF policies (e.g., an extension of [22]). Finally, taking a step back, MD-PIBT as formulated given safe paths and agent dependencies is agnostic to the low-level search. This is similar to Conflict-Based Search [18] which is popular due to its generality and performance. Thus, MD-PIBT could potentially be developed and used as broadly as CBS or developed as a future multi-robot protocol [21]. Acknowledgments This work used Bridge-22 at Pittsburgh Supercomputing Center (PSC) [3] through allocation CIS220115220115 from the Advanced Cyberinfrastructure Coordination Ecosystem: Services & Support (ACCESS) program, which is supported by NSF under grant numbers #21382592138259, #21382862138286, #21383072138307, #21376032137603, and #21382962138296. References [1] M. Barer, G. Sharon, R. Stern, and A. Felner (2014) Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In SoCS, p. 19–27. Cited by: §I-B. [2] A. S. BrownA. Science (Ed.) (2022) How Amazon robots navigate congestion. Note: https://w.amazon.science/latest-news/how-amazon-robots-navigate-congestionAccessed: 2023-05-09 Cited by: §I. [3] S. T. Brown, P. Buitrago, E. Hanna, S. Sanielevici, R. Scibek, and N. A. Nystrom (2021) Bridges-2: a platform for rapidly-evolving and data intensive research. In Proceedings of the Practice and Experience in Advanced Research Computing (PEARC): Evolution Across All Dimensions, PEARC ’21. Cited by: §A3-B, Acknowledgments. [4] A. Chakravarty, M. X. Grey, M. A. Viraj, J. Muthugala, and M. R. Elara (2026) Extending pibt to support heterogeneous robot fleets. In International Workshop on Multi-Agent Path Finding, Cited by: §I-C, §VI. [5] S. Chan, Z. Chen, T. Guo, H. Zhang, Y. Zhang, D. Harabor, S. Koenig, C. Wu, and J. Yu (2024) The league of robot runners competition: goals, designs, and implementation. In ICAPS – System Demonstrations Track, Cited by: §I-B. [6] M. Erdmann and T. Lozano-Perez (1987) On multiple moving objects. Algorithmica 2, p. 477–521. Cited by: §I-B. [7] W. Hönig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian (2019) Persistent and robust execution of MAPF schedules in warehouses. IEEE RA-L 4 (2), p. 1125–1131. External Links: Document Cited by: §V-C. [8] H. Jiang, Y. Wang, R. Veerapaneni, T. Duhan, G. Sartoretti, and J. Li (2025) Deploying ten thousand robots: scalable imitation learning for lifelong multi-agent path finding. In ICRA, p. 1–7. Cited by: §I, §I-B, §I-C. [9] H. Jiang, Y. Zhang, R. Veerapaneni, and J. Li (2024) Scaling lifelong multi-agent path finding to more realistic settings: research challenges and opportunities. In SoCS, p. 234–242. External Links: Document Cited by: §I, §I-A, §I-C, §V-A. [10] J. Li, W. Ruml, and S. Koenig (2021) EECBS: a bounded-suboptimal search for multi-agent path finding. In AAAI, p. 12353–12362. Cited by: §I-B. [11] J. Li, P. Surynek, A. Felner, H. Ma, T. K. S. Kumar, and S. Koenig (2019) Multi-agent path finding for large agents. In AAAI, Cited by: §I-A. [12] J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. S. Kumar, and S. Koenig (2021) Lifelong multi-agent path finding in large-scale warehouses. In AAAI, Vol. 35, p. 11272–11281. Cited by: §I, §I-A, §V-A, §V-C. [13] H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig (2019) Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, Cited by: §I-B. [14] K. Okumura, M. Machida, X. Défago, and Y. Tamura (2022) Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence 310, p. 103752. Cited by: §I, §I-B, §IV-D, §V-A, §V. [15] K. Okumura, Y. Tamura, and X. Défago (2019) Winpibt: extended prioritized algorithm for iterative multi-agent path finding. arXiv preprint arXiv:1905.10149. Cited by: §I, §I-C, §V. [16] K. Okumura (2023) Lacam: search-based algorithm for quick multi-agent pathfinding. In AAAI, Vol. 37(10), p. 11655–11662. Cited by: §I, §I-C. [17] G. Sartoretti, J. Kerr, Y. Shi, G. Wagner, T. K. S. Kumar, S. Koenig, and H. Choset (2019) PRIMAL: pathfinding via reinforcement and imitation multi-agent learning. IEEE RA-L 4 (3), p. 2378–2385. Cited by: §I-B. [18] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219, p. 40–66. Cited by: §I, §I-B, §VI. [19] A. Skrynnik, A. Andreychuk, M. Nesterova, K. Yakovlev, and A. Panov (2024) Learn to follow: decentralized lifelong multi-agent pathfinding via planning and learning. In AAAI, Cited by: §I-B. [20] R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Barták (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In SoCS, p. 151–159. Cited by: §I, §I-A, §A3-C, §A3-E, §V-A, §V-B2, §V-D. [21] R. Veerapaneni, A. Tang, H. He, S. Zhao, V. Shah, Y. Cen, Z. Ji, G. Olin, J. Arrizabalaga, Y. Shaoul, et al. (2025) Conflict-based search as a protocol: a multi-agent motion planning protocol for heterogeneous agents, solvers, and independent tasks. arXiv preprint arXiv:2510.00425. Cited by: §VI. [22] R. Veerapaneni, Q. Wang, K. Ren, A. Jakobsson, J. Li, and M. Likhachev (2024) Improving learnt local mapf policies with heuristic search. International Conference on Automated Planning and Scheduling. Cited by: §VI. [23] K. Wang and A. Botea (2011) MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees. Journal of Artificial Intelligence Research 42, p. 55–90. Cited by: §I-B. [24] J. Yan, Y. Zhang, Z. Liu, H. Zhang, H. Jiang, J. Chen, S. F. Smith, and J. Li (2026) Lifelong scalable multi-agent realistic testbed and a comprehensive study on design choices in lifelong agv fleet management systems. arXiv abs/2602.15721. Cited by: §I-A, §V-C. [25] E. Yukhnevich and A. Andreychuk (2025) Enhancing pibt via multi-action operations. In AAAI, Cited by: §I, §I, §I-C, §I-C, §V-A, §V-A, §V. [26] Y. Zhang, A. O. G. Barbosa, F. Pecora, and J. Li (2025) Destination-to-chutes task mapping optimization for multi-robot coordination in robotic sorting systems. In MRS, External Links: Document Cited by: §I. [27] Y. Zhang, V. Bhatt, M. C. Fontaine, S. Nikolaidis, and J. Li (2026) Optimization of edge directions and weights for mixed guidance graphs in lifelong multi-agent path finding. arXiv abs/2602.23468. Cited by: §V-A. Appendix A1 Theoretical Analysis A1-A Runtime Complexity We analyze the runtime complexity via bookkeeping. Specifically, pretend each agent enumerates all its possible paths, and has two counters, a path index counter and a total number of failures counter. For generality, we assume that the total possible paths for an agent are P, e.g., in standard MAPF without rotation with 5 discrete actions and a multi-step planning window of w, ||=Kw|P|=K^w paths, where K is the number of actions in each timestep. Each time an agent aja_j fails to find a path, it will call one of the parents to replan. Importantly, when that parent agent replans, it must try a new path it has not considered before. In particular, that parent agent will increase its path counter |||P|. With that in mind, consider the ’root’ agent ai1a_i_1, which is the first agent in the MDPIBT call (in particular, without a parent agent). Suppose ai1a_i_1’s first plan causes a dependency with ai2a_i_2, and ai2a_i_2’s first plan causes a dependency with ai3a_i_3, and so on, where there is a dependency from aika_i_k to aik+1∀1≤k≤N−1a_i_k+1∀1≤ k≤ N-1. Suppose that this eventually fails when aiNa_i_N fails to find a valid path, after trying all of its |||P| paths. This forces aiN−1a_i_N-1 to try its next best path. Then suppose that all of aiN−1a_i_N-1’s |||P| paths cause dependencies on aiNa_i_N. Note that in each case, aiNa_i_N will need to try |||P| paths, which means that we invoke the findBestPath function |2||P^2| times in total. We can recursively apply this logic for each aika_i_k, where k=N−1,N−2,…,2,1k=N-1,N-2,…,2,1, giving us the worst case scenario where MD-PIBT invokes the findBestPath function ||N|P|^N times before returning. This results in a runtime of O(||N)O(|P|^N). This bound is both useless and useful. The bound is useless in that O(||N)O(|P|^N) is the size of enumerating all possible paths, which is the naive bound. However, the bound is insightful as it reveals how MD-PIBT is searching through the entire search space when encountering failures. Finally, we can show that this bound is somewhat tight in that we can construct an instance (where all agents lined up going into a dead-end corridor) which takes O(||N)O(|P|^N) planning calls. Using R as an upper bound for how many times an agent may replan reduces the exponential runtime to O(NR)O(N^R) instead. Note that NR<<PNN^R<<P^N, as each agent can fail only a maximum of R times before choosing the safe path, and is never replanned again afterwards. A1-B Returns Collision-Free Path Theorem 1 MD-PIBT returns a collision-free solution. Proof: We will prove this via induction. Our inductive hypothesis is that when planning/unplanning every agent, all planned agents have collision-free paths in respect to other planned agents. In the base case with one agent planned, this is trivially true. Now assume at some point in MD-PIBT, we have an AgDG and are planning the next agent aja_j. By our inductive hypothesis, all previously planned paths are collision-free in respect to each other. Case 1: aja_j finds a collision-free solution that avoids previously planned paths (i.e., higher priority agents). If this occurs, then our inductive step holds directly. Case 2: aja_j fails to find a valid solution. Since the safe-path exists, this means that there must exist another agent aia_i whose path is overlapping with aja_j’s safe-path. This would be captured in our AgDG via an edge ai→aja_i→ a_j or ai⇢aja_i a_j. If aja_j has reached its maximum replan limit, then aja_j will choose the safe-path and cause all parents aia_i to clear their paths and replan. In this scenario, all non-cleared paths are still collision-free. If aja_j has not reached its limit, then aia_i’s path is cleared and asked to replan, which still ensures that all non-cleared paths are collision-free. Since 1) the number of planning iterations are bounded as shown in the runtime analysis, 2) at each planning iteration the tentatively planned agents have collision-free paths, and 3) each agent has MD-PIBT called at least once on it, MD-PIBT will find a collision-free solution for all agents. ∎ This proof has two additional subtleties. First, although we use a proof by induction, the progress of MD-PIBT is not monotonic in respect to the number of agents planned. In other words, it is possible that MD-PIBT has less agents planned after an intermediate step (which occurs when an agent fails and a parent’s subtree is cleared). However, as our runtime complexity analysis shows, MD-PIBT is monotonic in respect to the replan counter, and that there exists a finite upper bound and thus guarantees that MD-PIBT will terminate. Second, our proof does not require that if an agent aja_j fails, its parent aia_i clears the entire subtree below it. Thus, it is potentially possible that clearing just aia_i’s path and ai→aja_i→ a_j is sufficient without clearing other nodes/edges. However, this means that if aia_i was replanning, it might need to avoid other agents j′j that were children of aia_i’s original path, meaning that aia_i must avoid paths of lower priority. This behavior is not what we want MD-PIBT to preserve PIBT’s reachability property. 1 2Function findBestPath(ak,Aplan|m,Ca_k,A_plan [rgb]0.7,0,0~|~m,C): 3 4 Acurr←ai∈A|ai.π≠⟂A_curr←\a_i∈ A|a_i.π≠ \ 5 Λ←⋃ai∈Aai.τ∖⋃ai∈Acurrai.τ∪⋃ai∈Acurrai.π ← _a_i∈ Aa_i.τ _a_i∈ A_curra_i.τ∪ _a_i∈ A_curra_i.π 6 while ak.d<|ak.|a_k.d<|a_k.P| do 7 tp←ak.[ak.d]tp← a_k.P[a_k.d] 8 ak.d←ak.d+1a_k.d← a_k.d+1 9 Acollide←A_collide← getCollidingAgents(tptp, Λ ) 10 if |Acollide|>C|A_collide|>C then 11 continue 12 if m=PIBTm=PIBT and Acollide∩Aplan=∅A_collide∩ A_plan= then 13 return tptp 14 15 else if m=EPIBTm=EPIBT and Acollide∩Acurr=∅A_collide∩ A_curr= and ∀ac∈Acollide,ac.p>p,ac.r<R∀ a_c∈ A_collide,a_c.p>p,a_c.r<R then 16 return tptp 17 18 19 return ⟂ 20 Algorithm 5 Path-Related Helper Functions MAPF Map |V||V| Agent Model w h R C m p One-shot Paris-1-256 47,240 PM 1,2,3,4\1,2,3,4\ 1,w\1,w\ 100 1,∞\1,∞\ PIBT,EPIBT\PIBT,EPIBT\ LET room-64-64-8 3,232 PM Lifelong Paris-1-256 47,240 PM, RM PM:1,2,3\1,2,3\ RM:3,4,5\3,4,5\ 1,w\1,w\ PM/RM:10,100,1000\10,100,1000\ 1,∞\1,∞\ PIBT,EPIBT\PIBT,EPIBT\ PM/RM:LET,SD room-64-64-8 3,232 PM, RM TABLE A1: Summary of MAPF model, maps, and agent models used in the additional experiments. |V||V| is the number of vertices in the maps. For agent priority strategies (p), we consider Longer Elapsed Time (LTE) and Shorter Dist (SD). (a) random-32-32-20 (b) warehouse-10-20-10-2-1 (c) Paris-1-256 (d) room-64-64-8 Figure A1: Results of one-shot MAPF with PM agents. A2 Additional Algorithms Algorithm 5 shows the pseudocode of our implementation of the findBestPath function, used in Algorithm 3. Depending on the find path mode m, the function finds a valid path for agent aka_k that does not collide with a different set of agents. We start by finding all agents AcurrA_curr that currently have a tentative path (line 2). We then form a reservation table Λ that consists of the most recent path of each agent (line 3). Specifically, if an agent ai∈Acurra_i∈ A_curr, we add its tentative path ai.πa_i.π to Λ , otherwise, we add its safe path ai.τa_i.τ to Λ . We then start iterating through the candidate paths ak.a_k.P starting from the current path index ak.da_k.d (lines 4-5). After incrementing the path index (line 6), we obtain the set of agents AcollideA_collide with the current candidate path tptp (line 7). Depending on the find path mode m and the maximum number of colliding agents C, we judge whether tptp is valid. For all m, if tptp collides with more than C agents, it is not valid, and we proceed to the next candidate path (lines 8-9). If m=PIBTm=PIBT, then tptp should not collide with the tentative paths of the agents in AplanA_plan (line 10). If m=EPIBTm=EPIBT, aka_k should not collide with agents that have a tentative path in the current MDPIBT function call, agents with higher priorities, and agents that have no replan attempts left (line 12). If tptp is valid, we return it (lines 11 and 13). If no valid paths are found, we return the failure (line 14). A3 Additional Experiments A3-A Visualization of Different Agent Models (a) Pebble Motion (b) Rotation Motion (c) Pebble Motion w/ Large Agents (d) Differential Drive Robots Figure A2: Visualization of agent models used in our one-shot/lifelong MAPF experiments. Figure A2 visualizes the agent models used in our experiments. (a) random-128-128-PMLA (b) empty-64-64-PMLA (c) maze-128-128-PMLA (d) room-128-128-PMLA Figure A3: Suboptimality of sum-of-cost and makespan for different numbers of agents for one-shot MAPF with PMLA agents. A3-B Compute Resources For one-shot experiments, we use a local machine with a 64 core AMD Ryzen 3990X CPU and 192 GB of RAM. For lifelong experiments, we use three machines: (1) a local machine with a 64 core AMD Ryzen 3990X CPU and 128 GB of RAM, (2) a local machine with a 64 core AMD Ryzen 7980X CPU and 256 GB of RAM, and (3) a High Performing Cluster with AMD EPYC 7742 CPUs [3]. (a) random-128-128-PMLA (b) empty-64-64-PMLA (c) maze-128-128-PMLA (d) room-128-128-PMLA Figure A4: Distribution of the number of agent dependencies generated per agent per successful planning attempt, under different agent densities, with w=4w=4. S and L refers to the number of small and large agents, respectively. A3-C One-shot MAPF with PM Agents Rows 1 and 2 of Table A1 summarize the additional experiments we conduct for MD-PIBT in one-shot MAPF. We use these configurations to perform a hyper-parameter search in the Paris-1-256 and room-64-64-8 maps of the MAPF benchmark [20] with PM agents. In addition to runtime and success rate, we show the solution qualities as Sum-of-cost / LB and Makespan / LB, which are the suboptimality of sum-of-cost and makespan, respectively. The sum of-costs is the sum of each agent’s path length while the makespan is the number of timesteps it takes for all agents to reach their goals. LB refers to the lower bound. The lower bound of sum-of-cost is obtained by summing the shortest possible path of each agent, and the lower bound of makespan is obtained by taking the longest shortest path of all agents. If the success rate is less than 1, only the successful runs are used to calculate the suboptimality of sum-of-cost and makespan. Figure A1 shows the results. We show the averages as solid lines and the 95% confidence intervals as shaded areas. MD-PIBT achieves equivalent or better success rates compared to EPIBT and PIBT. Meanwhile, MD-PIBT finds solutions of equivalent higher quality than EPIBT, both in terms of sum-of-cost and makespan. Surprisingly, the solution quality of PIBT is slightly better than other algorithms. To better understand which configuration of MD-PIBT is superior, we show the best sets of hyper-parameters of MD-PIBT in each map with different numbers of agents in Table A2. For the mode of finding path, m=EPIBTm=EPIBT outperforms m=PIBTm=PIBT most of the time. Other parameters in the best configurations vary across maps. In warehouse-10-20-10-2-1, for example, the long corridors push MD-PIBT to prefer longer planning windows of w=4w=4. In random-32-32-20 and room-64-64-8, on the other hand, using a shorter planning window of w=3w=3 is good enough. For Paris-1-256, the map is too large, making a shorter planning window of w≤2w≤ 2 the best option. We do not observe particular patterns in the best value of C. We conjecture that allowing one agent to collide with multiple agents during planning is not always helpful in all scenarios. A3-D One-shot MAPF with PMLA Agents In Figure A3, we show the suboptimality of sum-of-cost and makespan of the experiment results discussed in Figure 3 of Section V-B. We show the average as solid lines and the 95% confidence interval as shaded areas. Clearly, MD-PIBT variants find paths of higher quality compared to EPIBT. Among the MD-PIBT variants, a higher value of C is generally helpful in terms of searching for better solutions. In Figure A4, we perform the same analysis as in Figure 4 in Section V-B, with a different size of the planning window of w=4w=4. The trend is similar to the result in Figure 4, where more agents correspond to more agent dependencies on all maps. (a) Paris-1-256 (b) room-64-64-8 Figure A5: Throughput and runtime with different numbers of agents for LMAPF with PM agents. (a) Paris-1-256 (b) room-64-64-8 Figure A6: Throughput and runtime with different numbers of agents for LMAPF with RM agents. W h C m ρ random-32-32-20 room-64-64-8 warehouse-10-20-10-2-1 Paris-1-256 11 11 11 EPIBT LET 300 22 22 11 PIBT LET 20 22 22 11 EPIBT LET 600 22 22 ∞ EPIBT LET 40 100, 200 100, 200, 400, 500, 700, 800, 900, 1000 33 11 11 EPIBT LET 80, 120, 280, 360 33 11 ∞ EPIBT LET 160, 200, 240, 320 33 33 ∞ EPIBT LET 300, 400, 500, 600, 700, 800, 900, 1000 44 11 11 EPIBT LET 40, 100, 120 44 11 ∞ EPIBT LET 80, 140, 160, 180 44 44 11 EPIBT LET 60 44 44 ∞ PIBT LET 400 TABLE A2: Best configurations of MD-PIBT for each map for different numbers of agents in one-shot experiments (R=100R=100). The best configuration is sorted by success rate, and sum-of-cost and runtime are used as tie-breakers. W h C m ρ random-32-32-20 room-64-64-8 warehouse-10-20-10-2-1 Paris-1-256 11 11 11 PIBT SD 800 600, 1000, 1400, 2200 4000, 5000, 6000, 7000, 9000, 10000 11 11 11 PIBT LET 2600 1800, 2200, 2600 11 11 ∞ PIBT SD 400, 500, 600, 700 200, 1800 8000 11 11 ∞ PIBT LET 3000 3000 22 22 ∞ PIBT LET 3000 33 11 11 PIBT SD 600 33 11 11 PIBT LET 1400 33 11 11 EPIBT SD 1000 33 11 ∞ EPIBT SD 200 33 33 ∞ PIBT SD 200 33 33 ∞ PIBT LET 300 2000 33 33 ∞ EPIBT LET 100 1000 TABLE A3: Best configurations of MD-PIBT for each map for different numbers of agents in LMAPF experiments with PM agents. The best configuration is sorted by throughput. W h C m ρ random-32-32-20 room-64-64-8 warehouse-10-20-10-2-1 Paris-1-256 33 11 11 PIBT SD 300 200 33 11 11 PIBT LET 3000 2000, 3000, 4000 33 11 11 EPIBT SD 400, 500, 600, 700 600, 1000, 1400, 1800, 2200, 2600 33 11 11 EPIBT LET 1800, 2200, 2600 5000 33 33 11 PIBT SD 800 3000 33 33 11 PIBT LET 6000, 7000, 8000, 9000, 10000 55 11 11 PIBT SD 1000 55 11 11 PIBT SD 100 200, 600 55 11 11 EPIBT SD 200 1000 55 11 11 EPIBT LET 1400 TABLE A4: Best configurations of MD-PIBT for each map for different numbers of agents in LMAPF experiments with RM agents. The best configuration is sorted by throughput. A3-E Lifelong MAPF Rows 3 and 4 of Table A1 summarize the additional experiments we conduct for MD-PIBT in one-shot MAPF. We use these configurations to perform a hyper-parameter search in the Paris-1-256 and room-64-64-8 maps of the MAPF benchmark [20] with PM and RM agents. Figures A5 and A6 show the result of LMAPF with PM and RM agents, respectively. With PM agents, PIBT remains surprisingly powerful in terms of throughput and runtime, and our MD-PIBT replication of PIBT closely follows. With RM agents, EPIBT and our MD-PIBT replication of EPIBT generally achieve the highest throughput. Tables A3 and A4 summarizes the best MD-PIBT configurations with PM and RM agents, respectively. For PM agents, interestingly, the MD-PIBT variant with w=h=1w=h=1, m=PIBTm=PIBT, and C=1C=1, which replicates PIBT, is quite powerful, especially in larger maps with many agents. The benefit of C=∞C=∞ and the higher values of w and h can be seen with a moderate number of agents on different maps (e.g, 100-300 in random-32-32-20, 1000-1400 in warehouse-10-20-10-2-1and 1000-2000 in Paris-1-256). For RM agents, the MD-PIBT variant with w≥1w≥ 1, h=1h=1, C=1C=1, and m=PIBTm=PIBT, which replicates EPIBT, achieves the highest throughput most of the time. Surprisingly, C=∞C=∞ never outperforms C=1C=1. We conjecture that resolving multiple collisions per agent is more challenging with RM agents than with PM agents.