动态调整机器人避让点,提升仓库多机配送效率与安全性。
Dynamic Haven Selection for Multi-Agent Pickup and Delivery in Constrained Warehouses

- 根据任务分配动态切换避让点,避免路径冲突。
- 在7.2万次测试中100%完成任务,使完工时间中位数降低16.7%。
- 适合高密度仓库中需实时调度的多机器人系统。
空间紧凑的仓库常有单人通道和死端工位,导致机器人难以找到不阻塞他人的等待位置。在受限布局下的多机器人取送货(MAPD)中,机器人需在线接收任务,同时保护专用的避让点(Havens)。现有方法SHARP虽能为每条路径预留返回初始避让点的退路,但固定避让点可能导致任务完成后仍需远距离返回。本文提出A-sharp(自适应SHARP),在任务分配时动态调整机器人的退路目标。为防止两个机器人共用同一避让点或路径穿行于被占用区域,A-sharp引入候选避让点可用性检测与待释放规则,确保前一避让点在机器人离开前持续受保护。在显式避让结构和安全间隔路径规划(SIPP)假设下,证明了状态不变性与有限释放完备性:任何有限任务序列均可在有限时间内完成。在4个地图、14,400组地图-机器人数量-任务率-种子组合上共进行72,000次实验,两者均成功完成全部14,400次运行。在138种避让点数大于机器人数的配置中,配对比较显示,经霍尔姆校正后,A-sharp在107种配置中显著优于SHARP,且从未显著更差;在测试的树形地图上,中位数完工时间减少16.7%。
原文摘要 · Abstract (English)
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%.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。