解决移动障碍物下的多智能体路径规划问题，提升仓库机器人协同效率
Conflict-Based Search and Prioritized Planning for Multi-Agent Path Finding Among Movable Obstacles
- 融合冲突搜索与优先规划，结合单智能体移动障碍物求解器
- 支持20个智能体和数百个移动障碍物，路径规划成功率显著提升
- 适合物流、仓储场景中复杂动态环境下的多机器人调度
本文研究多智能体在可移动障碍物中的路径规划（M-PAMO），旨在为多个智能体在静态与可移动障碍物环境中从起点到目标点找到无碰撞路径。该问题常见于物流与仓储场景，当移动机器人面对突发的可移动物体时面临挑战。尽管多智能体路径规划（MAPF）与单智能体在可移动障碍物中的路径规划（PAMO）已有研究，但M-PAMO仍鲜有探索。可移动障碍物使状态空间呈指数级增长，且常在时空上紧密耦合智能体。本文首次尝试将流行的冲突基于搜索（CBS）与优先规划（PP）方法，与近期提出的单智能体PAMO*求解器融合，以应对M-PAMO。实验对比了最多20个智能体与数百个可移动障碍物下的性能，揭示了各方法的优劣。
原文摘要 · Abstract (English)
This paper investigates Multi-Agent Path Finding Among Movable Obstacles (M-PAMO), which seeks collision-free paths for multiple agents from their start to goal locations among static and movable obstacles. M-PAMO arises in logistics and warehouses where mobile robots are among unexpected movable objects. Although Multi-Agent Path Finding (MAPF) and single-agent Path planning Among Movable Obstacles (PAMO) were both studied, M-PAMO remains under-explored. Movable obstacles lead to new fundamental challenges as the state space, which includes both agents and movable obstacles, grows exponentially with respect to the number of agents and movable obstacles. In particular, movable obstacles often closely couple agents together spatially and temporally. This paper makes a first attempt to adapt and fuse the popular Conflict-Based Search (CBS) and Prioritized Planning (PP) for MAPF, and a recent single-agent PAMO planner called PAMO*, together to address M-PAMO. We compare their performance with up to 20 agents and hundreds of movable obstacles, and show the pros and cons of these approaches.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。