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

Aug 27, 2026

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

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%.

Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji +1

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

Ask PDF

Jul 20, 2026

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

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.

Chuanlong Zang, Isabelle Barz, Anna Mannucci +3

1Robert Bosch GmbH, Corporate Research, Stuttgart, Germany. · 2Technical University of Berlin, Berlin, Germany. · 3Robotics Institute Germany (RIG).

Multi-Agent Coordination Multi-Robot Systems Multi-Agent Planning

Ask PDF

May 8, 2026

Many-to-Many Multi-Agent Pickup and Delivery

Multi-robot systems in automated warehouses must manage continuous streams of pickup-and-delivery tasks while ensuring efficiency and safety. Prior work on Multi-Agent Pickup-and-Delivery (MAPD) has largely focused on the one-to-one variant, where each task has a fixed pickup and delivery location. In contrast, real warehouses often present many-to-many MAPD scenarios, where items, tracked by stock keeping unit (SKU) identifiers, can be retrieved from or stored at multiple locations, resulting in an NP-hard four-dimensional assignment problem. To solve the many-to-many MAPD problem, we contribute our algorithm: Many-to-Many Multi-Agent Pickup and Delivery (M2M). We experiment with two variants of our algorithm: one that minimizes estimated task durations (M2M), and one which incorporates SKU distribution into the objective function (M2M-wSKU). Simulation results over 8-hour warehouse operations show that our method consistently matches or outperforms prior state of the art, with M2M completing up to 22,000 more tasks on average across different environments and warehouse inventory densities.

Ethan Schneider, Jingkai Chen, Tianyi Gu +3

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

Multi-Agent System Optimization Multi-Robot Task Allocation Multi-Agent Planning Warehouse Automation

Ask PDF

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