期望狀態序列導向的深空探測器規劃修復方法

陳 超,徐 瑞,李朝玉,朱圣英,梁子璇

(1.北京理工大學宇航學院,北京 100081；2.深空自主導航與控制工信部重點實驗室,北京 100081)

0 引 言

作為探索其它天體上生命跡象、追溯太陽系起源的重要手段,深空探測一直是NASA、ESA以及中國、日本、印度等機構和國家航天發展的重點[1-5]。通過遙控遙測的方式,人類可以借助深空探測器獲取大量有關地外天體的有價值信息[6-7]。然而,由于對深空環境認知不全、設備長時間運行導致的性能下降以及太陽風等難預測的突發事件,探測器的既定規劃在執行中面臨著實際狀況與預期不符,進而導致任務目標無法實現的難題[8-9]。因此,在器地通信存在長時延、星蝕、日凌等客觀事實下,探測器應具備自主重規劃功能,以增強其自主應對故障的能力,提高任務回報。

重規劃可分為完全重規劃與規劃修復兩類[10]。其中,完全重規劃放棄既定規劃,重新決策出新的動作序列來完成任務目標。此時,可以利用現有的任務規劃方法[11-13]實現完全重規劃；而規劃修復對既定規劃進行修補來實現任務目標,一般通過改造現有規劃器實現規劃修復。雖然規劃修復在理論上不一定比完全重規劃簡單[14],但大量的仿真實驗表明,規劃修復效率更高[15-17]?？紤]到任務的時效性以及任務執行失敗可能導致的故障迅速蔓延,深空探測器應優先選擇規劃修復方法應對突發事件。

現有的規劃修復方法根據采用的修復策略,可分為規則匹配型、局部調整型、刪除/求精型、狀態轉移型以及構造新問題型五類[10]。由于空間環境的不確知性,通過提前設想故障類型并人為給出解決方案的規則匹配型規劃修復方法,無法應對實際執行中的各種突發情況[18]。Bechon等[19]依次移除動作后再利用原有規劃方法來尋找機器人任務執行失敗的解決方案,本質上是初始狀態不斷變化下的完全重規劃,效率有待進一步提高；Soubaras等[20]將規劃修復問題轉化成柔性作業車間調度問題,并提出15數碼算法,能夠給出水下航行器群中部分個體失效時的規劃方案,但是應對突發事件類型有限。Zheng等[21]通過刪除、注入、修改參數等方式,調用其提出的混合動態變化遺傳算法,來給出不同突發事件下多衛星系統的觀測通信方案,但是對動作時序的討論少。Guzman等[22]基于狀態回退機制提出了響應式規劃方法,可以快速給出下一個動作或者一段特定時間內的動作,但處理的動作對象是瞬時、串行的。Scala等[23]基于火星巡視器動作模式的多樣性,利用約束可滿足理論,提出了基于動作模式重構的規劃修復方法,卻并未考慮能源消耗的問題。Chen等[24]從能源和動作邏輯兩個角度分別提出了全局能源診斷及修復方法、小偏差規劃修復方法,并結合二者提出了響應式規劃修復策略,但是修復時采用盲搜策略,效率有待進一步提高。

考慮深空探測器多系統耦合并行、活動持續且消耗能源,同時探測任務多時間窗口的特點,本文采用PDDL2.2[25](Planning domain definition language 2.2)對深空探測器任務規劃進行建模,為獲取初始規劃結果以及后續規劃修復做好準備。針對環境不確知、設備故障及外部突發事件引起的既定規劃失效問題,結合動作的完成情況,本文在前向狀態塢概念的基礎上,提出了邏輯與能源混合的期望狀態序列計算方法,為規劃修復提供可選目標。在此基礎上,提出了能源補給優先的規劃修復策略,并設計了狀態轉移路徑搜索算法。最后以火星環繞器為例,通過仿真測試,驗證了本文方法的有效性和合理性。

1 規劃修復問題及建模方法

規劃修復是在既定規劃基礎上的再決策。而既定規劃是在執行環境的先驗知識條件下,通過合理挑選、安排活動的順序并處理好時間、能源與活動之間的約束關系,進行綜合決策后給出的規劃結果。深空探測器的既定規劃可以在人工給出后通過地面站上傳,也可以自主生成,其定義如下：

