一种对地图特征定向采样的改进A*算法

简介

在移动机器人全局最优路径规划中,提出了一种对地图特征定向采样的改进A*算法,指在确保安全的前提下兼顾算法的效率和最优性。此算法分为三个部分,第一部分地图前处理,为确保路径安全无碰撞先进行障碍物膨胀处理,再借鉴基于采样的方法思想,但对地图特征进行定向采样,避免了基于采样的算法的随机性带来的路径成本过高问题。第二部分邻接矩阵构建,将采样所得特征点与始末点连接,将各点坐标及通断信息以邻接矩阵存储。第三部分路径搜索,用邻接矩阵替代原地图,并使用基于搜索的算法找出最优解,此时邻接矩阵信息量远低于原地图,避免了基于搜索的算法在处理大量节点时效率低下的问题。将改进的A*算法与传统A*路径规划算法在栅格地图中进行仿真对比。结果表明,虑移动机器人外围尺寸的障碍物膨胀处理能够确保规划出的路径是安全无碰撞的。改进A*算法的路径更短,冗余拐点更少,规划效率更高,特别是路径总转角降低达到60%,同地图再次规划时的规划效率可提升40%。