于曉強，郭繼峰，趙毓，顏鵬

哈爾濱工業(yè)大學(xué) 航天學(xué)院，哈爾濱 150002

在中國嫦娥四號探月工程中，玉兔二號月球車成功實現(xiàn)了人類首次在月背的巡視探測任務(wù)，掀開了人類探索月球的新篇章。在月球探測任務(wù)中，月球車(也稱月面巡視機器人)作為任務(wù)的執(zhí)行體，其能力的大小直接關(guān)乎探測任務(wù)的效率及成功性。美國阿波羅計劃中的月球車已經(jīng)初步具備自主能力，但還是以航天員的駕駛為主，仍處于人機配合的階段[1]。中國玉兔二號月球車同時具備地面遙控和自主導(dǎo)航移動能力，其可以通過自身搭載的傳感器感知周圍環(huán)境并進(jìn)行自主路徑規(guī)劃。美國正在開展高級月面巡視機器人的研究，包括全地形六角形地形探測者計劃(The All-Terrain Hex-Limbed Extra-Terrestrial Explorer, ATHLETE)[2]、空間探索飛行器(Space Exploration Vehicle)[3]等，旨在開發(fā)具備高自主、全地形及大范圍轉(zhuǎn)移能力的巡視機器人，以支持未來月球基地的建設(shè)計劃。月面巡視機器人的自主移動及探測能力無疑會給月球探測提供了更加自主魯棒的探測模式，同時也極大提高了月球探測的效率。

在增加巡視機器人自主探測能力的同時，必須要考慮對其安全性的影響。美國“勇氣號”火星車曾因車輪陷入沙地而導(dǎo)致無法移動，最終于2011年3月徹底失聯(lián)。這說明巡視機器人的安全性是其探測任務(wù)成功與否最重要的因素，必須在自主探測過程中保證巡視機器人的安全可靠性，使其盡量遠(yuǎn)離危險區(qū)域，維持巡視機器人長期穩(wěn)定的工作。

路徑規(guī)劃技術(shù)作為月面巡視機器人自主探測最重要的環(huán)節(jié)之一，其規(guī)劃結(jié)果直接影響了探測任務(wù)的效率與安全性，受到了國內(nèi)外研究人員的廣泛關(guān)注。文獻(xiàn)[4]提出一種基于地形可通過性定量評價和目標(biāo)可達(dá)的局部綜合避障規(guī)劃方法，在實現(xiàn)局部避障的同時保證目標(biāo)可達(dá)，并成功應(yīng)用于中國“玉兔號”和“玉兔二號”月球車自主導(dǎo)航中。文獻(xiàn)[5]分析了行星車自身能力約束及外部環(huán)境約束對規(guī)劃的影響，并根據(jù)履帶式和輪式巡視機器人不同的運動特性，對其規(guī)劃路徑進(jìn)行了仿真，驗證了其方法的有效性。

目前對于月面路徑規(guī)劃問題的研究大多是針對較小區(qū)域、考慮精確約束的局部避障路徑規(guī)劃，而隨著月面探測需求以及月球車運動能力的提升，需要開展針對月面大范圍移動的全局路徑規(guī)劃研究。全局路徑規(guī)劃算法主要包括啟發(fā)式算法(如遺傳算法、蟻群算法等)、基于采樣的算法(如RRT算法、PRM算法等)以及基于圖搜索的精確式算法(如Dijkstra、A*等)[6-10]。由于啟發(fā)式算法及采樣算法的算法機制導(dǎo)致求解存在較高的不確定性，不能保證解的最優(yōu)性?？紤]到月面探測任務(wù)的高代價及高風(fēng)險性，本文主要研究具有最優(yōu)性保證的精確式搜索算法。而此類算法主要的缺點是搜索速度太慢，尤其針對大范圍地圖中的路徑搜索。

