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

Andrea Di Nezza; Mihir Patel; Fabio Fagnani; Sara Bernardini

cs.AIAug 25, 2026

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

Authors: Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini

Organizations: Department of Mathematical Sciences, Politecnico di Torino, Turin, Italy · Department of Computer Science, University of Oxford, Oxford, United Kingdom

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Example of a PS-MAPF instance $\mathcal{I}$ and its solution $\Pi$ on a grid graph with black obstacles. Pivots $\mathcal{P}=\{p_{1},p_{2}\}$ and storage destinations $\mathcal{S}=\{s_{1},..,s_{6}\}$ are highlighted in orange and yellow, respectively. In 1(a) , the problem instance, showing the labeled positions of pivots and destinations, along with the starting positions of tasked agents (red circles 1, 2, 3) and the untasked agent (blue circle 4). In 1(b) , the corresponding solution, showing the non-conflicting paths $\Pi=(\pi_{1},\pi_{2},\pi_{3},\pi_{4})$ toward their targets, with time markers indicating the agent positions at each time step.

Figure 2: An unsolvable instance: red vertices are origins of tasked agents, the green vertex is the only pivot, every vertex is a station.

Figure 3: Two edge-independent paths linking the origin of an agent (in red) to a pivot (in green). Concatenation of rotation along the obtained cycles eventually leads

i

p

Figure 4: In the top figure, a tasked agent

i

is positioned at the red vertex, at distance

6

from the pivot

p

in green. Despite there being only

4

unoccupied vertices (in white), a feasible motion that brings

i

p

exists and can be easily constructed by starting from the initial condition and then passing through the two intermediate configurations (central and bottom figures).

Figure 5: Construction of PS-MAPF instance

\mathcal{I}

from 3SAT formula

(x_{1}\vee\overline{x_{3}}\vee x_{4})\wedge(\overline{x_{1}}\vee x_{2}\vee\overline{x_{4}})\wedge(\overline{x_{2}}\vee x_{3}\vee x_{4})

. Red/blue vertices are tasked/untasked agent origins, respectively. Yellow vertices are stations; orange vertices are pivots.

		$\displaystyle\bigwedge_{v\notin\mathcal{P}}\bigwedge_{t=0}^{T}\neg x_{v,t}^{\mathcal{P}}\vee\neg x_{v,t}^{\mathcal{S}}$		(C1a)
		$\displaystyle\bigwedge_{t=1}^{T}\bigwedge_{(u,v)\in\mathcal{E}}(\neg y_{u,v,t}^{\mathcal{P}}\land\neg y_{u,v,t}^{\mathcal{S}})\lor(\neg y_{v,u,t}^{\mathcal{P}}\land\neg y_{v,u,t}^{\mathcal{S}})$		(C1b)
		$\displaystyle\bigwedge_{t=0}^{T-1}\bigwedge_{v\notin\mathcal{P}}(x_{v,t}^{\mathcal{P}}=\sum_{u\in N[v]}y_{v,u,t+1}^{\mathcal{P}})$		(C2a)
		$\displaystyle\bigwedge_{t=1}^{T}\bigwedge_{v\notin\mathcal{P}}(x_{v,t}^{\mathcal{P}}=\sum_{u\in N[v]\setminus\mathcal{P}}y_{u,v,t}^{\mathcal{P}})$		(C2b)
		$\displaystyle\bigwedge_{t=0}^{T-1}\bigwedge_{v\in\mathcal{V}}(x_{v,t}^{\mathcal{S}}=\sum_{u\in N[v]}y_{v,u,t+1}^{\mathcal{S}})$		(C2c)
		$\displaystyle\bigwedge_{t=1}^{T}\bigwedge_{v\notin\mathcal{P}}(x_{v,t}^{\mathcal{S}}=\sum_{u\in N[v]}y_{u,v,t}^{\mathcal{S}})$		(C2d)
		$\displaystyle\bigwedge_{t=1}^{T}\bigwedge_{v\in\mathcal{P}}(x_{v,t}^{\mathcal{S}}=\sum_{u\in N[v]\setminus\mathcal{P}}y_{u,v,t}^{\mathcal{P}}+\sum_{u\in N[v]}y_{u,v,t}^{\mathcal{S}})$		(C2e)

Figure 6: Pseudo-Boolean formula

\Phi(T)

Panel of Figure 7 — Figure 7: (a) Optimal-solver performance over 10 feasible $16\times 16$ instances ( $\text{Obstacle}\%=0.2$ ) vs. agent density, by tasked percentage ( $\text{Station}\%=\text{Agent}\%$ , $\text{Pivot}\%=0.05$ ); (b) Optimal-solver and PPP performances over 20 well-formed $16\times 16$ instances ( $\text{Obstacle}\%=0.2$ ) vs. pivot density ( $\text{Agent}\%=\text{Station}\%=0.15$ , $\text{Tasked}\%=0.5$ ). 60-sec timeout.

