Paper deep dive
Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations
Chuanlong Zang, Isabelle Barz, Anna Mannucci, Philipp Schillinger, Florian Lier, Wolfgang Hönig
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/21/2026, 5:30:14 AM
Summary
The paper addresses the Multi-Subsystem Multi-Agent Pickup and Delivery (MS-MAPD) problem with buffer-limited handover stations (MS-MAPD-BHS). It proposes Handover-Aware Reservation and Routing (HARR), an online controller that coordinates separate agent fleets by coupling per-subsystem Token Passing planners via shared dock reservation calendars and deterministic buffer occupancy projections. HARR ensures collision-free dock usage and buffer safety, achieving significant improvements in throughput and backlog reduction compared to baselines.
Entities (7)
Relation Signals (7)
Handover Station → has → Dock
confidence 95% · These stations, equipped with single docks and finite buffers
Handover Station → has → Buffer
confidence 95% · These stations, equipped with single docks and finite buffers
HARR → solves → MS-MAPD-BHS
confidence 95% · We formalize this problem as Multi-Subsystem MAPD with Buffer-limited Handover Stations (MS-MAPD-BHS). We then propose Handover-Aware Reservation and Routing (HARR)...
HARR → coordinates → Handover Station
confidence 90% · HARR uses a shared dock reservation calendar and a deterministic rolling-horizon projection of buffer occupancy to coordinate actions.
HARR → uses → Token Passing
confidence 90% · HARR couples per-subsystem Token Passing (TP) planners using a shared dock calendar
HARR → improves → Throughput
confidence 85% · HARR achieves up to 77% higher throughput... than a fixed-dock ablation
HARR → reduces → Backlog
confidence 85% · HARR achieves... 92% lower backlog than a fixed-dock ablation
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Coordinating payload transfers between subsystems is a critical challenge in lifelong Multi-Agent Pickup and Delivery (MAPD). We study systems where agents are confined to separate regions and must exchange payloads through shared handover stations. These stations, equipped with single docks and finite buffers, are inherently vulnerable to blocking and starvation. We formalize this problem as Multi-Subsystem MAPD with Buffer-limited Handover Stations (MS-MAPD-BHS). We then propose Handover-Aware Reservation and Routing (HARR), an online controller that couples per-subsystem planners. HARR uses a shared dock reservation calendar and a deterministic rolling-horizon projection of buffer occupancy to coordinate actions. A candidate route is accepted only if its dock interval is free and the resulting buffer occupancy projection remains within capacity. Under perfect execution, these checks ensure collision-free dock use and buffer-safe committed operations within the reservation horizon. In simulation, HARR achieves up to 77% higher throughput and 92% lower backlog than a fixed-dock ablation at moderate load, while also reducing planning time relative to a coupled station-aware Token Passing baseline. These results show that explicit interface coordination substantially improves stability in modular multi-subsystem transport.
Tags
Links
- Source: https://arxiv.org/abs/2607.17724v1
- Canonical: https://arxiv.org/abs/2607.17724v1
Trouble viewing inline? Open PDF directly →
Full Text
46,788 characters extracted from source content.
Expand or collapse full text
Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations Chuanlong Zang1,2, Isabelle Barz1, Anna Mannucci1, Philipp Schillinger1, Florian Lier1, Wolfgang Hönig2,3 1Robert Bosch GmbH, Corporate Research, Stuttgart, Germany. Chuanlong.Zang@de.bosch.com2Technical University of Berlin, Berlin, Germany.3Robotics Institute Germany (RIG). Abstract Coordinating payload transfers between subsystems is a critical challenge in lifelong Multi-Agent Pickup and Delivery (MAPD). We study systems where agents are confined to separate regions and must exchange payloads through shared handover stations. These stations, equipped with single docks and finite buffers, are inherently vulnerable to blocking and starvation. We formalize this problem as Multi-Subsystem MAPD with Buffer-limited Handover Stations (MS-MAPD-BHS). We then propose Handover-Aware Reservation and Routing (HARR), an online controller that couples per-subsystem planners. HARR uses a shared dock reservation calendar and a deterministic rolling-horizon projection of buffer occupancy to coordinate actions. A candidate route is accepted only if its dock interval is free and the resulting buffer occupancy projection remains within capacity. Under perfect execution, these checks ensure collision-free dock use and buffer-safe committed operations within the reservation horizon. In simulation, HARR achieves up to 77% higher throughput and 92% lower backlog than a fixed-dock ablation at moderate load, while also reducing planning time relative to a coupled station-aware Token Passing baseline. These results show that explicit interface coordination substantially improves stability in modular multi-subsystem transport. I Introduction Multi-Agent Pathfinding (MAPF) and especially its lifelong variants, such as Multi-Agent Pickup and Delivery (MAPD), provide foundational tools for coordinated transport in warehouses, factories, and traffic systems. These frameworks couple task allocation with collision-free routing under continuous task arrivals [18, 20, 15]. While powerful, they typically assume a single, globally-coordinated fleet. However, many real-world deployments are inherently multi-subsystem, where distinct agent fleets operate within separate regions — often under different management — but must collaboratively exchange payloads at shared interfaces to complete end-to-end transport. Examples range from multi-vendor logistics, robotic systems interfacing with conveyors to heterogeneous cooperative teams and interacting subsystems in terminals [4, 12, 24, 1]. The primary challenge in such distributed architectures lies in coordinating the interfaces between subsystems without sacrificing modularity or scalability. Our focus is on the common scenario where subsystems exchange payloads exclusively through fixed handover stations. Unlike in standard MAPD, each handover station is a critical shared resource: it has one dock vertex with exclusive access, non-preemptive operation times, and a finite-capacity buffer. Under realistic load, these constraints can cause upstream blocking (an unload cannot start because the buffer is full) and downstream starvation (a load cannot start because the requested payload is unavailable), even when motion within each individual subsystem is efficient [3, 6]. Here, buffer safety means that no accepted operation causes a station buffer to underflow or exceed its capacity, whereas availability coordination means that a downstream load is reserved only for a payload already present at that station. Consequently, merely running independent MAPD solvers and allowing agents to ‘queue’ at the interface can commit mutually incompatible station operations. To address this challenge, we formalize MS-MAPD-BHS (Multi-Subsystem MAPD with Buffer-limited Handover Stations) and propose HARR (Handover-Aware Reservation and Routing). HARR schedules two-sided station operations while respecting dock exclusivity and finite-buffer dynamics. Its interface state is a deterministic schedule derived from operations that have already been accepted. Figure 1: Two-fleet lifelong MAPD with buffer-limited handover stations. The crossed-circle marking on the upper route denotes a dock entry that is inadmissible at the illustrated timestep because the loaded upstream agent would unload into a full buffer; it does not make the entire route permanently forbidden. The agent may wait or replan and enter after capacity becomes available. The main contributions of this paper are: • We formally define MS-MAPD-BHS, a lifelong multi-subsystem pickup-and-delivery problem where agents are confined to regions and inter-subsystem transfers occur only through shared handover stations with single-dock access, non-preemptive load/unload times, and finite-capacity buffers with explicit dynamics (Fig. 1). • We propose HARR, an online controller that couples per-subsystem Token Passing (TP) planners [20] using a shared dock calendar and a deterministic rolling-horizon buffer occupancy projection. Candidate plans are accepted only when the dock interval is free and the resulting committed buffer schedule remains feasible. • We evaluate mean service time under online task arrivals, comparing HARR against a coupled TP reference and a fixed-dock ablation, measuring service time, throughput, backlog, and planning cost. I Related Work MAPF methods range from optimal search variants to bounded-suboptimal, large-neighborhood, prioritized, and rolling-horizon approaches [25, 13]. Package-exchange and shared-infrastructure variants also exist [21, 14], but do not address lifelong finite-buffer transfer. Online Multi-Agent Pickup and Delivery (MAPD), where tasks arrive dynamically, is commonly addressed via Token Passing (TP) and reservation-table methods [20, 19]. Other MAPD variants incorporate richer objectives and constraints like task deadlines [22, 17], external agents [2], kinematic constraints [19], or exchange coordination (e.g., PERR, MAPD-MP [11], MAPF-E [14], MAPD-HA [10]). These formulations enrich tasks and motion, but do not model a finite-capacity, single-server transfer interface that stores payloads between independently operating fleets. Cooperation among heterogeneous teams is also studied outside MAPD. For example, decentralized hierarchical planning coordinates aerial and ground vehicles with distinct capabilities [1]. Such work motivates inter-team task decomposition and coordination, but does not address lifelong collision-free payload flow through a shared finite buffer. Conversely, parcel-transshipment research studies terminal capacity, sorting resources, blocking, and combined simulation and optimization [23, 7]. These models provide relevant operational context for handover bottlenecks, but typically aggregate parcel flow rather than plan time-indexed trajectories for individual robots. Table I positions MS-MAPD-BHS along five dimensions: online task arrivals, multiple fleets or environments, explicit payload transfer, finite transfer-point storage, and time windows or deadlines. Existing work covers several of these dimensions separately, but not their combination. In particular, it does not explicitly model the buffer dynamics that create blocking and starvation at an asynchronous handover interface, as highlighted by the Buf column. HARR is complementary to work on joint task allocation and path planning [16, 9, 5]. Rather than redesigning allocation or MAPF solvers, it augments scalable online MAPD with explicit dock and buffer calendars while keeping motion planning subsystem-local. TABLE I: Comparison of related MAPF and MAPD variants. Variants Online Multi Xfer Buf TW PDP [8] ✓ ✗ ✓ ✗ ✓ PERR [21] ✗ ✗ ✓ ✗ ✗ online MAPD [20] ✓ ✗ ✗ ✗ ✗ MAPD-D [22] ✓ ✗ ✗ ✗ ✓ MAPD-MP [11] ✓ ✓ ✓ ✗ ✗ MAPD-EA [2] ✓ ✓ ✗ ✗ ✗ DPDTW [17] ✓ ✗ ✗ ✗ ✓ MAPF-E [14] ✗ ✓ ✗ ✗ ✗ MAPD-HA [10] ✓ ✓ ✓ ✗ ✗ MS-MAPD-BHS (ours) ✓ ✓ ✓ ✓ ✗ Online: Online tasks. Multi: multiple fleets/environments. Xfer: handover/exchange. Buf: buffer/storage. TW: time windows/deadlines. I Problem Statement We formally define MS-MAPD-BHS: Multi-Subsystem MAPD with Buffer-limited Handover Stations. We study the two-subsystem, one-way-flow case, which is the smallest setting in which a shared finite buffer induces blocking and starvation. The controller and experiments are limited to this case; reverse flow, bidirectional competition for the same station, and chains with more than two subsystems are outside the evaluated scope. Throughout this section, we use the notation summarized in Table I. TABLE I: Selected notation used in Sec. I. Symbol Meaning G=(V,E)G=(V,E) global undirected graph environment Vi⊆V_i V vertex set of subsystem i Gi=(Vi,Ei)G_i=(V_i,E_i) subsystem-i induced subgraph G[Vi]G[V_i] H⊆VH V handover station vertices A=⋃iAiA= _iA_i set of all agents (for all subsystems i) pa(t)p_a(t) vertex of agent a at timestep t τload,τunloadτ load,τ unload load/unload durations [timesteps] BhB_h buffer capacity of dock h∈Hh∈ H bh(t)b_h(t) buffer occupancy of dock h at t o=(s(o),g(o),r(o))o=(s(o),g(o),r(o)) task (source, destination, release time) c(o)c(o) completion time of task o I-A Environment and motion model As in the standard discrete MAPF/MAPD setting, the environment is an undirected graph G=(V,E)G=(V,E) typically induced by a 4-neighbor grid map: each free grid cell is a vertex and an edge connects horizontally/vertically adjacent free cells. Time is discrete, i.e., t∈ℤ≥0t _≥ 0. Each subsystem i∈1,2i∈\1,2\ operates within its own dedicated region defined by a vertex set Vi⊆V_i V, forming a vertex-induced subgraph Gi=G[Vi]=(Vi,Ei)G_i=G[V_i]=(V_i,E_i), with Ei=u,v∈E:u,v∈ViE_i= \\u,v\∈ E:u,v∈ V_i \. These subsystems are geographically disjoint except for a set of shared dock vertices, H=h1,…,h|H|H=\h_1,…,h_|H|\, which constitute their only overlap (V1∩V2=HV_1∩ V_2=H) and are otherwise disjoint ((V1∖H)∩(V2∖H)=∅(V_1 H)∩(V_2 H)= ). Crucially, there are no edges connecting non-dock regions directly across subsystems. This means payload transfers are exclusively conducted via dock vertices in H. Each dock vertex itself represents an isolated station, implying no direct edges exist between distinct dock vertices (h≠h′∈H⟹h,h′∉Eh≠ h ∈ H \h,h \∉ E). Each subsystem i has its own set of agents AiA_i. Let pa(t)p_a(t) denote the location (i.e., occupied vertex) of agent a at the timestep t. Agents are strictly confined to their respective GiG_i: for any a∈Aia∈ A_i, pa(t)∈Vi,∀tp_a(t)∈ V_i,\,∀ t, and all moves must be along edges in EiE_i. Also, at each t, an agent executes one action (either wait or move to an adjacent vertex in its subsystem graph), yielding the next position pa(t+1)∈pa(t)∪NGi(pa(t))p_a(t+1)∈\p_a(t)\∪ N_G_i(p_a(t)), where NGi(.)N_G_i(.) denotes neighbor set in GiG_i. All agents act simultaneously at each t. Let A=⋃iAiA= _iA_i. A vertex collision between agents a≠b∈Aa≠ b∈ A occurs at timestep t iff pa(t)=pb(t)p_a(t)=p_b(t). An edge collision (swap) occurs at timestep t iff pa(t)=pb(t+1)p_a(t)=p_b(t+1) and pa(t+1)=pb(t)p_a(t+1)=p_b(t). Agents must avoid collisions. We assume perfect execution. We define τload,τunload∈ℤ>0τ load,τ unload _>0 as the fixed durations for load/unload operations at task sources/destinations or dock vertices. Operations are non-preemptive and are modeled as consecutive waits at the operation vertex. If an agent arrives at time t0t_0 and waits for τ steps, it occupies that vertex at integer times t0,…,t0+τ\t_0,…,t_0+τ\ and may depart at t0+τ+1t_0+τ+1. An agent begins its assigned operation immediately upon arrival at the vertex if preconditions are met (see Section I-C). I-B Handover station interface model Subsystems exchange payloads only via handover stations. Each station is represented by a shared dock vertex h∈Hh∈ H together with a finite buffer of capacity Bh∈ℤ>0B_h _>0 (max number of storable payloads). At any timestep t, the dock vertex h may be occupied by at most one agent. I-C Tasks and buffer dynamics Tasks arrive online. Each task o is a triple (s(o),g(o),r(o))(s(o),g(o),r(o)) with source s(o)∈V1∖Hs(o)∈ V_1 H, destination g(o)∈V2∖Hg(o)∈ V_2 H, and release time r(o)∈ℤ≥0r(o) _≥ 0. Thus subsystem 1 is upstream and subsystem 2 is downstream. We consider only one-way inter-subsystem tasks from upstream to downstream; reverse and bidirectional flows are not modeled in this paper. At time r(o)r(o), a payload becomes available at s(o)s(o) and remains there until an upstream agent loads it. Payloads do not block agent paths. The buffer models storage capacity only, holding up to BhB_h payloads. By imposing no physical ordering (e.g., FIFO/LIFO), it abstracts a common staging area where any item can be accessed. Buffered payloads retain their task association o (including destination g(o)g(o)). A downstream agent loading at h may retrieve any available payload, providing maximum planning flexibility but complicating coordination. Each agent starts empty and carries at most one payload at a time. Let bh(t)∈ℤ≥0b_h(t) _≥ 0 denote the buffer occupancy at dock vertex h at timestep t. All buffers are initially empty (i.e., bh(0)=0,∀h∈Hb_h(0)=0,∀ h∈ H), and occupancy is always limited by the buffer capacity (i.e., 0≤bh(t)≤Bh0≤ b_h(t)≤ B_h for all t). An upstream agent performs the following sequence: loads a payload at s(o)s(o) (duration τloadτ load), travels to a chosen dock vertex h∈Hh∈ H, and unloads at h (duration τunloadτ unload). An upstream agent may enter h and start the unload operation at timestep t only if the buffer is not full (bh(t)<Bhb_h(t)<B_h). If the operation starts at t, the payload enters the buffer, and bhb_h increases by one, at timestep t+τunloadt+τ unload. A downstream agent performs the following sequence: loads a buffered payload at h (duration τloadτ load), travels to the corresponding g(o)g(o), and unloads it (duration τunloadτ unload). A downstream agent may enter h and start the load operation at timestep t only if the selected payload is present at h; in particular, bh(t)>0b_h(t)>0. If the operation starts at t, that payload is removed from the buffer, and bhb_h decreases by one at timestep t+τloadt+τ load. The entry guards for upstream and downstream operations apply only at the planned dock-entry time: an agent may wait elsewhere or replan until the operation becomes admissible. I-D Service time metric and optimization goal Let c(o)c(o) denote the completion time of task o, defined as the timestep at which the downstream agent finishes its unload operation at g(o)g(o). For a horizon T, let OT=o:c(o)≤TO_T=\o:c(o)≤ T\. When OT≠∅O_T≠ , service time [11] is the mean completion delay: ServiceTime(T)=1|OT|∑o∈OT(c(o)−r(o)),ServiceTime(T)= 1 |O_T | _o∈ O_T (c(o)-r(o) ), (1) Given (G,Ai,Bh,τload,τunload) (G, \A_i \, \B_h \,τ load,τ unload ) and an online task stream, a solution to MS-MAPD-BHS is an online policy that assigns tasks, selects handover stations, schedules station usage, and plans collision-free paths. The primary objective is low service time subject to motion and buffer safety; Sec. VI additionally reports throughput and backlog to diagnose overload. IV Handover-Aware Reservation and Routing (HARR) IV-A Overview and Token Passing Token Passing (TP) is an online MAPD scheme in which a token stores every local agent’s committed, time-indexed path and task assignment [20]. An agent requests the token when it reaches the end of its stored path. While holding the token, it selects an unassigned task, computes a space-time path that avoids the other paths stored in the token, writes its new path back, and releases the token. We call this stored sequence a token path; for agent a, it is πa=(πa(t),πa(t+1),…) _a=( _a(t), _a(t+1),…) with πa(t)=pa(t) _a(t)=p_a(t). HARR maintains one TP token per subsystem and a shared station manager that reserves dock occupancy and enforces buffer feasibility. Each inter-subsystem task is decomposed into two subtasks, called legs: an upstream push leg from s(o)s(o) to a selected dock h∈Hh∈ H, followed by a downstream pull leg from the same dock to g(o)g(o). HARR processes pulls before pushes at each timestep to favor buffer drainage. Alg. 1 details the HARR online control loop. Throughout this section, dGi(u,v)d_G_i(u,v) denotes the shortest-path distance between u,v∈Viu,v∈ V_i in GiG_i. Figure 2: HARR runs TP in each subsystem and couples the planners only through shared station state. RhR_h reserves exclusive dock occupancy, and QhQ_h is a deterministic projection obtained by applying the events of already committed buffer operations to the observed current occupancy. IV-B Shared station calendars At global time t, HARR maintains per-dock calendars over a rolling horizon Θ=[t,t+W]∩ℤ =[t,t+W] , where W∈ℤ>0W _>0 is the window size. Dock reservation calendar For each dock vertex h∈Hh∈ H, we define its dock reservation calendar as a time-indexed map Rh:ℤ≥0→A∪⊥R_h:Z_≥ 0→ A∪\ \. Rh(θ)∈AR_h(θ)∈ A indicates the unique agent reserved to occupy h at time θ, or Rh(θ)=⊥R_h(θ)= if h is unreserved. This calendar RhR_h is global; it is queried during planning and updated when a new token path is committed (Alg. 1, ReserveDocks). Committed buffer-event calendar and occupancy projection For each dock h, the event calendar Eh:ℤ≥0→ℤE_h:Z_≥ 0 stores occupancy changes caused by already committed operations. An upstream unload beginning at dock-entry time t0t_0 adds +1+1 to Eh(t0+τunload)E_h(t_0+τ unload), whereas a downstream load adds −1-1 to Eh(t0+τload)E_h(t_0+τ load). These events define the deterministic occupancy projection QhQ_h: Qh(t)=bh(t),Qh(θ)=Qh(θ−1)+Eh(θ)for θ>t.Q_h(t)=b_h(t),\,\,Q_h(θ)=Q_h(θ-1)+E_h(θ)\;\;for θ>t. (2) Thus, QhQ_h is the time-indexed buffer schedule implied by accepted operations. As the planning horizon advances, past events are discarded and Qh(t)Q_h(t) is re-anchored to the observed occupancy bh(t)b_h(t). Events are committed online via CommitDockAndBuffer (Alg. 1). Dock occupancy interval Under the operation model defined in Sec. I, an operation of duration τ that begins upon an agent entering h at time t0t_0 exclusively occupies the dock vertex at integer times Idock(t0,τ)=t0,t0+1,…,t0+τ.I dock(t_0,τ)=\t_0,t_0+1,…,t_0+τ\. Station-feasible insertion of a dock operation To insert an operation for agent a at dock h with dock-entry time t0t_0, duration τ, and event sign σ∈+1,−1σ∈\+1,-1\ (+1+1 for push/unload, −1-1 for pull/load), we define the event time θevt:=t0+τθ evt:=t_0+τ with θevt∈Θθ evt∈ . The insertion is station-feasible iff: ∀θ∈Idock(t0,τ):Rh(θ)=⊥, ∀θ∈ I dock(t_0,τ):\;\;R_h(θ)= , (3) start guard: Qh(t0)<Bhif σ=+1(push)Qh(t0)>0if σ=−1(pull) guard: \;\; casesQ_h(t_0)<B_h&if σ=+1\ (push)\\ Q_h(t_0)>0&if σ=-1\ (pull) cases (4) ∀θ∈[θevt,t+W]∩ℤ: 0≤Qh(θ)+σ≤Bh. ∀θ∈[θ evt,t+W] :\;\;0≤ Q_h(θ)+σ≤ B_h. (5) These conditions require: • Condition (3): The dock must be unreserved (Rh(θ)=⊥R_h(θ)= ) throughout the operation’s exclusive interval Idock(t0,τ)I dock(t_0,τ). • Condition (4): At t0t_0, the buffer must have space for a push (Qh(t0)<BhQ_h(t_0)<B_h) or contain the selected pull payload; the latter also implies Qh(t0)>0Q_h(t_0)>0. • Condition (5): After inserting the candidate event, the committed occupancy projection must remain within [0,Bh][0,B_h] through the end of the enforced horizon, so the insertion cannot invalidate an already accepted later operation. IV-C Station-aware Token Passing When an agent requests its subsystem token, PlanFirstFeasible runs space-time A* on GiG_i. The search avoids vertex and edge conflicts with the other token paths in that subsystem, and additionally respects the shared station calendar. Dock constraints During A* for agent a, a dock state (h,θ)(h,θ) is unavailable whenever Rh(θ)∉⊥,aR_h(θ)∉\ ,a\. After a path is accepted, ReserveDocks writes every dock occupancy on that path within the horizon to RhR_h, preventing cross-subsystem conflicts at shared dock vertices. Dock operations A dock operation beginning t0t_0 is admissible only if Eqs. (3)–(5) hold. If accepted, the corresponding event is posted to EhE_h and the occupancy projection QhQ_h is updated before the next request is considered. IV-D Leg paths and unassigned-leg sets Let ℰi⊆ViE_i V_i denote the endpoint set used by TP in subsystem i (task endpoints plus additional parking endpoints). Parking is restricted to ℰi∖HE_i H. HARR uses two sets to track work that is currently available for assignment. T↑(t)T (t) contains released tasks whose push leg is unassigned, and T↓(t)T (t) contains buffered tasks whose pull leg is unassigned. For each o∈T↓(t)o∈ T (t), the data structure also stores the dock h(o)h(o) where the payload is present. A task leaves T↑T when its push path is committed, enters T↓T only after the upstream unload completes, leaves T↓T when its pull path is committed, and exits the system after the downstream unload at g(o)g(o). While a leg is in progress, its state is represented by the responsible agent’s token path rather than duplicated in either set. Push template (subsystem 1) A push for task o to dock h plans through s(o)s(o) (wait τloadτ load), then h (wait τunloadτ unload), and finally a parking endpoint e∈ℰ1∖He _1 H. The dock operation uses (σ,τ)=(+1,τunload)(σ,τ)=(+1,τ unload). Pull template (subsystem 2) A pull for buffered task o at dock h(o)h(o) plans through h(o)h(o) (wait τloadτ load), then g(o)g(o) (wait τunloadτ unload), and finally a parking endpoint e∈ℰ2∖He _2 H. The dock operation uses (σ,τ)=(−1,τload)(σ,τ)=(-1,τ load). Algorithm 1 HARR: station- and buffer-aware decoupled Token Passing. 1:Subsystem graphs GiG_i, agents AiA_i, docks H, capacities BhB_h, endpoints ℰiE_i 2:Operation times τload,τunloadτ load,τ unload, parameters W, kmaxk_ , MmaxM_ 3:Initialize TP tokens: πa←[pa(0)] _a←[p_a(0)] for all a∈Aa∈ A 4:Initialize station calendars Rh(θ)←⊥R_h(θ)← , Eh(θ)←0E_h(θ)← 0 for all h∈Hh∈ H, θ∈[0,W]θ∈[0,W] 5:Initialize unassigned-leg sets T↑←∅T ← , T↓←∅T ← 6:for t=0,1,2,…t=0,1,2,… do 7: Observe bh(t)b_h(t) for all h∈Hh∈ H 8: Shift horizon Θ=[t,t+W]∩ℤ =[t,t+W] ; discard Rh(θ),Eh(θ)R_h(θ),E_h(θ) for θ<tθ<t 9: Anchor Qh(t)=bh(t)Q_h(t)=b_h(t) and recompute QhQ_h from EhE_h on Θ 10: Insert newly released tasks into T↑T 11: Update the sets from executed operations (completed push →T↓→ T with h(o)h(o); completed pull → remove from system) 12: ProcessRequests(2,Pull)(2, Pull) ⊳ downstream first 13: ProcessRequests(1,Push)(1, Push) 14: Execute one timestep: all agents follow their token paths; advance to t+1t+1 15:end for 16:function ProcessRequests(i,Modei, Mode) 17: (T⋆,σ,τ)←ModeParams(Mode)(T ,σ,τ)← ModeParams( Mode) ⊳ T⋆T : unassigned legs for this mode 18: for each agent a∈Aia∈ A_i requesting the token do 19: ←Candidates(a,Mode,T⋆)C← Candidates(a, Mode,T ) 20: (π,o,h,t0)←PlanFirstFeasible(a,,Mode,R,Q)(π,o,h,t_0)← PlanFirstFeasible(a,C, Mode,R,Q) 21: if π≠⊥π≠ then 22: πa←π _a←π; ReserveDocks(a,π,R)(a,π,R) 23: CommitDockAndBuffer(h,t0,σ,τ,E,Q)(h,t_0,σ,τ,E,Q); remove o from T⋆T ⊳ the leg is now in progress 24: else 25: πa←Park(a,ℰi∖H) _a← Park(a,E_i H) 26: end if 27: end for 28:end function Algorithm helpers ModeParams selects (T↑,+1,τunload)(T ,+1,τ unload) for pushes and (T↓,−1,τload)(T ,-1,τ load) for pulls; Candidates applies the ordering below. PlanFirstFeasible runs space-time A* for each pair and enforces R and Eqs. (3)–(5). ReserveDocks writes accepted dock-time states to R, and CommitDockAndBuffer posts the event to E and updates Q. Park uses the same path constraints to reach a non-dock endpoint. IV-E Task and dock selection When a downstream agent a∈A2a∈ A_2 requests the token, it considers up to MmaxM_ candidates o∈T↓o∈ T in increasing order of J↓(a,o)=dG2(pa(t),h(o))+dG2(h(o),g(o)).J_ (a,o)=d_G_2 (p_a(t),h(o) )+d_G_2 (h(o),g(o) ). When an upstream agent a∈A1a∈ A_1 requests the token, it considers up to MmaxM_ tasks o∈T↑o∈ T (oldest first). For each task, it considers up to kmaxk_ docks h∈Hh∈ H in increasing order of J↑(a,o,h)=dG1(pa(t),s(o))+dG1(s(o),h)+dG2(h,g(o)).J_ (a,o,h)=d_G_1 (p_a(t),s(o) )+d_G_1 (s(o),h )+d_G_2 (h,g(o) ). Candidates are attempted in the above order; the first candidate for which station-aware A* finds a feasible plan is accepted. IV-F Computational cost, guarantees, and feasibility Computational cost For one token request, a pull attempts at most MmaxM_ task–dock pairs, whereas a push attempts at most Mmaxminkmax,|H|M_ \k_ ,|H|\ pairs. Each pair invokes one space-time A* search. In addition to TP’s collision checks, HARR examines the τ+1τ+1 dock slots in Eq. (3) and at most W+1W+1 occupancy entries in Eq. (5). The rolling-horizon arrays R, E, and Q each store |H|(W+1)|H|(W+1) entries. Enumeration stops at the first feasible pair. Collision safety Within each subsystem, standard TP checks preserve vertex- and edge- collision freedom among committed local paths. Across subsystems, the only shared vertices are docks, and Rh(θ)R_h(θ) permits at most one agent to occupy a dock at a time. Therefore, under perfect execution, committed dock use is collision-free over the enforced reservation horizon. It does not claim completeness or collision safety beyond t+Wt+W, where future paths have not yet been committed. Sequential insertion semantics Requests are processed sequentially as in Alg. 1. After each accepted plan, CommitDockAndBuffer immediately updates (Eh,Qh)(E_h,Q_h) before the next candidate is checked. The guarantee below therefore assumes this insertion order and perfect execution. Buffer safety At time t, each occupancy projection is anchored at Qh(t)=bh(t)∈[0,Bh]Q_h(t)=b_h(t)∈[0,B_h]. Committing an operation leaves QhQ_h unchanged before its event and shifts it by σ from the event time onward. Condition (5) is exactly the requirement that the updated projection remain in [0,Bh][0,B_h]. By induction over sequentially accepted insertions, every committed event calendar is occupancy-consistent over [t,t+W][t,t+W]. The guarantee is horizon-local. HARR makes no claim beyond t+Wt+W until the horizon advances and the projection is re-anchored. Feasibility and completeness MS-MAPD-BHS is not universally solvable. Feasibility depends on subsystem geometry, endpoint availability, reachability between task vertices and admissible docks, staffing balance, and interface load. HARR is not complete: it uses a finite horizon, caps task candidates at MmaxM_ , and inherits the limitations of prioritized TP planning. Our domains avoid trivial endpoint deadlocks—agents can park outside H, and the relevant task and dock vertices are reachable—but a full completeness and stability characterization is left to future work. V Comparators and Ablations We compare HARR with one coupled reference method and two mechanism ablations. The reference evaluates the computational effect of subsystem-local rather than global Token Passing, whereas the ablations isolate online dock selection and forward buffer projection. MonoSBTP (coupled station- and buffer-aware TP) We run TP with a single global token over all agents A, while restricting each agent’s search space to its subsystem vertices ViV_i. Dock exclusivity is enforced implicitly by global collision avoidance at shared dock vertices, and buffer feasibility uses the same committed occupancy projection (Eh,Qh)(E_h,Q_h) and capacity guard (Eq. (5)) as HARR. FixedDock (no online dock selection) This method is identical to HARR, except that each task is assigned at release to the dock minimizing dG1(s(o),h)+dG2(h,g(o))d_G_1(s(o),h)+d_G_2(h,g(o)) and cannot change docks online. It is an ablation of adaptive dock selection. StartResBuf negative control (local start-time admission only) This ablation omits the rolling-horizon occupancy projection: a newly inserted dock operation is checked only against dock availability and its local start guard, without (Eh,Qh)(E_h,Q_h) and Eq. (5). Because online insertions can occur out of chronological order, a newly accepted earlier event can invalidate an already committed later operation. In our simulator, StartResBuf yielded no valid run in the tested settings, so it is retained as a negative control and excluded from quantitative plots. TABLE I: Comparators and ablations. Method G-TP R Projection DynDock MonoSBTP ✓ ✗ ✓ ✓ FixedDock ✗ ✓ ✓ ✗ StartResBuf ✗ ✓ ✗ ✓ HARR (ours) ✗ ✓ ✓ ✓ G-TP: token scope in ProcessRequests. R: written by ReserveDocks. Projection: updated by CommitDockAndBuffer. DynDock: dock enumeration in Candidates. VI Experiments We evaluate HARR in a C++ simulator implementing the two-subsystem MS-MAPD-BHS model from Sec. I. Unless stated otherwise, all methods use the same motion model, task process, and endpoint sets ℰiE_i (with parking restricted to ℰi∖HE_i H), as well as uniform station parameters τload=τunload=2τ load=τ unload=2 and Bh=B_h=B. For HARR, we set W=60W=60, Mmax=20M_ =20, and kmax=8k_ =8. Because the largest tested configuration has |H|=8|H|=8, the dock-candidate cap never binds in the reported experiments. Default provisioning is |H|=4|H|=4, B=1B=1, with n1=n2=12n_1=n_2=12 agents. VI-A Domains and station layouts We use two representative grid domains: Empty, an open map (40×2040× 20) that isolates interface-induced effects (dock contention, blocking, and starvation); and Warehouse, a shelf-like layout (34×2634× 26) that induces within-subsystem congestion and longer detours. At each timestep t, the number of new inter-subsystem tasks is Nt∼Poisson(ρ)N_t (ρ). Each task o=(s(o),g(o),r(o))o=(s(o),g(o),r(o)) samples s(o)s(o) uniformly from a fixed upstream source set ⊂V1∖HS⊂ V_1 H and g(o)g(o) uniformly from a fixed downstream destination set ⊂V2∖HG⊂ V_2 H. We choose 4 sources and 4 destinations, whose locations are initialized by random seeds. Handover stations are distributed approximately uniformly along the interface; the released configurations specify their exact coordinates for every tested |H||H|. To compare runs across different numbers of docks |H||H| and operation times, we define the normalized offered dock load ϱ=ρ⋅(τunload+1)+(τload+1)|H|, \;=\;ρ· (τ unload+1)+(τ load+1)|H|, where τ+1τ+1 matches the dock-occupancy interval length |Idock(⋅,τ)||I dock(·,τ)| used by HARR (Sec. IV). Thus, ϱ compares requested dock time with nominal aggregate dock capacity. It is an offered-load indicator, not a sufficient stability condition, because path congestion, staffing imbalance, and heterogeneous dock accessibility also affect throughput. VI-B Protocol and metrics Each configuration runs for Ttot=4000T_ tot=4000 timesteps. We discard the first Twarm=1000T_ warm=1000 timesteps (25% of the run) to reduce the common initialization transient caused by initially empty buffers and seeded initial agent positions; the same warm-up is used for every method and configuration. Results are averaged over Nseed=10N_ seed=10 independent random seeds and reported with 95% confidence intervals. Performance metrics We report three complementary metrics: 1. Service time [timesteps]. ServiceTime(Ttot)ServiceTime(T_ tot) from Eq. (1), computed over tasks released after warm-up and completed by TtotT_ tot. 2. Throughput [tasks/timestep] (stability). Throughput=|o:c(o)∈(Twarm,Ttot]|Ttot−Twarm,Throughput\;=\; | \o:\;c(o)∈(T_ warm,T_ tot] \ |T_ tot-T_ warm, i.e., completed tasks per timestep during the measurement window. 3. Backlog [tasks] (unserved demand). Backlog=|o:Twarm<r(o)≤Ttot,c(o)>Ttot|.Backlog= | \o:\;T_ warm<r(o)≤ T_ tot,\;c(o)>T_ tot \ |. Throughput and backlog remain informative in overload regimes and prevent survivorship bias. VI-C Results The two comparison studies target different mechanisms. The load and provisioning sweeps compare HARR with the FixedDock ablation to isolate adaptive dock selection, whereas the fleet-size sweep compares HARR with the coupled MonoSBTP reference to isolate global-token coupling. They should therefore be read as two controlled comparisons, not as a single three-way ranking. VI-C1 Adaptive dock selection: HARR vs. FixedDock We first study whether online dock selection improves both service time and stability as the interface approaches saturation. We sweep the offered dock load ϱ on both maps under default provisioning and balanced staffing. For each configuration, we report service time, throughput, and backlog. Figure 3: Load sweep under default provisioning (|H|=4|H|=4, B=1B=1). Rows are Empty and Warehouse; columns show service time [timesteps] (lower is better), throughput [tasks/timestep] (higher is better), and backlog [tasks] (lower is better, log scale). Figure 3 shows that HARR outperforms FixedDock across the tested load range. At moderate load, it achieves higher throughput and substantially lower backlog on both maps (Table IV). Near saturation, throughput and backlog reveal overload more reliably than service time; the largest gains occur on Warehouse, where congestion makes static dock assignments less effective. TABLE IV: Moderate-load results (ϱ=0.15 =0.15; default provisioning). Throughput is measured in tasks/timestep and backlog in tasks. Throughput ↑ Backlog ↓ Map FixedDock HARR Gain FixedDock HARR Reduction Empty 0.071± 0.005 0.099±0.0070.099± 0.007 +39% 110± 34 9.2±3.69.2± 3.6 92% Warehouse 0.053± 0.006 0.093±0.0050.093± 0.005 +77% 181± 33 ±31± 18 83% We next vary the number of docks |H||H| and buffer capacity B separately at an arrival rate near saturation. Figure 4 shows that HARR benefits more from additional docks because it can exploit the currently reachable, buffer-feasible interface. At |H|=8|H|=8, its throughput is 202% higher on Empty and 245% higher on Warehouse. Figure 4: Interface provisioning sweeps (throughput). Columns sweep the number of docks |H||H| and the buffer capacity B. VI-C2 Fleet-size planning cost: HARR vs. MonoSBTP We compare the computational cost of decoupled planning in HARR with the coupled MonoSBTP reference while checking service time. We sweep the total number of agents N∈5,10,15,20,25,30,35,40,45N∈\5,10,15,20,25,30,35,40,45\ with a balanced split (n1,n2)=(⌊N/2⌋,⌈N/2⌉)(n_1,n_2)=( N/2 , N/2 ). Workload, workspace, and interface provisioning remain fixed, so this is a fleet-size study rather than a workspace-size scaling study. Figure 5 shows that HARR has lower or comparable mean planning time across the tested fleet sizes, with the clearest advantage on the structured Warehouse map. Service time is non-monotonic: adding agents initially reduces delay, but larger fleets eventually create more path interference and coordination work. On Warehouse, service time rises again beyond the best-performing fleet-size range. Thus, over-provisioning agents can be counterproductive even though demand and workspace are fixed. The comparison supports a narrower conclusion: subsystem-local tokens reduce planning cost relative to a global token over the tested fleet sizes while retaining comparable service quality. Figure 5: Fleet-size sweep on two fixed workspaces. Mean planning time per step [s] and service time [timesteps] are both lower when better; curves summarize ten seeds. VI-D Scope and limitations The evaluation covers two fixed workspaces and does not establish workspace-size or asymptotic scalability. The A* expansion term SiS_i in Sec. IV can grow substantially with map size, congestion, and reservation horizon. Sensitivity to W, MmaxM_ , and kmaxk_ is not swept; all are held constant to isolate the interface mechanisms. Since kmax=8k_ =8 and every tested configuration has |H|≤8|H|≤ 8, the cap never binds, so the experiments do not measure the effect of dock-candidate truncation in larger interfaces. The two comparator studies use different independent variables because they isolate different mechanisms, and no unified three-way ranking is claimed. Longer or hierarchical subsystem networks, reverse or bidirectional flow, deadlines and priorities, execution uncertainty, broader parameter sweeps, and spatial scaling remain future work. VII Conclusion We introduce MS-MAPD-BHS, a lifelong pickup-and-delivery problem in which region-confined fleets exchange payloads through buffer-limited handover stations. HARR coordinates subsystem-local Token Passing planners through shared dock reservations and a deterministic rolling-horizon projection of committed buffer events. Under perfect execution, accepted dock operations are collision-free and buffer-safe within the enforced horizon, although the method is explicitly incomplete. In simulation, HARR achieves up to 77% higher throughput and 92% lower backlog than FixedDock at moderate load and reduces planning time relative to MonoSBTP at comparable service time. Future work includes implementing and evaluating longer and hierarchical subsystem chains, incorporating deadlines and priority-aware assignment, handling execution uncertainty and bidirectional transfers, and studying workspace-size, parameter-sensitivity, and stability scaling. References [1] B. Arbanas, A. Ivanovic, M. Car, M. Orsag, T. Petrovic, and S. Bogdan (2018) Decentralized planning and control for UAV–UGV cooperative teams. Autonomous Robots 42 (8), p. 1601–1618. External Links: Document Cited by: §I, §I. [2] L. Bonalumi, B. Flammini, D. Azzalini, and F. Amigoni (2025) Multi-agent pickup and delivery with external agents. Robotics and Autonomous Systems 191, p. 105000. External Links: Link, Document Cited by: TABLE I, §I. [3] A. Bonetti, S. Proia, S. Guidetti, and L. Sabattini (2024) AGV traffic management in automated industrial plants: an enhanced lifelong multi-agent path finding approach. In International Conference on Automation Science and Engineering (CASE), p. 626–632. External Links: Link, Document Cited by: §I. [4] X. Chen, S. He, Y. Zhang, L. C. Tong, P. Shang, and X. Zhou (2020) Yard crane and AGV scheduling in automated container terminal: a multi-robot task allocation framework. Transportation Research Part C: Emerging Technologies 114, p. 241–271. Cited by: §I. [5] Z. Chen, J. Alonso-Mora, X. Bai, D. D. Harabor, and P. J. Stuckey (2021) Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters (RA-L) 6 (3), p. 5816–5823. External Links: Link, Document Cited by: §I. [6] C. H. Chung and Y. J. Jang (2024) Deadlock prevention and multi agent path finding algorithm considering physical constraint for a massive fleet AGV system. Applied Soft Computing 161, p. 111725. External Links: Link, Document Cited by: §I. [7] U. Clausen, D. Diekmann, M. Pöting, and C. Schumacher (2017) Operating parcel transshipment terminals: a combined simulation and optimization approach. Journal of Simulation 11 (1), p. 2–10. External Links: Document Cited by: §I. [8] B. Coltin and M. M. Veloso (2014) Online pickup and delivery planning with transfers for mobile robots. In International Conference on Robotics and Automation (ICRA), p. 5786–5791. External Links: Link, Document Cited by: TABLE I. [9] H. Fan, B. Ouyang, Q. Xie, Y. Wang, Z. Yan, J. He, and Q. Tan (2025) Joint optimization of multi-agent task allocation and path planning for continuous pickup and delivery tasks. In International Conference on Intelligent Robots and Systems (IROS), p. 20014–20019. External Links: Link, Document Cited by: §I. [10] B. Flammini, F. Amigoni, and B. Lacerda (2026) Multi-agent pickup and delivery with heterogeneous agents. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 2356–2364. External Links: Link, Document Cited by: TABLE I, §I. [11] B. Flammini, N. Hawes, and B. Lacerda (2025) Multi-agent pickup and delivery with mobile pickups. In International Conference on Intelligent Robots and Systems (IROS), p. 10525–10531. External Links: Link, Document Cited by: TABLE I, §I, §I-D. [12] G. Fragapane, R. de Koster, F. Sgarbossa, and J. O. Strandhagen (2021) Planning and control of autonomous mobile robots for intralogistics: literature review and research agenda. European Journal of Operational Research (EJOR) 294 (2), p. 405–426. External Links: Link, Document Cited by: §I. [13] J. Gao, Y. Li, X. Li, K. Yan, K. Lin, and X. Wu (2024) A review of graph-based multi-agent pathfinding solvers: from classical to beyond classical. Knowledge-based Systems 283, p. 111121. External Links: Link, Document Cited by: §I. [14] H. He, X. Wu, S. Zhao, and Z. Ren (2026) Conflict-based search for multi-agent path finding with elevators. CoRR abs/2602.20512. External Links: Link, Document, 2602.20512 Cited by: TABLE I, §I, §I. [15] J. He, Y. Zhang, R. Veerapaneni, and J. Li (2024) Scaling lifelong multi-agent path finding to more realistic settings: research challenges and opportunities. In International Symposium on Combinatorial Search (SOCS), p. 234–242. External Links: Link, Document Cited by: §I. [16] W. Hönig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian (2018) Conflict-based search with optimal task assignment. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 757–765. External Links: Link Cited by: §I. [17] H. Huang, Q. Zhang, B. Deng, X. Zhu, W. Mei, and H. Zhu (2026) Distributed and transferable task assignment for dynamic pickup-and-delivery with time windows. IEEE Robotics and Automation Letters (RA-L) 11 (2), p. 1442–1449. External Links: Link, Document Cited by: TABLE I, §I. [18] J. Li, Z. Chen, Y. Zheng, S. Chan, D. Harabor, P. J. Stuckey, H. Ma, and S. Koenig (2021) Scalable rail planning and replanning: winning the 2020 flatland challenge. In International Conference on Automated Planning and Scheduling (ICAPS), p. 477–485. External Links: Link Cited by: §I. [19] H. Ma, W. Hönig, T. K. S. Kumar, N. Ayanian, and S. Koenig (2019) Lifelong path planning with kinematic constraints for multi-agent pickup and delivery. In AAAI Conference on Artificial Intelligence (AAAI), p. 7651–7658. External Links: Link, Document Cited by: §I. [20] H. Ma, J. Li, T. K. S. Kumar, and S. Koenig (2017) Lifelong multi-agent path finding for online pickup and delivery tasks. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 837–845. External Links: Link Cited by: 2nd item, §I, TABLE I, §I, §IV-A. [21] H. Ma, C. A. Tovey, G. Sharon, T. K. S. Kumar, and S. Koenig (2016) Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In AAAI Conference on Artificial Intelligence (AAAI), p. 3166–3173. External Links: Link, Document Cited by: TABLE I, §I. [22] H. Makino and S. Ito (2024) Online multi-agent pickup and delivery with task deadlines. In International Conference on Intelligent Robots and Systems (IROS), p. 8428–8434. External Links: Link, Document Cited by: TABLE I, §I. [23] D. McWilliams (2014) Performance modelling and analysis of transshipment terminals in the parcel delivery industry. International Journal of Industrial and Systems Engineering (IJISE) 16 (4), p. 493–522. External Links: Document Cited by: §I. [24] F. Menebröker, J. Stadtler, A. Böckenkamp, D. Lünsch, and S. Franke (2025) Mobile robot collaboration in industrial applications: a structured survey. In International Conference on Automation Science and Engineering (CASE), p. 2428–2435. External Links: Link, Document Cited by: §I. [25] R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Barták, and E. Boyarski (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In International Symposium on Combinatorial Search (SOCS), p. 151–158. External Links: Link, Document Cited by: §I.