基于改进蚁群算法的机器人三维空间路径规划*

张文强，张 彦

(合肥工业大学 机械工程学院，合肥 230009)

0 引言

无碰撞路径规划也称为避障路径规划，是轨迹规划问题的一个重要组成部分，也是研究轨迹规划问题的前提[1]。机器人的无碰撞路径规划是指：在一个存在已知或未知障碍物的环境中，机器人通过相应算法能够获得一条从出发点到目标点的路径，该路径能够避开所有障碍物并满足一定的限制条件[2]。

三维路径规划是指在已知三维地图中，规划出一条从出发点到目标点并避开所有障碍物的最优路径。现有的路径规划算法例如人工势场法、模拟退火法等[3-5]多用于二维平面规划空间，该类问题处理起来较为简单。而进行一般的三维路径规划时，往往要面对数据存储量大、运算过程长、进行全局规划复杂等问题。现有的三维路径规划算法主要有A*算法、遗传算法、粒子群算法等[6-9]，但其中A*算法的计算量会随着搜索维数的增加而急剧加大，遗传算法和粒子群算法只能进行准三维空间的路径规划。针对本文所研究的问题，采用蚁群算法[10-12]较为适用，但原始的蚁群算法仍然存在着对待复杂环境灵活性不足、容易在障碍物表面反复震荡而影响收敛速度等缺点。

本文提出了一种结合人工势场思想的改进蚁群算法，结合了人工势场法和蚁群算法的优势，可以规避或在一定程度上降低两种算法的不足，使其可以更好的应用于三维空间中的无碰撞路径规划问题。

1 原始蚁群算法基本概述

本文提出的结合人工势场思想的改进蚁群算法是以蚁群算法为主体的一种改进算法，因此本节先对原始蚁群算法的概念进行简单介绍，以方便在下文中对改进方法及仿真结果进行说明和对比。

1.1 三维搜索空间

图1 规划空间示意图

三维路径规划算法首先需要从真实三维空间中抽象出三维空间模型，其方法如下：首先将地图左下角顶点作为三维坐标的原点A，以此为基准建立三维坐标系，x轴为纵向增加方向，y轴为横向增加方向，z轴为高度增加方向。沿x方向取长度AB，沿y轴方向取长度AD，沿z轴方向取长度AA′，这样就构成了一个三维空间ABCD—A′B′C′D′,该区域即为三维路径规划空间，如图1所示。

三维路径空间建立之后，采用等分空间法从三维规划空间中抽取路径规划所需的网格点。

首先沿着边AB将规划空间ABCD—A′B′C′D′分为n等分，得到n+1个分层面，接着对n+1个分层面沿边AB进行m等分，沿边AA′进行l等分，并求解出里面的交点。这样规划空间就离散化为一个三维点集合，蚁群算法即在这些三维路径点上进行规划。

1.2 分层前进原则与可达域

图2 空间分层及可视域示意图

在实际应用中，蚁群算法能够很好地解决二维路径规划问题，这是因为在二维空间中对节点的选择较为简单。而在三维空间中，由于选择范围的扩大，往往会造成所选路径局限在几个启发值较高的节点往复震荡，如不能较快地跳出这个陷阱会造成收敛速度的降低甚至算法的失效。为应对这个问题，在算法中采取了一种分层前进的原则，其思想是：选定从起点到终点的方向为前进方向，以该方向上以单位距离划分层次，以当前节点所在平面为基准，建立可达域，所选节点全部出自下一平面的可达区域内。图2为其示意图。

1.3 信息素系数

信息素概念是蚁群算法的核心概念，蚁群算法通过信息素的浓度对节点进行寻优。将搜索空间离散为一系列三维离散点，这些离散点就是算法所需要搜索的点，这里将信息素的值赋予在每个离散点中，这样每一点的信息素值就是一个关于坐标的函数，将其命名为信息素系数I(P)。该函数值由待选节点上的信息素浓度决定，信息素浓度越高证明之前经过的蚂蚁数越多。在算法具体运行过程中信息素是随时更新的，这里包括局部更新和全局更新。

