基于A* 算法的机器人路径规划研究

(沈阳理工大学 辽宁 沈阳 110159)

一、引言

路径规划问题成为机器人领域中一个重要的研究课题。研究者提出了多种算法，如Dijkstra 算法，蚁群算法，模拟退火算法、粒子群算法等。这些算法没有将实际工作中的机器人与算法紧密的结合起来。

二、路径规划问题描述

机器人路径规划问题是指在工作区域中,机器人通过已知的环境信息或者对周围环境进行感知,按照预先设计的代价函数，通过一系列的算法，从起点开始找到一条代价最小的到终点的运动路径,该路径能避开工作空间中的障碍物。

根据机器人对环境信息的掌握程度可以分为全局规划方法,局部规划方法以及混合规划方法三种。

(1)全局规划方法必须知道整个环境地图中障碍物分布的大体情况。该方法可以找到最佳路径，但是考虑全局信息导致计算量大，效率低，不适用于未知环境或动态环境。

(2)局部规划方法中依靠机器人当前得到的局部环境信息,根据制定的规则来实现避障导航,该方法可以满足实时性要求，缺点是易陷入局部极值点,机器人可能在中途停止，无法到达目标点。

(3)混合型方法结合了全局规划和局部规划,具有良好的实用性。

三、基于改进的A*算法的路径规划

(一)A*算法原理

A*算法基于启发式搜索结构，它是 Dijkstra 算法的扩展，通过评估扩展节点的代价值，并比较其大小加以选择，使得在起点与终点之间寻找到一条代价最小的路径。广度优先(BFS)和深度优先(DFS)是简单的状态空间搜索策略。BFS方法的原理是从初始节点逐层向下查找，将当前节点按照可拓展的策略一层一层展开，直到找到目标节点。该方法能找到最优路径，但节点展开的数量是和距离成级数增加的，不适用于大规模复杂的环境，效率低。DFS方法的原理是按照一定的顺序先查找完一个分支，再查找另一个分支，直到找到目标节点。

A*算法与BFS和DFS不同，就在于选择下一步节点时，通过估值函数对节点进行评估，通过排序并选择代价最小的节点作为下一步搜索节点进行拓展，如果存在一个以上代价最小的节点，选择距离当前节点最近的一个节点，该方法避免了搜索的盲目性，提高了算法的搜索效率。估值函数如公式(1)所示。

f(n)=g(n)+h(n)

(1)

其中，f(n)为节点n的估值函数，g(n)表示从初始节点到当前节点n的实际代价，h(n)表示从节点n行进到目标节点的估算代价。

估价函数h(n)的选取决定了是否能找到最优路径，如果估价值h(n)的小于或等于当前节点 n 到目标节点的真实代价，将导致搜索范围大，算法效率低，但能得到最优路径。如果估价值大于实际代价，算法的搜索范围小，效率高，但不一定能找到最优路径。

A*算法 与广度优先和深度优先的联系在于，当g(n)=0时，改算法雷石榆DFS，当h(n)=0时，该算法类似于BFS；如果实际代价函数 g(n)远大于估算代价函数 h(n)，则启发式函数 h(n)没有作用，A*算法退化成了 Dijkstra 算法。

本文中，将起始节点与当前节点之间的距离作为实际代价函数，估计代价函数 h(n)的采用曼哈顿方法。估计代价函数如公式(2)所示。

h(n)=|nx-px|+|ny-py|

(2)

其中，nx、ny为当前节点的横、纵坐标，px、py为目标节点横、纵坐标。

(二)改进的A*算法

在 A*算法中，若搜索方向为 8 方向搜索，则路径中存在的转弯方向角只有 45°。因为转向存在时间，机器人路径规划整个系统中的最短路径不仅仅式路径的长度。改进的策略是在原有的 A*算法评价函数上加一项t(n)表示转向过程所需要的时间，根据新的评价函数判断路径中的单位栅格代价。改进 A*算法的评价函数如式(3)所示。

f(n)=g(n)+h(n)+t(n)

(3)

改进 A*算法的评价函数之后，在原有的评价函数中增加了新的约束条件，即机器人自身特性所限制的运动转向时间。整个路径的评价因素不再仅是距离的长短，而是整个系统运行的时间。

得到规划后初始路径为F，遍历F内的所有节点，当两个节点之间的连线中没有障碍物节点时，将连线中的节点设置为空结点，最终删除集合 F内的所有空节点，将非空节点依次连接得到最终的路径。

(三)改进的A*算法流程

A*算法需要维护开表和闭表。开表存放拓展节点的可通行的相邻节点，闭表存放已访问过的节点。选择开表中总代价 f 最小的那个节点作为拓展节点，不断的向周围拓展。算法的具体流程如下：

(1)初始化开表和闭表，将起始节点添加到开表中。

(2)将开表中f 最小的节点作为拓展节点。

(3)按照如下方式处理该节点相邻的8个方向的每个节点。①若该邻节点为障碍物，或者在闭表中存在，则不进行任何操作。②若开表中没有该邻节点，就将其加入到开表中，并计算出该节点的实际代价 g 和估计代价 h。③若开表中已经有了该相邻节点，则比较当前节点到达该相邻节点的估计代价 h 与原来的估计代价 h 之间的大小。如果当前节点的估计代价 h 小的话，那么设置当前节点为该相邻节点的父节点；否则，不进行任何操作。

(4)将当前节点从开表中删除，加入到闭表中。

(5)判断开表是否为空以及闭表中是否包含有目标结点。如果开表不为空并且闭表中不包含目标结点，则返回到步骤(2)；如果开表不为空且闭表中包含有目标结点，执行步骤(6)；如果开表为空，停止搜索。

(6)从目标结点沿着父节点遍历到起始节点，得到初始规划路径F。

(7)遍历初始路径F内的所有节点，若某个两个节点之间没有障碍物节点时，将中间节点置为空结点。

(8)将 F 中的所有空节点删除，依次连接剩余节点，得到最终的路径 Q。

四、实验结果及分析

本文提出的改进的 A*算法，对A*算法的评价函数改进，考虑了转向时间对整体路径规划的影响，并对规划后的路径进行了平滑处理，与传统 A*算法相比，采用改进的 A*算法规划出的路径长度和路径的转折角度有所减小，使得规划出的路径更优。