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

(1.北京理工大學(xué)宇航學(xué)院,北京 100081；2.深空自主導(dǎo)航與控制工信部重點(diǎn)實(shí)驗(yàn)室,北京 100081)

0 引 言

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

重規(guī)劃可分為完全重規(guī)劃與規(guī)劃修復(fù)兩類[10]。其中,完全重規(guī)劃放棄既定規(guī)劃,重新決策出新的動(dòng)作序列來完成任務(wù)目標(biāo)。此時(shí),可以利用現(xiàn)有的任務(wù)規(guī)劃方法[11-13]實(shí)現(xiàn)完全重規(guī)劃；而規(guī)劃修復(fù)對(duì)既定規(guī)劃進(jìn)行修補(bǔ)來實(shí)現(xiàn)任務(wù)目標(biāo),一般通過改造現(xiàn)有規(guī)劃器實(shí)現(xiàn)規(guī)劃修復(fù)。雖然規(guī)劃修復(fù)在理論上不一定比完全重規(guī)劃簡(jiǎn)單[14],但大量的仿真實(shí)驗(yàn)表明,規(guī)劃修復(fù)效率更高[15-17]?？紤]到任務(wù)的時(shí)效性以及任務(wù)執(zhí)行失敗可能導(dǎo)致的故障迅速蔓延,深空探測(cè)器應(yīng)優(yōu)先選擇規(guī)劃修復(fù)方法應(yīng)對(duì)突發(fā)事件。

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

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

1 規(guī)劃修復(fù)問題及建模方法

規(guī)劃修復(fù)是在既定規(guī)劃基礎(chǔ)上的再?zèng)Q策。而既定規(guī)劃是在執(zhí)行環(huán)境的先驗(yàn)知識(shí)條件下,通過合理挑選、安排活動(dòng)的順序并處理好時(shí)間、能源與活動(dòng)之間的約束關(guān)系,進(jìn)行綜合決策后給出的規(guī)劃結(jié)果。深空探測(cè)器的既定規(guī)劃可以在人工給出后通過地面站上傳,也可以自主生成,其定義如下：

定義1.一個(gè)規(guī)劃結(jié)果P是一列時(shí)間有序的實(shí)例化動(dòng)作集合。對(duì)于P中的任意元素a,可以形式化描述為a=。其中,ta表示動(dòng)作a的執(zhí)行安排時(shí)間,na表示a的名稱,pa表示a的具體參數(shù),da表示a的持續(xù)時(shí)間。

然而,深空環(huán)境不確知,導(dǎo)致先驗(yàn)知識(shí)不足,既定規(guī)劃難以正確執(zhí)行。同時(shí),設(shè)備故障、太陽風(fēng)暴等突發(fā)事件導(dǎo)致執(zhí)行異常,既定規(guī)劃難以保證探測(cè)任務(wù)的成功。因此,在深空探測(cè)器的既定規(guī)劃失效時(shí),有必要研究規(guī)劃修復(fù)問題及其解決方法。

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

為了形式化描述深空探測(cè)器的規(guī)劃修復(fù)問題并進(jìn)行求解,考慮到探測(cè)任務(wù)的時(shí)間約束,采用支持時(shí)間窗口表達(dá)的規(guī)劃領(lǐng)域定義語言PDDL2.2[25]進(jìn)行建模。

PDDL2.2采用一階邏輯,通過謂詞的形式將邏輯與數(shù)值相結(jié)合,為后續(xù)的任務(wù)規(guī)劃及規(guī)劃修復(fù)奠定模型基礎(chǔ)。它將任務(wù)分成領(lǐng)域、問題兩部分進(jìn)行描述。其中,領(lǐng)域主要描述探測(cè)器的行為能力及相關(guān)約束,例如數(shù)傳操作及其能源需求、指向約束、時(shí)間窗口約束、持續(xù)時(shí)間約束等；問題主要描述具體的探測(cè)任務(wù),包括探測(cè)器的初始狀態(tài)和任務(wù)目標(biāo),例如獲取某區(qū)域的光學(xué)影像并傳回地面。而在領(lǐng)域和問題的描述中,操作和時(shí)間窗口的表示至關(guān)重要。

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

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