局部更新是指当蚂蚁经过某一节点时，令该点信息素获得较大的衰减，从而保证后续的蚂蚁可以寻访其他节点，避免陷于局部最优，从而达到全局搜索的目的。其公式为：

τP=(1-ζ)τP

(1)

τP是点(i,j,k)上的信息素值，ζ为信息素衰减系数。

全局更新是指在放出的一批蚂蚁完成了一条路径的搜索后，根据评价函数找出最短路径并增加该路径上的节点的信息素值。其表达式为：

(2)

其中，ρ为全局信息素更新系数；K为信息素增长系数；min(l)为该批次蚂蚁所寻得最短路径。

1.4 最佳个体适应度

最佳个体适应度是体现结果优化程度的指标。在该算法中以路径的总长度为优化准则，每完成一次搜索，都会用评价函数计算路径的总长度并记录下来。这里将记录的最短路径数据称为最佳个体适应度。评价函数的计算公式为：

(3)

1.5 原始蚁群算法流程

根据蚁群算法的思想，实现其功能的流程如图3所示。

图3 原始蚁群算法流程图

2 算法改进方案

当蚂蚁从当前点向下一点移动时，需要对下一点进行选择，在原始算法中选择节点的依据是由信息素系数单方面决定的，在实际应用中该系数波动较大，会造成收敛速度慢、易于落入局部最优等问题。为改进上述不足，在改进算法中引入结合人工势场法思想的启发函数，该启发函数将与信息素系数共同作用来对节点进行选择。

2.1 启发函数

针对节点选择的启发函数的表达式为：

H(P)=D(P)z1·G(P)z2·S(P)z3

(4)

式中，D(P)为当前点与待选点间的距离，其计算公式如下：

(5)

a为当前点，b为待选节点。由式可知两点间距离越小则函数值越大，通过该式可令蚂蚁优先选择较近的点。

G(P)和S(P)分别引力系数和避障系数。z1,z2,z3为权重系数，分别代表各因素的重要程度。

2.2 引力系数及避障系数

在人工势场理论中，目标点对机器人末端执行器有一个虚拟的引力势，本文在改进蚁群算法中将其功能转化为另一种形式，即G(P)，并称G(P)为引力系数，其表达式为：

(6)

其中，P代表节点空间坐标，b为待选节点，d为最终目标点。其含义是在待选节点中，距离终点最近的点可得到更高的引力系数，从而影响该点的启发值，获得更高的选择概率。

同理，将人工势场理论中的斥力势概念转化为避障系数，用于判断下一点是否可达，其表达式如下：

(7)

式中,d0为避障极限距离，dm为斥力作用距离，d为待选节点与障碍物距离，h为避障系数最大值。当d小于d0时，S(P)取值为0，使该节点无法被选取。当d位于d0与dm之间时，可根据公式计算该节点的避障系数。当d大于dm时，节点不受斥力势影响，避障系数取最大值h。

2.3 节点选择概率函数

在蚁群算法中引入人工势场方法，得到的改进节点选择概率函数形式为：

(8)

式中，C代表规划空间的可行区域，α、β分别代表启发函数与信息素系数的权重。

2.4 改进蚁群算法流程

实现改进后的蚁群算法功能的流程如图4所示。

图4 改进蚁群算法流程图

3 算法仿真及结果分析

在机器人的工作空间中抽取三维空间ABCD—A′B′C′D′作为路径规划空间，对空间进行离散化，置入虚拟障碍并对障碍物进行包裹处理，最终得到的规划空间如图5所示。对算法的仿真分析都将在该空间中进行。

图5 三维规划空间

为验证在算法中引入引力系数和避障系数所起的作用，下面分别利用原始蚁群算法和改进后的蚁群算法以相同的初始条件进行仿真，并对结果做对比分析。算法仿真的初始条件如表1所示。