定義1.一個規劃結果P是一列時間有序的實例化動作集合。對于P中的任意元素a,可以形式化描述為a=。其中,ta表示動作a的執行安排時間,na表示a的名稱,pa表示a的具體參數,da表示a的持續時間。

然而,深空環境不確知,導致先驗知識不足,既定規劃難以正確執行。同時,設備故障、太陽風暴等突發事件導致執行異常,既定規劃難以保證探測任務的成功。因此,在深空探測器的既定規劃失效時,有必要研究規劃修復問題及其解決方法。

定義2.一個規劃修復問題Π是一個六元組,即Π=。其中,P是既定規劃,IΠ表示執行異常時深空探測器的狀態,GP則描述既定規劃P中仍未實現的任務目標；F描述探測器狀態的邏輯命題,其取值為true或false；V表示探測器狀態中的數值變量及其取值范圍；操作O包含了改變探測器狀態的方式及效果。規劃修復問題就是在F和V的約束下,如何從O中找到一系列操作并實例化,使得探測器能夠從狀態IΠ到達既定規劃P中的任務目標狀態GP。

為了形式化描述深空探測器的規劃修復問題并進行求解,考慮到探測任務的時間約束,采用支持時間窗口表達的規劃領域定義語言PDDL2.2[25]進行建模。

PDDL2.2采用一階邏輯,通過謂詞的形式將邏輯與數值相結合,為后續的任務規劃及規劃修復奠定模型基礎。它將任務分成領域、問題兩部分進行描述。其中,領域主要描述探測器的行為能力及相關約束,例如數傳操作及其能源需求、指向約束、時間窗口約束、持續時間約束等；問題主要描述具體的探測任務,包括探測器的初始狀態和任務目標,例如獲取某區域的光學影像并傳回地面。而在領域和問題的描述中,操作和時間窗口的表示至關重要。

對于操作,其實例化后就是動作。操作中的任意一個元素都可以表示成o=,其中no表示該操作的名稱,po表示其參數,do表示其持續時間,Pre描述其前提條件,Eff則表示其效果。在PDDL2.2中,一個持續動作被轉化成開始(at start)、中間(over all)、結束(at end)三部分進行描述。例如,對地數傳操作,參數包含可用的數傳窗口、使用的數傳天線及其工作模式,以及要傳輸的目標影像及其類型；持續時間難以估計,因此使用函數表示方法,由外部確定；開始前提包括探測器指向地球、數傳天線可用且已打開、已經獲得目標影像并且數傳窗口可用；開始效果為數傳天線進入工作狀態；中間的前提條件為探測器繼續指向地球、剩余存儲可用、數傳窗口可用且星上能源充足；沒有中間的效果和結束的前提條件；結束效果為數傳天線閑置、目標影像成功被傳輸、剩余存儲減小、可用存儲增加、星上可用能源降低。其中,操作消耗的能源、持續時間等難以提前確定的量都采用函數形式由外部輸入確定。

對于時間窗口,采用由一對相反謂詞和不同時刻組成的時間初始化文字表示。例如,(at 120(image_active w1probe))表示了探測器在120 s可以進行觀測,(at 180 (not (image_active w1probe)))則表示探測器在180 s無法觀測。由此,兩者結合,就可以表示一個從120～180 s的觀測窗口。

在建模過程中,主要從頂層考慮探測器的執行能力,設計相應的操作,并加入時間、能源、參數等相關約束,建立探測器領域模型。同時著眼于探測任務目標,輸入不同階段探測器的初始狀態和任務目標,形成探測器問題模型。領域模型和問題模型經過不斷測試、確認沒有錯誤后,作為自動規劃器的輸入,調用智能規劃算法,輸出任務規劃方案,為后續的探測器執行和規劃修復提供依據。

2 期望狀態序列計算

