改进蚁群算法的移动机器人三维路径规划

李志锟

(1.广东科技学院 机电工程学院，广东 东莞 523083；2.安徽工程大学 高端装备先进感知与智能控制教育部重点实验室，安徽 芜湖 241005)

0 引言

科学技术的高速发展带来了移动机器人性能的不断提升，作为集成了动态决策与路径规划[1-5]、环境感知、可编程及模块可拓展等特点的移动机器人，其应用领域不断拓宽。比如农业、医疗服务、科学实验和空间探测等，这些领域的应用场景不局限于二维环境，而且大量应用于三维环境。移动机器人的种种应用也基本上都基于三维环境展开，因此，从未来的发展前景以及日常实用性角度出发，研究三维环境下的移动机器人路径规划具有十分重要的意义。

目前，由于在三维空间中，三维地图环境较为复杂，移动机器人可移动方向大幅增加，加上目前有关移动机器人路径规划的研究成果较少，因此，移动机器人在三维环境下的路径规划难度高于二维环境下的路径规划。据此，本文将研究移动机器人应用改进蚁群算法[6-13]的问题以及在三维环境下的路径规划问题。

移动机器人三维路径规划是指移动机器人在三维地图环境中寻找出一条从起始点到终点的最优路径[14-16]，所规划出的最优路径必须满足与所有障碍物安全无碰撞。目前，路径规划算法主要是基于二维地图环境运行，由于应用在三维地图环境下的路径规划算法信息量存储较大，同时要考虑三个维度导致计算复杂。因此，已有的三维路径规划算法较少，主要有：遗传算法、A*算法、蚁群算法等。蚁群算法具有分布计算、收敛速度相对较快的优势，非常适合移动机器人路径规划，通过对蚁群算法进行改进，不仅适用于移动机器人二维路径规划，而且适用于移动机器人三维路径规划。

1 三维环境的抽象建模

对移动机器人进行三维路径规划前，需要通过对三维地图构造出三维空间模型。模型构造方法：在三维地图中挑选合适的顶点作为坐标原点，对该坐标原点建立三维直角坐标系A-XYZ，A点为坐标原点，确定栅格地图的最大长度AB，最大宽度AD，最大高度AE，构造出了容纳三维地图的立方体ABCD-EFGH，如图1所示，将直角坐标系上的三维地图划分为独立的立方体，再对立方体栅格化为体积相等的小栅格。然后将三维地图空间沿着X轴方向进行等分，得到(n+1)个长方体，接着对(n+1)个长方体沿着Y轴方向进行m等分，得到了(n+1)×(m+1)个长方体；后沿着Z轴方向对三维地图空间进行l等分，得到了(n+1)×(m+1)×(l+1)个正方体，这些正方体就是组成三维地图的独立栅格。

图1 三维环境模型

利用以上三维地图的构建方法，三维地图的立方体区域ABCD-EFGH被切割成三维点集合，集合中的每一个点a都将拥有两个坐标,分别为序号坐标a(1)(i,j,k)(i=0,1,…，n;j=0,1,…,m;k=0,1,…,l)与位置坐标a(2)(xi,yi,zi)，其中：i是当前位置点a沿着AB方向的划分序号，j是当前位置点a沿着AD方向的划分序号，k是当前位置点a沿着AE方向的划分序号。令AB=h，则在三维地图环境下的任意一点p(i,j,k)与三维坐标A-XYZ中的点p(x,y,z)的对应关系如下：

2 三维环境下移动机器人路径规划

2.1 信息素更新策略

蚁群算法利用信息素的分布来吸引蚁群进行路径寻优，因此，信息素的初始化分布以及信息素的更新策略对于蚁群最终搜索到的最优路径至关重要。本研究已经介绍了如何将三维地图离散为一系列的三维栅格节点，这些三维栅格节点组成了蚁群算法可以移动的栅格集合。通过信息素的初始化，在蚁群搜索路径前，在每个三维栅格节点设定初始信息素值，经过一次迭代后，每个三维栅格节点进行信息素更新。

