基于果蠅優(yōu)化算法的月球車(chē)全局路徑規(guī)劃

毛正陽(yáng)，方 群

（西北工業(yè)大學(xué) 航天學(xué)院 航天飛行動(dòng)力學(xué)技術(shù)重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710072）

月球車(chē)是能夠在月球表面移動(dòng)，實(shí)施近距離探測(cè)，從而有效拓展探測(cè)范圍的航天器。月球車(chē)要適應(yīng)探測(cè)環(huán)境，需要找到從起始位置到目標(biāo)位置的安全路徑，即進(jìn)行路徑規(guī)劃。路徑規(guī)劃分為基于地圖的全局路徑規(guī)劃和基于傳感器的局部路徑規(guī)劃。

路徑規(guī)劃的算法正在不斷的發(fā)展和完善中。文獻(xiàn)[1]將人工勢(shì)場(chǎng)的思想引入到蟻群算法中，構(gòu)建并加入了權(quán)重可調(diào)的引力概率函數(shù)作為啟發(fā)因子，使新的算法在較快的收斂速度下仍能得到全局較優(yōu)解；文獻(xiàn)[2]針對(duì)粒子群算法在路徑規(guī)劃中易造成不收斂的問(wèn)題，去掉了速度更新中的速度慣性因子，同時(shí)引入經(jīng)典遺傳算法中的變異因子以增強(qiáng)算法的全局尋優(yōu)能力；文獻(xiàn)[3]以多組螞蟻為研究對(duì)象，采用最近鄰居搜索策略和趨近導(dǎo)向函數(shù)相互協(xié)作完成全局最優(yōu)路徑的搜索。

全局路徑規(guī)劃側(cè)重于最短可行路徑的選取，不考慮速度等因素[2]。本文討論的是在柵格地圖上進(jìn)行月面巡視器的全局路徑規(guī)劃問(wèn)題，將2011年Wen-Tsao Pan提出的果蠅優(yōu)化算法改進(jìn)后應(yīng)用于全局路徑規(guī)劃，達(dá)到快速尋找到最優(yōu)路徑的目的。

1 果蠅優(yōu)化算法

Wen-Tsao Pan從果蠅的覓食行為得到啟發(fā)，提出了尋求全局優(yōu)化的新方法[4]。果蠅本身在感官知覺(jué)上優(yōu)于其他物種，其嗅覺(jué)器官能夠很好的搜集漂浮在空氣中的各種氣味，甚至能嗅到40公里外的的食物源。果蠅飛近食物后亦可使用敏銳的視覺(jué)發(fā)現(xiàn)食物與同伴聚集的位置，并往該方向飛去，如圖1所示。

圖1 果蠅群體迭代搜索食物示意圖Fig.1 Food finding iterative process of a fruit fly swarm

依照果蠅搜索食物的特性，可將果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）歸納為以下幾個(gè)重要步驟：

1）隨機(jī)初始果蠅群體位置X，Y。

2）分配果蠅個(gè)體利用嗅覺(jué)搜尋食物隨機(jī)方向與距離：

3）估計(jì)果蠅與原點(diǎn)的距離Dist，再計(jì)算味道濃度判定值S，S為距離Dist的倒數(shù)：

4）味道濃度判定值代入味道濃度判定函數(shù)（Fitness Function）以求出該果蠅個(gè)體位置味道濃度smell：

5）找出果蠅群體中味道濃度最大的果蠅：

6）保留最佳味道濃度值與X、Y坐標(biāo)，此時(shí)果蠅群體利用視覺(jué)往該位置飛去：

smellbest=bestsmell；

X=X（bestindex）；

Y=Y（bestindex）；

7）進(jìn)入迭代尋優(yōu)，重復(fù)步驟2）-5），并判斷味道濃度是否優(yōu)于前一迭代味道濃度，若是則進(jìn)行步驟6）。

2 基于果蠅優(yōu)化算法的路徑導(dǎo)航點(diǎn)規(guī)劃問(wèn)題建模

