移动机器人全局路径规划算法的研究

黄 静，陈汉伟

(浙江理工大学信息学院，浙江杭州 310018)

0 引言

目前，移移动机器人普遍存在行动机械、决策迟钝的问题，无法真正实现模拟自然环境中生物体的行为模式。因此，如何使这些移动机器人拥有较为真实的行为能力成为一个研究热点。全局路径规划是移动机器人要解决的重要问题之一[1]，作用是移动机器人在已知错综复杂的地形的状况下，找到一条到目标位置较优的路径，不仅能够有效避开障碍，而且时间开销较短。由于特殊地形、障碍、多角色实时移动等因素，使路径规划变得十分复杂。优秀的路径规划方法不仅可以让移动机器人的行为让用户看起来更加智能，而且能够节约大量的运算时间。

如图1所示，尽管两条路径的长度相同，图1(b)模型显然更符合现实中智能体的移动规律。

(a)路径一

(b)路径二图1无障碍普通路径规划示意图

文中针对移动机器人智能化中的路径规划问题，着重研究了盲目式搜索算法、A*算法和遗传算法，使用A*算法在Unity平台上实现移动机器人的路径规划模块，旨在提高路径搜索的效率，提升移动机器人的真实感。

1 路径规划算法的研究与分析

1.1 盲目式搜索算法

深度优先搜索算法(Deep First Search, DFS)和广度优先搜索算法(Breadth First Search, BFS)是两种常见的搜索算法[2]。

DFS沿着树的深度遍历地图中的节点，尽可能深地搜索分支节点。当一个节点i的所有子节点都已被探寻过，搜索将回溯到发现节点i的那条边的起始节点。如果并没有搜索到目标节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到发现目标节点为止。深度优先算法找到的路径通常不是最短或最有效的路径，在场景地形复杂、障碍物繁多的情况下，搜索到的路线常常偏离目标方向，具有一定的盲目性，搜索的过程也缺乏移动机器人应有的智能性。图2为深度优先搜索的示意图。

BFS则是从起始节点开始，先访问起始节点的所有子节点，再访问子节点的所有子节点，直到搜索到目标节点为止。这种搜索方式可以搜索到最短的路径，但是算法本身消耗的时间根本无法满足移动机器人决策模块对实时性的要求。图3为广度优先搜索的示意图。

使用C/C++实现DFS和BFS搜索算法，解决一个20×20的矩阵中的路径搜索问题，起始点为点[3,3]，搜索目标点为点DFS和BFS都是盲目式搜索算法，算法进行搜索的时候，不会对节点进行评估，且跳转到最优结点进行下一步的搜索。当搜索状态最为糟糕的时候，算法很可能需要搜索整个地图空间才能得出所需的路径。显然，这类盲目型搜索算法只能适用于解决规模不大的搜索问题。

图2 DFS示意图

图3 BFS示意图

[17,17]，结果如图4和图5所示。实验结果证明，DFS的搜索路径十分地盲目，完全不符合智能体的决策行为，而BFS能够更为有效地搜索到最短路径，路径较真实，但时间消耗较大。

图4 DFS路径搜索的实现

图5 BFS路径搜索的实现

1.2 A*算法

不同于DFS和BFS等传统的盲目式搜索算法，启发式搜索算法在从一个节点向下一个节点搜索时，会引入一个启发函数，这个启发函数为每一个子节点进行评估，选择子节点中评估值最低的节点作为路径的节点。优秀的启发函数可以迅速地搜索到路径规划问题中的最优路径。A*算法是启发式搜索中比较有效的方法[3]，常用于解决最优路径问题及其他一些策略性问题。

在路径规划过程中，A*算法会引入一些具有启发意义的信息，这些信息能够引导算法发现有效的路径。算法通常使用一个启发函数表示这些信息，在搜索的过程中使用启发函数对路径规划中的搜索位置进行评估，选取评估值最低的节点作为路径节点，并从这个节点再次进行进一步搜索，直到目标节点被搜索到，完成整个搜索过程。A*算法避免了路径规划问题中常常产生的大量无效搜索路径，相对于盲目式搜索，提高了算法本身的搜索效率。

A*算法中最重要的就是算法的启发函数：

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

(1)

式中：f(n)是路径中每个可能搜索节点的评估值，由两部分组成：g(n)表示从起始节点到当前节点的评估值；h(n)表示当前节点到目标节点的评估值，h(n)的优劣会直接影响算法的性能，也决定了算法是否能够被定义为A*算法。

如果要将启发式搜索算法定义为A*算法，需要保证路径规划问题中存在着从起始节点到目标节点的最优路径，而且路径中所有节点的评估值都大于零。此外，h(n)需要尽量地接近路径规划问题的实际评估值h*(n)。

