基于狀態(tài)差異的火星巡視器快速任務(wù)規(guī)劃修復(fù)方法

陳 超，徐 瑞，李朝玉

（1.北京理工大學(xué) 宇航學(xué)院，北京 100081；2.深空自主導(dǎo)航與控制工信部重點實驗室，北京 100081）

引 言

由于距離地球遙遠(yuǎn)，火星探測器與地面站之間的通信存在3～20 min的長時延，嚴(yán)重影響著任務(wù)的成敗?；鹦翘綔y器需具備高度的自主能力，例如高增益天線的自主指向、利用星敏進(jìn)行姿態(tài)校準(zhǔn)、在線數(shù)據(jù)的存儲與轉(zhuǎn)發(fā)，以及在時間和資源約束條件下活動的合理安排等[1]，以降低地面依賴性、縮短任務(wù)周期。自主任務(wù)規(guī)劃技術(shù)可實現(xiàn)這一目標(biāo)[2]。現(xiàn)有文獻(xiàn)已經(jīng)從動作[3]、資源[4]、時間線[5]等多個角度對自主任務(wù)規(guī)劃技術(shù)進(jìn)行研究。但目前人類對火星的認(rèn)知不全面，火星表面地形的變化、土壤的堅硬程度、巖石的大小等仍存在極大的不確知性，影響著巡視器執(zhí)行任務(wù)的時間長短、消耗能量以及存儲空間大小等，嚴(yán)重制約著既定規(guī)劃的成功執(zhí)行。例如，“探路者號”（Pathfinder）任務(wù)中的“索杰納號”（Sojourner）巡視器就因為在先驗規(guī)劃過程中沒有充分考慮到這些不確定性因素的影響，整個任務(wù)中大約有70%的時間處于閑置狀態(tài)[6]。此外，風(fēng)沙等突發(fā)事件、電子器件故障等意外事件，都會對任務(wù)的成功執(zhí)行造成巨大威脅。因此，火星巡視器不僅需要具備任務(wù)規(guī)劃能力，自主管理日?；顒?，更需要具備任務(wù)規(guī)劃修復(fù)能力，自主應(yīng)對執(zhí)行過程中出現(xiàn)的執(zhí)行失敗情況，以增強自身的魯棒性，提高任務(wù)回報率。

在應(yīng)對突發(fā)事件導(dǎo)致任務(wù)規(guī)劃執(zhí)行失敗的問題方面，存在兩種策略：完全重規(guī)劃和規(guī)劃修復(fù)[7]。其中，完全重規(guī)劃是指放棄已有的規(guī)劃結(jié)果，重新決策出一個新的動作序列來完成任務(wù)目標(biāo)，而規(guī)劃修復(fù)是指通過增、刪、替換、移動等操作，對已有規(guī)劃結(jié)果進(jìn)行修補來達(dá)成任務(wù)目標(biāo)。雖然規(guī)劃修復(fù)在理論上不一定比完全重規(guī)劃簡單[8]，但大量的仿真實驗表明規(guī)劃修復(fù)效率更高[9-12]。Scala等[13]基于巡視器動作模式的多樣性，采用約束滿足問題（Constraint Satisfaction Problem，CSP）求解技術(shù)，在規(guī)劃執(zhí)行失敗時，通過動作模式重構(gòu)完成任務(wù)規(guī)劃修復(fù)。但是該方法不改變動作順序及類型，無法處理一般的規(guī)劃執(zhí)行失敗問題。Gallien等[14]將執(zhí)行階段設(shè)計成感知–修復(fù)–行動三階段的循環(huán)過程，對執(zhí)行任務(wù)過程中出現(xiàn)的錯誤，在限定時間內(nèi)采用規(guī)劃器推理得出相應(yīng)的解，用于解決執(zhí)行失敗的問題。但是該方法采用偏序規(guī)劃方法，效率較低。Guzman等[15]提出響應(yīng)式規(guī)劃（Reactive Plan，RP）方法，為執(zhí)行體設(shè)計了一個響應(yīng)式規(guī)劃器，通過與任務(wù)規(guī)劃器互相配合，并采用修復(fù)結(jié)構(gòu)樹來提高規(guī)劃修復(fù)的速度。但是修復(fù)結(jié)構(gòu)樹的長度和深度需要通過機器學(xué)習(xí)獲得，不能普遍適用于所有情況；并且即使修復(fù)結(jié)構(gòu)樹只包含少量動作，其中也會包含大量無用節(jié)點，這樣會造成存儲空間和搜索時間的浪費。

