该论文旨在解决匿名多智能体路径规划(Anonymous Multi-Agent Path-finding, AMAPF)中的一个关键限制。研究背景是:
- 经典多智能体路径规划(MAPF)中智能体与目标点的对应关系是固定的,而匿名AMAPF只要求所有目标点被占据,不关心具体哪个智能体到达哪个目标。
- 现有大多数算法基于离散环境表示(如方格网格),未考虑智能体尺寸,限制了在真实场景(如仓库移动机器人轨迹规划)中的应用。
- 连续空间方法通常对输入数据施加严格限制,例如要求起始/目标位置之间或与障碍物之间保持较大距离。
论文采用的具体方法是:
- 针对一种为连续空间设计的AMAPF算法进行改进,该算法将智能体建模为等尺寸的圆盘(disks)。
- 原算法要求任何起始/目标位置之间必须保持至少4倍智能体半径的严格最小间距。
- 提出一种修改方案,旨在放宽这一约束条件,将最小间距要求从4倍半径降低至2√3倍半径。
论文的核心创新点是:
- 显著放宽了连续空间匿名多智能体路径规划算法的输入约束条件,将所需的最小位置间距从4倍智能体半径降低至约3.464倍半径(即2√3)。
- 与现有工作相比,其独特之处在于:在保持算法理论保证的前提下,大幅降低了算法对起始/目标位置布局的苛刻要求,增强了算法在更紧凑、更现实场景中的适用性。
- 通过理论证明,所提出的增强措施保留了原算法的所有理论性质。
论文对该领域的整体贡献是:
- 理论上证明了在更宽松的间距约束(2√3倍半径)下,算法仍能保证所有智能体最终安全、无碰撞地到达目标。
- 提升了连续空间AMAPF算法的实用性和适用范围,使其能够处理起始/目标位置更密集的配置,更贴近实际应用场景(如仓库机器人调度)。
- 为将多智能体路径规划从离散网格推广到考虑智能体尺寸的连续空间模型提供了重要的约束条件优化方案。