Source-linked AI summary
Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses
Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji, Itsuki Noda
TL;DR
Constrained warehouses make online MAPD difficult because agents have few safe places to wait, while fixed-Haven retreat can create unnecessary travel. A-sharp dynamically transfers retreat targets using availability checks and pending release, preserving safety and completeness under stated assumptions. Across the evaluation, it matched SHARP’s success and improved makespan in most Haven-surplus configurations.
Problem
Fixed-Haven MAPD retreat planning can send agents toward distant Havens, while naive dynamic switching risks conflicts with occupied or reserved locations.
Method
A-sharp selects an available Haven at task assignment, validates the full path with SIPP, and keeps an occupied previous Haven protected until departure.
Results
A-sharp and SHARP each completed all 14,400 runs; A-sharp was significantly better in 107 of 138 Haven-surplus configurations and never significantly worse after Holm correction.
Takeaways & Limitations
Dynamic Haven ownership transfer preserved the tested safety and completion guarantees while improving makespan relative to fixed-Haven SHARP in the reported comparisons.
Takeaways & Limitations
The guarantees rely on explicit Haven-structure and SIPP assumptions, while constrained-map absolute task-performance values are not reported as commercial-product benchmarks.
Abstract
from arXiv · showhide
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%.
1. Introduction
MAPD completion is difficult in narrow, dead-end warehouse layouts because waiting and returning agents can obstruct one another. A-sharp extends safe-haven retreat planning with dynamic Haven ownership transfer while preserving safety and completion guarantees.
- Constrained warehouse layouts make MAPD completion difficult because waiting, returning, or blocked agents can obstruct narrow corridors and dead ends.
- SHARP pairs each committed task path with a SIPP-validated retreat to the agent’s dedicated initial Haven.Agents may accept new tasks before physically returning home when the replacement task path and retreat are validated.
- Fixed-Haven commitments can add unnecessary travel after delivery when nearby safe waiting locations exist.Dynamic selection must also account for other agents’ ownership and space-time reservations.
- A-sharp selects an available Haven at task assignment and protects an occupied previous Haven until the agent departs.Availability checks exclusive ownership and future reservations.
- 72,000 runs across 14,400 paired cases achieved 100% success for both SHARP and A-sharp, while A-sharp improved makespan significantly in 107 of 138 configurations without significant losses.The comparison used Holm correction across configurations with more Havens than agents.
2. Background and Positioning
MAPD adds online pickup-delivery tasks to MAPF, while existing completeness guarantees often depend on favorable graph structure. A-sharp isolates dynamic retreat-target ownership transfer from prior safe-haven and parking approaches.
- MAPD extends MAPF with online tasks having pickup, delivery, and release-time requirements.Completeness means delivering every released task in finite time.
- Existing methods rely on structural assumptions such as well-formedness for TP or biconnectivity for PIBT.
- Parking, dummy-endpoint, and standby-node methods manage waiting locations but differ from A-sharp in guarantees and ownership-transfer semantics.
- Prior SHARP: Prior SHARP reserves both task and retreat paths to a dedicated initial position using SIPP and permits validated retreat-suffix replacement.
- A-sharp positioning: A-sharp narrows the setting to standard graph-level online MAPD and adds availability-checked transfer of reservation-backed Haven ownership.
3. Problem Setting and Haven Conditions
The problem uses discrete-time MAPD on an undirected graph with designated Havens separated from a connected task-supporting core. Haven structure, distinct initial Havens, and explicit task assumptions support the completeness proof.
- Agents move or wait on an undirected graph while vertex collisions and edge-swap collisions are disallowed.
- Each task specifies pickup vertex, delivery vertex, and release time, and is assigned at most once without preemption or transfer.
- Havens are candidates outside the task-supporting core, and each agent’s exclusive set protects its current Haven and any occupied previous Haven during transfer.
- Haven structure conditions: The Haven structure requires a connected core, a core neighbor for every Haven, and all task endpoints in the core.
- Initial conditions: Agents start at distinct Havens, and the injectivity invariant maintains distinct current Havens over time.
- Scope of assumptions: These conditions are sufficient for the feasible path construction and completeness guarantee but are not necessary for every solvable instance.
4. Why Naive Dynamic Haven Switching Fails
Naive Haven switching can expose occupied locations, select future-reserved locations, or retain stale reservations. A-sharp addresses these failures through coupled ownership, reservation, and replacement rules.
- Safe transfer requires obligations covering occupied Haven protection, future-reservation exclusion, and stale-reservation replacement.
- The counterexamples show that premature release, future-reserved selection, and stale reservations respectively violate execution safety, reservation exclusion, and replacement semantics.
- Premature release: Releasing an occupied old Haven before the agent’s first move lets another agent plan through a physically occupied vertex.
- Future reservations: Ownership-only selection can choose a Haven appearing in another agent’s committed future path, creating a vertex-time conflict.Safe switching therefore requires both ownership and future-reservation tests.
- Replacement semantics: A retreating agent’s unexecuted suffix must be overwritten, because stale reservations can reject feasible updates or block later agents.
- Protocol response: A-sharp combines future-reservation testing, delayed release of occupied Havens, and controlled replacement to address these failures.
5. A♯: Dynamic Haven Retreat Planning
A♯ dynamically selects retreat Havens during task assignment while preserving ownership and reservation safety. It validates complete task-to-Haven paths and uses deterministic greedy selection with pending-release protection.
- Haven selection: A♯ selects an available Haven by checking both exclusive ownership and other agents’ future reservations.The current agent’s own reservations and exclusive set are ignored when testing candidate availability.
- Haven selection: Pending release keeps an agent’s previous Haven exclusive until the agent departs from it.This prevents ownership transfer from exposing an occupied or still-protected Haven.
- Assignment loop: Eligible agents greedily choose the nearest pending pickup and the nearest available Haven for that task, while SIPP—not distance—determines feasibility.Each assignment-loop pass evaluates one candidate per eligible agent, commits at most one globally best validated candidate, then recomputes candidates.
- Commitment and execution: After successful SIPP validation, A♯ replaces the agent’s future reservations with a full pickup–delivery–retreat path and updates Haven ownership.The current time reservation remains fixed, while later reservations are replaceable.
- Assignment loop: During active traffic, evaluating only one greedy task–Haven pair can delay assignment despite another feasible task or farther Haven.This is presented as a throughput heuristic rather than a safety condition or global completeness claim.
- Assignment loop: With cached shortest-path distances, one assignment-loop pass costs O(|𝐼|(|𝑄| + |𝐻|𝐶avail + 𝐶SIPP)).𝐶avail is the cost of one availability test and 𝐶SIPP is the cost of three SIPP segment searches.
6. Theoretical Guarantees
Under explicit Haven-structure, execution, reservation, and SIPP assumptions, A♯ preserves safety invariants and delivers every task in any finite release sequence. Quiescent planning and fixed-Haven recovery support the completeness argument.
- Invariant preservation: A♯ preserves exclusive-set invariants after dynamic Haven updates when the selected agent has no pending-release old Haven.The proposition covers injective current-Haven assignments, disjoint exclusive sets, and the one-pending-Haven bound.
- Invariant preservation: A♯ preserves execution and reservation invariants across each complete timestep of assignment, reserved execution, and pending-release cleanup.The proof applies the dynamic-update proposition and planner soundness in phase-local order.
- Finite-release completeness: In quiescence, PlanFullPath succeeds for any pending task, agent, and Haven available to that agent under the stated structural and SIPP assumptions.The result requires finite reservation constraints and a per-segment horizon of at least diam(𝐺[𝐹]) + 1.
- Finite-release completeness: Every task in any finite release sequence is delivered in finite time under A♯’s explicit execution, reservation, eligibility, and SIPP assumptions.The proof uses eventual quiescence of finite committed suffixes and quiescent planning to force another successful commitment.
- Fixed-Haven case: When A♯ always selects the current Haven initialized to the baseline’s fixed Havens, it recovers the fixed-Haven SHARP case and inherits the theorem’s guarantee.In this case Haven ownership never changes.
7. Experiments
The evaluation tests SHARP and A♯ across four warehouse maps, six agent counts, six task-generation rates, and paired seeds. Both safe-haven methods complete every tested configuration, while A♯ generally improves makespan in Haven-surplus settings but has selector-level service-time trade-offs on narrow-biconnected maps.
- Setup: The four maps range from a public well-formed benchmark to narrow-biconnected, dead-end, and tree-like layouts that violate progressively stronger structural assumptions.The constrained maps include single-width aisles, dead-end workstations, or tree-structured task areas.
- Setup: 72,000 runs cover 14,400 paired map–agent-count–rate–seed cases across four maps, five algorithms, six agent counts, and six task-generation rates.Each algorithm receives the same pre-generated task schedule within a paired case.
- Statistical comparison: On Haven-surplus configurations, the primary paired SHARP/A♯ comparison uses two-sided Wilcoxon tests with Holm correction across 138 tests for each metric.Configurations with equal numbers of agents and Havens are excluded because A♯ makes the same retreat-target choice as SHARP in the tested setup.
- Success: 100% success is achieved by both SHARP and A♯ in every tested configuration, whereas TP, PIBT, and PIBTTP-TA serve as structural-assumption diagnostics.A run succeeds only when all released tasks are delivered without collision, invalid movement, timeout, or stall safeguards being triggered.
- Results: On the public well-formed map with 30 agents and λ=3.0, A♯ reduces makespan from 695.2 ± 16.8 to 682.6 ± 15.7 and service time from 174.8 ± 5.7 to 173.8 ± 6.3.These correspond to 1.8% makespan and 0.6% service-time reductions in this setting.
- Metrics: Normalized service-time and makespan plots use per-map SHARP endpoint means, lower values are better, and error bars show one standard deviation over paired seeds.Absolute anchors for constrained maps are not reported.
8. Discussion and Limitations
The discussion bounds A-sharp’s claims by its simulation scope, execution assumptions, Haven-density requirement, and selector design. These boundaries distinguish the safety protocol from choices that affect congestion and performance.
- Scope and evaluation: Constrained-map results are paired relative algorithmic comparisons in simulation, not benchmarks of deployed products.Absolute constrained-map makespan and service-time values are not reported; the public well-formed benchmark and computation times use absolute units.
- Scope and evaluation: Each structural category uses one map, so the findings do not generalize across broader topology distributions or nonuniform warehouse demand.The 100 seeds vary Haven assignments and task sequences rather than map topology, with endpoints sampled uniformly from the stated candidate set.
- Assumptions: The completeness guarantee assumes deterministic discrete-time execution and a centralized reservation table.Unexpected delays, mechanical failures, and localization errors are outside the theorem and would require additional repair, slack, or replanning policies.
- Assumptions: The framework assumes distinct Havens with |A| ≤ |H|, while denser fleets would require shared parking, queueing, or buffer-cell rules.This assumption corresponds to dedicated parking or charging cells for robots.
- Selector limitations: Nearest-pickup and nearest-available-Haven selection are safety-independent heuristics that can be replaced if availability and commitment invariants remain preserved.On some narrow-biconnected configurations, a locally nearest Haven attracts traffic to constrained areas, indicating a selector-level trade-off.
9. Conclusion
A-sharp updates retreat targets while jointly maintaining Haven ownership and future reservations. Under the stated assumptions, it preserves safe completion and improves makespan in most Haven-surplus comparisons, while leaving selector refinement open.
- Conclusion: A-sharp jointly updates future path reservations and persistent Haven ownership when retreat targets change.Availability checks and pending release preserve the safety structure of safe-haven retreat planning.
- Conclusion: A-sharp preserves exclusivity and reservation invariants and delivers every task in any finite release sequence under the stated Haven and SIPP assumptions.This is the paper’s formal completion guarantee.
- Conclusion: Both SHARP and A-sharp achieved 100% success across all tested configurations.The result indicates that dynamic Haven ownership transfer did not weaken the fixed-Haven baseline’s tested robustness.
- Conclusion: A-sharp was significantly better in 107 of 138 Haven-surplus configurations and never significantly worse than SHARP after Holm correction.The largest map-level median gain was 16.7% on the tested tree map.
- Conclusion: Congestion-aware, learned, or optimization-based Haven selection remains a natural next step.The protocol is presented as compatible with future selector improvements that preserve its commitment semantics.
A. Detailed Proofs
The proofs show that availability-checked Haven transfers preserve ownership and reservation invariants, while finite committed suffixes and quiescent replanning establish finite-release completeness.
- Invariant preservation: Availability ensures a new Haven is not exclusively owned by another agent, preserving injectivity and disjointness during transfer.If the agent still occupies the old Haven, pending release keeps it protected; otherwise it can be released.
- Invariant preservation: Each successful commitment updates phase-local execution and reservation state before the next candidate is evaluated.PlanFullPath validates the candidate full path, after which the invariant argument proceeds through execution and cleanup.
- Quiescent completeness: In quiescence, every idle agent can validate a full path for a pending task to at least one available Haven.The current Haven is available to its owner, and any selected alternative is excluded from conflicting ownership or committed future reservations.
- Finite-release completeness: After the final successful commitment, finite committed suffixes execute to Havens and the system reaches quiescence; Lemma 2 then rules out a permanently pending task.This establishes delivery of every task in any finite release sequence.
B. Restricted Fixed-Haven Baseline
The restricted SHARP baseline keeps the initial injective Haven assignment fixed while matching A-sharp’s task selection, SIPP validation, and commitment order for comparison.
- Baseline design: The baseline uses the same task selector, SIPP validation, and commitment order as Algorithm 1.Its distinguishing restriction is retaining the initial Haven assignment throughout the experiment.
- Baseline design: The baseline requires a fixed injective Haven assignment η0, static exclusive sets X0(a), a reservation table R, and segment horizon Tmax.These inputs support the updated task, reservation, and agent commitments returned by the assignment loop.
- Assignment loop: At each decision time, the loop adds released tasks, considers idle or retreating agents, and selects the nearest feasible agent-task candidate.A validated full path returns to the agent’s fixed Haven η0(a); accepted commitments replace future reservations while retaining the current-time reservation.
Declaration on Generative AI
The authors disclose using OpenAI Codex for language-related assistance while retaining responsibility for the scientific content and publication.
- OpenAI Codex was used to paraphrase and reword the manuscript.
- The tool also assisted with writing style and grammar and spelling checks.
- The authors supplied and verified the scientific content and arguments, reviewed and edited tool-assisted changes, and take full responsibility for the publication's content.