如圖1所示,探測器的既定規劃在實際執行時,若異常導致規劃失效,其動作根據安排的發生時刻與當前執行時刻的相對關系,可分為異常出現前已經執行完成的部分以及異常出現后未執行完成的部分。由于探測器的活動具有一定的持續時間,既定規劃中未執行完成的部分活動可能已經發生但未結束(如圖1中的a1～a3,稱為未完成執行的動作),而其它活動仍未開始(如圖1中的b1～b8,稱為待執行的動作)。已有的規劃修復方法大都忽略這一事實,而選擇放棄未完成執行的動作并尋找新的動作序列以連接當前異常狀態與部分待執行的動作,從而丟失部分有價值的參考信息,在一定程度上降低了規劃修復效率。

圖1 根據動作執行完成情況劃分后的既定規劃Fig.1 A pre-designed plan after division according to the completion of action execution

因此,從既定規劃中提取未完成執行動作的期望效果、待執行動作的期望前提,組成期望狀態集合,并按照期望效果在前、期望前提按動作發生順序排列的方式進行組合,構成期望狀態序列。這樣做有以下優勢：1)相對于探測器龐雜的狀態信息,期望狀態只包含了動作的必要前提/效果,從而縮小了搜索空間大小；2)相較于任務目標,期望狀態序列為規劃修復提供了更容易達成的目標,從而使得規劃修復能夠快速給出修復方案；3)由于并行動作之間的不互斥,待執行的動作可以另安排執行時間而不產生沖突,從而使得探測器能夠在有限的時間內集中處理當前未完成執行動作的執行失效問題,進一步縮小了搜索空間大小。為有效管理執行過程中探測器的狀態信息以及既定規劃中的期望狀態序列信息,借用前向狀態塢[24]這一概念,提出邏輯與能源混合的期望狀態計算方法,為后續的規劃修復搜索提供子目標。

2.1 前向狀態塢

探測器的既定規劃是一組時間有序的動作集合。圖2所示描述了探測器觀測某區域并將觀測結果傳回地面這一任務的既定規劃。其動作根據所屬的子系統,可以分別被納入姿態系統、相機以及數傳天線三條時間線上。不同時間線上的動作在同一空時間線上映射,可轉換為一組時間有序的狀態隊列(如圖2中的{S1,…,S6})。執行過程中,探測器通過動作的連續執行,實現不同狀態之間的轉移,直至完成任務目標。當突發事件發生時,實際執行狀態與規劃預期狀態不一致,導致既定規劃無法適用于當前情形。此時,由圖1可知,存在探測器的感知狀態、未完成執行動作、待執行動作,以及由動作導出的多個期望狀態信息,為了便于在規劃修復時及時給出可用的修復目標,高效管理狀態,給出前向狀態塢的概念,其定義如下：

定義3.一個前向狀態塢Rf是一個七元組,表示成：Rf=。其中,t表示當前的執行時刻;Acur表示當前正在執行的動作集合;Scur表示當前探測器的感知狀態;Scexp表示當前期望的狀態;Anext表示即將執行的動作集合;Snexp表示Anext執行前的期望前提;Ei表示已經執行但未結束的動作效果集合;Eo表示觀測到、待發生的突發事件。

如圖2所示,前向狀態塢是一段時間區間內的狀態集合。其成員可分為兩大類：當前執行時刻包含的相關信息(包括Acur、Scur、Scexp),以及未來一段時間內的相關信息(包括Anext、Snexp和Ei、Eo)。已經執行完成的動作,其效果通過狀態轉移歸結到探測器的當前狀態中,從而可以被忽略。前向狀態塢總是從動作的發生時刻或者執行異常的時刻開始,而其終端由于動作持續并行的影響,無法簡單地根據時刻確定。例如,圖1對應的前向狀態塢中,Acur包含a1～a3,Anext包含b1、b2,不包含Snexp以及Eo。在正常執行時,其兩端會隨著動作的不斷執行而隨時間向前移動,并更新成員信息；在執行失敗時,其起始端固定在失敗時刻,而其終端隨著規劃修復的不斷進行,逐漸向前擴展,直至找到修復方案。

2.2 邏輯與能源混合的期望狀態計算方法

期望狀態是在理想狀況下,既定規劃在各個執行時刻想要實現的狀態。在前向狀態塢中,期望狀態序列為規劃修復提供修復目標,包括已開始執行但未結束動作的期望狀態Ei以及待執行動作發生的期望狀態Snexp,可通過式(1)的狀態回退函數Γ(S,a)計算。而當前的期望狀態Scexp是部分待執行動作的必要前提,因此可以看成是Snexp的特殊情況。

