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

AI summary

Overview

Research area: Multi-Agent Pickup and Delivery (MAPD) and Multi-Agent Path Finding (MAPF) applied to automated warehouses, with a focus on planning safety guarantees on constrained guidepath graphs.

Technical level: Advanced. The paper is built on formal graph definitions, invariant-based proofs, and Safe Interval Path Planning (SIPP) reservation semantics; the experimental protocol uses prespecified paired statistical comparisons with Holm correction.

One-sentence scope: The paper proposes A♯sharp (Adaptive SHARP), a dynamic Haven selection method that lets an agent's protected retreat target change at task assignment time, and proves that this ownership transfer preserves safety and finite-release completeness.

What This Paper Is About

In MAPD, robots must accept online pickup-and-delivery tasks and keep a safe place to wait without blocking others. Prior SHARP guarantees this by pairing every committed task path with a validated retreat to the agent's fixed dedicated initial Haven, which can force unnecessary travel when the robot finishes a delivery far from home. A♯sharp asks whether the retreat target itself can be changed online — and answers that this requires an ownership-transfer protocol, not just a nearest-available-Haven heuristic.

Key Contributions

1. A dynamic Haven extension of safe-haven retreat planning. A♯sharp adds an availability-checked, pending-release ownership-transfer protocol on top of fixed-Haven retreat planning, allowing the retreat target to change at task assignment time.

2. A formal safety and completeness proof. Under explicit Haven-structure conditions (Definition 2) and SIPP planning assumptions, the authors prove that dynamic Haven updates preserve exclusivity and reservation invariants (Proposition 1, Lemma 1) and that every task in any finite release sequence is delivered (Theorem 1). A corollary shows the algorithm recovers the fixed-Haven baseline when it always selects the current Haven.

3. Three documented failure modes of naive switching. The paper isolates why a naive switch fails: premature release of an occupied Haven, selecting a Haven that appears in another agent's committed future path, and self-collision with stale self-reservations. These motivate the three protocol obligations expressed as Equations (1)–(3).

4. A large paired empirical evaluation. A♯sharp and the restricted fixed-Haven SHARP baseline are compared across 72,000 runs on 14,400 paired map–agent-count–rate–seed cases over four maps.

Main Findings

• Complete success for both methods: Across 72,000 runs, both SHARP and A♯sharp complete all 14,400 runs assigned to each method (100% success).

• Makespan improvement in most Haven-surplus configurations: A prespecified paired comparison with Holm correction over all 138 Haven-surplus configurations (|A| < |H|) finds A♯sharp significantly better in 107 configurations.

• No significant losses: A♯sharp is never significantly worse than SHARP across all 138 comparisons after Holm correction.

• Median makespan reduction on the tree map: On the tested tree map, the median reduction in makespan (final delivery time) is 16.7%.

• Release-to-delivery results are map-dependent: Reductions in average release-to-delivery time are strong on the tested tree map but are not uniform on the two narrow-biconnected maps.

• Naive switching is provably unsafe: The three counterexamples (premature release of an occupied Haven, selecting a future-reserved Haven, self-collision with stale reservations) each negate one of the three transfer obligations, showing that dynamic Haven selection requires an explicit transfer protocol rather than a heuristic substitution.

• No empirical comparison to standby-node methods: The authors state that porting Standby-Based Deadlock Avoidance (SBDA) would require reimplementing its task-execution, standby-node, and coordination semantics in the common simulator, so no such comparison is presented.

• Planning cost: With cached shortest-path distance fields, one assignment-loop pass costs O(|I|(|Q| + |H|C_avail + C_SIPP)), and worst-case per-timestep cost is O(min(|I|,|Q|)|I|(|Q| + |H|C_avail + C_SIPP)).

Methodology in Plain English

The researchers start from an existing safe-haven retreat design (SHARP). When a robot accepts a task, the planner reserves not only the path that does the pickup and delivery, but also a return path to a protected waiting spot called a Haven. In the original design, that Haven is fixed for the whole run — the robot's dedicated initial position.

A♯sharp keeps the reservation-based retreat idea but lets the Haven itself change. At each task assignment, an agent picks the nearest pending task by pickup distance, then the nearest Haven by delivery-to-Haven distance among candidates that pass an availability test. That test has two parts: no other agent may hold the candidate in its exclusive set, and no other agent may have a committed reservation occupying it at any future time. A full path is then validated by concatenating three SIPP segments — current position to pickup, pickup to delivery, delivery to Haven — where other agents' reservations and exclusive Havens are constraints, and the replanning agent's own replaceable future reservations (times later than the current timestep) are excluded because a successful commitment deletes and replaces them. If any segment fails, nothing changes.

