基于果蠅優化算法的月球車全局路徑規劃

毛正陽，方 群

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

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

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

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

1 果蠅優化算法

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

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

依照果蠅搜索食物的特性，可將果蠅優化算法（Fruit Fly Optimization Algorithm，FOA）歸納為以下幾個重要步驟：

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

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

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

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

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

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

smellbest=bestsmell；

X=X（bestindex）；

Y=Y（bestindex）；

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

2 基于果蠅優化算法的路徑導航點規劃問題建模

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

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

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

3 果蠅優化算法的改進與實現

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

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

4 仿真及分析

4.1 環境建模

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

圖3 月面數字地形圖Fig.3 Digital terrain of lunar surface

4.2 FOA算法的路徑規劃

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

4.3 改進FOA算法的路徑規劃

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

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

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

圖4 FOA路徑規劃結果Fig.4 Path planning based on FOA

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

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

5 結 論

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

[1]孫純哲，桂貴生，韓東，等.基于蟻群算法的移動機器人路徑規劃研究與應用[J].合肥工業大學學報:自然科學版，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]彭松，賈陽.基于粒子群優化算法的月面巡視器全局路徑規劃[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]朱慶保.動態復雜環境下的機器人路徑規劃螞蟻預測算法[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種群智能算法的尋優性能研究[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]張珗，李清毅，許曉霞.月球表面地形數學建模方法[J].航天器環境工程，2007，24（6）:341-343.ZHANG Yue，LI Qing-yi，XU Xiao-xia.Mathematical modeling oflunarsurfaceterrain[J].SpacecraftEnvironmentEngineering，2007，24（6）:341-343.