(1)

圖3 期望狀態序列計算流程Fig.3 Diagram of expected state sequence calculation

圖4 不同的期望狀態計算過程示意圖Fig.4 Diagram of the different expected state calculation process

值得注意的是,在使用PDDL2.2建立的深空探測器模型中,操作的前提和效果根據其持續時間被分成了開始、中間和結束三部分,而其實際效果又都在結束時體現。因此,在收集既定規劃中動作的效果時,直接提取動作的結束效果；在收集動作的前提時,由于動作的連續計算,一個動作結束時的前提可能由自身開始時的效果提供,也可能被之前發生的其它動作提供。因此,自我滿足的這部分被剔除,以避免被誤認為需要額外動作來提供,從而減少不必要的求解時間。

3 基于期望狀態序列的規劃修復方法

探測器的既定規劃具有動作持續、并行、消耗能源的特點,在前向狀態塢的支持下,可統一映射到同一空時間線上,從而成為一組時間有序的狀態點,而邏輯與能源(用數值體現)在狀態點中可以體現。因此,規劃修復問題可轉化為從當前狀態到期望狀態序列的可行狀態轉移路徑搜索問題。在問題求解過程中,提出能源修復與邏輯修復分離、能源補給優先的基于期望狀態序列的規劃修復方法,并進一步提出狀態轉移路徑搜索算法。該規劃修復方法具有以下優勢：1)深空探測器的規劃修復是邏輯與能源耦合的問題,優先補給能源,將能源修復與邏輯修復分離,可以在一定程度上降低整個規劃修復問題的求解難度,減少邏輯修復過程中因能源約束不滿足而導致的回溯次數,從而提高規劃修復求解效率；2)利用期望狀態序列進行修復,可以充分利用既定規劃中的信息,有序地決策出修復方案；3)深空探測器的任務執行是個連續的過程,按照期望狀態序列的順序先修復未完成執行的動作,可以更及時地處理突發事件,降低影響程度,特別是在著陸下降等緊急任務中,可以做出快速響應。

3.1 能源補給優先的規劃修復策略

探測器活動的順利執行需要充足的能源支持,而修復方案可能會額外搶占既定規劃中預分配的能源份額。因此,為了簡化修復過程中局部邏輯沖突與全局能源沖突的耦合計算,在修復時優先對低可再生能源進行補給。如探測器通過帆板對日定向可以實現電能補給,在一定程度上能夠減少因電能供給不足而導致的操作選取受限,從而降低規劃修復問題求解難度。因此,設計能源補給優先的規劃修復策略,將能源修復與邏輯修復分離,如圖5所示。

圖5 基于期望狀態序列的規劃修復方法流程Fig.5 Schematic diagram of the plan repair method based on expected state sequence

能源補給時,在可再生能源首次不足之前,利用補給-復原動作流[24](即在待執行動作前嘗試插入能源補給動作進行充能以及狀態回歸動作將探測器狀態恢復至待執行動作的期望狀態),比較充能后富余的能源大小,從而確定最優的補給時刻及對應的能源補給方案。若能源不足以支撐既定規劃中剩余動作的實施,且該能源沒有補給方案,規劃修復失敗。此時,探測器進入安全模式,等待地面操作人員發現問題并上傳有效的解決方案。否則,將能源補給方案與既定規劃進行融合,并更新前向狀態塢中的各個元素,從而更新期望狀態序列。

在補充明顯不足的可再生能源后,以期望狀態序列中的元素為修復目標,搜索探測器當前狀態到期望狀態的可行路徑。在該過程中,遵循已發生動作優先、待執行動作其次的修復順序。只有當前向狀態塢中的所有期望狀態都不可達時,才會啟用重規劃方法,直接搜索到達任務目標的可行解。對于已發生動作,其期望狀態是最晚結束時刻時的預期效果集合,如圖4中的Ei。因此,其修復過程就是在找到一條從Scur到Ei的可行路徑后,將修復方案與既定規劃融合、生成新的執行方案。若不存在這樣的解,進入待執行動作的修復。對于待執行動作,其期望狀態是動作發生的預期條件,是一段時間內離散分布的狀態點,隨著前向狀態塢的不斷更新而不斷變化。因此,其修復過程需要先根據期望狀態中的邏輯條件及相關約束在探測器當前狀態下滿足的情況,分析、判斷既定規劃失效的原因,確定期望狀態的時刻,然后搜索一條Scur到Snexp的可行路徑。若搜索失敗,嘗試尋找到達下一個期望狀態的路徑,直至遍歷整個既定規劃。若整個期望狀態序列都不可達,調用規劃算法進行完全重規劃。

