弱全局信息下月面超遠距離保通行性移動規(guī)劃

郭繼峰，于曉強，王 平，余 歡，趙 毓

(1. 哈爾濱工業(yè)大學航天學院，哈爾濱 150001； 2. 北京空間飛行器總體設計部，北京 100094)

0 引 言

隨著行星探測技術的不斷發(fā)展及月球探測任務的逐漸深入，未來月球巡視器將面臨諸多大范圍、超遠距離(>1000 km)移動探測任務場景，如月球基地選址可行性勘探、不同著陸點或月球基地間的移動探測、月球廣域地質演變及資源分布的探測分析等，月球巡視器的超遠距離自主移動探測能力是實現(xiàn)未來月球復雜探測任務的基礎能力，具有很高的科學價值和應用價值[1-2]。世界各國針對具備遠距離移動探測能力的巡視器相繼開展了相關研究，美國NASA曾提出空間探索飛行器(Space exploration vehicle)[3]計劃，通過在輪式底盤上安裝小型增壓艙的設計，使航天員可以進行長途探測，而不受航天服的限制。美國噴氣推進實驗室提出的全地形六角形地形探測者計劃(All-terrain hex-limbed extra-terrestrial explorer, ATHLETE)[4]旨在開發(fā)一種六足/輪式月球巡視機器人，實現(xiàn)多模式下的全地形巡視，為大件貨物轉運及遠距離運輸提供支撐。日本宇宙航空研究開發(fā)機構(JAXA)和豐田汽車正在共同研發(fā)氫動力漫游車，以在少量可用能源支持下實現(xiàn)超過10000 km的超遠距離月球巡視，進而為后續(xù)月球基地建設提供可靠保障[5]。噴氣推進實驗室提出了“無畏號”(Intrepid)月球大范圍巡視任務[6]，目標是在四年內穿越1800 km月面區(qū)域來進行更大范圍、更深層次的月球科學探測。綜上可以看出，目前世界各國皆在開發(fā)具備超遠距離移動探測能力的月球巡視器。

月球巡視器的移動路徑規(guī)劃技術作為月球超遠距離探測任務中最重要的環(huán)節(jié)之一，其規(guī)劃出的路徑會直接影響月球超遠距離探測任務的執(zhí)行效率和成功率。相比于目前已有巡視器的考慮精確約束的小范圍路徑規(guī)劃技術[7-11]，針對月面超遠距離移動規(guī)劃問題仍缺乏較為系統(tǒng)、完備的技術體系，存在以下主要問題。

(1)無高精度地圖等全局精確信息

Intrepid大范圍探測任務雖然制定了上千公里的巡視路線，但其是針對探測特定區(qū)域規(guī)劃的固定路線，且有軌道探測器提供的極高分辨率地圖數(shù)據(jù)作為支撐[6]。而未來月球巡視器面臨的是任意起點/終點的超遠距離移動探測任務，且部分區(qū)域沒有高分辨率地圖數(shù)據(jù)等信息的支撐，而缺乏高精度地圖數(shù)據(jù)會使可行區(qū)域分析產生誤差，使巡視器陷入現(xiàn)有精度地圖無法發(fā)現(xiàn)的不可通行區(qū)域而導致超遠距離移動任務失敗。

(2)缺少路徑可通行性考慮

目前全局規(guī)劃算法著重于在一定評價標準下(如路徑長度最短、消耗能量最小等)求解出一條最優(yōu)路徑[12-15]，而缺乏對路徑可通行性和目標可達性的考慮。由于月面超遠距離探測任務的高代價及高風險性，對路徑的要求不單是路徑最短或時間最短，更要保證路徑的可通行性及探測目標地點的可達性，確保巡視器安全到達目標點是探測任務成功的必須，也是巡視器系統(tǒng)完備性的必要保證，需在規(guī)劃技術中著重考慮。

(3)規(guī)劃效率過低

當前全局規(guī)劃算法的共同缺點是規(guī)劃效率過低，尤其是針對超遠距離轉移任務中的路徑規(guī)劃問題，會消耗大量的搜索時間及計算資源，很難處理上千公里移動規(guī)劃這類超大規(guī)模問題。

綜上所述，目前全局規(guī)劃技術在解決月面超遠距離移動規(guī)劃問題時仍存在規(guī)劃完備性不足、缺少路徑可通行性考慮、規(guī)劃效率過低等諸多問題。受地面超遠距離移動規(guī)劃方式啟發(fā)，本文提出月面道路拓撲網(wǎng)的構建設想，擬憑借其復雜道路網(wǎng)絡的連通能力提高巡視器超遠距離移動規(guī)劃系統(tǒng)完備性和成功率。首先分析構建月面道路拓撲網(wǎng)的重要科學意義和應用價值，并進行月球道路拓撲網(wǎng)的設計構建方法研究，提出了滑動最優(yōu)泊松采樣算法進行網(wǎng)絡節(jié)點設計，可使生成的網(wǎng)絡節(jié)點分布均勻并確保道路網(wǎng)的密度適中且覆蓋完整；同時提出了均勻鄰域網(wǎng)絡模型作為網(wǎng)絡拓撲結構模型，并改進了A*算法的代價評估函數(shù)，連接各節(jié)點完成幾何結構設計，可以使網(wǎng)絡各路徑盡量遠離障礙區(qū)域，由此完成安全月面道路網(wǎng)的設計構建。然后進行基于月面道路網(wǎng)的路徑規(guī)劃，首先證明了基于月面道路拓撲網(wǎng)進行路徑規(guī)劃具有概率完備性，給出了影響完備性的因素，并分析了月面道路拓撲網(wǎng)的整體可通行概率，同時提出RPC-Dijkstra算法完成基于月面道路拓撲網(wǎng)的K優(yōu)路徑規(guī)劃，為超遠距離移動探測提供多條備選轉移路徑，可以提高巡視器超遠距離移動規(guī)劃系統(tǒng)的規(guī)劃效率和完備性。最后以Apollo 11和Apollo 12兩次登月任務著陸點之間進行超遠距離轉移任務為仿真場景，驗證本方法的有效性。