針對巡視器在火星表面執(zhí)行任務(wù)過程中由環(huán)境不確定性和自身設(shè)備故障等引起的規(guī)劃執(zhí)行失敗問題，本文提出了一種基于狀態(tài)差異的規(guī)劃修復(fù)方法（State Difference Plan Repair，RPDS），使巡視器能夠迅速從失敗中恢復(fù)正常。與響應(yīng)式規(guī)劃方法RP不同的是，本文不提前構(gòu)建修復(fù)結(jié)構(gòu)樹以輔助規(guī)劃修復(fù)，而是在執(zhí)行失敗后，利用不同狀態(tài)之間的差異，有目的地生成搜索節(jié)點，并對擴展的節(jié)點根據(jù)謂詞沖突進(jìn)行篩選，從而刪減搜索空間，加快巡視器規(guī)劃修復(fù)的速度。

本文的結(jié)構(gòu)組織如下：第一部分構(gòu)建火星巡視器任務(wù)模型并引出部分狀態(tài)的概念，為后續(xù)的方法描述奠定基礎(chǔ)。第二部分提出基于部分狀態(tài)的火星巡視器快速任務(wù)規(guī)劃修復(fù)策略，為第三部分描述基于實際狀態(tài)與部分狀態(tài)之間的差異而設(shè)計的搜索空間刪減方法建好框架。第四部分給出仿真測試結(jié)果和分析。最后給出本文結(jié)論。

1 火星巡視器任務(wù)模型

自主任務(wù)規(guī)劃屬于高層次的智能決策，在給定初始狀態(tài)下找到滿足約束并且能夠完成任務(wù)目標(biāo)的動作序列的一種技術(shù)[16]。本文假設(shè)火星巡視器的姿態(tài)、導(dǎo)航等系統(tǒng)具備一定自主能力，在接收各自的任務(wù)指令后，各系統(tǒng)能夠以一定的方法完成指令。由此，定義如下幾個方面的規(guī)劃修復(fù)問題。

表1 火星巡視器模型中的活動及其含義Table 1 Activities in the Mars rover model and their meanings

圖1 對巖石采樣的動作模型示例Fig.1 An example of an action model for rock sampling

一般情況下，火星巡視器接收任務(wù)指令，進(jìn)行任務(wù)規(guī)劃，在獲得規(guī)劃結(jié)果后執(zhí)行具體指令時，需要傳感器感知環(huán)境信息并將其傳回監(jiān)控系統(tǒng)，用于觀察和控制任務(wù)的執(zhí)行情況。然而感知狀態(tài)中含有許多與具體動作執(zhí)行無關(guān)的冗余信息，影響任務(wù)規(guī)劃修復(fù)的效率。例如，對于原位采樣動作，感知狀態(tài)中著陸器的位置、通信設(shè)備的占用情況等就不必要顯示。因此，利用感知狀態(tài)與動作執(zhí)行的必要狀態(tài)之間的差異，定義部分狀態(tài)，在狀態(tài)中直接提取與動作直接相關(guān)的信息，以減小任務(wù)規(guī)劃修復(fù)的搜索空間大小，加快任務(wù)規(guī)劃修復(fù)速度。

