Fixed-Haven Reservation for Online Multi-Agent Pickup and Delivery in Dense Warehouses

Taisei Hirayama; Kohei Yoshida; Hiroki Sakaji; Itsuki Noda

cs.MAAug 27, 2026

Fixed-Haven Reservation for Online Multi-Agent Pickup and Delivery in Dense Warehouses

Authors: Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda

Organizations: Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan

Abstract

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.

Figures & tables

Method	Setting	Fallback target	Completeness assumption	Fallback cell source	Dense endpoints in guarantee	Comment
TP ( Ma et al. 2017 )	onl.	endpoint holding	well-formed MAPD	non-task endpoints	no	Complete online MAPD with endpoint-avoidance
Liu et al. (2019)	offl.	designated parking endpoint + dummy path	well-formed / parking-avoidance variant	designated parking endpoints	parking-limited	Offline dummy-path feasibility; no online suffix overwrite
Xu et al. (2022)	MG	dummy endpoint from shared endpoint pool	well-formed MG-MAPD	shared endpoint pool	no	Goal-sequence paths with dynamic dummy reassignment
SHARP	onl.	exclusive Haven (fixed start cell)	Haven-Reachable + finite releases + progress conditions	fixed per-agent starts	yes	Every busy agent keeps a Haven retreat reservation

Table 1: Positioning relative to fallback-based MAPD mechanisms. “Dense endpoints” means pickup/delivery locations may lie on narrow passageways; “parking-limited” means the guarantee can relax endpoint avoidance only through designated parking/dummy endpoints. Abbreviations: onl.=online, offl.=offline, MG=multi-goal MAPD.

Panel of Figure 1 — Figure 1: Map classes. Narrow-bi abbreviates narrow-biconnected, and narrow-bi-dead abbreviates narrow-biconnected with dead ends. Orange cells denote start/Haven candidate locations; in a given run only the sampled start cells belong to $H$ . The same sampled start cells are fixed homes for TP-home-return variants. Gray cells are task endpoints, white cells are traversable non-task cells, and black cells are obstacles.

Figure 2: Success-rate heatmap for the main sweep. Axes are agent count (x) and task-generation rate $\lambda$ (y). The map panels move from the common well-formed regime to increasingly restrictive narrow, dead-end, and tree layouts. Among the representative TP and PIBT-family MAPD baselines in the main sweep, only SHARP attains 100% success on all tested configurations.

Panel of Figure 3 — Figure 3: Normalized service time. Bars show successful-run means, error bars show one standard deviation, and missing bars mean no successful runs.

Panel of Figure 4 — Figure 4: Normalized makespan, with the same plotting conventions as Figure 3 .

Well-formed (absolute means)
$\lambda$	Method	Succ.	Makespan	Service	Runtime
1.0	TP	100.0	370.8	39.1	2.53
	TP-home-return	100.0	537.9	120.3	2.42
	TP-SIPP-home-return	100.0	538.4	120.3	2.80
	SHARP	100.0	349.2	33.0	2.86
3.0	TP	100.0	702.0	180.8	4.53

Table 2: TP-style fixed-home-return comparison on Ma et al. well-formed 30-agent conditions (30 paired seeds). Values are absolute means; lower is better except success; runtime is in seconds.

Tree (ratios)
$\lambda$	Method	Succ.	Makespan	Service	Runtime
1.0	TP	0.0	–	–	–
	TP-home-return	100.0	1.00	1.00	1.00
	TP-SIPP-home-return	100.0	1.01	1.00	1.34
	SHARP	100.0	0.79	0.53	20.46
3.0	TP	0.0	–	–	–

Table 3: Tree subset of the TP-style fixed-home-return comparison on 30-agent conditions (30 paired seeds). Ratios are normalized to TP-home-return = 1.00; lower is better except success.

Metric	SHARP	No-overwrite
Success (%)	100	100
Makespan	1.00	1.53
Service time	1.00	1.89
Travel distance	1.00	1.53
ms/step	1.00	1.43
Planner calls	1.00	1.24

Table 4: No-overwrite variant on the high-load tree condition (30 agents,

\lambda=3.0

, 30 paired seeds). Ratios are normalized to SHARP = 1.00; lower is better except success.

Setting	Calls	Expanded	Failed
well-formed 30 agents, $\lambda=3.0$	4,201	0.72M	0.75
narrow-bi-dead 30 agents, $\lambda=3.0$	4,249	0.84M	102.19
tree 30 agents, $\lambda=1.0$	19,530	61.08M	9513.75
tree 30 agents, $\lambda=3.0$	56,964	185.98M	27790.61

Table 5: Representative SHARP planner effort in the main sweep, reported as mean per successful run. Calls are SIPP segment searches, Expanded is the number of expanded SIPP nodes, and Failed is the number of rejected SIPP segment searches rather than failed simulation runs. Smaller values indicate less search effort.

Warehouse Automation

See all 14 papers

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses
Aug 27, 2026Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji +1Multi-Agent Planning Multi-Agent Path Finding
Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan
Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations
Jul 20, 2026Chuanlong Zang, Isabelle Barz, Anna Mannucci +3Multi-Agent Coordination Multi-Robot Systems
1Robert Bosch GmbH, Corporate Research, Stuttgart, Germany. · 2Technical University of Berlin, Berlin, Germany. · 3Robotics Institute Germany (RIG).
Many-to-Many Multi-Agent Pickup and Delivery
May 8, 2026Ethan Schneider, Jingkai Chen, Tianyi Gu +3Multi-Agent System Optimization Multi-Robot Task Allocation
Institute of Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA · Symbotic Inc., Wilmington, MA 01887, USA · Northeastern University, Boston, MA 02115, USA

Aug 27, 2026J/K move · Enter open · S save

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses

Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda

Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan

Multi-Agent Planning Multi-Agent Path Finding Constrained Motion Planning Multi-Robot Task Allocation

Open paper AskPDF arXiv

Space-efficient warehouse layouts often contain single-agent-width aisles and dead-end workstations where robots have few places to wait without blocking others. In Multi-Agent Pickup and Delivery (MAPD) on such constrained layouts, robots must accept online pickup-delivery tasks while preserving protected waiting locations called Havens. The Safe HAven Retreat Planner (SHARP) introduced a mechanism that extends each committed task path with a validated retreat to the agent's dedicated initial Haven, but fixed-Haven commitments can send agents toward distant Havens after deliveries. We present A-sharp (Adaptive SHARP), which changes an agent's retreat target at task assignment time. A naive switch can cause two agents to rely on the same waiting location or let another committed path pass through a location that is still occupied or reserved. A-sharp prevents these failures with an availability test for candidate Havens and a pending-release rule that keeps the previous Haven protected until the agent departs. Under explicit Haven-structure and Safe Interval Path Planning (SIPP) assumptions, we prove invariant preservation and finite-release completeness: every task in any finite release sequence is delivered in finite time. Across 72,000 runs on 14,400 paired map-agent-count-rate-seed cases over four maps, both SHARP and A-sharp complete their respective 14,400 runs. For makespan (final delivery time), a prespecified paired comparison with Holm correction over all 138 configurations with more Havens than agents finds A-sharp significantly better in 107 configurations and never significantly worse than SHARP; on the tested tree map, the median reduction is 16.7%.

Abstract

Warehouse Automation

Explore similar work

Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses

Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations

Many-to-Many Multi-Agent Pickup and Delivery