路径规划问题存在解、节点评估值大于零，这些条件都比较容易满足，但是如果要满足h(n)接近实际评估值就需要进行有效的设计。A*算法中的h(n)和h*(n)相差不能过大[4-5]，过小的h(n)会使整个算法的区分能力减弱，从而使算法的效率降低。优秀的h(n)应该尽量逼近h*(n)，但是始终小于h*(n)[6-7]。这种设计不仅可以增加启发信息，还能减少搜索过程中需要探索的节点数，从而有效提高算法的搜索速度。

和盲目式搜索算法相比，A*算法搜索时探索的节点要少很多，而且路径的效果较好，如图6所示。

图6 A*搜索算法的实现

1.3 遗传算法

遗传算法是一种模拟自然选择和遗传机制的随机搜索算法[8-9]。遗传算法模拟生物遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从种群中选取较优的个体，利用遗传算子进行选择、交叉和变异，对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足预置收敛指标为止。

基本过程如下：

(1)初始化。确定种群规模N、交叉概率Pc、变异概率Pm和置终止进化准则；随机生成个体数量为N的种群作为初始种群Population(t)；种群代数t=0。

(2)个体评价。计算或估价Population(t)中各个体的适应度。

(3)种群进化。

①选择亲代染色体。从Population(t)中运用选择算子选择出M/2对染色体(M≥N)。

②交叉。对所选择的M/2对染色体，根据Pc的概率执行交叉形成M个临时个体。

③变异。M个临时个体都有Pm的几率发生变异，形成M个候选个体。

④选择子代染色体。从上述所形成的M个候选个体中根据适应度选择出N个个体组成新一代种群Population(t+1)。

(4)终止检验。如果已经满足终止的条件，则输出Population(t+1)中具有最大适应度的个体作为最优解，终止计算；否则置t=t+1并转至步骤(3)。

在智能体的路径规划中，文中将四个搜索动作编码为二进制码，如表1所示。

表1 遗传算法二进制编码

由表1中编码组成的二进制序列，如00100111，就是遗传算法在解决路径规划时的一个染色体。若要评估这条染色体的适应度，则从起始点开始，根据染色体中的编码进行搜索。若其中的一个编码使本次搜索遇到了障碍，则忽略该编码，使用下一个编码继续搜索，直到历遍所有编码或者抵达目标位置。适应度fitness由这次搜索的最终位置距离目标位置的距离d给出：

(2)

图7、图8为使用遗传算法进行路径搜索的实验结果。从图中易知，遗传算法能够有效地搜索到目标位置，且规划的路径较符合自然环境中智慧生物的决策行为。然而，随着地图面积的增大，遗传算法在解决此类问题时就需要增长染色体的长度，增加种群的规模，因此算法的计算量往往变得十分庞大，这显然无法满足移动机器人的高实时性需求[10]。当虚拟场景的地图较大，起始位置和目标位置相聚较远时，遗传算法并不是最合适的路径规划算法。

图7 进化4次后的路径

图8 进化11次后的路径

1.4 算法总体分析

盲目式的搜索算法不仅运算时间长，而且搜索得到的路径真实性差；遗传算法得到的路径较符合现实中智能体的路径选择方式，但运算量大，耗时长，无法满足实时性要求；启发式的搜索算法能够有效利用路径中的启发信息，搜索得到的路径真实，运算效率较好。A*算法能够有效解决传统虚拟环境路径搜索算法造成的避障不及时，原地徘徊等移动机器人反应不灵活等问题，而且效率较好。

2 A*路径规划的应用及其优化

本文利用Unity平台[11-12]虚拟移动机器人路径规划模块，针对移动机器人行动迟钝，行动时模型重叠等问题，选取最适用于移动机器人路径规划的A*算法设计移动机器人的路径规划模块，并且使用贪婪平滑算法进行优化，旨在使虚拟移动机器人能够灵活避开障碍。

A*算法需要维持两张列表：存放未评估节点的Open表和存放已评估节点的Closed表，具体实现方式如下：

(1)把起始节点添加到Open表。

(2)考察Open表

①如果Open表中的元素为空，则表示搜索失败；寻找Open表中f(n)值最低的节点作为当前的搜索节点，并把它移入Closed表中。

②如果当前点为终点，则路径规划成功，转骤(4)。

(3) 对相邻的上下左右4个方向的每个节点进行如下操作。

①如果该节点不可访问，或者已经存在于Closed表中，忽略该节点。

②如果该节点不在Open表中，把它添加进去，并记录它的f(n)、g(n)和h(n)值。

③如果该节点已经在Open表中，用f(n)值作为参考检查新的路径是否更好，即有更低的f(n)值，并且重新计算该点的f(n)值。