1 月面道路拓撲網(wǎng)的設計構建

月面道路拓撲網(wǎng)是指具備一定拓撲結構的互連互通的通行道路網(wǎng)，通過構建全月通行路網(wǎng)，可以實現(xiàn)巡視器在全月可達區(qū)域內的超遠距離移動路徑的規(guī)劃。相比于傳統(tǒng)規(guī)劃算法直接搜索大范圍轉移路徑，構建月面道路拓撲網(wǎng)進行轉移路徑規(guī)劃具有以下優(yōu)勢：

1)月面道路拓撲網(wǎng)可憑借其網(wǎng)絡連通能力為超遠距離移動規(guī)劃提供多條轉移路徑選擇，在某條路徑無法通行時，可基于道路網(wǎng)絡快速提供其他備選路徑。同時當月球巡視器移動過程中遇到地圖數(shù)據(jù)無法發(fā)現(xiàn)的不可通行區(qū)域時，可構建局部拓撲網(wǎng)絡來尋找繞行路徑，提高超遠距離移動探測的可通行概率，實現(xiàn)更加完備高效的月面超遠距離探測路徑規(guī)劃。

2)月面道路拓撲網(wǎng)構建完成后，由于月球地形環(huán)境基本不會發(fā)生變化，可長期用于大范圍探測路徑規(guī)劃，使月面道路拓撲網(wǎng)成為可以信任且永久使用的有效工具。同時可基于月面道路拓撲網(wǎng)進行某些重點探測區(qū)域間安全轉移通道的規(guī)劃構建，類似我國古代重要地理要塞“河西走廊”，以供世界各國巡視器移動探測使用。

3)通過道路網(wǎng)規(guī)劃超遠距離轉移路徑規(guī)劃速度明顯高于直接在大規(guī)模地圖上搜索轉移路徑，通過構建不同規(guī)模及不同密度的拓撲網(wǎng)絡，可實現(xiàn)不同范圍、不同粒度的自主探測路徑規(guī)劃。

對于在月面構建覆蓋全月的通行道路網(wǎng)，相比于地球構建的公路、鐵路等路網(wǎng)，月球具體月面環(huán)境未知，因此需要依靠分辨率有限的高程圖和影像圖進行地形分析。而相比于地球的城市作為路網(wǎng)的中途節(jié)點，月球目前沒有構建道路網(wǎng)所需的網(wǎng)絡節(jié)點，需要設計節(jié)點選取策略，要保證月面道路網(wǎng)節(jié)點盡量選在安全平坦區(qū)域，并且分布均勻，確保道路網(wǎng)的密度適中且覆蓋完整。同時由于月球部分地區(qū)地形地貌十分復雜，如月背、兩極等，因此需要構建安全道路網(wǎng)，確保超遠距離移動路徑的可行性和安全性。

綜上所述，本節(jié)提出月面道路拓撲網(wǎng)的設計構建方法，首先提出了滑動最優(yōu)泊松采樣算法，可選擇盡量平坦的區(qū)域中心作為構建路網(wǎng)所需的網(wǎng)絡節(jié)點，同時保證節(jié)點分布均勻且覆蓋完整，然后設計了均勻鄰域網(wǎng)絡模型作為網(wǎng)絡拓撲結構，并使用改進A*算法來連接各節(jié)點完成幾何結構設計，可以使道路網(wǎng)結構合理且連通性良好，網(wǎng)絡中路徑盡量遠離障礙區(qū)域，實現(xiàn)全月通行安全道路網(wǎng)的構建。

1.1 基于滑動最優(yōu)泊松采樣的網(wǎng)絡節(jié)點設計

本節(jié)對構建路網(wǎng)所需網(wǎng)絡節(jié)點的選取方法進行詳細介紹。首先需要保證構成道路拓撲網(wǎng)G=(,)的網(wǎng)絡節(jié)點集={v1,v2,…,vn}內,各節(jié)點要選在盡量平坦、遠離障礙的區(qū)域，來保證路網(wǎng)的安全性，同時節(jié)點需分布均勻又滿足對整個任務區(qū)域的覆蓋性。因此本節(jié)提出滑動最優(yōu)泊松采樣算法，通過設計固定大小的滑動窗口來計算任務區(qū)域內所有位置的可行區(qū)域覆蓋情況，并選擇滑動窗口內可行區(qū)域覆蓋率滿足設定的安全要求的位置作為備選節(jié)點位置來滿足節(jié)點安全性要求，在滿足覆蓋性要求的備選位置中做最優(yōu)泊松均勻采樣，得到分布均勻的采樣點作為構建路網(wǎng)所需的網(wǎng)絡節(jié)點。

