基于改進(jìn)螢火蟲算法的移動機(jī)器人路徑規(guī)劃

丁建文，瞿遂春

（1.湖南工業(yè)大學(xué) 電氣與信息工程學(xué)院，湖南 株洲 412007；2.南通大學(xué) 電氣工程學(xué)院，江蘇 南通 226019）

基于改進(jìn)螢火蟲算法的移動機(jī)器人路徑規(guī)劃

丁建文1，瞿遂春2

（1.湖南工業(yè)大學(xué) 電氣與信息工程學(xué)院，湖南 株洲 412007；2.南通大學(xué) 電氣工程學(xué)院，江蘇 南通 226019）

針對標(biāo)準(zhǔn)螢火蟲算法尋優(yōu)容易陷入局部最優(yōu)的缺點(diǎn)，通過改變螢火蟲算法的搜索策略，對螢火蟲算法進(jìn)行改進(jìn)，提高螢火蟲算法的尋優(yōu)能力。在移動機(jī)器人路徑規(guī)劃問題上采用改進(jìn)后的螢火蟲算法，實(shí)現(xiàn)了移動機(jī)器人全局路徑規(guī)劃的最優(yōu)路徑，理論與實(shí)驗(yàn)結(jié)果證明了改進(jìn)后的螢火蟲算法的有效性，此方法能滿足移動機(jī)器人路徑規(guī)劃的要求。

螢火蟲算法；移動機(jī)器人；路徑規(guī)劃

0 引言

導(dǎo)航是移動機(jī)器人研究的一個重點(diǎn)，不管是單機(jī)器人還是多機(jī)器人，它們都處于一種移動的工作狀態(tài)中，導(dǎo)航是移動機(jī)器人技術(shù)研究的核心，是機(jī)器人首要研究任務(wù)[1]。簡單地說，移動機(jī)器人導(dǎo)航問題就是從始點(diǎn)引導(dǎo)機(jī)器人到目標(biāo)終點(diǎn)的路徑導(dǎo)航，在無人干預(yù)的情況下，能夠順利到達(dá)目標(biāo)點(diǎn)。根據(jù)移動機(jī)器人作業(yè)環(huán)境的規(guī)劃來看，導(dǎo)航技術(shù)中路徑規(guī)劃方法大體上可分為全局路徑規(guī)劃和局部路徑規(guī)劃。其中，全局路徑規(guī)劃方法通過獲取全局作業(yè)環(huán)境的信息，利用算法獲取一條優(yōu)化的全局路徑，其常用的方法包括位廣義錐法、自由空間法（MAKLINK圖論）[2]、構(gòu)型空間法[3]、柵格法[4]等；局部路徑規(guī)劃方法通過獲取部分局部環(huán)境信息，實(shí)現(xiàn)路徑規(guī)劃。其通常的方法有人工勢場法[5]、遺傳算法[6]等。在機(jī)器人領(lǐng)域，國內(nèi)外學(xué)者們都傾向于使用人工智能算法[7-8]，并在移動機(jī)器人路徑規(guī)劃上得到了很好的效果。人工智能算法基本原理是根據(jù)模擬生物的生理行為而實(shí)現(xiàn)仿生，其由群體智能發(fā)展而來。生物群體智能算法具有魯棒性強(qiáng)、并行性高等優(yōu)勢。

本文主要討論人工智能算法中的螢火蟲算法，其根據(jù)模擬自然界中螢火蟲的發(fā)光機(jī)制，即發(fā)光強(qiáng)的螢火蟲吸引發(fā)光弱的螢火蟲，利用這種方式進(jìn)行互相通信、溝通、求偶或者進(jìn)行捕食等行為的智能算法。文獻(xiàn)[9]中螢火蟲算法與幾種智能算法的比較結(jié)果，證明了其在一定條件下的性能比較好，說明了標(biāo)準(zhǔn)螢火蟲算法是一種高性能的仿生算法。通過借鑒其他發(fā)展成熟的群智能算法（如Yang Xinshe利用Levy Flight與螢火蟲算法相結(jié)合，得出其在全局尋優(yōu)方面相比遺傳算法和粒子群算法成功率更高、更高效[10]），本文擬對已有螢火蟲算法進(jìn)行改進(jìn)，并將改進(jìn)后的螢火蟲算法運(yùn)用在移動機(jī)器人的路徑規(guī)劃上，實(shí)現(xiàn)移動機(jī)器人最優(yōu)的路徑規(guī)劃，以驗(yàn)證改進(jìn)后的螢火蟲算法的有效性。

1 標(biāo)準(zhǔn)螢火蟲算法

在標(biāo)準(zhǔn)螢火蟲算法中，每個螢火蟲代表優(yōu)化目標(biāo)的一個可行解，并將螢火蟲的亮度用解的適應(yīng)度來表示。在每次迭代開始前，每個螢火蟲搜索周圍比自身亮的個體，也就是通過螢火蟲之間的發(fā)光強(qiáng)度比較，光強(qiáng)度大的螢火蟲吸引力大，強(qiáng)度小的螢火蟲吸引力小。吸引力小的螢火蟲被吸引力大的螢火蟲吸引，并以輪盤賭的方式隨機(jī)向吸引力大的螢火蟲運(yùn)動。移動后再更新自己的位置和亮度，通過多次迭代，最終可得到優(yōu)化目標(biāo)的最優(yōu)解。

