论文链接：https://ieeexplore.ieee.org/document/11554306

多智能体路径规划（MAPF）旨在为多个智能体计算从起点到目标配置的安全、无冲突路径。现代机器人部署常涉及形状不规则或载荷较大的异构智能体，使得基于点或圆的近似方法无法用于安全高效的规划。为此，我们提出了任意角度和任意形状的安全区间路径规划（AAG-SIPP）算法，该算法通过允许任意角度在相邻和非相邻网格单元之间移动，为拥有任意多边形形状（包括凸和凹多边形）的多智能体系统规划安全路径。由于AAG-SIPP在优先规划框架下运行，我们引入了形状启发式（SH）策略，根据几何复杂度确定代理的规划顺序，确保更高的成功率和平衡的路径长度。实验结果表明，AAG-SIPP为复杂的MAPF场景提供了更稳健高效的解决方案，实现了多达92.44%的运行时间缩短和跨多样地图的优越路径质量，有效解决了循环模型基线难以处理的密集仓库问题。

Y. Li, X. Zhang, R. Wang, Z. Hu, Y. Wang. Any-Angle and Arbitrary-Geometry SIPP: Multi-Agent Path Finding With Polygonal Shapes. IEEE Robotics and Automation Letters (RA-L), 2026, 11(8): 9367-9374.

Abstract

Multi-Agent Path Finding (MAPF) aims to compute safe, conflict-free paths from start to goal configurations for multiple agents. Modern robotic deployments frequently involve heterogeneous agents with irregular shapes or large payloads, making conventional point or circle based approximations inapplicable for safe and efficient planning. To address this, we propose the Any-Angle and Arbitrary-Geometry Safe Interval Path Planning (AAG-SIPP) algorithm, which plans safe paths for multi-agent systems with arbitrary polygonal shapes, including convex and concave geometries, by allowing any-angle movement between both adjacent and non-adjacent grid cells. As AAG-SIPP operates within a prioritized planning framework, we introduce a Shape Heuristic (SH) strategy to determine the planning sequence of agents based on their geometric complexity, ensuring higher success rate and balanced path lengths. Experimental results show that AAG-SIPP provides a more robust and efficient solution for complex MAPF scenarios, delivering up to a 92.44% reduction in runtime and superior path quality across diverse maps, effectively solving dense warehouse problems that remain difficult for circular-model baselines.