改进型蚁群算法在多关节机器人捕捉路径规划上的应用

王江华，赵 燕

(1.华北科技学院 电子信息工程学院，河北 三河 065201； 2.燕京理工学院 信息科学与技术学院，河北 三河 065201)

改进型蚁群算法在多关节机器人捕捉路径规划上的应用

王江华1，赵 燕2

(1.华北科技学院 电子信息工程学院，河北 三河 065201； 2.燕京理工学院 信息科学与技术学院，河北 三河 065201)

针对狭窄空间中机械臂的路径规划问题，提出一种改进型蚁群优化算法应用于机械臂的路径规划。通过对传统蚁群算法从概率分布的计算、最优路径二次优化、路径淘汰机制等方面进行改进，并使用Matlab软件进行仿真。对比改进前后算法的收敛效果，发现改进型蚁群算法的自组织性大大增强了系统的鲁棒性，能够明显提高机械臂在矿井等复杂环境下的适应能力。

机械臂； 路径规划； 蚁群优化算法； 自组织性

0 引 言

随着工业3.0的普及和人工智能的发展，机器人已经在结构化的工厂环境中得以灵活应用。在工业领域，机器人主要以机械臂的形式出现，并作为提升工作效率的利器被许多自动化生产线所广泛应用，尤其像工矿企业，工作重复度较高且工作环境恶劣，完全可以使用机械臂替代传统人工劳动力。在对机械臂的优化控制以及路径规划方面，近年来出现过很多算法，例如传统的栅格法、人工势场法，以及近几年出现的一些仿生学算法，包括遗传算法、蚁群算法等。本文提出一种改进型蚁群算法，应用于多关节机械臂的路径规划中，利用蚁群算法的自组织能力以及较强的鲁棒性，提高机械臂在复杂环境下工作的适应能力。

1 蚁群优化算法

1.1蚁群优化算法的基本原理

蚁群优化算法(ACO)是一种基于种群的启发式仿生进化系统[1]。在蚂蚁觅食过程中，依靠觅食的蚂蚁在寻找食物过程中散发的信息素来引导其他蚂蚁对路径的选择，选择过程可用下式描述[2]：

(1)

通过信息素聚集与挥发的反馈作用实现信息素的更新，以此来区分不同优劣程度的路径，最终使得蚂蚁都能够沿着一条最优的路径到达食物所在处，其更新过程可用下式描述：

(2)

(3)

1.2ACO在机械臂路径规划中存在的问题

经过仿真实验，机械臂在传统蚁群算法的引导下，并不能快速到达目标点。经过反复对比总结，原因在于机械臂的路径规划中最初只知道2个点的初、末位置，且其不确定性较大。同时，ACO是根据全局信息素来选择道路，在初始状态下各道路信息素浓度一致，在蚂蚁遍历过程中，逐渐淘汰信息素低的路径，对新道路的试探性较低，这样就会使得算法陷入局部最优解的情况。故不能直接将ACO应用到机械臂的路径规划中，需要对基本ACO做一些调整[4-5]。

2 ACO的改进

ACO主要改进的流程：①计算概率分布的改进。结合道路选择概率、转移概率，根据不同状态下蚁群系统的不同状态进行动态融合两种概率，以配置蚂蚁的道路选择概率[6]。②路径优化改进。通过蚂蚁淘汰制的应用以及优势蚂蚁最短路径的保存，加速蚁群系统的收敛速度达到加速算法的目的。

2.1计算概率分布的改进

在机械臂的路径规划中，由于只知道起点与终点，不确定性因素较大，依靠原有的转移概率，只能在路径交叉点处，依靠信息启发因子和期望启发因子对路径进行选择[7]。期望启发因子ηij一般采用：

ηij=1/dij

其中：dij表示相邻两个城市之间的距离，是固定的量，仅能够表示局部道路的情况。信息启发因子虽有一定的全局效果，但是只有在正确的正反馈前提下才能够发挥真正的作用。

(4)

式中：W(i)表示点i周围可选择点的集合，算法中人工蚂蚁可以向前后左右、左上左下、右上右下8个方向活动，因此W(i)中i≤8；distence(j,end)指点j到终点end的距离。由于相邻格点距离差较小，故通过参数匹配，使用ω、μ、λ将其差距扩大，设定ω=10=μ=2=λ=2。

Pnewij=(1-ρh)Pij+ρhPhij

(5)

随着蚂蚁路径的逐渐收敛，地图中的信息素差异性增大，故在一定时间后可逐步增加距离导向概率的融合比ρh，使得蚂蚁能更加有目的的选择路径，从而加快蚁群的收敛速度，进而加速算法的执行速度。