定義1 螢火蟲的最大熒光亮度為

式中：xi為第i只螢火蟲在空間的位置；

f(xi)為這只螢火蟲所在位置的適應(yīng)度值。

定義2 螢火蟲的相對熒光亮度為

rij為2個螢火蟲之間的空間距離。

定義3 螢火蟲的吸引度為

螢火蟲i被螢火蟲j所吸引，螢火蟲i向其移動而更新自己的位置，因此螢火蟲i位置更新公式為

式中：xi為原來螢火蟲的位置；

螢火蟲算法的基本流程如圖1所示。

文獻(xiàn)[11]以網(wǎng)絡(luò)損耗作為目標(biāo)函數(shù)，提出螢火蟲算法解決該問題，但發(fā)現(xiàn)螢火蟲算法有收斂速度慢以及容易陷入局部最優(yōu)等缺點(diǎn)。基于此，課題組在螢火蟲算法的基礎(chǔ)上進(jìn)行改進(jìn)。

2 螢火蟲算法的改進(jìn)

螢火蟲算法的改進(jìn)，主要通過改變螢火蟲的更新搜索策略來消去螢火蟲容易陷入局部最優(yōu)的缺點(diǎn)，新的搜索策略在螢火蟲每一次將要移動前，將該螢火蟲的亮度與全種群的亮度的平均值進(jìn)行對比，當(dāng)其亮度低于全種群亮度的平均值時，對該螢火蟲進(jìn)行自由變異，即讓其自由尋找自己的位置。這樣可以加大該螢火蟲種群對外界進(jìn)行搜索，減少陷入局部最優(yōu)的情況。否則，對該螢火蟲進(jìn)行移動，移動后提前判斷螢火蟲的亮度是否低于移動前的亮度，如果亮度增加，將更新亮度，如果亮度變暗，則返回上一個步驟，進(jìn)行與種群的平均亮度對比。在每一次螢火蟲更新之后，計(jì)算螢火蟲新種群中的最優(yōu)值，如果更新前的最優(yōu)值變差了，則把之前較優(yōu)的個體替換進(jìn)新種群中，防止種群退化；否則更新最優(yōu)值。改進(jìn)后的螢火蟲算法流程如圖2所示。

3 仿真及性能分析

通過測試函數(shù)驗(yàn)證標(biāo)準(zhǔn)螢火蟲算法與改進(jìn)螢火蟲算法的性能，本文的尋優(yōu)對象選取如下二元非線性目標(biāo)函數(shù)：

二元非線性目標(biāo)函數(shù)的三維圖如圖3所示。

如圖3所示，該函數(shù)在(0, 0)處取得極大值，并且在極大值點(diǎn)周圍有若干個局部極值點(diǎn)。所以該函數(shù)適合2種算法的尋優(yōu)實(shí)驗(yàn)。

分別用螢火蟲算法和改進(jìn)后的螢火蟲算法對目標(biāo)函數(shù)進(jìn)行尋優(yōu)實(shí)驗(yàn)。設(shè)定螢火蟲個數(shù)為10個，迭代次數(shù)為50次，最大的吸引力0為1，光強(qiáng)吸收因子為0.5，為0.2。得到螢火蟲算法與改進(jìn)后的螢火蟲算法的尋優(yōu)分布實(shí)驗(yàn)結(jié)果分別如圖4～5所示。

從以上測試結(jié)果可以看出，標(biāo)準(zhǔn)螢火蟲算法中螢火蟲大部分都在局部極值點(diǎn)處，只有少量螢火蟲位于最大極值點(diǎn)；而改進(jìn)后的螢火蟲算法中的螢火蟲基本上聚集在極大值點(diǎn)附近。由此可知，改進(jìn)后的算法解決了標(biāo)準(zhǔn)螢火蟲容易陷入局部最優(yōu)的問題。

在以上仿真的基礎(chǔ)上，通過選取多峰函數(shù)為尋優(yōu)對象，進(jìn)行了多次仿真驗(yàn)證。仿真結(jié)果都驗(yàn)證了改進(jìn)后的螢火蟲算法在尋優(yōu)能力以及收斂速度方面都有了很大的提高。

4 移動機(jī)器人全局路徑規(guī)劃

移動機(jī)器人的路徑規(guī)劃主要是通過自由空間法來實(shí)現(xiàn)全局路徑規(guī)劃，即通過構(gòu)建作業(yè)環(huán)境中的廣義錐形和凸多邊形等基本幾何圖形的信息，通過在自由空間中連通各個幾何圖進(jìn)行路徑規(guī)劃。自由空間法具有建模簡單、實(shí)現(xiàn)效果好、重構(gòu)環(huán)境信息簡單等優(yōu)點(diǎn)，但算法的復(fù)雜程度與作業(yè)環(huán)境中障礙物的數(shù)目成正比關(guān)系。文獻(xiàn)[12]中基于自由空間法與Dijkstra算法、蟻群算法相結(jié)合的二維機(jī)器人路徑規(guī)劃。從該文獻(xiàn)結(jié)果可以看出，蟻群算法的優(yōu)化時間過長、優(yōu)化結(jié)果不穩(wěn)定，并不能獲得全局最優(yōu)的路徑。

