Paper deep dive

Distance-Constrained Unlabeled Multi-Agent Pathfinding

Takahiro Suzuki, Yuma Tamura, Keisuke Okumura

Year: 2026Venue: arXiv preprintArea: cs.MAType: PreprintEmbeddings: 79

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%

Last extracted: 7/8/2026, 1:56:41 PM

Summary

This paper introduces Distance-r Independent Unlabeled Multi-Agent Pathfinding (rIUMAPF), a graph pathfinding problem where agents must maintain a minimum pairwise distance of r+1 to avoid collisions. Unlike standard unlabeled MAPF, rIUMAPF feasibility is PSPACE-complete. The authors propose two complementary solution approaches: a reduction-based optimal algorithm using Integer Linear Programming (ILP) with feasibility-preserving compression, and a scalable configuration generator-based search combining IU-PIBT and IU-LaCAM. Empirical results demonstrate that these methods can efficiently handle hundreds of agents despite theoretical hardness.

Entities (9)

AIST · organization · 99%Takahiro Suzuki · person · 99%Tohoku University · organization · 99%rIUMAPF · problem · 98%PSPACE-complete · complexity · 97%ILP · method · 96%Unlabeled MAPF · problem · 95%IU-LaCAM · algorithm · 94%IU-PIBT · algorithm · 94%

Relation Signals (6)

Takahiro Suzuki → affiliatedwith → Tohoku University

confidence 99% · Takahiro Suzuki 1,2 ... 1 Tohoku University

Keisuke Okumura → affiliatedwith → AIST

confidence 99% · Keisuke Okumura 2 ... 2 National Institute of Advanced Industrial Science and Technology (AIST)

rIUMAPF → hascomplexity → PSPACE-complete

confidence 97% · This additional distance constraint makes feasibility (i.e., whether a solution exists) PSPACE-complete, in contrast to standard (unlabeled) MAPF, where it can be decided in polynomial time.

IU-LaCAM → uses → IU-PIBT

confidence 96% · IU-LaCAM consists of the configuration generator IU-PIBT that supports distance-r independence and a search scheme LaCAM with tuning for the unlabeled setting.

rIUMAPF → extends → Unlabeled MAPF

confidence 95% · This additional constraint, generalizing collision modeling for classical MAPF, targets aspects of real-world multi-agent coordination.

rIUMAPF → solvedby → ILP

confidence 94% · we present a reduction to INTEGER LINEAR PROGRAMMING (ILP), and an optimal algorithm based on the reduction.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:We study a graph pathfinding problem Distance-$r$ Independent Unlabeled Multi-Agent Pathfinding, finding a set of collision-free paths between two sets where agents must stay at pairwise distance at least $r+1$ at all times. This additional constraint, generalizing collision modeling for classical MAPF, targets aspects of real-world multi-agent coordination. This additional distance constraint makes feasibility (i.e., whether a solution exists) PSPACE-complete, in contrast to standard (unlabeled) MAPF, where it can be decided in polynomial time. We address the challenge via two complementary approaches: (i) reduction-based optimal algorithms with a feasibility-preserving compression procedure, and (ii) a configuration generator-based search. Despite the hardness, empirical results show that our algorithm can handle hundreds of agents in a practical timeframe.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

78,810 characters extracted from source content.

Expand or collapse full text