在基于圖搜索的精確式算法中，如何定義代價函數(shù)(啟發(fā)值函數(shù))是路徑規(guī)劃的關(guān)鍵。即使使用相同的算法，生成的路徑也可能因評估指標(biāo)的不同而不同。針對月面探測路徑規(guī)劃的代價函數(shù)，文獻(xiàn)[11]綜合考慮了地形可達(dá)、光照情況、通信可達(dá)等多種因素，在導(dǎo)航單元規(guī)劃中設(shè)計了考慮地形行走代價、移動里程代價、操作控制代價等因素的平滑曲線路徑搜索算法。文獻(xiàn)[5]分別考慮了距離代價、與行星車自身能力相關(guān)的地形代價、與外部環(huán)境相關(guān)的光照代價，并分析了他們之間不同權(quán)重對路徑的影響。綜上來看，目前代價函數(shù)的設(shè)計缺少對路徑安全代價的考慮，而安全性是巡視機器人路徑規(guī)劃最重要的因素之一，必須保證生成的路徑盡量遠(yuǎn)離危險區(qū)域，來實現(xiàn)巡視機器人的安全可靠探測。

本文提出了一種基于月面數(shù)字高程模型(Digital Elevation Model, DEM)地圖的大范圍移動快速安全路徑規(guī)劃算法，首先根據(jù)月面DEM地圖分析地形可通過性，并生成了歐幾里得距離地圖(Euclidean Distance Map, EDM)。然后提出了FSA*(Fast-Safe A*)算法，改進(jìn)了A*算法的搜索機制以適用于大范圍的快速路徑搜索，并結(jié)合EDM設(shè)計了一種安全啟發(fā)式函數(shù)，極大地提高了生成路徑的安全性，同時縮短了算法的搜索時間。最后以嫦娥四號著陸的南極艾特肯盆地附近區(qū)域作為仿真場景，驗證了本文所提算法的有效性，并與其他主要搜索算法進(jìn)行了性能對比。

1 DEM地圖處理

數(shù)字高程模型是通過有限的地形高程數(shù)據(jù)實現(xiàn)對地面地形的數(shù)字化模擬(即地形表面形態(tài)的數(shù)字化表達(dá))。月面DEM地圖是獲取月面地形信息的主要方式。目前國際上常用的月面DEM數(shù)據(jù)集包括中國嫦娥二號CE2TMap2015數(shù)據(jù)[12]、美國SLDEM數(shù)據(jù)[13]、GLD100數(shù)據(jù)[14]以及LOLA DEM數(shù)據(jù)[15]。文獻(xiàn)[12]對他們的精度進(jìn)行了分析對比，結(jié)果表明CE-2全月地形數(shù)據(jù)產(chǎn)品在空間分辨率、全月覆蓋率、數(shù)據(jù)連續(xù)性、絕對定位精度和地貌結(jié)構(gòu)細(xì)節(jié)表達(dá)等方面與其他全月地形產(chǎn)品相比具有明顯的優(yōu)勢。所以本文采用嫦娥二號CE2TMap2015數(shù)據(jù)進(jìn)行月面地形處理。

月球DEM數(shù)據(jù)按柵格形式存儲了月面每個位置的高程信息，不能直接作為路徑規(guī)劃中的環(huán)境地圖，需要通過提取高程數(shù)據(jù)計算深層次的地形特征信息，如坡度、平滑度等，再根據(jù)設(shè)定的巡視機器人能力限制轉(zhuǎn)化為可通過性地圖。

本文主要從坡度、起伏度以及粗糙度3個方面從DEM數(shù)據(jù)中提取月面地形信息，采用滾動窗口的形式計算每個柵格內(nèi)的地形特征，即通過設(shè)置一個3×3柵格大小的滾動窗口，將窗口內(nèi)的地形信息作為中心柵格的地形特征。

地形坡度θ由式(1)計算得到：

(1)

式中：fx為中心柵格東西方向高程變化率；fy為中心柵格南北方向高程變化率，采用三階不帶權(quán)差分方法計算：

(2)

式中：H1～H9分別為3×3窗口內(nèi)部的9個柵格對應(yīng)的高程值；g為DEM數(shù)據(jù)的分辨率大小。

地形起伏度R可由窗口內(nèi)高程最大值與高程最小值的差計算得到：

R=Hmax-Hmin

(3)

式中：Hmax為窗口內(nèi)的最大高程值；Hmin為窗口內(nèi)的最小高程值。

地形粗糙度δ可由窗口內(nèi)所有點的高程值標(biāo)準(zhǔn)差計算得到：

(4)