假定任務(wù)目標(biāo)是對w2處的土壤進(jìn)行采樣分析并將分析結(jié)果傳回著陸器，對應(yīng)的動作序列ΠA及部分狀態(tài)序列如圖2所示。G0表示初始部分狀態(tài)，G3為目標(biāo)部分狀態(tài)，圖2中帶下劃線的謂詞為下一個動作的前提條件。每個狀態(tài)下的所有動作前提集合即構(gòu)成一個部分狀態(tài)，為規(guī)劃修復(fù)提供可選修復(fù)目標(biāo)。此時，若外界環(huán)境的發(fā)生改變或其它原因?qū)е麓龍?zhí)行動作的前提條件得不到滿足，便可利用部分狀態(tài)中來設(shè)計快速任務(wù)規(guī)劃修復(fù)策略。

圖2 規(guī)劃的部分狀態(tài)序列Fig.2 Partial state sequence of the plan ΠA

2 火星巡視器快速任務(wù)規(guī)劃修復(fù)策略

在任務(wù)執(zhí)行的過程中，火星巡視器將要執(zhí)行動作的前提條件可能會因為環(huán)境的不確定性或者自身設(shè)備的故障而不再得到滿足，執(zhí)行效果達(dá)不到預(yù)期，從而被迫中止任務(wù)。任務(wù)規(guī)劃修復(fù)就是在盡可能保留原有規(guī)劃結(jié)果的前提下，運用一定技術(shù)和方法，使巡視器能夠從失敗狀態(tài)中恢復(fù)正常、繼續(xù)執(zhí)行任務(wù)。相較于感知狀態(tài)而言，部分狀態(tài)包含未執(zhí)行動作的必要條件，不含冗余信息，縮小了狀態(tài)空間的規(guī)模，有利于快速完成任務(wù)規(guī)劃修復(fù)。因此，設(shè)計基于部分狀態(tài)的火星巡視器快速任務(wù)規(guī)劃修復(fù)策略。

圖3 任務(wù)規(guī)劃修復(fù)策略示意圖Fig.3 Illustration of mission plan repair strategy

火星巡視器快速任務(wù)規(guī)劃修復(fù)策略的偽代碼如圖4所示。第1～4行對規(guī)劃結(jié)果中的動作序列運用狀態(tài)回退函數(shù)，通過計算得到部分狀態(tài)集合G。以G為可選修復(fù)目標(biāo)，引導(dǎo)修復(fù)操作。當(dāng)巡視器監(jiān)控到動作ak的前提條件被破壞而難以執(zhí)行時，記此時的巡視器狀態(tài)為S（第5行），未執(zhí)行動作集合為PA（第6行）。其中，PA既是原規(guī)劃結(jié)果中的動作序列，又是一個不完整的規(guī)劃修復(fù)解。規(guī)劃修復(fù)的要求之一就是盡可能地保留PA中的元素。第8～28行是整個策略的核心部分。從失敗動作前提所在的部分狀態(tài) Gk?1開始，嘗試尋找使PA一致的修復(fù)動作序列，即PA在當(dāng)前狀態(tài)S下能夠得到應(yīng)用。若不存在這樣的動作序列，換到下一個部分狀態(tài)，重復(fù)該過程。

圖4 火星巡視器快速任務(wù)規(guī)劃修復(fù)策略偽代碼Fig.4 Pseudocode of fast mission plan repair strategy for Mars rover

在每次求解的過程中，構(gòu)造一顆搜索樹Tree以存儲中間狀態(tài)信息。Tree中的節(jié)點是部分狀態(tài)，邊是動作。其節(jié)點的生成和擴展通過回退函數(shù)完成，直至達(dá)到限制要求。圖4中的策略采用寬度優(yōu)先原則對樹進(jìn)行擴展，并對樹的生長過程進(jìn)行了限制，即樹的深度需要小于可能擴展的部分狀態(tài)數(shù)量+3（第15行，從第8行可知i的取值跨度為n–k+1，則可能擴展的部分狀態(tài)數(shù)量也為n–k+1，深度限制加3即為第15行中的n–k+4）。通過限制樹的深度，避免樹的無窮擴展，縮小算法的搜索時間，以實現(xiàn)快速完成修復(fù)的目的。當(dāng)擴展的節(jié)點在S下被滿足時，通過節(jié)點和邊的關(guān)系逆序追溯修復(fù)動作序列，對PA進(jìn)行修補（第21行），返回修復(fù)解。若所有嘗試都失敗了，策略返回失敗標(biāo)志，通知巡視器調(diào)用規(guī)劃器進(jìn)行完全重規(guī)劃或等待地面救援。