Distance-Constrained Unlabeled Multi-Agent Pathfinding Takahiro Suzuki 1,2 , Yuma Tamura 1 , Keisuke Okumura 2 1 Tohoku University 2 National Institute of Advanced Industrial Science and Technology (AIST) takahiro.suzuki.q4@dc.tohoku.ac.jp, tamura@tohoku.ac.jp, okumura.k@aist.go.jp Abstract We study a graph pathfinding problem DISTANCE- r INDEPENDENT UNLABELED MULTI-AGENT PATHFINDING, finding a set of collision-free paths between two sets where agents must stay at pair- wise distance at least r + 1 at all times. This ad- ditional constraint, generalizing collision modeling for classical MAPF, targets aspects of real-world multi-agent coordination. This additional distance constraint makes feasibility (i.e., whether a solu- tion exists) PSPACE-complete, in contrast to stan- dard (unlabeled) MAPF, where it can be decided in polynomial time. We address the challenge via two complementary approaches: (i) reduction-based optimal algorithms with a feasibility-preserving compression procedure, and (i) a configuration generator-based search. Despite the hardness, em- pirical results show that our algorithm can handle hundreds of agents in a practical timeframe. 1 Introduction Research on Multi-Agent Pathfinding (MAPF) has attracted considerable attention in the last decade, driven by the grow- ing demand for modern multi-robot systems. MAPF aims to find a set of paths (a plan) from the initial point to the target for given agents, without collisions at every time. In response to diverse requirements and constraints arising in practical settings, many variants of MAPF have been proposed [ Stern et al., 2019 ] ; one of them is the unlabeled (anonymous) ver- sion of MAPF, in which the agents are identical and a colli- sion is defined as multiple agents simultaneously occupying the same vertex. This problem naturally arises in the scenario of homogeneous robots such as warehouse transport [ Ma and Koenig, 2016 ] , where we need to solve an integrated joint problem that optimizes goal assignment and path planning. Although MAPF has been widely studied, it often simpli- fies a collision by ignoring geometric interference, which hin- ders its direct application. For example, we need to address the agents that occupy more than one grid cell (for real-world deployment [ Lehoux-Lebacque et al., 2024 ] ), safety margins (for drone planning [ H ̈ onig et al., 2018 ] ), and delay tolerance (for robust execution [ Atzmon et al., 2020 ] ). These issues motivate a formulation that goes beyond the standard one. These extensions can be naturally abstracted to a sin- gle distance constraint: any pair of agents comes within a distance r on a graph. Hence, a feasible placement of agents corresponds to a distance-r independent set, which has been actively studied in the context of graph theory and graph algorithms. We introduce an extension of unla- beled MAPF; given two vertex subsets, DISTANCE-r IN- DEPENDENT UNLABELED MULTI-AGENT PATHFINDING (rIUMAPF in short) aims to find a plan between them while keeping the placements distance-r independent at every time. Despite the case r = 0 has been studied as Unlabeled MAPF [ Yu and LaValle, 2012 ] , this generalization remains largely under-explored; no algorithm applies to general r ∈ N, while an optimal polynomial-time algorithm is known for r = 0. Moreover, prior work [ Kristan and Svoboda, 2025 ] shows the PSPACE-completeness for determining feasibility when r = 1. PSPACE-completeness reveals not only that the problem is unlikely to be solved in polynomial time, but also that some instances have plans with super-polynomial makespan, i.e., feasibility can depend on extremely long- horizon coordination rather than on locally improving moves. Although no general algorithm is known, rIUMAPF re- mains practically motivated and poses a nontrivial algorith- mic challenge. To this end, we propose two approaches to tackle rIUMAPF, respectively following common practice in MAPF: algorithms based on reduction, and configuration generator, which is a function that computes the next place- ments of the agents from the current ones. 1.1 Our contribution 1. To guarantee the plan quality, we present a reduction to INTEGER LINEAR PROGRAMMING (ILP), and an op- timal algorithm based on the reduction. Furthermore, we give a feasibility-preserving compression that works well when the number of agents is small. However, the empirical result reveals the limitation of scalability. 2. To handle large instances, we propose a configuration generator IU-PIBT and search algorithm IU-LaCAM, which is an analogue to PIBT [ Okumura et al., 2022 ] and LaCAM [ Okumura, 2023 ] for MAPF. IU-PIBT rapidly computes the next configuration, but its rule- based nature tends to get stuck. IU-LaCAM resolves this issue by adding a search following LaCAM and a live- lock detection technique to IU-PIBT, thereby quickly arXiv:2605.11503v1 [cs.MA] 12 May 2026 solving large-scale benchmark instances. The former provides an approach when the plan quality is required, whereas the latter offers a method for handling a large swarm of agents. Together, we establish complemen- tary schemes for rIUMAPF and enable systematic study of it beyond classical Unlabeled MAPF. In what follows, we present a formulation, related work, algorithms, and evalua- tions for both approaches in order. All the proofs of the claims are omitted in the appendix. 2 Preliminaries Notation. Let G = (V,E) be a simple, undirected, and fi- nite connected graph. For a pair of vertices u,v ∈ V , we define dist(u,v) as the length (i.e., number of edges) of the shortest path between u and v. For a vertex v ∈ V , the closed neighborhood is N [v] = w ∈ V | vw ∈ E∪v, and its degree is deg(v) = |N [v]|− 1. We extend the notation; let N r [v] be a set of vertices u such that dist(u,v) ≤ r for an integer r ≥ 0. We define ∆ : = max v∈V deg(v) and ∆ r : = max v∈V |N r [v]|. For a vertex set V ′ ⊆ V , the neigh- borhood is N [V ′ ] = S v∈V ′ N [v]. We define next r (s,t) = arg min v∈N[next r−1 (s,t)] dist(v,t), and next 0 (s,t) = s. We assume that arg min deterministically returns exactly one vertex. We use a notation for a set of continuous integers: let [i,j] be a seti,i + 1,...,j− 1,j for i≤ j. Problem Definition. Let G be a graph and A = [1,n] be a set of n agents. A configuration Q = (q 1 ,...,q n ) ∈ V n is an assignment of each agent to a vertex. Although the con- figurationQ is defined as a list of vertices, we may also refer to it as a (multi-)set of vertices for convenience. A configura- tionQ is distance-r independent if there is no pair of agents i,j ∈ A such that dist(Q[i],Q[j])≤ r. Given a set of initial and target vertices S,T ⊂ V with |S| = |T| = n and a radius r ∈N, rIUMAPF aims to find a finite sequence of configurations Π = [Q 0 ,Q 1 ,...,Q t ∗ ], called a plan, where setsQ 0 andQ t ∗ equals to S and T , re- spectively. Throughout the plan, each agent can move to one of the closed neighbors of the current vertex, provided that ev- ery configuration remains distance-r independent. Formally, a plan Π from S to T in rIUMAPF holds: 1. ∀k ∈ [1,t ∗ ],i∈ A :Q k [i]∈ N [Q k−1 [i]] (reachability). 2. ∀k ∈ [0,t ∗ ] :Q k is distance-r independent. Note that vertex conflicts and swap conflicts commonly used in MAPF [ Stern et al., 2019 ] can be omitted due to the distance-r independence of configurations and anonymous setting. 3 Related work MAPF Extensions. Numerous MAPF variants move be- yond the classical abstraction to capture practical constraints such as extended-body robots and execution uncertainty. Our work offers an alternative approach to accounting for such an extension. One line of research extends MAPF beyond point agents. Large-agent MAPF has been studied under various colli- sion models, including continuous Euclidean distance con- straints [ Agafonov and Yakovlev, 2025 ] , explicit geometric shapes [ Li et al., 2019 ] , and adaptations of Conflict-Based Search (CBS) [ H ̈ onig et al., 2018; Li et al., 2019 ] . While these studies are closely related to our setting in that they generalize collision handling, our formulation represents fea- sible configurations as distance-r independent sets. This per- spective enables the use of graph-theoretic and combinatorial techniques, which we exploit to derive the tractable algorithm presented in Section 5. In addition, we focus on the unlabeled setting, where gen- eralized collision handling has been largely underexplored. Since unlabeled MAPF often admits more tractable formu- lations than its labeled counterpart, as reflected in the com- plexity of makespan optimization [ Yu and LaValle, 2013; Yu and LaValle, 2012 ] and in the design of efficient subopti- mal algorithms [ Okumura et al., 2022; Okumura and D ́ efago, 2023 ] , developing a planner tailored to the unlabeled set- ting enables a faster and more scalable approach than directly adapting labeled algorithms with target assignment. Another line of work relaxes perfect synchrony, consider- ing robust execution under delays [ Atzmon et al., 2020 ] and time uncertainty [ Shahar et al., 2021; Okumura et al., 2023 ] ; a plan of rIUMAPF is one for unlabeled MAPF that allows delays of at most r steps. Reduction-based Approach translates MAPF into well- known problem and leverage off-the-shelf solvers, e.g., SAT- based approach for MAPF [ Surynek et al., 2016 ] , and flow- based optimal one for unlabeled MAPF [ Yu and LaValle, 2012 ] . One of the advantages is that they can readily pro- vide guarantees: often used when the plan quality is required. We follow this line of work. Configuration Generator-based Approach is one of the successful schemes for large-scale, discrete coordination problems [ Okumura et al., 2022 ] , as it rapidly generates the successor configuration from the current one and iterates through execution. These algorithms find plans in large in- stances by localizing the search. Moreover, Okumura (2023) develops a search algorithm, LaCAM, that leverages a con- figuration generator, addressing long-horizon tasks that are difficult to handle solely with a configuration generator. Prior works [ Fu et al., 2026; Suzuki and Okumura, 2025 ] show the advantages of this approach for MAPF variants beyond clas- sical formulation (including the anonymity of agents), and these approaches partially inspire our work. 4 Optimal algorithm with ILP As described in Section 3, several works on MAPF take a reduction-based approach to guarantee the solution qual- ity. In this study, we also adopt a reduction-based approach for rIUMAPF to perform planning with guaranteed solution quality: we choose ILP as the target of the reduction to han- dle the distance-r independence constraint flexibly. First, we define the Bounded rIUMAPF: given a graph G = (V,E), vertex subsets S,T ⊆ V , and time bound τ ∈N, it determines whether there is a plan with length at most τ . Let x v,t be a variable that indicates whether an agent is at v ∈ V at step t, that is, x v,t = 1 when v ∈ Q t , and x v,t = 0 otherwise. Also, f u,v,t represents whether an agent at vertex u at step t moves to v ∈ N [u] at step t + 1 along uv ∈ E. Then, the problem can be formulated by ILP as follows. 1. ∀(v,t)∈ V × [0,τ ], x v,t ∈ [0, 1]. 2. ∀(u,v,t)∈ V 2 × [0,τ ], f u,v,t ∈ [0, 1]. 3. The initial (or final) configuration Q 0 (resp. Q τ ) coin- cides withS (T ): forv ∈ V , x v,0 = 1 ifv ∈ S (x v,τ = 1 if v ∈ T ), and x v,0 = 0 (x v,τ = 0) otherwise. 4. For every step t ∈ [0,τ − 1], exactly x u,t agents on u moves to some vertex v ∈ N [u]: ∀u ∈ V , P v∈N[u] f u,v,t = x u,t . 5. For every step t ∈ [1,τ ], exactly x u,t agents on u comes from some vertex v ∈ N [u]: ∀u ∈ V , P v∈N[u] f v,u,t−1 = x u,t . 6. For every step t ∈ [0,τ ], Q t is distance-r independent: ∀u,v ∈ V s.t. dist(u,v)≤ r. x u,t + x v,t ≤ 1. Condition 6 guarantees distance-r independence of a config- uration: for every pair u,v ∈ V with distance at most r, it holds x u,t = 0 or x v,t = 0. Then we set an objective as a constant, to check whether there is a satisfying assignment to these constraints. It leads to an optimal algorithm, since the time bound for YES-instances is upper bounded by |V (G)| n : the number of vertex subsets with size n. 5 Compression Algorithm The above ILP adds O(|V| 2 ) constraints per step, even when the number of agents n is extremely small. However, one might think that if n is small, a given graph contains redun- dant vertices that can be contracted while preserving feasibil- ity. Such a reduction results in a more compact ILP instance. In this section, we theoretically demonstrate that such a re- duction is possible if ∆ and n are sufficiently small. Specif- ically, we develop an algorithm called a kernelization that bounds the size of the reduced graph by a function of ∆ and n. To this end, we reduce rIUMAPF to the galactic reconfiguration framework [ Bartier et al., 2023 ] . It was re- cently established to design kenelizations for TOKEN SLID- ING, which asks whether one can reach a target token place- ment from an initial one by repeatedly sliding a token to an adjacent vertex while maintaining the placements as an inde- pendent set [ Hearn and Demaine, 2005 ] . To adapt the frame- work to rIUMAPF, we first define notations for the algo- rithms and the galactic variant. We then present a kerneliza- tion for Galactic 1IUMAPF (GMAPF in short). Finally, we generalize this method to the distance-r variant. Kernelization and FPT algorithm. A parameterized prob- lem of a decision problem L is a set of instances (x,κ), where x is an instance of L and κ ∈N is called the parameter of the problem. An algorithm forP is fixed-parameter tractable (FPT) if the algorithm solvesP in h(k)· poly(|x|) time for every instance (x,κ), where h is some computable function and |x| is the size of x. Moreover, P admits a kernelization if there is a polynomial-time algorithm that takes an instance (x,κ) and outputs another instance (x ′ ,κ ′ ) (called a kernel) such that (i) x is a YES-instance of P if and only if x ′ is a YES-instance ofP , (i)|x ′ | is bounded from above by f (κ), where f is a computable function, and (i) κ ≥ κ ′ . Kernel- ization immediately yields an FPT algorithm via exhaustive search. See [ Cygan et al., 2015 ] for more details. Notation for GMAPF. For a vertex subset S of a graph G, let G[S] denote the subgraph induced by S. A graph G is connected if there is a path between any two vertices of G. A component of G is a maximal connected subgraph. A galactic graph G = (P ∪ B,E) is a graph whose vertex set is the disjoint union of two sets P (called planets) and B (called black holes). Recall that, in rIUMAPF, agents are required to keep each configuration independent; thus, no ver- tex can be occupied by more than one agent at any time. We relax this constraint so that only agents on the vertices in P are required to be independent, while each vertex in B may hold at most n agents. That is, a black hole b ∈ B behaves as a vertex that absorbs agents located at adjacent vertices. We say that a configurationQ is galactic distance-r indepen- dent if there is no pair i,j ∈ A such that Q[i],Q[j] ∈ P and dist P (Q[i],Q[j]) ≤ r, where dist P (u,v) for a pair of vertices u,v ∈ P is the length of the shortest path in G[P ] between u and v. In particular, a galactic distance-1 inde- pendent configuration is simply called a galactic independent configuration. Given a galactic graph G and two sets of ver- tices S,T ⊆ P such that b /∈ N [S ∪ T ] for all black hole b and|S| = |T| = n, Galactic rIUMAPF asks whether there is a plan Π = [S = Q 0 ,Q 1 ,...,Q t ∗ = T ] satisfying the following two conditions: 1. ∀k ∈ [1,t ∗ ],∀i∈ A :Q k [i]∈ N [Q k−1 [i]]. 2. ∀k ∈ [0,t ∗ ] :Q k is galactic distance-r independent. Note that GMAPF generalizes 1IUMAPF; an instance (G = (V,E),S,T ) of 1IUMAPF can be viewed as an instance (G ′ = (P∪B,E),S,T ) of GMAPF withP = V andB =∅. ILP formulation of GMAPF. Observe that GMAPF can be reduced to ILP by slightly modifying 1IUMAPF formu- lation as follows: Cond. 1: x v,t ∈ [0, 1] if v ∈ P , and x v,t ∈ [0,n] otherwise; Cond. 2: f u,v,t ∈ [0,n] if u,v ∈ B, and otherwise f u,v,t ∈ [0, 1], and; Cond. 6 galactic indepen- dence: ∀u,v ∈ P s.t. dist P (u,v) ≤ 1. x u,t + x v,t ≤ 1. By the same discussion as Section 4, we obtain an optimal algorithm for GMAPF; similar for DISTANCE-r variant. 5.1 Kernelization for GMAPF Given an instance (G = (P ∪ B,E),S,T ), we first perform a preprocessing step as follows. For each vertex v ∈ P , we partition the vertices into layers: L i : = v ∈ P | d(v) = i, where d(v) : = min s∈S∪T dist P (s,v). Note that every vertex is contained in exactly one layer. Under this preprocessing, our kernelization algorithm repeatedly performs the follow- ing two reductions: one is a straightforward rule, and the other generates black holes. For the sake of simplicity, we write V p for the set of vertices in the planet that are not adja- cent to S or T , i.e., P\(N [S∪T ]), and we write G p = G[V p ]. Reduction rule 1. If two black holes u and v are adjacent, we contract them into a single black hole. Reduction rule 2. Let v ∈ V p be a vertex of a component C of G p . If v is included in the layer L k such that k ≥ 2n + 3, C 1 C 2 C 3 v ∈ L 7 C 1 C 2 C 3 v C 2 C 3 b Figure 1: An illustration of Reduction rule 2 when r = 1, n = 2, and B = ∅. Red (or blue) vertices indicate S (resp. T ). Each square C 1 ,C 2 ,C 3 represents a component of G r . Left: Suppose that a vertex v ∈ C 1 has a large layer, 2n + 3 = 7. Middle: Then there is a path of 7− 2 = 5 vertices that does not touch N[S∪ T], and if an agent can move to a vertex of C 1 , it can enter some vertex on this path. Right: Then C 1 can absorb any agents; behave like a black hole. Thus, we compress C 1 to a black hole b. we replace C with a single black hole b, and connect b to every vertex in N [C]\ C by adding edges. Our core idea of Reduction rule 2 is that, if there is a vertex v that is included in L k with k > 2, then there is a path with k− 2 vertices that is not touched by N [S∪T ]. If k ≥ 2n + 3 (Figure 1 left), there is an independent set with n vertices on the path. Moreover, agents placed on vertices in C can be re- assigned to the path without breaking galactic independence (Figure 1 center); C can absorb n agents and behave like a black hole. Thus, we contract C into b (Figure 1 right). Lemma 1. Reduction rules 1 and 2 are both safe, i.e., there is a plan in the graph after reductions if and only if there is a plan in the one before reductions. The reductions terminate in linear time. Consider an in- stance (G,S,T ) of GMAPF, where Reduction rules 1 and 2 are iteratively applied until no updates are available. One can observe that every planet p has its layer less than 2n + 2; oth- erwise p is contracted into a black hole. Moreover, the size of B is bounded by|N [P ]\ P|. This leads to Theorem 1. Theorem 1. GMAPF admits a kernel with ∆ O(n) n vertices. Moreover, if we are given an induced grid graph, an in- duced subgraph of the Cartesian product of two paths, the upper bound of |P| is much smaller. Note that induced grid graphs are commonly used in empirical evaluation of the MAPF algorithms [ Stern et al., 2019 ] . Theorem 2. GMAPF admits a kernel with O(n 3 ) vertices when an induced grid graph is given. Corollary 1. IUMAPF admits an FPT algorithm when pa- rameterized by ∆ + n. Extension to DISTANCE-r variant. Recall that our core idea is to find a path of sufficiently long length that can “ab- sorb” n agents. In the distance-r variant, an analogous argu- ment holds for a path of length (r + 1)(n + 1)− 1. Therefore, it suffices to modify Reduction rule 2 to find a vertex with the layer L k with k ≥ (r + 1)(n + 1) − 1 + (r + 1) = (r + 1)(n + 2)− 1, ensuring that the path does not touch the distance-r neighbors of S∪ T . From the same discussion on Theorem 1, the problem admits a kernel of size ∆ O(rn) n. Algorithm 1 IU-PIBT, generator for IUMAPF Input: configurationQ from , goals T (with priority p), assignment g Output: configurationQ to , new assignment g ′ and priority p ′ 1:while∃ deadlock do rotate targets to resolve it▷ rule 1 2:for v ∈ T do 3:p ′ (v)← ifQ from [g −1 (v)] = v then frac(p(v)) else p(v) + 1 4: Sort A by an descending order of p ′ (g(i)) 5:for i∈ A do 6:ifQ to [i] =⊥ then IU-PIBT(i,ε,g)▷ ε: empty list 7: returnQ to ,g,p ′ 8: function IU-PIBT(i,S,g) 9:Sort v ∈ N[Q from [i]] in ascending order of dist(v,g(i)) 10:for v ∈ N[Q from [i]] do 11:if∃j s.t. Q to [j]̸=⊥∧Q to [j]∈ N r [v] then continue; 12:if∃j s.t. Q from [j]∈ N r [v]∧ j ∈ S then continue; 13:Q to [i]← v, f ← TRUE▷ temporal assignment 14:if∃k : = SWAP(i,v) then swap g(i) and g(k) ▷ rule 2 15:for u∈ N r [v] do 16:if∃j s.t. Q from [j] = u∧ j ̸= i then 17:ifQ to [j] =⊥ then IU-PIBT(j,S + [i],g) 18:ifQ to [j]∈ N r [v] then f ← false; break; 19:if f = TRUE then return VALID 20:swap back g(i) and g(k) if k exists; 21:Q to [i]←Q from [i]; return INVALID 6 Configuration Generator-Based Algorithm Although the ILP-based algorithm guarantees solution qual- ity, it has scalability limitations, as we observe in Section 7.1. To complement this limitation, this section proposes a config- uration generator-based algorithm IU-LaCAM, scalable for large instances. IU-LaCAM consists of the configuration gen- erator IU-PIBT that supports distance-r independence and a search scheme LaCAM with tuning for the unlabeled setting. We first present IU-PIBT, and then search. 6.1 Configuration Generator IU-PIBT IU-PIBT takes the current configuration Q from , the target T , and a bijection g : A → T (used for a target assignment) as input to compute the configuration Q to and a new bijection g ′ : A → T for the next time step. Note that an initial bi- jection can be obtained by some bipartite matching algorithm (e.g., the Hungarian method) with distance evaluation. Concept. IU-PIBT is inspired by rotation-free PIBT [ Oku- mura et al., 2022 ] , which repeatedly performs prioritized one-step planning, i.e., sequentially determining the next lo- cation Q to [i] of each agent i in decreasing order of prior- ity. It additionally prevents rotations, namely cyclic moves where agents simultaneously shift along a directed cycle, since it is enabled by the standard abstraction for MAPF. In this paper, IU-PIBT generates Q to while maintaining distance-r independence.Moreover, it avoids distance-r rotations, a sequence of agents (a 1 ,a 2 ,...,a k ) such that Q to [a i ] ∈ N r [Q from [a i+1 ]] for i ∈ [1,k− 1], and Q to [a k ] ∈ N r [Q from [a 1 ]]. Further, inspired by the suboptimal unlabeled MAPF work [ Okumura and D ́ efago, 2023 ] , it finds a plan by inserting swap and rotation of goal assignment in IU-PIBT. a b c d e a b c d e a b c d e a b c d e a b c d e a b c d e 12 3 4 1 2 3 Figure 2: An example of the IU-PIBT’s operation when r = 1. The graph G is a part of a grid, and v i-j denotes the vertex with row i and column j. Dashed arrows represent the assignment g, red and blue arrows represent the next location of each agent (red if fixed, and blue if temporal). Column 1: IU-PIBT calls IU-PIBT for agent a, and temporary decides Q to [a] = v 1-2 . Then it starts to check neighbors, and first calls IU-PIBT for b with S = [a]. Since moving b to v 2-3 causes a distance-1 rotation, this fails. Column 2: Then IU- PIBT for b reassignsQ to [b] = v 1-4 , and it swaps targets of b and c since c =SWAP(b,v 1-4 ). Recursive calls to c and d occur. Column 3: Calls for b,c,d succeed, and IU-PIBT next checks whether e can safely move out of N[Q from [a]]. Agent e cannot move to any vertex and decides to stay at v 1-1 . Since a can no longer move to v 1-2 , it next chooses another vertex v 2-3 as temporal Q to [a]. This does not break the independence of Q to ; the assignment succeeds. This yields the next configurationQ to and a new goal assignment g ′ . Algorithm. Algorithm 1 illustrates IU-PIBT, consisting of (i) top-level procedure (line 1–7), and (i) recursive function (line 8–21). Blue lines indicate the differences from the orig- inal PIBT. Our core is a function IU-PIBT, which determines the next locationQ to [i] for agent i with a list S of agents and a bijection g, so that dist(Q to [i],Q to [j]) > r holds for all agents j ̸= i, and Q from [j] /∈ N r [Q to [i]] holds for all agents j ∈ S. Here, S denotes the set of agents waiting for agent i to move. When attempting to move agent j to vertex v, agent i blocks the move due to the constraint of distance-r indepen- dence. In such a case, we consider moving i first through a recursive process. By maintaining S, we prevent distance-r rotations: if there exists j ∈ S withQ from [j]∈ N r [Q to [i]], the distance-r rotation involving i occurs, and j cannot move to v. In other words, IU-PIBT fixesQ to [j] for each j ∈ S only if both conditions for i are satisfied. A step-by-step example of execution is shown in Figure 2. (i) Top-level procedure. (line 1–7) Given a configuration Q from , goals T , temporal target assignment g : A → T , IU- PIBT first detects a deadlock starting with i ∈ A, which is a sequence of agents (i = a 1 ,a 2 ,...,a ℓ ) that satisfies next r+1 (Q from [a k ],g(a k )) = Q from [a k+1 ] for k ∈ [1,ℓ− 1], and next r+1 (Q from [a ℓ ],g(a ℓ )) = Q from [a 1 ] (see Figure 3 (a) left). If a deadlock is detected, we exchange the targets of agents to eliminate it (Figure 3 (a) right). The detailed imple- mentation is shown in the Appendix. Then IU-PIBT updates the goal priorities based on the assignment g and the current configurationQ from . For a goal v ∈ T , if there exists an agent i∈ A that has arrived at its goal v (i.e., g(i) =Q from [i] = v), then p ′ (v) is defined as frac(p(v)) : = p(v)−⌊p(v)⌋; other- wise, p ′ (v) is set to p(v) + 1. Here, we assume that at step 0, each goal receives a unique decimal p(v)∈ (0, 1) to break ties. IU-PIBT sorts agents in descending order of p ′ (g(i)) for i ∈ A, and in that order, it calls IU-PIBT for an agent i with the next location Q to [i] = ⊥ (means undecided), and determinesQ to [i] sequentially. (i) IU-PIBT. (line 8–21) Then, IU-PIBT determines the next location for agent i with a list S of agents and a tempo- ral target assignment. We enumerate the neighbors, and sort them in ascending order of dist(v,g(i)) for v ∈ N [Q from [i]]. A function IU-PIBT then validates whether moving i to v violates the distance-r independence or causes a distance- r rotation (line 10–20). Specifically, the move is rejected if there is an agent j ̸= i such thatQ to [j]̸=⊥ orQ to [j]∈ N r [v] (line 11), or there is an agent j ∈ S such that Q from [j] ∈ N r [v] (line 12). Otherwise, IU-PIBT temporarily decides to move i to v (line 13). However, there may exist agents j ̸= i whose next location is currently undetermined (Q to [j] = ⊥), but will later be assigned to a vertex in N r [v]; this breaks distance-r independence. To validate whether the agent i can move v, IU-PIBT recursively calls IU-PIBT for the agent j to ask whether j can move to a vertex v ′ /∈ N r [v] (line 17). Here, we add i to a list S to avoid a distance-r rotation involv- ing i. If this recursive call fixes Q to [j] to be in N r [v], then the for-loop of lines 15–18 breaks, and IU-PIBT tries another vertex in N [Q from [i]] as the next locationQ to [i] of agent i. If i passes these checks, IU-PIBT fixes the next locationQ to [i] as the vertex v and returns VALID. When the for-loop of lines 10–20 fails for all candidates v ∈ N [Q from [i]], it forces i to stay atQ from [i]. Target swapping. (line 14, 20) As a preprocessing of the recursive call, we additionally perform a temporal tar- get swapping. Given an agent i and vertex v ∈ N [v], func- tion SWAP(i,v) asks, there is an agent that should swap the goal with i. Suppose that there is an agent k (denoted by SWAP(i,v)) at next r (v,g(i)), and Q from [k] = g(k) (Fig- ure 3 (b) middle). Such k blocks agent i from reaching its goal. To avoid this, we temporarily swap the goals of these two (line 14). If the recursive call returns VALID (line 19), then the swap is fixed (Figure 3 (b) top). Otherwise (line 20), we revert it by swapping back (Figure 3 (b) bottom). A pseu- docode of the function SWAP is provided in the Appendix. 6.2 Theoretical Analysis of IU-PIBT Now we argue that IU-PIBT is a reasonable configuration generator. In what follows, we present soundness, running time, completeness for 0IUMAPF in some restricted cases, and adversarial instance. The discussion of solution quality for r ≥ 1 is omitted due to PSPACE-completeness. Lemma 2. If Q from is distance-r independent, then Q to is reachable and a distance-r independent configuration. Lemma 3. IU-PIBT outputsQ to in ∆ r ∆(r + 1)n + α time, where α denotes the time for resolution of deadlock. Theorem 3. IU-PIBT is complete for 0IUMAPF, when the given graph has no edge uv ∈ E such that G[V \u,v] is not connected. i j i j (a) i j j : INVALID i j j : VALID i j (b) Figure 3: Two rules in IU-PIBT, when r = 1. Black arrows rep- resent the assignment of goals to each agent, red and blue arrows represent the next location of each agent (red if fixed, and blue if temporal). (a) Before (left) and after (right) performing deadlock resolution. If a deadlock is found, we resolve it by rotating the as- signment of targets. (b) Target swapping. When an agent j has already reached its goal (center), it swaps g(i) and g(j) and calls IU-PIBT for j. When the call for j succeeds (right), we retain the modified one; otherwise (left), we revert to the original one. (a) i j i j i j (b) Figure 4: Adversarial instances for IU-PIBT, when r = 1. (a) One needs a rotation, which cannot be captured by IU-PIBT. The resulting configuration Q to is equal to Q from . (b) Livelock. If p ′ (j) > p ′ (i), IU-PIBT for j is called first, and i is forced to move down. Otherwise, IU-PIBT for i is called first, and j is forced to move up. This process recurs infinitely, ensuring that i and j will never reach the goal simultaneously. Adversarial instances. Since IU-PIBT employs sequential decision forQ to , it performs poorly on instances where mul- tiple agents must move simultaneously (see Figure 4 (a)). Furthermore, when a pair of agents attempts to pass each other, they cannot rotate, causing a livelock (see Figure 4 (b)). These examples show that IU-PIBT can fail even on simple local structures. While one may add ad hoc rules to handle these particular cases, obtaining a general scheme that guar- antees completeness is unlikely to be simple, since deciding feasibility in rIUMAPF is PSPACE-complete. 6.3 IU-LaCAM Although IU-PIBT gets stuck when distance-r rotations are needed, a rotation-free implementation is necessary for the validity of configurations, and it is difficult to overcome this issue with a simple rule-based method. Thus, we employ the LaCAM search and propose IU-LaCAM for rapid planning. LaCAM [ Okumura, 2023 ] is a well-known complete MAPF solver that utilizes a configuration generator with con- straints, which include a subset of agents and their next lo- cations for creating a successor configuration of the current one. LaCAM maintains search states as tuples⟨Q,JCK⟩ of a configuration and a list of constraints during the search; if the generator produces a configuration identical to one already Algorithm 2 livelock detection and target reassignment input: nodeN =⟨Q,JCK,g,B⟩▷ generated known configQ params: depth of detection d∈N ≥0 1: N ans ← parent(N)▷N ans =⟨Q ans , [C ans ],g ans ,B ans ⟩ 2: for [0,d] while∃N ans do 3:ifQ =Q ans ∧ g = g ans then 4:D ←i|Q[i] =Q ans [i]∧Q[i]̸= g(i) 5:B ′ ← [B ans [i]∪g(i)| i∈ D] 6:find an assignment g ′ s.t. g ′ (i) /∈B ′ [i] 7:if succeeded thenN ans ←⟨Q,JC init K,g ′ ,B ′ ⟩ 8:pushN ans to stack OPEN 9:break; 10:N ans ← parent(N ans ) generated, it modifies the constraints to induce the genera- tion of a different configuration. Eventually, it tries all possi- ble constraints for every configuration, thereby generating all reachable successors. This guarantees completeness. It was originally developed for labeled MAPF; however, we can also adapt it to the unlabeled setting by including the target assignment function g in the search state. A brief pseudocode of LaCAM is in the Appendix. Here, a prior work [ Jain et al., 2026 ] reports that a livelock detection scheme potentially accelerates the search speed of LaCAM. Inspired by these results, we introduce a similar technique: we detect the livelock described in Section 6.2 and resolve it by reconstructing the target assignment. A concrete strategy is shown in Algorithm 2, where each search node stores a list B of goals that must not be chosen as its goal during assignment for each agent, in addition toQ, JCK, and g. If a new configuration constructed by IU-PIBT (see the Appendix for pseudocode) is identical to one of the most recent d (= 2 in our experiment) configurations and the assignment g is also identical, then we regard the search as entering a livelock. Then, we detect the set D of agents that have not reached their goals and whose positions have not changed. For i ∈ D, we add each goal g(i) to B so that its current goal will not be assigned in a new function g ′ . If we can compute g ′ that avoids B ′ , then we update the stack so that IU-PIBT is called with g ′ and reset constraints (line 8). This target reassignment does not break the completeness of LaCAM, since the number of target reassignments (line 6) is bounded, thus initialization of constraints is bounded. Theorem 4. IU-LaCAM is complete for rIUMAPF. 7 Empirical Evaluation We evaluate both ILP- and configuration generator-based methods on several maps. These are coded in Python, and the experiments were run on a Mini PC with Intel Core i9- 13900H 2.6 GHz CPU and 32 GB RAM. For our evalua- tion, we use the empty-16-16, random-64-64-20, lak303d, and warehouse-10-20-10-2-2 in MAPF benchmarks [ Stern et al., 2019 ] . Since the scenario in MAPF benchmarks does not apply to rIUMAPF, we generate instances by sampling two random distance-r independent sets (S and T ), for each map, distance r, and number of agents n. 0.0 0.5 1.0 0 125250375500 0 100 200 0 83 166250333 0 62 125188250 0.0 0.5 1.0 0 375750 11251500 0 250 500 750 0 250500750 1000 0 188375562750 0.0 0.5 1.0 0 250500750 1000 0 250 500 750 0 166333500666 0 125250375500 random-64-64-20lak303d warehouse-10-20-10-2-2 success rate makespan r = 1r = 2r = 3r = 1r = 2r = 3r = 1r = 2r = 3 IU-PIBTIU-LaCAM w/o alg2IU-LaCAM #agents Figure 5: Time and makespan across three maps. For larger r, we cannot secure a sufficient number of distance-r independent sets when the number n of agents is large; thus, the upper bound on n differs among r. We also report the 95% CI of the makespan by filled area. ILPCompression IU-LaCAM Map n r rate (%) time (s) ratetime ratetime empty-16-16 10 20 30 1 2 1 2 1 2 100 100 100 100 100 100 0.482 0.801 0.408 0.587 0.386 0.527 100 100 100 100 100 100 0.334 0.691 0.255 0.484 0.231 0.409 100 100 100 100 100 100 0.030 0.032 0.037 0.036 0.045 0.043 random-64-64-20 10 20 30 1 2 1 2 1 2 86 74 90 56 84 76 41.60 44.69 41.57 45.84 40.43 42.62 100 82 92 66 90 82 0.056 23.79 20.01 34.55 21.13 29.61 100 100 100 100 100 100 0.091 0.088 0.149 0.159 0.206 0.216 Table 1: Evaluation of the ILP algorithms, using 60 s timeout. We prepared 50 random instances for each map and r ∈ 1, 2, n ∈ 10, 20, 30, and report the rate (%) of instances solved within 60 s and the average running time (s) over those instances. We also report the success rate and running time of IU-LaCAM. 7.1 Evaluation of Exact ILP algorithms Table 1 shows both the effectiveness and limitations of ILP approach, which uses Gurobi as the ILP solver. We pre- pare 50 random instances for each setting. On a simple map (empty-16-16), the solver can find an optimal solution within a second, while on a large-scale instance (random-64-64-20), the solver often fails to find a solution, and the number of failed instances increases as n increases. On large maps, compression can partially mitigate this issue; see random- 64-64-20 with n = 10. However, this improvement appears only in extremely sparse settings. These results indicate that the scalability of the ILP approach is primarily limited by the growth in the number of variables. In settings where kernelization does not effectively reduce the instance size, IU-LaCAM overcomes this scalability barrier. Indeed, IU- LaCAM achieves at least a 500% speedup on empty-16-16, and a speedup by a factor of roughly 100 on random-64-64- 20 (e.g., n = 30 and r = 1). 7.2 Large-scale Problem of r ≥ 1 We evaluate the scalability of the configuration generator- based approach LaCAM on large instances. Since our ILP- based algorithm is not scalable to a large-scale setting, we exclude ILP from these experiments. We generate random instances on the large maps random-64-64-20, lak303d, and warehouse-10-20-10-2-2 for r ∈ [1, 3], and analyzed the frac- tion solved within 60 seconds (success rate) and the length of plan (makespan). Figure 5 shows the empirical result for each setting. The main observation is as follows: • Although IU-PIBT works in sparse settings to find a so- lution, IU-PIBT alone rarely finds a solution in moder- ately dense situations. This suggests that IU-PIBT alone often gets stuck due to livelocks. • LaCAM substantially increases the number of solved in- stances in dense settings, 1 indicating that LaCAM re- solves stucks by explicitly specifying moves of agents. • By explicitly handling livelocks within LaCAM, we fur- ther increase the number of solvable instances. This sug- gests that leveraging the anonymity of agents enables us to plan faster. However, this yields no clear benefit on maps with many narrow corridors (e.g., warehouse-10- 20-10-2-2 and r = 1), suggesting that there are difficul- ties other than livelocks in instances on such maps. 7.3 Special case r = 0: Unlabeled MAPF Recall that rIUMAPF is equivalent to unlabeled MAPF when r = 0. Thus, we evaluate the performance of IU- PIBT against existing algorithms specialized in unlabeled MAPF. We carefully choose the state-of-the-art configu- ration generator-based algorithm TSWAP [ Okumura and D ́ efago, 2023 ] as a baseline, 2 and evaluate the running time and solution quality. Both algorithms require an initial tar- get assignment function; we use the Hungarian method. Note that the completeness of the two algorithms does not depend 1 Extremely dense scenarios yield too few distance-r independent sets to sample, so they are outside our experimental scope; conse- quently, the success rate never falls below 1.0 in some settings. 2 The code is available in https://github.com/Kei18/pytswap.git. 0 20 40 60 64-64-20lak303dwarehouse 5001000 2 4 6 8 10 10002000300010002000 running time ( s ) suboptimality IU-PIBTTSWAP #agents Figure 6: Average running time and suboptimality of TSWAP and IU-PIBT. Note that IU-PIBT always found a plan on the three maps. on the assignment function. We use the average running time and the suboptimality of the plan (defined as the plan length over a trivial lower bound) for our evaluation. Here, we use the value of a BOTTLENECK MATCHING as the trivial lower bound, as it represents the plan length when each agent moves toward its goal, disregarding any conflicts. Figure 6 shows the running time and suboptimality in three maps. We observe that the running time does not differ signif- icantly, suggesting that the Hungarian algorithm likely dom- inates the overall time. However, IU-PIBT achieves lower suboptimality, as it allows more flexible moves than TSWAP. 8 Conclusion We study rIUMAPF, a variant of MAPF that introduces an extended collision definition by distance into a standard un- labeled MAPF. This extension makes conventional MAPF algorithms inapplicable, and there are no algorithms read- ily applicable to rIUMAPF. We tackle this problem with two approaches from the view of quality and scalability: reduction-based algorithms with compression, and configura- tion generator-based search. A direction for future work is to develop a search scheme for the unlabeled variant, efficiently handling the anonymity of agents; leave as an open question. Acknowledgments This research was partially supported by JSPS KAKENHI Grant Number 25K21289 and JST PRESTO (JPMJPR2513). References [ Agafonov and Yakovlev, 2025 ] Artem Agafonov and Kon- stantin Yakovlev. Multi-agent path finding for large agents is intractable. In Proceedings of European Conference on Artificial Intelligence (ECAI), volume 413, 2025. [ Atzmon et al., 2020 ] Dor Atzmon, Roni Stern, Ariel Felner, Glenn Wagner, Roman Bart ́ ak, and Neng-Fa Zhou. Ro- bust multi-agent path finding and executing. J. Artif. Intell. Res., 67, 2020. [ Bartier et al., 2023 ] Valentin Bartier, Nicolas Bousquet, and Amer E. Mouawad. Galactic token sliding. J. Comput. Syst. Sci., 136, 2023. [ Cygan et al., 2015 ] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parame- terized Algorithms. Springer Publishing Company, Incor- porated, 1st edition, 2015. [ Fu et al., 2026 ] Bo Fu, Zhe Chen, Rahul Chandan, Alex Barbosa, Michael Caldara, Joey Durham, and Federico Pecora. Symbolic planning and multi-agent path finding in extremely dense environments with movable obstacles. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2026. [ Hearn and Demaine, 2005 ] Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puz- zles and other problems through the nondeterministic con- straint logic model of computation. Theor. Comput. Sci., 343(1-2), 2005. [ H ̈ onig et al., 2018 ] Wolfgang H ̈ onig, James A. Preiss, T. K. Satish Kumar, Gaurav S. Sukhatme, and Nora Aya- nian. Trajectory planning for quadrotor swarms. IEEE Transactions on Robotics (T-RO), 34(4), 2018. [ Jain et al., 2026 ] Rishabh Jain, Keisuke Okumura, Michael Amir, and Amanda Prorok. Graph attention-guided search for dense multi-agent pathfinding. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2026. [ Kristan and Svoboda, 2025 ] Jan Maty ́ as Kristan and Jakub Svoboda. Reconfiguration using generalized token jump- ing. In Proceedings of International Conference and Work- shops on Algorithms and Computation (WALCOM), vol- ume 15411. Springer, 2025. [ Lehoux-Lebacque et al., 2024 ] VassilissaLehoux- Lebacque, Tomi Silander, Christelle Loiodice, Seungjoon Lee, Albert Wang, and Sofia Michel. Multi-agent path finding with real robot dynamics and interdependent tasks for automated warehouses. In Proceedings of European Conference on Artificial Intelligence (ECAI), volume 392, 2024. [ Li et al., 2019 ] Jiaoyang Li, Pavel Surynek, Ariel Felner, Hang Ma, T. K. Satish Kumar, and Sven Koenig. Multi- agent path finding for large agents.Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 33(01), 2019. [ Ma and Koenig, 2016 ] Hang Ma and Sven Koenig. Optimal target assignment and path finding for teams of agents. In Proceedings of International Conference on Autonomous Agents & Multiagent Systems (AAMAS), 2016. [ Okumura and D ́ efago, 2023 ] Keisuke Okumura and Xavier D ́ efago. Solving simultaneous target assignment and path planning efficiently with time-independent execution. Ar- tificial Intelligence, 2023. [ Okumura et al., 2022 ] Keisuke Okumura, Manao Machida, Xavier D ́ efago, and Yasumasa Tamura. Priority inheri- tance with backtracking for iterative multi-agent path find- ing. Artificial Intelligence, 2022. [ Okumura et al., 2023 ] Keisuke Okumura, Franc ̧ois Bonnet, Yasumasa Tamura, and Xavier D ́ efago.Offline time- independent multiagent path planning. IEEE Transactions on Robotics, 2023. [ Okumura, 2023 ] Keisuke Okumura. LaCAM: Search-based algorithm for quick multi-agent pathfinding. In Proceed- ings of AAAI Conference on Artificial Intelligence (AAAI), 2023. [ Shahar et al., 2021 ] Tomer Shahar, Shashank Shekhar, Dor Atzmon, Abdallah Saffidine, Brendan Juba, and Roni Stern. Safe multi-agent pathfinding with time uncertainty. J. Artif. Intell. Res., 70, 2021. [ Stern et al., 2019 ] Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Bart ́ ak, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of Annual Symposium on Combinatorial Search (SoCS), 2019. [ Surynek et al., 2016 ] Pavel Surynek, Ariel Felner, Roni Stern, and Eli Boyarski. Efficient SAT approach to multi- agent path finding under the sum of costs objective. In Proceedings of European Conference on Artificial Intelli- gence (ECAI), volume 285, 2016. [ Suzuki and Okumura, 2025 ] Takahiro Suzuki and Keisuke Okumura. Polynomial-time configuration generator for connected unlabeled multi-agent pathfinding.ArXiv preprint, 2510.19567, 2025. [ Yu and LaValle, 2012 ] Jingjin Yu and Steven M. LaValle. Multi-agent path planning and network flow. In Workshop on the Algorithmic Foundations of Robotics (WAFR), vol- ume 86, 2012. [ Yu and LaValle, 2013 ] Jingjin Yu and Steven M. LaValle. Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2013. Appendix A Omitted discussions in Section 5 TOKEN SLIDINGis a problem that asks whether one can reach a target token placement from a given initial one by moving one token to an adjacent vertex, while maintaining the placement as an independent set [ Hearn and Demaine, 2005 ] . Formally, the problem asks whether there exists a se- quence of independent sets [S = S 0 ,S 1 ,...,S ℓ = T ] such that S i−1 and S i are adjacent for every i ∈ [1,ℓ] under the following rule. In TOKEN SLIDING, for two independent sets I 1 and I 2 , we say that I 1 and I 2 are adjacent if there exist vertices u,v ∈ V (G) such that I 1 \ I 2 =u, I 2 \ I 1 =v, and uv ∈ E(G). This problem is similar to 1IUMAPF in the sense that we can view agents as tokens and allow at most one token to move to an adjacent vertex in each step. Indeed, some recent works have progressed on settings motivated by MAPF [ Kristan and Svoboda, 2025 ] . A.1 Proofs We begin by proving that the reduction rules in Section 5 are safe. Here, for a graph G = (V,E), we define the open neigh- borhood N (v) of v ∈ V as N (v) =w ∈ V | vw ∈ E, and N (V ′ ) for V ′ ⊆ V as N [V ′ ]\ V ′ for the sake of simplicity. Lemma 1. Reduction rules 1 and 2 are both safe, i.e., there is a plan in the graph after reductions if and only if there is a plan in the one before reductions. To prove Lemma 1, we first present the following lemma. Lemma 4. Let G = (V,E) be a graph and let G ′ = (V ′ ,E ′ ) be the graph obtained by applying either Reduction Rule 1 or Reduction Rule 2 once, which replaces a vertex subset W with a single black hole b. If there is a plan from S to T for G, then there is a plan from S to T for G ′ . Proof. Let Π = [Q 0 ,Q 1 ,...,Q ℓ ] be a plan for G from S to T . Consider the sequence Π ′ = [Q ′ 0 ,Q ′ 1 ,...,Q ′ ℓ ] such that: Q ′ k [i] = bifQ k [i]∈ W Q k [i] otherwise. We now show that Π ′ is a plan for G ′ from S to T . First, we claim the reachability of each configuration. For a step k ∈ [0,ℓ − 1], consider an arbitrary agent i. If Q k [i] /∈ W and Q k+1 [i] /∈ W hold, then Q ′ k [i] = Q k [i] and Q ′ k+1 [i] = Q k+1 [i]. Since Π is a plan for G, we have Q ′ k+1 [i] = Q k+1 [i] ∈ N [Q k [i]] = N [Q ′ k [i]]. Otherwise, Q k [i] ∈ W or Q k+1 [i] ∈ W holds. Without loss of gen- erality, assume that Q k [i] ∈ W . Then there are two cases: Q k+1 [i] ∈ W and Q k+1 [i] ∈ N (W ). The former case is straightforward because Q ′ k [i] = Q ′ k+1 [i] = b. In the lat- ter case, we have Q ′ k+1 [i] = Q k+1 [i]. Since Q ′ k [i] = b is adjacent to the vertices in N (W ) by definition, we have Q ′ k+1 [i] = Q k+1 [i] ∈ N (W ) = N (b) ∈ N [Q ′ k [i]]. There- fore,Q ′ k+1 is a reachable configuration. This claim holds for every k ∈ [0,ℓ− 1]. Moreover, no pair of two agents i,j on P \ W is adjacent on G, where P is a set of planets in G. SinceQ k [i] = Q ′ k [i] for every agent i with Q k [i] /∈ W , the configuration Q ′ k is also galactic independent. Therefore, Π ′ is a plan for G ′ , completing the proof. Thus, we can transform any plan for G into a plan for G ′ in both rules. We next show the converse, i.e., we can transform any plan for G ′ into a plan for G, which completes the proof of Lemma 1. We begin with the correctness of Reduction rule 1. As a preparation, for a vertex b, we denote by S pro t and S abs t the sets of agents that leave b and enter b at step t, respectively, that is, S pro t = i ∈ A | Q ′ t−1 [i] = b∧Q ′ t [i] ̸= b and S abs t =i∈ A|Q ′ t [i] = b∧Q ′ t−1 [i]̸= b. Lemma 5. Reduction rule 1 is safe. Proof. Let G be the initial graph and G ′ be a graph obtained after applying Reduction rule 1 to adjacent black holes u,v of G. By Lemma 4, if there is a plan from S to T for G, then there is a plan for G ′ . Suppose that there is a plan Π ′ = [Q ′ 0 ,Q ′ 1 ,...,Q ′ k ] for G ′ fromQ ′ 0 = S toQ ′ k . Note thatQ ′ k is not necessarily equal to T . For an integer ℓ, a plan Π = [Q 0 ,Q 1 ,...,Q ℓ ] for G is said to be compatible with Π ′ ifQ 0 =Q ′ 0 ,Q ℓ [i] =Q ′ k [i] for each agent i withQ ′ k [i] ̸= b, andQ ℓ [i] ∈ u,v for each agent i with Q ′ k [i] = b. By induction on k, we show that there is a plan Π for G compatible with Π ′ . The base case k = 0 is straightforward. Consider the in- ductive case k > 0. Let Φ ′ = [Q ′ 0 ,Q ′ 1 ,...,Q ′ k−1 ]. Since Φ ′ is a plan fromQ ′ 0 toQ ′ k−1 , there is a plan Φ = [Q 0 ,Q 1 ,...,Q ℓ ] for G compatible with Φ ′ , by the induction hypothesis. We extend this plan to construct a plan Π for G compatible with Π ′ . Consider agent i ∈ A. It is clear that if Q ′ k−1 [i] ̸= b and Q ′ k [i] ̸= b hold, then the same move can be performed in G, that is, defineQ ℓ+1 [i] = Q ′ k [i]. SinceQ ℓ [i] = Q ′ k−1 [i], this move is valid. Otherwise, Q ′ k−1 [i] = b or Q ′ k [i] = b holds. If Q ′ k−1 [i] = b and Q ′ k [i] = b, it suffices to specify that Q ℓ+1 [i] =Q ℓ [i], which force i to stay the former location. Now we explain the case where one ofQ ′ k−1 [i] andQ ′ k [i] is b, and the other is a neighbor of b. By symmetry, suppose thatQ ′ k−1 [i] = b andQ ′ k [i] ∈ N (b). Recall that u and v are contracted to b, and hence N (b) = N (u)∪ N (v)\u,v. Suppose thatQ ℓ [i] = u. IfQ ′ k [i] ∈ N (u), agent i can move to Q ′ k [i], that is, define Q ℓ+1 [i] = Q ′ k [i]. If Q ′ k [i] ∈ N (v), agent i moves to v first, and then move to Q ′ k [i] at the next step. In other words,Q ℓ+1 [i] = v andQ ℓ+2 [i] =Q ′ k [i]. Note that the agents not located at u or v at step ℓ + 2 remain at their current positions. The case where Q ℓ [i] = v is analo- gous. It is obvious that Π = [Q 0 ,Q 1 ,...,Q ℓ ,Q ℓ+1 ,Q ℓ+2 ] is compatible with Π ′ . Moreover, since the agents on planets P at steps ℓ + 1 and ℓ + 2 followQ ′ k [i], we conclude thatQ ℓ+1 andQ ℓ+2 are galactic independent. Next, we discuss the correctness of Reduction rule 2. To this end, we give two lemmas that impose a constraint on plans in G ′ . Lemma 6. Let Π = [Q 0 ,Q 1 ,...,Q ℓ ] be a plan from S to T for G ′ . Then, Π can be transformed to a plan Π ′ = [Q ′ 0 ,Q ′ 1 ,...,Q ′ ℓ ′ ] for G such that no two consecutive configu- rations have an agent in the neighborhood of b. Proof. Consider a step t such thatQ t ∩ N (b) ̸= ∅. We now give five intermediate configurationsQ 1 t ,Q 2 t ,Q 3 t ,Q 4 t ,Q 5 t be- tweenQ t andQ t+1 : Q 1 t [i] = bifQ t [i]∈ N [b] Q t [i]otherwise Q 2 t [i] = bifQ t [i]∈ N [b] Q t+1 [i]otherwise Q 3 t [i] = bifQ t [i]∈ N [b] ∨ Q t+1 [i]∈ N [b] Q t+1 [i]otherwise Q 4 t [i] = bifQ t+1 [i]∈ N [b] Q t [i]otherwise Q 5 t [i] = bifQ t+1 [i]∈ N [b] Q t+1 [i]otherwise Note that the galactic independence of these five configurations is followed by the galactic indepen- dence of Q t and Q t+1 .We claim that the sequence [Q t ,Q 1 t ,Q 2 t ,Q 3 t ,Q 4 t ,Q 5 t ,Q t+1 ] is a plan for G and satisfies the required conditions, that is, no two consecutive config- urations have an agent in the neighborhood of b. For this purpose, we classify the agents into the following four types: 1. Q t [i]∈ N [b] ∧ Q t+1 [i]∈ N [b], 2. Q t [i]∈ N [b] ∧ Q t+1 [i] /∈ N [b], 3. Q t [i] /∈ N [b] ∧ Q t+1 [i]∈ N [b], and 4. Q t [i] /∈ N [b] ∧ Q t+1 [i] /∈ N [b], and verify their locations in each configuration. For each agent i, a sequence [Q t [i],Q 1 t [i],Q 2 t [i],Q 3 t [i],Q 4 t [i],Q 5 t [i], Q t+1 [i]] of vertices consists of: 1. [Q t [i],b,b,b,b,b,Q t+1 [i]], 2. [Q t [i],b,b,b,Q t [i],Q t+1 [i],Q t+1 [i]], 3. [Q t [i],Q t [i],Q t+1 [i],b,b,b,Q t+1 [i]], and 4. [Q t [i],Q t+1 [i],Q t+1 [i],Q t+1 [i],Q t [i],Q t+1 [i],Q t+1 [i]]. Thus, every agent either moves to an adjacent vertex along an edge or stays at its current vertex, ensuring the reachability. Moreover, if agent i is located in a neighbor of b, it moves out of the open neighborhood of b in the next step. The lemma follows by applying this procedure to every t∈ [0,ℓ− 1] such that Q t ∩ N (b)̸=∅ holds. In what follows, we transform the plan on G ′ obtained above into one that satisfies additional restrictions on S pro t and S abs t . Lemma 7. Suppose that G ′ is obtained by applying Reduc- tion rule 2 to replace a component C with a black hole b. Let Π = [Q 0 ,Q 1 ,...,Q ℓ ] be a plan for G ′ from S to T . One can transform it to a plan Π ′ = [Q ′ 0 ,Q ′ 1 ,...,Q ′ ℓ ′ ] with the following two conditions: 1. no two consecutive configurations of Π ′ have an agent in the neighborhood of b, and 2. |S pro t | +|S abs t |≤ 1 for every t∈ [0,ℓ ′ ]. Proof. Assume that Π satisfies condition 1 by applying Lemma 6. Consider a step t ∈ [1,ℓ] such that |S pro t | + |S abs t | > 1. Note that it holds that t /∈ 1,ℓ by the fact that b /∈ N [S ∪ T ], and |S pro t | = 0∨|S abs t | = 0 by condi- tion 1. Here, by symmetry, we assume that |S abs t | > 0 and |S pro t | = 0. Let i 1 ∈ S abs t be an agent, and consider the se- quence [Q t−1 ,Q 6 t−1 ,Q 7 t−1 ,Q t ] with the following: Q 6 t−1 [i] = bif i∈ S abs t \i 1 Q t−2 [i]otherwise Q 7 t−1 [i] = bif i∈ S abs t \i 1 Q t−1 [i]otherwise. In other words, each agent i /∈ S abs t \ i 1 follows the se- quence of moves Q t−1 [i] → Q t−2 [i] → Q t−1 [i] → Q t [i], and i∈ S abs t \i 1 moves fromQ t−1 [i] to b =Q t [i]; hence, this sequence of configurations is a plan for G ′ . Moreover, the plan satisfies the condition 1, since Q t−2 ∩ N (b) = ∅ holds from Lemma 6. By inserting this subsequence between Q t−1 and Q t , the size of S abs t decreases by one. Applying this process it- eratively, we eventually achieve |S abs t | = 1. We thereby obtain a sequence in which the number of steps satisfying |S pro t | + |S abs t | > 1 is strictly smaller than that of Π. By symmetry, a similar argument is applicable to the case where |S abs t | = 0 and |S pro t | > 0. Therefore, we can obtain a plan for G ′ that satisfies conditions 1 and 2. This completes the proof. We now demonstrate that Reduction rule 2 is safe using the aforementioned lemmas. Lemma 8. Reduction rule 2 is safe. Proof. Let G 1 be a graph, and let G 2 be a graph after Reduc- tion rule 2 is applied to a component C. By Lemma 4, if there is a plan from S to T for G, then there is a plan for G ′ . Assume that there is a plan Π = [Q 0 ,Q 1 ,...,Q ℓ ] for G 2 from S to T . By Lemma 7, we can assume that Π satisfies the following two conditions: (i) no two consecutive config- urations of Π have an agent in the neighborhood of b, and (i)|S pro t | +|S abs t | ≤ 1 for every t ∈ [0,ℓ]. Consider a vertex v ∈ L k ∩C withk ≥ 2n+3, and a shortest pathR length from v to a vertex u∈ S∪T . Note that for every pair of distance-1 configurations X and Y in R with|X| = |Y| ≤ n, there is a plan from X to Y that uses only the vertices of R. Accord- ingly, for an agent i that moves to b at step t on G 2 , we will instead route i to a vertex on the path R on G 1 . Here, for an agent i on G 2 and step t ′ ∈ [0,ℓ − 1], if Q t ′ [i]̸= b andQ t ′ +1 [i]̸= b, then the same move can be done on G 1 , since G[V (G 1 ) ] is isomorphic to G[V (G 2 )\b]. Now we assume that Q t ′ [i] = b or Q t ′ +1 [i] = b. Since b /∈ S∪ T , there is a step t ≤ t ′ + 1 such thatQ t [i] ∈ N (b) and Q t+1 [i] = b. We now show that the agent i on G 1 can imitate such a move on C, that is, agent i can move to some vertex of R while ensuring that every other agent j currently contained in C is also located at some vertex in R. Consider shortest paths from Q t [i] to every vertex of R, and let R ′ be the shortest one among them. We move agent i along this path R ′ and place it at a vertex r ′ on the path R. Once i has moved to some vertex of C, for each agent j ̸= i contained in N [C]\ C, we move it to Q t+1 [j]. This ensures that i and j are never on adjacent vertices, since Q t+1 [j] /∈ N [b] on G 2 , and thus Q ′ t+1 [j] /∈ N [C] on G 1 . Before i reaches the endpoint r ′ , agent i could become ad- jacent to an agent k on R, violating the independence. In this case, i is at the vertex v ′ on R ′ adjacent to r ′ . Note that N (v ′ )∩ R consists of at most three consecutive vertices on R; otherwise, we would obtain a path shorter than R via v ′ . Accordingly, we ensure that no agent is placed on N (v ′ )∩R before agent i moves to v ′ . Here, after removing at most three vertices in N (v ′ )∩ R from R, there remain at least 2n− 2 vertices, which can accommodate an independent set of size n− 1. Then, we move the agents on R so that they form this independent set. After completing these moves, agent i can move from v ′ to r ′ . Therefore, the agent i on G 1 can imitate a move on G 2 from a vertex in N (b) to b. Until agent i moves from b to a vertex in N (b) on G 2 , it can be kept at some vertex of R. This holds because, whenever another agent j moves to b, agent j can imitate its move on G 2 . From here on, we consider the reverse move, that is, i moves from b to a vertex in v ∈ N (b) at step t 1 . we try to move i from a vertex on R to v ∈ N (b). However, since there may be other agents on R, it might be impossible to move i without violating the independence constraint. Neverthe- less, by considering the shortest path R ′ from v to a vertex R again, we can see that at least one agent j can be moved to v. Then, consider the sequence obtained by swappingQ t ′ [i] and Q t ′ [j] in every configurationQ t ′ with t ′ ≥ t 1 . This sequence is also a plan from S to T on G 2 , and it yields a sequence in which j moves to v on G 1 . Here, every agent i holds that Q ℓ [i] /∈ N [b], since b /∈ N [T ]. Eventually, every agent moves from b to some planet. At some step, agent i can imitate the move of some agent moving from b to N (b). This completes the proof. Lemma 5 and Lemma 8 immediately lead to Lemma 1. We bound the running time to obtain an instance after ap- plying Reduction rules 1 and 2 until no updates are possi- ble. We first compute the layers in time O(|V (G)| +|E(G)|) using Breadth-first search. Reduction rule 1 searches for adjacent black holds and Reduction rule 2 contract a com- ponent to a vertex.Thus, each application of the rules requires O(|V (G)| + |E(G)|) time. The running time is O(|V (G)| +|E(G)|). We now provide an upper bound on the size of the obtained instance. We first claim that the size of B is bounded by ∆·|P|. Since there is no edge b 1 b 2 ∈ B such that b 1 ,b 2 are both in B, the remaining black hole b∈ B holds that N (b)⊆ P . Moreover, we can see that the degree of vertex v ∈ P does not increase by applying Reduction rules 1 and 2. Thus,|B| can be upper bounded by|N [P ]|≤ ∆|P|. It remains only to bound|P|. Theorem 1. GMAPF admits a kernel with ∆ O(n) n vertices. Proof. Consider the instance obtained after applying the rules until no updates are possible. Since every planet p ∈ P is contained in the layer L k with k ≤ 2n + 2, the size of P is bounded from above by P 0≤k≤2n+2 |L k |. Note that, since the maximum degree of G[P ] is at most ∆, we have|L k | ≤ ∆·|L k−1 | for eachk ∈ [1, 2n+2]. It follows fromL 0 = S∪T that X 0≤k≤2n+2 |L k | ≤ X 0≤k≤2n+2 |S∪ T|· ∆ k ≤ 2n· ∆ 2n+3 − 1 ∆− 1 ≤ 2n· ∆ 2n+3 . This completes the proof. Here, when an induced grid graph is given, the above bound is overestimated. Any vertex within distance k from a vertex v lies inside the grid of width 2k centered at v. Thus, P 0≤k≤2n+2 |L k | = O(|S∪ T|· n 2 ) = O(n 3 ). This leads to the following theorem. Theorem 2. GMAPF admits a kernel with O(n 3 ) vertices when an induced grid graph is given. An FPT algorithm for 1IUMAPF immediately follows. Corollary 1. IUMAPF admits an FPT algorithm when pa- rameterized by ∆ + n. Proof. Let (G,S,T ) be an instance of 1IUMAPF. We trans- form it to an instance (G ′ ,S,T ) of GMAPF, where a set of planets is V (G) and a set of black holes is ∅. By applying Theorem 1, we obtain a kernel with ∆ O(n) n vertices. Then the claim follows from a brute-force search. Remark. We note that the lemma established above does not specialize to GMAPF and also applies to GALACTIC TO- KEN SLIDING, a galactic variant of TOKEN SLIDING. There- fore, we can say that GALACTIC TOKEN SLIDING admits a kernel with ∆ O(n) n vertices in general, and with O(n 3 ) ver- tices when an induced grid graph is given. This claim im- proves the known upper bound on the kernel size ∆ O(n 2 ) n in [ Bartier et al., 2023 ] . B Omitted pseudocode in Section 6 In order, Algorithms 3 to 6 illustrate pseudocodes for dead- lock detection and resolution, detection of SWAP(i,v), the strategy of IU-LaCAM, and a modified configuration gener- ator using IU-PIBT. All implementations are shown in the code appendix. Algorithm 3 detect a deadlock starting with i Input: agent i∈ [n], vertex u∈ N [Q from [i]] Output: list of agents L, that there is a deadlock, or⊥ (means empty list) 1: v ← next r (u,g(i))▷ dist(u,v) = r 2:if∃j s.t. Q from [j] = v∧j ̸= i∧Q to [j] =⊥ then L← [j] ▷∃j ⇒ dist(Q from [i],u) = r + 1 3:else return⊥ 4:while j ̸= i do 5:v ′ ← next r+1 (Q from [j],g(j)) 6:if¬(∃j s.t. Q from [j] = v∧Q to [j] =⊥) then return⊥ 7:else if∃a s.t. L[a] = j then return⊥ 8:else L← L + [j] 9: return L Algorithm 4 rule 2: swap detection Input: agent i and vertex v ∈ N[Q from [i]] Output: an agent j ∈ A that needs to swap the target 1: u← next r (v,g(i))▷ dist(u,v) = r 2:if∃j s.t. Q from [j] = u∧Q to [j] =⊥ then 3:if g(j) = u then return j ▷∃j ⇒ dist(Q from [i],u) > r 4: return⊥ Algorithm 5 LaCAM for rIUMAPF 1: initialize Open , Explored 2: N init ←⟨S,JC init K,g init ,B init ⟩ ▷C init ,B init : no constraints ⟨config, constraints, assignment, bannedlist⟩ 3: OPEN.push(N init ); Explored[S] =N init 4:while OPEN̸=∅ do 5:N ← OPEN.top() 6:ifN.config = T then return plan 7:ifN.constraints =∅ then OPEN.pop(); continue 8:C←N.constraints.pop() 9:updateconstraints(N,C)▷ constraints synthesis 10:Q new ,g new ← configurationgenerator(N,C) 11:ifQ new =⊥ then continue 12:detectlivelockandreassignment(Q new ,g new ) ▷ for resolving livelock 13:if Explored[Q new ]̸=⊥ then continue 14:N new ←⟨Q new ,JC init K, g new , B init ⟩ 15:OPEN.push(N new ); Explored[Q new ] =N new 16: return NOPLAN 17:function configurationgenerator(N,C) 18:DefineQ to [i] : = v if (i,v)∈C else⊥ ▷C: list of (agent, destination) 19:Q,g ←N.config,N.g 20:Q new ,g new ← IU-PIBT(Q,T,N.g) initialzed withQ to 21:returnQ new ,g new Algorithm 6 Configuration generator for LaCAM Input: configurationQ from , constraintsC, goals T , temporal tar- get assignment g : [1,n]→ T , order P of agents Output: configurationQ to , new assignment g ′ ▷ initialized by ((⊥) n ,g,p) 1: for (i,v)∈C doQ to [i] = v 2:if∃i,j ∈ A s.t. i̸= j∧ dist(Q to [i],Q to [j])≤ r then 3:return⊥,g▷ not a distance-r independent config 4:for i∈ P do▷ respect the order P , indicates the priority 5:ifQ to [i] =⊥ then IU-PIBT(i, [ ],g) 6:if∃i,j ∈ A s.t. i̸= j∧ dist(Q to [i],Q to [j])≤ r then 7:return⊥,g▷ not a distance-r independent config 8: returnQ to ,g C Omitted Proofs in Section 6 For a timestep τ , letQ τ and g τ denote the inputsQ from and g at τ . Moreover, we use the inverse function g −1 τ of g τ . For a vertex subset S of a graph G, let G[S] denote the subgraph induced by S. We also use a notation used in Appendix A; for a graph G = (V,E), we define the open neighborhood N (v) of v ∈ V as N (v) = w ∈ V | vw ∈ E, and N (V ′ ) for V ′ ⊆ V as N [V ′ ]\ V ′ for the sake of simplicity. Lemma 2 provides the soundness of Algorithm 1. We assume that IU-PIBT(i,S,∗) returns a value after all recursive call IU-PIBT(∗,S + [i],∗) return values. Thus, for every pair of agents x,y ∈ [n], Q to [x] and Q to [y] are not determined simultaneously. Consequently, we can con- struct a ordering P = (a 1 ,a 2 ,...,a n ) for [n] based on the time at which the procedure IU-PIBT(x,S,g) return a value VALID or INVALID for each x ∈ [n]. We write i < P j when a i < a j , for simplicity. Also, we can see that once IU-PIBT(x,∗,∗) returns a value inVALID,INVALID for agent x∈ A, it will not be called again for agent x. Lemma 2. If Q from is distance-r independent, then Q to is reachable and a distance-r independent configuration. Proof. We prove the statement by induction using the or- dering P , which is sorted in ascending order by the time the IU-PIBT returns a value. Note that, it is clear that if IU-PIBT(i,S,∗) recursively calls IU-PIBT(j,S + [i],∗), then j < P i. Let Q k be a configuration defined as Q 0 = Q from and Q k = Q to [a c ] | 1 ≤ c ≤ k ∪ Q from [a c ] | k + 1≤ c≤ n for k ≥ 1. Now we show that Q k is distance- r independent for every k ∈ [n]. Note that Q k represents the hypothetical configuration where every agent i without a determined destination remains at their current locations Q from [i]. The base case k = 0 is trivial since Q 0 = Q from holds the condition by the initial assumption. We now show that the claim holds for k = k ′ + 1, assum- ing that Q k ′ is distance-r independent for some integer k ′ ∈ [0,n− 1]. Consider the case when IU-PIBT(a k ′ +1 ,S,g) = INVALID. We can easily see that Q k ′ +1 holds the claim, sinceQ to [a k ′ +1 ] =Q from [a k ′ +1 ], thus Q k ′ +1 = Q k ′ . We next move to the case IU-PIBT(a k ′ +1 ,S,g) = VALID: a k ′ +1 is assigned to a vertex v ∈ N [Q from [a k ′ +1 ]]. Since IU-PIBT(a k ′ +1 ,S,g) returns VALID only when there is no agent i ∈ A \ a k ′ +1 holds that dist(Q to [a k ′ +1 ],Q to [i]) ≤ r or dist(Q to [a k ′ +1 ],Q from [i]) ≤ r ∧ i ∈ S. Here, every index i ∈ [k ′ + 2,n] holds either IU-PIBT(a i ,∗,∗) has already been called or it has not. Let D be the set of agents a i , whose index i belongs to the for- mer. We need to prove that Q k ′ +1 is distance-r independent if all of the agent i ∈ D holds that dist(Q from [i],v) ≥ r, since agent a i /∈ D such that i ∈ [k ′ + 2,n] satisfies dist(v,Q from [i]) > r and dist(v,Q from [i]) > r from line 18. Now we show that every agent x ∈ D is an element of S, that is, every agent i ∈ D holds that Q from [i] /∈ N r [v]. We assume that there is an agent a x ∈ D such that a x /∈ S, for a contradiction. If there is a multiple agent that satisfies the condition, let a x be the minimum index based on P . Consider the call of function IU-PIBT(a x ,S ′ ,∗). Here, consider the function call with a list S ∗ , where S ∗ is the longest common prefix of S and S ′ . Since a list S is modified only in Line 17, there is a call IU-PIBT(a y ,S ∗ ,∗) and IU-PIBT(a z ,S ∗ ,∗), where a y and a z correspond to the first characters of the re- maining substrings obtained by removing their longest com- mon prefix from S and S ′ , respectively. If y < P z, then IU-PIBT call IU-PIBT(a z ,S ∗ ,∗) after IU-PIBT(a y ,S ∗ ,∗) returns a value; a contradiction to a x ∈ D. Thus, we assume that z < P y, from the maximality of S ∗ . Here, a similar discussion can be applied; a call IU-PIBT(a y ,S ∗ ,∗) occurs after IU-PIBT(a z ,S ∗ ,∗) returns a value. Since a z is an el- ement of S ′ , we can see that IU-PIBT(a z ,S ∗ ,∗) returns a value after IU-PIBT(a x ,S ′ ,∗) returns a value. Therefore, we have x < k ′ + 1, a contradiction to x≥ k ′ + 2. There is no agent j ∈ S such thatQ from [j] ∈ N r [v]. This directly leads to the proof of claim: Q k ′ +1 is distance-r inde- pendent when IU-PIBT(a k ′ +1 ,S,g) = VALID. This com- pletes the proof. For a running time, we show the following. Lemma 3. IU-PIBT outputsQ to in ∆ r ∆(r + 1)n + α time, where α denotes the time for resolution of deadlock. Proof. Within one step, the function IU-PIBT is called ex- actly n times, either recursively or by the top-level procedure. Now we analyze the time for each for-loop in line 10. It is sufficient that we first compute N r [v], and for every vertex u ∈ N r [v], store the agents that satisfy either Q from [j] = u or Q to [j] = u. This can be done in at most O(∆ r ) time for each, since |N r [v]| ≤ ∆ r . Moreover, the swap detection in line 14 needs O((r +1)∆) time, since the function next(u,v) returns a vertex in O(∆) time among at most ∆ neighbors. Thus, each for-loop in line 10 takes O(∆ r + (r + 1)∆) = O(∆ r (r + 1)) time. Since|N [Q from [i]]| ≤ ∆ + 1 = O(∆), and sorting the vertices in N [Q from [i]] takes O(∆) time, the running time for each call of IU-PIBT isO(∆ r ∆(r+1)) time. This completes the proof of Lemma 3. Note that the theoretical upper bound of α is O(n 3 ); how- ever, this is too conservative in practice, as we can see in the experiment. Then we proceed to the case when r = 0. To this end, we prove it by showing that the size of a set T τ : = v | ∃i ∈ A s.t.Q to [i] = g(i) = v is non-decreasing, and increases by at least one in finite steps. Note that the closed neighbor N r [v] = N 0 [v] is exactly v. Let v τ be a goal with the highest priority in step τ . Lemma 9. Let v ∈ T τ be a vertex. If there is an agent i = g −1 τ (v) such that Q from [i] = v, then there is an agent i ′ = g −1 τ+1 (v) such thatQ to [i ′ ] = v. Proof. Consider an arbitrary vertex v ∈ T τ . If the top-level procedure calls IU-PIBT for agenti : = g −1 τ (v), then IU-PIBT determines Q to [i] = Q from [i] and terminates, and this does not change in step τ . Thus, g −1 τ+1 (v) = g −1 τ (v) = i and Q τ+1 [i] = Q τ [i] = v holds; we are done. Note that such an agenti can not be included in any deadlock. Consider the case when IU-PIBT for i is called recursively by another agent j. Here, since r = 0, it is clear that Q from [j] ∈ N [Q from [i]]. Since next 0 (v,u) = v for every vertex u ∈ V , agent i is exactly the agents SWAP(j,v). Thus, the target swap oc- curs between i and j. If IU-PIBT for i returns INVALID, then Q to [i] = Q from [i] = v, and g −1 (v) = i.Thus, Q τ+1 [i] = Q τ [i] = v and g −1 τ+1 (v) = i; we are done. Other- wise,Q τ+1 [j] =Q to [j] =Q from [i] =Q τ [i] and g −1 (v) = j, thusQ τ+1 [g −1 τ (v)] = v. This completes the proof. Here, we observe the following observation that is the same as the one in rotation-free PIBT [ Okumura et al., 2022 ] . A proof is omitted since the discussion is almost identical to Lemma 6 of [ Okumura et al., 2022 ] . Observation 1. Let i be an agent, and assume that i calls IU-PIBT(j,S,∗) recursively.If there is a path P = (v 1 ,v 2 ,...,v k ) such that, there is a sequence of agents (j = a 1 ,a 2 ,...,a k−1 ) that holds a x /∈ S ∧ Q from [a x ] = v x ∧ Q to [a x ] = ⊥ ∧ v x+1 ∈ N (v x ) for x ∈ [1,k − 1], and there is no agent a such that Q from [a] = v k , then IU-PIBT(j,S,∗) returns VALID. Lemma 10. Assume that the input graph G has no edge uv ∈ E such that G[V \u,v] is not connected, and|A| < |V|. Then, for a step τ , if Q τ [g −1 (v τ )] ̸= v τ , then there is an agent i ′ = g −1 (v τ+1 ) such that dist(Q τ ′ [i τ+1 ],g τ (i τ )) ≤ dist(Q τ [i τ ],g τ (i τ ))− 1. Proof. First, observe that resolving a deadlock decreases the distance dist(Q from [g −1 (v τ )],v τ ). Therefore, let i ∗ be the agent whose p ′ (g(i)) is the highest in line 4; then the distance fromQ τ [i ∗ ] to v τ does not exceed that fromQ τ [g −1 τ (v τ )] to v τ . When Q from [i ∗ ] = v τ , we have Q τ [g −1 (v τ )] ̸= v τ , and hence dist(Q τ [g −1 (v τ )],v τ ) > 1; therefore, the claim holds. Consider the case whenQ from [i ∗ ]̸= v τ . Now we show that dist(Q τ [i ∗ ],v τ ) > dist(Q τ+1 [g −1 τ+1 (v τ )],v τ ) (♠). Here, we consider a vertex v 1 : = next(Q from [i ∗ ],g(i)). First, assume that there is no agent j such thatQ from [j] = v 1 . Thus, there is no agent j ̸= i ∗ such that Q to [j] = v 1 since i ∗ has the highest priority; we are done since the value f = TRUE in line 19. Thus, we obtained (♠) in this case. Next, assume that there is an agent j such thatQ from [j] = v 1 . If j holds thatQ from [j] ̸= g(j), then there is a path from v 1 to an arbitrary vertex, not going throughQ from [i ∗ ]. Since there is a vertex w such that there is no agent on w, we can find a path desired by Observation 1. Thus, a call of IU-PIBT for j returns VALID, then IU-PIBT for i ∗ returns VALID, and determine g(i ∗ ) = v τ andQ to [i ∗ ] = v 1 (♠). We proceed to the case when Q from [j] = g(j) = v 1 . In this case, g −1 (v τ ) may not be i ∗ , by swap operations in line 14. Despite this, we now claim that there is a vertex u such thatQ to [g −1 (v τ )] = u and dist(u,v τ ) < dist(Q from [i ∗ ],v τ ). Consider the shortest path [Q from [i ∗ ],v 1 ,...,v τ ], determined by the function next, and let R = [Q from [i],v 1 ,v 2 ,...v ℓ ,v ′ ] be a subpath of the path above such that: Q from [g −1 (v c )] = v c for every c ∈ [1,ℓ] and g(a) ̸= v ′ for an agent a 1 such that Q from [a 1 ] = v ′ and w be an arbitrary vertex such that there is no agent currently on w. Note that v τ is not included in R, since g is a bijection: no agent j ̸= i ∗ satisfies g(j) = v τ . First consider the case when R = [Q from [i ∗ ],v 1 ,v ′ ]. Then, there is a path fromQ from [i ∗ ] to w, going through v 1 and v ′ , since there is a path from v ′ to w in G[V \Q from [i ∗ ],v 1 ]; sufficient to combine the path with [Q from [i ∗ ],v 1 ,v ′ ]. Thus, by Observation 1, IU-PIBT(i ∗ ,ε,∗) returns VALID. More- over, Q to [g −1 τ (v τ )] = v ′ holds for an agent g −1 τ (v τ ). Also, the distance dist(v ′ ,v τ ) = dist(Q from [i ∗ ],v τ ) − 2; implies (♠) in this case. We move to the case when the length of R is more than three. Here, consider a set of vertices R ′ = Q from [i] ∪ p c | c ∈ [1,ℓ] on the path R, and an induced subgraph G[V \ R ′ ]. We claim that there is a vertex u ∈ N (R \ Q from [i],v 1 )\v 1 such that there is a path from u to w and not going through the vertices in R. This implies that, IU-PIBT(i ∗ ,ε,∗) returns VALID. First, consider the case when G[V ′ ] is connected. Then, every vertex u 1 ∈ N (R\Q from [i])\v 1 can be chosen as u, since there is a path between u 1 and w. Consider the case when G[V \ R ′ ] is not connected; this consists of more than one component. We partition the vertex sets of the com- ponents into the following two: let C 1 be a set of vertices of the component that contains w, and C 2 : = V \ (R ′ ∪ C 1 ). Consider an arbitrary vertex v c ∈ R ′ . If there is a vertex u 2 ∈ N (v c ) ∩ C 1 , then we can find a vertex appropriate for u. Thus, if there is a vertex v c ∈ R \ Q from [i],v 1 such that N [v c ] ∩ C 1 ̸= ∅, we obtain an appropriate ver- tex. Otherwise, we have N (R ′ )\v 1 ∈ C 2 , every vertex in (R\Q from [i],v 1 )∪C 2 has no neighbor in C 1 . This implies G[V \Q from [i],v 1 ] is not connected, a contradiction to the fact that there is no edge uv ∈ E such that G[V \u,v] is disconnected. Now we evaluate the distance dist(u,v τ ). Since v c ∈ R ′ is a vertex on the shortest path from Q from [i ∗ ] to v τ and c ̸= 1, the distance dist(v c ,v τ ) is less than or equals to dist(v 2 ,v τ ) = dist(Q from [i ∗ ],v τ ) − 2. Therefore, u is a neighbor of some vertex v C ∈ R ′ , the distance dist(u,v τ )≤ dist(Q from [i ∗ ],v τ )− 2 + 1 = dist(Q from [i ∗ ],v τ )− 1. Assume that there is an agent a 2 on u such that its target is not u, we have thatQ to [g −1 τ+1 (v τ )] = u, implies (♠). Other- wise, the target vertex of a 2 is u. In this case, a similar discus- sion can be applied to the shortest path fromu tov τ . We again obtain a vertex u 1 such that dist(u 1 ,v τ ) ≤ dist(u,v τ )− 1. By repeatedly applying the discussion above, we obtain a ver- tex u ∗ such that there is no agent on u ∗ , or there is an agent on u ∗ that is not currently on its target. Moreover, u ∗ is a vertex that is closer to v τ than u (♠). These complete the proof. Theorem 3. IU-PIBT is complete for 0IUMAPF, when the given graph has no edge uv ∈ E such that G[V \u,v] is not connected. Proof. Consider the target v ∈ T with the highest priority at some step t. Then, v remains the target with the highest priority until some step t ′ such that there exists an agent i withg(i) =Q t ′ [i] = v. Thus, by Lemma 10, there is an agent g(i) =Q t ′ [i] = v in step τ , where τ−t≤ n. In this step,|T τ | increaces at least one in step τ . This holds for an arbitrary step. Thus, a sequence (|T τ |) of integers is non-increasing with only finitely many ties; hence, it reaches the upper bound n in finite steps. Since|T τ | = n impliesQ τ = T , all agents reaches their assigned target; this completes the proof. Theorem 4. IU-LaCAM is complete for rIUMAPF. Proof. We show that IU-LaCAM can generate all reachable configurations for every configurationQ in finite time. This leads to the fact that, for every vertex subset T such that there is a plan from S to T , a plan from S to T can be obtained by traversing a generated reachable configuration from S, im- plying the completeness, since the number of configurations is bounded by 2 |V (G)| . We proceed to prove the initial claim. To this end, we prove the following: (i) the number of node reinserts (in line 8) is bounded, and (i) the number of possible constraints are bounded. For (i), we show that P i∈A |B[i]| is strictly increases when if-statement in line 3 is true. It is clear that D is not empty; otherwiseQ = T , thus a plan fromS toT is already obtained. Therefore, there is an agent such that|B[i]| increases, derives that P i∈A |B[i]| increases. The upper bound of P i∈A |B[i]| is|A| 2 , thus the number of node reinserts is also bounded by |A| 2 . Next, for (i), constraints have information that includes a subset of agents and their next locations. Here, the number of subsets of agents is bounded by 2 |A| , and the number of candidate next locations is bounded by ∆ + 1 for each agent. Thus, the number of constraints is bounded by 2 |A| · (∆ + 1) |A| . We show that IU-LaCAM can generate all reachable con- figurations for every configurationQ in finite time. This com- pletes the proof.

Instant research discovery