蚁群在路径寻优时，通过蚂蚁信息素的分泌起到正反馈作用，因此，在三维栅格节点合理分布初始信息素对于蚁群后期寻优至关重要。设定蚂蚁从起始点到终点移动时的方向所指向的区域为有利通行区域，增加该区域的信息素初始值，利用信息素的正反馈作用激励蚁群快速到达终点，设定初始信息素值为τ1，初始信息素不均匀分布公式为

(4)

其中：τ0为信息素初始值；C为大于1的常数；R为有利通行区域。根据三维地图的复杂程度，合理调整C值的大小，吸引蚁群朝向最优路径靠拢，既保证了蚁群的搜索效率，又兼顾了全局路径搜索的目的，有利于提高蚁群算法收敛速度。

通过全局信息素更新和局部信息素更新两种方式，实现改进信息素更新策略，当蚂蚁到达某个三维栅格时，通过降低该栅格的信息素值，增加蚂蚁搜索其他三维栅格的概率，达到全局路径搜索的目的。局部信息素随着蚂蚁的移动动态调整，局部信息素更新公式为

τijk=(1-ζ)τijk+τ1,

(5)

其中：τijk为三维栅格(i,j,k)上已有的信息素值；ζ为信息素值的衰减系数。

为了避免信息素值过高或过低，导致蚁群算法过快的收敛于非最优路径，限制信息素值τijk∈[τmin,τmax]。当蚂蚁从起始点到终点完成一次路径寻优时，筛选出所有最优路径，增加最优路径所涉及的三维栅格信息素值，全局信息素更新公式为

τijk=(1-ρ)τijk+ρΔτijk,

(6)

其中：l(m)表示第m只蚂蚁完成一次路径寻优所爬行的路径长度；ρ为信息素更新系数；K为常数。

2.2 多元化启发函数设计

蚁群算法利用启发函数计算可视区域内下一步可到达节点的概率，通过蚂蚁当前位置与终点位置的距离信息吸引蚂蚁选择最优路径。因此，启发函数的设计对于蚂蚁能否找到最优路径至关重要，设计后的启发函数为

H(i,j,k)=D(i,j,k)w1×S(i,j,k)w2×Q(i,j,k)w3,

(8)

其中：D(i,j,k)表示当前位置与下一步可到达节点位置之间的路径长度，其吸引蚂蚁选择可视区域内路径更短的节点位置；S(i,j,k)表示安全因素；Q(i,j,k)表示下一步到达节点距离终点的路径长度，其吸引蚂蚁向距离终点更近的节点移动；w1,w2,w3均为系数。

其中：a表示当前节点；b表示下一节点；d表示终点；N(i,j,k)代表点(i,j,k)拥有的所有可视节点的个数；UN(i,j,k)代表所有可视节点内不可到达区域的节点的个数。

2.3 蚁群搜索策略

三维空间环境下，蚂蚁可以选择的栅格节点大幅增加，蚁群算法的计算量也变得更复杂，蚁群从起始点到终点的路径寻优也变得更难，蚁群甚至在路径寻优中陷入死锁现象而无法找到最优路径。因此，对于蚁群在三维空间环境下的路径搜索，采取栅格平面和分层前行两种方案互相结合的搜索策略。如图2所示，Ps为蚂蚁出发的起始点，设定蚂蚁每次横向移动的最大距离为xmax，每次纵向移动的最大距离为ymax，则蚂蚁下一步可到达的栅格节点为一个可视区域，简化了蚁群的搜索空间。蚂蚁离开起始点ps后，将在第一个可视区域内找到可到达节点p1(x1,y1,z1)，离开节点p1后，将在第二个可视区域内找到可到达节点p2(x2,y2,z2)，蚂蚁每次离开当前节点位置后，都将在下一个可视区域内寻找可达到节点位置，直到搜索到终点pg，则蚁群算法的三维路径规划结束。

图2 三维环境搜索模式