值得注意的是,即使優先補給不足的能源,在邏輯修復時,仍有可能因為修復序列所包含的動作消耗能源總量太大而再次出現能源不足的問題。此時,本規劃修復策略直接舍棄已有的搜索步驟,并直接以下一個緊鄰的期望狀態為目標進行新一輪修復過程。

3.2 狀態轉移路徑搜索算法

在能源補給優先的規劃修復策略中,可行狀態轉移路徑的搜索是解決規劃修復問題的關鍵。搜索時,本文采用最佳優先搜索算法確定節點的訪問順序,并修改現有的時間松弛規劃圖[26](Temporal relaxed planning graph,TRPG)啟發式來評價節點,優先擴展評價值最高的節點。如圖6所示,搜索過程中,將邏輯前提和數值前提在上一狀態均得到滿足的動作加以應用,實現狀態轉移。在轉移過程中,通過簡單時間約束網絡和線性規劃技術,對時間、能源約束進行推理,若發現時間窗口、能源總量等約束被破壞的情況,則進行回溯。重復該過程,直至找出一個可行的修復方案。

圖6 狀態轉移路徑搜索算法流程Fig.6 Procedure of the state transition path search algorithm

在整個搜索過程中,TRPG啟發式能對待擴展節點的優劣進行評價,從而指導搜索方向,提高規劃修復的搜索效率。如圖7所示,TRPG忽略動作的刪除效果、擴大數值效果(若動作的效果是增加/刪除某類型能源值,則TRPG在下一事實層中直接將該類型能源增加/減小該能源的最大值/最小值)、并且將數值前提簡化為大于/大于等于兩種類型,采用事實層和動作層交替的框架向前擴展。其中,每個事實層和動作層都與對應事實成立的時刻、動作發生的時刻綁定。TRPG啟發式則通過統計初始狀態層到達目標狀態層的動作序列中動作總數,給出啟發式估計值。與規劃中的功能一樣,TRPG啟發式也可以用于規劃修復[27],為規劃修復搜索提供目標距離估計和病態節點識別。

圖7 時間松弛規劃圖示意圖Fig.7 Illustration of temporal relaxed planning graph

在搜索過程中,TRPG啟發式被多次調用,并且每次被調用時的待評估狀態和目標狀態都不盡相同。因此,為了獲得準確的啟發式值,在修復搜索過程中使用TRPG時需注意以下幾條：

1)初始狀態的改變。與原TRPG啟發式中初始狀態為執行前開始規劃的狀態不同,規劃修復中的初始狀態為計劃執行失敗時探測器的感知狀態。但是考慮到前向狀態塢中,在該狀態下,部分動作已經開始執行但未結束(其效果被收入Ei之中),且被觀測到的突發事件(Eo)將要發生,除了將當前探測器感知的狀態置為TRPG啟發式的初始狀態外,為了充分利用既定規劃中的信息,同時不遺漏新的執行環境,Ei和Eo都應被納入到前向狀態塢中,為后續的規劃修復搜索分別提供修復目標和限制條件；

2)目標狀態的改變。與原TRPG中固定的任務目標不同,規劃修復中的目標可以是前向狀態塢中任意一個可達的期望狀態,因此規劃修復目標是可變的。利用第2.2節中的期望狀態序列計算方法可以提取不同時刻的規劃修復目標,包括邏輯目標與數值目標；

3)動作數值部分的重新計算。由于PDDL 2.2支持的模型是離散的,動作的邏輯部分在TRPG構建后幾乎保持不變,而數值部分由于動作對能源的依賴及生產而不斷變化。因此,為了獲取更準確的節點評價值,在每次更新規劃修復目標狀態且利用TRPG啟發式估計目標距離時,數值部分需要重新計算,即重新計算動作的數值效果及其持續時間。