3 基于狀態(tài)差異的搜索空間刪減方法

在實際應(yīng)用火星巡視器快速任務(wù)規(guī)劃修復(fù)策略時，節(jié)點需要頻繁地生成、擴展（第17～19行）。此時，若使用盲目搜索，無疑會增加問題求解的時間。相反，若能充分利用實際狀態(tài)與部分狀態(tài)之間的差異，設(shè)計相應(yīng)的節(jié)點生成方法和沖突消解方法，有目的的生成和擴展節(jié)點，會減小搜索空間大小，從而縮短搜索的時間，提高方法的效率。

3.1 節(jié)點生成方法

在PDDL2.1的描述中，狀態(tài)主要由謂詞表示。當(dāng)動作執(zhí)行失敗時，狀態(tài)中只有部分謂詞發(fā)生變化。因此，針對執(zhí)行失敗的動作，結(jié)合失敗時的實際狀態(tài)與部分狀態(tài)之間謂詞的差異，如圖5所示，將部分狀態(tài)分割成相同謂詞和相異謂詞兩部分。修復(fù)時，忽略相同謂詞，采用狀態(tài)回退函數(shù)對相異謂詞回退，進(jìn)行后向搜索，有目的地擴展并生成搜索節(jié)點，可以減少擴展節(jié)點的總數(shù)，加快搜索效率。而在節(jié)點擴展的過程中，以相異謂詞為起點進(jìn)行回退后的狀態(tài)可能會刪除相同謂詞部分，導(dǎo)致最終得到的修復(fù)解無法滿足期望要求，從而誘發(fā)新一輪的搜索過程，降低修復(fù)效率。因此，在得到修復(fù)解之后，需要檢查解的可行性：即在感知狀態(tài)下模擬應(yīng)用規(guī)劃修復(fù)解后，判斷推導(dǎo)的理論狀態(tài)是否包含相應(yīng)的部分狀態(tài)，若包含，說明修復(fù)解可行，否則應(yīng)該舍棄該節(jié)點繼續(xù)處理下一個節(jié)點。

圖5 基于狀態(tài)差異的節(jié)點生成方法示意Fig.5 Node generation method based on state difference

3.2 沖突消解方法

圖6 部分狀態(tài)與回退狀態(tài)之間的沖突示意Fig.6 Conflict between the partial state and the regressed state

通過分析可以發(fā)現(xiàn)，發(fā)生沖突的部分狀態(tài)節(jié)點至少有兩個名稱相同但參數(shù)不相同的謂詞成分，如at（r，w1）與at（r，p）。但名稱相同而參數(shù)不同的謂詞不一定構(gòu)成沖突，例如描述巡視器載荷能力的謂詞（supports?camera?mode），用于表征相機具有的功能模式，例如光譜成像、立體成像、紅外成像等，這類謂詞可以在同一個部分狀態(tài)中并存而不產(chǎn)生沖突。因此，有必要針對火星巡視器，明確會引發(fā)部分狀態(tài)節(jié)點沖突的謂詞。在第1部分建立的火星巡視器任務(wù)模型中，易產(chǎn)生沖突的謂詞是（at?rover?waypoint）和（at_lander?lander?waypoint），分別描述巡視器和著陸器的位置。由此，可以設(shè)計節(jié)點中的沖突消解方法如下：在判斷節(jié)點是否存在沖突時，首先判斷部分狀態(tài)中是否存在可能引發(fā)沖突的謂詞；若存在，再進(jìn)一步判斷其參數(shù)是否會引發(fā)沖突。沖突的部分狀態(tài)自身就存在矛盾，所以在根據(jù)回退動作生成節(jié)點后，可以將自身沖突的節(jié)點刪除，以減少要擴展的節(jié)點，進(jìn)一步節(jié)省問題求解的時間。