通過滾動窗口在DEM地圖中依次計算，可以得到地圖中所有柵格的地形信息。然后根據(jù)巡視器的能力約束，設(shè)置最大坡度、起伏度、粗糙度的閾值限制為θmax=20°，Rmax=g/2，δmax=g/5。超過此閾值限制的柵格區(qū)域視為障礙區(qū)域，據(jù)此可將DEM地圖轉(zhuǎn)化為規(guī)劃可用的可通過性地圖。

為保證探測路徑的高可靠性和安全性，本文在可通過性二值地圖的基礎(chǔ)上生成了歐幾里得距離地圖(EDM)[16]，即地圖中每個柵格內(nèi)儲存了其距離最近障礙點的歐氏距離，并將此距離作為路徑規(guī)劃的啟發(fā)值，保證規(guī)劃出的路徑盡量遠(yuǎn)離障礙區(qū)域，以提高探測任務(wù)的安全性。

選取嫦娥四號著陸點附近的南極艾特肯盆地區(qū)域作為仿真場景，采用上述方法對CE2TMap2015數(shù)據(jù)的42°S～56°S， 156°E～180°E(約540 km×440 km，50 m分辨率)區(qū)域進(jìn)行地形分析處理，結(jié)果如圖1所示。

由圖1可以看出，本節(jié)所提出的地形計算方法可以較好地還原月面地形特征，對環(huán)形山邊緣、小型山脈等危險區(qū)域有很好的提取效果。同時，EDM地圖可以給出距離障礙較遠(yuǎn)的區(qū)域(圖中明亮的區(qū)域)，為后續(xù)安全路徑規(guī)劃算法提供參考。

2 大范圍快速安全路徑規(guī)劃

由于月面探測任務(wù)的高風(fēng)險性與高代價性，本節(jié)選用具有路徑最優(yōu)性保證的A*算法進(jìn)行改進(jìn)，提出了FSA*算法，首先根據(jù)大范圍移動的任務(wù)場景改進(jìn)了A*算法的搜索機制，加速了算法的搜索過程，然后結(jié)合EDM地圖設(shè)計了一種安全啟發(fā)式函數(shù)，保證生成的路徑可以盡量遠(yuǎn)離障礙區(qū)域。

A*算法是一種啟發(fā)式搜索算法，根據(jù)啟發(fā)式函數(shù)f(n)擴展搜索的節(jié)點，f(n)=g(n)+h(n)，其中g(shù)(n)為從起點到節(jié)點n的路徑的確切代價，h(n)為節(jié)點n到目標(biāo)點的剩余路徑代價估計。文獻(xiàn)[17]證明了當(dāng)啟發(fā)式函數(shù)f(n)滿足一致性條件時A*可以找到最優(yōu)解。同時，A*算法使用OPEN表和CLOSE表存儲正在探索的節(jié)點和已經(jīng)探索過的節(jié)點，首先從OPEN表中選擇啟發(fā)式函數(shù)f(n)最小的節(jié)點最為當(dāng)前節(jié)點，并將其加入CLOSE表中，然后擴展當(dāng)前節(jié)點的所有鄰居節(jié)點加入OPEN表中，再選擇f(n)最小的節(jié)點進(jìn)行擴展，如此迭代直至搜索到目標(biāo)節(jié)點。其中還要考慮當(dāng)前節(jié)點的鄰居節(jié)點已經(jīng)在OPEN表中的情況，這時要判斷由當(dāng)前節(jié)點擴展的f(n)值是否更小，如果是則需要對OPEN表進(jìn)行更新，并重新排序。

由此可見，A*算法在擴展的過程中，每次循環(huán)都要判斷本節(jié)點是否在OPEN表和CLOSE表中，并且OPEN表內(nèi)的節(jié)點可能會被探索多次，重復(fù)計算g(n)以及對OPEN表重復(fù)排序，事實上這是對路徑最優(yōu)性影響較小且非常耗費時間的操作，尤其是在大范圍地圖中搜索的情況。同時，本文所提出的安全啟發(fā)式函數(shù)破壞了原啟發(fā)式函數(shù)的一致性，會導(dǎo)致A*算法搜索失敗以及進(jìn)一步增加算法的搜索時間。

