CWave: High-performance single-source any-angle path planning on a grid
CWave: High-performance single-source any-angle path planning on a grid
复制标题
CWave：网格上的高性能单源任意角度路径规划
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
T. Padır
中科院分区：
文献类型：
--
作者：
D. Sinyukov;T. Padır
二维网格上的路径规划是机器人领域的一个研究热点。它通常涉及搜索网格上两个顶点之间的最短路径。单源路径规划是一个改进的问题，它要求找到从给定点到地图上所有其他点的距离。提出了一种高性能的单源任意角度路径规划算法CWave。路径规划算法的“任意角度”属性意味着这样的算法可以找到可以包括任意角度段的路径，与8连通图上的标准A/D相反，路径只能以45°增量转弯。该算法的核心思想是，它不表示为一个图形的网格，并使用离散的几何图元来定义波前。在其最纯粹的形式中，CWave只需要整数运算和乘以2，但可以在转折点处累积距离误差。还开发了一个修改版本的CWave与最小的使用浮点计算。它可以消除任何累积误差，这在多张地图上得到了数学和实验的证明。该算法在三个地图上的性能被证明是显着快于Theta的，懒惰Theta的和字段A的适应于单源规划。目前的算法实现的局限性以及潜在的改进进行了讨论。
Path planning on a 2D-grid is a well-studied problem in robotics. It usually involves searching for a shortest path between two vertices on a grid. Single-source path planning is a modified problem which asks to find distances from a given point to all other points on the map. A high-performance algorithm for single-source any-angle path planning on a grid that we named CWave is proposed in this work. “Any-angle” attribute of a path planning algorithm implies that such algorithm can find paths which may include any angle segments, as opposed to standard A∗ on an 8-connected graph, the path can turn with 45°-increments only. The key idea of the presented algorithm is that it does not represent the grid as a graph and uses discrete geometric primitives to define the wave front. In its purest form, CWave requires for computation only integer arithmetics and multiplication by two, but can accumulate the distance error at turning points. A modified version of CWave with minimal usage of floating-point calculations is also developed. It allows to eliminate any accumulative errors which is proven mathematically and experimentally on several maps. The performance of the algorithm on three maps is demonstrated to be significantly faster than that of Theta∗, Lazy Theta∗ and Field A∗ adapted for single-source planning. The limitations of the current implementations of the algorithm as well as potential improvements are discussed.