Solver	empty-48-48				random-64-64-10				warehouse-10-20-10-2-1
Solver	Runtime	$\mathbf{M_{\mathcal{S}}^{\mathcal{I}}}$	$\mathbf{\Sigma_{\mathcal{S}}^{\mathcal{I}}}$	Success	Runtime	$\mathbf{M_{\mathcal{S}}^{\mathcal{I}}}$	$\mathbf{\Sigma_{\mathcal{S}}^{\mathcal{I}}}$	Success	Runtime	$\mathbf{M_{\mathcal{S}}^{\mathcal{I}}}$	$\mathbf{\Sigma_{\mathcal{S}}^{\mathcal{I}}}$	Success
BA	22.29	3859.72	391533.70	100.0	64.78	6326.42	750692.14	100.0	282.32	23933.24	5740934.78	100.0
LH	8.76	31.33	2428.33	87.0	25.33	42.54	3855.11	84.0	141.53	91.90	17000.67	81.0
SH	8.67	30.88	2387.69	86.5	25.08	42.85	3844.63	85.0	151.12	92.17	16681.59	78.5
RND	8.42	30.98	2365.56	83.5	24.70	42.35	3811.54	82.0	148.66	91.22	16876.49	78.0
LC	8.91	31.17	2383.30	84.5	25.41	42.90	3773.30	81.0	143.45	90.00	15983.05	74.5

Table 1: Average Runtime (s), Station-Makespan (

M_{\mathcal{S}}^{\mathcal{I}}

), Station-Flowtime (

\Sigma_{\mathcal{S}}^{\mathcal{I}}

) and Success Rate (%); for fairness, averages are over instances solved by all six algorithms. Best results among the PPP orderings are in bold. No time limit was imposed.

Explore similar work

Aug 21, 2026

Goal Staying Makes Sum-of-Costs Anonymous Multi-Agent Path Finding NP-Hard

Anonymous Multi-Agent Path Finding (AMAPF) admits polynomial-time network-flow algorithms for several objectives, including makespan, total distance, and sum-of-costs (SoC) when agents disappear upon reaching goals. We show that standard goal-staying AMAPF is fundamentally different. We first formulate SoC minimization by augmenting the standard time-expanded flow model with goal-settlement constraints and show that the resulting linear programming relaxation is non-integral. We then prove that minimizing SoC in goal-staying AMAPF is NP-hard via a reduction from 3-SAT. Together with the polynomial-time result for the disappearing variant, this establishes a sharp complexity boundary determined by whether completed agents remain at their goals.

Hang Ma

Simon Fraser University

Multi-Agent Path Finding

Ask PDF

Aug 8, 2026

AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

Many research fields share a common structure: a set of agents, each pursuing its own goal, whose actions must be coordinated so that no two of them conflict. Multi-Agent Path Finding (MAPF) is a concrete instance of this structure, with applications from warehouses to road traffic and airports. Much of MAPF research assumes discrete time, circular agents sharing one spatial graph, a single goal per agent, and that an agent must remain at its goal once reached, precluding heterogeneous fleets, non-geometric conflicts, task sequences, and agents that move on after completing them. We generalise the MAPF formulation to lift these assumptions, and present Anytime-Optimal Continuous-time Conflict-Based Search (AOC-CBS), an exact and solution-complete solver for it. AOC-CBS guarantees the eventual return of an optimal solution, while reporting an incumbent with a known optimality gap upper bound throughout its runtime; it is configurable with a portfolio of repair functions, one of which we introduce (Tier-Prioritized Safe Interval Path Planning), and can exploit multiple processor cores. We demonstrate AOC-CBS on a mixed fleet of non-convex agents moving along smooth, kinodynamically feasible trajectories. Preliminary experiments against the exact solver OC-CBS, on well-known benchmarks and roadmaps we sample from them, show AOC-CBS is comparable at finding optimal solutions while extending scalability from the tens to the hundreds of agents when a bounded optimality gap is accepted.

Alvin Combrink, Sabino Francesco Roselli, Martin Fabian

Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

Robust MAPF Conflict-Based Search Multi-Agent Path Finding

Ask PDF

Jun 4, 2026

Hardness of Multi-Agent Path Finding on Trees: A Unified Approach

This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives - distance, makespan, and flowtime - for both labeled and colored variants. In MAPF, agents occupy the vertices of a graph and must move to target vertices without collisions while optimizing a given objective. In the labeled case, the agents are distinct and have respective targets; in the colored case, agents of the same color are interchangeable. While many MAPF variants are known to be intractable, several basic cases on trees have remained open. We prove NP-hardness on trees for both labeled and 2-colored MAPF under all three objectives. In particular, we resolve the classical Pebble Motion problem, where one pebble moves at a time to an adjacent empty vertex and the goal is to minimize the total number of moves. Despite being one of the most basic discrete motion models, its complexity on trees had remained open for several decades. Moreover, for colored Pebble Motion, we give the first hardness result on any graph class, already with two colors, which is tight. All of these results are established through the hardness of Stack Rearrangement, itself posed as an open problem, which asks to optimally rearrange items stored in stacks, and which we also prove to be NP-hard. Notably, the connection to stacks yields hardness already on very simple trees - subdivided stars - across all problems. Together, these results reveal a common tractability barrier that permeates several fundamental motion models, thereby unifying and strengthening prior hardness results.

Tzvika Geft

Rutgers University, NJ, USA · NJ, USA

Motion Planning Multi-Agent Path Finding

Ask PDF