4 仿真測試

為驗證本文提出的基于狀態(tài)差異的火星巡視器快速任務(wù)規(guī)劃修復(fù)方法RPDS的有效性，設(shè)置如圖7所示的仿真場景：存在4個地點w0、w1、w2、w3，各地存在巖石或者土壤樣本；w0和w3之間、w3和w1之間、w1和w2之間道路互通，巡視器可以直接通過；目標(biāo)object0和object1在4個地點方向均可見；初始狀態(tài)下，著陸器L位于w0，巡視器R位于w3，任務(wù)目標(biāo)是對w2的土壤進(jìn)行采樣并將分析數(shù)據(jù)傳回著陸器、對w3的巖石采樣并將分析數(shù)據(jù)傳回著陸器、對object1拍攝高分照片并將數(shù)據(jù)傳回著陸器。利用Sapa規(guī)劃器[18]對該問題進(jìn)行求解，得到的規(guī)劃結(jié)果如圖7中的下部分所示。由此，巡視器就可以在不同時刻執(zhí)行對應(yīng)的動作以完成任務(wù)目標(biāo)。同時，根據(jù)定義2中的狀態(tài)回退函數(shù) Γ (s1,a)，可以計算得到部分狀態(tài)集合。當(dāng)該規(guī)劃執(zhí)行失效時，觸發(fā)RPDS進(jìn)行規(guī)劃修復(fù)。

圖7 仿真場景示意及規(guī)劃結(jié)果Fig.7 Simulation scenario and its planning results

考慮火星巡視器領(lǐng)域特點，其規(guī)劃執(zhí)行失敗類型主要分為兩種，一是固有條件的破壞，如w1和w2之間的道路被破壞，導(dǎo)致巡視器無法直接從w1到達(dá)w2；另一種是可變條件的改變，如巡視器位置的變化、電能的存儲變化等。當(dāng)規(guī)劃失效時，例如，若由于某種原因w3和object1之間不可互見，使得第1個動作（校準(zhǔn)相機）的前提條件被破壞，從而使巡視器處于閑置狀態(tài)。巡視器的感知狀態(tài)與規(guī)劃結(jié)果中的預(yù)估狀態(tài)存在差異，RPDS就利用這些不同，有目的地向著對應(yīng)的部分狀態(tài)生成并擴展節(jié)點，并通過不斷地搜索和沖突消解，完成規(guī)劃修復(fù)問題的求解。

仿真中，通過在不同執(zhí)行時刻手動植入意外事件來模擬規(guī)劃執(zhí)行失效，并采用RPDS進(jìn)行修復(fù)。仿真測試結(jié)果如表2、圖8和圖9所示。其中，RP為文獻(xiàn)[15]中的方法，在該仿真算例中，構(gòu)造的修復(fù)結(jié)構(gòu)樹長度為3，深度為4。代碼語言為Java，測試環(huán)境為I7-6 700 CPU@3.40 GHz和 8 GB內(nèi)存。

圖8 不同方法的運行時間對比Fig.8 Comparison of operation time of different methods

圖9 不同方法的擴展節(jié)點數(shù)對比Fig.9 Comparison of the number of expansion nodes in different methods

表2 不同方法測試結(jié)果對比Table 2 Comparison of test results of different methods