如圖2所示，將全局地圖進(jìn)行等柵格大小劃分，I為起始點(diǎn)，G為目標(biāo)點(diǎn)。果蠅以給定的速度沿柵格邊飛行，圖2中粗實(shí)線為飛行路徑，P1、P2、P3為路徑導(dǎo)航點(diǎn)，將起點(diǎn) I視為P0，終點(diǎn)G視為P4，則整個(gè)路徑長(zhǎng)度

路徑規(guī)劃問(wèn)題即是對(duì)Pj的位置進(jìn)行優(yōu)化選擇，保證連線PjPj+1不與障礙物相交并使LP最小。

圖2 路徑導(dǎo)航點(diǎn)規(guī)劃建模Fig.2 Model of the path navigation points planning

3 果蠅優(yōu)化算法的改進(jìn)與實(shí)現(xiàn)

文獻(xiàn)[5]對(duì)果蠅優(yōu)化算法做了仿真分析，分析表明果蠅算法穩(wěn)定性較差，易于陷入局部最優(yōu)。

由上可知，利用FOA算法進(jìn)行路徑規(guī)劃時(shí)，需要對(duì)參數(shù)進(jìn)行必要的設(shè)置，對(duì)算法做出必要的改進(jìn)。考慮到FOA算法的參數(shù)設(shè)置是導(dǎo)致算法是否會(huì)陷入局部最優(yōu)的關(guān)鍵，本文提出基于改進(jìn)參數(shù)設(shè)置方法的改進(jìn)FOA算法，其對(duì)算法的改進(jìn)包括：第一，由于路徑規(guī)劃問(wèn)題的起始點(diǎn)與目標(biāo)點(diǎn)均是已知的，因而2中步驟1）果蠅群體的初始位置及食物源位置可以設(shè)為是已知的；第二，月球車(chē)具有一定的越障能力，2中步驟2）需要給予果蠅一定的越障能力并設(shè)置允許行進(jìn)代價(jià)值范圍；第三，一般情況下，起始點(diǎn)和目標(biāo)點(diǎn)相距較遠(yuǎn)，這樣2中步驟3）Dist的取值范圍會(huì)很大，為此當(dāng)計(jì)算味道濃度判定值S時(shí)，使得S的取值范圍很小，因而將其代入味道濃度判定函數(shù)時(shí)，很可能引起早熟收斂并陷入局部最優(yōu)。針對(duì)此問(wèn)題，本文提出將Dist直接帶入味道濃度判定函數(shù)，計(jì)算與目標(biāo)點(diǎn)距離差。因此不需將S代入味道濃度判定函數(shù)，從而不易陷入局部最優(yōu)，提高了算法的穩(wěn)定性，并可使果蠅群體向已知食物源飛行。

4 仿真及分析

4.1 環(huán)境建模

月球表面總體上可以分為月海和高地兩大地理單元，分布有大小不一的巖石和撞擊坑。根據(jù)以往獲得的月面地形信息，擬合得到其數(shù)學(xué)模型[6]。本文以平緩月海為例建立月面數(shù)字地形，綜合巡視器工作能力和體積水平，確定研究區(qū)域?yàn)?00 m×100 m。圖3為月面數(shù)字地形圖，單位m。然后分析其可通行性，得到可通行性代價(jià)地圖。

圖3 月面數(shù)字地形圖Fig.3 Digital terrain of lunar surface

4.2 FOA算法的路徑規(guī)劃

利用FOA優(yōu)化算法進(jìn)行仿真時(shí)，設(shè)定初始位置（1，1，0），目標(biāo)點(diǎn)（100，100，0），種群規(guī)模 200，迭代次數(shù) 500。規(guī)劃路徑，結(jié)果如圖4（a）所示，迭代次數(shù)如圖4（b）所示。多次仿真，除少數(shù)幾次外，均陷入局部最優(yōu)，無(wú)法得到完整規(guī)劃路徑。

4.3 改進(jìn)FOA算法的路徑規(guī)劃

