Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
Stuckey, and Sven Koenig
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
years
2026 5verdicts
UNVERDICTED 5representative citing papers
Formalizes CT-TAPF problem and introduces CT-TCBS optimal solver using incremental expansion for team formation plus task-centric sub-optimal solvers that improve efficiency over agent-centric baselines.
DiffLNS uses a discrete diffusion initializer to produce warm-start plans that lift LNS2 success rates to 95.8% across 20 congested MAPF settings, generalizing from 96 to 312 agents.
Distance-r Independent Unlabeled Multi-Agent Pathfinding is PSPACE-complete, with reduction-based and configuration-generator algorithms that solve instances with hundreds of agents.
C-ORCA* and C-ORCA*-MAPF proactively prevent deadlocks in continuous MAPF using entire trajectories and spatial dependencies, outperforming prior methods in solve rate, runtime, and flowtime.
citing papers explorer
-
On the Hardness of Optimal Motion on Trees
Establishes NP-hardness of MAPF on trees for labeled and 2-colored variants across three objectives by proving hardness of stack rearrangement, which reduces to motion on subdivided stars.
-
Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
Formalizes CT-TAPF problem and introduces CT-TCBS optimal solver using incremental expansion for team formation plus task-centric sub-optimal solvers that improve efficiency over agent-centric baselines.
-
Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention
DiffLNS uses a discrete diffusion initializer to produce warm-start plans that lift LNS2 success rates to 95.8% across 20 congested MAPF settings, generalizing from 96 to 312 agents.
-
Distance-Constrained Unlabeled Multi-Agent Pathfinding
Distance-r Independent Unlabeled Multi-Agent Pathfinding is PSPACE-complete, with reduction-based and configuration-generator algorithms that solve instances with hundreds of agents.
-
Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation
C-ORCA* and C-ORCA*-MAPF proactively prevent deadlocks in continuous MAPF using entire trajectories and spatial dependencies, outperforming prior methods in solve rate, runtime, and flowtime.