泊松圓盤采樣(Poisson disc sampling)算法是一種平面隨機采樣算法[16]，生成的采樣點滿足隨機且分布均勻的特性，且各點之間的距離均不小于指定的最小距離。首先設定采樣點之間的最小距離為r，然后在采樣范圍內隨機生成一個活躍采樣點，在這個采樣點周圍的環(huán)形區(qū)域中再隨機生成k個候選采樣點，這個環(huán)形區(qū)域以該活躍采樣點為圓心，半徑從r延伸到2r。在這k個隨機候選采樣點中，剔除與已選定的采樣點距離小于r的點，剩下的作為新的活躍采樣點。如果這k個采樣點都被剔除了，沒有剩下任何可用的點，則將此環(huán)形區(qū)域圓心處的所選活躍采樣點標記為非活躍，不再用于生成候選項。在對候選采樣點剔除篩選時，使用了對角線長度為r的單元網(wǎng)格來加速距離檢查。每個單元網(wǎng)格最多只能包含一個采樣點，只需檢查候選采樣點周邊固定數(shù)量的相鄰單元網(wǎng)格即可。當所有采樣點均為非活躍狀態(tài)時，算法迭代結束。

圖1為矩形區(qū)域內一次隨機采樣和泊松圓盤采樣的結果對比。泊松圓盤采樣生成的點集既滿足隨機性又滿足均勻性，但這類方法有一個缺點是無法精確地控制采樣點的數(shù)目和質量，尤其在月面環(huán)境這種典型的多障礙場景，泊松圓盤采樣生成的點集無法保證節(jié)點是否處于可行區(qū)且盡量遠離障礙。

本節(jié)提出滑動最優(yōu)泊松圓盤采樣算法，首先在在月面可行區(qū)域地圖上設置一個邊長為Rw的正方形采樣窗口，采取滑動窗口的方法計算窗口內的可行區(qū)域覆蓋率，選擇所有可行覆蓋率超過90%的窗口區(qū)域作為備選采樣窗口，然后對所有備選窗口進行最優(yōu)泊松圓盤采樣得到網(wǎng)絡節(jié)點集。最優(yōu)泊松圓盤采樣即在采樣時選取可達區(qū)域覆蓋率最高的備選窗口中心位置作為新的采樣點，并根據(jù)設置的采樣半徑Rs進行節(jié)點活躍性檢測，將滿足條件的節(jié)點作為滑動最優(yōu)泊松采樣點?；瑒幼顑?yōu)泊松圓盤采樣算法可以保證可行區(qū)域覆蓋最優(yōu)性，可以使最終采樣得到的路網(wǎng)節(jié)點處于可行區(qū)域且盡量遠離障礙，算法流程如圖2所示。

圖2 滑動最優(yōu)泊松圓盤采樣算法流程Fig.2 Sliding optimal Poisson disk sampling algorithm flow

1.2 均勻最近鄰域網(wǎng)絡結構設計

月面道路拓撲網(wǎng)的網(wǎng)絡結構是將道路網(wǎng)以抽象復雜網(wǎng)絡的形式表達出來，從而進行復雜性的研究，通過拓撲結構能夠對道路結構的復雜性有直觀的認識理解。道路網(wǎng)結構一般分為拓撲結構和幾何結構，拓撲結構即對道路網(wǎng)二維空間布局性結構的一次抽象，就是把實體抽象成與其位置、形狀無關的“節(jié)點”，而把連接實體的道路抽象成“邊”，進而以圖的形式來表示這些點與邊之間關系，拓撲結構的重點在于研究節(jié)點之間的相連關系。而幾何結構表征的是點、線之間的位置關系，強調的是節(jié)點與邊的位置、所構成的形狀(大小)，幾何結構的重點包括道路長度、道路寬度、道路方向等多種幾何屬性的綜合影響分析。本節(jié)分別從拓撲結構和幾何結構兩方面進行月面道路拓撲網(wǎng)的結構設計。

(1)網(wǎng)絡拓撲結構設計

復雜網(wǎng)絡的結構可根據(jù)隨機性的增加由最近鄰域網(wǎng)絡等規(guī)則網(wǎng)絡逐漸向完全隨機網(wǎng)絡演化，而對于月面移動探測任務來說，由于需要根據(jù)地形約束設計安全、可靠、長久使用的道路拓撲網(wǎng)，需要將隨機性降到最低，因此需要采用規(guī)則網(wǎng)絡結構來進行網(wǎng)絡拓撲結構設計。本節(jié)提出了均勻最近鄰域網(wǎng)絡模型作為月面道路拓撲網(wǎng)的結構模型，具體定義如下。

定義1：均勻最近鄰域網(wǎng)絡模型

(1)

式中:vi,vj為節(jié)點vi,vj之間的平面歐氏距離;Rn為節(jié)點鄰域范圍，即每個節(jié)點只與距離其小于Rn的其他節(jié)點相連。

由前節(jié)滑動最優(yōu)泊松采樣算法可知，節(jié)點間的最小距離可由采樣半徑Rs控制，而相鄰節(jié)點間的最大距離可由節(jié)點鄰域范圍Rn控制，因此可通過設計合理的采樣半徑Rs以及節(jié)點鄰域范圍Rn完成道路拓撲網(wǎng)的拓撲網(wǎng)絡結構設計。通過調節(jié)采樣半徑Rs的大小，可以調節(jié)道路網(wǎng)的密度，適當?shù)牡缆肪W(wǎng)密度可以保證良好的月面區(qū)域可達性以及道路網(wǎng)的覆蓋面積，從而提高道路網(wǎng)的覆蓋效率。而節(jié)點鄰域范圍Rn決定了網(wǎng)絡的連接情況和基本結構，需要綜合考慮月面道路拓撲網(wǎng)的設計約束及需求進行分析設計。

