Source-linked AI summary
Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
TL;DR
High-density storage fleets must visit scarce task-critical resources and then park without obstructing operations. This paper introduces PS-MAPF, characterizes solvability and complexity, and evaluates complete, optimal, and prioritized algorithms. PPP solves 74–89% of benchmark instances while achieving much lower cost than the baseline.
Problem
The problem is coordinating tasked and untasked agents so tasked agents visit interchangeable pivots before the whole fleet reaches distinct anonymous stations.
Method
The paper develops PS-MAPF, proves solvability conditions, establishes single-pivot NP-hardness, and presents baseline, SAT-based, and Pivot-Prioritized Planning algorithms.
Results
74–89% of benchmark instances are solved by PPP, with orders-of-magnitude lower cost than the baseline.
Takeaways & Limitations
The results support PPP as a fast but incomplete approach, while the baseline is complete and the SAT solver targets makespan optimality.
Takeaways & Limitations
The general-graph characterization applies to well-formed instances, and SAT performance depends heavily on lower-bound tightness and can time out.
Abstract
from arXiv · showhide
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.
1 Introduction and Related Work
PS-MAPF models fleets that must route tasked agents through interchangeable pivots before the entire fleet parks at distinct anonymous stations. The paper distinguishes this structure from existing MAPF variants and establishes its solvability, complexity, and algorithmic contributions.
- PS-MAPF: PS-MAPF requires tasked agents to visit any pivot before all agents terminate at distinct stations, while untasked agents go directly to stations.Tasked and untasked agents remain coupled through shared space and collision-free paths.
- Relation to existing variants: Unlike Anonymous MAPF, TAPF, Generalized TAPF, Multi-Goal MAPF, and MCPF, PS-MAPF combines interchangeable intermediate pivots with anonymous terminal placement for the whole fleet.Its requirement differs from MCPF because every tasked agent must visit some pivot, rather than every intermediate target being visited.
- Contributions: The paper gives a polynomial-time solvability characterization using 2-edge connectivity and, on arbitrary connected graphs, effective distance relative to unoccupied vertices.The characterization is stated as necessary and sufficient on arbitrary connected graphs.
- Contributions: A single pivot already makes station-makespan and station-flowtime minimization NP-hard.This contrasts with pivot-free anonymous MAPF, whose feasibility and makespan optimization are polynomial-time solvable in the cited comparison.
- Algorithms and experiments: The proposed algorithms include a complete baseline, a SAT-based optimal solver, and Pivot-Prioritized Planning, which solves 74–89% of benchmarks at orders-of-magnitude lower cost than the baseline.PPP is incomplete but fast, while the baseline is complete and the SAT solver is reduction-based.
2 Problem Statement
A PS-MAPF instance places tasked and untasked agents on a connected graph with pivots and stations, requiring conflict-free paths that satisfy pivot access and final station occupancy. The section formalizes paths, conflicts, success conditions, solutions, and station-based costs.
- Agent requirements: Tasked agents must pass through any pivot before reaching a station, whereas untasked agents may go directly to a station.Any agent may terminate at any station, and any pivot may serve any tasked agent.
- Instance definition: A PS-MAPF instance consists of a graph, pivot set, station set, tasked and untasked agents, and an injective origin assignment.The station set must contain at least as many positions as agents.
- Paths: A path is a sequence of moves or waits from an origin to a destination, and its length is the number of time steps.Graph distance is the minimum length over all paths between two vertices.
- Collision model: Conflict-free motion excludes both simultaneous vertex occupancy and opposite-direction traversal of the same edge.Paths of unequal lengths are handled by padding the shorter path.
- Success and solutions: An agent succeeds when it eventually reaches a station and remains there; tasked agents additionally must reach a pivot beforehand.A solution is a successful motion whose paths are pairwise conflict-free and have equal length.
- Objectives: Station-makespan and station-flowtime measure costs based on when agents reach their stations.The example solution has station-makespan 6 and station-flowtime 20, both minimal for that instance.
3 Solvability
PS-MAPF solvability is guaranteed in broad graph settings and admits a complete characterization on arbitrary connected graphs. The key obstruction is tasked-agent access to pivots, governed by graph connectivity and available unoccupied vertices.
- 3.1 Existence on 2-Edge-Connected Graphs: A pivot-free PS-MAPF instance is always solvable, so station placement cannot obstruct feasibility after pivot visits are complete.The remaining fleet can then be routed as an anonymous MAPF instance.
- 3.2 Existence on General Graphs: A path graph with an endpoint pivot can be unsolvable because agents cannot exchange relative order, even when many vertices are unoccupied.This illustrates why pivot requirements, rather than station locations, determine the obstruction.
- 3.1 Existence on 2-Edge-Connected Graphs: On a 2-edge-connected graph, every tasked agent can reach a suitable pivot, making every well-formed instance solvable.The construction uses two edge-independent paths and concatenated rotations, then completes the fleet routing pivot-free.
- 3.2 Existence on General Graphs: On arbitrary connected graphs, solvability is characterized in polynomial time by each tasked agent’s reachable p-adapted configuration and effective distance relative to unoccupied vertices.The characterization is necessary and sufficient for every tasked agent and some pivot.
- 3.2 Existence on General Graphs: A shortest-path condition requiring d(o(i), p) ≤ h(V, o) is sufficient for reaching a pivot but is not necessary.Unoccupied vertices can be redistributed within connected subgraphs, enabling feasible motions that exceed the direct empty-path bound.
4 Complexity Analysis
The paper proves that optimizing station-makespan and station-flowtime in PS-MAPF is NP-hard even with one pivot, via reductions from 3SAT. The reductions encode variable assignments as route choices and use the pivot and station structure to force the needed correspondence.
- Reduction construction: The reduction uses a single pivot strategically positioned so that agents are forced toward predetermined station sets.This makes the constructed instance’s analysis analogous to classical MAPF while retaining anonymous destinations.
- Makespan reduction: A satisfying 3SAT assignment yields a solution with station-makespan at most m + 3.Variable-agent choices between upper and lower paths represent truth values, leaving a compatible route for each clause agent.
- Makespan reduction: Conversely, any solution with station-makespan at most m + 3 induces a satisfying assignment.Shortest, non-waiting paths force variable agents onto one of two paths, and each clause agent’s available path identifies a satisfying literal.
- Complexity results: The MSM and MSF decision problems are proved NP-hard.The proofs reduce from 3SAT and establish the hardness threshold for both station objectives.
- Flowtime reduction: The station-flowtime threshold is linked to the same construction: flowtime at most (m + n)(m + 3) holds exactly when the corresponding makespan threshold holds.This equivalence transfers the 3SAT reduction to MSF.
- Complexity threshold: The results reveal a sharp jump from polynomial solvability in pivot-free anonymous MAPF to intractability when even one pivot requirement is added.Pivot-free instances always admit a solution, whereas the optimization problems become NP-hard under a single pivot.
5 Algorithms
The paper develops a complete baseline, a polynomial-time Pivot-Prioritized Planning method, and a SAT-based optimal solver for PS-MAPF. These methods trade completeness, solution quality, speed, and optimality through constructive routing, prioritized planning, and anonymized pseudo-Boolean encoding.
- Algorithmic overview: Three algorithms span the main trade-offs: BA is complete but low-quality, PPP is fast but incomplete, and the SAT solver computes makespan-optimal solutions at exponential worst-case cost.Any solution returned by PPP is correct, although PPP may fail on solvable instances.
- Baseline Algorithm: BA processes tasked agents sequentially, routes each to a pivot using the solvability construction, then solves the residual pivot-free instance anonymously.The final routing step uses the fact that all pivot requirements have already been satisfied.
- Baseline Algorithm: BA uses the graph’s 2-edge condensation tree to select activatable pivots, clear components, advance agents, and rewind the state between tasked-agent computations.Its decomposition distinguishes non-singleton, branching-singleton, and degree-two-singleton components.
- Pivot-Prioritized Planning: PPP first reserves prioritized paths for tasked agents to pivots, then routes the full fleet to stations as an anonymous MAPF flow.A returned path set is guaranteed to be a valid PS-MAPF solution.
- Pivot-Prioritized Planning: PPP runs in O(n^4m) worst-case time, remaining polynomial in the instance size.The bound follows from the Phase 2 maximum-flow computation with τmax = O(n^2).
- SAT-Based Optimal Solver: The anonymized SAT encoding avoids dependence on the number of agents by distinguishing pivot-oriented and station-oriented agents instead of agent identities.This design is expected to outperform direct encoding in dense instances, although performance depends strongly on the lower bound for T*.
- SAT-Based Optimal Solver: The SAT solver increases time horizons and tests satisfiability of a pseudo-Boolean formula Φ(T), using BA for solvability and an upper bound before searching from a theorem-derived lower bound.The encoding is correct when Φ(T) is satisfiable exactly when a solution of the corresponding makespan exists.
6 Experimental Study
Experiments isolate how density, obstacles, stations, pivots, and grid size affect PS-MAPF difficulty, then compare PPP with the complete baseline across benchmark settings.
- SAT-Based Optimal Solver: Agent and tasked densities interact: runtimes spike at 50% agent density when all agents are tasked, while 25% tasked agents remain tractable to 90% density.At equal tasked-origin density, more untasked agents can substantially increase runtime.
- SAT-Based Optimal Solver: 100% of instances are solved up to 15% obstacle density, but solve rates fall to 40% at 30%; station density instead reduces difficulty.With 40% agent density, average optimal makespan decreases from 9.8 at 40% station density to 8.4 at 100%.
- SAT-Based Optimal Solver: 100% of five instances are solved on grids up to 20 × 20, while the success rate remains 80% on 28 × 28 grids.These results provide the reported scalability range for the optimal solver experiments.
- SAT-Based Optimal Solver: Increasing pivot density helps most at 1–10% density, after which success-rate gains and makespan reductions level off.The pivot-density study compares the optimal solver and PPP on 16 × 16 instances with a 60-second timeout.
- PPP vs. Baseline Algorithm: Across benchmark maps and priority orderings, PPP achieved 74–89% success while substantially outperforming BA in runtime, makespan, and flowtime.No heuristic ordering dominated overall; MC was strongest overall, and PPP failures concentrated in extreme bottleneck cases.
7 Conclusion and Future Work
The paper introduces PS-MAPF, completes its solvability and complexity analysis, and evaluates three algorithms. It concludes that PPP offers large practical gains while remaining incomplete, motivating several extensions.
- Conclusion: PS-MAPF requires tasked agents to visit anonymous pivots before the entire fleet terminates at anonymous stations.The model targets fleet coordination with interchangeable intermediate resources and terminal stations.
- Conclusion: The paper completely characterizes solvability, proves station-makespan and station-flowtime minimization NP-hard with one pivot, and presents three algorithms.The algorithms are a complete baseline, a SAT-based makespan-optimal solver, and incomplete but fast PPP.
- Future Work: PPP produces solutions orders of magnitude better than the baseline, but future work includes pivot-based objectives, domain-specific solvers, and adapted MAPF techniques.The conclusion frames these as directions beyond the current algorithms and objectives.