# Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

arXiv: https://arxiv.org/abs/2608.24585 · HTML: https://mlsanity.com/paper/2608.24585/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 35 references that are in the map.
- First posted on arXiv 25 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios](https://mlsanity.com/paper/1702.05515/) (2017)
- [Engineering LaCAM^ast: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.04292/) (2023)

## Abstract (arXiv)

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.