(2)網(wǎng)絡幾何結構設計

對于道路拓撲網(wǎng)的幾何網(wǎng)絡結構，需要根據(jù)網(wǎng)絡節(jié)點的位置及拓撲關系來完成每條邊的設計構造，在此過程中需要考慮月面復雜地形環(huán)境，要確保道路拓撲網(wǎng)的轉移道路，即網(wǎng)絡的每條邊都處于月面可行區(qū)域，并避開月面主要地形障礙，因此道路拓撲網(wǎng)的網(wǎng)絡幾何結構設計問題即可轉化為節(jié)點間的路徑規(guī)劃問題。

本節(jié)提出一種連接各網(wǎng)絡節(jié)點形成安全月面道路網(wǎng)的路徑規(guī)劃方法。由于DEM地圖的柵格地圖特性以及月面巡視路徑規(guī)劃的最優(yōu)性要求，本文主要研究具有最優(yōu)性保證的啟發(fā)式圖搜索算法(A*算法)，改進了A*算法的代價評估函數(shù)，使其生成的路徑盡量遠離障礙區(qū)域，從而提高路網(wǎng)的安全性和可通過概率。

A*算法是一種啟發(fā)式圖搜索算法[17]，根據(jù)啟發(fā)式函數(shù)f(n)來指導搜索節(jié)點的擴展，f(n)=g(n)+h(n)，其中g(n)是從起點到節(jié)點n的路徑的確切代價，h(n)是節(jié)點n到目標點的剩余路徑代價估計。本節(jié)定義安全啟發(fā)式函數(shù)fsafe(n)來指導算法進行安全路徑搜索，具體定義如式(2)所示：

fsafe(n)=g(n)+ωsafe(n)+fDiag(n)

(2)

式中：ωsafe(n)為節(jié)點n的安全代價，定義為以節(jié)點n為中心的滑動窗口內的障礙總數(shù)量，安全代價越大說明節(jié)點n周圍障礙越多，其安全性越低；fDiag()為對角啟發(fā)式距離函數(shù)，也可替換為歐氏距離函數(shù)或其他滿足一致性條件的啟發(fā)式函數(shù)。通過使用改進A*算法規(guī)劃可連通節(jié)點間的安全路徑，可實現(xiàn)節(jié)點間的遠離障礙區(qū)域的路徑連接，完成全月通行安全道路網(wǎng)的構建。

2 基于月面道路拓撲網(wǎng)的超遠距離移動規(guī)劃

在月面道路拓撲網(wǎng)構建完成后，可依據(jù)路網(wǎng)實現(xiàn)超遠距離移動的全局路徑規(guī)劃。區(qū)別于傳統(tǒng)路徑規(guī)劃方法在進行路徑規(guī)劃時根據(jù)任務設定的最優(yōu)性指標規(guī)劃出一條由起點到終點的轉移路徑，這種方法缺少對目標點可達性和路徑可通行概率的考慮，無法確保月面超遠距離移動任務的成功。月面道路拓撲網(wǎng)可憑借其復雜網(wǎng)絡的連通能力和局部拓撲重構能力提高巡視器超遠距離移動系統(tǒng)完備性和成功性。本節(jié)首先證明了基于月面道路拓撲網(wǎng)進行路徑規(guī)劃具有概率完備性，并給出了影響完備性的因素，然后分析了月面道路拓撲網(wǎng)的可通行概率，提出了RPC-Dijkstra算法完成基于月面道路拓撲網(wǎng)的K優(yōu)路徑規(guī)劃，可為月面大范圍移動任務一次性提供多種路徑選擇，實現(xiàn)更加完備高效的超遠距離移動路徑規(guī)劃。

2.1 月面道路拓撲網(wǎng)規(guī)劃完備性分析

路徑規(guī)劃算法的完備性是指如果規(guī)劃空間中存在起點至終點的可行路徑，那么算法一定可以規(guī)劃出一條路徑，反之如果算法規(guī)劃失敗，說明空間中一定不存在可行路徑?；趫D搜索的算法(如A*算法)皆具有完備性，但完備性算法在超遠距離規(guī)劃場景中應用困難，因此有些算法放寬了完備性要求以換取更高的求解效率，如基于采樣的方法(RRT等)，此類算法具有概率完備性。概率完備性是指如果規(guī)劃空間中存在起點至終點的可行路徑，只要搜索或計算的時間夠長，那么算法一定可以規(guī)劃出一條路徑。本節(jié)將證明基于月面道路拓撲網(wǎng)的規(guī)劃方法具有概率完備性。

下面進行一些基本概念定義。對于離散化的地圖空間可行區(qū)域F，假設可行區(qū)域內存在一條由點A到點B的長度為L的路徑p[0:L]∈F，其中p(0)=A，p(L)=B，路徑p上的點距離其最近障礙的距離可表示為o(t),t∈[0,L]，對于可行路徑p來說，其距離障礙最小值Ro=mint∈[0,L]o(t)>0。

本節(jié)將從點A至點B之間存在可通行網(wǎng)絡的概率與網(wǎng)絡節(jié)點數(shù)量n的關系來分析月面道路拓撲網(wǎng)的概率完備性。首先給出以下定理。

定理1：假設存在一條由點A到點B的長度為L的路徑p[0:L]∈F，則基于網(wǎng)絡Gn無法在點A至點B間生成可行路徑的概率Pfail的上界可表示為：