表1 仿真初始条件

经过程序运算，得到仿真路径规划结果，三维空间路径如图6所示，图7为最佳个体适应度变化趋势图，图中虚线为原始算法，实线为改进算法。

图6 三维空间路径规划结果

图7 最佳个体适应度变化

通过观察三维空间路径的搜索结果可知，原始算法和改进算法搜索到的路径均满足避障要求，但可以明显看到原始算法得到的路径较为曲折，而改进算法得到的路径要光滑许多。这是因为在启发函数中引入引力系数令路径节点的选择更具有目的性，使每次的选择都更加接近目标点，而斥力系数的引入令路径更有效地避开障碍物防止路径在障碍物附近震荡。通过对比最佳个体适应度变化趋势可以看到改进算法在迭代初期就已获得适应度在30以下的路径，并随迭代次数增加获得了更优的路径；而原始算法的适应度从35

左右开始，经过迭代虽有所下降，但在迭代200次之后仍高于改进算法，这说明通过对原始算法的改进，可令算法达到更快的收敛速度。

4 结论

为了提高进行路径规划时的收敛效率和增加面对复杂规划空间的灵活性，本文对机器人的无碰撞路径规划问题进行了探讨，并提出了一种结合人工势场思想的改进蚁群算法。

针对原始蚁群算法在复杂环境中收敛速度慢以及可能陷入局部最优陷阱而导致收敛失败的问题，改进后的算法在启发函数的设计中，引入了具有人工势场思想的引力系数和避障系数，以提高算法的搜索效率和收敛速度，使其更加适合于复杂规划空间。通过仿真及其结果分析表明，该改进算法比原始蚁群算法能更快地搜索到更优的解。该算法的提出可以为三维空间中的无碰撞路径规划提供一种快速而有效地解决问题的新方法。

[参考文献]

[1] FANG H C, ONG S K, NEE A Y C. Interactive robot trajectory planning and simulation using Augmented Reality[J]. Robotics and Computer-Integrated Manufacturing, 2012, 28(2):227-237.

[2] 史峰, 王辉, 郁磊, 等. MATLAB智能算法30个案例分析 [M].2版.北京：北京航空航天大学出版社,2015.

[3] 王肖青, 王奇志. 传统人工势场的改进[J]. 计算机技术与发展, 2006, 16(4):96-98.

[4] 丁家如, 杜昌平, 赵耀,等. 基于改进人工势场法的无人机路径规划算法[J]. 计算机应用, 2016, 36(1):287-290.

[5] 徐飞. 基于改进人工势场法的机器人避障及路径规划研究[J]. 计算机科学, 2016, 43(12):293-296.

[6] 毕慧敏, 董海鹰. 改进遗传算法在机器人路径规划中的应用[J]. 兵工自动化, 2006, 25(4):53-54.

[7] LI Q, ZHANG W, YIN Y, et al. An Improved Genetic Algorithm of Optimum Path Planning for Mobile Robots[C]// Intelligent Systems Design and Applications, 2006. ISDA ′06. Sixth International Conference on IEEE, 2006:637-642.

[8] 龙传泽, 杨煜俊. 基于遗传算法的柔性机器人制造单元调度问题研究[J]. 组合机床与自动化加工技术, 2015(11):141-144.

[9] 林惠乐, 黄振峰, 毛汉领. 基于遗传神经网络的机器人焊接工艺参数优化[J]. 组合机床与自动化加工技术, 2015(10):124-127.

[10] SONG H, WANG D. Path Planning for Mobile Robot Based on Modified Ant Colony Optimization[J]. Machine Tool & Hydraulics, 2012.

[11] 李擎, 张超, 陈鹏,等. 一种基于粒子群参数优化的改进蚁群算法[J]. 控制与决策, 2013,28(6):873-878.

[12] 曹宗华, 吴斌, 黄玉清,等. 基于改进蚁群算法的多机器人任务分配[J]. 组合机床与自动化加工技术, 2013(2):34-37.