提出多依赖PIBT，让上千智能体在复杂环境中高效规划路径。
Planning over MAPF Agent Dependencies via Multi-Dependency PIBT
- 通过构建代理依赖关系，扩展了传统PIBT的单碰撞路径限制。
- 可处理最多10000个同质智能体，支持旋转、差速等运动约束。
- 适合大规模密集场景下的多智能体路径规划，尤其适用于大尺寸代理。
现代多智能体路径规划（MAPF）算法需在拥挤环境中于1秒内为数百至数千个智能体生成路径，要求极高效率。优先级继承回溯（PIBT）是此类场景下流行的高效算法，但其基于规则的规划过程受限于仅考虑与单一其他智能体冲突的路径，缺乏通用性。本文提出从代理依赖关系角度重构MAPF求解思路，受PIBT优先级继承逻辑启发，定义了代理依赖概念，并提出多依赖PIBT（MD-PIBT），在依赖关系空间中进行搜索。该框架具备通用性，特定参数可还原PIBT和增强型PIBT（EPIBT）；其他配置则拓展其能力，支持多步推理，可处理与多个智能体冲突的路径。实验表明，MD-PIBT可在多种动力学约束下有效规划最多10,000个同质智能体，包括石子移动、旋转运动及具有速度与加速度限制的差速驱动机器人。在不同类型的MAPF问题上进行了全面评估，结果表明其在大尺寸代理场景中表现尤为出色。代码已开源：https://github.com/lunjohnzhang/MD-PIBT。
原文摘要 · Abstract (English)
Modern Multi-Agent Path Finding (MAPF) algorithms must plan for hundreds to thousands of agents in congested environments within a second, requiring highly efficient algorithms. Priority Inheritance with Backtracking (PIBT) is a popular algorithm capable of effectively planning in such situations. However, PIBT, and its variants like Enhanced PIBT (EPIBT), is constrained by its rule-based planning procedure and lacks generality because it restricts its search to paths that collide with at most one other agent. In this paper, we describe a new perspective on solving MAPF by planning over agent dependencies. Taking inspiration from PIBT's priority inheritance logic, we define the concept of agent dependencies and propose Multi-Dependency PIBT (MD-PIBT) that searches over agent dependencies. MD-PIBT is a general framework where specific parameterizations can reproduce PIBT and EPIBT. At the same time, alternative configurations generalize PIBT and EPIBT to multi-step planning capable of reasoning paths that collide with more than one other agent. Our experiments demonstrate that MD-PIBT effectively plans for as many as 10,000 homogeneous agents under various kinodynamic constraints, including pebble motion, rotation motion, and differential drive robots with speed and acceleration limits. We perform thorough evaluations on different variants of MAPF and find that MD-PIBT is particularly effective in MAPF with large agents. Our code is available at https://github.com/lunjohnzhang/MD-PIBT.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。