(3)

式中：α=π/(4|F|)是一個常數(shù); |F|為任務空間可行區(qū)域面積;Ro為路徑p距離障礙的最小值;n為網(wǎng)絡節(jié)點數(shù)。

BRo/2(xi+1)?BRo(xi), ?i=0,…,n-1

(4)

圖3 沿路徑p構建圓示意圖Fig.3 Construct a circle diagram along path p

對于有n個節(jié)點的網(wǎng)絡Gn來說，若沿路徑p構建的x個圓BRo/2(pi),i=1,…,x，每個圓中均至少含有一個網(wǎng)絡節(jié)點，則這些節(jié)點及節(jié)點之間的邊均處于可行區(qū)域中，說明基于該網(wǎng)絡一定可以規(guī)劃出由點A到點B的可行路徑。若其中存在不包含網(wǎng)絡節(jié)點的圓，則基于該網(wǎng)絡的規(guī)劃有可能失敗。本節(jié)定義事件1：沿路徑p構建的x個圓BRo/2(pi),i=1,…,x，中存在不包含網(wǎng)絡Gn節(jié)點的圓的概率為P1，事件2：圓BRo/2(pi)中不包含任一網(wǎng)絡Gn節(jié)點的概率為P2。由于網(wǎng)絡Gn的節(jié)點{v1,v2,…,vn}所處位置相互獨立，因此有：

P2=[1-SBRo/2(pi)/(|F|)]n=

(5)

則基于網(wǎng)絡Gn在點A至點B間規(guī)劃失敗的概率Pfail，有：

(6)

而基于如下式所示的不等式關系：

1-x≤exp(-x), ?x≥0

(7)

可將式(6)轉化為

(8)

定理1證畢。

由定理1可得，基于月面道路拓撲網(wǎng)在兩點間搜索出可行路徑的成功概率Psucc滿足：

1-a·exp(-bn)

(9)

(1)規(guī)劃距離，即可行路徑長度L，規(guī)劃距離越長，整體任務難度越高，規(guī)劃成功率越低。

(2)環(huán)境復雜度，即可行路徑距離障礙的最小值Ro，Ro越小，環(huán)境復雜度越高，規(guī)劃成功率越低。

(3)網(wǎng)絡節(jié)點數(shù)，網(wǎng)絡節(jié)點數(shù)越多，對整個任務區(qū)域的覆蓋性就越強，基于該網(wǎng)絡規(guī)劃的成功率就越高。

綜上，對于一個確定的規(guī)劃環(huán)境或規(guī)劃任務，其規(guī)劃距離及環(huán)境復雜度是固定的，即使對于未知動態(tài)的任務其也是一個有界的數(shù)值，而網(wǎng)絡節(jié)點數(shù)可以根據(jù)任務動態(tài)調整，且基于月面道路拓撲網(wǎng)規(guī)劃成功的概率隨網(wǎng)絡節(jié)點數(shù)增加而增加，極限條件下當網(wǎng)絡密度足夠大時，可保證基于月面道路拓撲網(wǎng)的路徑規(guī)劃成功率趨近于1，因此利用月面道路拓撲網(wǎng)進行月面超遠距離移動路徑規(guī)劃具有概率完備性。

2.2 月面道路拓撲網(wǎng)可通行概率分析

月面地形條件是影響路徑可通行性最重要的因素，在保證地形特征提取精度精準可靠的條件下，可以直接依靠計算提取的地形特征進行路徑可通行性分析。由于DEM地圖是獲取月面地形特征的主要方式，而目前可公開獲取的具有較高分辨率及數(shù)據(jù)精度的全月數(shù)據(jù)集主要包括中國嫦娥二號拍攝形成的CE2TMap2015全月數(shù)據(jù)集以及美國SLDEM全月數(shù)據(jù)集，其最大分辨率分別為20 m及59 m，該分辨率地圖不足以獲取月面精細準確的地形特征，使用有限分辨率DEM地圖計算得到的地形特征及可通行區(qū)域等信息會存在一定誤差，因此需要針對不同分辨率地圖分析不同區(qū)域的地形計算誤差及可通行概率。

本節(jié)首先分析單條路徑的可通行概率，其可以表示為該路徑途徑的月面區(qū)域的最小可通行概率，而月面不同區(qū)域的可通行概率將主要考慮該區(qū)域坡度的影響，坡度越小，可通過性越高，但同時還需要考慮使用不同分辨率DEM地圖進行地形提取所帶來的誤差的影響，誤差越大，對地形描述越不準確，將會一定程度上降低地形的可通過概率。因此需要對有限分辨率DEM地圖下的坡度計算誤差進行分析。

月面地形特征提取精度與DEM地圖誤差及分辨率直接相關，而DEM地圖誤差固定且連續(xù)，對地形特征提取影響不大，但DEM分辨率不同，所提取的地形特征也會發(fā)生改變，從而對地形特征分析造成一定的影響?，F(xiàn)有文獻研究表明，以坡度為例，根據(jù)不同分辨率DEM地圖提取的坡度數(shù)據(jù)，隨著DEM地圖分辨率的降低，每個分辨率包含的地形信息更加概括，對不同區(qū)域地形細節(jié)的表達能力逐漸降低，坡度提取誤差會逐漸增大。文獻[18]對平均坡度與DEM地圖分辨率間的關系進行分析，結果表明，針對所有地形，隨著分辨率降低地形平均誤差(記作Ea)均增大，并且地形起伏程度越高，這種增加越明顯，說明分辨率降低總體造成坡度的誤差數(shù)值增大。該文獻根據(jù)在黃土高原試驗樣區(qū)高程數(shù)據(jù)采樣并對Ea誤差進行了回歸分析，得到Ea誤差與DEM分辨率及平均坡度的關系模型如下所示：