蚂蚁从平面Pi上的节点pi搜索到下一平面Pi+1上的节点pi+1的步骤如下：首先，利用抽象环境找到平面Pi+1上蚂蚁可视区域内的所有节点的集合，其次，利用启发函数公式算出节点pi到平面Pi+1上蚂蚁可视区域内所有节点集合的启发信息值Ha+1,u,v，同时，计算出平面Pi+1上的任意一点(i+1,u,v)被选择的概率P(i+1,u,v)，其结果为

其中τ(a+1,u,v)表示平面Pi+1上的点p(a+1,u,v)的信息素值。最后，通过公式(12)计算出各点被选择的概率来确定下一个到达的节点。

2.4 算法流程

改进后的蚁群算法运行流程如图3所示。

图3 三维环境下蚁群算法流程图

三维路径寻优步骤如下：

步骤1：对蚁群所在的三维环境抽象建模，初始化信息素，信息素按照节点位置的重要程度不均匀分布；

步骤2：蚁群从起始点开始搜索路径，根据式(12)计算可视区域内到达各点的概率，确定蚂蚁下一步要到达的节点位置；

步骤3：蚂蚁在搜索路径时，进行局部信息素更新，当蚁群算法完成一次迭代后，更新全局信息素；

步骤4：蚁群算法达到最大迭代次数时，蚂蚁结束路径寻优，保存最优三维路径，当蚁群算法没有达到最大迭代次数，继续搜索路径；

步骤5：输出最优三维路径，结束蚁群算法。

为解决移动机器人在三维地图环境中寻找出一条从起始点到终点的最优路径问题，提出一种改进蚁群算法，将三维地图离散成一系列的三维栅格节点，这些三维栅格节点组成了蚁群算法可以移动的栅格集合，通过全局信息素更新和局部信息素更新两种方式，对栅格集合实现改进信息素更新策略，设计多元化启发函数，吸引蚁群选择最优路径，提高算法的收敛速度。

3 实验与结果

本研究对改进蚁群算法以及传统蚁群算法分别进行仿真实验并作对比分析，两次实验的三维地图环境保持一致，起始点坐标均为(1,3,1)，终点坐标均为(21,10,10)，蚂蚁数量取值为100，蚁群算法的最大迭代次数取值为100，对两种算法分别运行3次，选择其中最佳实验结果。传统蚁群算法的三维路径轨迹如图4所示，改进蚁群算法的三维路径轨迹如图5所示，传统蚁群算法、改进蚁群算法的收敛曲线图分别如图6和图7所示。

图4 传统蚁群算法三维路径轨迹 图5 改进蚁群算法三维路径轨迹

图6 传统蚁群算法收敛曲线 图7 改进蚁群算法收敛曲线

实验结果显示，应用传统蚁群算法进行三维路径寻优搜索的最优路径长度为77.78 m，应用本文改进蚁群算法进行三维路径寻优搜索的最优路径长度为71.36 m，改进蚁群算法在搜索最优路径长度方面相比于传统蚁群算法提高了8.3%；改进蚁群算法迭代16次搜索到全局最优路径，同时达到稳定状态，传统蚁群算法迭代44次搜索到最优路径，同时达到稳定状态，在收敛速度方面，改进蚁群算法比传统蚁群算法提高了63.7%。以上数据表明，本文改进蚁群算法要明显优于传统蚁群算法，能更快更稳定的完成三维路径规划。

4 结论

本研究通过分析传统蚁群算法的不足，对该蚁群算法进行改进。首先，通过对三维空间环境进行建模，改进信息素更新策略，利用初始化信息素的不均匀分布，吸引蚁群每次搜索路径时优先选择距离终点更近的栅格位置。然后采用信息素全局更新及局部更新两种方式，达到全局路径搜索的目的。最后通过多元启发函数计算出蚂蚁选择三维可视区域内各点的概率，促进蚂蚁能完成起点到终点的路径搜索，提高算法收敛速度。在三维空间下进行传统蚁群算法与改进蚁群算法的仿真实验并作对比分析，结果显示，改进后的蚁群算法在路径搜索速度方面及最优路径轨迹方面均优于传统蚁群算法。

(责任编辑：潘姝静)