Paper deep dive
A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning
Alex DeWeese, Jiaoyang Li, Guannan Qu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/19/2026, 5:38:28 AM
Summary
This paper introduces Group Decentralized Rolling-Horizon Collision Resolution (GD-RHCR), a parallelized framework for Lifelong Multi-Agent Path Finding (L-MAPF). Building on a theoretical proof that the standard RHCR framework is near-optimal within a Locally Interdependent Multi-Agent MDP (LI-MDP) formulation, the authors propose GD-RHCR. This new method partitions agents into groups based on a transitive communication scheme (visibility radius) and plans for each group in parallel. Theoretical analysis shows GD-RHCR maintains similar near-optimality guarantees as RHCR, establishing a duality between time-based restrictions in vanilla RHCR and space-based partitioning in GD-RHCR. Empirical results demonstrate that GD-RHCR significantly reduces computational cost (up to 24.9x faster planning) while maintaining high throughput, outperforming PIBT and collapsed RHCR in large agent counts.
Entities (9)
Relation Signals (7)
DeWeese → coauthored → Qu
confidence 99% · A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning Alex DeWeese Jiaoyang Li Guannan Qu
GD-RHCR → solves → L-MAPF
confidence 98% · In the Lifelong Multi-Agent Path Finding (L-MAPF) problem... we show that across varying maps, GD-RHCR is able to attain high throughput
GD-RHCR → usesmechanism → group decentralized structure
confidence 96% · GD-RHCR which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme
GD-RHCR → extends → RHCR
confidence 95% · we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR)
RHCR → analyzedusing → LI-MDP
confidence 94% · leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature... we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation
GD-RHCR → reducescostvs → RHCR
confidence 93% · average plan time of can be reduced by a factor of 24.9x and match RHCR in performance before its collapse.
GD-RHCR → outperforms → PIBT
confidence 90% · shows up to a 57.7% improvement in the throughput against PIBT and collapsed RHCR.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.
Tags
Links
- Source: https://arxiv.org/abs/2608.17928v1
- Canonical: https://arxiv.org/abs/2608.17928v1
Trouble viewing inline? Open PDF directly →
Full Text
68,235 characters extracted from source content.
Expand or collapse full text
A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning Alex DeWeese Jiaoyang Li Guannan Qu Abstract In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature (DeWeese and Qu 2024), we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost. 1 Introduction The (one-shot) multi-agent path finding (MAPF) problem is a highly studied area which navigates a large number of agents from some start points to end points on a map while avoiding obstacles as well as collisions among each other. Applications are broad, encompassing warehouse logistics (Ma et al. 2017), airport logistics (Li et al. 2019), UAV traffic management (Ho et al. 2019), parking navigation (Okoso, Otaki, and Nishi 2019), video games (Li et al. 2020) etc. When agents are continuously moving such as in automated package delivery in warehouses, this shifts to a new paradigm called Lifelong MAPF (L-MAPF). In this setting as agents reach a destination, they are immediately assigned a new destination. They must attain a high throughput (e.g. delivered packages) while avoiding collisions with obstacles and with other agents. A wide range of methods have been proposed for this lifelong setting (see section 2). Of these, one important baseline is Priority Inheritance with Backtracking (PIBT), an ultra fast and scalable method that serves as a strong baseline but can have greedy behavior. In contrast to PIBT, another popular solution is the Rolling-Horizon Collision Resolution (RHCR) framework which is seen as one of the highest performing solutions in terms of attaining high throughput. Unfortunately, a weakness of RHCR is its high computational cost especially when compared to PIBT. In practical scenarios like robot navigation in warehouses, RHCR must repeatedly use one-shot MAPF solvers in a short amount of time. Even when using suboptimal solvers like Priority Based Search (PBS), we observe that RHCR explodes exponentially in computational cost. In fact, within the research community, running RHCR as a baseline is seen as a computationally expensive part of running simulations and often must be reported as a partial plan before timeouts hit or run on a smaller subset of problems (Arita and Okumura 2026; Chen et al. 2024). In practice, RHCR can be used with a fallback mechanism where another algorithm (such as PIBT) is taken when some timeout is hit. While it is tempting to speed up RHCR by developing parallelized versions of it (across agents), it remains open how to do so in a theoretically principled way without sacrificing the performance of RHCR. 1.1 Contributions The goal of this work is to develop theoretically principled parallelized RHCR methods that keep (or exceeds) the high-throughput of RHCR, and plans with a fraction of the compute cost. Towards this goal, we build a novel theoretical foundation for RHCR, which leads to a theoretically principled parallelization of RHCR called Group Decentralized RHCR (GD-RHCR), as detailed below. Theoretical foundation of RHCR. We start with a theoretical underpinning of vanilla RHCR as a near-optimal method when modeling the MAPF problem as a discounted MDP using newly established techniques from the Locally Interdependent Multi-Agent MDP (LI-MDP) literature (DeWeese and Qu 2024; DeWeese and Qu 2025). That is, in this discounted setting, the performance of RHCR converges to optimal exponentially fast with the increase in the planning horizon (theorem 4.1). This worst-case bound is agnostic to the replan window (the frequency of reevaluation), suggesting a theoretical motivation for this previously existing concept. Group Decentralized RHCR. The theoretical foundation also motivates a Group Decentralized (GD) version (see definition 3.1) to the RHCR framework. We show that the new GD-RHCR framework satisfies similar theoretical guarantees as RHCR up to constant factors (theorem 6.1), establishing a theoretical duality between the time based restrictions performed by RHCR and the group decentralized distance based partitioning scheme performed by GD-RHCR. These theory results mean GD-RHCR keeps the high-performance advantage of RHCR. In addition to the theoretical guarantee, GD-RHCR has a variety of desirable empirical characteristics that significantly reduce the computational cost compared to RHCR. (1) The time complexity of near-optimal one-shot MAPF algorithms (e.g., CBS and PBS) grows exponentially with the number of agents. By partitioning agents into groups and solving each group independently, GD-RHCR significantly reduces the complexity of the planning problem. (2) GD-RHCR enables replanning for different groups to be performed in parallel and even asynchronously. In particular, only a subset of the groups needs to be replanned at each timestep, reducing the computational burden of online planning. (3) GD-RHCR allows different one-shot MAPF planners to be assigned to different groups. For example, more optimal solvers such as PBS can be used for small groups, while more scalable planners such as PIBT can be used for large groups, providing a natural trade-off between solution quality and computational efficiency. Because of these strengths, for small agent counts that RHCR can already handle, GD-RHCR achieves similar throughput in many cases with significantly faster planning speed; for large agent counts that only PIBT can handle, GD-RHCR can also solve them yet with consistently higher throughput. Experimental Validation. We demonstrate GD-RHCR empirically across a variety of maps and show that the average plan time of can be reduced by a factor of 24.924.9x and match RHCR in performance before its collapse. Further, it performs well deeper into the large agent range and shows up to a 57.7%57.7\% improvement in the throughput against PIBT and collapsed RHCR. 2 Related Works One-Shot MAPF One-shot MAPF solvers are widely put into two categories: Theoretically guaranteed versus greedy methods. The theoretically guaranteed methods provide optimal or near-optimal solution at a potential of high computation time. Some algorithms include Conflict Based Search (CBS) (Sharon et al. 2015), Enhanced CBS (ECBS) (Barer et al. 2014), Explicit Estimation CBS (EECBS) (Li, Ruml, and Koenig 2021). However, since solving MAPF optimally is NP-Hard (Yu and LaValle 2013), these methods can tend to blow up in computation time especially as the number of agents increase. For greedy methods, there are priority based planners such as Priority Planning (Erdmann and Lozano-Perez 1987) and Priority Based Search (PBS) (Ma et al. 2019). These methods can be fast but forgo the theoretical near-optimality. In a similar vein, there are ultra-fast but greedy methods that rely on Priority Inheritance with Backtracking (PIBT) (Okumura et al. 2022) and its variants such as LaCAM (Okumura 2023b; Okumura 2023a). These methods are extremely scalable but may be suboptimal (see section 7). There are also learning based methods that use reinforcement learning or imitation learning directly to solve the MAPF problem (Sartoretti et al. 2019). These methods can perform some parallelism through decentralization, yet there is no guarantee on how much performance is lost due to parallelization/decentralization. Lifelong MAPF Largely, this literature is divided into the the slow but high quality solutions provided by RHCR and the fast but greedy solutions like PIBT. Recall, RHCR enables conversion of the one-shot MAPF solvers to the lifelong setting but may incur a large computation time since one-shot MAPF is NP-hard (Morag, Stern, and Felner 2023). On the other hand, PIBT is a method that can be used in the one-shot context or the lifelong setting and it along with its variations (Chen et al. 2024; Okumura, Tamura, and Défago 2019) remain as a fast alternatives that are greedy and can often suffer from deadlocks when the graph is not biconnected (Okumura et al. 2022). Analogously we have multi-agent RL and imitation learning methods for this setting as well (Damani et al. 2021; Jiang et al. 2025). Grouping in MAPF There have been a number of prior works that attempt to speed up computation by grouping agents. A static grouping method can divide the map into sub-regions and treat agents in each sub-region as a group (Leet, Li, and Koenig 2022). In another context, more sophisticated methods attempt to dynamically identify independent groupings (Veerapaneni et al. 2025; Zhang et al. 2026). This however is done in the context of speeding up an algorithm that maintains completeness guarantees rather than identifying coordination groups that may perform well together. Locally Interdependent Multi-Agent MDP Adjacent to the MAPF literature, there has been a recent breakthrough in the study of discounted multi-agent MDP environments with dynamic local dependencies. A model was proposed called the Locally Interdependent Multi-Agent MDP (LI-MDP) which is a theoretical model for multi-agent systems with local interactions (DeWeese and Qu 2024; DeWeese and Qu 2025). Further the same works proposed the group decentralized setting which connects agents transitively based on their visibility and connected agents are allowed to coordinate. This special observability structure in between the centralized and decentralized setting permits strong theoretical guarantees not available to the decentralized setting (exponentially close to optimal with respect to visibility) but still allows for groups of agents to plan in parallel. We show that the LI-MDP framework brings insight into the effectiveness of existing methods like RHCR to prove near optimality and can be used to propose new methods like GD-RHCR that integrates this new observability structure. 3 Motivation: Natural Extension to RHCR Figure 1: k agents with goal locations GiG_i on the right. Arrows depict timestep of first movement. To motivate our method, we begin by introducing an abstracted version of RHCR. To stay consistent with traditional MDP notation, we will use H to refer to the planning horizon and α will refer to the replanning period. RHCR: Assume a one-shot solver SOLVER(sources, destinations, H) that produces a H step collision-free path for all agents and as H→∞H→∞, the path moves all agents from their sources to destinations. The RHCR framework proposes to run SOLVER for some α≤Hα≤ H timesteps before recomputing and repeating. That is, at each t=kαt=kα, RHCR will run SOLVER(positions[kα],remaining_destinations[kα],H)SOLVER(positions[kα],remaining\_destinations[kα],H) and that path will be taken for t′∈[kα,kα+α)t ∈[kα,kα+α). In this paper, we seek to mitigate the computational requirements of repeatedly using SOLVERSOLVER in RHCR by running SOLVERSOLVER on groups of agents in parallel. Our observation is that we can view RHCR as temporally ignoring agent interactions beyond some time horizon H to reduce computation time. Therefore, if we want to achieve parallelization, a natural idea is also to ignore interactions but now based on spatial distance (e.g. with some threshold V) – this way, the planning can be broken up into parallel groups where inter-group interactions have been intentionally ignored. The question is then, (*) what is the “correct way” to ignore interactions based on distance to achieve parallelization without sacrificing the performance of RHCR? Failure of Naive Decentralization: Naively, it appears that the conventional fully decentralized method, where all agents are computed independently in parallel using the information within visibility V of the agents (without communication), would be the answer to the question. However, in fig. 1, we show a counter example. Notice that a centralized scheme could move the agents to their goals in k steps but for a decentralized scheme it would take at least 2k2k timesteps because agents cannot move before the agent in front has moved (at least k iterations for agent k to move its first step). Therefore, increasing V for the independent decentralized setting is clearly not analogous to increasing the time horizon H in SOLVERSOLVER, which would approach the optimal solution as H→∞H→∞. Group Decentralized Setting: Fortunately, it turns out that L-MAPF problem can be modeled as a recently proposed Locally Independent Multi-Agent MDP (LI-MDP) model (DeWeese and Qu 2024), which also presents a theoretically grounded method to divide the agents into parallel groups without sacrificing much performance. The main solution concept is the group decentralized setting. Definition 3.1 (group decentralization). Given visibility radius V and a distance metric, for agents N treated as vertices, create a graph there is an edge between two agents if they are within distance V. We define groups as the connected components of the graph. Each group is planned independently. Notice this resolves the issues faced in fig. 1. See fig. 2 for a visual of a group decentralization partitioning. In section 4, we will formally formulate L-MAPF as a discounted LI-MDP problem and provide a theoretical guarantee for RHCR. Then, we propose our full extension to the RHCR framework that uses this group decentralized setting (GD-RHCR) in section 5, then formally prove this new framework non-trivially satisfies a similar guarantee to RHCR in section 6. We show the performance of this method in practice in section 7. Figure 2: Group decentralized partitioning for =2V=2. Groups are connected by lines and color coded (colors are reused). 4 Theory: LI-MDP Analysis of RHCR In this section we will set up the L-MAPF as a discounted reward LI-MDP model. RHCR when viewed in a LI-MDP environment will turn out to be a near optimal method. Conventional L-MAPF Model: n agents are placed in a grid environment with open spaces X. At each step every agent i may use movements =UP,DOWN,LEFT,RIGHT,STAYD=\UP,DOWN,LEFT,RIGHT,STAY\ to transition from xiprev∈x_i^prev to the same or an adjacent space xi∈x_i if no other agent moves to the space at the same time xi≠xj∀j∈x_i≠ x_j∀ j (vertex collision) and agents do not interchange locations ¬(xiprev=xj∧xjprev=xi),∀j∈ (x_i^prev=x_j x_j^prev=x_i),∀ j (edge collision). Each agent i is assigned a list of goal locations gi1,gi2,…g_i^1,g_i^2,… to be navigated to in sequence and the metric of evaluation is number of goals achieved per unit time referred to as the throughput. L-MAPF as Multi-Agent MDP: To model the L-MAPF problem an MDP with n agents, we will assume the state space for every agent i is i=×D×GS_i=X× D× G where D is interpretted as the direction the agent came from and G⊂G is a set of goal states. This creates the joint state =1×2…×nS=S_1×S_2…×S_n. The action space for every agent i will be the standard MAPF grid movements i=A_i=D with joint action space =1×2,…nA=A_1×A_2,…A_n. The transition function will transition an agent i’s state (xi,di,gi)(x_i,d_i,g_i) deterministically with action aia_i by updating xix_i based on the action taken and adjacent positions in X, update did_i with the direction of their previous locations, and set a new goal whenever xi=gix_i=g_i (keeping the same gig_i otherwise). If the spaces are blocked by obstacles, they will remain in their current positions. Lastly, the reward function will be the sum of a positive reward rgoal>0r_goal>0 for every agent i at their goal (gi=xig_i=x_i) and negative reward (penalty) pcollide<0p_collide<0 for every agent i involved in a vertex or edge collision. That is r((x,d,g),a)=∑i(I[xi=gi]rgoal+∑jI[collision(xi,xj)]pcollide)r((x,d,g),a)= _i (I[x_i=g_i]r_goal+ _jI[collision(x_i,x_j)]p_collide ). Here collisioncollision refers to any vertex or edge collisions where xjprevx_j^prev is inferred from the current positions x and the directions they came from d. We will assume |pcollide| p_collide is much larger than |rgoal| r_goal . Without loss of generality, we will also assume |r|≤1 r ≤ 1 for bounded reward. Our metric for evaluation will be Vπ(s)=τ∼π|s[∑tγtr(s(t),a(t))]V^π(s)=E_τ π _s[ _tγ^tr(s(t),a(t))] where γ∈(0,1)γ∈(0,1) and the trajectory τ∼π|sτ π _s is the trajectory (s(t),a(t))(s(t),a(t)) starting at s(0)=s(0)=s taking the policy π:→Δ()π:S→ (A) at each timestep. This discounted model is helpful for the lifelong setting as the sum of rgoalr_goal terms may diverge as t→∞t→∞ but the discounted rewards will remain finite. For analysis purposes, for a finite horizon policy πfinite(s)=π0,π1,…,πH−1 _finite(s)=\ _0, _1,…, _H-1\ we will define the finite horizon value function Vhπfinite(s)=τ∼πfinite|s[∑t=hH−1γt−hr(s(t),a(t))].V_h _finite(s)=E_τ _finite _s[ _t=h^H-1γ^t-hr(s(t),a(t))]. Denote π∗π^* as the optimal stationary infinite horizon policy and the optimal discounted finite horizon policy for horizon H as πfinite∗=π0∗,π1∗,…,πH∗ _finite^*=\π^*_0,π^*_1,…,π^*_H\. We will denote V∗(s)=Vπ∗(s)V^*(s)=V^π^*(s) and Vh∗(s)=Vhπfinite∗(s)V_h^*(s)=V^π^*_finite_h(s). L-MAPF as LI-MDP: It turns out that these assumptions made on the multi-agent MDP fit into the LI-MDP model (DeWeese and Qu 2024) except for a minor discrepancy with edge collisions. Agents move independently in a space with a distance metric (shortest path) and move at most 1 space at a time with local rewards and penalties for interactions. See appendix A for a formal introduction to the LI-MDP and how this model is a near special case of LI-MDP. Modeling the MAPF problem as a LI-MDP has two consequences (1) leveraging techniques from the LI-MDP theory, we prove a near optimality guarantee for RHCR below (2) LI-MDP theory also suggests a near optimal group decentralized policy structure (see Definition 3.1), which motivates our GD-RHCR framework. Near Optimality of RHCR: Under this model, if we assume that SOLVERSOLVER outputs a trajectory τsSOLVERτ^SOLVER_s is ϵε-near optimal V0∗−τsSOLVER[∑tγtr(s(t),a(t))]≤ϵV^*_0-E_τ^SOLVER_s[ _tγ^tr(s(t),a(t))]≤ε then, Theorem 4.1. Let τsRHCRτ^RHCR_s denote the trajectory generated by RHCR with planning horizon H and replan window α∈[1,H]α∈[1,H] starting at the state s. Let VRHCR(s)V^RHCR(s) the corresponding sum of discounted rewards for τsRHCRτ^RHCR_s. Then, the following result holds: V∗(s)−VRHCR(s)≤2γH(1−γ)2+ϵ1−γV^*(s)-V^RHCR(s)≤ 2γ^H(1-γ)^2+ ε1-γ Aside from the error from the ϵε-optimality of SOLVERSOLVER, we can see that the suboptimality decreases exponentially fast with the increase in H. Also, perhaps counterintuitively, we see that the guarantee is independent of the replan window α establishing a theoretical justification for using a replan window to improve on computation time from (Li et al. 2021). Note however, that a smaller α can be still be useful in practice to reduce V∗(s)−VRHCR(s)V^*(s)-V^RHCR(s) within [0,2γH(1−γ)2+ϵ1−γ][0, 2γ^H(1-γ)^2+ ε1-γ]. Why group decentralized? It is shown in DeWeese and Qu 2024 that group decentralized policies can also satisfy these type of near optimality bounds, so we expect a group decentralized version of RHCR (algorithm 1) to satisfy a similar guarantee (see section 6). The primary intuition will be that agents within different groups theoretically cannot collide within ⌊2⌋ V2 steps (see lemma B.1). This means that agents in different groups can safely be “ignored” in the computation when considering a finite horizon. This will also be the explanation to why the group decentralized scheme is the answer to question (*) posed in section 3. After introducing our algorithm in the following section, we show in section 6 the theoretical results for our group decentralized method. Algorithm 1 GD-RHCR 1: λi←∅ _i← for each agent i∈i 2: for t=0,1,2,…t=0,1,2,… do 3: ←Connected Components(,)G← Connected Components(N,V) 4: λ¯←λ:=(λi)i∈ λ←λ:=( _i)_i // snapshot end-of-previous-step plans 5: for all groups g∈g in parallel do 6: if |g|≥Kth|g|≥ K_th then 7: P←Solver2(g)P← Solver2(g) // early termination 8: λi←P _i← P for all i∈gi∈ g 9: else if t=0t=0 or ∃i,j∈g:λi,λj∃\,i,j∈ g:\ _i, _j not from same solve or (λi)i∈g( _i)_i∈ g exhausted then 10: C←SoftConstraints(λ¯k:k∉g,csoft)C← SoftConstraints(\ λ_k:k∉ g\,\ c_soft) 11: P←Solver(g,H,C,τ)P← Solver(g,\ H,\ C,\ τ) // lazy recompute 12: if P=NULLP=NULL then 13: P←SOLVER2(g)P← SOLVER2(g) // solver timeout 14: end if 15: λi←P _i← P for all i∈gi∈ g 16: else 17: continue // all agents agree: reuse cached plan 18: end if 19: end for 20: advance each i∈i one step along λi _i 21: end for 5 Our Method: Group Decentralized RHCR Our algorithm will consist of four components and is summarized in algorithm 1. Firstly, we will identify the groups from the group decentralized scheme described earlier. Secondly, our algorithm will have a “as needed” lazy evaluation scheme which will dynamically adjust the reevaluation window α for groups of agents. Next, to improve the accuracy of our parallel computation across groups, we will add soft constraints for out of view agents in other groups in our lower level planner. Lastly, the algorithm will include a fast secondary solver to rapidly solve large congestion groups. Group Decentralized: We begin by identifying the partitions in the group decentralized setting by identifying the connected components as in definition 3.1. This is performed at each timestep shown in line 3 of the algorithm. In practice, we use the shortest path distance and the union find data structure to hold the connected components. The shortest path will become longer near obstacles, allowing us to take advantage of map topology (such as warehouse-10-20-2-1 in section 7). Agents remain sparser and the grouping scheme is more likely to break apart into smaller groups. warehouse-10-20-10-2-1 warehouse-10-20-10-2-2 sortation-1 sortation-2 package throughput plan runtime [s] agents Figure 3: MAPD simulations. Agents move between red stars and blue squares. Color coding is GD-RHCR, RHCR, and PIBT Lazy Evaluation: Now that the groups have been identified, we will now decide which groups will require computation. At the first timestep of the algorithm, we will run SOLVERSOLVER with some horizon H on every identified group in parallel (line 11). Agents are given a reference to the finite horizon “plan” (λi)i∈g( _i)_i∈ g computed for their group and move according to their plan. Then, at every subsequent timestep, if all of the agents in a group have references to the same solution, then the agents will act according to the referenced “plan” (line 17). On the other hand, if the agents in the group disagree about the plan, the agents will recompute a new plan which all the agents will now reference (again line 11). Intuitively, this triggers when a new agent unaccounted for in the plan has just joined the group. Notice this lazy evaluation scheme can be interpereted as dynamically deciding on a replan window α for different subsets of agents. This can improve the the longevity of our often cheap parallel computations made across groups and staggers the evaluations which significantly reduces the per iteration computational load compared to RHCR. Soft Constraints: When planning for a group, we will take the plans of all of the agents not within our group at the end of the previous timestep (line 4) and any collision with those plans caused during our compute in SOLVERSOLVER will introduce a cost csoftc_soft, applied to the lower level search (line 10). For example, our simulations we will use PBS with an efficient space-time A* implementation, SIPP, as the lower level planner, and a soft penalty csoftc_soft is applied to the lower level SIPP search every time the constraint is violated. Plans from the previous timestep are used because the parallel computation across groups must begin computation before plans for other groups are settled. However, the staleness of those trajectories is mitigated with lazy evaluation, since not all groups are planning at the same time. Therefore, only the plans of a subset of agents which are planning are stale at any given time. It is important that csoftc_soft remains relatively small as a large cost can increase the computation time of the lower level planner (e.g. SIPP) that is called frequently (see our ablation simulation in appendix B.3). In fact, if we use hard constraints (csoft=∞c_soft=∞), we may have no solution as this would effectively give all agents in other groups higher priority than agents we are planning for. Secondary Solver: Since the large computation time for RHCR can often be caused by a small number of congested regions, we may use our group decentralized mechanism to use different algorithms in different locations. For our algorithm, if the group size reaches some threshold KthresholdK_threshold, we will immediately use a fast secondary solver SOLVER2SOLVER2 (in our case PIBT) to avoid those expensive computations (line 7). This allows for the use of our primary SOLVERSOLVER for routing other groups while a faster secondary solver like PIBT is used to decongest large groups. This will also have the counterintuitive but highly desirable property that when KthresholdK_threshold is hit more and uses SOLVER2SOLVER2 (e.g. highly congested problems), the algorithm will speed up. This is in contrast to RHCR which will run SOLVERSOLVER all the way to timeout every time it fails to find a solution quickly enough before relying on a secondary solver. Therefore GD-RHCR leverages the “fallback” as a part of the algorithm rather than a “failure” of the method as in RHCR. Flexible choice of solvers. Our framework allows flexible choice of potentially heterogeneous solvers for different groups, exploiting heterogeneous structures of the groups. Although for this work, our specific implementation uses a specific (SOLVERSOLVER, SOLVER2SOLVER2) pair that mirrors a fallback mechanism similar to RHCR across different groups. In general, this group decentralization sets up a modular framework where different solvers can easily be used for different groups of agents. We believe this will open the door to many variations and new research directions. 6 Theory: Near Optimality of GD-RHCR For the theoretical results, we will again consider the L-MAPF problem modeled as a discounted MDP as described in section 4. We will also consider a simplified version of the algorithm where Kthreshold=∞K_threshold=∞ so the secondary solver is not used and the soft constraint cost csoft=0c_soft=0 to simplify the analysis. In practice csoftc_soft will be small and incorporating estimations of out of view often does not change the overall theoretical guarantee (DeWeese and Qu 2025). Again assuming that SOLVERSOLVER outputs an ϵε-optimal finite horizon policy, we have the following theorem. Theorem 6.1. Let τsGDτ^GD_s denote the trajectory generated by GD-RHCR with csoft=0c_soft=0, Kthreshold=∞K_threshold=∞, and horizon H starting at the state s. Let VGD(s)V^GD(s) be the corresponding sum of discounted rewards (taking expectation over τsGDτ^GD_s). Then, the following result holds: V∗(s)−VGD(s)≤6γmin(⌊/2⌋+1,H)(1−γ)2+ϵ1−γV^*(s)-V^GD(s)≤ 6γ ( /2 +1,H)(1-γ)^2+ ε1-γ Notice that the exponent min(⌊/2⌋+1,H) ( /2 +1,H) captures the duality between the space restriction and time restriction. With the group decentralized scheme (and csoft=0c_soft=0), we will be ignoring agents beyond distance V from any agent in the group. Notice that by the Dependence Time Lemma in lemma B.1, agents in different groups are not able to collide within ⌊/2⌋ /2 timesteps, so if H=⌊/2⌋+1H= /2 +1 computing according to parallel groups will have no consequence on the solution and improves the computation time for free. In practice, V and H may not be aligned so the theoretical guarantee depends on the minimum of the two. Overall, in the same way that the replan window α in RHCR can be motivated through theoretical justification (see section 4), the theory also motivates this group decentralized parallelization scheme as well as the lazy evaluation scheme. 7 Simulations Algorithm 1 is simulate across in different maps and settings. We will plot the behavior between PIBT, RHCR with PIBT fallback, and GD-RHCR with PIBT as SOLVER2SOLVER2. Average Plan Time Metric: There will be important nuance with the computational runtime graphs, where we will compare the average planning time and assume perfect parallelism. That is, for GD-RHCR we will plot the average maximum time to complete the parallel groups across that timestep (only a subset of groups will be computing at each timestep). For RHCR and PIBT, the average planning time is just the average of the planning times whenever it plans (RHCR only plans every 1/α1/α iterations). For RHCR, this is a useful metric when there is a uniform computation limit across all timesteps such as in applications with physical robots and move times. However, this metric may not capture this reduced number of overall computations (reduced by 1/α1/α). In appendix C, total wall times are provided which incorporate the imperfect parallelism as well as the reduced frequency of RHCR evaluations. Our method still demonstrates a improvement in this case as well. Maps: We will consider the Multi-Agent Pickup Delivery (MAPD) setting with 4 maps in fig. 3 where agents move from random pickup and dropoff locations. The sortation-1 and sortation-2 maps are inspired by (Li et al. 2021). We also consider the random navigation L-MAPF setting where agents are assigned goals to random open spaces with 6 maps in fig. 4. We introduce three more custom maps room-32-32-var1, room-64-64-var1, room-64-64-var2 which are variations on the traditional room maps (room-32-32-4 and room-64-64-8) with uniform openings between the rooms (see fig. 4). This is because the specifically placed openings between the rooms in the traditional room maps make it more “maze like” and suitable for traditional MAPF rather than testing the topology of the room structure in L-MAPF. Parameters: All RHCR simulations are run with PBS as the main solver with PIBT fallback and α=5α=5,H=20H=20. Simulations for GD-RHCR will primarily use csoft=1c_soft=1, H=20H=20, =2V=2 and a threshold that depends on the agent count Kthresh=min(⌊0.1k⌋,20)K_thresh= ( 0.1k ,20) (sortation-2 uses Kthresh=min(⌊0.1k⌋,50)K_thresh= ( 0.1k ,50)). We use 30 seeds with 3 in parallel for 500 timesteps on a 13th Gen Intel(R) Core(TM) i9-13900HX. Plotted is the average with 1-SD bands. 7.1 Results The outcomes of our MAPD simulations are shown in fig. 3 and random navigation simulations in fig. 4. See appendix B.3 and D for abalations and group statistics respectively. random-64-64-20 room-64-64-var1 room-64-64-var2 random-32-32-20 room-32-32-var1 empty-48-48 throughput plan runtime [s] agents Figure 4: Random navigation simulations. The color coding is GD-RHCR, RHCR, and PIBT Near RCHR Throughput of GD-RHCR with Reduced Compute Cost. For a wide variety of maps (warehouse-10-20-10-2-1, warehouse-10-20-10-2-2, sortation-1, random-64-64-20, room-64-64-var1, room-64-64-var2), GD-RHCR is able to maintain near RHCR performance before RHCR collapses. For example in warehouse-10-20-10-2-1, the throughput of GD-RHCR stays within ≈2%≈ 2\% with an average of 24.924.9x improvement in plan time over RHCR before collapse. Although the visibility remains =2V=2, the soft constraints contributes significantly to incorporate global agent information across groups (see section B.3). Further, we see that this is done at a significantly lower per-plan cost over RHCR. The staggered lazy evaluations of GD-RHCR significantly reduces the plan time required at each step because not all agents are planning simultaneously. Further, the paralellism substantially reduces the planning time for the agents that do evaluate at the same time. GD-RHCR Extends the Range of RHCR Because GD-RHCR restricts to planning for small groups (based on KthresholdK_threshold), it is able to retain the planning leverage much further than RHCR. Even if challenging large congestion regions form, GD-RHCR will immediately use PIBT for those groups and continue to plan for the other smaller groups. This means that the throughput can remain higher and results in a much more graceful return to the PIBT as a fallback planner. We see the most dramatic improvement in throughput on the warehouse-10-20-10-2-1 map. At its peak at k=800k=800, GD-RHCR sees a +57.7% improvement over collapsed RHCR / PIBT while retaining its low per plan cost. Even at k=1000k=1000, there are an average of approximately 250 groups that remain separated (see appendix D for full graphs). For warehouse-10-20-10-2-2 and sortation-1, we see an improvement of 12.6%12.6\% and 9.66%9.66\% respectively at k=1000k=1000. Topology Influences Performance Overall, the topology of the map can substantially influence the performance of the algorithms. In maps such as warehouse-10-20-10-2-1 where the obstacles are dense and the shortest path (which wraps around obstacles) and Manhattan distance (which goes through obstacles) differ significantly, the topology induces smaller groups that allow for a significant advantage through the parallelism and group decentralized planning. However, the advantage of GD-RHCR over the two methods is not as large when the maps are small (random-32-32-20 and room-32-32-var1) or less obstacle dense maps (sortation-2 and empty-48-48). In both cases, the topology induces large groups which must be planned all at once or drops through to the PIBT fallback when KthresholdK_threshold is reached. Further, random-32-32-20, and room-32-32-var1 are not biconnected and can cause deadlocking in PIBT. Therefore for GD-RHCR that begins to rely on PIBT before RHCR can cause a reduced performance. However, we do see that computationally, GD-RHCR hits KthresholdK_threshold early and actually speeds up with more agents. We also see in empty-48-48 that trivially all methods have similar throughput because RHCR itself does not have a significant advantage. However, the computation time of GD-RHCR is near PIBT because the large groups immediately transition to PIBT. 8 Conclusion and Future Work In this work, we provided a theoretical grounding for RHCR using methods from the LI-MDP literature. We then used those analytical techniques to motivate our new GD-RHCR framework that satisfies similar theoretical guarantees to RHCR and performs well empirically across many maps into larger agent counts over RHCR. For future works, we believe that group decentralization is a relatively new concept to the MAPF community and can be integrated in various ways. For example with traditional learning based methods or performing parallelism for other methods such as PIBT. Further, this work creates a simple setup to use different algoriths in different locations / settings which opens up many research directions. 9 Acknowledgements Guannan Qu is supported by NSF Grants 2339112, 2512805, Jane Street, and Pennsylvania Infrastructure Technology Alliance. Jiaoyang Li is supported by NSF Grants 2328671 and 2441629. In addition, Alex DeWeese is supported by Leo Finzi Memorial Fellowship in Electrical & Computer Engineering, the David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship, and the Fritsch Family Fellowship. References Arita and Okumura (2026) Arita, T.; and Okumura, K. 2026. Lifelong LaCAM with Local Guidance for Lifelong MAPF. arXiv preprint arXiv:2605.16855. Barer et al. (2014) Barer, M.; Sharon, G.; Stern, R.; and Felner, A. 2014. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In Proceedings of the international symposium on combinatorial Search, volume 5, 19–27. Chen et al. (2024) Chen, Z.; Harabor, D.; Li, J.; and Stuckey, P. J. 2024. Traffic flow optimisation for lifelong multi-agent path finding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 20674–20682. Damani et al. (2021) Damani, M.; Luo, Z.; Wenzel, E.; and Sartoretti, G. 2021. PRIMAL _2\_2: Pathfinding via reinforcement and imitation multi-agent learning-lifelong. IEEE Robotics and Automation Letters, 6(2): 2666–2673. DeWeese and Qu (2024) DeWeese, A.; and Qu, G. 2024. Locally interdependent multi-agent mdp: Theoretical framework for decentralized agents with dynamic dependencies. arXiv preprint arXiv:2406.06823. DeWeese and Qu (2025) DeWeese, A.; and Qu, G. 2025. Thinking Beyond Visibility: A Near-Optimal Policy Framework for Locally Interdependent Multi-Agent MDPs. arXiv preprint arXiv:2506.04215. Erdmann and Lozano-Perez (1987) Erdmann, M.; and Lozano-Perez, T. 1987. On multiple moving objects. Algorithmica, 2(1): 477–521. Ho et al. (2019) Ho, F.; Goncalves, A.; Salta, A.; Cavazza, M.; Geraldes, R.; and Prendinger, H. 2019. Multi-agent path finding for UAV traffic management: Robotics track. Jiang et al. (2025) Jiang, H.; Wang, Y.; Veerapaneni, R.; Duhan, T.; Sartoretti, G.; and Li, J. 2025. Deploying ten thousand robots: Scalable imitation learning for lifelong multi-agent path finding. In 2025 IEEE International Conference on Robotics and Automation (ICRA), 1–7. IEEE. Leet, Li, and Koenig (2022) Leet, C.; Li, J.; and Koenig, S. 2022. Shard systems: Scalable, robust and persistent multi-agent path finding with performance guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, 9386–9395. Li et al. (2019) Li, J.; Gong, M.; Liang, Z.; Liu, W.; Tong, Z.; Yi, L.; Morris, R.; Pasearanu, C.; and Koenig, S. 2019. Departure scheduling and taxiway path planning under uncertainty. In AIAA Aviation 2019 Forum, 2930. Li, Ruml, and Koenig (2021) Li, J.; Ruml, W.; and Koenig, S. 2021. Eecbs: A bounded-suboptimal search for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, volume 35, 12353–12362. Li et al. (2020) Li, J.; Sun, K.; Ma, H.; Felner, A.; Kumar, T.; and Koenig, S. 2020. Moving agents in formation in congested environments. In Proceedings of the International Symposium on Combinatorial Search, volume 11, 131–132. Li et al. (2021) Li, J.; Tinka, A.; Kiesel, S.; Durham, J. W.; Kumar, T. S.; and Koenig, S. 2021. Lifelong multi-agent path finding in large-scale warehouses. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 11272–11281. Ma et al. (2019) Ma, H.; Harabor, D.; Stuckey, P. J.; Li, J.; and Koenig, S. 2019. Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, volume 33, 7643–7650. Ma et al. (2017) Ma, H.; Li, J.; Kumar, T.; and Koenig, S. 2017. Lifelong multi-agent path finding for online pickup and delivery tasks. arXiv preprint arXiv:1705.10868. Morag, Stern, and Felner (2023) Morag, J.; Stern, R.; and Felner, A. 2023. Adapting to planning failures in lifelong multi-agent path finding. In Proceedings of the International Symposium on Combinatorial Search, volume 16, 47–55. Okoso, Otaki, and Nishi (2019) Okoso, A.; Otaki, K.; and Nishi, T. 2019. Multi-agent path finding with priority for cooperative automated valet parking. In 2019 IEEE intelligent transportation systems conference (ITSC), 2135–2140. IEEE. Okumura (2023a) Okumura, K. 2023a. Improving lacam for scalable eventually optimal multi-agent pathfinding. arXiv preprint arXiv:2305.03632. Okumura (2023b) Okumura, K. 2023b. Lacam: Search-based algorithm for quick multi-agent pathfinding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 11655–11662. Okumura et al. (2022) Okumura, K.; Machida, M.; Défago, X.; and Tamura, Y. 2022. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence, 310: 103752. Okumura, Tamura, and Défago (2019) Okumura, K.; Tamura, Y.; and Défago, X. 2019. winpibt: Extended prioritized algorithm for iterative multi-agent path finding. arXiv preprint arXiv:1905.10149. Sartoretti et al. (2019) Sartoretti, G.; Kerr, J.; Shi, Y.; Wagner, G.; Kumar, T. S.; Koenig, S.; and Choset, H. 2019. Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics and Automation Letters, 4(3): 2378–2385. Sharon et al. (2015) Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219: 40–66. Veerapaneni et al. (2025) Veerapaneni, R.; Saleem, M. S.; Li, J.; and Likhachev, M. 2025. Windowed MAPF with completeness guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, 23323–23332. Yu and LaValle (2013) Yu, J.; and LaValle, S. 2013. Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 27, 1443–1449. Zhang et al. (2026) Zhang, T.; Veerapaneni, R.; Chan, S.-H.; Li, J.; and Likhachev, M. 2026. Dynamic agent grouping ecbs: Scaling windowed multi-agent path finding with completeness guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, 29911–29920. Appendix A MAPF as LI-MDP Below, we give the formal definition of the Locally Interdependent Multi-Agent MDP (LI-MDP) and demonstrate how our MAPF MDP model from section 4 fits into this model. Assume we have agent N with some metric space X with a corresponding distance metric d. Each agent i may each also have an internal state iY_i (e.g. battery power) resulting in a state space of i=(,i)S_i=(X,Y_i) with an arbitrary action space of iA_i. Each agent i will transition independently in the environment according to a individual transition function Pi(si′|si,ai)P_i(s _i s_i,a_i) with si,si′∈is_i,s_i _i, ai∈ia_i _i however, we assert that this probability is 0 when d(si,si′)>1d(s_i,s_i )>1 (agents cannot move more than 1 space at a time in the environment). Lastly, for any two agents i,j∈i,j we will assume a local reward function r¯i,j(si,ai,sj,aj) r_i,j(s_i,a_i,s_j,a_j) which is 0 when d(si,sj)>ℛd(s_i,s_j)>R according to a dependence radius ℛ≥0R≥ 0. Here, i,ji,j can be equal in which case r¯i,i(si,ai,si,ai) r_i,i(s_i,a_i,s_i,a_i) represents the “single agent reward” which depends only on a single agent state / action (the agent will always be within distance ℛR of itself so the restriction does not apply). Therefore the reward function decomposes into ∑i,j∈gr¯i,j(si,ai,sj,aj)=∑i∈r¯i(si,ai)+∑i≠jr¯i,j(si,ai,sj,aj) _i,j∈ g r_i,j(s_i,a_i,s_j,a_j)= _i r_i(s_i,a_i)+ _i≠ j r_i,j(s_i,a_i,s_j,a_j) where r¯i(si,ai)=r¯i,i(si,ai,si,ai) r_i(s_i,a_i)= r_i,i(s_i,a_i,s_i,a_i). To summarize, we have the following: Definition A.1. Assume the definition of the components mentioned above. The LI-MDP is defined as: • :=×i∈iS:=×_i S_i where i=(,i)S_i=(X,Y_i) • :=×i∈iA:=×_i A_i • P(s′|s,a)=∏i∈Pi(si′|si,ai)P(s s,a)= _i P_i(s _i s_i,a_i) • r(s,a)=∑i∈r¯i(si,ai)+∑i≠jr¯i,j(si,ai,sj,aj)r(s,a)= _i r_i(s_i,a_i)+ _i≠ j r_i,j(s_i,a_i,s_j,a_j) Notice the similarities with the MAPF MDP formulation described in section 4. Each agent moves in an environment with a metric space at most one space at a time individually. The agents have a single agent goal incentive captured by r¯i(si,ai) r_i(s_i,a_i) and a interdependent collision penalty when agents have vertex collisions captured by r¯i,j(si,ai,sj,aj) r_i,j(s_i,a_i,s_j,a_j) with ℛ=0R=0. The only discrepancy is the edge collisions which allow for collision penalties with agents 1 step away (which we want to handle with ℛ=0R=0). It turns out that this does not impact the theory as a critical lemma called the Dependence Time Lemma (lemma B.1) still holds. Appendix B Proofs B.1 RHCR If πfinite(s)=π0,π1,…,πH−1 _finite(s)=\ _0, _1,…, _H-1\ is a finite horizon policy, let Vhπfinite(s)=τ∼πfinite|s[∑t=hH−1γt−hr(st,at)]V_h _finite(s)=E_τ _finite _s[ _t=h^H-1γ^t-hr(s_t,a_t)]. Assume πfinite∗(s)=π0∗,π1∗,…,πH−1∗π^*_finite(s)=\ _0^*, _1^*,…, _H-1^*\ is the finite horizon optimal policy calculated by RHCR at each replan window α. Recall, RHCR repeatedly takes the finite horizon policy only up to a certain number of timesteps α. So, to express the discounted sum of rewards (the value function) of RHCR, we can repeatedly take the discounted rewards in the value function V0πfinite∗(st)V^π^*_finite_0(s_t) up to timesteps α and subtract the discounted value function beyond timestep α. This takes the form as follows VRHCR(s)=τ∼π|s[V0πfinite∗(s)−∑ℓ=1∞γαℓΔℓτ]V^RHCR(s)=E_τ π _s [V^π^*_finite_0(s)- _ =1^∞γ^α _ ^τ ] where Δℓτ=Vαπfinite∗(s(αℓ))−V0πfinite∗(s(αℓ)) _ ^τ=V^π^*_finite_α(s(α ))-V^π^*_finite_0(s(α )). Now, we would like to bound Δℓτ _ ^τ. However, notice the value function terms within Δℓτ _ ^τ contain discounted rewards that consider different time intervals. Vαπfinite∗(s(ℓα))=τ∼πfinite∗|s[∑t=αH−1γt−αr(s(t),a(t))]V^π^*_finite_α(s( α))=E_τ _finite^* _s[ _t=α^H-1γ^t-αr(s(t),a(t))] only considers H−αH-α timesteps and V0πfinite∗(sαℓ)=τ∼πfinite∗|s[∑t=0H−1γtr(s(t),a(t))]V^π^*_finite_0(s_α )=E_τ _finite^* _s[ _t=0^H-1γ^tr(s(t),a(t))] considers H timesteps. We will take an arbitrary finite horizon policy πfinite _finite and complete the trajectory within Vαπfinite∗(s(α(ℓ−1)))V^π^*_finite_α(s(α( -1))). The extended value function Vℓ,extendedV ,extended can be expressed as follows. Vℓ,extended=τ∼πfinite∗|s[∑t=αH−1γt−αr(st,at)] V ,extended=E_τ _finite^* _s [ _t=α^H-1γ^t-αr(s_t,a_t) ] +τ∼πfinite|s[∑t=H+α−1γt−αr(s(t),a(t))] 107.63855pt+E_τ _finite _s [ _t=H^H+α-1γ^t-αr(s(t),a(t)) ] =Vαπfinite∗(s(α(ℓ−1)))+τ∼πfinite|s[∑t=H+α−1γt−αr(st,at)] =V^π^*_finite_α(s(α( -1)))+E_τ _finite _s [ _t=H^H+α-1γ^t-αr(s_t,a_t) ] ≥Vαπfinite∗(s(α(ℓ−1)))−γH−α(1−γα1−γ) ≥ V^π^*_finite_α(s(α( -1)))-γ^H-α( 1-γ^α1-γ) ≥Vαπfinite∗(s(α(ℓ−1)))−γH−α1−γ ≥ V^π^*_finite_α(s(α( -1)))- γ^H-α1-γ Now, since V0πfinite∗(s(αℓ))V^π^*_finite_0(s(α )) is the optimal finite horizon reward, we may bound Δiτ _i^τ as follows: Δℓτ ^τ_ =Vαπfinite∗(s(αℓ))−V0πfinite∗(s(αℓ)) =V^π^*_finite_α(s(α ))-V^π^*_finite_0(s(α )) ≤Vℓ,extended−V0πfinite∗(s(αℓ))+γH−α1−γ ≤ V ,extended-V_0^π^*_finite(s(α ))+ γ^H-α1-γ ≤ϵ+γH−α1−γ ≤ε+ γ^H-α1-γ Therefore, VRHCR(s) V^RHCR(s) =τ∼π|s[V0πfinite∗(s)−∑ℓ=1∞γαℓΔℓτ] =E_τ π _s [V^π^*_finite_0(s)- _ =1^∞γ^α _ ^τ ] ≥V0πfinite∗(s)−γH(1−γ)2−ϵ1−γ ≥ V^π^*_finite_0(s)- γ^H(1-γ)^2- ε1-γ To complete our analysis, we may compare the optimal stationary policy π∗π^* and the RHCR trajectory as follows: V∗(s)−VRHCR(s) V^*(s)-V^RHCR(s) ≤V∗(s)−V0πfinite∗(s) ≤ V^*(s)-V_0^π^*_finite(s) +γH(1−γ)2+ϵ1−γ 43.05542pt+ γ^H(1-γ)^2+ ε1-γ ≤γH1−γ+γH(1−γ)2+ϵ1−γ ≤ γ^H1-γ+ γ^H(1-γ)^2+ ε1-γ ≤2γH(1−γ)2+ϵ1−γ ≤ 2γ^H(1-γ)^2+ ε1-γ B.2 Group Decentralized RHCR In this section, we will prove theorem 6.1. Recall, we will be using csoft=0c_soft=0 and Kthreshold=∞K_threshold=∞. Let Z(s)=z1,z2,…,zℓZ(s)=\z_1,z_2,…,z_ \ where zi⊂z_i be the partition formed by the transitive “grouped decentralized” connections. Similar to (DeWeese and Qu 2024), our proofs will rely on a fundamental geometric property that agents in separate groups cannot interact with each other within a certain number of steps. In the MAPF case, this means agents will not be able to collide within c=⌊2⌋c= V2 timesteps. This is a special case of the Dependence Time Lemma from (DeWeese and Qu 2024) with ℛ=0R=0 which shows up in c=⌊−ℛ2⌋c= V-R2 with the exception of edge collisions. Lemma B.1 (Dependence Time Lemma for MAPF). For some state s∈s , let i,j∈i,j be any two agents in different partitions in Z(s)Z(s). Then, agents i,ji,j cannot have vertex or edge collisions within ⌊2⌋ V2 timesteps. Proof. See proof for the Dependence Time Lemma in (DeWeese and Qu 2024) with ℛ=0R=0. Edge collisions do not make a difference in the proof because showing that the closest two agents in different groups can get is distance 1 in ⌊2⌋ V2 steps rules out both vertex and edge collisions. Notice by our reward model in section 4, r(s,a)=∑i(I[xi=gi]rgoal+∑jI[collision(xi,xj)]pcollide)r(s,a)= _i (I[x_i=g_i]r_goal+ _jI[collision(x_i,x_j)]p_collide ), for any policy π, we may decompose the value function as follows for any partition P: Vhπ(s)=∑p∈P([Vhπ]p(sp)+∑i∈p[Vhπ]i→p¯(s)) V^π_h(s)= _p∈ P ([V_h^π]_p(s_p)+ _i∈ p[V_h^π]_i→ p(s) ) where we define p¯:=∖p p:=N p and for every p′⊂p both [Vhπ]p′(s)=[∑t=0∞γt∑i∈p′I[xi=gi]rgoal [V^π_h]_p (s)=E [ _t=0^∞γ^t _i∈ p I[x_i=g_i]r_goal +∑j∈p′I[collision(xi,xj)]pcollide] 86.11084pt+ _j∈ p I[collision(x_i,x_j)]p_collide ] and [Vhπ]i→p′(s)=[∑t=0∞γt∑j∈p′I[collision(xi,xj)]pcollide]. [V_h^π]_i→ p (s)=E [ _t=0^∞γ^t _j∈ p I[collision(x_i,x_j)]p_collide ]. Symbolically, i→p′i→ p represents the interactions of agent i (or collisions) with agents in p′p . Using these new notations, we may express the trajectory value obtained by GD-RHCR as VGD(s)≥τ∼π|s[∑z∈Z(s)[V0πfinite∗]z(s)−∑t=1∞γtΔtτ]−ϵ1−γ V^GD(s) _τ π _s [ _z∈ Z(s)[V^π^*_finite_0]_z(s)- _t=1^∞γ^t _t^τ ]- ε1-γ where Δtτ=∑z∈Z(s)I[lazy(z,t)](∑i∈z([Vδitπfinite∗]z(szt,i(t))CLOSECLOSE _t^τ= _z∈ Z(s)I[lazy(z,t)] ( _i∈ z ([V^π^*_finite_ _i^t]_z(s_z_t,i(t)) OPENOPEN+[Vδitπfinite∗]i→zt,i∖z(szt,i(t)))−[V0πfinite∗]z(s(t))) 43.05542pt+[V^π^*_finite_ _i^t]_i→ z_t,i z(s_z_t,i(t)) )-[V^π^*_finite_0]_z(s(t)) ) Here I(lazy(z,t))I(lazy(z,t)) is an indicator whether lazy evaluation was triggered at that timestep and zt,iz_t,i is the group associated with the previous "plan". Intuitively, we repeatedly remove the remainder of the trajectory when lazy evaluation is triggered and bring in the new trajectory plan for each of the groups. This accounts for the collisions across groups because in order for agents to collide, they must enter each others groups first (triggering a lazy evaluation). Next, as in section B.1, we will extend the trajectory of [Vδitπfinite∗]i(szt,i(t))[V^π^*_finite_ _i^t]_i(s_z_t,i(t)) with some arbitrary policy πi,finite _i,finite. Notice here that in our extension Vi,t,extV^i,t,ext, we will only consider collisions between agents that were initially in the same zt,iz_t,i group. Defining ri,maxr_i,max as the maximum reward possible for a single agent (we assume ∑i∈|ri,max|≤1 _i r_i,max ≤ 1), we have ∑i∈I[lazy(z,t)]Vi,t,ext=∑i∈I[lazy(z,t)](Vδitπfinite∗(szt,i(t))CLOSE _i I[lazy(z,t)]V^i,t,ext= _i I[lazy(z,t)] (V^π^*_finite_ _i^t(s_z_t,i(t)) +τ∼πi,finite|s[∑t′=H+δit−1γt′−δit(I[xi=gi]rgoal 86.11084pt+E_τ _i,finite _s [ _t =H^H+ _i^t-1γ^t - _i^t (I[x_i=g_i]r_goal +∑j∈zt,iI[collision(xi,xj)]pcollide)] 172.22168pt+ _j∈ z_t,iI[collision(x_i,x_j)]p_collide ) ] ≥∑i∈I[lazy(z,t)](Vδitπfinite∗(szt,i(t))−γH−δit(1−γδit1−γ)ri,max) ≥ _i I[lazy(z,t)] (V^π^*_finite_ _i^t(s_z_t,i(t))-γ^H- _i^t( 1-γ _i^t1-γ)r_i,max ) ≥∑i∈I[lazy(z,t)](Vδitπfinite∗(szt,i(t))−γH−δit1−γri,max) ≥ _i I[lazy(z,t)] (V^π^*_finite_ _i^t(s_z_t,i(t))- γ^H- _i^t1-γr_i,max ) Now we may bound Δtτ _t^τ as follows. γtΔtτ=γt∑z∈Z(s)I[lazy(z,t)](∑i∈z([Vδitπfinite∗]z(szt,i(t))CLOSECLOSE γ^t _t^τ=γ^t _z∈ Z(s)I[lazy(z,t)] ( _i∈ z ([V^π^*_finite_ _i^t]_z(s_z_t,i(t)) OPENOPEN+[Vδitπfinite∗]i→zt,i∖z(szt,i(t)))−[V0πfinite∗]z(s(t))) 86.11084pt+[V^π^*_finite_ _i^t]_i→ z_t,i z(s_z_t,i(t)) )-[V^π^*_finite_0]_z(s(t)) ) (1) ≤γt∑z∈Z(s(t))I[lazy(z,t)](∑i∈zVi,t,ext−[V0πfinite∗]z(s(t))CLOSE ≤γ^t _z∈ Z(s(t))I[lazy(z,t)] ( _i∈ zV^i,t,ext-[V_0^π^*_finite]_z(s(t)) OPEN∑i∈z[Vδitπfinite∗]i→zt,i∖z(szt,i(t))+∑i∈zγH−δitri,max1−γ) 107.63855pt _i∈ z[V^π^*_finite_ _i^t]_i→ z_t,i z(s_z_t,i(t))+ _i∈ z γ^H- _i^tr_i,max1-γ ) (2) ≤∑z∈Z(s)I[lazy(z,t)](γt(∑i∈zVi,t,ext−[V0πfinite∗]z(s(t)))CLOSE ≤ _z∈ Z(s)I[lazy(z,t)] (γ^t( _i∈ zV^i,t,ext-[V_0^π^*_finite]_z(s(t))) (3) +∑i∈zγ⌊2⌋+t−δit+1ri,max1−γ+γH+t−δitri,max1−γ) 129.16626pt+ _i∈ z γ V2 +t- _i^t+1r_i,max1-γ+ γ^H+t- _i^tr_i,max1-γ ) (4) ≤∑z∈Z(s)I[lazy(z,t)](∑i∈zγI[t>⌊2⌋]⋅tri,max ≤ _z∈ Z(s)I[lazy(z,t)] ( _i∈ zγ^I[t> V2 ]· tr_i,max (5) +∑i∈zγ⌊2⌋+t−δit+1ri,max1−γ+γH+t−δitri,max1−γ) 129.16626pt+ _i∈ z γ V2 +t- _i^t+1r_i,max1-γ+ γ^H+t- _i^tr_i,max1-γ ) (6) In line 2, we substitute our extension. In line 4, we use the Dependence Time Lemma (lemma B.1) where cross group interactions are beyond ⌊2⌋ V2 iterations (with a head start of δit _i^t iterations). In line 6, recall that in the definition of Vi,t,extV^i,t,ext only the collisions between agents in the same zt,iz_t,i groups were added. For cross group interactions, these may leave residual terms. However, these terms must occur beyond ⌊2⌋ V2 iterations by the Dependence Time Lemma. Therefore we introduce the quantity with the indicator in the exponent I[t>⌊2⌋]⋅tI[t> V2 ]· t. Now notice that t−δitt- _i^t is some quantity unique for every t (when the indicator I[lazy(z,t)]I[lazy(z,t)] is triggered) and therefore the t−δitt- _i^t terms can be summed up as indices of 1,…,∞1,…,∞. Therefore we have τ∼π|s[∑t=1∞γtΔtτ]≤γH(1−γ)2+2γ⌊/2⌋+1(1−γ)2 _τ π _s [ _t=1^∞γ^t _t^τ ]≤ γ^H(1-γ)^2+ 2γ /2 +1(1-γ)^2 And substituting into our VGDV^GD expression, VGD(s) V^GD(s) ≥τ∼π|s[∑z∈Z(s)[V0πfinite∗]z(s)−∑t=1∞γtΔtτ]−ϵ1−γ _τ π _s [ _z∈ Z(s)[V^π^*_finite_0]_z(s)- _t=1^∞γ^t _t^τ ]- ε1-γ ≥∑z∈Z(s)[V0πfinite∗]z(s)−γH(1−γ)2−2γ⌊/2⌋+1(1−γ)2−ϵ1−γ ≥ _z∈ Z(s)[V^π^*_finite_0]_z(s)- γ^H(1-γ)^2- 2γ /2 +1(1-γ)^2- ε1-γ ≥∑z∈Z(s)[V0πfinite∗]z(s)−4γmin(H,⌊/2⌋+1)(1−γ)2−ϵ1−γ ≥ _z∈ Z(s)[V^π^*_finite_0]_z(s)- 4γ (H, /2 +1)(1-γ)^2- ε1-γ Finally, we complete our analysis by comparing to the optimal value function V∗(s)V^*(s). V∗(s)−VGD(s) V^*(s)-V^GD(s) ≤V∗(s)−∑z∈Z(s)[V0πfinite∗]z(s) ≤ V^*(s)- _z∈ Z(s)[V^π^*_finite_0]_z(s) +4γmin(H,⌊/2⌋+1)(1−γ)2+ϵ1−γ 43.05542pt+ 4γ (H, /2 +1)(1-γ)^2+ ε1-γ ≤2γmin(H,⌊/2⌋+1)1−γ+4γmin(H,⌊/2⌋+1)(1−γ)2+ϵ1−γ ≤ 2γ (H, /2 +1)1-γ+ 4γ (H, /2 +1)(1-γ)^2+ ε1-γ ≤6γmin(H,⌊/2⌋+1)(1−γ)2+ϵ1−γ ≤ 6γ (H, /2 +1)(1-γ)^2+ ε1-γ Here, the penultimate line uses again the Dependence Time Lemma (lemma B.1). Visibility Soft Constraint Fallback throughput plan runtime [s] agents Figure 5: Warehouse-10-20-10-2-1 abalation simulations: red, orange, pink, purple, brown is least to most of value (see legend) B.3 Abalations The outcome of our ablation simulations on warehouse-10-20-10-2-1 are shown in fig. 5. Advantage of Smaller Visibilities When using different visibilities with a fixed Kthreshold=20K_threshold=20, overall we observe that the algorithm hits this threshold sooner resulting a degradation of performance fig. 5. Without this threshold, if we view RHCR as GD-RHCR with V=∞V=∞ (ignoring a minor discrepancy with the replan window), we observed in previous simulations that in the region before RHCR collapse that the throughput remains close for most maps (aside from the smaller 32x32 maps) indicating the effectiveness of using smaller visibilities with soft constraints. Advantage of Smaller Soft Constraints When increasing csoftc_soft, we observe a relatively fast degradation in the computation time which translates to a lower throughput when groups begin to time out. Advantage of Lower Fallback The simulation shows that the throughput is relatively agnostic to the increase in K of Kthreshold=min(0.1k,K)K_threshold= (0.1k,K). This is because for this map, the topology breaks agents into smaller groups which GD-RHCR continues to route into the large agent range and the PIBT fallback is effectively decongesting the larger groups. Appendix C Simulation Times In this section, we will show the scaled plan times and wall times for each of the following simulations shown in fig. 6 and fig. 7. It is important to note for the following that the timeout cap placed on RHCR will cap the wall time but if this wall time is hit, this means RHCR has failed and is simply running the PIBT fallback. Below, we have plotted both the scaled planning time and total wall times. The scaled planning time is simply the average plan time plots taken from fig. 3 and fig. 4 and scaled down the RHCR times by 1/5 representing the evaluation of RHCR happening 1/5th of the timesteps due to the simulation replan window α=5α=5 that were used. We hope that by showing both these plots, we can get better insight into the contribution of the due to the fewer evaluations by RHCR and the error of the core contention and scheduling issues. Wall Times Are Faster Aside from some anomolous maps, we see that overall the wall times are consistently achieve at least a 2x improvement in computation time in the range before RHCR collapse. If we include the region of RHCR after collapse, this improvement ratio can often be made exponentially large as we increase the timeout time for RHCR. Also beyond the RHCR collapse region, RHCR is simply taking the fallback PIBT and not accomplishing any meaningful work. The anomalous maps appear to be the smaller 32x32 random and room maps which is expected by our main discussion in section 7, however, we see that warehouse-10-20-10-2-2 has an oddly large wall time that matches RHCR. Looking at the discrepancy between the scaled plan time and wall time gives a much clearer picture that this is mostly due to scheduling issues and core contention. This primarily shows in the warehouse-10-20-10-2-2 map because the number of groups is large (the largest of all the simulations - see appendix D). Fallback Means Faster Wall Times The maps where GD-RHCR begins to rely on SOLVER2SOLVER2 (PIBT) more and cannot perform well in, we see that the computation time speeds up, sometimes significantly as in random-32-32-20 and room-32-32-var1. For larger agent counts, the groups join and become large and immediately enters PIBT, dropping the wall time. This graceful retreat to the fallback is compared to RHCR which has a computation time that is often exponential with the number of agents only to hit a timeout and falling back anyways. Appendix D Group Statistics A summary of group stastics for each simulation is provided in fig. 8 and fig. 9. We can see that for most maps the average number of groups increases then trends down with the number of agents. This makes sense as the density of agents increases on the map, they tend to form larger groups indicated by the larger average group size. We see clearly for the examples where GD-RHCR had throughput near PIBT (sortation-2, random-32-32-20, room-32-32-var1) the average number of groups is low towards the end range and has a high average max group size. warehouse-10-20-10-2-1 warehouse-10-20-10-2-2 sortation-1 sortation-2 scaled plan time[s] wall time [s] agents Figure 6: Wall times for MAPD. The color coding is GD-RHCR, RHCR, and PIBT random-64-64-20 room-64-64-var1 room-64-64-var2 random-32-32-20 room-32-32-var1 empty-48-48 scaled plan time[s] wall time [s] agents Figure 7: Wall times for random navigation. The color coding is GD-RHCR, RHCR, and PIBT warehouse-10-20-10-2-1 warehouse-10-20-10-2-2 sortation-1 sortation-2 mean num groups mean group size mean max group size agents Figure 8: MAPD group statistics for GD-RHCR. The color coding is GD-RHCR random-64-64-20 room-64-64-var1 room-64-64-var2 random-32-32-20 room-32-32-var1 empty-48-48 mean num groups mean group size mean max group size agents Figure 9: Random navigation group statistics for GD-RHCR. The color coding is GD-RHCR