Ea=(0.514s-0.002)ln(r)-(0.285s+0.004)

(10)

式中:r為DEM分辨率；s為分析區(qū)域的平均坡度。由此可得地形平均誤差與DEM分辨率與區(qū)域平均坡度之間的對應關系。

本節(jié)將某分辨率地圖中某柵格的可通行概率Ptrans(i)建模為該柵格內真實地形全部滿足巡視器運動能力的概率，首先將柵格內真實地形分布建模為正態(tài)分布，均值μi為該分辨率地圖計算的地形坡度，標準差為該區(qū)域該分辨率地圖對應的地形計算誤差，建立該分布后，計算該柵格內坡度全部小于巡視器最大爬坡能力smax的概率即為該柵格的可通行概率。

(11)

在分析完單條月面規(guī)劃路徑的可通行概率后，可進行月面道路拓撲網(wǎng)的整體可通行概率分析。對于網(wǎng)絡G及其任意兩個節(jié)點對vi，vj之間存在的可行路徑數(shù)量Nij，假設每條路徑均存在一個通行概率Ptrans(i)，則可采用概率分析理論計算月面道路拓撲網(wǎng)任意節(jié)點對vi，vj之間的可通行概率Ptrans(i, j)如下式所示：

(12)

式中：Ptrans(i)∈[0,1]為月面道路拓撲網(wǎng)中節(jié)點對vi，vj之間的每條路徑的可通行概率。

對于網(wǎng)絡G，網(wǎng)絡內任意兩個節(jié)點對vi，vj之間存在的可行路徑數(shù)量為[19]：

(13)

式中：lmax為節(jié)點vi，vj之間最長可行路徑限制，可人為設定或根據(jù)網(wǎng)絡節(jié)點數(shù)量計算。

下面分析網(wǎng)絡節(jié)點數(shù)量及網(wǎng)絡邊數(shù)對可行路徑數(shù)量的影響。當網(wǎng)絡節(jié)點數(shù)量n增加時，其鄰接矩陣A內的非零元素增加，Nij增大。對于網(wǎng)絡G，令網(wǎng)絡G′表示對網(wǎng)絡G中隨機增加一條邊e后的網(wǎng)絡，則網(wǎng)絡G′中任意兩個節(jié)點對vi，vj之間存在的可行路徑數(shù)量Nij(G′) =Nij(G)+N′ij，其中，Nij(G)是不經(jīng)過邊e的可行路徑數(shù)量，即沒有添加邊e的原網(wǎng)絡G的路徑數(shù)量，N′ij為節(jié)點對vi，vj之間經(jīng)過邊e的可行路徑數(shù)量，顯然N′ij≥0，因此網(wǎng)絡任意兩節(jié)點間可行路徑數(shù)量滿足網(wǎng)絡節(jié)點數(shù)量及邊數(shù)量的單調性。

因此月面道路拓撲網(wǎng)任意節(jié)點對vi，vj之間的可通行概率Ptrans(i, j)與節(jié)點間可行路徑的數(shù)量成正比，即Nij越大，總體可達性Ptrans(i, j)越大，而可行路徑的數(shù)量Nij與網(wǎng)絡節(jié)點數(shù)量n，網(wǎng)絡邊數(shù)皆成正比。由此可見，基于月面道路拓撲網(wǎng)進行月面超遠距離路徑規(guī)劃相比于傳統(tǒng)單條最優(yōu)路徑規(guī)劃方法可提高路徑的可通行概率，同時在網(wǎng)絡密度變大時，即網(wǎng)絡節(jié)點和邊的數(shù)量增加時，月面道路拓撲網(wǎng)的可通行概率增加，極限條件下當網(wǎng)絡密度足夠大時，可保證月面道路拓撲網(wǎng)的整體可通行概率趨近于1，也間接證明了利用月面道路拓撲網(wǎng)進行月面超遠距離移動路徑規(guī)劃具有概率完備性。

2.3 考慮重復路徑代價的K優(yōu)路徑規(guī)劃

本節(jié)進行基于月面道路拓撲網(wǎng)進行超遠距離探測K優(yōu)路徑規(guī)劃的方法研究。首先進行K優(yōu)路徑規(guī)劃問題的定義，設Pij是網(wǎng)絡G中節(jié)點vi和vj間所有可行路徑的集合，則最優(yōu)路徑規(guī)劃問題的定義就是在Pij中尋找一條距離最小的路徑p′，即在網(wǎng)絡G中尋找一條路徑p′，滿足p′∈Pij，且對于任意路徑p∈Pij,p≠p′，都有路徑長度dp′≤dp。而K優(yōu)路徑規(guī)劃問題是最優(yōu)路徑規(guī)劃問題的擴展，目的是尋找包括最短路徑、次短路徑直至第k短路徑的集合，即在網(wǎng)絡G中尋找路徑集合P′={p′1,p′2,…,p′k}，滿足P′∈Pij，且對于任意路徑p∈Pij,p?P′，都有dp′i≤dp，同時對于1≤i≤k，有dp′i≤dp′i+1。