從仿真結(jié)果可以看出，本文提出的基于狀態(tài)差異的任務(wù)規(guī)劃修復(fù)方法RPDS不僅能夠處理固有條件被破壞、可變條件被改變的動作執(zhí)行錯誤，而且相較于RP方法，既減少了因為構(gòu)造修復(fù)結(jié)構(gòu)樹而增加的節(jié)點擴展數(shù)，且在大部分情況下縮短了修復(fù)時間，尤其是對于回退目標(biāo)狀態(tài)包含失敗動作的前提條件情況，RPDS能夠提升大約62%的效率。此外，與重規(guī)劃方法Sapa的結(jié)果比較，RPDS提高了巡視器從執(zhí)行失敗中恢復(fù)的效率。

采用文獻(xiàn)[11]中穩(wěn)定性的評價方法，統(tǒng)計兩個規(guī)劃結(jié)果中互不相同的動作數(shù)之和，從表2的最后兩列結(jié)果可知，RPDS在快出給出修復(fù)解的同時，仍然能夠以較少的動作保障規(guī)劃穩(wěn)定性。從第10例規(guī)劃修復(fù)問題可以看出，相較于文獻(xiàn)[15]中提出的規(guī)劃修復(fù)算法RP，本文提出的方法RPDS能夠處理更多的規(guī)劃執(zhí)行失敗情況?？赡艿脑蛉缦拢篟P在每次修復(fù)時，都是將已有規(guī)劃結(jié)果按固定長度劃分后，在限定的搜索空間內(nèi)，通過后向搜索找到新的動作序列完成修復(fù)。那么對于每段中處于右端點的動作，在該限定的搜索空間內(nèi)沒有對應(yīng)的子節(jié)點，從而導(dǎo)致RP無解的情況，或者該動作能夠在下一段規(guī)劃結(jié)果中找到規(guī)劃解，但是由于搜索深度的限制，RP仍然無法給出對應(yīng)的修復(fù)方案。而對于本文提出的RPDS方法來說，直接利用整個已有規(guī)劃結(jié)果，從中提取部分狀態(tài)，為規(guī)劃修復(fù)提供修復(fù)目標(biāo)，而不需要提前建立小范圍內(nèi)的搜索空間，從而避免了規(guī)劃結(jié)果分段所導(dǎo)致的斷層節(jié)點動作無法修復(fù)的問題。

RPDS能夠快速解決問題，主要是因為它能充分利用已有規(guī)劃中的動作信息，構(gòu)建部分狀態(tài)，明確其與實際狀態(tài)之間的差異，有目的地進(jìn)行搜索，同時在已知回退目標(biāo)狀態(tài)的前提下，通過節(jié)點生成和沖突消解方法的控制，能夠減少節(jié)點擴展數(shù)、縮減搜索空間的大小，從而提高修復(fù)效率。

5 結(jié) 論

火星表面凹坑、凸起、坡度和石塊的隨機分布，土壤松軟、厚度不均等復(fù)雜地貌，以及自身電子設(shè)備的意外故障等，均容易導(dǎo)致火星巡視器任務(wù)執(zhí)行失敗。針對該問題，本文提出了適用于火星巡視器的基于狀態(tài)差異的快速任務(wù)規(guī)劃修復(fù)方法RPDS，完成了以下工作：①利用火星巡視器的感知狀態(tài)與動作執(zhí)行的必要狀態(tài)之間的差異，在已有規(guī)劃的基礎(chǔ)上，構(gòu)建了不同時刻的部分狀態(tài)，為規(guī)劃修復(fù)提供可選修復(fù)目標(biāo)；②基于部分狀態(tài)，給出了火星巡視器快速規(guī)劃修復(fù)策略；③利用部分狀態(tài)和實際狀態(tài)之間的差異，提出了基于狀態(tài)差異的搜索空間刪減方法，有目的性地生成、擴展節(jié)點并消解沖突。通過仿真實驗驗證，RPDS能夠快速有效地完成任務(wù)規(guī)劃修復(fù)，并能夠保障規(guī)劃穩(wěn)定性，可以為航天器自主快速應(yīng)對執(zhí)行時的突發(fā)事件提供技術(shù)支撐。