基于改进萤火虫算法的移动机器人路径规划

丁建文，瞿遂春

（1.湖南工业大学 电气与信息工程学院，湖南 株洲 412007；2.南通大学 电气工程学院，江苏 南通 226019）

基于改进萤火虫算法的移动机器人路径规划

丁建文1，瞿遂春2

（1.湖南工业大学 电气与信息工程学院，湖南 株洲 412007；2.南通大学 电气工程学院，江苏 南通 226019）

针对标准萤火虫算法寻优容易陷入局部最优的缺点，通过改变萤火虫算法的搜索策略，对萤火虫算法进行改进，提高萤火虫算法的寻优能力。在移动机器人路径规划问题上采用改进后的萤火虫算法，实现了移动机器人全局路径规划的最优路径，理论与实验结果证明了改进后的萤火虫算法的有效性，此方法能满足移动机器人路径规划的要求。

萤火虫算法；移动机器人；路径规划

0 引言

导航是移动机器人研究的一个重点，不管是单机器人还是多机器人，它们都处于一种移动的工作状态中，导航是移动机器人技术研究的核心，是机器人首要研究任务[1]。简单地说，移动机器人导航问题就是从始点引导机器人到目标终点的路径导航，在无人干预的情况下，能够顺利到达目标点。根据移动机器人作业环境的规划来看，导航技术中路径规划方法大体上可分为全局路径规划和局部路径规划。其中，全局路径规划方法通过获取全局作业环境的信息，利用算法获取一条优化的全局路径，其常用的方法包括位广义锥法、自由空间法（MAKLINK图论）[2]、构型空间法[3]、栅格法[4]等；局部路径规划方法通过获取部分局部环境信息，实现路径规划。其通常的方法有人工势场法[5]、遗传算法[6]等。在机器人领域，国内外学者们都倾向于使用人工智能算法[7-8]，并在移动机器人路径规划上得到了很好的效果。人工智能算法基本原理是根据模拟生物的生理行为而实现仿生，其由群体智能发展而来。生物群体智能算法具有鲁棒性强、并行性高等优势。

本文主要讨论人工智能算法中的萤火虫算法，其根据模拟自然界中萤火虫的发光机制，即发光强的萤火虫吸引发光弱的萤火虫，利用这种方式进行互相通信、沟通、求偶或者进行捕食等行为的智能算法。文献[9]中萤火虫算法与几种智能算法的比较结果，证明了其在一定条件下的性能比较好，说明了标准萤火虫算法是一种高性能的仿生算法。通过借鉴其他发展成熟的群智能算法（如Yang Xinshe利用Levy Flight与萤火虫算法相结合，得出其在全局寻优方面相比遗传算法和粒子群算法成功率更高、更高效[10]），本文拟对已有萤火虫算法进行改进，并将改进后的萤火虫算法运用在移动机器人的路径规划上，实现移动机器人最优的路径规划，以验证改进后的萤火虫算法的有效性。

1 标准萤火虫算法

在标准萤火虫算法中，每个萤火虫代表优化目标的一个可行解，并将萤火虫的亮度用解的适应度来表示。在每次迭代开始前，每个萤火虫搜索周围比自身亮的个体，也就是通过萤火虫之间的发光强度比较，光强度大的萤火虫吸引力大，强度小的萤火虫吸引力小。吸引力小的萤火虫被吸引力大的萤火虫吸引，并以轮盘赌的方式随机向吸引力大的萤火虫运动。移动后再更新自己的位置和亮度，通过多次迭代，最终可得到优化目标的最优解。

定义1 萤火虫的最大荧光亮度为

式中：xi为第i只萤火虫在空间的位置；

f(xi)为这只萤火虫所在位置的适应度值。

定义2 萤火虫的相对荧光亮度为

rij为2个萤火虫之间的空间距离。

定义3 萤火虫的吸引度为

萤火虫i被萤火虫j所吸引，萤火虫i向其移动而更新自己的位置，因此萤火虫i位置更新公式为

式中：xi为原来萤火虫的位置；

萤火虫算法的基本流程如图1所示。

文献[11]以网络损耗作为目标函数，提出萤火虫算法解决该问题，但发现萤火虫算法有收敛速度慢以及容易陷入局部最优等缺点。基于此，课题组在萤火虫算法的基础上进行改进。

2 萤火虫算法的改进