對于無向圖中從一個頂點到其余各頂點的最短路徑規(guī)劃問題，可使用Dijkstra算法[19]進行求解。經(jīng)典Dijkstra一次只能搜索出一條起點至終點的最短路徑，為了求解無向加權圖G中的K優(yōu)路徑規(guī)劃問題，本節(jié)提出基于重復路徑代價Dijkstra (Repea-ted path cost Dijkstra, RPC-Dijkstra)的K優(yōu)路徑規(guī)劃算法，引入路徑重復度及重復路徑代價因子的概念，在最優(yōu)路徑規(guī)劃完成后，將與最優(yōu)路徑重復的路徑段增加重復路徑代價，使無向圖中重復路段對應邊的權重增加，從而使算法再進行次優(yōu)路徑規(guī)劃時產生與最優(yōu)路徑差異化的路徑結果，為超遠距離移動探測提供多條備選轉移路徑。

RPC-Dijkstra求解流程如圖4所示，首先基于原權重圖G利用Dijkstra算法規(guī)劃最優(yōu)路徑，將此最優(yōu)路徑加入K優(yōu)路徑集合P′，然后為當前最優(yōu)路徑添加重復路徑代價，將最優(yōu)路徑途徑邊的權值乘以重復路徑代價因子ωRP(ωRP>1)，根據(jù)權值更新后的圖G規(guī)劃下一最優(yōu)路徑p′i+1，然后計算p′i+1與路徑集合P′中路徑的重復度。本節(jié)定義圖G中路徑pi相對于pj的路徑重復度Rij為pi和pj相同邊的數(shù)量與路徑pj長度的比值，代表兩條路徑的重復情況。若路徑p′i+1與集合P′中路徑的重復度均滿足要求，即均小于設定的最大重復度，則將此路徑p′i+1加入P′，然后繼續(xù)增加重復路徑代價，直至找出全部k條最優(yōu)路徑。

圖4 RPC-Dijkstra算法求解流程Fig.4 Solution flow of RPC Dijkstra algorithm

此外，由于月面道路拓撲網(wǎng)是基于分辨率有限的DEM地圖構建，不能保證巡視器在真實轉移過程中全程路徑的可行性，如基于超遠距離全局規(guī)劃結果轉移途中發(fā)現(xiàn)實際不可通行區(qū)域，則需要轉移路線的重規(guī)劃，通過在無法通行點至下一網(wǎng)絡節(jié)點之間通過構建密度更大的局部拓撲網(wǎng)絡，可對月面道路拓撲網(wǎng)進行更新，生成新的可通行路徑，這樣即可快速實現(xiàn)轉移路徑重規(guī)劃，避免重新搜索超遠距離全局路徑，極大的縮小了重規(guī)劃所需的時間及計算資源。

3 仿真校驗分析

3.1 仿真場景

本文擬在Apollo 11和12兩次登月任務的著陸點之間進行超遠距離轉移任務，選取Apollo 11及Apollo 12兩次任務的著陸點作為超遠距離移動探測任務的起止點。首先獲取任務區(qū)域的DEM數(shù)據(jù)，由于嫦娥二號全月地形數(shù)據(jù)產品在空間分辨率、全月覆蓋率、定位精度和地貌結構細節(jié)表達等方面相比其他全月地形數(shù)據(jù)具有明顯優(yōu)勢[21]，所以本文采用嫦娥二號CE2TMap2015數(shù)據(jù)產品中的DEM-50 m數(shù)據(jù)集進行月面可達區(qū)域分析，分析區(qū)域面積達2207.2 km×871.3 km。提取任務區(qū)域高程信息如圖5所示。

圖5 Apollo任務區(qū)域DEM地圖Fig.5 DEM map of the Apollo mission area

3.2月面道路拓撲網(wǎng)構建仿真

下面對月面道路拓撲網(wǎng)構建方法進行仿真分析。首先對該任務區(qū)域進行最優(yōu)泊松圓盤采樣，選取構建路網(wǎng)所需網(wǎng)絡節(jié)點，設置采樣滑動窗口大小為20 km×20 km，設置采樣半徑Rs=30 km，阿波羅任務區(qū)域進行網(wǎng)絡節(jié)點選取結果及其泊松圓盤覆蓋情況如圖6所示，共采樣網(wǎng)絡節(jié)點668個，采樣節(jié)點窗口內可達區(qū)域覆蓋率最高100%，最低95.2%。由圖6可以看出，網(wǎng)絡節(jié)點基本處于安全平坦區(qū)域，最優(yōu)泊松圓盤采樣結果密度適中且對整個任務區(qū)域覆蓋性很好，使得路網(wǎng)的覆蓋效率達到最大。

然后進行月面道路拓撲網(wǎng)的結構設計仿真，基于本文所提出的網(wǎng)絡拓撲結構及幾何結構設計方法進行網(wǎng)絡結構設計。本節(jié)設置節(jié)點鄰域范圍Rn= 45 km。同時設置改進A*算法的安全代價函數(shù)的窗口大小為1 km×1 km，即算法的安全代價權重考慮該范圍內的障礙總數(shù)量，在阿波羅任務區(qū)域路網(wǎng)構建結果如圖7所示，網(wǎng)絡參數(shù)統(tǒng)計信息如表1所示，可以看出，本文構建的月面道路拓撲網(wǎng)可以完整覆蓋Apollo任務區(qū)域，網(wǎng)絡連通性良好，可以保證較高的月面區(qū)域可達性以及網(wǎng)絡覆蓋效率。同時，基于月面道路拓撲網(wǎng)的轉移路徑會盡量遠離多障礙區(qū)域，從而提高了路網(wǎng)的安全性和可通過概率。

