基于蚁群-粒子群算法的巡检机器人路径规划

杨天宇，薛阳，张亚飞

（上海电力学院自动化工程学院，上海200090）

基于蚁群-粒子群算法的巡检机器人路径规划

杨天宇，薛阳，张亚飞

（上海电力学院自动化工程学院，上海200090）

目前，巡检机器人采用传统蚁群算法来实现路径规划较普遍，但传统蚁群算法在实现路径规划时在收敛速度、效率以及局部最优等问题表现较差，因此提出基于蚁群-粒子群组合优化算法应用到巡检机器人路径规划中，利用栅格法建立机器人工作环境，改善信息素的更新方式和解的多样性，仿真结果表明相较传统蚁群算法，采用蚁群-粒子群融合算法更能够更好地缩小最优路径的搜索范围，改善最优解的搜索效率，降低迭代次数，实现最优且无碰撞的全局路径。

0 引言

如今，变电站巡检主要是由值班员来人工完成，人工巡检存在诸如漏巡、漏检等方面的缺陷。此外，人工巡检在了解现场设备状态、发现隐患等方面并不够及时[1]。随着智能电网与智能化机器人的大力快速地发展，在未来，人工被智能机器人所取代来完成变电站巡检已成必然。因此，基于变电站环境下的智能巡检机器人尤为重要，而路径规划是巡检机器人最核心的技术之一[2]。

目前，巡检机器人的路径规划还是主要通过模仿动物的群集行为，如蚂蚁、鸟儿觅食等。蚁群算法（Ant Colony Optimization，ACO）即一种寻找优化路径的机率型算法[3]。蚂蚁识别彼此在各路径上所留下信息素的强弱来挑选觅食路径。蚁群算法特别适用于组合优化问题中，其具有精度高、强鲁棒性和收敛性等特点。蚁群算法虽然具有上述优势，但其还有改进之处，如计算量大，搜索较慢，难以摆脱局部最优等。

粒子群算法（Particle Swarm Optimization，PSO）是一种依托种群随机优化的算法，其在稳定性、收敛速度、全局搜索能力和搜索时间等方面具有明显优势，但是在处理组合优化的问题上，粒子群算法依旧存在短板[4]。

因此，鉴于上述蚁群与粒子群优化算法各自的优缺点，为机器人实现路径规划时能够利用各自的优势，提出了将传统蚁群算法与粒子群算法组合的方法，即首先采用粒子群算法所具有的较强的全局搜索能力作为基础，然后利用蚁群算法获取最优解。

1 蚁群与粒子群算法原理

1.1 蚁群算法（ACO）的基本原理

其中：ηij(t)为启发式因子，取ηij(t)=1/dij，dij为点i与点j之间的距离；τij(t)为点i与点j两点间t时刻的路径上信息素的浓度；allowedk为t时刻蚂蚁k所能选择的点的集合；α为τ相对重要程度；β为η相对重要程度。当蚂蚁经过所有点之后，更新存储在环境中的信息素。

其中：Q为信息素总量；Lk为蚂蚁k在经过所有点之后路径的总长度。当全部蚂蚁完成自己的路径构建，各路径上信息素的量逐渐增加，计算释放的信息素浓度，当浓度满足终止条件（即当迭代次数超过某一设定值）为止，则由蚂蚁构建的最优路径即为所求的最终解[6]。

1.2 粒子群算法（PSO）的基本原理

粒子群算法的初始状态为一组粒子随机分布在解区间内，作用是使迭代更加快速有效。通过不断更新粒子的位置（解的大小）和速度（解变化的步长），不断比较得到最优或较优解，进而实现路径最优。公式如下：

其中Vij(t)、Xij(t)分别是该粒子当前速度与位置，C1、C2为学习因子，Pij,Best为到目前为止第（i，j）个粒子搜索到的个体极值，gBest为全局值，rand（）为（0，1）之间的随机数，ω为加权系数。

上式中ω表示加权系数，通过控制当前速度影响后一个速度的方式，可以得到新的空间，通过不断迭代，ω值逐渐变小，不断更新全局值与个体极值，以获得全局最优[7]。

2 蚁群-粒子群融合优化算法

针对文中上述蚁群与粒子群算法各自优劣势，故采取蚁群算法与粒子群算法相互融合[8]的策略，发挥二者的优势来优化巡检机器人路径规划。在处理组合优化问题时，蚁群算法优势显著，因其包含较好的并行性、精度高、反馈良好，强鲁棒性和收敛性等特点。粒子群算法优势在于其较快的收敛速度、较好的全局搜索以及搜索时间短等。因此巡检机器人路径优化可先通过粒子群算法具有的较好的全局搜索来的特点，实现粗略搜索以获取路径上足够的信息素;再通过蚁群算法的正反馈特点来精确搜索[9]。

蚁群-粒子群组合算法步骤如下:

（1）参数初始化;

（2）采用PSO对全局粗略搜索;

（3）利用粗略搜索得到次优解;

（4）更新信息素，改善ACO搜索能力;

（5）通过ACO在次优路径上精确搜索;

（6）最终获得问题的最优解。

图1 蚁群-粒子群组合算法原理图

3 仿真结果

3.1 仿真环境建模

为了表明蚁群-粒子群算法的有效性与可行性，分别构建结合传统蚁群算法与蚁群-粒子群融合算法下巡检机器人的路径全局规划[10]，并在MATLAB软件和VC++6.0的环境下进行仿真。如图1所示:用一个全局静态10×10栅格矩阵表示，黑色栅格和白色栅格分别表示障碍物与可行栅格[11]，这个区域内分布了形状不同、大小不等的障碍物。Start、End分别表示机器人的起点与终点位置。

