Paper deep dive
Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms
Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.24585v1
- Canonical: https://arxiv.org/abs/2608.24585v1
Trouble viewing inline? Open PDF directly →
Full Text
119,538 characters extracted from source content.
Expand or collapse full text
Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms Andrea Di Nezza Mihir Patel Fabio Fagnani Sara Bernardini 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 (P), the last solving 74-89% of benchmark instances with makespan and flowtime orders of magnitude below the baseline. 1Department of Mathematical Sciences, Politecnico di Torino, Turin, Italy 2Department of Computer Science, University of Oxford, Oxford, United Kingdom 1 Introduction and Related Work Infrastructure-based high-density automated storage systems (warehouses, robotic parking, plant logistics; e.g., Ocado, Amazon Sequoia, Versatile, Robotic Parking, WPS) move fleets of agents (robots, shuttles, or motorized cells) through a fixed mechanical topology of rails, lifts, conveyors, or grid cells. At any moment, some agents are moving toward a pivot: a task-critical resource that must be visited, such as a workstation, a pickup or drop-off point, or a charging interface; in a given system, pivots form a single class of functionally interchangeable resources (systems with several classes give rise to typed pivots; we treat one). The other agents, having visited a workstation or not needing one, must park at a station: an admissible terminal position (storage cell, staging area) from which they remain available for future tasks without obstructing traffic; any agent may terminate at any station, one agent per station. Poor terminal placement propagates congestion, and poorly coordinated pivot access causes active agents to queue; the two should therefore be optimized jointly: a locally good route to a pivot may leave agents obstructing others’ paths or blocking terminal placements, while convenient station assignments may ignore upcoming access to scarce resources. We call the combined problem Pivot-and-Station Multi-Agent Path Finding (PS-MAPF), a new variant of Multi-Agent Path Finding (MAPF) (Stern et al. 2019): on a graph whose vertices include pivots and stations, a subset of agents is tasked and must visit at least one pivot (any pivot serves any tasked agent) before reaching its terminal position; the remaining untasked agents have no pivot requirement but still occupy space and interact with tasked agents throughout. Every agent must terminate at a distinct station, and a solution is a set of collision-free paths satisfying both the pivot-access and terminal-station requirements. In classical MAPF (Stern et al. 2019), feasibility is polynomial-time decidable via pebble motion (Kornhauser et al. 1984), whereas optimizing makespan or flowtime is NP-hard (Yu and LaValle 2013b). Optimal solvers are search-based, e.g., CBS (Sharon et al. 2015), or reduction-based, encoding MAPF as SAT (Surynek et al. 2016), which often dominates in dense settings (Asín Achá et al. 2022; Surynek 2019); scalable suboptimal methods include rule-based algorithms (Luna and Bekris 2011; Surynek 2009), prioritized planning (Erdmann and Lozano-Pérez 1987), whose modern variants tune agent orderings (Silver 2005; Ma et al. 2019), the near-optimal LaCAM* (Okumura 2024), and MAPF-HD (Makino and Ito 2026) for high-density settings. Our optimal solver builds on the SAT line, and our fast method is a prioritized planner. PS-MAPF captures a coordination structure not fully addressed by existing variants (Ma et al. 2016). In Anonymous MAPF (AMAPF), destinations are unassigned and makespan optimization is polynomial (Yu and LaValle 2013a); in Target Assignment and Path Finding (TAPF), destinations are interchangeable only within subgroups, which is NP-hard (Ma and Koenig 2016); neither models mandatory access to scarce intermediate resources. Generalized TAPF (Nguyen et al. 2017) and Multi-Goal MAPF (Surynek 2021) assign each agent or group a specific sequence of targets, whereas PS-MAPF treats pivots as unassigned, interchangeable resources. Multi-Agent Combinatorial Path Finding (MCPF) (Ren et al. 2021; Ren et al. 2022) is the nearest, combining intermediate targets with anonymous terminal assignment, but the requirement points the opposite way (in MCPF every target must be visited by some agent; in PS-MAPF every tasked agent must visit some pivot, and a pivot no agent needs is never visited). MCPF treats agents symmetrically, while PS-MAPF distinguishes tasked/untasked agents and places the entire fleet. MAPF with Unassigned Agents (Felner and Stern 2026) distinguishes tasked and untasked agents but does not require anonymous terminal reconfiguration of the whole fleet. Multi-Agent Pickup and Delivery (Ma et al. 2017) shares the intermediate requirement but is lifelong with assigned pickup and delivery locations, whereas PS-MAPF is one-shot with anonymous pivots and stations. This paper makes the following contributions. (i) A new MAPF variant, PS-MAPF, motivated by high-density automated storage systems (Sec. 2). (i) A complete characterization of solvabilitycheckable in polynomial time: sufficiency via 2-edge connectivity and, on arbitrary connected graphs, a necessary and sufficient condition comparing an effective-distance measure with the number of unoccupied vertices (Sec. 3). (i) A sharp complexity threshold: minimizing station-makespan and station-flowtime is NP-hard already for a single pivot (Sec. 4). (iv) Algorithms and experiments: a complete baseline derived from our constructive solvability proof, a reduction-based optimal solver, and Pivot-Prioritized Planning (P), incomplete but fast (prioritized pivot routing plus flow-based station assignment), solving 74–89% of benchmark instances at orders-of-magnitude lower cost than the baseline (Sec. 5 and 6). 2 Problem Statement We consider a connected, undirected graph =(,ℰ)G=(V,E) without self-loops, with a set of pivots ⊆P , a set of stations ⊆S , and a set A of agents moving on the graph. A configuration is an injective function :→c:A assigning to each agent a distinct vertex (hence ||≥|||V|≥|A|). Agents’ initial positions are specified by a configuration :→o:A , called the origin configuration; we refer to (i)o(i) as the origin of agent i. Agents are partitioned into tasked agents tA^t, which must pass through one of the pivots in P before reaching a station, and untasked agents uA^u, which can go directly to a station. Any pivot serves any tasked agent, and any agent may terminate at any station. Definition 1. Given a graph =(,ℰ)G=(V,E), a set of pivots ⊆P , a set of stations ⊆S , a set of tasked agents tA^t, a set of untasked agents uA^u, and an origin function :→o:A , where =t∪uA=A^t ^u, t∩u=∅A^t ^u= , o is injective and ||≥|||S|≥|A|, we define a PS-MAPF Instance as the tuple ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ). p1p_1p2p_2s1s_1s2s_2s3s_3s4s_4s5s_5s6s_61234 (a) 012345012345601234012345 (b) Figure 1: Example of a PS-MAPF instance ℐI and its solution Π on a grid graph with black obstacles. Pivots =p1,p2P=\p_1,p_2\ and storage destinations =s1,..,s6S=\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 Π=(π1,π2,π3,π4) =( _1, _2, _3, _4) toward their targets, with time markers indicating the agent positions at each time step. Example 1. Figure 1(a) illustrates instance ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ), where G is a grid graph with black cells representing obstacles; pivots =p1,p2P=\p_1,p_2\ (orange), stations =s1,..,s6S=\s_1,..,s_6\ (yellow), tasked agents t=1,2,3A^t=\1,2,3\ (red circles) and untasked agents u=4A^u=\4\ (blue circle), with each agent starting at the indicated position. A path in =(,ℰ)G=(V,E) from x∈x to y∈y is a function π:[0..T]→π:[0..T] , T∈ℕT , with π(0)=xπ(0)=x, π(T)=yπ(T)=y, and, for every t∈[0..T−1]t∈[0..T-1], (π(t),π(t+1))∈ℰ(π(t),π(t+1)) (moving) or π(t+1)=π(t)π(t+1)=π(t) (waiting); T is the path’s length. The distance d(x,y)d(x,y) between two vertices x and y is the minimum length among all paths between them. Given ⊆W , the subgraph induced by W is []=(,ℰ∩(×))G[W]=(W,E∩(W×W)). Movements must avoid two types of conflicts between paths πi,πj:[0..T]→ _i, _j:[0..T] . A vertex conflict occurs at time t∈[0..T]t∈[0..T] if πi(t)=πj(t) _i(t)= _j(t); a swapping conflict occurs at time t∈[0..T−1]t∈[0..T-1] if πi(t)=πj(t+1) _i(t)= _j(t+1) and πi(t+1)=πj(t) _i(t+1)= _j(t), with πi(t)≠πi(t+1) _i(t)≠ _i(t+1) and πj(t)≠πj(t+1) _j(t)≠ _j(t+1) (the two agents traverse the same edge in opposite directions). Paths πi _i and πj _j are conflict-free if neither conflict occurs at any time step; the definitions extend to paths of different lengths by padding the shorter one with wait actions. For an agent’s path π:[0..T]→π:[0..T] , the time-at-pivot is the first time at which the agent reaches a pivot, t(π)=mint∈[0..T]∣π(t)∈t_P(π)= \t∈[0..T] π(t) \, and the time-at-station is the first time at which the agent reaches a station vertex and never leaves it, t(π)=mint∈[0..T]∣∃q∈∀τ∈[t..T],π(τ)=qt_S(π)= \t∈[0..T] ∃ q \ ∀τ∈[t..T],\ π(τ)=q\; for both, min∅=∞ =∞. An untasked agent i∈ui ^u’s path π is successful if π(0)=(i)π(0)=o(i) and t(π)<∞t_S(π)<∞; a tasked agent i∈ti ^t’s path π is successful if π(0)=(i)π(0)=o(i), t(π)<∞t_P(π)<∞ and t(π)<∞t_S(π)<∞. Definition 2. Given a PS-MAPF instance ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ), a tuple of paths Π=πii∈ =\ _i\_i , all of the same length T, is called a feasible motion of length T if all paths are pairwise conflict-free, and a successful motion if, moreover, all paths are successful. A successful motion Π is also called a solution for ℐI. We denote the set of all solutions for ℐI by Sol(ℐ)Sol(I). Given a feasible motion Π=πii∈ =\ _i\_i of length T, Π(t) (t) is the configuration i↦πi(t)i _i(t) (well-defined since Π is conflict-free); a feasible motion need not start at o. Example 2. Figure 1(b) depicts a solution Π=(π1,π2, =( _1, _2, π3,π4) _3, _4) for the instance ℐI introduced in Figure 1(a). The non-conflicting paths are illustrated by the colored trajectories, with time markers indicating the time steps. Tasked agents 1, 2, and 3 successfully reach a pivot with t_P values of 1, 3, and 2, respectively, before reaching their storage destinations with t_ D values of 5, 6, and 5, respectively. The untasked agent 4 reaches its storage destination with a t_S value of 4. Below, we define two cost functions based on the time all agents reach their stations. Definition 3. Given a PS-MAPF instance ℐI and a solution Π=πii∈ =\ _i\_i , the Station-Makespan and the Station-Flowtime of Π are Mℐ(Π)=maxi∈At(πi)M_S^I( )= _i∈ At_S( _i) and Σℐ(Π)=∑i∈At(πi) _S^I( )= _i∈ At_S( _i). Example 3. The example solution in Figure 1(b) has Mℐ(Π)=6M_S^I( )=6 and Σℐ(Π)=20 _S^I( )=20, which are all minimal for this instance. We aim to find optimal solutions w.r.t. these functions. 3 Solvability We analyze when a PS-MAPF instance admits a solution. When no agent is tasked (t=∅A^t= and =uA=A^u), PS-MAPF coincides with anonymous MAPF (Yu and LaValle 2013a), and we call the instance pivot-free. The following proposition follows from classical results on the unlabeled pebble motion problem (Kornhauser et al. 1984). Proposition 1. A pivot-free PS-MAPF instance ℐ=(,,,∅,u,)I= (G,P,S, ,A^u,o ) always admits a solution (Sol(ℐ)≠∅Sol(I)≠ ). Prop. 1 implies that solvability never depends on where the stations lie: once the tasked agents have completed their pivot visits, routing the whole fleet onto S is a pivot-free instance. Only the pivot requirement can obstruct solvability, e.g., on a path graph, no two agents can ever exchange their relative order, so if a single pivot is located at an endpoint, and there are two tasked agents, the farther one can never reach the pivot, no matter how many vertices are unoccupied (see Figure 2). Figure 2: An unsolvable instance: red vertices are origins of tasked agents, the green vertex is the only pivot, every vertex is a station. To present the results, we first introduce some preliminary notation. A path γ:[0..T]→γ:[0..T] is called simple if γ(t)≠γ(t′)γ(t)≠γ(t ) for every t,t′∈[0..T]t,t ∈[0..T] with t≠t′t≠ t and t,t′≠0,T\t,t \≠\0,T\. A simple path is called a cycle if T>2T>2 and γ(0)=γ(T)γ(0)=γ(T). Often, a cycle γ is identified with the set of edges (γ(t),γ(t+1))|t=[0..T−1]\(γ(t),γ(t+1))\,|\,t=[0..T-1]\. We can associate every cycle γ:[0..T]→γ:[0..T] with T≥3T≥ 3 with a feasible length-one motion rotation, Πγ=πiγi∈ ^γ=\π^γ_i\_i , defined by a synchronized rotation of all agents present in the vertices of the cycle. Formally, for i∈i in position γ(ti)γ(t_i) for some ti∈[0..T−1]t_i∈[0..T-1], we put (πiγ(0),πiγ(1))=(γ(ti),γ(ti+1))(π^γ_i(0),π^γ_i(1))=(γ(t_i),γ(t_i+1)). For the remaining i∈i whose location is outside the cycle, we instead put πiγ(0)=πiγ(1)=(i)π^γ_i(0)=π^γ_i(1)=o(i). Finally, we introduce two operations on motions. If Π=πii∈ =\ _i\_i is a motion of length T, the inversion of Π is the motion Π−=πi−i∈ ^-=\π^-_i\_i of length T where πi−(t)=πi(T−t)π^-_i(t)= _i(T-t) for t=0..Tt=0..T. We also have a natural concept of motion concatenation. Two tuples of paths Π1=πi1i∈ ^1=\π^1_i\_i and Π2=πi2i∈ ^2=\π^2_i\_i , with πir:[0..Tr]→ _i^r:[0..T_r] for i∈i and r=1,2r=1,2, are called concatenable if πi1(T1)=πi2(0)π^1_i(T_1)= _i^2(0) for every i∈i . We define their concatenation Π2∘Π1=πi2∘πi1i∈ ^2 ^1=\π^2_i _i^1\_i by putting (πi2∘πi1)(t)=πi1(t)(π^2_i _i^1)(t)= _i^1(t) for t≤T1t≤ T_1 and (πi2∘πi1)(t)=πi2(t−T1)(π^2_i _i^1)(t)= _i^2(t-T_1) for T1<t≤T1+T2T_1<t≤ T_1+T_2. The inversion of a feasible motion or the concatenation of concatenable feasible motions is always feasible. We also recall a classical concept from graph theory. Given a graph =(,ℰ)G=(V,E), we say that two vertices u,v∈u,v are 2-edge connected if the removal of any single edge from G does not disconnect u from v. By Menger’s theorem (Diestel 2017), this condition is equivalent to saying that there are two paths with no common edge linking u to v (such paths are called edge-independent). Moreover, G is 2-edge connected if any pair of vertices is 2-edge connected. 3.1 Existence on 2-Edge-Connected Graphs Grids, warehouses, and similar layouts are 22-edge connected, the case dominating in practice; there, solvability is always guaranteed: Thm. 1’s per-agent hypothesis holds for every instance on a 22-edge-connected graph with ≠∅P≠ . Theorem 1. Let ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ) be a PS-MAPF instance in which, for every tasked agent i, there exists a pivot p∈p such that (i)o(i) and p are 22-edge connected. Then, the instance admits a solution (Sol(ℐ)≠∅Sol(I)≠ ). Proof. Consider any tasked agent i∈ti ^t and assume that (i)o(i) and p∈p are 22-edge connected. By assumption, there exist two edge independent simple paths γ′=(γ0′..γl′)γ =(γ _0..γ _l ) and γ′=(γ0′..γl′)γ =(γ _0..γ _l ) in G such that γ0′=γ0′=(i)γ _0=γ _0=o(i) and γl′=γl′=pγ _l =γ _l =p. If the two paths have no intermediate vertex in common, then the concatenation of γ′γ with the reverse of γ′γ yields a cycle. A concatenation of l′l rotations, moving i along γ′γ , yields a motion bringing i into p. If instead the two paths have common intermediate vertices, we consider the one of them closest to (i)o(i) along γ′γ , say v=γh′=γh′v=γ _h =γ _h and arguing as before, we construct a motion composed of rotations bringing i into v. A direct inductive argument based on the common intermediate points between γ′γ and γ′γ now permits us to construct a motion bringing i to p (see Figure 3). Finally, notice that all agents whose starting points are within the vertices belonging to the two paths γ′γ and γ′γ remain 22-edge connected to p under such rotations. The remaining agents have not moved and thus remain 22-edge connected to some pivot vertex. We can iterate this construction for each tasked agent and, by concatenating all such feasible motions, obtain a motion Π of length T by which all tasked agents pass through a pivot. We now consider the pivot-free instance ℐ′=(,,,∅,,Π(T))I =(G,P,S, ,A, (T)). By Prop. 1, a solution exists for ℐ′I , call it Π′ . The concatenation Π′∘Π is finally, by construction, a successful feasible motion for ℐI. ∎ 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 in p. 3.2 Existence on General Graphs For arbitrary connected graphs, solvability admits a complete, polynomial-time-checkable characterization based on the number and distribution of tasked and untasked agents, as well as on the topology of G. Given any subset of vertices ⊆W and a configuration c, we define H(,)=∖()H(W,c)=W (A), i.e. the set of W’s unoccupied vertices when the agents are in configuration c. We also define h(,)=|H(,)|h(W,c)=|H(W,c)|. The following lemma shows that, on any connected subgraph ′G , feasible motions can arbitrarily move the set of unoccupied vertices in ′V , while keeping at rest all agents outside of it. Lemma 1. Let ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o) be a PS-MAPF instance, and let ′=(′,ℰ′)G =(V ,E ) be a connected induced subgraph of G. Let ⊆′D be such that ||=h(′,)|D|=h(V ,o). Then, there exists a feasible motion Π of length T such that Π(0)= (0)=o, H(′,Π(T))=H(V , (T))=D, and πi(t)=(i) _i(t)=o(i) for every t if (i)∉′o(i) . Proof. Consider the pivot-free sub-instance restricted to the set of agents ′A currently in ′G , defining ′∖V as the set of their stations: ℐ′=(′,,′∖,∅,′,|′)I =(G ,P,V , ,A ,o|_A ). Since ′G is connected and, by construction, |′|=|′|−h(′,)=|′∖||A |=|V |-h(V ,o)=|V |, Prop. 1 guarantees a solution to this anonymous MAPF problem. By extending the paths of all agents outside ′G with wait actions, this yields the desired feasible motion on the entire graph G. ∎ We now investigate motion constraints in arbitrary topologies. We notice that 22-edge connectivity is an equivalence relation that decomposes the set of vertices V into disjoint subsets C1..CsC_1..C_s, inducing subgraphs that are maximally 22-edge connected. We call such subsets the 22-edge connected components of G. We indicate with =(,ℱ)T=(N,F) the 22-edge condensation tree of G: the tree with vertices =C1..CsN=\C_1..C_s\ and with an edge (Ci,Cj)(C_i,C_j) if in G there exists an edge between a node in CiC_i and a node in CjC_j (we refer to such edges as bridges). In our analysis, we need to distinguish among the various 22-edge connected components. To this aim, we decompose the set N as =10∪11∪>1N=N_1^0 _1^1 _>1. 10N_1^0 and 11N_1^1 indicate the set of singleton components of degree not larger than 22 and above 22, respectively, while >1N_>1 indicates the set of non-singleton components (thus of cardinality at least 33). We refer to the components in 11N_1^1 as singleton branching. It will be useful to consider configurations in which all unoccupied vertices form a single connected region containing p; intuitively, the free space is gathered at the pivot rather than dispersed through the graph. Definition 4. The configuration o is called p-adapted if the set of unoccupied vertices H(,)H(V,o) is either empty or it contains p and the induced subgraph [H(,)]G[H(V,o)] is connected. The following result shows that the agents can always be brought to a p-adapted configuration, for any pivot p. Proposition 2. Let ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ) be a PS-MAPF instance and let p∈p . There exists a feasible motion Π of length T such that Π(T) (T) is a p-adapted configuration. Proof. Consider any set of vertices W of cardinality h(,)h(V,o) that contains p and such that the induced subgraph is connected. Lemma 1 yields a motion leading to a configuration ′o such that H(,′)=H(V,o )=W. This proves the result. ∎ We now consider a fixed (tasked) agent i and a pivot vertex p in P, and investigate the existence of a feasible motion that brings agent i from (i)o(i) to p. We will give an explicit characterization of the existence, assuming the starting point is a p-adapted configuration. A clear sufficient condition for the existence of such a feasible motion is that d((i),p)≤h(,o)d(o(i),p)≤ h(V,o). Indeed, in this case, as the original configuration is p-adapted, one can distribute the unoccupied vertices to follow exactly a minimal path from (i)o(i) (excluded) to p without moving i. Then, a direct motion, in which only agent i moves along the empty path, leads it to p. However, this is not at all a necessary condition, as shown in the instance presented in Figure 4. Figure 4: In the top figure, a tasked agent i is positioned at the red vertex, at distance 66 from the pivot p in green. Despite there being only 44 unoccupied vertices (in white), a feasible motion that brings i to 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). Below, we describe a computable method for determining whether feasible motions exist that lead a tasked agent to a pivot p. It applies only to initial configurations that are p-adapted, so our characterization of the existence of solutions is not fully explicit. However, since the reduction to p-adapted configurations is achieved via polynomial algorithms, it is indeed fully computable. We indicate with C′C and C′C the 22-edge connected components to which (i)o(i) and p respectively belong. We then consider the unique path in the 22-edge condensation tree T from C′C to C′C , say C′=C0,C1,…,Cl=C′C =C_0,C_1,…,C_l=C . Furthermore, we let 0=m0<m1<m2<⋯<mr=l0=m_0<m_1<m_2<·s<m_r=l be such that Cmh∈11∪>1C_m_h _1^1 _>1 for every h=1,…,r−1h=1,…,r-1, while Ck∈10C_k _1^0 for all k∈1,…,l∖m1,…,mrk∈\1,…,l\ \m_1,…,m_r\. For h=0,…,rh=0,…,r, the binary variable ρh _h is set to 11 exactly when 0<h<r0<h<r and Cmh∈11C_m_h _1^1, namely when we are not considering the initial or final component and the component is a singleton of degree greater than two. We finally define the effective distance of agent i to p as the quantity dpeff((i)):=max0≤h≤r−1(mh+1−mh+ρh+ρh+1)d^\,eff_p(o(i)):= _0≤ h≤ r-1(m_h+1-m_h+ _h+ _h+1) (1) assuming, by convention, the maximum is 00 on empty sets. In the definition of dpeff((i))d_p^\,eff(o(i)), we are considering the maximum distance between two subsequent components that are not degree two singletons, augmented by one or two, depending on whether one or both components are singletons. Notice that, by construction, dpeff((i))≤d((i),p)d^\,eff_p(o(i))≤ d(o(i),p). Figure 4 (top) depicts a p-adapted configuration with a path of l=6l=6 22-edge connected components from (i)o(i) to p. Notice that in this case m1=3,m2=6m_1=3,m_2=6 and ρ1=1 _1=1 so that dpeff((i))=max3+1,3+1=4d^\,eff_p(o(i))= \3+1,3+1\=4. As the next result shows, this distance is of fundamental importance, as it determines the minimum number of unoccupied vertices required for a feasible motion that brings agent i to p to exist. Lemma 2. Let ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ) be a PS-MAPF instance and assume that o is p-adapted with respect to some pivot p. Given an agent i∈ti ^t, there exists a feasible motion that brings i to p if and only if the following condition holds: dpeff((i))≤h(,)=||−||d_p^\,eff(o(i))≤ h(V,o)=|V|-|A| (2) Proof. Consider the unique path in the 22-edge condensation graph C0,C1,…,ClC_0,C_1,…,C_l connecting C0C_0, the 22-edge connected component containing (i)o(i), to ClC_l the 22-edge connected component containing p. We prove both directions by induction on l. If l=0l=0, (i)o(i) and p lie in the same 22-edge connected component and the result follows from Thm. 1 and is independent of h(,)h(V,o). From now on, we assume that l≥1l≥ 1. We assume that condition (2) holds. If |C0|>1|C_0|>1 and C0C_0 contains at least one unoccupied vertex, then agent i, by first repositioning itself in the unique vertex v0∈C0v_0∈ C_0 connecting to C1C_1 and then freely following the pattern of unoccupied vertices, can reach p. We now assume that all vertices in C0C_0 are occupied. We also assume that (i)=v0o(i)=v_0, as it can always be reached with a motion only involving agents in C0C_0 thanks to Thm. 1, and that d(v0,p)>h(,)d(v_0,p)>h(V,o); if not, by setting the unoccupied vertices along a minimal path from v0v_0 to p, we again would directly construct the wanted feasible motion. Consider now the unique path in G, v0,v1..vm1v_0,v_1..v_m_1 where vk∈Ckv_k∈ C_k for k=0,1..m1k=0,1..m_1. Removing C0C_0, consider now the set of all vertices W belonging to the connected component of G containing p. By construction, we know that all unoccupied vertices are in W: h=h(,)=h(,)h=h(V,o)=h(W,o). Assume first that ρ1=0 _1=0. Consider any subset D of W of cardinality h and possessing the property that v1..vm1⊆\v_1..v_m_1\ , while the h−m1h-m_1 leftover vertices of D form a connected set of vertices containing p. Assumption (2) yields h≥m1h≥ m_1, which together with the case assumption d((i),p)>hd(o(i),p)>h ensures such a choice of D is possible. It follows from Lemma 1 that there exists a motion bringing the unoccupied vertices into D while maintaining fixed all agents j with (j)∉o(j) , so, in particular, agent i. Afterward, agent i can move to vertex vm1v_m_1 along the path of empty vertices. If r=1r=1, vm1v_m_1 and p are in the same 22-edge connected component, and we conclude using Thm. 1 again. Otherwise, |Cm1|>1|C_m_1|>1. If there are unoccupied vertices within Cm1C_m_1, then there is a path of unoccupied vertices leading to p and, as above, we could find a feasible motion bringing i to p. If not, let vm1+∈Cm1v^+_m_1∈ C_m_1 be the unique point in Cm1C_m_1 that is connected through an edge to some node in Cm1+1C_m_1+1. 22-edge connectivity implies that there exists v′∈Cm1v ∈ C_m_1 that is connected with an edge to vm1v_m_1 and whose removal does not disconnect vm1v_m_1 from vm1+v^+_m_1. A motion within the 22-edge connected component Cm1C_m_1 leads agent i to v′v and, afterward, unoccupied vertices can be again distributed to form a connected set containing p while leaving agent i still in node v′v . We are thus now again in a p-adapted configuration, and the number of 22-edge connected components between the position of i and p is equal to l−m1<l-m_1<l. Induction then applies. If instead ρ1=1 _1=1 so that Cm1C_m_1 is a branching component, consider any vertex v′∉vm1−1,vm1+1v ∈\v_m_1-1,v_m_1+1\ connected to vm1v_m_1. Consider now any subset D of W of cardinality h(,)h(W,o) and possessing the property that v1..vm1,v′⊆\v_1..v_m_1,v \ , while the remaining vertices form a connected set containing p. Assumption (2) yields h≥m1+1h≥ m_1+1, which together with the case assumption d((i),p)>hd(o(i),p)>h ensures such a choice of D is possible. t follows from Lemma 1 that there exists a motion bringing the unoccupied vertices into D while maintaining fixed all agents j with (j)∉o(j) , so, in particular, agent i. Afterward, agent i can move to vertex v′v along the path of empty vertices. If we now remove vertex v′v , we notice that, by construction, all empty vertices are in the component containing p (in the line v0..vm1\v_0..v_m_1\ and in a connected subset containing p). This implies that there exists a feasible motion leading again to a p-adapted configuration without moving agent i currently in v′v . Now, the new distance in the condensation tree between the components containing i and p is equal to l−m1+1l-m_1+1. If m1>1m_1>1, this is strictly less than l. In the case when m1=1m_1=1, we cannot directly apply the inductive reasoning. However, notice that, in this case, dpeff((i))≥m2−m1+ρ2+ρ1=m2+ρ2d_p^\,eff(o(i))≥ m_2-m_1+ _2+ _1=m_2+ _2. This implies that, in this case, we can work directly with the path from (i)o(i) to Cm2C_m_2, omitting the intermediate step Cm1C_m_1. In both cases ρ2=0 _2=0 and ρ2=1 _2=1, previous considerations allow us to apply the inductive argument and thus conclude the proof. Conversely, suppose that there exists a feasible motion Π=πjj∈ =\ _j\_j that brings i to p. Necessarily, agent i will need to touch all 22-edge-connected components along the path C0,C1,…,ClC_0,C_1,…,C_l during its motion. Let v0∈C0v_0∈ C_0 be the only node that is connected to C1C_1 through an edge. Consider then the unique path in G, v0,v1..vm1v_0,v_1..v_m_1 where vk∈Ckv_k∈ C_k for k=0,1..m1k=0,1..m_1. Let t1t_1 be the first time i visits vm1v_m_1 and let t0t_0 be the last time below t1t_1 that i visits v0v_0. Then, at every instant t∈[t0,t1]t∈[t_0,t_1], agent i will be in one of the vertices vk(t)v_k(t) for k(t)∈0..m1k(t)∈ 0..m_1. Indicate with h0≤h(,)h_0≤ h(V,o) the number of unoccupied vertices at time t0t_0 present in the connected component containing p when v0v_0 is removed. We indicate with h(t)h(t) the number of unoccupied vertices at time t present in the connected component containing p when the node vk(t)v_k(t) containing i is removed. A direct inductive reasoning shows that h(t)=h0−k(t)h(t)=h_0-k(t). In particular, 0≤h(t1)=h0−m10≤ h(t_1)=h_0-m_1 that yields h0≥m1h_0≥ m_1. In case ρ1=1 _1=1 and h0=m1h_0=m_1, there is no unoccupied position in the connected component containing p when the node vm1v_m_1 is removed, and thus, since all edges connecting vm1v_m_1 to nodes different from vm1−1v_m_1-1 are bridges, no further motion is possible. We assume that Π is a solution, so eventually i must move further, contradicting the assumption made. This implies that h0≥m1+1h_0≥ m_1+1. In any case, this proves that h(,)≥m1+ρ1h(V,o)≥ m_1+ _1 (3) As in the direct implication, in the case m1=1m_1=1 and ρ1=1 _1=1, we can not directly apply the inductive argument on distance, as when i reaches v′v , it is at the same distance from p as it was in v0v_0. In this case, we argue that also the condition h(,)≥m2+ρ2h(V,o)≥ m_2+ _2 (4) holds. This can be seen as follows. Let s2s_2 be the first time i visits vm2v_m_2 and let s1s_1 be the last time below s2s_2 that i visits v1=vm1v_1=v_m_1. Consider, moreover, s1−=maxt≤s1|π(t)≠vm1s_1^-= \t≤ s_1\,|\,π(t)≠ v_m_1\. By construction, we have that, at every instant t∈[s1−+1,s2]t∈[s_1^-+1,s_2], agent i will be in one of the vertices vk(t)v_k(t) for k(t)∈m1..m2k(t)∈ m_1..m_2. Indicate now with h1h_1 the number of unoccupied vertices at time s1−+1s_1^-+1 present in the connected component containing p when vm1v_m_1 is removed. Notice that the motion of i at time s1−s_1^- has left at least one empty node in one of the components not containing p. This yields h(,)≥h1+1h(V,o)≥ h_1+1. As above, we indicate with h(t)h(t) the number of unoccupied vertices at time t present in the connected component containing p when the node vk(t)v_k(t) containing i is removed. Direct inductive reasoning shows that h(t)=h1−k(t)+1h(t)=h_1-k(t)+1. In particular, 0≤h(s2)=h1−m2+10≤ h(s_2)=h_1-m_2+1 that yields h1≥m2−1h_1≥ m_2-1. With the same argument as above, we can improve the estimation to h1≥m2−1+ρ2h_1≥ m_2-1+ _2 that, together with h(,)≥h1+1h(V,o)≥ h_1+1, yields (4). In both cases (either (3) or, when m1=ρ1=1m_1= _1=1, (4)), using the direct implication (i.e. that condition (2) is sufficient for existence), we can bring i, through a feasible motion Π′ of length T′T , into a new position ′(i)=πi′(T)o (i)=π _i(T) whose distance in the condensation graph to p is strictly reduced, and the configuration ′=π′(T)o =π (T) is still p-adapted. Notice that from ′o there exists a feasible motion bringing i to p: it is sufficient to consider the concatenation of the inversion of Π′ with Π , namely the feasible motion Π∘(Π′)− ( )^-. By induction, dpeff(′(i))≤h(,′)=h(,)d^\,eff_p(o (i))≤ h(V,o )=h(V,o) and since, by the way ′o was defined, dpeff(′(i))=max1≤h≤r−1(mh+1−mh+ρh+ρh+1)d^\,eff_p(o (i))= _1≤ h≤ r-1(m_h+1-m_h+ _h+ _h+1) combined with h(,)≥h0≥m1+ρ1h(V,o)≥ h_0≥ m_1+ _1 yields the validity of relation (2). ∎ The effective distance defined in (1) depends on the particular p-adapted configuration we choose. However, the statement itself of Lemma 2 implies that condition (2) is a characterization of existence and thus it does not depend on the particular p-adapted configuration. Lemma 2 yields the following result. Theorem 2. A PS-MAPF instance ℐ=(,,,t,u,)I= (G,P,S,A^t,A^u,o ) is solvable if and only if, for every tasked agent i∈ti ^t, there exist a pivot p∈p and a p-adapted configuration c, reachable from o by a feasible motion, such that dpeff((i))≤h(,)=||−||.d^\,eff_p(c(i))≤ h(V,o)=|V|-|A|. (5) Proof. ’If’: Proposition 2 and Lemma 2 (using condition (5)) guarantee, for every tasked agent i, the existence of a feasible motion Πi ^i bringing agent i to touch a pivot. The concatenations of all such motions with their inversions (i.e., for agent i, we create a motion that reaches (i)c(i), visits p, and inverts back to (i)o(i), and then we concatenate these motions across agents) yield a feasible motion Π allowing all tasked agents to touch a pivot. We now consider the pivot-free instance ℐ′=(,,,∅,,Π(T))I =(G,P,S, ,A, (T)). By Prop. 1, a solution Π′ exists for ℐ′I . The concatenation Π′∘Π is finally, by construction, a successful feasible motion for ℐI. ’Only if’: Suppose Π=πii∈ =\ _i\_i is a solution of length T. For every agent i∈ti ^t, let p be a pivot such that πi(ti)=p _i(t_i)=p for some ti≤Tt_i≤ T. Consider the restriction Π|[0,ti] _|[0,t_i] of Π to the time interval [0,ti][0,t_i]. Let Π~i ^i be a motion of length TiT^i that brings the system, originally in configuration o, into a p-adapted configuration c. Then, Π|[0,ti]∘Π~i− _|[0,t_i] ^i- is a feasible motion from configuration c that leads i to pivot p. Thanks to Lemma 2, condition (5) holds true. ∎ Algorithmically, the check of necessary conditions in Thm. 2 can proceed as follows. For every pivot p∈p , we bring the system into any p-adapted configuration, and we let t(p)A^t(p) be the set of tasked agents for which condition (2) is satisfied. Existence of a solution is then equivalent to ∪p∈t(p)=t _p A^t(p)=A^t. The complexity is bounded, in the worst case, by |||P| polynomial reductions to pivot adapted configurations, and for each of them, the check of |t||A^t| conditions as (5). Finally, a simple structural condition guarantees solvability and underlies our experimental instances. Definition 5. A PS-MAPF instance ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o) is well-formed if, for every tasked agent i∈ti ^t, there is a path from (i)o(i) to some pivot p∈p none of whose vertices, other than the start (i)o(i), is the origin (j)o(j) of another agent j≠ij≠ i. Proposition 3. Every well-formed instance is solvable. Proof. Let ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o) be a well-formed instance and consider a tasked agent i∈ti ^t. Since ℐI is well-formed, there exists a pivot p∈p and a path γ from (i)o(i) to p such that all vertices along γ, with the exception of (i)o(i), are unoccupied by any other agent. Consider the subgraph ′G induced by the vertices of γ, ′V , and the corresponding restricted sub-instance for agent i: ℐ=(′,p,′,i,∅,(i))I=(G ,\p\,V ,i, ,o(i)). In this restricted setting, the initial configuration is trivially p-adapted and clearly satisfies condition (2). Thus, we can obtain a feasible motion Πi ^i_i that routes agent i from (i)o(i) to p within ′G . We can then construct a feasible motion Πi ^i for the full instance ℐI by applying the movements of Πi ^i_i to agent i while assigning wait actions to all other agents. This motion is strictly feasible because only agent i moves (precluding swapping conflicts), and it does so exclusively through unoccupied vertices (precluding vertex conflicts). By concatenating Πi ^i with its inversion Πi− ^i^-, agent i visits p and the system subsequently returns to the initial configuration o. Iterating this construction sequentially across all tasked agents yields a concatenated feasible motion Π of length T that allows every tasked agent to touch a pivot. We now consider the pivot-free instance ℐ′=(,,,∅,,Π(T))I =(G,P,S, ,A, (T)). By Proposition 1, a solution Π′ exists for ℐ′I . The concatenation Π′∘Π is finally, by construction, a successful feasible motion for ℐI. ∎ 4 Complexity Analysis We prove the NP-hardness of minimum station-makespan (MSM) and station-flowtime (MSF) decision problems. Problem 1. Given a PS-MAPF instance ℐI and k∈ℕk , is there a solution Π with Fℐ(Π)≤kF_S^I( )≤ k, where F∈M,ΣF∈\M, \? We refer to the MSM decision problem when F=MF=M, and to the MSF decision problem when F=ΣF= . We reduce from 3SAT (Cook 1971) in a similar fashion to Yu and LaValle (2013b). Our key additional insight is that strategically positioning the pivot in our constructed instance forces every agent to a predetermined station, thereby making the analysis similar to classical MAPF. Let (X,C)(X,C) be a 3SAT instance with n variables and m clauses, in conjunctive normal form (Sipser 2012) with at most three literals per clause. For each variable xix_i, create vertices vxiv_x_i and vxi′v_x_i joined by two internally disjoint paths of length m+3m+3, the “upper” and the “lower” path (Fig. 5); for each clause cjc_j, create vertices vcjv_c_j and vcj′v_c_j , connecting the vcj′v_c_j as a path from vc1′v_c_1 to vcm′v_c_m ; create a vertex p adjacent to vcm′v_c_m and to all the vxiv_x_i. Finally, for each cjc_j and each literal xi∈cjx_i∈ c_j, connect vcjv_c_j to the jthj^th vertex from vxiv_x_i on the upper path if xix_i is unnegated in cjc_j, and on the lower path if negated. The stations are =c∪xS=S^c ^x with c=vcj′|j∈[1..m]S^c=\v_c_j \,|\,j∈[1..m]\, and x=vxi′|i∈[1..n]S^x=\v_x_i \,|\,i∈[1..n]\; the agents are m tasked “clause agents” acja_c_j with (acj)=vcjo(a_c_j)=v_c_j and n untasked “variable agents” axia_x_i with (axi)=vxio(a_x_i)=v_x_i, yielding the instance ℐ=(,p,,t,u,)I=(G,\p\,S,A^t,A^u,o). Figure 5: Construction of PS-MAPF instance ℐI from 3SAT formula (x1∨x3¯∨x4)∧(x1¯∨x2∨x4¯)∧(x2¯∨x3∨x4)(x_1 x_3 x_4) ( x_1 x_2 x_4) ( x_2 x_3 x_4). Red/blue vertices are tasked/untasked agent origins, respectively. Yellow vertices are stations; orange vertices are pivots. Proposition 4. If (X,C)∈3SAT(X,C) 3SAT, then there is a solution Π with station-makespan Mℐ(Π)M_S^I( ) at most m+3m+3. Proof. For each xi∈Xx_i∈ X, if xix_i is set to true in the satisfying assignment, let axia_x_i use the lower path to vxi′v_x_i . If set to false, let it use the upper path. Because this is a satisfying assignment, each cj∈Cc_j∈ C contains at least one true literal, say corresponding to the variable xix_i. If xix_i is unnegated in cjc_j, then xix_i is set to true, and we have routed axia_x_i on the lower path. By our construction, vcjv_c_j connects to the upper path, which is now guaranteed to be unobstructed. Alternatively, if xix_i is negated in cjc_j, then xix_i is false and thus axia_x_i uses the upper path. In this case, we would have connected vcjv_c_j to the lower path, which is again unobstructed for acja_c_j. In short, each acja_c_j will have an unobstructed path to a vxiv_x_i. Furthermore, because each clause origin connect to upper/lower paths at a unique index, the clause agents arrive to the vxiv_x_i vertices at staggered times, preventing vertex conflicts. Specifically, ac1a_c_1 will arrive first, proceeding to p∈Vp∈ V and then to vc1′v_c_1 , followed sequentially by the remaining clause agents, which will filter into their respective stations. We have now described a solution Π where all agents traverse m+3m+3 edges without stopping, thus Mℐ(Π)≤m+3M_S^I( )≤ m+3. ∎ To prove the converse statement, we first establish several preliminary results. Lemma 3. The graph G has the following properties: (i) d(vxi,vxi′)=m+3d(v_x_i,v_x_i )=m+3 for every i in [1..n][1..n]; (i) d(vxi,vxℓ′)≥m+5d(v_x_i,v_x_ )≥ m+5 for every i,ℓi, in [1..n][1..n] with i≠ℓi≠ ; (i) d(p,vxi′)=m+4d(p,v_x_i )=m+4 for every i in [1..n][1..n]; (iv) d(p,vcj′)=m−j+1d(p,v_c_j )=m-j+1 for every j in [1..m][1..m]; (v) d(p,vcj)=j+2d(p,v_c_j)=j+2 for every j in [1..m][1..m]; Proof. Direct consequences of the way G is defined. ∎ A solution Π=πii∈ =\ _i\_i is called non-crossing if πa(T)∈c _a(T) ^c when a∈ta ^t and πa(T)∈x _a(T) ^x when a∈ua ^u. The following result holds. Lemma 4. Suppose Π=πii∈ =\ _i\_i is a solution of ℐI such that Mℐ(Π)≤m+3M_S^I( )≤ m+3. Then, Π is non-crossing. Proof. Suppose to the contrary that there is a j∈[1..m]j∈[1..m] such that πacj(T)∈x _a_c_j(T) ^x. Since clause agents must pass through p, items (i) and (v) of Lemma 3 imply that t(πacj)≥m+6+j>m+3,t_S( _a_c_j)≥ m+6+j>m+3, contradicting the assumption that Mℐ(Π)≤m+3M_S^I( )≤ m+3. ∎ Lemma 5. Suppose Π=πii∈ =\ _i\_i is a solution for ℐI of length T such that Mℐ(Π)≤m+3M_S^I( )≤ m+3. Then, πaxi(T)=vxi′∀i∈[1..n],πacj(T)=vcj′∀j∈[1..m]. _a_x_i(T)=v _x_i\ ∀ i∈[1..n], _a_c_j(T)=v _c_j\ ∀ j∈[1..m]. Proof. Considering the variable agents, Lemma 4 tells us that Π is non-crossing and, because of (i) and (i) of Lemma 3, we must have that πaxi(T)=vxi′ _a_x_i(T)=v _x_i for every i∈[1..n]i∈[1..n]. Regarding the clause agents, let Ω=j|πacj(T)≠vcj′ =\j\,|\, _a_c_j(T)≠ v _c_j\. If Ω is empty, the proof is complete. Otherwise, for h¯=maxΩ h= , we must have πach¯(T)=vch′ _a_c_ h(T)=v _c_h with some h<h¯h< h. It then follows from items (iv) and (v) of Lemma 3 that t(πach¯)≥m+3+h¯−h>m+3,t_S( _a_c_ h)≥ m+3+ h-h>m+3, a contradiction. ∎ Proposition 5. If there is a solution Π with Mℐ(Π)≤m+3M_S^I( )≤ m+3, then (X,C)∈3SAT(X,C) 3SAT. Proof. It follows from Lemmas 3 and 5 that each agent a follows a shortest path πa _a to its station destination without wait actions. In particular, since upper and lower paths are internally disjoint, a shortest path between vxiv_x_i and vxi′v_x_i is one of these two paths exclusively. Consequently, the variable agent axia_x_i occupies only one of these paths to reach vxi′v_x_i , ensuring the other path is free of variable agents and available for clause agents to move left on unobstructed. We extract a satisfying assignment for (X,C)(X,C) based on the paths that the clause agents take. Suppose acja_c_j uses the upper path of vxiv_x_i. By construction, vcjv_c_j connects to the upper path of vxiv_x_i only if xix_i is unnegated in cjc_j. So, in this case, we set xix_i to true and thus cjc_j is satisfied. Alternatively, if acja_c_j uses the lower path, then xix_i must be negated in cjc_j, so we set xix_i to false. Each clause agent must go through some unobstructed upper/lower path, so we can use this process to satisfy each clause. Thus, (X,C)(X,C) has a satisfying assignment. ∎ Theorem 3. The MSM decision problem is NP-hard. Proof. Direct consequence of Prop. 4 and 5. ∎ For the MSF decision problem, we show that Σℐ(Π)≤(m+n)(m+3) _S^I( )≤(m+n)(m+3) is equivalent to Mℐ(Π)≤m+3M_S^I( )≤ m+3 on the constructed instance. Lemma 6. Given a solution Π=πii∈ =\ _i\_i of the instance ℐI of length T, the following facts hold. (i) if an agent a¯ a is such that πa¯(T)∈c _ a(T) ^c, then t(πa¯)≥m+1t_S( _ a)≥ m+1. (i) if Π is non-crossing, t(πa)≥m+3t_S( _a)≥ m+3 for every a∈a . Proof. Suppose a¯ a is an agent such that πa¯(T)=vcj′ _ a(T)=v _c_j for some j∈[1..m]j∈[1..m]. Let ′A be the set of agents (tasked or untasked) a′a such that πa′(T)∈vc1′,…,vcj−1′ _a (T)∈\v _c_1,…,v _c_j-1\. As every path from origins to any clause-stations passes through p, every agent a∈′∪a¯a ∪\ a\ must necessarily pass through p in their motion πa _a. Moreover, if we let τa=maxt∈[0..T]|πa(t)=p _a= \t∈[0..T]\,|\, _a(t)=p\ to be the last time that agent a visits the pivot node p, we must have τa¯>τa′∀a′∈′ _ a> _a ∀ a (6) This can be seen formally as follows. Consider the natural total order on the line graph induced by the vertices c∪pS^c∪\p\, increasing from left to right. Then, πa(t)∈c _a(t) ^c and πa(t)<p _a(t)<p for every t>τat> _a for every a in ′∪a¯A ∪\ a\. If τa¯<τa′ _ a< _a for some a′∈′a , then, both agents a¯ a and a′a are in c∪pS^c∪\p\ from τa′ _a on. Since, by construction, πa¯(τa′)<πa′(τa′)=p _ a( _a )< _a ( _a )=p, the two agents must maintain such order of position at any future times (as we are assuming the absence of vertex or edge conflicts). However, this contradicts the fact that πa′(T)<vcj′=πa¯(T) _a (T)<v _c_j= _ a(T). As the absence of conflicts implies that a↦τa _a is injective among the agents passing through p, inequality (6) yields τa¯≥j _ a≥ j. Finally, t(πa¯)≥τa¯+d(p,vcj′)≥j+m−j+1=m+1,t_S( _ a)≥ _ a+d(p,v _c_j)≥ j+m-j+1=m+1, proving (i). If Π is non-crossing, in the above considerations, we have that ′⊆tA ^t and the stronger inequality τa′≥3 _a ≥ 3 for every a′∈′a . The estimation above now reads t(πa¯)≥τa¯+d(p,vcj′)≥j+2+m−j+1=m+3.t_S( _ a)≥ _ a+d(p,v _c_j)≥ j+2+m-j+1=m+3. Finally if a∈ua ^u, t(πa)≥m+3t_S( _a)≥ m+3 because of estimations (i) and (i) in Lemma 3. This proves (i). ∎ Lemma 7. Given any solution Π=πii∈ =\ _i\_i of the constructed instance ℐI, if Σℐ(Π)≤(m+n)(m+3) _S^I( )≤(m+n)(m+3), then Π is non-crossing. Proof. Let u(Π)=a∈u|πa(T)∈cA^u( )=\a ^u\,|\, _a(T) ^c\, t(Π)=a∈t|πa(T)∈xA^t( )=\a ^t\,|\, _a(T) ^x\, u(Π)c=u∖u(Π)A^u( )^c=A^u ^u( ), and t(Π)c=t∖t(Π)A^t( )^c=A^t ^t( ). Since ||=|||A|=|S|, necessarily, q=|u(Π)|=|t(Π)|q=|A^u( )|=|A^t( )|. For every tasked agent acj∈At(Π)ca_c_j∈ A^t( )^c, we let ℓj∈[1..m] _j∈[1..m] to be the index such that πacj(T)=vcℓj′ _a_c_j(T)=v _c_ _j. We now estimate the station-flowtime as follows: Σℐ(Π)=∑a∈t(πa)=∑a∈u(Π)t(πa)+∑a∈u(Π)ct(πa)+∑a∈t(Π)t(πa)+∑a∈t(Π)ct(πa)≥q(m+1)+(n−q)(m+3)+∑acj∈t(Π)(j+2+m+4)+∑acj∈t(Π)c(m+3+j−ℓj)=q(m+1)+(n−q)(m+3)+(m+6)q+(m+3)(m−q)+∑j=1mj−∑acj∈t(Π)cℓj≥(m+n)(m+3)+q, array[]rcl _S^I( )&=&Σ _a t_S( _a)\\[5.0pt] &=&Σ _a ^u( )t_S( _a)+Σ _a ^u( )^ct_S( _a)\\ &+&Σ _a ^t( )t_S( _a)+Σ _a ^t( )^ct_S( _a)\\[5.0pt] &≥&q(m+1)+(n-q)(m+3)\\[2.0pt] &+&Σ _a_c_j ^t( )(j+2+m+4)\\ &+&Σ _a_c_j ^t( )^c(m+3+j- _j)\\ &=&q(m+1)+(n-q)(m+3)\\ &+&(m+6)q+(m+3)(m-q)\\ &+&Σ _j=1^mj-Σ _a_c_j ^t( )^c _j\\ &≥&(m+n)(m+3)+q, array (7) where we have used Lemmas 3 and 6 in the first inequality, and the fact that j↦ℓj _j is an injective map in the second inequality. Thus, the assumption implies that q=0q=0, telling us Π is non-crossing. ∎ Proposition 6. Given any solution Π=πii∈ =\ _i\_i of the constructed instance ℐI, Σℐ(Π)≤(m+n)(m+3) _S^I( )≤(m+n)(m+3) if and only if Mℐ(Π)≤m+3M_S^I( )≤ m+3. Proof. We only need to show the “only if” part. Assume that Σℐ(Π)≤(m+n)(m+3) _S^I( )≤(m+n)(m+3). We know from Lemma 7 that Π is non-crossing. Then, Lemma 6 implies that t(πa)≥m+3t_S( _a)≥ m+3 for every agent a. Consequently, t(πa)=m+3t_S( _a)=m+3 for every a∈a and thus Mℐ(Π)=m+3M_S^I( )=m+3. ∎ Theorem 4. The MSF decision problem is NP-hard. Proof. Consequence of Theorem 3 and Proposition 6. ∎ Thms. 3 and 4 highlight a sharp complexity jump: pivot-free PS-MAPF is anonymous MAPF, hence polynomial-time solvable, yet our reduction uses a single pivot, so combining anonymous destinations with even one pivot-visit requirement makes both problems intractable. 5 Algorithms Building on Secs. 3 and 4, we develop three algorithms: a complete baseline (BA, Sec. 5.1) derived from the constructive solvability analysis, which solves every solvable instance but with very poor quality; a SAT-based solver (Sec. 5.3) computing makespan-optimal solutions at worst-case exponential cost; and, between the two, polynomial-time Pivot-Prioritized Planning (P, Sec. 5.2), of far higher quality than BA at the price of completeness: it may fail on solvable instances, but any solution it returns is correct. 5.1 Baseline Algorithm (BA) Our solvability analysis in Section 3 is constructive and directly yields a complete algorithm, which we adopt as a baseline and call BA. The algorithm processes tasked agents one at a time: for each tasked agent, it first brings the fleet into a p-adapted configuration (Proposition 2) and then routes the agent to a pivot via the motion constructed in the proof of Lemma 2. Once all tasked agents have passed through a pivot, the residual instance is pivot-free and is solved as an anonymous MAPF problem (Proposition 1). Concatenating these feasible motions yields a solution whenever one exists (Theorem 2), making the algorithm complete. BA, however, prioritizes completeness over solution quality: its sequential, one-agent-at-a-time construction yields station-makespan and station-flowtime values that leave substantial room for improvement. Algorithm A Baseline Algorithm (BA) 0: Feasible Instance ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o) 0: Global Solution Π 1: Π←∅ ← , σ←σ 2: ,ℱ←2EdgeCondensationTree()\N,F\← 2EdgeCondensationTree(G) 3: 10,11,>1←Decompose()\N_1^0,N_1^1,N_>1\← Decompose(N) 4: for all a∈ta ^t do 5: Π′←∅ ← 6: p,πsetup←SelectActivatablePivot(a,σ,,)p, _setup← SelectActivatablePivot(a,σ,P,G) 7: ApplyMotion(πsetup,σ) ApplyMotion( _setup,σ) 8: append πsetup _setup to Π′ 9: P←ShortestPath(σ(a),p,(,ℱ))P← ShortestPath(σ(a),p,(N,F)) 10: m0,…,mr←DecomposePath(P,11∪>1)\m_0,…,m_r\← DecomposePath(P,N_1^1 _>1) 11: for all h=0h=0 to r−1r-1 do 12: u←mhu← m_h, v←mh+1v← m_h+1 13: if u∈>1u _>1 then 14: πclear←Clear2EC(u,v,,σ,a) _clear← Clear2EC(u,v,G,σ,a) 15: else 16: πclear←ClearBranching(u,v,,σ,a) _clear← ClearBranching(u,v,G,σ,a) 17: end if 18: ApplyMotion(πclear,σ) ApplyMotion( _clear,σ) 19: append πclear _clear to Π′ 20: πadv←Advance(u,v,,σ,a) _adv← Advance(u,v,G,σ,a) 21: ApplyMotion(πadv,σ) ApplyMotion( _adv,σ) 22: append πadv _adv to Π′ 23: end for 24: if mr∈>1m_r _>1 then 25: πadv←Advance(mr,p,,σ,a) _adv← Advance(m_r,p,G,σ,a) 26: ApplyMotion(πadv,σ) ApplyMotion( _adv,σ) 27: append πadv _adv to Π′ 28: end if 29: Π′−←InvertMotion(Π′) -← InvertMotion( ) 30: ApplyMotion(Π′−,σ) ApplyMotion( -,σ) 31: append Π′ followed by Π′− - to Π 32: end for 33: πfinal←ARouting(,σ,) _final← ARouting(G,σ,S) 34: append πfinal _final to Π 35: return Π In Phase 1, tasked agents sequentially compute and execute paths to a pivot, subsequently rewinding the system state to ensure independent solvability (lines 4-32). The procedure relies on the graph’s 2-edge condensation tree, which is computed (line 2) and partitioned into distinct component types (line 3): non-singletons, branching singletons, and degree-two singletons. For a given tasked agent a∈ta ^t, the algorithm identifies an activatable pivot p (line 6) and determines the shortest path of components in the condensation tree leading to it (lines 9-10). The core of the pivot-routing logic (lines 11-23) iteratively prepares the graph for the agent’s progression: it repositions the unoccupied vertices (holes) to "clear" the way to the next component along the sequence. This is achieved using specific subroutines depending on whether the current component is a non-singleton 2-edge component or a branching singleton (lines 13-17), before advancing the agent into it (lines 19-21). A final advance step is performed if the pivot lies within a non-singleton component (lines 24-28). Crucially, to prevent agents from blocking each other, the algorithm inverts the agent’s entire motion sequence Π′ into Π′− - (line 29). Applying this inverse motion (line 30) completely rewinds the global state σ back to the initial configuration o. The concatenated forward and reverse motions are appended to the global solution (line 31), guaranteeing that every subsequent agent operates under the exact same initial conditions without interference. In Phase 2, after all tasked agents have visited their designated pivots and the global state has been safely restored to σ=σ=o, the problem reduces to a pivot-free instance. The algorithm executes an anonymous MAPF routing (line 33) to direct the entire fleet to the final station vertices in S. Because all pivot requirements are already satisfied in Phase 1, this final step leverages classical flow-based techniques to move the agents to their destinations without tracking their identities. The resulting motion πfinal _final is appended to complete the global solution Π (lines 34-36). Complexity Analysis. Let n=||n=|V|, m=|ℰ|m=|E|. Computing the 2-edge condensation tree and its decomposition (lines 2-3) takes (n+m)O(n+m) time. In Phase 1, the outer loop processes |t|≤n|A^t|≤ n tasked agents. For each agent, SelectActivatablePivot (line 6) evaluates at most ||≤n|P|≤ n pivots. For each candidate, verifying condition (2) requires reducing the system to a p-adapted configuration. Because this sub-problem is anonymous, we only need to route at most n unoccupied vertices (holes). Repositioning these holes along a spanning tree requires at most (n2)O(n^2) operations (Yu and LaValle 2013a). Crucially, because the global state is rewound to o after each agent, this evaluation can be computed once offline for all pivots and cached, taking (||n2)O(|P|n^2) time globally across the entire algorithm. Determining the shortest path in the condensation tree (line 9) takes (n)O(n). The inner loop (lines 11-23) advances the agent across at most n components. At each step, repositioning the holes (Clear2EC, ClearBranching) reduces to an anonymous MAPF problem costing (n2)O(n^2) operations (Yu and LaValle 2013a). Advancing the agent through a 2-edge-connected component (as established in Theorem 1) requires finding two edge-independent paths and performing synchronous cycle rotations; this moves at most n agents along a path of length at most n, taking (n2)O(n^2) time. Thus, clearing and advancing costs (n2)O(n^2) per component, leading to (n3)O(n^3) for the entire inner loop. Generating and applying the inverse motion (lines 29-30) traces back this sequence, taking another (n3)O(n^3). Processing a single agent therefore takes (n3)O(n^3) time, and over all tasked agents, Phase 1 costs (|t|n3)≤(n4)O(|A^t|n^3) (n^4). In Phase 2, ARouting (line 33) solves a final pivot-free instance; applying flow-based anonymous routing requires time at most (n3)O(n^3). Therefore, Phase 1 dominates, and the Baseline Algorithm runs in (|t|n3)≤(n4)O(|A^t|n^3) (n^4) worst-case time, proving it is strictly polynomial in the instance size. 5.2 Pivot-Prioritized Planning (P) P trades completeness for solution quality and speed, working in two phases: tasked agents are first routed to a pivot; the residual configuration is then an anonymous MAPF problem in which all agents move to the stations. Algorithm B Pivot-Prioritized Planning (P) 0: Instance ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o), Priority order σ=(σ1,…,σ|t|)σ=( _1,…, _|A^t|) 0: Valid solution Π , or ∅ if failure 1: ℛ←((a),t)∣a∈t,t∈[0,∞)R←\(o(a),t) a ^t,t∈[0,∞)\ 2: for j=1j=1 to |t||A^t| do 3: a←σja← _j 4: ℛ←ℛ∖((a),t)∣t∈[0,∞)R \(o(a),t) t∈[0,∞)\ 5: πa←ST-A∗((a),,,ℛ,max(0∪τσii<j)+||) _a -A^* (o(a),P,G,R, (\0\∪\ _ _i\_i<j)+|V| ) 6: if πa _a is ∅ then 7: return ∅ 8: end if 9: τa←arrival_time(πa,) _a \_time( _a,P) 10: ℛ←ℛ∪Reserve(πa)R ( _a) 11: end for 12: τmax←max(0∪τa∣a∈t) _ ← (\0\∪\ _a a ^t\ ) 13: for T=τmaxT= _ to τmax+2|| _ +2|V| do 14: f←MaxFlow(ext,un(T)(ℐ,ℛ,(πa,τa)a∈t))f (G_ext,un^(T)(I,R,\( _a, _a)\_a ^t) ) 15: if |f|==|||f|==|A| then 16: Π←ReconstructPaths(f,πa) (f,\ _a\) 17: return Π 18: end if 19: end for 20: return ∅ In Phase 1, tasked agents sequentially compute conflict-free paths to a pivot in priority order σ (lines 2-11), planning as if untasked agents were absent: moving them out of the way is deferred entirely to Phase 2. The start locations of lower-priority tasked agents are static obstacles: line 1 places an infinite-horizon reservation on every tasked origin in the table ℛR, and line 4 lifts only the current agent’s own reservation before its Space-Time A* search (Silver 2005) (line 5); ℛR stores occupied (vertex, time) and traversed (edge, time) pairs, preventing both vertex and swapping conflicts. If a tasked agent’s path traverses the initial location of an untasked agent at some t>0t>0, the crossing simply becomes a constraint on Phase 2, which must move that agent away before time t or fail. To guarantee termination even when a pivot is unreachable, the search horizon is bounded by the latest arrival time of any previously routed agent plus |||V| steps; if no path is found within it, the algorithm fails (lines 6-8). Otherwise, πa _a and its arrival time τa _a are stored, and ℛR is updated (lines 9-10) with all reservations induced by πa _a, each traversed edge recorded in both directions. In Phase 2, all agents must reach the stations in S without collisions; exploiting anonymity, we model this as a maximum flow (line 14) on a customized time-expanded graph for a horizon T≥τmax=maxa∈tτaT≥ _ = _a ^t _a (τmax=0 _ =0 if t=∅A^t= , line 12). As in Yu and LaValle (2013a), our graph ext,un(T)G_ext,un^(T) is built from the time-expanded graph of G for horizon T, adding a super-source and a super-sink. We prune all reserved nodes and their incident edges except for the final arrival nodes of tasked agents, namely all (v,t)∈ℛ∖J(v,t) J, where J=(πa(τa),τa)∣a∈tJ=\( _a( _a), _a) a ^t\. This prevents conflicts between the two phases. The super-source connects, through unit-capacity arcs, to the start locations of untasked agents at t=0t=0 and to the pivot locations of tasked agents at their arrival times t=τat= _a (the injection nodes); the super-sink connects to all station vertices at time T. If a flow of value |||A| is found (line 15), the paths are extracted (line 16): tasked agents concatenate their Phase 1 and flow paths, untasked agents use the flow path; otherwise the horizon is incremented, failing once the window is exhausted (line 20). The window searched in line 13 is strictly sufficient: Lemma 8. If a Phase 2 flow of value |||A| exists for some horizon T′≥τmaxT ≥ _ , then one exists for some T≤τmax+2||−1T≤ _ +2|V|-1. Proof. We first analyze the temporal extent of the reservations stored in ℛR at the conclusion of Phase 1. Initially, line 1 assigns infinite-horizon reservations to the starting locations of all tasked agents. However, during the execution of the loop (lines 3-11), line 4 systematically removes this infinite-horizon reservation for each agent a∈ta ^t prior to computing its path. The only reservations subsequently added to ℛR (line 10) are those strictly induced by the spatial and temporal traversal of the computed paths πa _a. Because every path πa _a terminates at time τa _a, and by definition τmax=maxa∈tτa _ = _a ^t _a, it follows that for all t>τmaxt> _ , no reservations exist in ℛR. Now, assume that a valid Phase 2 flow of value |||A| exists for some horizon T′≥τmaxT ≥ _ . This implies that the time-expanded graph ext,un(T′)G_ext,un^(T ) supports a collision-free routing, meaning that at time τmax _ , all |||A| agents (both tasked and untasked) are positioned at distinct vertices in G without any vertex or swapping conflicts. Let this valid configuration at time τmax _ be denoted as τmaxc_ _ . Because ℛR imposes no constraints for t>τmaxt> _ , the time-expanded graph for t>τmaxt> _ coincides exactly with the unconstrained time-expanded graph of G. Consequently, the routing problem from the intermediate configuration τmaxc_ _ to the set of stations S over the interval [τmax,T′][ _ ,T ] reduces to a standard, unconstrained anonymous MAPF instance. According to classical bounds on anonymous multi-agent path finding (Yu and LaValle 2013a), if such an instance is solvable, it can be completed in at most ||+||−1|A|+|V|-1 steps. Given that the number of agents is strictly bounded by the number of vertices (||≤|||A|≤|V|), the number of steps required from τmax _ to reach the stations cannot exceed 2||−12|V|-1. Therefore, if a flow exists for T′T , a valid flow of value |||A| is guaranteed to exist for a total horizon T satisfying T≤τmax+2||−1T≤ _ +2|V|-1. ∎ Phase 2 feasibility is also monotone in T so the returned horizon is the minimum admitting a conflict-free completion of the Phase 1 motions. Proposition 7. Given a PS-MAPF instance ℐI, if P (Algorithm B) returns a set of paths Π≠∅ ≠ , then Π∈Sol(ℐ) ∈ Sol(I). Proof. To prove that Π is a solution for ℐI, we must show that Π=πii∈ =\ _i\_i is a feasible motion of length T and that all paths are successful. First, the algorithm terminates successfully only if an integral maximum flow of value |||A| is found at some horizon T. Such a flow decomposes into |||A| arc-disjoint unit paths from the super-source to the super-sink; since each super-source arc has unit capacity and targets a distinct injection node, each unit path is unambiguously assigned to one agent. Every path in Π has length exactly T: for a tasked agent a, the Phase 1 path on [0..τa][0.. _a] is concatenated with its flow path on [τa..T][ _a..T], and the two agree at the handover node (πa(τa),τa)( _a( _a), _a), so the concatenation is well defined. We verify conflict-freedom separately for each kind of pair of path segments. (i) Two Phase 1 paths. Each Space-Time A* search respects all vertex and edge reservations accumulated in ℛR by higher-priority agents, while the origins of lower-priority tasked agents remain statically blocked until their turn; hence, no vertex or swapping conflict arises among Phase 1 paths. (i) Two Phase 2 paths. The unit vertex capacities of ext(T)G^(T)_ext make the flow paths vertex-disjoint at every time step, and its edge gadget forbids simultaneous opposite traversals of the same edge, excluding swapping conflicts. (i) A Phase 1 path of agent a and a Phase 2 path of a distinct agent b. Every vertex-time pair occupied by a Phase 1 motion belongs to ℛR and, unless it lies in J, is deleted from ext,un(T)G^(T)_ext,un; the flow path of b could therefore meet a Phase 1 motion only at an injection node. An integral flow of value |||A| saturates all |||A| unit-capacity super-source arcs, so each injection node already carries the unit injected by the super-source, and its unit vertex capacity admits no further unit; hence b’s flow path visits no injection node other than its own. Swapping conflicts between the two phases are excluded because reserved edge traversals are pruned in both directions. Consequently, the only vertex-time pair shared between a Phase 1 motion and a flow path is the handover node of one and the same tasked agent, which is not a conflict. Therefore, Π is a feasible motion. Second, we verify that every path is successful. By the initialization of the search spaces and super-source, πi(0)=(i) _i(0)=o(i) holds for all i∈i . For any untasked agent i∈ui ^u, the flow in Phase 2 connects its origin at t=0t=0 to the super-sink representing the stations S at time T. Thus, there exists a finite time-at-station t(πi)≤T<∞t_S( _i)≤ T<∞, making the path successful. For any tasked agent i∈ti ^t, Phase 1 explicitly routes the agent to a pivot in P at some time τi≤τmax _i≤ _ . Thus, there exists a finite time-at-pivot t(πi)≤τmax<∞t_P( _i)≤ _ <∞. Phase 2 then routes this agent from its pivot location to the super-sink representing S at time T, guaranteeing a finite time-at-station t(πi)≤T<∞t_S( _i)≤ T<∞. Since all conditions are met, every path in Π is successful. Because Π is a feasible motion and all its paths are successful, Π is a successful motion. Hence, Π∈Sol(ℐ) ∈ Sol(I). ∎ Complexity Analysis. Let n=||n=|V|, m=|ℰ|m=|E|. Induction on the line-5 horizon bound yields τa≤|t|n≤n2 _a≤|A^t|n≤ n^2, so Phase 1 costs (|t|m(τmax+n)logn)O(|A^t|m( _ +n) n) over its Space-Time A* searches. Phase 2 tries (n)O(n) horizons; for each, ext,un(T)G_ext,un^(T) has (mT)O(mT) arcs and a maximum flow needs at most ||≤n|A|≤ n augmenting-path computations of cost (mT)O(mT), giving (n2m(τmax+n))O(n^2m( _ +n)) overall, which dominates. Since τmax=(n2) _ =O(n^2), P runs in (n4m)O(n^4m) worst-case time, polynomial in the instance size. 5.3 SAT-Based Optimal Solver Reduction-based algorithms often empirically outperform search-based for classical MAPF in densely occupied environments (Surynek 2017; Stern 2019), the very regime motivating PS-MAPF. Consequently, our optimal solver follows the classical reduction-based strategy of sequentially increasing time horizons (Kautz and Selman 1992; Surynek 2017). We first use BA to determine if ℐI is solvable and, if so, obtain an upper bound on T∗T which prevents an infinite search. Then, we initialize T with the lower bound of Thm. 6 (see below) and construct a pseudo-Boolean formula Φ(T) (T) that is satisfiable if and only if ℐI admits a solution with station-makespan at most T (Thm. 5 below). We query an off-the-shelf solver with Φ(T) (T), incrementing T and repeating if Φ(T) (T) is unsatisfiable. The first satisfiable T equals T∗T , and the satisfying assignment yields an optimal solution. The standard “direct” encoding (Surynek 2022; Stern 2019) introduces a Boolean variable χa,v,t _a,v,t for every agent, vertex, and time step. However, we eliminate the dependency on |||A| by observing that tasked agents are identical to untasked agents once they have visited a pivot, and that constraints need not specify agent identities due to the anonymity of pivots and stations. Therefore, we say an agent is pivot-oriented (q=q=P) if it is tasked and has not yet visited a pivot, and station-oriented (q=q=S) otherwise. We call this encoding anonymized, with decision variables xv,tq=1x_v,t^q=1 iff any agent in state q occupies vertex v at time t∈[0..T]t∈[0..T], and yu,v,tq=1y_u,v,t^q=1 iff an agent in state q moves from u to v between times t−1t-1 and t∈[1..T]t∈[1..T]; the latter is defined for all (u,v)∈ℰ(u,v) and for u=vu=v (wait actions). Since reaching a pivot immediately transitions an agent to state S, a pivot-oriented agent never occupies a pivot: for q=q=P, xv,tqx^q_v,t is defined only for v∉v and yu,v,tqy^q_u,v,t only for u∉u . Any variable outside its defined domain is 00. With these variables, Φ(T) (T) is the conjunction of the constraints in Fig. 6, where N[v]=N[v]= u∈∣(u,v)∈ℰ\u (u,v) \ ∪v∪\v\ is the closed neighborhood of v. ⋀v∉⋀t=0T¬xv,t∨¬xv,t _v _t=0^T x_v,t^P x_v,t^S (C1a) ⋀t=1T⋀(u,v)∈ℰ(¬yu,v,t∧¬yu,v,t)∨(¬yv,u,t∧¬yv,u,t) _t=1^T _(u,v) ( y_u,v,t^P y_u,v,t^S) ( y_v,u,t^P y_v,u,t^S) (C1b) ⋀t=0T−1⋀v∉(xv,t=∑u∈N[v]yv,u,t+1) _t=0^T-1 _v (x_v,t^P= _u∈ N[v]y_v,u,t+1^P) (C2a) ⋀t=1T⋀v∉(xv,t=∑u∈N[v]∖yu,v,t) _t=1^T _v (x_v,t^P= _u∈ N[v] y_u,v,t^P) (C2b) ⋀t=0T−1⋀v∈(xv,t=∑u∈N[v]yv,u,t+1) _t=0^T-1 _v (x_v,t^S= _u∈ N[v]y_v,u,t+1^S) (C2c) ⋀t=1T⋀v∉(xv,t=∑u∈N[v]yu,v,t) _t=1^T _v (x_v,t^S= _u∈ N[v]y_u,v,t^S) (C2d) ⋀t=1T⋀v∈(xv,t=∑u∈N[v]∖yu,v,t+∑u∈N[v]yu,v,t) _t=1^T _v (x_v,t^S= _u∈ N[v] y_u,v,t^P+ _u∈ N[v]y_u,v,t^S) (C2e) ⋀v∈(u)xv,0∧⋀v∈(u)∖¬xv,0 [72.24144pt][l]$ _v (A^u)x_v,0^S$ _v (A^u) x_v,0^P (C3a) ⋀v∈(t)∩xv,0∧⋀v∈(t)∖(xv,0∧¬xv,0) [72.24144pt][l]$ _v (A^t) x_v,0^S$ _v (A^t) (x_v,0^P x_v,0^S) (C3b) ⋀v∉()¬xv,0∧⋀v∉()∪¬xv,0 [72.24144pt][l]$ _v (A) x_v,0^S$ _v (A) x_v,0^P (C3c) ⋀v∉¬xv,T∧⋀v∉¬xv,T [72.24144pt][l]$ _v x_v,T^S$ _v x_v,T^P (C3d) Figure 6: Pseudo-Boolean formula Φ(T) (T). The anonymized encoding cannot represent two agents at the same (state, vertex, time), and the flow conservation constraints (C2a)–(C2e) forbid agent paths from merges or splits. This prevents vertex conflicts within each state, and constraint (C1a) is the relevant, cross-state/non-pivot case. Constraint (C1b) excludes swapping conflicts by forbidding simultaneous, opposite traversals of an edge in any combination of states. Constraints (C2a)–(C2e) tie vertex occupancy to agent movement (an agent is at a vertex at time t iff exactly one incoming movement variable equals 11 at t and exactly one outgoing variable at t+1t+1) across pivot-/station-oriented and pivot/non-pivot vertex cases. Notably, (C2e) models an agent’s transition between states. Since (C2d) contains no y^P terms, the transition can occur only at a pivot which, combined with (C3d), forces every pivot-oriented agent through a pivot by time T. Constraints (C3a)–(C3c) set the t=0t=0 states of untasked origins, tasked origins, and unoccupied vertices. (C3d) requires that, at time T, all non-station vertices are unoccupied and no agent is pivot-oriented. Proposition 8. If Φ(T) (T) is satisfiable, then there exists Π with Mℐ(Π)≤TM_S^I( )≤ T. Proof. Given a satisfying assignment for Φ(T) (T), we generate a path πa _a for each a∈a as follows. First, set πa(0)=(a) _a(0)=o(a). Since (a)o(a) is injective, this gives us |||A| distinct origin locations, i.e. paths. Next, for each t∈[0..T−1]t∈[0..T-1], if πa(t)=u _a(t)=u, find the unique v such that yu,v,ty_u,v,t^P or yu,v,ty_u,v,t^S equals 11. Then set πa(t+1)=v _a(t+1)=v and repeat until we have identified πa(T) _a(T). To show that Π=πaa∈ =\ _a\_a is a solution for ℐI with Mℐ(Π)≤TM_S^I( )≤ T, we will first show that each πa _a is in fact a valid path from πa(0) _a(0) to πa(T) _a(T). Then, we will show that Π meets all the criteria for a solution to ℐI set out in Definition 2. As each path in Π is of length at most T, this achieves the desired result. Claim. Each πa _a is a valid path, Π is conflict-free. We first demonstrate that Π is free of vertex conflicts. Suppose two distinct paths occupy a vertex v at time t. This would require either two agents in different states or two agents in the same state converging on v. The former directly violates constraint (C1a). The latter is impossible due to the flow conservation constraints (C2b, C2d, C2e). Because variables are restricted to 0,1\0,1\ and the vertex variable is constrained to the sum of its incoming edge variables, at most one incoming edge variable can equal 11 for any given state. Thus paths cannot merge, implying that two paths of the same state cannot occupy the same vertex. Because we have established that exactly one agent occupies v at t, at most one of the outgoing flow constraints (C2a, C2c) can be activated. Consequently, constraints (C2a)-(C2e) enforce that a vertex variable equals 11 if and only if exactly one incoming and exactly one outgoing edge variable equal 11. Thus paths do not branch or spontaneously appear/disappear, making each πa _a a valid, continuous path. Finally, suppose a swapping conflict occurs between u and v at time t. This requires simultaneous traversals in opposite directions, meaning (yu,v,t∨yu,v,t)=1(y_u,v,t^P y_u,v,t^S)=1 and (yv,u,t∨yv,u,t)=1(y_v,u,t^P y_v,u,t^S)=1, which directly violates constraint (C1b). Thus, Π is entirely conflict-free. Claim. For all a∈a , πa(0)=(a) _a(0)=o(a) and πa(T)∈ _a(T) . By construction, πa(0)=(a) _a(0)=o(a) for all agents. Suppose there was a∈a such that πa(T)=v _a(T)=v with v∉v . Given how we traced πa _a from the satisfying assignment, this would imply that either yu,v,Ty_u,v,T^P or yu,v,Ty_u,v,T^S equals 11 for some u∈N[v]u∈ N[v]. Consequently, either xv,Tx_v,T^P or xv,Tx_v,T^S equals 11, due to the incoming flow constraints (C2b,C2d,C2e). Either case would violate (C3d) since v∉v , contradicting the assumption that we have a satisfying assignment. Claim. For all a∈ta ^t, there exists p∈p and t∈[0..T]t∈[0..T] such that πa(t)=p _a(t)=p. Suppose there exists a∈ta ^t with πa(t)∉ _a(t) for all t∈[0..T]t∈[0..T]. As πa(0) _a(0) is set to (a)∉o(a) , we know that x(a),0=1x_o(a),0^P=1. Since a never occupies a pivot, (C2e) is never “activated”. That is to say, the flow and vertex variables associated with a are always pivot-oriented, implying that xv,T=1x_v,T^P=1 where v=πa(T)v= _a(T). However, this violates (C3d), a contradiction. ∎ Proposition 9. If there exists Π with Mℐ(Π)≤TM_S^I( )≤ T, then Φ(T) (T) is satisfiable. Proof. To construct a satisfying assignment for Φ(T) (T), we use each πa∈Π _a∈ to determine which decision variables to set to 11, with all other variables set to 00. Using τa _a to abbreviate the time-at-pivot t(πa)t_P( _a), assign values as follows: xv,t=1⇔ x_v,t^P=1 ∃a∈t∣πa(t)=v,t<τa ∃ a ^t _a(t)=v,\ t< _a xv,t=1⇔ x_v,t^S=1 ∃a∈u|πa(t)=v∨ ∃ a ^u _a(t)=v\ ∃a∈t∣πa(t)=v,t≥τa ∃ a ^t _a(t)=v,\ t≥ _a yu,v,t=1⇔ y_u,v,t^P=1 ∃a∈t∣πa(t−1)=u,πa(t)=v,t≤τa ∃ a ^t _a(t-1)=u,\ _a(t)=v,\ t≤ _a yu,v,t=1⇔ y_u,v,t^S=1 ∃a∈u∣πa(t−1)=u,πa(t)=v∨ ∃ a ^u _a(t-1)=u,\ _a(t)=v\ ∃a∈t∣πa(t−1)=u,πa(t)=v,t>τa ∃ a ^t _a(t-1)=u,\ _a(t)=v,\ t> _a We now verify this assignment satisfies all constraints of Φ(T) (T). Claim. (C1a),(C1b) are satisfied. Since Π has no vertex conflicts, at most one agent occupies v at time t for all v∈v and t∈[0..T]t∈[0..T]. This single agent cannot be simultaneously tasked and untasked, nor before and after its time-at-pivot, thus our variable mapping will set at most one of xv,tx_v,t^P and xv,tx_v,t^S to 11, satisfying (C1a). Similarly, no two agents simultaneously traverse the same edge (u,v)(u,v) in opposite directions for all (u,v)∈ℰ(u,v) . Therefore, the conditions in our mapping for either yu,v,ty_u,v,t^P or yu,v,ty_u,v,t^S to be 11, and the conditions for either yv,u,ty_v,u,t^P or yv,u,ty_v,u,t^S to be 11, cannot both be satisfied. Thus at most one of (yu,v,ty_u,v,t^P or yu,v,ty_u,v,t^S) and (yv,u,ty_v,u,t^P or yv,u,ty_v,u,t^S) can be 11, satisfying (C1b). Claim. (C2a)-(C2e) are satisfied. As Π is a solution, all πa∈Π _a∈ are continuous, conflict-free paths without vertex conflicts. Therefore, a vertex v is visited by an agent a at time t if and only if it is preceded by exactly one edge traversal (or wait action) from some u∈N[v]u∈ N[v] at t (for t≥1t≥ 1), and succeeded by exactly one edge traversal (or wait action) to some w∈N[v]w∈ N[v] at t+1t+1 (for t≤T−1t≤ T-1). We show this fact satisfies (C2a)-(C2e) by looking at the three cases for the state of vertex v at time t. First, if no agent occupies v at time t, then our mapping will assign 00 to xv,t,xv,tx_v,t^P,x_v,t^S, as well as to any flow variable containing v as an endpoint (incoming at time t, outgoing at time t+1t+1). Thus both sides of each of (C2a)-(C2e) are 00, and satisfied. Second, if a pivot-oriented agent occupies v∉v at time t, then the mapping sets xv,t=1x_v,t^P=1 and xv,t=0x_v,t^S=0. The incoming flow must therefore be pivot-oriented, not station oriented, as a∈ta ^t and this traversal happens before τa _a. Thus (C2b) evaluates to 1=11=1 and (C2d) to 0=00=0. The outgoing flow must similarly be pivot oriented, thus (C2a) and (C2c) are satisfied at 1=11=1,0=00=0 respectively. Third, if a station-oriented agent a occupies v at t, we set xv,t=0x_v,t^P=0 and xv,t=1x_v,t^S=1. For incoming flow, if v∉v , then the incoming flow was already station-oriented. Thus (C2b) evaluates to 0=00=0 and (C2d) to 1=11=1. If v∈v , either a∈ta ^t and (C2e) is 1=1+01=1+0 or a∈ua ^u and it is 1=0+11=0+1. We know that the pivot-oriented incoming flow (a∈ta ^t) can only come from non-pivots because otherwise the flow would not be pivot-oriented. Outgoing flow will all be station-oriented (as a is already station-oriented at time t), so (C2c) and (C2a) are satisfied at 1=11=1, 0=00=0 respectively. Claim. (C3a)-(C3d) are satisfied. For any v∈(u)v (A^u), an untasked agent begins at v, thus our construction assigns xv,0=1x_v,0^S=1 and xv,0=0x_v,0^P=0, satisfying (C3a). For any v∈(t)v (A^t), if v∈v , then the agent a with (a)=vo(a)=v immediately has τa=0 _a=0. Thus we assign xv,0=1x_v,0^S=1. If v∉v , then τa>0 _a>0 and we set xv,0=1x_v,0^P=1 and xv,0=0x_v,0^S=0. In either case, (C3b) is satisfied. If v∈v contains no agent at t=0t=0, we set xv,0=xv,0=0x_v,0^P=x_v,0^S=0, satisfying (C3c). Finally, for (C3d), because Mℐ(Π)≤TM_S^I( )≤ T, every agent terminates its path at a station s∈s by time T. Thus no agent occupies any v∉v at time T, so we assign xv,T=0x_v,T^S=0 for all of them. Furthermore, since every a∈ta ^t reached a pivot at some time τa≤T _a≤ T, no xv,Tx_v,T^P will be set to 11. ∎ This proves each direction, giving us the desired equivalence. Theorem 5. Let ℐ=(,,,t,u,)I=(G,P,S,A^t,A^u,o) be a PS-MAPF instance and T∈ℕT . The formula Φ(T) (T) is satisfiable if and only if ℐI admits a solution Π with Mℐ(Π)≤TM_S^I( )≤ T. While (C2a)–(C2e) could be reduced to propositional logic with cardinality constraints (Cai et al. 2019; Frisch and Giannaros 2010) for a traditional SAT solver, doing so may cause a significant increase in the number of clauses. We thus maintain the pseudo-Boolean structure of Φ(T) (T) and rely on a solver with lazy clause generation, which dynamically generates Boolean conflict clauses from the sums only when necessary (Ohrimenko et al. 2026). 5.4 Lower Bounds The number of variables in the anonymized encoding does not depend on |||A|, so we expect it to outperform a direct encoding in dense instances. However, the algorithm’s efficiency depends heavily on a tight lower bound for T∗T , as every unsatisfiable query is a full SAT call. We derive one from the pivot bottleneck, assuming that t≠∅A^t≠ , otherwise the instance reduces to Anonymous MAPF and can be solved optimally in polynomial time (Yu and LaValle 2013a). For each a∈ta ^t, let δ(a)=minp∈d((a),p)δ(a)= _p d(o(a),p), the distance from its origin to its closest pivot. Sort the δ(a)δ(a) distances in ascending order to create the sequence (δ1,…,δ|t|)( _1,…, _|A^t|). Lemma 9. Let ℐI be a PS-MAPF instance with t≠0A^t≠ 0. For any solution Π of ℐI, let (t1,t2,…,t|t|)(t_1,t_2,…,t_|A^t|) be the time-at-pivots for tasked agents sorted in ascending order. Then, ti≥δi t_i≥ _i ∀i∈1,2,…|t| ∀ i∈\1,2,…|A^t|\ ti≥ti−||+1 t_i≥ t_i-|P|+1 ∀i∈||+1,…|t|. ∀ i∈\|P|+1,…|A^t|\. Proof. For the first statement, consider a fixed i∈1,2,…|t|i∈\1,2,…|A^t|\ and suppose that ti<δit_i< _i. Certainly the time-at-pivot of any agent a is at least δ(a)δ(a), as an agent can only travel across one edge per time step. Furthermore, there are i−1i-1 time-at-pivots smaller than tit_i, by definition. Therefore, i of the δ(a)δ(a) values are smaller than tit_i (and δi _i as well, by extension). However, this contradicts the definition of δi _i. For the second statement, observe that the set of pivots can “process” at most |||P| agents per time step, else there would be a vertex conflict. Thus ||+1|P|+1 agents cannot share the exact same time-at-pivot, i.e. the i-th agent to arrive at a pivot must arrive strictly later than the (i−||)(i-|P|)-th agent. ∎ These lower bounds depend recursively on the actual time-at-pivots, making them difficult to apply directly. To construct an explicit, independently computable lower bound, we define the sequence lil_i for i∈[1..|t|]i∈[1..|A^t|] as li=δil_i= _i if i≤||i≤|P|, and li=max(δi,li−||+1)l_i= ( _i,l_i-|P|+1) if i>||i>|P|. Lemma 10. Let ℐI be a PS-MAPF instance with t≠0A^t≠ 0. For any solution Π , let (t1,t2,…,t|t|)(t_1,t_2,…,t_|A^t|) be the time-at-pivots for tasked agents sorted in ascending order. Then ti≥lit_i≥ l_i for all i∈1,2,…,|t|i∈\1,2,…,|A^t|\. Proof. We proceed by induction on i. The base cases (i≤||i≤|P|) follow from Lemma 9 and the fact that li=δil_i= _i in this case. Now fix some j>||j>|P|, and assume that ti≥lit_i≥ l_i for all i<ji<j; we will show that tj≥ljt_j≥ l_j. By Lemma 9, we have that tj≥δjt_j≥ _j and tj≥tj−||+1t_j≥ t_j-|P|+1. As tj−||≥lj−||t_j-|P|≥ l_j-|P| by the inductive hypothesis, tj≥max(δj,lj−||+1)=lj.t_j≥ ( _j,l_j-|P|+1)=l_j. ∎ Theorem 6. For every solution Π of a PS-MAPF instance ℐI with t≠∅A^t≠ , Mℐ(Π)≥l|t|+minp∈,s∈d(p,s).M_S^I( )≥ l_|A^t|+ _p ,s d(p,s). Proof. First, we show that lil_i is an monotone non-decreasing sequence. This implies no element in the sequence is larger than l|t|l_|A^t|, thus some tasked agent has a time-at-pivot of at least l|t|l_|A^t|. So suppose instead that i is the first index at which li>li+1l_i>l_i+1. The δi _i sequence is sorted, meaning δi≤δi+1 _i≤ _i+1, leaving the case that i>||i>|P|. We know that li=max(δi,li−||+1)l_i= ( _i,l_i-|P|+1) must take the value li−||+1l_i-|P|+1, else li+1≥δi+1l_i+1≥ _i+1 would be greater than or equal to it. That is, li−||+1=li>li+1≥li+1−||+1.l_i-|P|+1=l_i>l_i+1≥ l_i+1-|P|+1. Subtracting one from both sides gives us that li−||>li+1−||l_i-|P|>l_i+1-|P|, contradicting the assumption that i is the first decreasing index, as desired. The tasked agent which first reaches a pivot no earlier than l|t|l_|A^t| must still reach the station at which it terminates, requiring at least minp∈,s∈d(p,s) _p ,s d(p,s) further steps. ∎ 6 Experimental Study Our experiments address two questions: on small grid instances where the optimal solver is viable, we map the empirical sources of difficulty of PS-MAPF, the tightness of the lower bound of Thm. 6, and P’s solution quality; on standard MAPF benchmarks probing those regimes at scale, we compare P against BA across five priority orderings and characterize P’s failure modes. The optimal solver was implemented using the C++ interface of CP-SAT (Perron and Didier 2025), while P and BA were programmed in Python 3.11. Experiments were run on a Linux cluster, with each Slurm job allocated 16 cores and 64 GB of RAM. Source code, preprocessing scripts, and generated instances will be made publicly available. (a) (b) Figure 7: (a) Optimal-solver performance over 10 feasible 16×1616× 16 instances (Obstacle%=0.2Obstacle\%=0.2) vs. agent density, by tasked percentage (Station%=Agent%Station\%=Agent\%, Pivot%=0.05Pivot\%=0.05); (b) Optimal-solver and P performances over 20 well-formed 16×1616× 16 instances (Obstacle%=0.2Obstacle\%=0.2) vs. pivot density (Agent%=Station%=0.15Agent\%=Station\%=0.15, Tasked%=0.5Tasked\%=0.5). 60-sec timeout. (a) Performance vs Obstacle %. (b) Performance vs Station %. (c) Performance vs Grid Size Solver empty-48-48 random-64-64-10 warehouse-10-20-10-2-1 Runtime ℐM_ S^I ℐ _ S^I Success Runtime ℐM_ S^I ℐ _ S^I Success Runtime ℐM_ S^I ℐ _ S^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 MC 8.82 31.38 2452.07 89.0 23.44 42.25 3842.34 83.5 137.76 91.74 16915.78 80.5 Table 1: Average Runtime (s), Station-Makespan (MℐM_S^I), Station-Flowtime (Σℐ _S^I) and Success Rate (%); for fairness, averages are over instances solved by all six algorithms. Best results among the P orderings are in bold. No time limit was imposed. 6.1 The SAT-Based Optimal Solver Instances are generated by randomly assigning vertices on a 16×1616× 16 grid to satisfy five parameters: the percentage of grid vertices that are blocked (Obstacle%=0.2), the percentage of unblocked vertices containing an agent origin (Agent%), the percentage of tasked agents (Tasked%), and the percentages of unblocked vertices designated as stations (Station%, at least Agent%) and as pivots (Pivot%). To understand the impact of agent density, we generate 10 feasible instances per configuration, maintaining Station%≥Agent%Station\% \% by setting them equal. We evaluate only the optimal algorithm here, as generating the well-formed instances required by P becomes prohibitively difficult at high agent densities. For pivot density, we compare the performance of all three solvers and fix Agent%=Station%=0.15Agent\%=Station\%=0.15 so that it is easier to find well-formed instances for P. We sweep pivot density geometrically from 0.1% to 30%, generating 20 well-formed instances per data point and excluding instances unsolved by P from the makespan averages. We use a 60-sec timeout. Instances with a large gap between T∗T and the bound of Thm. 6 are likelier to time out; discarding them would inflate the bound’s apparent tightness, so unsolved instances are plotted at the highest T reached before timeout. In the agent-density experiment, Figure 7(a) shows that performance depends on the combination of Agent% and Tasked%: runtimes spike at 50% agent density when all agents are tasked, while instances with 25% tasked agents remain tractable up to 90% density. An instance with 90% density and 25% tasked agents has significantly higher average runtime than one with 30% density and 75% tasked agents, despite both having 22.5% of unblocked vertices as tasked origins: the number of untasked agents (67.5% vs. 7.5%) does, in fact, affect difficulty. We similarly analyze non-agent or pivot parameters. Unsurprisingly, higher obstacle densities increase difficulty. Generating feasible instances becomes prohibitively difficult beyond 30% obstacles on 16×1616× 16 grids. Algorithm solve rates hold at 100% for obstacle densities up to 15%, but decline sharply to just 40% at 30% density. Conversely, increasing station density reduces problem difficulty. With Obstacle%=0.1Obstacle\%=0.1 and Agent%=0.4Agent\%=0.4, we solve all instances for station densities from 40% to 100%. Runtimes remain low throughout, and the average optimal makespan decreases linearly from 9.8 (at 40% density) to 8.4 (at 100% density). In terms of scalability, our algorithm efficiently solves 100% of 5 feasible instances on grids up to 20×2020× 20, and maintains an 80% success rate on 28×2828× 28 grids. An increase in pivot density is most impactful for small |||P| (1–10% density), as the gains in success rate and the reductions in makespan level off past that point. BA failed to solve any instance within the 60-sec limit, likely bottlenecked by repeated maximum-flow resolutions during its constructive phases. However, P excelled across all jointly solved instances, averaging a runtime of just 0.359 sec compared to 14.185 sec for the SAT solver and maintaining an average makespan gap strictly between 0.55 and 2.73 steps. 6.2 P vs. Baseline Algorithm P uses a given priority order for the tasked agents, and we evaluate several well-known ordering heuristics (Ma et al. 2019; Bennewitz et al. 2001): SH (Shortest path first) prioritizes agents with shorter shortest paths to a pivot, LH (Longest path first) the opposite, and RND (Random) orders agents uniformly at random (fixed seed 42 for reproducibility). We also evaluate two conflict-based orderings: for each tasked agent, we generate a static, shortest path to a pivot and count the spatio-temporal (vertex and edge) collisions it shares with the others’ static paths; LC (Least Conflicts first) prioritizes agents with fewer initial conflicts, MC (Most Conflicts first) those with more. We perform experiments on three maps from the Moving AI benchmark (Stern et al. 2019): empty 48×4848× 48 grids, 64×6464× 64 grids with 10% obstacle density, and warehouse maps, covering diverse topologies and congestion levels. For each map, we generated 200 well-formed instances with number of pivots in 1,5,10,20,30\1,5,10,20,30\, proportion of tasked agents in 10%,25%,50%,75%,100%\10\%,25\%,50\%,75\%,100\%\, and total number of agents over eight evenly spaced values, from 1% of the map’s free cells to the maximum multiple of 10 yielding a well-formed instance: 150 (empty), 170 (random), 340 (warehouse). Table 1 presents the evaluated cost metrics and success rates. BA is complete but incurs prohibitive computational and qualitative costs; P sacrifices completeness for massive efficiency gains, maintaining a 74–89% success rate while drastically outperforming BA across all metrics and solving warehouse instances in half the time with orders-of-magnitude lower makespan and flowtime. Among the heuristics, no ordering dominates, but MC is the strongest overall, achieving the lowest average runtimes on the two denser maps and the highest success rate on the empty map, while remaining competitive on every metric elsewhere. P’s failures concentrate in extreme bottleneck scenarios (e.g., 1–5 pivots, 75–100% tasked agents): Phase 1 always completes on our instances but saturates ℛR, and this prevents the Phase 2 flow from routing all agents within the allowed horizon, making all heuristics fail simultaneously at critical density thresholds, though MC resolves borderline instances where the others get stuck. 7 Conclusion and Future Work We introduced PS-MAPF, a MAPF variant in which tasked agents must reach an anonymous pivot before the entire fleet terminates at anonymous stations. We characterized solvability completely, proved that minimizing station-makespan and station-flowtime is NP-hard already with a single pivot, and presented three algorithms: a complete, low-quality baseline, a SAT-based makespan-optimal solver, and the incomplete but fast Pivot-Prioritized Planning (P), with solutions orders of magnitude better than the baseline. Future work includes pivot-based objectives, domain-specific solvers, and adapting state-of-the-art MAPF techniques to PS-MAPF. References Asín Achá et al. (2022) R. Asín Achá, R. López, S. Hagedorn, and J. A. Baier Multi-Agent Path Finding: A New Boolean Encoding. Journal of Artificial Intelligence Research 75, p. 597–624. External Links: Link Cited by: §1. Bennewitz et al. (2001) M. Bennewitz, W. Burgard, and S. Thrun Optimizing Schedules for Prioritized Path Planning of Multi-Robot Systems. In Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1, Piscataway, NJ, p. 271–276. External Links: Link Cited by: §6.2. Cai et al. (2019) J. Cai, Y. Su, X. Yang, J. Min, and Y. Lai A New SAT Encoding Scheme for Exactly-One Constraints. Journal of Physics: Conference Series 1288, p. 012035. External Links: Link Cited by: §5.3. Cook (1971) S. A. Cook The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, New York, NY, p. 151–158. External Links: Link Cited by: §4. Diestel (2017) R. Diestel Graph Theory. 5th edition, Graduate Texts in Mathematics, Vol. 173, Springer, Berlin, Heidelberg. External Links: Link Cited by: §3. Erdmann and Lozano-Pérez (1987) M. Erdmann and T. Lozano-Pérez On Multiple Moving Objects. Algorithmica 2, p. 477–521. External Links: Link Cited by: §1. Felner and Stern (2026) A. Felner and R. Stern Multi-Agent Path Finding with Unassigned Agents (MAPFUA). In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, Menlo Park, CA, p. 39691–39698. External Links: Link Cited by: §1. Frisch and Giannaros (2010) A. M. Frisch and P. A. Giannaros SAT Encodings of the At-Most-k Constraint: Some Old, Some New, Some Fast, Some Slow. In Proceedings of the Tenth International Workshop of Constraint Modelling and Reformulation, p. 36. External Links: Link Cited by: §5.3. Kautz and Selman (1992) H. A. Kautz and B. Selman Planning as Satisfiability. In Proceedings of the 10th European Conference on Artificial Intelligence, Chichester, p. 359–363. External Links: Link Cited by: §5.3. Kornhauser et al. (1984) D. Kornhauser, G. L. Miller, and P. G. Spirakis Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, Washington, DC, p. 241–250. External Links: Link Cited by: §1, §3. Luna and Bekris (2011) R. Luna and K. E. Bekris Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, Menlo Park, CA, p. 294–300. External Links: Link Cited by: §1. Ma et al. (2019) H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig Searching with Consistent Prioritization for Multi-Agent Path Finding. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, Vol. 33, Menlo Park, CA, p. 7643–7650. External Links: Link Cited by: §1, §6.2. Ma et al. (2016) H. Ma, S. Koenig, N. Ayanian, L. Cohen, W. Hönig, T. K. S. Kumar, T. Uras, H. Xu, C. Tovey, and G. Sharon Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios. In Proceedings of the IJCAI Workshop on Multi-Agent Path Finding, External Links: Link Cited by: §1. Ma and Koenig (2016) H. Ma and S. Koenig Optimal Target Assignment and Path Finding for Teams of Agents. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Richland, SC, p. 1144–1152. External Links: Link Cited by: §1. Ma et al. (2017) H. Ma, J. Li, T. K. S. Kumar, and S. Koenig Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks. In Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems, Richland, SC, p. 837–845. External Links: Link Cited by: §1. Makino and Ito (2026) H. Makino and S. Ito MAPF-HD: Multi-Agent Path Finding in High-Density Environments. IEEE Robotics & Automation Magazine , p. 2–12. External Links: Link Cited by: §1. Nguyen et al. (2017) V. Nguyen, P. Obermeier, T. C. Son, T. Schaub, and W. Yeoh Generalized Target Assignment and Path Finding Using Answer Set Programming. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Menlo Park, CA, p. 1216–1223. External Links: Link Cited by: §1. Ohrimenko et al. (2026) O. Ohrimenko, P. Stuckey, and M. Codish Lazy Clause Generation in Retrospect. Constraints , p. . External Links: Link Cited by: §5.3. Okumura (2024) K. Okumura Engineering LaCAM*: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding. In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, Richland, SC, p. 1501–1509. External Links: Link Cited by: §1. Perron and Didier (2025) L. Perron and F. Didier CP-SAT (Version 9.12). Note: https://developers.google.com/optimization/cp/cp_solver/Accessed: 2026-07-24 Cited by: §6. Ren et al. (2021) Z. Ren, S. Rathinam, and H. Choset MS*: A New Exact Algorithm for Multi-Agent Simultaneous Multi-Goal Sequencing and Path Finding. In Proceedings of the IEEE International Conference on Robotics and Automation, Piscataway, NJ, p. 11560–11565. External Links: Link Cited by: §1. Ren et al. (2022) Z. Ren, S. Rathinam, and H. Choset Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding. In Proceedings of Robotics: Science and Systems, New York, NY. External Links: Link Cited by: §1. Sharon et al. (2015) G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence 219, p. 40–66. External Links: Link Cited by: §1. Silver (2005) D. Silver Cooperative Pathfinding. In Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Menlo Park, CA, p. 117–122. External Links: Link Cited by: §1, §5.2. Sipser (2012) M. Sipser Introduction to the Theory of Computation. 3rd edition, Cengage Learning, Boston, MA. External Links: Link Cited by: §4. Stern et al. (2019) R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. In Proceedings of the Twelfth Annual Symposium on Combinatorial Search, Vol. 10, Menlo Park, CA, p. 151–158. External Links: Link Cited by: §1, §1, §6.2. Stern (2019) R. Stern Multi-Agent Path Finding – An Overview. In Artificial Intelligence: 5th RAAI Summer School, G. S. Osipov, A. I. Panov, and K. S. Yakovlev (Eds.), p. 96–115. External Links: Link Cited by: §5.3, §5.3. Surynek et al. (2016) P. Surynek, A. Felner, R. Stern, and E. Boyarski Efficient SAT Approach to Multi-Agent Path Finding Under the Sum of Costs Objective. In Proceedings of the Twenty-Second European Conference on Artificial Intelligence, Amsterdam, Netherlands, p. 810–818. External Links: Link Cited by: §1. Surynek (2009) P. Surynek A Novel Approach to Path Planning for Multiple Robots in Bi-connected Graphs. In Proceedings of the IEEE International Conference on Robotics and Automation, Piscataway, NJ, p. 3613–3619. External Links: Link Cited by: §1. Surynek (2017) P. Surynek Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems. Annals of Mathematics and Artificial Intelligence 81 (3–4), p. 329–375. External Links: Link Cited by: §5.3. Surynek (2019) P. Surynek Unifying Search-Based and Compilation-Based Approaches to Multi-Agent Path Finding Through Satisfiability Modulo Theories. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, Menlo Park, CA, p. 1177–1183. External Links: Link Cited by: §1. Surynek (2021) P. Surynek Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, Menlo Park, CA, p. 12409–12417. External Links: Link Cited by: §1. Surynek (2022) P. Surynek Problem Compilation for Multi-Agent Path Finding: A Survey. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, Menlo Park, CA, p. 5615–5622. External Links: Link Cited by: §5.3. Yu and LaValle (2013a) J. Yu and S. M. LaValle Multi-agent Path Planning and Network Flow. In Algorithmic Foundations of Robotics X, p. 157–173. External Links: Link Cited by: §1, §3, §5.1, §5.2, §5.2, §5.4. Yu and LaValle (2013b) J. Yu and S. M. LaValle Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs. In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, Menlo Park, CA, p. 1443–1449. External Links: Link Cited by: §1, §4.