圖7 Apollo任務區(qū)域月面道路拓撲網(wǎng)構建結果Fig.7 Results of safety road network construction in the Apollo mission area

表1 月面道路拓撲網(wǎng)網(wǎng)絡參數(shù)統(tǒng)計Table 1 Statistics of lunar road topology network parameters

3.3 基于月面道路拓撲網(wǎng)超遠距離路徑規(guī)劃仿真

本節(jié)進行基于月面道路拓撲網(wǎng)的超遠距離路徑規(guī)劃仿真，在路網(wǎng)中進行最優(yōu)路徑搜索，選取Apollo 11和Apollo 12兩次任務著陸點為仿真的起點終點，模擬超遠距離移動路徑規(guī)劃任務。設置最優(yōu)路徑數(shù)量k=5，重復路徑代價因子ωRP=1.2，最大可接受路徑重復度為80%，所得K優(yōu)路徑規(guī)劃結果如圖8所示，指標參數(shù)對比如表2所示，可以看出RPC-Dijkstra算法能夠實現(xiàn)基于月面道路網(wǎng)的K優(yōu)路徑規(guī)劃，5條路徑在路徑長度、窗口可行區(qū)域覆蓋率及可通行概率方面各有優(yōu)勢，綜合考慮5條路徑的整體可通行概率為99.99%，可保證超遠距離移動路徑的安全性及可通行性。

圖8 Apollo任務區(qū)域超遠距離路徑規(guī)劃結果Fig.8 Large scale path planning results of the Apollo mission area

表2 K優(yōu)路徑規(guī)劃路徑指標參數(shù)對比Table 2 Path index comparison of K-optimal path planning

然后以路徑1為例，本節(jié)對超遠距離移動規(guī)劃路徑的全路程坡度信息及路徑節(jié)點窗口內障礙區(qū)域覆蓋率進行統(tǒng)計處理，結果如圖8及圖9所示，圖中陰影部分為原始數(shù)據(jù)，實線為經(jīng)過平滑后的數(shù)據(jù)?？梢钥闯龌谠旅娴缆吠負渚W(wǎng)規(guī)劃的移動路徑整體坡度較為平緩，全程坡度最大值約為10°，且路徑全程1 km×1 km窗口內障礙覆蓋率很低，在中段及后段高原區(qū)域的障礙覆蓋率有所增長，但整體障礙覆蓋率在5%以下，說明本文所構建月面道路拓撲網(wǎng)可以實現(xiàn)移動路徑遠離多障礙區(qū)域，從而提高超遠距離移動探測的安全性及可通過概率。

圖9 月面道路網(wǎng)規(guī)劃路徑的坡度變化信息Fig.9 Slope change information of planned path of lunar road network

圖10 月面道路網(wǎng)規(guī)劃路徑的障礙覆蓋率Fig.10 Obstacle coverage of planned path of lunar road network

本節(jié)同時將基于月面道路拓撲網(wǎng)的路徑規(guī)劃與標準A*算法、JPS算法[22]進行了性能對比，結果如表3所示。可以看出，基于月面道路拓撲網(wǎng)的路徑規(guī)劃雖然路徑長度略高于其他兩個算法，但路徑平均坡度及平均障礙區(qū)域覆蓋率明顯優(yōu)于其他算法，表明月面道路拓撲網(wǎng)的構建可以提高超遠距離移動路徑的安全性。同時，由于本節(jié)是基于已經(jīng)構建完成的月面道路拓撲網(wǎng)的路徑規(guī)劃，路徑搜索時間明顯優(yōu)于其他算法，可以極大提高超遠距離全局路徑搜索的計算效率。

表3 不同算法的性能表現(xiàn)對比Table 3 Performance comparison of different algorithms

4 結 論

本文基于月面道路拓撲網(wǎng)的構建設想提出了一種弱全局信息下月面超遠距離保通行性移動規(guī)劃技術，得出以下主要結論：

1) 提出了月面道路拓撲網(wǎng)的構建設想，分別針對節(jié)點及結構設計提出了網(wǎng)絡設計方法，仿真結果表明本文構建的道路網(wǎng)密度適中且對整個任務區(qū)域覆蓋性很好，網(wǎng)絡中各移動路徑會盡量遠離多障礙區(qū)域，從而提高了月面道路網(wǎng)的安全性和可通過概率。

2) 進行了基于月面道路拓撲網(wǎng)的超遠距離保通過性路徑規(guī)劃，首先證明道路網(wǎng)規(guī)劃的概率完備性，并分析了月面道路網(wǎng)整體可通行概率，同時提出了RPC-Dijkstra算法實現(xiàn)基于道路網(wǎng)的K優(yōu)路徑規(guī)劃。仿真表明基于月面道路拓撲網(wǎng)可實現(xiàn)上千公里級的月面探測路徑規(guī)劃，網(wǎng)絡可通行概率明顯高于單條路徑，同時路徑的安全性和搜索時間明顯優(yōu)于其他算法。

本文旨在通過月面道路拓撲網(wǎng)的設計構建實現(xiàn)更加安全完備的月面超遠距離移動探測任務，具有重要的概念創(chuàng)新和理論研究意義，有一定的工程應用潛力，可為未來月球探測任務提供有價值的發(fā)展建設思路。