在建模過程中,主要從頂層考慮探測(cè)器的執(zhí)行能力,設(shè)計(jì)相應(yīng)的操作,并加入時(shí)間、能源、參數(shù)等相關(guān)約束,建立探測(cè)器領(lǐng)域模型。同時(shí)著眼于探測(cè)任務(wù)目標(biāo),輸入不同階段探測(cè)器的初始狀態(tài)和任務(wù)目標(biāo),形成探測(cè)器問題模型。領(lǐng)域模型和問題模型經(jīng)過不斷測(cè)試、確認(rèn)沒有錯(cuò)誤后,作為自動(dòng)規(guī)劃器的輸入,調(diào)用智能規(guī)劃算法,輸出任務(wù)規(guī)劃方案,為后續(xù)的探測(cè)器執(zhí)行和規(guī)劃修復(fù)提供依據(jù)。

2 期望狀態(tài)序列計(jì)算

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

圖1 根據(jù)動(dòng)作執(zhí)行完成情況劃分后的既定規(guī)劃Fig.1 A pre-designed plan after division according to the completion of action execution

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

2.1 前向狀態(tài)塢

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

定義3.一個(gè)前向狀態(tài)塢Rf是一個(gè)七元組,表示成：Rf=。其中,t表示當(dāng)前的執(zhí)行時(shí)刻;Acur表示當(dāng)前正在執(zhí)行的動(dòng)作集合;Scur表示當(dāng)前探測(cè)器的感知狀態(tài);Scexp表示當(dāng)前期望的狀態(tài);Anext表示即將執(zhí)行的動(dòng)作集合;Snexp表示Anext執(zhí)行前的期望前提;Ei表示已經(jīng)執(zhí)行但未結(jié)束的動(dòng)作效果集合;Eo表示觀測(cè)到、待發(fā)生的突發(fā)事件。

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

2.2 邏輯與能源混合的期望狀態(tài)計(jì)算方法

期望狀態(tài)是在理想狀況下,既定規(guī)劃在各個(gè)執(zhí)行時(shí)刻想要實(shí)現(xiàn)的狀態(tài)。在前向狀態(tài)塢中,期望狀態(tài)序列為規(guī)劃修復(fù)提供修復(fù)目標(biāo),包括已開始執(zhí)行但未結(jié)束動(dòng)作的期望狀態(tài)Ei以及待執(zhí)行動(dòng)作發(fā)生的期望狀態(tài)Snexp,可通過式(1)的狀態(tài)回退函數(shù)Γ(S,a)計(jì)算。而當(dāng)前的期望狀態(tài)Scexp是部分待執(zhí)行動(dòng)作的必要前提,因此可以看成是Snexp的特殊情況。

(1)

圖3 期望狀態(tài)序列計(jì)算流程Fig.3 Diagram of expected state sequence calculation

圖4 不同的期望狀態(tài)計(jì)算過程示意圖Fig.4 Diagram of the different expected state calculation process

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

3 基于期望狀態(tài)序列的規(guī)劃修復(fù)方法

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

3.1 能源補(bǔ)給優(yōu)先的規(guī)劃修復(fù)策略

探測(cè)器活動(dòng)的順利執(zhí)行需要充足的能源支持,而修復(fù)方案可能會(huì)額外搶占既定規(guī)劃中預(yù)分配的能源份額。因此,為了簡(jiǎn)化修復(fù)過程中局部邏輯沖突與全局能源沖突的耦合計(jì)算,在修復(fù)時(shí)優(yōu)先對(duì)低可再生能源進(jìn)行補(bǔ)給。如探測(cè)器通過帆板對(duì)日定向可以實(shí)現(xiàn)電能補(bǔ)給,在一定程度上能夠減少因電能供給不足而導(dǎo)致的操作選取受限,從而降低規(guī)劃修復(fù)問題求解難度。因此,設(shè)計(jì)能源補(bǔ)給優(yōu)先的規(guī)劃修復(fù)策略,將能源修復(fù)與邏輯修復(fù)分離,如圖5所示。

圖5 基于期望狀態(tài)序列的規(guī)劃修復(fù)方法流程Fig.5 Schematic diagram of the plan repair method based on expected state sequence

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

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