利用改進(jìn)FOA優(yōu)化算法進(jìn)行仿真時(shí)，設(shè)定初始條件與5.2相同。規(guī)劃路徑，結(jié)果如圖5（a）所示，迭代次數(shù)如圖5（b）所示。運(yùn)算時(shí)間為3.39 s。

利用改進(jìn)FOA優(yōu)化算法進(jìn)行仿真時(shí)，設(shè)定初始位置（1，1，0），目標(biāo)點(diǎn)（100，100，0），種群規(guī)模 20，迭代次數(shù) 500。規(guī)劃路徑，結(jié)果如圖6（a）所示，迭代次數(shù)如圖6（b）所示。運(yùn)算時(shí)間4.17 s。

由以上兩組仿真結(jié)果對(duì)比分析可知，使用改進(jìn)FOA算法多次進(jìn)行路徑規(guī)劃均不會(huì)陷入局部最優(yōu)，表明了算法的穩(wěn)定性和有效性；但種群數(shù)目越多，搜索出的路徑越短，速度越快，迭代次數(shù)也越少。

圖4 FOA路徑規(guī)劃結(jié)果Fig.4 Path planning based on FOA

圖5 改進(jìn)FOA路徑規(guī)劃結(jié)果Fig.5 Path planning based on modified FOA

圖6 改進(jìn)FOA路徑規(guī)劃結(jié)果Fig.6 Path planning based on modified FOA

5 結(jié) 論

根據(jù)月球車(chē)遙操作系統(tǒng)中全局路徑規(guī)劃的要求，對(duì)果蠅優(yōu)化算法進(jìn)行修改并將其用于全局路徑規(guī)劃。考慮到果蠅優(yōu)化算法易于陷入局部最優(yōu)的問(wèn)題，將果蠅與原點(diǎn)的距離直接帶入味道濃度判定函數(shù)，通過(guò)仿真表明，該算法具有規(guī)劃速度快、全局尋優(yōu)能力強(qiáng)、不易陷入局部最優(yōu)的特點(diǎn)，能夠很好地找到全局優(yōu)化路徑。

[1]孫純哲，桂貴生，韓東，等.基于蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究與應(yīng)用[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2006，29（10）:1208-1211.SUN Chun-zhe，GUI Gui-sheng，HAN Dong，et al.Algorithm for mobile robot path planning based on the ant colony algorithm and its application[J].Journal of Hefei University of Technology，2006，29（10）:1208-1211.

[2]彭松，賈陽(yáng).基于粒子群優(yōu)化算法的月面巡視器全局路徑規(guī)劃[J].航天器工程，2012，21（1）:11-16.PENG Song，JIA Yang.Global path planning for lunar rover based on particle swarm optimization algorithm[J].Spacecraft Engineering，2012，21（1）:11-16.

[3]朱慶保.動(dòng)態(tài)復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃螞蟻預(yù)測(cè)算法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（11）:1898-1892.ZHU Qing-bao.Ants predictive algorithm for path planning of robot in a complex dynamic environment[J].Chinese Journal of Computers，2005，28（11）:1898-1892.

[4]Wen-Tsao Pan.Fruit fly optimization algorithm[M].Taipei:Tsang Hai Book Publishing Co.，2011.

[5]吳小文，李擎.果蠅算法和5種群智能算法的尋優(yōu)性能研究[J].火力與指揮控制，2013，38（4）:17-20.WU Xiao-wen，LI Qing.Research of optimizing performance of fruit fly optimization algorithm and five kinds of intelligent algorithm[J].Fire Control&Command Control，2013，38（4）:17-20.

[6]張珗，李清毅，許曉霞.月球表面地形數(shù)學(xué)建模方法[J].航天器環(huán)境工程，2007，24（6）:341-343.ZHANG Yue，LI Qing-yi，XU Xiao-xia.Mathematical modeling oflunarsurfaceterrain[J].SpacecraftEnvironmentEngineering，2007，24（6）:341-343.