4 數值仿真

為了檢驗本文提出的基于期望狀態序列的深空探測器規劃修復方法(以下用pr-e2s指代該方法)的有效性,以火星環繞器這類多時間窗口任務的對象為例,對其建模并進行數值仿真。

4.1 火星環繞器建模

規劃修復是在約束條件下對探測器自身能力的充分再利用。考慮到環繞器在探測過程中,利用環火軌道實現全球探測和指定區域的觀測,實現火星表面形貌、土壤特性、物質成分等的探測,并將所獲得的數據傳回地面,以建立火星總體性和全局性的科學認知[28]。因此,在進行規劃修復前,設計火星環繞器的能力如下：

1)搭載相機和天線這兩類設備,共四件。各自所支持的功能/模式見表1,狀態包含打開、工作、關閉等；

表1 火星環繞器的主要設備及其功能Table 1 Main devices of the Mars orbiter and their functions

2)主要操作包括觀測、數傳、充電以及姿態機動等,如表2所示。各操作(充電操作除外)均消耗一定電能。

表2 火星環繞器的主要操作及其含義Table 2 Main operations of the Mars orbiter and their meaning

設置仿真初始條件如表3所示：相機與天線兩類設備均處于關機狀態,環繞器初始時指向太陽,保持+Z軸對日定向；星上存儲總量為1000個單位,當前沒有存儲任何數據；星上電池容量為800個單位,當前電量為400個單位；對地數傳速率為高速每秒20個單位,低速每秒10個單位；存在2個觀測窗口以及2個數傳窗口。

表3 火星環繞器初始狀態設置Table 3 Initial state setting of the Mars Orbiter

設置仿真任務目標如表4所示：將g3區域的熱成像圖和光學成像圖、g4區域的熱成像圖傳回地面。

表4 火星環繞器的任務目標Table 4 Mission goals of the Mars Orbiter

采用PDDL 2.2建模語言,分別構建火星環繞器的領域模型和問題模型后,調用POPF2規劃器[29],給出規劃結果如圖8所示。圖8描述了探測器的姿態機動過程、相機和天線等各星載設備的工作時間和對應的動作,以及星上電能大小和存儲值隨時間的變化,共包含20個動作,構成表4任務目標的既定規劃,為探測器的任務執行提供依據,也為后續的規劃修復方法提供輸入。

圖8 深空探測器任務規劃結果Fig.8 Mission plan result of the Mars orbiter

4.2 規劃修復數值仿真結果及分析

圖8中的既定規劃包含20個動作,涉及4項載荷設備的活動、電能和存儲這2種能源的消耗與補充,以及多個觀測時間窗口和數傳時間窗口的時間限制。在實際執行出錯時,如何在限定的電能總量和存儲總額的能源限制條件下,快速且合理地挑選活動并修改既定規劃,以滿足邏輯約束、能源約束、時間窗口約束等約束,使得環繞器能夠繼續完成任務,是規劃修復面臨的最大問題。

對于環境不確知、外部突發事件及自身設備故障等造成的既定規劃執行失敗的問題,采用事件的形式對其進行描述,即E=〈t,e〉。其中,E表示事件,t表示事件發生的時刻,e表示事件的具體內涵。例如E=〈10.5,(not (camera_calibrated cam))〉表示在t=10.5的時候,相機未校準。由此,結合探測器動作執行的特點,采取事件的形式,在不同的執行時刻注入邏輯約束不滿足、能源供給不足等類型故障,來模擬探測器在執行過程中可能遇到的突發事件。

本文提出的方法pr-e2s在POPF2規劃器上實現。針對圖8的既定規劃,本文共注入了30組故障,在配備Xeon(R)E5-2698 v3 @ 2.30 GHz CPU和12 GB內存的服務器上,測試本文方法的性能表現,并與第4屆智能規劃大賽表現最佳的規劃器LPG-td[30]在同平臺下進行對比。每次測試設置了10分鐘的運算時長限制。測試結果如圖9、圖10所示。

圖9 程序運行耗時結果對比(1)耗時結果都是通過程序運行三次后取平均值得到；測試問題上若無耗時數據點,說明該問題用該方法無法求解。Fig.9 Comparison of CPU time results

