郭繼峰，于曉強(qiáng)，王 平，余 歡，趙 毓

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

0 引 言

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

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

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

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

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

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

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

當(dāng)前全局規(guī)劃算法的共同缺點(diǎn)是規(guī)劃效率過低，尤其是針對(duì)超遠(yuǎn)距離轉(zhuǎn)移任務(wù)中的路徑規(guī)劃問題，會(huì)消耗大量的搜索時(shí)間及計(jì)算資源，很難處理上千公里移動(dòng)規(guī)劃這類超大規(guī)模問題。

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

1 月面道路拓?fù)渚W(wǎng)的設(shè)計(jì)構(gòu)建

月面道路拓?fù)渚W(wǎng)是指具備一定拓?fù)浣Y(jié)構(gòu)的互連互通的通行道路網(wǎng)，通過構(gòu)建全月通行路網(wǎng)，可以實(shí)現(xiàn)巡視器在全月可達(dá)區(qū)域內(nèi)的超遠(yuǎn)距離移動(dòng)路徑的規(guī)劃。相比于傳統(tǒng)規(guī)劃算法直接搜索大范圍轉(zhuǎn)移路徑，構(gòu)建月面道路拓?fù)渚W(wǎng)進(jìn)行轉(zhuǎn)移路徑規(guī)劃具有以下優(yōu)勢(shì)：

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

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

3)通過道路網(wǎng)規(guī)劃超遠(yuǎn)距離轉(zhuǎn)移路徑規(guī)劃速度明顯高于直接在大規(guī)模地圖上搜索轉(zhuǎn)移路徑，通過構(gòu)建不同規(guī)模及不同密度的拓?fù)渚W(wǎng)絡(luò)，可實(shí)現(xiàn)不同范圍、不同粒度的自主探測(cè)路徑規(guī)劃。

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

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

1.1 基于滑動(dòng)最優(yōu)泊松采樣的網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)計(jì)

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

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

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

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

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

1.2 均勻最近鄰域網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)

月面道路拓?fù)渚W(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)是將道路網(wǎng)以抽象復(fù)雜網(wǎng)絡(luò)的形式表達(dá)出來(lái)，從而進(jìn)行復(fù)雜性的研究，通過拓?fù)浣Y(jié)構(gòu)能夠?qū)Φ缆方Y(jié)構(gòu)的復(fù)雜性有直觀的認(rèn)識(shí)理解。道路網(wǎng)結(jié)構(gòu)一般分為拓?fù)浣Y(jié)構(gòu)和幾何結(jié)構(gòu)，拓?fù)浣Y(jié)構(gòu)即對(duì)道路網(wǎng)二維空間布局性結(jié)構(gòu)的一次抽象，就是把實(shí)體抽象成與其位置、形狀無(wú)關(guān)的“節(jié)點(diǎn)”，而把連接實(shí)體的道路抽象成“邊”，進(jìn)而以圖的形式來(lái)表示這些點(diǎn)與邊之間關(guān)系，拓?fù)浣Y(jié)構(gòu)的重點(diǎn)在于研究節(jié)點(diǎn)之間的相連關(guān)系。而幾何結(jié)構(gòu)表征的是點(diǎn)、線之間的位置關(guān)系，強(qiáng)調(diào)的是節(jié)點(diǎn)與邊的位置、所構(gòu)成的形狀(大小)，幾何結(jié)構(gòu)的重點(diǎn)包括道路長(zhǎng)度、道路寬度、道路方向等多種幾何屬性的綜合影響分析。本節(jié)分別從拓?fù)浣Y(jié)構(gòu)和幾何結(jié)構(gòu)兩方面進(jìn)行月面道路拓?fù)渚W(wǎng)的結(jié)構(gòu)設(shè)計(jì)。

(1)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)

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

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

(1)

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

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

(2)網(wǎng)絡(luò)幾何結(jié)構(gòu)設(shè)計(jì)

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

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

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

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

(2)

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

2 基于月面道路拓?fù)渚W(wǎng)的超遠(yuǎn)距離移動(dòng)規(guī)劃

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

2.1 月面道路拓?fù)渚W(wǎng)規(guī)劃完備性分析

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

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

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

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

(3)

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

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

(4)

圖3 沿路徑p構(gòu)建圓示意圖Fig.3 Construct a circle diagram along path p

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

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

(5)

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

(6)

而基于如下式所示的不等式關(guān)系：

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

(7)

可將式(6)轉(zhuǎn)化為

(8)

定理1證畢。

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

1-a·exp(-bn)

(9)

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

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

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

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

2.2 月面道路拓?fù)渚W(wǎng)可通行概率分析

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

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

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

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

(10)

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

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

(11)

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

(12)

式中：Ptrans(i)∈[0,1]為月面道路拓?fù)渚W(wǎng)中節(jié)點(diǎn)對(duì)vi，vj之間的每條路徑的可通行概率。

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

(13)

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

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

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

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

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

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

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

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

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

3 仿真校驗(yàn)分析

3.1 仿真場(chǎng)景

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

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

3.2月面道路拓?fù)渚W(wǎng)構(gòu)建仿真

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

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

圖7 Apollo任務(wù)區(qū)域月面道路拓?fù)渚W(wǎng)構(gòu)建結(jié)果Fig.7 Results of safety road network construction in the Apollo mission area

表1 月面道路拓?fù)渚W(wǎng)網(wǎng)絡(luò)參數(shù)統(tǒng)計(jì)Table 1 Statistics of lunar road topology network parameters

3.3 基于月面道路拓?fù)渚W(wǎng)超遠(yuǎn)距離路徑規(guī)劃仿真

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

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

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

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

圖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é)同時(shí)將基于月面道路拓?fù)渚W(wǎng)的路徑規(guī)劃與標(biāo)準(zhǔn)A*算法、JPS算法[22]進(jìn)行了性能對(duì)比，結(jié)果如表3所示。可以看出，基于月面道路拓?fù)渚W(wǎng)的路徑規(guī)劃雖然路徑長(zhǎng)度略高于其他兩個(gè)算法，但路徑平均坡度及平均障礙區(qū)域覆蓋率明顯優(yōu)于其他算法，表明月面道路拓?fù)渚W(wǎng)的構(gòu)建可以提高超遠(yuǎn)距離移動(dòng)路徑的安全性。同時(shí)，由于本節(jié)是基于已經(jīng)構(gòu)建完成的月面道路拓?fù)渚W(wǎng)的路徑規(guī)劃，路徑搜索時(shí)間明顯優(yōu)于其他算法，可以極大提高超遠(yuǎn)距離全局路徑搜索的計(jì)算效率。

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

4 結(jié) 論

本文基于月面道路拓?fù)渚W(wǎng)的構(gòu)建設(shè)想提出了一種弱全局信息下月面超遠(yuǎn)距離保通行性移動(dòng)規(guī)劃技術(shù)，得出以下主要結(jié)論：

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

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

本文旨在通過月面道路拓?fù)渚W(wǎng)的設(shè)計(jì)構(gòu)建實(shí)現(xiàn)更加安全完備的月面超遠(yuǎn)距離移動(dòng)探測(cè)任務(wù)，具有重要的概念創(chuàng)新和理論研究意義，有一定的工程應(yīng)用潛力，可為未來(lái)月球探測(cè)任務(wù)提供有價(jià)值的發(fā)展建設(shè)思路。