值得注意的是,即使優(yōu)先補(bǔ)給不足的能源,在邏輯修復(fù)時(shí),仍有可能因?yàn)樾迯?fù)序列所包含的動(dòng)作消耗能源總量太大而再次出現(xiàn)能源不足的問題。此時(shí),本規(guī)劃修復(fù)策略直接舍棄已有的搜索步驟,并直接以下一個(gè)緊鄰的期望狀態(tài)為目標(biāo)進(jìn)行新一輪修復(fù)過程。

3.2 狀態(tài)轉(zhuǎn)移路徑搜索算法

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

圖6 狀態(tài)轉(zhuǎn)移路徑搜索算法流程Fig.6 Procedure of the state transition path search algorithm

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

圖7 時(shí)間松弛規(guī)劃圖示意圖Fig.7 Illustration of temporal relaxed planning graph

在搜索過程中,TRPG啟發(fā)式被多次調(diào)用,并且每次被調(diào)用時(shí)的待評(píng)估狀態(tài)和目標(biāo)狀態(tài)都不盡相同。因此,為了獲得準(zhǔn)確的啟發(fā)式值,在修復(fù)搜索過程中使用TRPG時(shí)需注意以下幾條：

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

2)目標(biāo)狀態(tài)的改變。與原TRPG中固定的任務(wù)目標(biāo)不同,規(guī)劃修復(fù)中的目標(biāo)可以是前向狀態(tài)塢中任意一個(gè)可達(dá)的期望狀態(tài),因此規(guī)劃修復(fù)目標(biāo)是可變的。利用第2.2節(jié)中的期望狀態(tài)序列計(jì)算方法可以提取不同時(shí)刻的規(guī)劃修復(fù)目標(biāo),包括邏輯目標(biāo)與數(shù)值目標(biāo)；

3)動(dòng)作數(shù)值部分的重新計(jì)算。由于PDDL 2.2支持的模型是離散的,動(dòng)作的邏輯部分在TRPG構(gòu)建后幾乎保持不變,而數(shù)值部分由于動(dòng)作對(duì)能源的依賴及生產(chǎn)而不斷變化。因此,為了獲取更準(zhǔn)確的節(jié)點(diǎn)評(píng)價(jià)值,在每次更新規(guī)劃修復(fù)目標(biāo)狀態(tài)且利用TRPG啟發(fā)式估計(jì)目標(biāo)距離時(shí),數(shù)值部分需要重新計(jì)算,即重新計(jì)算動(dòng)作的數(shù)值效果及其持續(xù)時(shí)間。

4 數(shù)值仿真

為了檢驗(yàn)本文提出的基于期望狀態(tài)序列的深空探測(cè)器規(guī)劃修復(fù)方法(以下用pr-e2s指代該方法)的有效性,以火星環(huán)繞器這類多時(shí)間窗口任務(wù)的對(duì)象為例,對(duì)其建模并進(jìn)行數(shù)值仿真。

4.1 火星環(huán)繞器建模

規(guī)劃修復(fù)是在約束條件下對(duì)探測(cè)器自身能力的充分再利用?？紤]到環(huán)繞器在探測(cè)過程中,利用環(huán)火軌道實(shí)現(xiàn)全球探測(cè)和指定區(qū)域的觀測(cè),實(shí)現(xiàn)火星表面形貌、土壤特性、物質(zhì)成分等的探測(cè),并將所獲得的數(shù)據(jù)傳回地面,以建立火星總體性和全局性的科學(xué)認(rèn)知[28]。因此,在進(jìn)行規(guī)劃修復(fù)前,設(shè)計(jì)火星環(huán)繞器的能力如下：

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

表1 火星環(huán)繞器的主要設(shè)備及其功能Table 1 Main devices of the Mars orbiter and their functions

2)主要操作包括觀測(cè)、數(shù)傳、充電以及姿態(tài)機(jī)動(dòng)等,如表2所示。各操作(充電操作除外)均消耗一定電能。

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

設(shè)置仿真初始條件如表3所示：相機(jī)與天線兩類設(shè)備均處于關(guān)機(jī)狀態(tài),環(huán)繞器初始時(shí)指向太陽,保持+Z軸對(duì)日定向；星上存儲(chǔ)總量為1000個(gè)單位,當(dāng)前沒有存儲(chǔ)任何數(shù)據(jù)；星上電池容量為800個(gè)單位,當(dāng)前電量為400個(gè)單位；對(duì)地?cái)?shù)傳速率為高速每秒20個(gè)單位,低速每秒10個(gè)單位；存在2個(gè)觀測(cè)窗口以及2個(gè)數(shù)傳窗口。

