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

毛正陽，方 群

（西北工業(yè)大學 航天學院 航天飛行動力學技術重點實驗室，陜西 西安 710072）

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

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

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

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

Wen-Tsao Pan從果蠅的覓食行為得到啟發(fā)，提出了尋求全局優(yōu)化的新方法[4]。果蠅本身在感官知覺上優(yōu)于其他物種，其嗅覺器官能夠很好的搜集漂浮在空氣中的各種氣味，甚至能嗅到40公里外的的食物源。果蠅飛近食物后亦可使用敏銳的視覺發(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）歸納為以下幾個重要步驟：

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

2）分配果蠅個體利用嗅覺搜尋食物隨機方向與距離：

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

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

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

6）保留最佳味道濃度值與X、Y坐標，此時果蠅群體利用視覺往該位置飛去：

smellbest=bestsmell；

X=X（bestindex）；

Y=Y（bestindex）；

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

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

如圖2所示，將全局地圖進行等柵格大小劃分，I為起始點，G為目標點。果蠅以給定的速度沿柵格邊飛行，圖2中粗實線為飛行路徑，P1、P2、P3為路徑導航點，將起點 I視為P0，終點G視為P4，則整個路徑長度

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

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

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

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

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

4 仿真及分析

4.1 環(huán)境建模

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

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

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

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

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

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

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

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

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

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

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

5 結 論

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

[1]孫純哲，桂貴生，韓東，等.基于蟻群算法的移動機器人路徑規(guī)劃研究與應用[J].合肥工業(yè)大學學報:自然科學版，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ō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]朱慶保.動態(tài)復雜環(huán)境下的機器人路徑規(guī)劃螞蟻預測算法[J].計算機學報，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ù)學建模方法[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.