萤火虫算法的改进，主要通过改变萤火虫的更新搜索策略来消去萤火虫容易陷入局部最优的缺点，新的搜索策略在萤火虫每一次将要移动前，将该萤火虫的亮度与全种群的亮度的平均值进行对比，当其亮度低于全种群亮度的平均值时，对该萤火虫进行自由变异，即让其自由寻找自己的位置。这样可以加大该萤火虫种群对外界进行搜索，减少陷入局部最优的情况。否则，对该萤火虫进行移动，移动后提前判断萤火虫的亮度是否低于移动前的亮度，如果亮度增加，将更新亮度，如果亮度变暗，则返回上一个步骤，进行与种群的平均亮度对比。在每一次萤火虫更新之后，计算萤火虫新种群中的最优值，如果更新前的最优值变差了，则把之前较优的个体替换进新种群中，防止种群退化；否则更新最优值。改进后的萤火虫算法流程如图2所示。

3 仿真及性能分析

通过测试函数验证标准萤火虫算法与改进萤火虫算法的性能，本文的寻优对象选取如下二元非线性目标函数：

二元非线性目标函数的三维图如图3所示。

如图3所示，该函数在(0, 0)处取得极大值，并且在极大值点周围有若干个局部极值点。所以该函数适合2种算法的寻优实验。

分别用萤火虫算法和改进后的萤火虫算法对目标函数进行寻优实验。设定萤火虫个数为10个，迭代次数为50次，最大的吸引力0为1，光强吸收因子为0.5，为0.2。得到萤火虫算法与改进后的萤火虫算法的寻优分布实验结果分别如图4～5所示。

从以上测试结果可以看出，标准萤火虫算法中萤火虫大部分都在局部极值点处，只有少量萤火虫位于最大极值点；而改进后的萤火虫算法中的萤火虫基本上聚集在极大值点附近。由此可知，改进后的算法解决了标准萤火虫容易陷入局部最优的问题。

在以上仿真的基础上，通过选取多峰函数为寻优对象，进行了多次仿真验证。仿真结果都验证了改进后的萤火虫算法在寻优能力以及收敛速度方面都有了很大的提高。

4 移动机器人全局路径规划

移动机器人的路径规划主要是通过自由空间法来实现全局路径规划，即通过构建作业环境中的广义锥形和凸多边形等基本几何图形的信息，通过在自由空间中连通各个几何图进行路径规划。自由空间法具有建模简单、实现效果好、重构环境信息简单等优点，但算法的复杂程度与作业环境中障碍物的数目成正比关系。文献[12]中基于自由空间法与Dijkstra算法、蚁群算法相结合的二维机器人路径规划。从该文献结果可以看出，蚁群算法的优化时间过长、优化结果不稳定，并不能获得全局最优的路径。

课题组通过改进后的萤火虫算法与Dijkstra算法的结合，实现移动机器人导航技术的路径最优，进一步证明了改进后的萤火虫算法的有效性。

4.1 二维路径规划

通过绘制室内环境的障碍物坐标图，建立移动机器人的二维路径障碍图，如图6所示。其中A至D 4个黑色区域代表室内环境中的障碍物，S作为始点，T作为终点。以下图中每个单元格的边长为7 cm。

通过图6基于MAKLINK图论建立的作业环境的二维路径空间模型，图7为室内移动机器人作业环境的MAKLINE空间模型的无向网络图。其中MAKLINK空间模型包括两障碍物顶点之间的可行连线，以及障碍物顶点与边界相交的可行连线，并且保证可行连线之间不能相互交叉。

由图7可以看出，MAKLINE存在20条可行线（图中用虚线表示），用v1～v20表示。因此，本文利用始点S和终点T构造整个作业环境的初始路径无向网络。

4.2 无向网络的最短路径

Dijkstra算法是有代表性的最短路径算法，构建Dijkstra算法的关键是如何建立贪心策略。Dijkstra算法同贪心算法一样都是先运算出局部最优，然后将这些局部最优合起来得到全局最优。

图8实线路径为Dijkstra算法搜索到的最短路径。通过该算法实现得到最短路径序列：S->v8->v7-> v6->v12->v13->v11->T，路径总长度为229.4 cm。从图8可看出Dijkstra算法搜寻的最短路径与可行连线v8, v7, v6, v12, v13, v11相交，且此最短路径必经过可行连线v8, v7, v6, v12, v13, v11的中点。

优化路径在可行连线v8, v7, v6, v12, v13, v11的两端点之间自由调整，直到找到最优路径。

图8中虚线路径为改进后的萤火虫算法结合Dijkstra算法搜索得到的最短路径，此时的最短路径总长度为168.5 cm。与Dijkstra算法最短路径229.4 cm相比，缩短了60.9 cm，优化效果相当明显。

5 结论

1）针对标准萤火虫算法寻优容易陷入局部最优的缺点，通过改变标准萤火虫算法中萤火虫位置更新的搜索策略，使萤火虫算法得到改进。