The subtle part is ownership transfer. If the agent is still physically sitting on its old Haven, the old Haven stays protected by a pending-release rule until the agent actually departs, at which point post-execution cleanup removes it. The update is atomic: no other assignment or planning step can observe only part of the new state. Each assignment pass evaluates one greedy task–Haven candidate per eligible agent against the same state, commits at most one globally best validated candidate, then recomputes.

The proof proceeds in layers: Proposition 1 handles the ownership update, Lemma 1 shows one timestep preserves all invariants, Lemma 2 shows that once traffic has quiesced any available Haven yields a feasible full path through the connected core G[F], and Theorem 1 combines the invariants with finite task releases and repeated assignment-loop invocation. The authors note the guarantee only covers deterministic discrete-time execution, a centralized reservation table, non-preemptive one-pickup-one-delivery tasks, and maps satisfying Definition 2 (connected core G[F], every Haven adjacent to the core, all task endpoints in the core, and |A| ≤ |H| initially). Execution delays, localization errors, dynamic obstacles, and shared parking are not modeled.

Experiments use four maps — the public well-formed MAPD benchmark reflecting Kiva-style warehouses, narrow-biconnected (narrow-bi), narrow-biconnected with depth-1 dead ends (narrow-bi-dead), and a tree-like task-area layout. All maps were checked against the Haven structure conditions before evaluation.

Why This Matters

Impact on research: The paper isolates a specific, previously unaddressed question — can the retreat target in a reservation-based safe-haven planner be transferred online without breaking reservation semantics? It supplies the invariants, proof obligations, and a transfer protocol, which is a distinct contribution from the broader prior SHARP system. It also expands the class of layouts on which completion guarantees can be maintained beyond well-formedness and biconnectivity assumptions used by Token Passing and PIBT.

Real-world applications:

• Space-efficient automated warehouses with single-agent-width aisles where robots cannot pass side by side.
• Facilities with dead-end workstations where a parked robot can disconnect the remaining traffic area.
• Tree-structured guidepath layouts with narrow aisles and branches leading to workstations and storage locations.
• Logistics systems where fleets must accept online pickup-delivery tasks and keep a valid fallback waiting location at all times.

Industry relevance: Warehouse operators care about throughput and about avoiding deadlock in dense layouts. A♯sharp's practical claim is modest but concrete: on the tested tree map, median makespan falls 16.7% versus fixed-Haven retreat, with no significant makespan losses in any of the 138 Haven-surplus configurations. The paper explicitly says it does not claim throughput state of the art; the contribution is a completion-preserving ownership-transfer mechanism that a learned or optimization-based selector could also use, subject to the same availability test.

Future Directions

• Removing the greedy single-candidate restriction. A♯sharp evaluates only one greedy task–Haven pair per considered agent per pass; if validation fails, assignment may be delayed even when another pending task or farther Haven would validate. The authors call this a throughput heuristic, not a safety condition, and note segment-wise validation is not a global completeness claim during active traffic.

• Comparing against standby-node methods. A controlled comparison with SBDA would require reimplementing its task-execution, standby-node, and coordination semantics in the common simulator, which the authors deliberately did not do.

• Broadening the execution model. The guarantee excludes execution delays, localization errors, dynamic obstacles, and shared parking, all of which are listed as outside the proof's scope and are natural extensions.

• Characterizing why gains differ by map. Reductions in average release-to-delivery time are strong on the tree map but not uniform on the two narrow-biconnected maps; understanding the structural properties that determine when dynamic Haven selection helps is left open.

Target Audience

Researchers and graduate students in multi-agent path finding, multi-agent pickup and delivery, and automated-warehouse planning who are interested in completion guarantees on constrained graph structures. It is also relevant to practitioners designing warehouse guidepath layouts who need waiting-location and deadlock-avoidance strategies, and to readers familiar with SIPP and reservation tables who want a concrete example of proving safety for an online ownership-transfer protocol. The paper is not beginner-friendly: it assumes comfort with formal invariants, graph-theoretic conditions, and space-time path planning.

Authors’ abstract

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