2.2路径优化改进

2.2.1最优路径二次优化

为避免蚁群在寻找最优路径中陷入“死胡同”，在算法运行之前，可将蚁群运行环境进行人为调整，将路障图中的自然死路的路口进行封闭。以此减小算法的失误率。在算法执行过程中不仅在地图初始化过程中需要人工对地图凸化处理，在每次迭代中产生的优秀路线也需要进行处理，化曲为直，并将优秀路线引入到下一代的蚁群运行中[10]。优化路线化曲为直，首先判断是否存在凹陷路线并查找路径Path1数组，Path1数组用下式描述：

(6)

判断该点附近的可到达点Iwt，是否在数组Path1中，若存在修正点Iwt，则舍去Path1数组中该点与当前点的中间点，并将当前点Path1和修正点Iwt保存于优化路径中，以达到修正路线的目的。最后将修正路线保存并移入下一次迭代指导算法的发展方向。

2.2.2路径淘汰机制

在蚁群算法的路径处理中，设置“路径淘汰制”，当有蚂蚁在行走中已经进入“死胡同”，没有道路可走时，自动放弃该蚂蚁的路径，所经过路径不进行信息素的更新。该种方法使得每次迭代只需对部分蚂蚁路径进行信息素更新，降低计算量，同时也削弱了路径质量较差的蚂蚁对蚁群系统的影响[11]。

2.3改进的ACO

改进的ACO实现过程如下[12-13]：

(1) 初始化蚁群参数。信息素τ，定义最大迭代次数Kmax，设定机械臂起始点S、终止点E，设置启发因子α与期望启发因子β以及信息素挥发系数ρ与启发函数η。

(2) 迭代循环K=K+1。

(3) 蚂蚁编号m=m+1。

(4) 初始化地形图矩阵，计算邻接矩阵相关距离矩阵，并进行凸化处理。

(5) 设置m只蚂蚁从起点S出发，采用路径淘汰原则进行探索，并计算每只蚂蚁的道路选择概率。

(6) 结合道路选择概率、转移概率以及迭代分配比，计算蚂蚁的路径选择概率。

(7) 是否到达目的地？是则执行(8)，否则跳转到(3)。

(8) 记录蚂蚁路线和长度，保留优秀蚂蚁，保存到下一次迭代。采用式(5)对路径进行优化，同时执行(3)。

(9) 根据式(1)、(4)，更新地图中的信息素。

(10) 是否达到最大迭代次数Kmax，若达到则执行(11)，否则跳转到(2)。

(11) 循环结束，绘制最优路径图、误差曲线图以及各代路径图。

3 仿真实验与分析

3.1仿真环境搭建

为了检验改进算法使机械臂在井下复杂狭窄环境中的适应性，在Matlab中使用栅格法模拟井下狭窄空间内的障碍分布情况，如图1所示[14]。栅格障碍地图中白色方块为可通过路径，黑色方块为抽象障碍，将改进型蚁群算法应用于路径规划。设置地图中的起点(即机械臂的位置)和终点(即所要捕捉的物体)，蚁群从起点出发，通过路径规划寻出一条到达终点的最优路线。设定蚂蚁个数m=15，期望启发因子β=7，启发式因子α=1，信息素蒸发系数ρ=0.3。

图1 栅格障碍仿真地图

3.2实验结果分析

由各代蚂蚁路径图2可看出，蚁群对地图中区域路径都进行过尝试，所选择的路径具有一定的全局优秀特征。在路径图中也可以看见有许多路径并未到达终点便中途截止，可以看出，算法中淘汰制的有效应用[15]。从收敛曲线图3中可以看出，改进型算法通过优势种群的传递以及距离导向概率的引入再加上动态的概率选择，使得整个算法在第40次迭代后基本收敛，即已经搜寻到全局最优路线。

图2 各代蚂蚁路径图

3.3ACO路径规划

在矿井的狭小环境下，机械臂可沿图4所示路径对目标物体进行抓取。原始算法与改进算法所得最优规划路径见图4。

图3 收敛曲线图

(a) 改进算法

经过多次重复取点实验，所得原始算法与改进算法的最优路径与执行时间如表1所示。

表1 原始算法与改进算法的最优路径与执行时间表

4 结 语

