Search papers, labs, and topics across Lattice.
This paper introduces Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a novel variant designed for high-density automated storage systems, where agents must visit interchangeable pivots before reaching their final destinations. The authors establish a comprehensive solvability characterization for PS-MAPF on connected graphs, revealing that all instances on 2-edge-connected graphs are solvable and providing a structural effective-distance measure for arbitrary graphs. They also demonstrate that minimizing station-makespan or station-flowtime is NP-hard, while their proposed algorithms, particularly Pivot-Prioritized Planning (PPP), significantly outperform baseline methods by solving 74-89% of benchmark instances with drastically improved efficiency.
Solving high-density multi-agent pathfinding problems can be drastically improved, with one algorithm achieving 74-89% success in complex scenarios.
Automated high-density storage systems (warehouses, robotic parking, plant logistics, etc.) require fleets of agents to move through scarce task-critical resources and then park without obstructing future operations. We introduce Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a MAPF variant in which a subset of tasked agents must each visit one of a set of interchangeable pivots (e.g., workstations) before the entire fleet terminates at anonymous stations, one agent per station. We characterize solvability completely: every instance on a 2-edge-connected graph is solvable, and, on arbitrary connected graphs, a structural effective-distance measure relative to the number of unoccupied vertices gives a necessary and sufficient condition. We prove that minimizing station-makespan or station-flowtime is NP-hard already with a single pivot. We present three algorithms, a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning (PPP), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline.
