Source-linked AI summary
Fixed-Haven Reservation for Online Multi-Agent Pickup and Delivery in Dense Warehouses
Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda
TL;DR
Dense warehouse layouts challenge MAPD guarantees that depend on avoidable waiting endpoints or biconnected topology. The paper introduces fixed-Haven reservation and implements it in SHARP, which maintains validated routes ending at owner-only Havens. SHARP achieves 100% success across tested layouts, while fixed-home return recovers tree robustness and suffix overwrite improves efficiency under tested high load.
Problem
Dense warehouses have narrow aisles, dead ends, and tree-like guidepaths where waiting agents can block traffic and existing structural assumptions may fail.
Method
The paper assigns each agent an exclusive fixed Haven, blocks foreign Havens, and uses SHARP to validate reservations through task waypoints and back to each Haven.
Results
SHARP is the only representative main-sweep method with 100% success across all tested tree-map loads and agent counts; fixed-home return also recovers 100% success in tested tree conditions.
Takeaways & Limitations
Fixed return is a central robustness mechanism in the tested tree conditions, while mid-retreat suffix overwrite is associated with efficiency gains.
Takeaways & Limitations
The guarantee assumes centralized reservation and synchronized execution, fixed exclusive Havens, zero dwell duration, finite releases, and the stated fixed-Haven commitment model.
Abstract
from arXiv · showhide
Dense warehouses often contain single-lane aisles, dead ends, and tree-like guidepaths that leave little room for idle agents to wait without blocking others. Existing Multi-Agent Pickup and Delivery (MAPD) guarantees for completing all finitely released tasks typically rely on extra waiting endpoints that planned paths can avoid, or on biconnected topology; these assumptions may fail in such layouts. We study fixed-Haven reservation for online MAPD, where pickup-delivery tasks are released over time. Each agent owns a fixed Safe Haven (Haven for short), usually its start cell, that only the owner may occupy and that other agents treat as blocked. For finite task releases, we prove that this fixed-Haven contract completes all released tasks under Haven-Reachability and explicit planning/progress assumptions. We implement the contract in SHARP, a Safe-Haven Retreat Planner that keeps every busy or retreating agent on a collision-free reserved route ending at its Haven. We compare SHARP with representative TP and PIBT-family MAPD baselines: Token Passing (TP), Priority Inheritance with Backtracking (PIBT), and PIBT with Temporary Priority and Temporary Avoidance (PIBTTP-TA) for biconnected main areas with attached trees. In the robustness sweep, SHARP is the only method with 100% success on all tested configurations, at substantially higher centralized planning cost on tree-like layouts. A TP-style fixed-home-return counterfactual with full-route validation also recovers robustness on tested tree-like layouts, suggesting that fixed return is a central robustness mechanism there. A no-overwrite variant shows that disabling mid-retreat reassignment worsens service time (release-to-delivery latency) by 1.89 times and makespan by 1.53 times in the tested high-load tree condition.
1 Introduction
The paper addresses online MAPD in dense, restrictive warehouse layouts by introducing fixed owner-only Havens and a reservation contract that supports finite-release completion. SHARP implements this contract by maintaining validated collision-free routes through task waypoints and back to each agent’s Haven.
- Motivation: Dense warehouse layouts make waiting, returning, and newly assigned agents potential blockers in narrow passages and tree-like guidepaths.The challenge is especially acute in single-lane aisles, dead ends, and layouts lacking wide detours.
- Motivation: Existing MAPD guarantees rely on well-formed endpoint assumptions or biconnected topology that may not hold in these layouts.TP assumes separate waiting endpoints, while PIBT-family guarantees use biconnected graph structures and additional restrictions.
- Approach: Each agent receives a fixed Safe Haven that only its owner may occupy, while SHARP reserves a collision-free route through unfinished task waypoints and back to that Haven.A retreating agent may accept a new task only after the remaining retreat suffix is replaced by a newly validated pickup-delivery-Haven route.
- Contribution: The paper contributes a fixed-Haven contract and a finite-release completion guarantee under Haven-Reachability and explicit planning/progress assumptions.SHARP is the centralized graph-level implementation used to study layout coverage, fixed-home-return robustness, and suffix-overwrite efficiency.
2 Related Work and Positioning
The paper positions SHARP among fallback-location and structural-completeness approaches for MAPD. Its distinctive contract fixes owner-only Havens at agent starts, preserves executable retreat routes, and argues completion through quiescent states.
- MAPD scope: Online MAPD releases pickup-delivery tasks over time, whereas offline MAPD assumes the full task set is known in advance.This paper studies standard online MAPD with finite task releases.
- Structural guarantees: TP is complete on well-formed instances requiring enough separate waiting endpoints and endpoint-avoiding paths.This infrastructure assumption can be restrictive when pickup and delivery locations lie on narrow corridors.
- Structural guarantees: PIBT guarantees reachability mainly on biconnected graphs, while PIBTTP-TA extends the setting to biconnected main areas with attached trees under additional restrictions.The tree extension includes task-placement and motion restrictions inside trees.
- Fallback positioning: Prior fallback approaches use parking locations, dummy endpoints, dynamic standby nodes, or home-location variants, whereas SHARP fixes owner-only Havens at agent starts.SHARP also maintains an executable return suffix and proves completion through quiescent states in which the task area clears.
- Fallback positioning: The fixed-Haven framework protects only per-agent Havens rather than all endpoints and requires no separate shared fallback pool.Busy agents retain retreat reservations to their own Havens throughout execution.
- Terminology and baselines: SHARP and the broader fixed-Haven framework are distinct: SHARP denotes the centralized policy, while the framework denotes the wider guarantee framework.The paper separately compares TP-family reference points and diagnostic fixed-home-return counterfactuals.
3 SHARP Coordination Framework
SHARP coordinates online MAPD by assigning owner-only fixed Havens and reserving collision-free routes through each task and back to the agent’s Haven. Its validation and reassignment rules preserve these reservations, while Haven-Reachability broadens the supported layouts beyond well-formedness assumptions.
- Fixed-Haven coordination: Each agent has an exclusive fixed Haven, and all other agents treat that Haven as blocked.
- Reservation invariant: Busy agents reserve routes through unfinished pickup and delivery waypoints to their Havens, while retreating agents reserve suffixes back to their Havens.
- Haven-Reachability: Haven-Reachability requires a connected task-support region, access from every support vertex to every Haven, and unique Haven ownership.
- Layout scope: Haven-Reachability does not imply well-formedness, allowing task endpoints on narrow corridors without a separate fallback pool.
- Planning and validation: SHARP validates current-to-pickup-to-delivery-to-Haven routes with SIPP while preserving collision freedom and foreign-Haven blocking.
- Task assignment and validation: Nearest-pickup proposals are ranked by static distance, but only SIPP validation determines feasibility; failed candidates can be rejected outside quiescence.
4 Completeness Under Fixed Havens
The fixed-Haven framework proves finite-release completeness by combining route invariants, progress after quiescence, and Haven-Reachability. SHARP inherits the guarantee when its planning horizon and SIPP completeness assumptions hold.
- Guarantee: Finite-release completeness means every released task is delivered in finite time when only finitely many tasks are released.
- Quiescent feasibility: In quiescence, Haven-Reachability makes every pending task feasible for every agent because the support region is clear and connected.
- Assignment progress: SHARP’s nearest-pickup rule satisfies Assignment-Progress under Haven-Reachability, Tmax ≥ diam(G[W]) + 1, and bounded complete SIPP calls.
- Execution progress: If no further tasks are assigned, SHARP reaches quiescence in finite time because reserved suffixes are executed without later overwriting.
- Framework theorem: The fixed-Haven framework is finite-release complete when it maintains the reservation invariant and satisfies assignment and route-execution progress conditions.
- SHARP corollary: SHARP completes every finitely released task under Haven-Reachability, no-transfer commitments, the stated horizon bound, and SIPP completeness up to that horizon.
5 Warehouse-Inspired Experiments
The experiments stress-test SHARP and representative MAPD baselines across increasingly restrictive warehouse-inspired layouts, then isolate fixed-return and retreat-overwrite effects. SHARP provides the strongest robustness on difficult layouts, while fixed-return validation recovers tree-layout robustness and overwrite improves efficiency.
- Experimental setup: The evaluation covers well-formed, narrow-biconnected, narrow-biconnected-with-dead-ends, and tree-like maps using identical seeded task instances across methods.Starts and Havens are sampled from orange cells; tasks use gray endpoint candidates, with Haven-Reachability conditions verified for each sampled Haven set.
- Experimental setup: The main sweep varies agent counts from 5 to 30 and task-generation rates λ from 0.5 to 3.0 across 100 runs per configuration.It compares TP, PIBT, PIBTTP-TA, and SHARP, with success requiring delivery of all released tasks before a stop condition.
- Main sweep: SHARP is the only representative main-sweep baseline with 100% success across all tested loads and agent counts on the tree map.TP degrades on narrow-bi maps, while PIBT loses robustness on narrow-bi-dead maps; the well-formed map remains at 100% success for all four methods.
- Main sweep: On tree layouts, task-performance ratios are secondary because they condition on successful runs; the main result is structural robustness at much higher centralized planning cost.SHARP remains competitive with the strongest successful baseline on well-formed and narrow-bi-dead layouts.
- Fixed-home-return counterfactual: Both TP-style fixed-home-return variants recover 100% tree-layout success under full-route validation, while SHARP further improves normalized makespan and service time at substantially higher runtime.On well-formed conditions, naive fixed-home return more than doubles makespan and more than triples service time relative to TP at λ = 3.0.
- No-overwrite diagnostic: Disabling SHARP’s mid-retreat reassignment preserves 100% success but worsens all reported task-efficiency and planning-effort ratios.The ablation retains fleet-wide candidate scanning, isolating the penalty of disabling retreat-suffix overwrite; all 30 paired seeds worsen for makespan and service time.
6 Deployment Assumptions and Limitations
SHARP’s formal guarantee and deployment scope depend on centralized fixed-Haven coordination under explicit assumptions. Several richer task, timing, Haven, and guidepath settings remain outside the stated framework.
- SHARP assumes a centralized fleet manager, global reservation table, and synchronized route execution.
- The formal guarantee covers fixed exclusive Havens, zero pickup/delivery dwell duration, and finitely many task releases.
- Task swaps, deterministic nonzero dwell times, stochastic delays, and dynamic Haven reassignment are outside the stated scope.
7 Conclusion
The paper presents fixed-Haven reservation as a finite-release-complete coordination framework and realizes it in SHARP. Experiments indicate fixed return supports robustness on tested tree cases, while SHARP improves efficiency at substantial centralized planning cost.
- Fixed-Haven reservation provides finite-release completion under Haven-Reachability and explicit planning and progress assumptions.
- SHARP maintains retreat reservations to fixed Havens, implementing the fixed-return contract at the algorithm level.
- A TP-style fixed-home-return counterfactual with full-route validation recovers robustness on the representative tree cases tested.
- Fixed return is suggested as a central robustness mechanism in those tested conditions.
- Mid-retreat suffix overwrite is unnecessary for robustness in the tested high-load tree condition but is associated with 1.89 times service-time and 1.53 times makespan gains when fleet-wide scanning is retained.
- SHARP exploits fixed return more efficiently while exposing substantial centralized planning cost.