融合改进斜四邻域A^*与三次B样条曲线的路径规划算法

摘要

针对传统A*算法八邻域搜索路径节点多导致搜索及规划路径速度慢的问题,提出1种融合改进斜四邻域A*与三次B样条曲线的路径规划算法。在传统八邻域搜索启发下,删除原本上下左右4个方向上的搜索路径,保留右上、右下、左上及左下4个方向的搜索路径,使算法在搜索时速度更快,搜索路径节点数更少;引入三次B样条曲线,优化路径上的尖锐拐点,使路径更平滑。采用提出的算法与其他2种算法在3种不同分辨率及不同障碍率的地图上进行实验验证。结果表明:相比于传统A*算法,改进斜四邻域A*算法的搜索时间缩短83.4%,路径节点数减少89.7%;引入的三次B样条曲线使斜四邻域A*算法规划出的路径更平滑,提出的算法可极大提高路径搜索及规划的有效性。

关键词

A^*算法 / 斜四邻域搜索 / 三次B样条曲线 / 路径规划