韩晓微,刘宏宇,石泽亮,刘 晓

(沈阳大学 a.科技创新研究院,b.信息工程学院,辽宁 沈阳 110041)

路径规划是移动机器人技术研究中的重要组成部分[1],其目的是为移动机器人寻找一条从起点到终点的安全(无碰撞)、高效(最短距离或最短时间)的最优或接近最优的路径[2].

常用的路径规划算法有蚁群算法、粒子群算法、模拟退火算法和神经网络等[2].目前对路径规划算法的研究主要基于真实环境的栅格分解描述,把机器人的运动环境分解成许多简单的栅格,根据是否被障碍物占据来进行状态描述[3].Dijkstra算法解决的是有向图中从一个节点到其他节点的最短路径问题.以起点为中心,逐步向周围相邻节点拓展,被拓展的点都是到该点的最短路径,直到达到目标点[4].该方法在地图较小时可以使用,随着地图的增大计算量也会急剧增长[5].针对此问题提出的A*算法融合了Dijkstra算法及贪心算法思想,通过计算启发函数来评估当前节点到下一节点的代价大小来寻找一条最优路径.此算法应用较为灵活,但当起点与终点之间的距离较长时,A*算法评估代价时会计算大量重复数据,降低搜索效率[6].

2017年Charri等设计了松弛A*算法,其执行时间大大减少,增大了约束性复杂度,松弛A*能成为最佳路径规划器是因为其在度量之间提供了良好的权衡[7].石征锦等[8]在启发函数中加入余弦相似性和方向信息,再做归一化处理,改进A*算法.辛煜等[9]成功扩大搜索邻域,重新定义中心节……