arxiv: 2605.11503 · v1 · submitted 2026-05-12 · 💻 cs.MA

Recognition: 1 theorem link

· Lean Theorem

Distance-Constrained Unlabeled Multi-Agent Pathfinding

Takahiro Suzuki , Yuma Tamura , Keisuke Okumura

Authors on Pith no claims yet

Pith reviewed 2026-05-13 02:13 UTC · model grok-4.3

classification 💻 cs.MA

keywords multi-agent pathfindingunlabeled MAPFdistance constraintsPSPACE-completenessgraph pathfindingmotion planningcollision avoidance

0 comments

The pith

Distance-constrained unlabeled multi-agent pathfinding has PSPACE-complete feasibility unlike standard MAPF.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a graph-based pathfinding task in which multiple agents must travel from start positions to goal positions while never coming closer than a fixed minimum distance r+1 from one another. This added separation rule turns the question of whether any valid set of paths exists into a PSPACE-complete decision problem, whereas the same question without the distance rule can be answered in polynomial time. The authors present two practical solution methods: one that compresses the problem while preserving feasibility and another that searches over valid agent configurations. Experiments indicate these methods scale to instances containing hundreds of agents.

Core claim

We introduce Distance-r Independent Unlabeled Multi-Agent Pathfinding, the task of finding collision-free paths for unlabeled agents on an undirected graph such that every pair of agents remains at least distance r+1 apart at every time step. We prove that deciding whether a solution exists is PSPACE-complete. We then give two complementary algorithms: reduction-based optimal solvers that employ a feasibility-preserving compression step, and a configuration-generator search procedure. Empirical evaluation shows that these algorithms solve instances with hundreds of agents in practical time.

What carries the argument

The static pairwise distance-r independence constraint on an undirected graph, enforced at every time step, together with a feasibility-preserving compression procedure that reduces the state space for optimal search.

If this is right

Feasibility of distance-constrained unlabeled MAPF cannot be decided in polynomial time unless PSPACE equals P.
Optimal solutions can be obtained by first compressing the instance while keeping feasibility unchanged.
Configuration-based search offers a scalable alternative when optimal cost is not required.
Instances with hundreds of agents remain solvable in practice despite the theoretical hardness.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Real-world multi-robot systems that enforce safety distances may inherit the same computational limits shown here.
The compression technique could be adapted to other persistent constraints such as time-window or capacity limits.
The contrast with standard unlabeled MAPF suggests that labeling agents or relaxing distance rules can restore tractability in some settings.

Load-bearing premise

The distance constraint is expressed as a fixed minimum separation between every pair of agents on a static undirected graph, and the hardness reduction does not introduce feasibility artifacts absent from real instances.

What would settle it

A polynomial-time algorithm that correctly decides feasibility for arbitrary r greater than or equal to 1 on arbitrary graphs would falsify the PSPACE-completeness result.

Figures

Figures reproduced from arXiv: 2605.11503 by Keisuke Okumura, Takahiro Suzuki, Yuma Tamura.