本節(jié)所提出的FSA*算法改變了A*算法的搜索機制，使每個節(jié)點只被探索一次，每個節(jié)點的g(n)值改為該節(jié)點與起點的對角啟發(fā)式距離，是對從起點到該節(jié)點真實代價的估計值，這樣做就避免了對節(jié)點的重復(fù)探索。這也導(dǎo)致算法不必使用CLOSE表來儲存探索過的最優(yōu)節(jié)點，同時，可以使用每個節(jié)點的g(n)值比較代替節(jié)點是否在OPEN表的判斷以及OPEN表的排序操作，也加快了算法的搜索過程。具體算法詳見算法1。

首先是對算法進(jìn)行初始化(第2～6行)，包括OPEN表、啟發(fā)式函數(shù)f(n)、g(n)(這里將g(n)初始化為極大值矩陣)。然后是FSA*算法的擴展搜索過程(第7～22行)，選擇OPEN表內(nèi)f(n)值最小的節(jié)點作為當(dāng)前節(jié)點，對其所有鄰居節(jié)點進(jìn)行擴展(第13～21行)，這里選擇g(n)值變小的節(jié)點進(jìn)行探索。g(n)值變小的節(jié)點證明是未探索過的節(jié)點，這樣就避免了對節(jié)點n的多次探索以及是否在OPEN表中的判斷，節(jié)省了大量搜索時間。

算法1:FSA*算法1.輸入:Map, Start, Goal2.Openlist=Start∥初始化OPEN表3.f_score(start)=heuristic_safe(Start, Goal)∥初始化f(n)4.g_score = ones(length(Map),width(Map))*Inf∥初始化g(n)5.g_score(start) = 06.parent = Map∥初始化父節(jié)點查詢表7.while Openlist≠NULL do8. current = the node in openlist having the lowest f_score value9. if current = goal∥到達(dá)目標(biāo)節(jié)點10. return reconstruct_path(parent, current)11. end12. Openlist.Remove(current)13. for each free neighbor v of current do14. g_score_temp = diagonal_dist (start,v)15. if g_score_temp < g_score[v]16. g_score[v] = g_score_temp17. f _score[v] = g_score[v] + heuristic_safe(v, Goal)18. Openlist = [Openlist, v]19. parent(v) = current20. end21.end22.end23.return failure24.function reconstruct_path(parent, current)25. path = [current]26. while current≠Start do27. current = parent(current)28. path = [path, current]29. end30. return path

本節(jié)還定義了安全啟發(fā)式函數(shù)heuristic_safe()來指導(dǎo)算法進(jìn)行安全路徑搜索:

heuristic_safe(x,y)=Diagonal_heuristic(x,y)*

(5)

式中：Diagonal_heuristic(·)為對角啟發(fā)式距離函數(shù)，也可替換為歐氏距離函數(shù)或其他滿足一致性條件的啟發(fā)式函數(shù)；EDM(x)為第1節(jié)生成的歐幾里得距離地圖中節(jié)點x的距離值，表示節(jié)點x與其最近的障礙的距離值；Dismax為EDM地圖中的最大距離值；α為安全系數(shù)，可以人為設(shè)定來調(diào)節(jié)算法在不同風(fēng)險等級區(qū)域搜索的性能，其作用會在后續(xù)仿真驗證部分詳細(xì)介紹。

由于安全啟發(fā)式函數(shù)引入了EDM距離，破壞了原啟發(fā)式函數(shù)的一致性，同時還修改了原A*算法的搜索機制，所以不能保證FSA*算法生成的路徑具有距離最優(yōu)性，而本文關(guān)注的是月面巡視機器人大范圍自主探測的快速安全路徑規(guī)劃，具體性能表現(xiàn)會在仿真驗證部分進(jìn)行詳細(xì)分析。

3 仿真驗證分析

3.1 仿真場景

