Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm
Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm
复制标题
基于SIPP算法的多智能体任意角度寻路
DOI：
10.1609/icaps.v27i1.13856
复制
发表时间：
2017
影响因子：
0.2
通讯作者：
A. Andreychuk
中科院分区：
文献类型：
--
作者：
K. Yakovlev;A. Andreychuk
本文解决了为在共享 2D 工作空间中运行的相同圆形形状的多个代理找到无冲突轨迹的问题，并使用解耦（例如优先级）方法来解决此问题。代理的工作空间被镶嵌在允许任意角度移动的方形网格中，例如每个代理都可以向任意方向移动，只要该移动遵循其端点与不同网格元素相连的直线段即可。提出了一种基于安全间隔路径规划（SIPP）算法的新型任意角度规划器，用于寻找在网格上的动态障碍物（其他智能体）中移动的智能体的轨迹。然后将该算法用作优先多智能体规划器 AA-SIPP(m) 的一部分。在理论方面，我们证明 AA-SIPP(m) 在明确的条件下是完整的。在实验方面，在涉及多达 250 个智能体的模拟测试中，我们表明，与仅依赖基本移动的规划器相比，我们的规划器在成本方面找到了更好的解决方案（高达 20%）。
The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents' workspace is tessellated into the square grid on which any-angle moves are allowed, e.g. each agent can move into an arbitrary direction as long as this move follows the straight line segment whose endpoints are tied to the distinct grid elements. A novel any-angle planner based on Safe Interval Path Planning (SIPP) algorithm is proposed to find trajectories for an agent moving amidst dynamic obstacles (other agents) on a grid. This algorithm is then used as part of a prioritized multi-agent planner AA-SIPP(m). On the theoretical side, we show that AA-SIPP(m) is complete under well-defined conditions. On the experimental side, in simulation tests with up to 250 agents involved, we show that our planner finds much better solutions in terms of cost (up to 20%) compared to the planners relying on cardinal moves only.