算法参数初始化为:蚂蚁数量m=80，α=1，β=2，信息素 ρ=0.05，迭代数为100。

3.2 试验结果与分析

图2和图3表示传统的蚁群算法与优化的蚁群-粒子群组合算法在试验工作环境下巡检机器人的路径规划。如图2所示，在搜索过程中，采用传统蚁群算法的路径规划存在很多的缺陷，如易陷入局部最优，易早熟，没有很好地找到全局最优的路径。

图3表示蚁群-粒子群组合算法的路径规划，改善了信息素的更新方式，用巡检机器人所在的位置到终点的距离优化启发因子，加入粗略搜索，减少了搜索最优路径的时间，通过更新信息素浓度分布，精确搜索次优路径，从而完成全局从起点到终点的最优路径。

为了更加全面地阐述文中的蚁群改进算法在路径规划中的有效性和最优执行效率，在以上仿真的基础上，分别在不同的测试环境中进行仿真对比试验，重新改变仿真环境，包括改变障碍物的分布情况，设置5个不同的试验环境，参数初始化保持。

不变，更改障碍物的体积和个数等，每种环境下各测试25次，每次试验循环100次，试验搜索最优解所需迭代次数如下表。

从表1中可以看出，参数设置保持不变的前提下，在不同的试验环境下，蚁群-粒子群融合算法通过利用粗搜索得到次优解进而获取次优路径，更新次优路径上的信息素分布，能够有效加快机器人全局寻优的速度，相比传统蚁群算法，算法融合之后可有效地将最优路径搜索次数降低了约34%，缩短了收敛时间，改善了算法的执行效率。

表1 搜索最优解的迭代次数

4 结语

变电站巡检机器人路径规划是电力相关单位研究的重点，如何快速有效地搜索出一条起点与终点间无碰撞且最短路径的算法是研究目的。机器人路径规划若采用传统蚁群算法，则会存在执行效率低迭代次数多等缺点。提出了一种基于蚁群-粒子群融合算法的巡检机器人路径规划，在传统蚁群算法的基础上加入粒子群算法，改进信息素的更新方式，增加解的多样性。仿真结果表明采用蚁群-粒子群融合算法可以减小路径最优的搜索范围，改善最优解的搜索效率，降低迭代次数，实现全局路径最优且无碰撞的路径。

图2 传统蚁群算法巡检机器人路径规划

图3 蚁群-粒子群组合算法的巡检机器人路径规划

[1]周立辉,张永生,孙勇,等.智能变电站巡检机器人研制及应用[J].电力系统自动化,2011,35(19):85-88.

[2]陈瑶,陈阿莲,李向东,等.变电站智能巡检机器人全局路径规划设计[J].山东科学,2015,28(1):114-119.

[3]刘雄,雷勇,涂国强.基于蚁群算法的移动机器人路径规划[J].计算机仿真,2011,28(11):185-188.

[4]黄太安,生佳根,徐红洋,等.一种改进的简化粒子群算法[J].计算机仿真,2013,30(2):327-330.

[5]郑慧君,陈俞强.基于改进蚁群的路径导航算法[J].控制工程,2016,23(4):608-612.

[6]邱莉莉,郑建立.基于改进蚁群算法的机器人路径规划[J].信息技术,2015(6):150-152.

[7]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.

[8]简毅,张月.移动机器人全局覆盖路径规划算法研究进展与展望[J].计算机应用,2014,34(10):2844-2849.

[9]Che H,Wu Z,Kang R,et al.Global Path Planning for Explosion-Proof Robot Based on Improved Ant Colony Optimization[C].Intelligent Robot Systems.IEEE,2016:36-40.

[10]Ren C M,Zhang J X.Robot Path Planning Based on Improved Ant Colony Optimization[J].Computer Engineering,2008,34(15):1-3.

[11]周东健,张兴国,马海波,等.基于栅格地图-蚁群算法的机器人最优路径规划[J].制造业自动化,2014,12(5):1-3.

杨天宇（1990-），男，湖北武汉人，硕士研究生，研究方向为图像处理、机器视觉、机器人路径规划

薛阳（1977-），男，江苏无锡人，博士后，副教授，研究方向为机器人控制、微电网控制

张亚飞（1993-），男，江苏连云港人，硕士研究生，研究方向为机器人技术、图像处理

Path Planning;Inspection Robot;Ant Colony Algorithm;Particle Swarm Optimization Algorithm;Optimal Path

Path Planning of Inspection Robot Based on Ant Colony-Particle Swarm Optimization Algorithm

YANG Tian-yu，XUE Yang，ZHANG Ya-fei

（College of Automation Engineering，Shanghai University of Electric Power，Shanghai 200090）

At present,the inspection robot using the traditional ant colony algorithm to realize path planning are common,but the traditional ant colo⁃ny algorithm in path planning in the convergence speed and the efficiency of local optimization and poor performance,therefore is proposed based on ant colony particle swarm optimization algorithm is applied to the combination of robot path planning,the establishment of the working environment of the robot using grid method.Diversity to improve the information update in the settlement,the simulation results show that compared with the traditional ant colony algorithm,the ant colony particle swarm fusion algorithm can better reduce the optimal path search range,improve the search efficiency of the optimal solution,reduce the number of iterations,the global optimal and collision free path.

路径规划；巡检机器人；蚁群算法；粒子群算法；最优路径

国家自然科学基金资助项目（No.61040013）

1007-1423（2017）29-0048-04

10.3969/j.issn.1007-1423.2017.29.012