選取嫦娥四號著陸點附近的南極艾特肯盆地區(qū)域作為大范圍自主探測仿真場景，首先根據(jù)第1節(jié)所提地圖處理方法生成如圖1所示的可通過性地圖與EDM地圖，地圖規(guī)模約為10 000柵格×10 000柵格。然后選取任務(wù)起點為嫦娥四號著陸點45.5°S,177.6°E，即馮卡門撞擊坑中部區(qū)域，終點選取為南部的龐加萊撞擊坑中上部區(qū)域55.5°S,163.9°E，因為龐加萊撞擊坑是月球背面南半部一座龐大的古撞擊坑，很有可能挖掘出原始月幔物質(zhì)，是探測和研究深部月殼及月幔物質(zhì)的理想?yún)^(qū)域，具有較高的探測價值[18]。

所有算法的仿真測試軟件環(huán)境為Windows 10+MATLAB 2016，硬件環(huán)境為Intel(R) Core(TM)i5-7200U CPU+12.0 GB RAM。

3.2 有效性驗證

根據(jù)3.1節(jié)設(shè)定的仿真場景，本節(jié)對FSA*算法的有效性進(jìn)行驗證。分別設(shè)定安全系數(shù)α=1,3,5三種情況對算法進(jìn)行仿真，結(jié)果如圖2所示。由圖2可以看出，F(xiàn)SA*算法α較小的路徑會更加選擇圖中的安全區(qū)域(較明亮區(qū)域)。

然后對不同安全系數(shù)α情況下算法的性能表現(xiàn)做了對比，結(jié)果如表1所示。其中，累計安全距離的定義為該路徑上所有節(jié)點的累計EDM距離值，平均安全距離為累計安全距離除以路徑長度，用來表征該路徑的安全性。由表1可以看出，隨著安全系數(shù)α的增大，F(xiàn)SA*算法生成的路徑長度以及搜索時間逐漸變小，但路徑的安全距離也隨之下降，證明α可以調(diào)節(jié)算法的距離最優(yōu)性和安全最優(yōu)性，可以在平坦的區(qū)域增大α以增強算法的性能，而在危險的區(qū)域減小α來確保生成路徑的安全性。

表1 不同安全系數(shù)情況下算法的性能對比

3.3 算法性能對比

本節(jié)將FSA*算法(α=1)與標(biāo)準(zhǔn)A*算法、MHA*算法[19]、以及JPS算法[20]進(jìn)行對比，仿真條件均為3.1節(jié)所設(shè)定的仿真場景，各算法生成路徑如圖3所示。由圖3可以看出，相比于其他算法，F(xiàn)SA*算法搜索出的路徑會盡量選擇離障礙較遠(yuǎn)的安全區(qū)域，提高了探測路徑的安全性。

然后對這4種算法生成路徑的安全距離進(jìn)行了統(tǒng)計，結(jié)果如圖4所示?？梢钥闯鯢SA*算法生成路徑的安全距離明顯高于其他算法，可使巡視機器人在探測過程中盡量遠(yuǎn)離障礙區(qū)域，保證了自主探測過程的安全性。

然后在不同情況下對這些算法的性能表現(xiàn)進(jìn)行統(tǒng)計分析，在上述場景中隨機選取10組不同的起點終點位置(其中起點終點直線距離超過400 km)，統(tǒng)計他們的性能表現(xiàn)，結(jié)果如表2所示。

表2 不同算法的性能對比Table 2 Performance comparison of different algorithms

由表2結(jié)果對比可以看出，F(xiàn)SA*算法(α=1)累計安全距離以及平均安全距離明顯高于其他算法，搜索速度略低于JPS算法，高于標(biāo)準(zhǔn)A*算法及MHA*算法，說明FSA*在保證路徑安全性的基礎(chǔ)上縮短了算法的搜索時間。

4 結(jié) 論

1) 根據(jù)月面數(shù)字高程地圖提出一種地形可通過性分析方法，并生成了可通過性地圖和歐幾里得距離地圖(EDM)，用于大范圍安全路徑規(guī)劃。

2) 提出了FSA*(Fast-Safe A*)算法，改進(jìn)了A*算法的搜索機制以適用于大范圍地圖的快速路徑搜索，并結(jié)合EDM地圖設(shè)計了一種安全啟發(fā)式函數(shù)，可使生成路徑盡量遠(yuǎn)離危險區(qū)域，提高了巡視機器人自主探測過程的安全性，同時縮短了算法的搜索時間，提高了月面大范圍探測路徑規(guī)劃的效率與安全性。