2）通过对二元非线性目标函数的测试验证了改进后的萤火虫算法的有效性。

3）将改进后的萤火虫算法与Dijkstra算法结合，并运用在机器人全局路径规划上，很好地解决移动机器人导航的路径规划问题，实现了移动机器人全局路径规划的最优路径。

参考文献：

[1]包壁祯.移动机器人定位与导航的研究[D].成都：电子科技大学，2011.

BAO Bizhen.Research on Localization and Navigation of Mobile Robot[D].Chengdu：University of Electronic Science and Technology of China，2011.

[2]HOU Y L，HU J W，ZHAO C H，et al.Test Set Optimization Using Cultural Particle Swarm Optimization[J].Journal of Harbin Engineering University，2007，27(7)：151-154．

[3]BONABEAU E，DORIGO M，THERAULAZ G.Swarm Intelligence：From Natural to Artificial Systems[M].Boston：Oxford University Press，1999：134-145.

[4]DANESHYARI W，YEN G G.Cultural MOPSO：Acultural Framework to Adapt Parameters of Multiobjective Particle Swarm Optimization[C]//The 2008 IEEE Congress on Evolutionary Computation.Hongkong：IEEE，2008：1325-1332．

[5]DEB K.Optimization for Engineering Design[M].New Delhi：Pren-Tice-Hall，1995：290-317.

[6]LIU S，WANG X.Cultured Differential Particle Swarm Optimization for Numerical Optimization Problems[C]// The 3rd International Conference on Natural Computation.[S.l.]：IEEE，2007：642-646.

[7]卢永乐，文志强，李建飞.基于改进模拟退火算法的LUT逆半调模板选择[J].湖南工业大学学报，2015，29(1)：76-82.

LU Yongle，WEN Zhiqiang，LI Jianfei.Template Selection for LUT Inverse Halftoning Based on Improved Simulated Annealing Algorithm[J].Journal of Hunan University of Technology，2015，29(1)：76-82.

[8]陈兴国，李圣清.鲁棒递归神经网络变结构控制同步电动机伺服系统[J].湖南工业大学学报，2011，25(1)：88-92.

CHEN Xingguo，LI Shengqing.The Variable-Structure Control of Robust Recurrent Neural Network on Synchronizer Motor Servo System[J].Journal of Hunan University of Technology，2011，25(1)：88-92.

[9]董 静.萤火虫算法研究及其在水下潜器路径规划中的应用[D].哈尔滨：哈尔滨工程大学，2013.

DONG Jing.Study on the Firefly Algorithm and Itsapplication for Path Planning in the Dive in the Water[D].Harbin：Harbin Engineering University，2013.

[10]YANG Xinshe.Firefly Algorithms for Multimodal Optimization[C]//The 5th International Conference on Stochastic Algorithms：Foundations and Applications.Berlin：Springer-Verlag，2009：169-178．

[11]OUAFA H，NADHIR K，LINDA S，et al，Optimal Power Flow with Emission Controlled Using Firefly Algorithm[C]//2013 International Coference on Modeling，Simulation and Applied Optimization.[S.l.]：IEEE，2013：1-6.

[12]史 峰，王 辉，郁 磊，等.MATLAB 智能算法30个案例分析[M].北京：北京航天航空大学出版社，2011：145-166.

SHI Feng，WANG Hui，YU Lei，et al.30 Case Analysis of MATLAB Intelligent Algorithm[M].Beijing：Beijing Aerospace University Press，2011：145-166.

（责任编辑：申 剑）

On the Path Planning of Mobile Robots Based on Improved Firefly Algorithm

DING Jianwen1，QU Suichun2
（1.School of Electrical and Information Engineering，Hunan University of Technology，Zhuzhou Hunan 412007，China；2.School of Electrical Engineering，Nantong University，Nantong Jiangsu 226019，China）

In view of the flaw exhibited by the firefly algorithm in cases where it is liable to fall into the local optimum, some improvement has thus been made about it by changing the search strategy of the firefly algorithm, which helps to improve its optimization ability.As for the path planning of mobile robots, an optimal path planning has been achieved by adopting an improved firefly algorithm.The theoretical and experimental results have verified the effectiveness of the improved algorithm, which can meet the requirements of mobile robot path planning.

firefly algorithm；mobile robot；path planning

TP242

A

1673-9833(2017)01-0064-05

10.3969/j.issn.1673-9833.2017.01.012

2016-11-27

丁建文（1990-），男，湖南常德人，湖南工业大学硕士生，主要研究方向为电机控制，E-mail：315071532@qq.com