④ 如果所有方向都已搜索完毕，则转向骤(2)；否则，转向步骤(3)。

(4) 保存路径，根据Closed表中的节点信息，进行逆向提取，便能够得到一条从起始节点到目标节点的路径。

场景中的小型圆柱体需要需找一条从A点到达B点，并且能绕过障碍物的有效路径。场景设计如图9所示，路径搜索的实验结果如图10所示。实验结果表明，A*算法能够有效地避开路径中的障碍物抵达目标，而且能够满足决策模块对实时性要求。

图9 实验场景设计

(a) 障碍一

(b) 障碍二图10 在不同障碍场景中的路径搜索结果

然而，从实验结果也容易发现，A*算法搜索产生的路径存在一些多余路径，这是由于算法的启发函数并不一直最佳。因此，需要对A*算法得到的路径进行优化。在规划路径的过程中，如果相邻的两条直线路径之间没有障碍物，就使用一条路径代替这两条路径。

文中采用贪婪平滑算法改进A*算法[13-14]规划生成的路径。将A*生成的路径按下列步骤进行平滑：

(1)将路径中的第一点作为贪婪平滑算法的起点；

(2)如果路径中从起点开始后续没有连续的3个点，则转到步骤(4)；否则每次从路径当前起点开始连续取3个点，分别为记为a，b，c，如果ac直线路径上没有障碍并且ac长度小于ab长度加上bc长度，则在路径中删除b点，保持起点不变，重新执行步骤(2)；否则执行步骤(3)；

(3)将起点的下一点作为新的计算起点，转到步骤(2)执行；

(4)路径剩余的点就是平滑后的新路径。

算法优化前后的效果如图11和图12所示。

图11 普通A*算法的路径图

图12 优化后的A*算法的路径

通过贪婪平滑算法改进的A*算法，能够使移动机器人的行动路径更加接近真实智慧生命体的路径选择方式，并且依然居然较好的算法执行效率。

3 结论

文中基于Unity3D平台，针对移动机器人智能化中的全局路径规划问题，研究了盲目式搜索算法、遗传算法和A*算法的优劣：遗传算法虽然够有效地搜索到目标位置，但并不适合地图场景较大的情况；使用A*算法实现移动机器人的路径规划模块，相比传统的盲目搜索算法，能够有效寻找当前位置到目标位置成本最小的路径，然而实验结果表明，A*算法的启发函数并不总是最佳的，路径搜索过程中会产生一些拐角或者其他形式的多余路径，需要进行路径优化。文中利用贪婪平滑算法对A*算法进行优化，算法效率较好，移动机器人的智能性较强。

参考文献：

[1] 王丽. 移动机器人路径规划方法研究：[学位论文]. 西安: 西北工业大学, 2007.

[2] 曲道奎,杜振军,徐殿国,等. 移动机器人路径规划方法研究. 机器人, 2008(2): 97-101.

[3] 史辉, 曹闻, 朱述龙，等. A*算法的改进及其在路径规划中的应用. 测绘与空间地理信息, 2009(6): 208-211.

[4] 陈刚, 付少锋, 周利华. A*算法在游戏地图寻径中的几种改进策略研究. 科学技术与工程, 2007(15): 3731-3736.

[5] 邱磊. 基于A～*算法的游戏地图寻路实现及性能比较. 陕西科技大学学报(自然科学版), 2011(6): 89-93.

[6] 王红卫, 马勇, 谢勇，等. 基于平滑A*算法的移动机器人路径规划. 同济大学学报(自然科学版), 2010, (11): 1647-1650.

[7] 刘浩, 鲍远律. A*算法在矢量地图最优路径搜索中的应用. 计算机仿真, 2008(4): 253-257.

[8] 陈华华,杜歆,顾伟康. 基于遗传算法的静态环境全局路径规划. 浙江大学学报(理学版), 2005(1): 49-53.

[9] 马永杰, 云文霞. 遗传算法研究进展. 计算机应用研究, 2012(4): 1201-1206.

[10] 唐文艳. 结构优化中的遗传算法研究和应用：[学位论文].大连：大连理工大学, 2002.

[11] 陈俊锋. 基于Unity3D的跨平台手机网络游戏的研究与实现：[学位论文]. 广州：中山大学, 2013.

[12] 郑磊. 基于三维网页技术的Unity3D教学管理系统的设计与实现：[学位论文]. 上海：上海交通大学, 2013.

[13] ZHANG Z Y，ZHAO Z P. A multiple mobile robots path planning algorithm based on a-star and dijkstra algorithm．International Journal of Smart Home, 2014, 8(3)：75-86.

[14] LI J，SUN X X. Route planning's method for unmanned aerial vehicles based on improved a-star algorithm. Acta Armamentarii, 2008, 29(7), 788-792