圖10 擴展節點數對比(2)無法獲取LPG-td的源代碼(https://lpg.unibs.it/lpg/),因此無法輸出其擴展節點數。Fig.10 Comparison of the number of expansion nodes

具體來說,測試問題1～15針對表3的初始狀態設置,問題16～30針對圖8所示既定規劃的中間、結束部分設置,以此說明本文方法在不同執行階段的適用性。其中,問題1～5、問題16～20是由邏輯不滿足引起的執行失敗,問題6～10、問題21～25是由能源不足引起的執行失敗,問題11～15、問題26～30是由邏輯約束和能源約束均不滿足引起的執行失敗,以此說明本文方法對不同失敗類別原因的適應性。

統計三種方法成功求解問題的數目,結果見表5。可以看出,本文方法能夠應對更多的突發事件。針對部分測試問題,其它方法無法求解而本文的規劃修復方法卻能快速解決,可能存在以下幾個原因：

表5 成功率對比Table 5 Comparison of success rate

1)在既定規劃執行前期,星載能源處于低水平而實現任務目標仍需要探測器執行大量活動。此時,其它方法需要進行多次回溯,在邏輯約束與能源約束同時滿足的要求下擴展更多節點,導致運行時長超過最大時長限制；而規劃修復只需滿足既定規劃中未執行動作的期望條件。相對于其它方法的搜索耗時,規劃修復搜索空間小,目標距離短,從而能夠快速找到修復方案；

2)在既定規劃執行后期,存在固定的觀測窗口和數傳窗口的時間限制。此時,其它方法針對未實現的任務目標,面臨著活動持續時間長而時間窗口短的矛盾,活動的選取和調度受到制約；而規劃修復針對前向狀態塢中的期望狀態,相較于任務目標,修復目標距離更短,從而能夠更容易快速找到修補動作,通過與待執行動作的融合,生成完整的修復方案。

從圖9可以看出,本文方法能夠在1 s以內求解所有的規劃修復問題,且平均求解時間低于POPF2和LPG-td方法。對于這30個測試問題,本文方法的平均運算耗時為0.03415 s,是POPF2(12.89125 s)的0.265%,是LPG-td(9.27196 s)的0.368%。而在18、19、20這三個問題上,本文方法耗時略長于LPG-td方法。造成該現象的原因是搜索算法的不同：本文采用最佳優先搜索算法,而LPG-td采用帶有概率選擇下一擴展節點的Walkplan算法[30],在相同的問題下,LPG-td更容易跳出局部最優。

從圖10可以看出,本文方法擴展的節點數遠遠低于POPF2,且能夠額外解決一些問題。對于這30個測試問題,本文方法的平均擴展節點數為16.2個,是POPF2(1919.2個)的0.844%。

因此,可以得出結論：相較于其它方法而言,本文提出的基于期望狀態序列的深空探測器規劃修復方法能夠更快、更好地解決探測器的規劃修復問題。

5 結 論

針對深空環境不確知、外部突發事件及自身設備故障等引起的探測器既定規劃執行失敗問題,結合活動持續、并行、消耗能源的特點,本文提出了基于期望狀態序列的深空探測器規劃修復方法。該方法利用前向狀態塢將既定規劃中持續、并行的動作轉化為一組時間有序的狀態點,并通過期望狀態的計算將邏輯與能源包含在狀態點中,為后續規劃修復提供子目標,并將規劃修復問題轉化為狀態轉移路徑搜索問題。本文主要創新點如下：1)根據既定規劃中動作的執行完成情況,提出了邏輯與能源混合的期望狀態序列計算方法,能夠計算出未完成執行動作的期望效果和待執行動作的期望前提,為規劃修復提供可選修復目標；2)提出了將能源修復與邏輯修復分離的能源補給優先規劃修復策略,不僅在一定程度上降低了規劃修復問題求解的難度,而且使探測器能夠及時自主應對突發事件；3)結合時間松弛規劃圖啟發式,設計了狀態轉移路徑搜索算法,削減搜索空間大小,提高修復效率；4)基于PDDL2.2設計了火星環繞器任務模型,并通過數值仿真驗證了本文方法的有效性和合理性,可以為深空探測器自主應對突發事件提供技術支持。