表3 火星環(huán)繞器初始狀態(tài)設(shè)置Table 3 Initial state setting of the Mars Orbiter

設(shè)置仿真任務(wù)目標(biāo)如表4所示：將g3區(qū)域的熱成像圖和光學(xué)成像圖、g4區(qū)域的熱成像圖傳回地面。

表4 火星環(huán)繞器的任務(wù)目標(biāo)Table 4 Mission goals of the Mars Orbiter

采用PDDL 2.2建模語言,分別構(gòu)建火星環(huán)繞器的領(lǐng)域模型和問題模型后,調(diào)用POPF2規(guī)劃器[29],給出規(guī)劃結(jié)果如圖8所示。圖8描述了探測(cè)器的姿態(tài)機(jī)動(dòng)過程、相機(jī)和天線等各星載設(shè)備的工作時(shí)間和對(duì)應(yīng)的動(dòng)作,以及星上電能大小和存儲(chǔ)值隨時(shí)間的變化,共包含20個(gè)動(dòng)作,構(gòu)成表4任務(wù)目標(biāo)的既定規(guī)劃,為探測(cè)器的任務(wù)執(zhí)行提供依據(jù),也為后續(xù)的規(guī)劃修復(fù)方法提供輸入。

圖8 深空探測(cè)器任務(wù)規(guī)劃結(jié)果Fig.8 Mission plan result of the Mars orbiter

4.2 規(guī)劃修復(fù)數(shù)值仿真結(jié)果及分析

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

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

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

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

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

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

統(tǒng)計(jì)三種方法成功求解問題的數(shù)目,結(jié)果見表5?？梢钥闯?本文方法能夠應(yīng)對(duì)更多的突發(fā)事件。針對(duì)部分測(cè)試問題,其它方法無法求解而本文的規(guī)劃修復(fù)方法卻能快速解決,可能存在以下幾個(gè)原因：

表5 成功率對(duì)比Table 5 Comparison of success rate

1)在既定規(guī)劃執(zhí)行前期,星載能源處于低水平而實(shí)現(xiàn)任務(wù)目標(biāo)仍需要探測(cè)器執(zhí)行大量活動(dòng)。此時(shí),其它方法需要進(jìn)行多次回溯,在邏輯約束與能源約束同時(shí)滿足的要求下擴(kuò)展更多節(jié)點(diǎn),導(dǎo)致運(yùn)行時(shí)長(zhǎng)超過最大時(shí)長(zhǎng)限制；而規(guī)劃修復(fù)只需滿足既定規(guī)劃中未執(zhí)行動(dòng)作的期望條件。相對(duì)于其它方法的搜索耗時(shí),規(guī)劃修復(fù)搜索空間小,目標(biāo)距離短,從而能夠快速找到修復(fù)方案；

2)在既定規(guī)劃執(zhí)行后期,存在固定的觀測(cè)窗口和數(shù)傳窗口的時(shí)間限制。此時(shí),其它方法針對(duì)未實(shí)現(xiàn)的任務(wù)目標(biāo),面臨著活動(dòng)持續(xù)時(shí)間長(zhǎng)而時(shí)間窗口短的矛盾,活動(dòng)的選取和調(diào)度受到制約；而規(guī)劃修復(fù)針對(duì)前向狀態(tài)塢中的期望狀態(tài),相較于任務(wù)目標(biāo),修復(fù)目標(biāo)距離更短,從而能夠更容易快速找到修補(bǔ)動(dòng)作,通過與待執(zhí)行動(dòng)作的融合,生成完整的修復(fù)方案。

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

從圖10可以看出,本文方法擴(kuò)展的節(jié)點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)低于POPF2,且能夠額外解決一些問題。對(duì)于這30個(gè)測(cè)試問題,本文方法的平均擴(kuò)展節(jié)點(diǎn)數(shù)為16.2個(gè),是POPF2(1919.2個(gè))的0.844%。

因此,可以得出結(jié)論：相較于其它方法而言,本文提出的基于期望狀態(tài)序列的深空探測(cè)器規(guī)劃修復(fù)方法能夠更快、更好地解決探測(cè)器的規(guī)劃修復(fù)問題。

5 結(jié) 論

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