传统蚁群算法仅通过启发因子α和期望启发因子β控制蚂蚁的道路选择方向，在对机械臂路径规划应用中极容易陷入局部最优，并且由于算法的自组织性，使得系统需要一个较长时间的演化过程。本文针对ACO易陷入局部最优解以及算法的执行时间较长的缺陷，使用融合型道路选择概率、最优路径二次优化以及路径淘汰机制对传统蚁群算法进行改进[16-17]。通过对传统算法与改进算法的仿真实验，可以看出改进算法用时大幅度降低，最优路径中改进后不存在路径凹陷类型的路径影响道路质量，其次最优路径也得到了明显的减少，基本接近理论值。实验结果验证了改进型蚁群算法在机械臂上的应用能够大幅度提高机械臂的运动能力。

[1] 张 成，凌有铸，陈孟元.改进蚁群算法求解移动机器人路径规划[J].电子测量与仪器学报，2016(11)：1758-1764.

[2] 张晓玲，罗印升，张宝峰，等.基于蚁群算法的移动机器人路径规划[J].激光杂志，2016(11)：80-83.

[3] 杨雅宁，蔺 勇.基于蚁群算法的一种无人机二维航迹规划方法研究[J].电脑知识与技术，2016(28)：189-191.

[4] 宗泽宏.蚁群算法的应用与改进[J].电子技术与软件工程，2017(1)：155.

[5] 尚梦雨.无人机实时蚁群算法路径规划[J].自动化应用，2016(12)：61-63.

[6] 李 卿，吴玉渠.应急救援路径选择的蚁群算法优化[J].自动化技术与应用，2016(12)：1-5.

[7] 朱颢东，孙 振，吴 迪.基于改进蚁群算法的移动机器人三维路径规划[J].华中师范大学学报(自然科学版)，2016(6)：812-817.

[8] 易正俊，李勇霞，易校石.自适应蚁群算法求解最短路径和TSP问题[J].计算机技术与发展，2016(12)：1-5.

[9] 唐胜景，陈天悦，李 震，等.基于感知模糊自适应蚁群算法的非线性PID控制设计[J].计算机测量与控制，2016(11)：91-94，99.

[10] 赵晓侠，鞠成恩.基于改进蚁群算法的农业运输车辆路径优化研究[J].安徽农业科学，2016(33)：237-238.

[11] 谭覃，刘树东，张 艳.移动机器人路径规划仿真研究[J].计算机仿真，2016(8)：354-358，424.

[12] 黄亚平，熊 婧.基于改进蚁群算法作业车间调度问题仿真研究[J].计算机仿真，2009(8)：278-282.

[13] 朱颢东，孙 振，吴 迪，等.基于改进蚁群算法的移动机器人路径规划[J].重庆邮电大学学报(自然科学版)，2016(6)：849-855.

[14] 刘云龙，王瑞兰，刘丽君，等.基于Matlab仿真的自动控制原理实验教学改革[J].实验室研究与探索，2015(6)：103-106.

[15] 张汝波，李建军，杨 玉.基于改进蚁群算法的AUV航路避障任务规划[J].华中科技大学学报(自然科学版)，2015(S1)：428-430.

[16] 穆 克，陈 涛，褚俊霞，等.网络搜索中的“死胡同”现象及蚁群改进算法[J].控制工程，2013(4)：762-765.

[17] 付 鹏，罗 杰.基于改进蚁群算法的Q学习算法研究[J].计算机技术与发展，2013(2)：123-126.

ApplicationofImprovedAntColonyAlgorithminPathPlanningofMulti-jointRobot

WANGJianghua1，ZHAOYan2

(1.Electronic Information Engineering College，North China Institute of Science and Technology，Sanhe 065201, Hebei，China； 2.College of Information Science and Technology，Yanching Institute of Technology，Sanhe 065201，Hebei, China)

In this paper, an improved ant colony algorithm is proposed to solve the path planning problem of manipulator in narrow space.The traditional ant colony algorithm is improved from the calculation of probability distribution, quadratic optimization of optimal path and path elimination mechanism, and the simulation results are compared by using Matlab software.The results show that the organization ability of the improved ant colony algorithm greatly enhances the robustness of the system, the algorithm can significantly improve the adaptability of robot arm in the mine and other complex environments.

mechanical arm； route plan； ant colony optimization(ACO) algorithm； self-organization

TP 301

A

1006-7167(2017)10-0041-04

2017-02-15

河北省高等学校科学技术研究项目(Z2015202)；廊坊市科技支撑计划项目(2016011033)；华北科技学院科技基金项目(3142014072)

王江华(1981-)，男，河北邢台人，硕士，讲师，研究方向：智能控制、图像处理以及电机控制等。Tel.：13785699600；E-mail：jianghua960@163.com

赵 燕(1982-)，女，河北石家庄人，硕士，讲师，研究方向：实验室建设与管理、实验教学改革。Tel.：13784464373；E-mail：zhaoyan137@163.com