**Figure 2.** Figure 2: An example of the IU-PIBT’s operation when [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Figure 3: Two rules in IU-PIBT, when r = 1. Black arrows represent 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 assignment of targets. (b) Target swapping. When an agent j has already reached its goal … view at source ↗

**Figure 4.** 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 … view at source ↗

**Figure 5.** Figure 5: Time and makespan across three maps. For larger [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗

**Figure 6.** Figure 6: Average running time and suboptimality of TSWAP and [PITH_FULL_IMAGE:figures/full_fig_p008_6.png] view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Adding a distance constraint turns unlabeled MAPF PSPACE-complete while the authors still deliver solvers that handle hundreds of agents.

read the letter

The main thing to know is that this paper shows how a simple distance constraint turns unlabeled multi-agent pathfinding from polynomial-time decidable into PSPACE-complete. They back that up with two algorithmic approaches that still solve instances with hundreds of agents in practice. What is new here is the distance-r independent version and the hardness proof for the unlabeled case. Prior work on unlabeled MAPF did not include this constraint, so the jump in complexity is the core contribution. The reduction-based method with a feasibility-preserving compression step and the configuration generator search are presented as complementary ways to tackle the harder problem. The paper does well on the practical side. The empirical scaling to hundreds of agents is the kind of result that matters if you care about real deployments in robotics or logistics. Soft spots are limited and mostly about presentation. The abstract leaves the reduction construction and compression procedure undescribed, so a referee would need to verify that the hardness holds without artifacts that only appear in contrived graphs. The static pairwise distance model on undirected graphs is a reasonable choice but could be probed for how well it matches continuous motion in physical settings. Nothing in the stated claim looks internally inconsistent or circular. This paper is for the MAPF community and anyone building planners that must respect safety margins between agents. Readers who follow complexity results in pathfinding or need solvers that stay feasible under extra constraints will get value from it. It has enough new theory paired with usable algorithms to deserve a serious referee. I would recommend sending it for peer review.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Distance-r Independent Unlabeled Multi-Agent Pathfinding (DIUMAPF), a variant of unlabeled MAPF on graphs in which agents must maintain a static pairwise distance of at least r+1 at every time step. It proves that deciding feasibility is PSPACE-complete for r ≥ 1 (via a reduction that preserves feasibility), while the r = 0 case remains polynomial-time decidable. Two algorithmic approaches are presented: reduction-based optimal solvers that employ a feasibility-preserving compression procedure, and a configuration-generator search. Empirical results indicate that the methods scale to instances with hundreds of agents.

Significance. If the reduction is valid and the compression procedure correctly preserves feasibility, the work is significant because it demonstrates how a realistic generalization of collision avoidance changes the complexity class of an otherwise tractable problem, while supplying practical algorithms that remain effective at scale. The explicit contrast with standard unlabeled MAPF and the dual theoretical/practical treatment are strengths.

major comments (2)

[Hardness proof section] The reduction establishing PSPACE-completeness (presumably in the hardness section) must be checked to confirm that the distance-r constraint is enforced uniformly in the constructed instances and does not introduce spurious infeasibility artifacts not present in the source problem.
[Algorithm section on reduction-based solvers] The feasibility-preserving compression procedure (used in the reduction-based optimal algorithms) is load-bearing for correctness; its description should explicitly state the invariants maintained and any conditions under which compression is safe.

minor comments (2)

[Abstract] The abstract states the main complexity result and empirical scaling but omits even a one-sentence sketch of the reduction or the compression step; adding such a sketch would improve accessibility without lengthening the abstract appreciably.
[Experimental evaluation] Experimental reporting should include the range of r values tested, the graph families used, and the precise definition of 'practical timeframe' (e.g., timeout limits and hardware) to allow replication and assessment of the scalability claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation for minor revision. The comments are constructive and help strengthen the presentation of the theoretical and algorithmic contributions. We address each major comment below.

read point-by-point responses

Referee: [Hardness proof section] The reduction establishing PSPACE-completeness (presumably in the hardness section) must be checked to confirm that the distance-r constraint is enforced uniformly in the constructed instances and does not introduce spurious infeasibility artifacts not present in the source problem.

Authors: We have re-verified the reduction presented in Section 4. The construction is designed so that the distance-r constraint is enforced uniformly in every time step of the constructed DIUMAPF instance, with gadgets that directly encode the source problem's constraints. Any potential violation of the distance constraint in the target instance corresponds exactly to an invalid move or configuration in the source problem, without introducing extraneous infeasibility. To address the request for explicit confirmation, we will insert a short clarifying paragraph immediately after the reduction statement that restates this equivalence invariant. revision: yes
Referee: [Algorithm section on reduction-based solvers] The feasibility-preserving compression procedure (used in the reduction-based optimal algorithms) is load-bearing for correctness; its description should explicitly state the invariants maintained and any conditions under which compression is safe.

Authors: We agree that the current description of the compression procedure in Section 5.1 would benefit from greater explicitness. The procedure maintains the invariant that every feasible path in the original configuration space maps to a feasible path in the compressed space (and vice versa) while preserving the distance-r constraint. Compression is safe precisely when the underlying graph is undirected, the distance constraint is static, and there are no dynamic obstacles. We will revise the subsection to list these invariants and safety conditions in a dedicated paragraph. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The central claim is a PSPACE-completeness result for Distance-r Independent Unlabeled MAPF obtained via a standard graph-theoretic reduction from a known hard problem, contrasted against the established polynomial-time decidability of ordinary unlabeled MAPF. No equations, fitted parameters, self-definitional constructions, or load-bearing self-citations appear in the provided abstract or described derivation chain. The practical algorithms are presented as complementary heuristics that do not redefine or presuppose the complexity result. The reduction is asserted to preserve feasibility without circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract introduces no explicit free parameters, axioms, or invented entities beyond the standard definition of graph-based pathfinding and the new distance constraint.

pith-pipeline@v0.9.0 · 5436 in / 1021 out tokens · 35483 ms · 2026-05-13T02:13:04.838886+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

feasibility ... PSPACE-complete ... reduction-based optimal algorithms ... configuration generator-based search

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

[1]

In: IEEE International Conference on Robotics and Automation, ICRA 2024, Yokohama, Japan, May 13-17, 2024

Lukas Heuer and Luigi Palmieri and Anna Mannucci and Sven Koenig and Martin Magnusson , title =. 2024 , url =. doi:10.1109/ICRA57147.2024.10611005 , timestamp =

work page doi:10.1109/icra57147.2024.10611005 2024
[2]

Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T

Roni Stern and Nathan R. Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T. Walker and Jiaoyang Li and Dor Atzmon and Liron Cohen and T. K. Satish Kumar and Roman Bart. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks , booktitle = socs, year =

work page
[3]

Sturtevant , title =

Guni Sharon and Roni Stern and Ariel Felner and Nathan R. Sturtevant , title =. Artif. Intell. , volume =. 2015 , url =. doi:10.1016/J.ARTINT.2014.11.006 , timestamp =

work page doi:10.1016/j.artint.2014.11.006 2015
[4]

2022 , issn =

Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding , journal =. 2022 , issn =. doi:https://doi.org/10.1016/j.artint.2022.103752 , author =

work page doi:10.1016/j.artint.2022.103752 2022
[5]

2023 , url =

Baiyu Li and Hang Ma , title =. 2023 , url =. doi:10.1109/LRA.2023.3272272 , timestamp =

work page doi:10.1109/lra.2023.3272272 2023
[6]

Proceedings of the International Symposium on Combinatorial Search , author=

Which MAPF Model Works Best for Automated Warehousing? , volume=. Proceedings of the International Symposium on Combinatorial Search , author=. 2022 , month=. doi:10.1609/socs.v15i1.21767 , number=

work page doi:10.1609/socs.v15i1.21767 2022
[7]

Reconfiguration Using Generalized Token Jumping , booktitle = walcom, volume =

Jan Maty. Reconfiguration Using Generalized Token Jumping , booktitle = walcom, volume =. 2025 , url =

work page 2025
[8]

Boris de Wilde and Adriaan ter Mors and Cees Witteveen , title =. J. Artif. Intell. Res. , volume =. 2014 , url =. doi:10.1613/JAIR.4447 , timestamp =

work page doi:10.1613/jair.4447 2014
[9]

2023 , issn =

Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.artint.2023.103946 , author =

work page doi:10.1016/j.artint.2023.103946 2023
[10]

Mouawad , title =

Valentin Bartier and Nicolas Bousquet and Amer E. Mouawad , title =. J. Comput. Syst. Sci. , volume =. 2023 , doi =

work page 2023
[11]

2016 , doi =

Pavel Surynek and Ariel Felner and Roni Stern and Eli Boyarski , title =. 2016 , doi =

work page 2016
[12]

2023 , doi =

Keisuke Okumura , title =. 2023 , doi =

work page 2023
[13]

and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =

Cygan, Marek and Fomin, Fedor V. and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =. 2015 , isbn =

work page 2015
[14]

Non-Optimal Multi-Agent Pathfinding is Solved (Since 1984) , booktitle =

Gabriele R. Non-Optimal Multi-Agent Pathfinding is Solved (Since 1984) , booktitle =. 2012 , url =. doi:10.1609/SOCS.V3I1.18267 , timestamp =

work page doi:10.1609/socs.v3i1.18267 1984
[15]

LaValle , title =

Jingjin Yu and Steven M. LaValle , title =. 2012 , url =

work page 2012
[16]

URLhttps://doi.org/10.1609/aaai.v36i9.21266

MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search , volume=. Proceedings of the AAAI Conference on Artificial Intelligence , author=. 2022 , month=. doi:10.1609/aaai.v36i9.21266 , number=

work page doi:10.1609/aaai.v36i9.21266 2022
[17]

Subdimensional expansion for multirobot path planning , journal =

Glenn Wagner and Howie Choset , keywords =. Subdimensional expansion for multirobot path planning , journal =. 2015 , issn =. doi:https://doi.org/10.1016/j.artint.2014.11.001 , url =

work page doi:10.1016/j.artint.2014.11.001 2015
[18]

, title =

Yu, Jingjin and LaValle, Steven M. , title =. 2013 , booktitle = aaai, numpages =

work page 2013
[19]

and Kumar, T

Hönig, Wolfgang and Preiss, James A. and Kumar, T. K. Satish and Sukhatme, Gaurav S. and Ayanian, Nora , journal=tro, title=. 2018 , volume=

work page 2018
[20]

Spacing Policies for Adaptive Cruise Control: A Survey , year=

Wu, Cunxue and Xu, Zhongming and Liu, Yang and Fu, Chunyun and Li, Kuining and Hu, Minghui , journal=. Spacing Policies for Adaptive Cruise Control: A Survey , year=

work page
[21]

2025 , doi =

Artem Agafonov and Konstantin Yakovlev , title =. 2025 , doi =

work page 2025
[22]

2016 , issue_date =

Solovey, Kiril and Halperin, Dan , title =. 2016 , issue_date =. doi:10.1177/0278364916672311 , journal =

work page doi:10.1177/0278364916672311 2016
[23]

Li, Jiaoyang and Surynek, Pavel and Felner, Ariel and Ma, Hang and Kumar, T. K. Satish and Koenig, Sven , year=. Multi-Agent Path Finding for Large Agents , volume=. doi:10.1609/aaai.v33i01.33017627 , number=

work page doi:10.1609/aaai.v33i01.33017627
[24]

Proceedings of the International Conference on Automated Planning and Scheduling , author=

Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm , volume=. Proceedings of the International Conference on Automated Planning and Scheduling , author=. 2017 , month=. doi:10.1609/icaps.v27i1.13856 , number=

work page doi:10.1609/icaps.v27i1.13856 2017
[25]

Demaine and Nicholas J.A

Takehiro Ito and Erik D. Demaine and Nicholas J.A. Harvey and Christos H. Papadimitriou and Martha Sideri and Ryuhei Uehara and Yushi Uno , keywords =. On the complexity of reconfiguration problems , journal =. 2011 , issn =. doi:https://doi.org/10.1016/j.tcs.2010.12.005 , url =

work page doi:10.1016/j.tcs.2010.12.005 2011
[26]

Mouawad and Naomi Nishimura and Sebastian Siebertz , keywords =

Nicolas Bousquet and Amer E. Mouawad and Naomi Nishimura and Sebastian Siebertz , keywords =. A survey on the parameterized complexity of reconfiguration problems , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.cosrev.2024.100663 , url =

work page doi:10.1016/j.cosrev.2024.100663 2024
[27]

Bo Fu and Zhe Chen and Rahul Chandan and Alex Barbosa and Michael Caldara and Joey Durham and Federico Pecora , title =

work page
[28]

2025 , eprint=

A Scalable Post-Processing Pipeline for Large-Scale Free-Space Multi-Agent Path Planning with PiBT , author=. 2025 , eprint=

work page 2025
[29]

ArXiv preprint , volume =

Takahiro Suzuki and Keisuke Okumura , title =. ArXiv preprint , volume =. 2025 , url =

work page 2025
[30]

Robust Multi-Agent Path Finding and Executing , journal =

Dor Atzmon and Roni Stern and Ariel Felner and Glenn Wagner and Roman Bart. Robust Multi-Agent Path Finding and Executing , journal =. 2020 , url =. doi:10.1613/JAIR.1.11734 , timestamp =

work page doi:10.1613/jair.1.11734 2020
[31]

2016 , url =

Hang Ma and Sven Koenig , title =. 2016 , url =

work page 2016
[32]

Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses , booktitle = ecai, volume =

Vassilissa Lehoux. Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses , booktitle = ecai, volume =. 2024 , url =

work page 2024
[33]

Offline Time-Independent Multiagent Path Planning , year=

Okumura, Keisuke and Bonnet, François and Tamura, Yasumasa and Défago, Xavier , journal=. Offline Time-Independent Multiagent Path Planning , year=

work page
[34]

Tomer Shahar and Shashank Shekhar and Dor Atzmon and Abdallah Saffidine and Brendan Juba and Roni Stern , title =. J. Artif. Intell. Res. , volume =. 2021 , url =. doi:10.1613/JAIR.1.12397 , timestamp =

work page doi:10.1613/jair.1.12397 2021
[35]

DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies , volume=

Čapek, Martin and Surynek, Pavel , year=. DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies , volume=. doi:10.1609/socs.v12i1.18567 , number=

work page doi:10.1609/socs.v12i1.18567
[36]

Graph Attention-Guided Search for Dense Multi-Agent Pathfinding , author=

work page
[37]

Hearn and Erik D

Robert A. Hearn and Erik D. Demaine , title =. Theor. Comput. Sci. , volume =. 2005 , url =. doi:10.1016/J.TCS.2005.05.008 , timestamp =

work page doi:10.1016/j.tcs.2005.05.008 2005
[38]

Zur allgemeinen Kurventheorie , url =

Menger, Karl , journal =. Zur allgemeinen Kurventheorie , url =

work page
[39]

AI Matters , url =

Ma, Hang and Koenig, Sven , title =. AI Matters , url =. 2017 , issue_date =

work page 2017