Distance-Constrained Unlabeled Multi-Agent Pathfinding
Takahiro Suzuki, Yuma Tamura, Keisuke Okumura · 2026
Read Distance-Constrained Unlabeled Multi-Agent Pathfinding by Takahiro Suzuki, Yuma Tamura, Keisuke Okumura (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11503.txt.
Introduction
Takahiro Suzuki, Yuma Tamura and Keisuke Okumura study distance-constrained unlabeled multi-agent pathfinding. Agents must find collision-free paths between two sets while staying at pairwise distance at least r plus 1 at all times. That extra spacing rule, aimed at real-world coordination, makes deciding feasibility PSPACE-complete, unlike standard unlabeled MAPF, which is polynomial-time. The authors tackle it with reduction-based optimal algorithms using feasibility-preserving compression, plus a search built on a configuration generator. Despite the hardness, their algorithm handles hundreds of agents within practical time.
Catalog record
| CREATOR | Takahiro Suzuki, Yuma Tamura, Keisuke Okumura |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86363 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11503
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distance-Constrained Unlabeled Multi-Agent Pathfinding Takahiro Suzuki, Yuma Tamura, Keisuke Okumura Abstract We study a graph pathfinding problem Distance- r 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 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) 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{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. 1 Introduction Research on Multi-Agent Pathfinding ( MAPF ) has attracted considerable attention in the last decade, driven by the growing 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 18 ; one of them is the unlabeled (anonymous) version of MAPF , in which the agents are identical and a collision is defined as multiple agents simultaneously occupying the same vertex. This problem naturally arises in the scenario of homogeneous robots such as warehouse transport 12 , where we need to solve an integrated joint problem that optimizes goal assignment and path planning. Although MAPF has been widely studied, it often simplifies a collision by ignoring geometric interference, which hinders its direct application. For example, we need to address the agents that occupy more than one grid cell (for real-world deployment 10 ), safety margins (for drone planning 7 ), and delay tolerance (for robust execution 2 ). These issues motivate a formulation that goes beyond the standard one. These extensions can be naturally abstracted to a single 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 unlabeled MAPF ; given two vertex subsets, Distance- r Independent Unlabeled Multi-Agent Pathfinding ( r IUMAPF 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 21 , this generalization remains largely under-explored; no algorithm applies to general r\in\mathbb{N} , while an optimal polynomial-time algorithm is known for r=0 . Moreover, prior work 9 shows the \mathsf{PSPACE} -completeness for determining feasibility when r=1 . \mathsf{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, r IUMAPF remains practically motivated and poses a nontrivial algorithmic challenge. To this end, we propose two approaches to tackle r IUMAPF , respectively following common practice in MAPF : algorithms based on reduction , and configuration generator , which is a function that computes the next placements 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 optimal 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 15 and LaCAM 16 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 livelock detection technique to IU-PIBT, thereby quickly 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 complementary schemes for r IUMAPF and enable systematic study of it beyond classical Unlabeled MAPF . In what follows, we present a formulation, related work, algorithms, and evaluations 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 finite connected graph. For a pair of vertices u,v\in 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\in V , the closed neighborhood is N[v]=\{w\in V\mid vw\in E\}\cup\{v\} , and its degree is \textsf{deg}(v)=|N[v]|-1 . We extend the notation; let N_{r}[v] be a set of vertices u such that \dist(u,v)\leq r for an integer r\geq 0 . We define \Delta\coloneqq\max_{v\in V}\textsf{deg}(v) and \Delta_{r}\coloneqq\max_{v\in V}|N_{r}[v]| . For a vertex set V^{\prime}\subseteq V , the neighborhood is N[V^{\prime}]=\bigcup_{v\in V^{\prime}}N[v] . We define \textsf{next}^{r}(s,t)=\argmin_{v\in N[\textsf{next}^{r-1}(s,t)]}\dist(v,t) , and \textsf{next}^{0}(s,t)=s . We assume that \argmin deterministically returns exactly one vertex. We use a notation for a set of continuous integers: let [i,j] be a set \{i,i+1,\dots,j-1,j\} for i\leq j . Problem Definition. Let G be a graph and A=[1,n] be a set of n agents. A configuration \mathcal{Q}=(q_{1},\dots,q_{n})\in V^{n} is an assignment of each agent to a vertex. Although the configuration \mathcal{Q} is defined as a list of vertices, we may also refer to it as a (multi-)set of vertices for convenience. A configuration \mathcal{Q} is distance- r independent if there is no pair of agents i,j\in A such that \dist(\mathcal{Q}[i],\mathcal{Q}[j])\leq r . Given a set of initial and target vertices S,T\subset V with |S|=|T|=n and a radius r\in\mathbb{N} , r IUMAPF aims to find a finite sequence of configurations \Pi=[\mathcal{Q}_{0},\mathcal{Q}_{1},\ldots,\mathcal{Q}_{t^{\ast}}] , called a plan , where sets \mathcal{Q}_{0} and \mathcal{Q}_{t^{\ast}} equals to S and T , respectively. Throughout the plan, each agent can move to one of the closed neighbors of the current vertex, provided that every configuration remains distance- r independent. Formally, a plan \Pi from S to T in r IUMAPF holds: 1. \forall k\in[1,t^{\ast}],i\in A:\mathcal{Q}_{k}[i]\in N[\mathcal{Q}_{k-1}[i]] ( reachability ). 2. \forall k\in[0,t^{\ast}]:\mathcal{Q}_{k} is distance- r independent. Note that vertex conflicts and swap conflicts commonly used in MAPF 18 can be omitted due to the distance- r independence of configurations and anonymous setting. 3 Related work MAPF Extensions. Numerous MAPF variants move beyond 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 collision models, including continuous Euclidean distance constraints 1 , explicit geometric shapes 11 , and adaptations of Conflict-Based Search (CBS) 7 ; 11 . While these studies are closely related to our setting in that they generalize collision handling, our formulation represents feasible configurations