为密集仓库设计固定安全区,确保多机器人任务高效完成。
Fixed-Haven Reservation for Online Multi-Agent Pickup and Delivery in Dense Warehouses

- 每个机器人拥有专属安全区,其他机器人不可占用,避免阻塞。
- 在树状布局中实现100%任务成功率,优于现有方法。
- 适合高密度仓库场景,对路径规划鲁棒性要求高的应用。
密集仓库常有单行道、死胡同和树状导引路径,导致空闲机器人难以等待而不阻塞他人。现有多智能体取送货(MAPD)方法通常依赖额外等待点或双连通拓扑,这些假设在复杂布局中可能失效。本文研究在线MAPD中的固定安全区预留机制:每个代理拥有一个固定的专属安全区(通常为其起点),仅所有者可占据,其余代理视为障碍。对于有限任务释放,在安全区可达性和显式规划/进展假设下,该机制能保证所有任务完成。我们实现了名为SHARP的避险规划器,确保每个忙碌或回撤中的代理始终沿无碰撞的预留路径返回其安全区。与代表性TP和PIBT系列基线(如Token Passing、PIBT、PIBTTP-TA)相比,SHARP在树状布局中表现出100%成功率,尽管中心化规划成本更高。采用类似TP的固定返程机制并加入全程验证也能恢复鲁棒性,表明固定返回是关键机制。禁用中途回撤重分配的变体使服务时间增加1.89倍,总完成时间增加1.53倍(高负载树状条件)。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。