課題組通過改進(jìn)后的螢火蟲算法與Dijkstra算法的結(jié)合，實(shí)現(xiàn)移動機(jī)器人導(dǎo)航技術(shù)的路徑最優(yōu)，進(jìn)一步證明了改進(jìn)后的螢火蟲算法的有效性。

4.1 二維路徑規(guī)劃

通過繪制室內(nèi)環(huán)境的障礙物坐標(biāo)圖，建立移動機(jī)器人的二維路徑障礙圖，如圖6所示。其中A至D 4個黑色區(qū)域代表室內(nèi)環(huán)境中的障礙物，S作為始點(diǎn)，T作為終點(diǎn)。以下圖中每個單元格的邊長為7 cm。

通過圖6基于MAKLINK圖論建立的作業(yè)環(huán)境的二維路徑空間模型，圖7為室內(nèi)移動機(jī)器人作業(yè)環(huán)境的MAKLINE空間模型的無向網(wǎng)絡(luò)圖。其中MAKLINK空間模型包括兩障礙物頂點(diǎn)之間的可行連線，以及障礙物頂點(diǎn)與邊界相交的可行連線，并且保證可行連線之間不能相互交叉。

由圖7可以看出，MAKLINE存在20條可行線（圖中用虛線表示），用v1～v20表示。因此，本文利用始點(diǎn)S和終點(diǎn)T構(gòu)造整個作業(yè)環(huán)境的初始路徑無向網(wǎng)絡(luò)。

4.2 無向網(wǎng)絡(luò)的最短路徑

Dijkstra算法是有代表性的最短路徑算法，構(gòu)建Dijkstra算法的關(guān)鍵是如何建立貪心策略。Dijkstra算法同貪心算法一樣都是先運(yùn)算出局部最優(yōu)，然后將這些局部最優(yōu)合起來得到全局最優(yōu)。

圖8實(shí)線路徑為Dijkstra算法搜索到的最短路徑。通過該算法實(shí)現(xiàn)得到最短路徑序列：S->v8->v7-> v6->v12->v13->v11->T，路徑總長度為229.4 cm。從圖8可看出Dijkstra算法搜尋的最短路徑與可行連線v8, v7, v6, v12, v13, v11相交，且此最短路徑必經(jīng)過可行連線v8, v7, v6, v12, v13, v11的中點(diǎn)。

優(yōu)化路徑在可行連線v8, v7, v6, v12, v13, v11的兩端點(diǎn)之間自由調(diào)整，直到找到最優(yōu)路徑。

圖8中虛線路徑為改進(jìn)后的螢火蟲算法結(jié)合Dijkstra算法搜索得到的最短路徑，此時的最短路徑總長度為168.5 cm。與Dijkstra算法最短路徑229.4 cm相比，縮短了60.9 cm，優(yōu)化效果相當(dāng)明顯。

5 結(jié)論

1）針對標(biāo)準(zhǔn)螢火蟲算法尋優(yōu)容易陷入局部最優(yōu)的缺點(diǎn)，通過改變標(biāo)準(zhǔn)螢火蟲算法中螢火蟲位置更新的搜索策略，使螢火蟲算法得到改進(jìn)。

2）通過對二元非線性目標(biāo)函數(shù)的測試驗(yàn)證了改進(jìn)后的螢火蟲算法的有效性。

3）將改進(jìn)后的螢火蟲算法與Dijkstra算法結(jié)合，并運(yùn)用在機(jī)器人全局路徑規(guī)劃上，很好地解決移動機(jī)器人導(dǎo)航的路徑規(guī)劃問題，實(shí)現(xiàn)了移動機(jī)器人全局路徑規(guī)劃的最優(yōu)路徑。

參考文獻(xiàn)：

[1]包壁禎.移動機(jī)器人定位與導(dǎo)航的研究[D].成都：電子科技大學(xué)，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]盧永樂，文志強(qiáng)，李建飛.基于改進(jìn)模擬退火算法的LUT逆半調(diào)模板選擇[J].湖南工業(yè)大學(xué)學(xué)報(bào)，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īng)網(wǎng)絡(luò)變結(jié)構(gòu)控制同步電動機(jī)伺服系統(tǒng)[J].湖南工業(yè)大學(xué)學(xué)報(bào)，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]董 靜.螢火蟲算法研究及其在水下潛器路徑規(guī)劃中的應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué)，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].北京：北京航天航空大學(xué)出版社，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.

（責(zé)任編輯：申 劍）

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-），男，湖南常德人，湖南工業(yè)大學(xué)碩士生，主要研究方向?yàn)殡姍C(jī)控制，E-mail：315071532@qq.com