徐 瑞，陳 超，崔平遠(yuǎn)，朱圣英，徐 帆

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

0 引 言

智能規(guī)劃通過采用知識推理方法來尋找從指定狀態(tài)到達(dá)目標(biāo)狀態(tài)的活動(dòng)序列[1]，是希望系統(tǒng)能夠通過執(zhí)行這些活動(dòng)完成任務(wù)。雖然目前國內(nèi)外關(guān)于航天器自主任務(wù)規(guī)劃的研究比較多[2-6]，但實(shí)際應(yīng)用比較少，其中一個(gè)重要原因是將規(guī)劃與執(zhí)行分開[7]。由于航天器所處環(huán)境存在動(dòng)態(tài)性、不確定性和不可控性，且任務(wù)目標(biāo)在航天器運(yùn)行過程中可能發(fā)生變化[8]，繼續(xù)執(zhí)行原有任務(wù)規(guī)劃結(jié)果可能無法達(dá)成目標(biāo)。此時(shí)，通過地面遙測遙控的方式已經(jīng)很難滿足航天器控制的實(shí)時(shí)性和安全性要求。例如火星探路者號就由于未考慮到實(shí)際執(zhí)行時(shí)的環(huán)境影響，任務(wù)規(guī)劃結(jié)果執(zhí)行失敗[9]。因此，為了增強(qiáng)航天器自主能力、提高航天任務(wù)回報(bào)率，需要將規(guī)劃與執(zhí)行結(jié)合在一起，智能處理規(guī)劃結(jié)果執(zhí)行失敗的問題[10-12]。

在執(zhí)行過程中，若外界環(huán)境發(fā)生變化(如火星車行進(jìn)過程中刮起了風(fēng)暴)，或者目標(biāo)發(fā)生變化(如火山突然爆發(fā)需要觀測)，或者動(dòng)作執(zhí)行失敗(如太陽帆板未能展開)，原規(guī)劃結(jié)果都不能保證任務(wù)被順利完成。此時(shí)，存在完全重規(guī)劃、規(guī)劃修復(fù)兩種方法使航天器繼續(xù)執(zhí)行任務(wù)。其中，完全重規(guī)劃是指拋棄已有規(guī)劃結(jié)果，重新搜索抵達(dá)目標(biāo)的動(dòng)作序列；而規(guī)劃修復(fù)是指對已有規(guī)劃結(jié)果做一定修改來達(dá)成目標(biāo)?？紤]到正常的星上規(guī)劃過程需要耗費(fèi)大量時(shí)間，且原有規(guī)劃結(jié)果給執(zhí)行器或者其它智能系統(tǒng)已經(jīng)承諾一定資源或者其它信息，有效地利用已經(jīng)生成的規(guī)劃結(jié)果顯得更加合理。此外，對于有人參與的復(fù)雜任務(wù)，若拋棄原有規(guī)劃結(jié)果重新生成一個(gè)新的規(guī)劃結(jié)果，技術(shù)人員勢必耗費(fèi)時(shí)間去熟悉了解，在一定程度上影響任務(wù)的執(zhí)行效率。綜上所述，規(guī)劃修復(fù)技術(shù)比完全重規(guī)劃技術(shù)更具有應(yīng)用前景。

面對航天器自主控制和自主運(yùn)行的發(fā)展趨勢，開展航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)研究具有重大的理論意義和現(xiàn)實(shí)意義。本文首先給出航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)的定義，指出其難點(diǎn)，接著梳理國內(nèi)外的研究成果，然后對規(guī)劃修復(fù)方法的評價(jià)標(biāo)準(zhǔn)——規(guī)劃穩(wěn)定性進(jìn)行了總結(jié)，最后概括分析了各種方法的優(yōu)缺點(diǎn)，并對未來航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)的研究方向提出了發(fā)展建議。

1 航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)的定義和難點(diǎn)

綜合考慮航天器執(zhí)行任務(wù)的特點(diǎn)與任務(wù)規(guī)劃修復(fù)方法的特征，給出航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)的定義如下：

定義1. (航天器自主任務(wù)規(guī)劃修復(fù)技術(shù))航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)是指在航天器任務(wù)規(guī)劃結(jié)果執(zhí)行失敗時(shí)，通過智能搜索和智能推理方法，在原有規(guī)劃結(jié)果的基礎(chǔ)上，充分利用航天器專家知識，使航天器從失敗中恢復(fù)，從而得以繼續(xù)執(zhí)行任務(wù)的一項(xiàng)技術(shù)。該技術(shù)只能處理既定領(lǐng)域下的規(guī)劃執(zhí)行失敗情況，而不能應(yīng)對模型之外的故障情況，即需要新知識才能完成修復(fù)的故障。

雖然航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)只在模型之中解決問題，但它將規(guī)劃和執(zhí)行有機(jī)結(jié)合，既可以利用人工智能的方法在任務(wù)層面統(tǒng)籌全局，提前預(yù)測、修復(fù)故障，增強(qiáng)系統(tǒng)的可靠性；又可以充分利用星上資源，在當(dāng)前約束條件下嘗試所有可能的故障修復(fù)方法，提高系統(tǒng)的執(zhí)行效率。因此發(fā)展航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)勢必成為提高智能航天器魯棒性的必然要求和趨勢。

雖然在理論上規(guī)劃修復(fù)不一定簡單[13]，但試驗(yàn)結(jié)果表明規(guī)劃修復(fù)效率更高[14-17]。然而由于航天器領(lǐng)域的特殊性，航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)存在如下難點(diǎn)：

1)及時(shí)性。航天器資源有限且任務(wù)周期一般固定不變，當(dāng)任務(wù)尤其是對于觀測彗星撞擊等具有強(qiáng)烈時(shí)間要求的任務(wù)執(zhí)行失敗時(shí)，需要航天器能夠在任務(wù)截止時(shí)間之前，快速給出有效的修復(fù)方案。

2)環(huán)境不確定性。環(huán)境不確定性難以避免，一方面影響動(dòng)作執(zhí)行，另一方面需要航天器根據(jù)不同情況給出不同修復(fù)方案。

3)目標(biāo)動(dòng)態(tài)性。航天器執(zhí)行任務(wù)過程中，目標(biāo)可能發(fā)生動(dòng)態(tài)變化，如新的觀測請求。此時(shí)，航天器自主規(guī)劃修復(fù)技術(shù)需要考慮未執(zhí)行的動(dòng)作序列是否有利于完成目標(biāo)，以及如何利用該序列來完成新目標(biāo)。

4)系統(tǒng)耦合性。航天器各子系統(tǒng)之間存在耦合性，使得航天器動(dòng)作之間存在并行性。當(dāng)任務(wù)執(zhí)行發(fā)生并發(fā)性動(dòng)作沖突時(shí)，需要航天器能夠綜合考慮系統(tǒng)之間的關(guān)系，在盡可能不破壞已有約束的前提下，給出合理高效的修復(fù)方案。

5)資源約束的動(dòng)態(tài)復(fù)雜性。航天器上存在離散資源(載荷、子系統(tǒng)等各種設(shè)備)和連續(xù)資源(電能、燃料等)。對于航天器任務(wù)尤其是航天器組網(wǎng)任務(wù)來說，資源占用或者資源消耗情況在實(shí)際執(zhí)行時(shí)才能確定，而在規(guī)劃時(shí)只能給出資源消耗的大致范圍。當(dāng)任務(wù)執(zhí)行發(fā)生資源沖突時(shí)，航天器需要考慮規(guī)劃結(jié)果中已執(zhí)行部分和未執(zhí)行部分的資源利用、分配情況，在資源總量一定的前提下給出合理有效的資源修復(fù)方案。

6)動(dòng)作時(shí)間連續(xù)性。每個(gè)航天器活動(dòng)都有一定持續(xù)時(shí)間，而且該持續(xù)時(shí)間可能也是變化的(如航天器姿態(tài)轉(zhuǎn)動(dòng)需要的時(shí)間長短是由初始姿態(tài)和目標(biāo)姿態(tài)之間的差值決定)，且由于環(huán)境存在不確定性，部分動(dòng)作的持續(xù)時(shí)間是不可控的(如著陸器的行進(jìn)時(shí)間與地形地貌等因素有關(guān))。當(dāng)動(dòng)作執(zhí)行發(fā)生時(shí)間沖突時(shí)，比如動(dòng)作過早發(fā)生、過早完成或者推遲發(fā)生、推遲完成等，需要一個(gè)良好的修復(fù)機(jī)制來保證任務(wù)繼續(xù)執(zhí)行。

2 自主任務(wù)規(guī)劃修復(fù)技術(shù)研究現(xiàn)狀

當(dāng)航天器執(zhí)行任務(wù)出現(xiàn)小范圍偏差，即動(dòng)作序列局部失效，且不需要額外的設(shè)備或知識時(shí)，自主任務(wù)規(guī)劃修復(fù)方法可以有效地使航天器從失敗中恢復(fù)。根據(jù)方法內(nèi)容，將目前的規(guī)劃修復(fù)技術(shù)分為下面五類：規(guī)則匹配型、局部調(diào)整型、刪除/求精型、狀態(tài)轉(zhuǎn)移型和構(gòu)造新問題型。每類所包含的修復(fù)方法以及各自的特點(diǎn)如表1所示。

表1 規(guī)劃修復(fù)方法分類Table 1 Classification of plan repair methods

2.1 規(guī)則匹配型修復(fù)策略

規(guī)則匹配型方法事先定義一系列的錯(cuò)誤修補(bǔ)規(guī)則，每一個(gè)規(guī)則描述對應(yīng)的任務(wù)在執(zhí)行失敗的情況下應(yīng)該如何進(jìn)行修復(fù)。當(dāng)實(shí)際執(zhí)行失敗時(shí)，便從規(guī)則集合中搜索解決方案，其算法流程如圖1所示。規(guī)則來自專家經(jīng)驗(yàn)，如“若太陽帆板未能正確對日定向，則調(diào)整航天器姿態(tài)”。應(yīng)用該技術(shù)的典型系統(tǒng)有CHEF系統(tǒng)[18]和O-Plan系統(tǒng)[19]。CHEF中的規(guī)則是對錯(cuò)誤的解釋，而O-Plan中的規(guī)則是一些提前定義好的規(guī)劃。當(dāng)執(zhí)行失敗時(shí)，CHEF自動(dòng)構(gòu)建解釋，包括導(dǎo)致失效的步驟信息、狀態(tài)信息以及這些失效步驟試圖實(shí)現(xiàn)的目標(biāo)集合?；谠摻忉?，CHEF從修復(fù)規(guī)則集合中選擇一個(gè)修復(fù)策略子集合進(jìn)行實(shí)例化，然后從該策略子集合中挑選最佳的修復(fù)策略。而O-Plan對于執(zhí)行失敗的動(dòng)作不采用失敗的解釋方法，而是從一些預(yù)定義的規(guī)劃中挑選一個(gè)規(guī)劃來滿足當(dāng)前失效動(dòng)作的效果。當(dāng)失敗時(shí)，執(zhí)行停止，一個(gè)修復(fù)規(guī)劃被插入執(zhí)行。由于規(guī)則是根據(jù)經(jīng)驗(yàn)制定，該策略只能應(yīng)對已知問題。

2.2 局部調(diào)整型修復(fù)策略

規(guī)劃和規(guī)劃修復(fù)通常被認(rèn)為是一次性完成的，即規(guī)劃器立即給出相應(yīng)的動(dòng)作序列。然而實(shí)際上，在動(dòng)態(tài)多變的環(huán)境中，規(guī)劃需要多次進(jìn)行。此時(shí)，充分利用之前的規(guī)劃過程和規(guī)劃結(jié)果，可以完成修復(fù)，如圖2所示。

2.2.1基于規(guī)劃庫的局部調(diào)整方法

保存之前的規(guī)劃結(jié)果形成規(guī)劃庫，其表示方法既有邏輯表示[20]，也有框架表示[21]；其儲(chǔ)存模式既可以保存整個(gè)規(guī)劃結(jié)果，如基于案例的規(guī)劃方法[22]，又可以保存部分規(guī)劃結(jié)果，如宏動(dòng)作表示的規(guī)劃修復(fù)方法[23]。執(zhí)行失敗時(shí)，基于案例的規(guī)劃方法通過規(guī)劃結(jié)果提取、規(guī)劃結(jié)果重用、規(guī)劃結(jié)果修訂等一系列操作，從規(guī)劃庫中提取相似問題的解并作一定修改，使得該解能夠解決當(dāng)前問題；而采用宏動(dòng)作表示的規(guī)劃修復(fù)方法在規(guī)劃庫中只包含領(lǐng)域中經(jīng)常出現(xiàn)的部分規(guī)劃，并引入宏動(dòng)作對庫中的規(guī)劃進(jìn)行管理。通過重新定義宏動(dòng)作的前提和效果，實(shí)現(xiàn)了多個(gè)宏動(dòng)作之間的匹配，完成規(guī)劃修復(fù)。

盡管有多種方法提高規(guī)劃庫的規(guī)劃修復(fù)效率，如Fukushima等[24]的正交表搜索，但航天器星上資源極其有限，其效率仍待進(jìn)一步提高。

2.2.2基于動(dòng)作模式重構(gòu)的局部調(diào)整方法

當(dāng)任務(wù)沒有明確的質(zhì)量要求時(shí)，通過調(diào)整動(dòng)作的部分參數(shù)，可以在不改變原有任務(wù)規(guī)劃指令序列整體的基礎(chǔ)上，完成任務(wù)規(guī)劃修復(fù)。例如，航天器成像動(dòng)作參數(shù)可以由高分辨率設(shè)置成低分辨率，數(shù)傳動(dòng)作參數(shù)可以由高頻傳輸改成低頻傳輸。這樣，既不影響原有指令序列的完整性，又能完成任務(wù)規(guī)劃修復(fù)。因此，Scala等[25]提出ReCon方法，將原規(guī)劃結(jié)果轉(zhuǎn)換成約束可滿足問題(Constraint satisfiability problem, CSP)模型，在執(zhí)行出現(xiàn)資源沖突時(shí)，對資源信息進(jìn)行更新并利用CSP求解器，調(diào)整動(dòng)作模式以解決該問題；而當(dāng)出現(xiàn)其它異常時(shí)，中止執(zhí)行過程，進(jìn)行完全重規(guī)劃。顯然，該方法只適用于對目標(biāo)沒有具體要求的任務(wù)修復(fù)，對于具有明確質(zhì)量要求的任務(wù)，如獲得高分照片，該方法會(huì)失效。

2.3 刪除/求精型修復(fù)策略

規(guī)劃結(jié)果的執(zhí)行是動(dòng)作有序完成的過程。當(dāng)執(zhí)行出現(xiàn)故障，找到失效動(dòng)作，將其刪除，并用新的動(dòng)作序列代替該失效動(dòng)作的效果插入到原命令序列中，即為刪除/求精型修復(fù)策略。如圖3所示，若相機(jī)因外界擾動(dòng)未能校準(zhǔn)，那么成像動(dòng)作會(huì)因?yàn)橄鄼C(jī)校準(zhǔn)的前提無法得到滿足而失效。此時(shí)，刪除該成像動(dòng)作，原命令序列變得不再“完整”，即不一致。通過規(guī)劃求精方法[26]尋找使命令序列一致的解即為規(guī)劃修復(fù)解。例如，航天器可以調(diào)整姿態(tài)，重新校準(zhǔn)相機(jī)，再調(diào)整姿態(tài)對目標(biāo)進(jìn)行觀測，接著繼續(xù)執(zhí)行原指令序列。若刪除成像動(dòng)作后通過求精無法找到解，擴(kuò)大動(dòng)作失效范圍，繼續(xù)嘗試求精，直至擴(kuò)展到目標(biāo)狀態(tài)。例如，若相機(jī)損壞無法校準(zhǔn)，則跳過觀測任務(wù)，直接進(jìn)行下一探測任務(wù)如采樣，或者直接返回規(guī)劃修復(fù)失敗標(biāo)記。

根據(jù)規(guī)劃求解方式的不同，在確定失效動(dòng)作范圍時(shí)，存在規(guī)劃圖、啟發(fā)式和分層任務(wù)網(wǎng)絡(luò)(Hierarchy task net, HTN)三種不同的刪除/求精型任務(wù)規(guī)劃修復(fù)方法。

2.3.1基于規(guī)劃圖的刪除/求精方法

規(guī)劃圖是一種特殊的數(shù)據(jù)結(jié)構(gòu)，命題層和動(dòng)作層交替向前擴(kuò)展，直至達(dá)到不動(dòng)點(diǎn)。基于規(guī)劃圖的規(guī)劃修復(fù)方法將當(dāng)前失效動(dòng)作的刪除/求精稱之為局部搜索，而將擴(kuò)展的失效動(dòng)作范圍求解稱之為系統(tǒng)搜索[14]。該方法優(yōu)先嘗試使用局部搜索來解決執(zhí)行失敗的問題。在求解過程中，由于失效動(dòng)作被刪除，原規(guī)劃結(jié)果出現(xiàn)缺陷，具體包括互斥動(dòng)作以及不被支持的前提條件或者目標(biāo)。通過添加動(dòng)作、給動(dòng)作排序等方法逐一解決暴露的缺陷，找到所有的修復(fù)方法，然后引入代價(jià)函數(shù)，最終確定最優(yōu)的規(guī)劃修復(fù)動(dòng)作序列。但由于規(guī)劃圖只能面向完全實(shí)例化的動(dòng)作而無法處理框架型動(dòng)作(部分實(shí)例化或者完全未實(shí)例化的動(dòng)作)，基于規(guī)劃圖的修復(fù)技術(shù)需要耗費(fèi)大量的計(jì)算時(shí)間和存儲(chǔ)資源來使動(dòng)作完全實(shí)例化。

2.3.2基于啟發(fā)式的刪除/求精方法

啟發(fā)式估計(jì)當(dāng)前搜索節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)值，用于挑選擴(kuò)展節(jié)點(diǎn)中最優(yōu)的那個(gè)，指導(dǎo)規(guī)劃的搜索方向。Krogt等[27]以當(dāng)前規(guī)劃結(jié)果為根節(jié)點(diǎn)，通過構(gòu)建“移除樹”這種數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)啟發(fā)式，以選擇合適的移除樹并對其進(jìn)行生長、合并操作，從而確定當(dāng)前規(guī)劃結(jié)果中應(yīng)該刪除的動(dòng)作范圍。但是這個(gè)修復(fù)過程只能處理初始條件或者目標(biāo)狀態(tài)改變的情況，無法處理中間過程失效的情況。對此，Arangú等[28]通過核實(shí)和修復(fù)，提出了一種通用的修復(fù)方法，對其進(jìn)行了完善。基于啟發(fā)式的規(guī)劃修復(fù)方法將規(guī)劃和規(guī)劃修復(fù)技術(shù)聯(lián)系在一起，但是由于通過試錯(cuò)法逐層擴(kuò)展移除樹，耗時(shí)且具有一定盲目性。

2.3.3基于HTN的刪除/求精方法

HTN規(guī)劃通過行動(dòng)分解方法，不斷地分解、改進(jìn)規(guī)劃問題，直至達(dá)到系統(tǒng)能直接執(zhí)行的原子行動(dòng)。在確定失效動(dòng)作范圍時(shí)，基于HTN的規(guī)劃修復(fù)方法存在兩種方式：局部型和全局型。局部型在失敗動(dòng)作的周圍添加動(dòng)作，如PRIAR[29]。PRIAR利用節(jié)點(diǎn)之間的因果關(guān)系構(gòu)建驗(yàn)證結(jié)構(gòu)，通過它來明確失敗的位置和具體特征，并根據(jù)這些特征選擇相應(yīng)的修復(fù)策略。全局型在整個(gè)計(jì)劃之中搜尋失效的動(dòng)作的范圍，然后進(jìn)行刪除/求精操作，如Replan算法[30]。Replan用演繹樹(derivation tree)記錄HTN規(guī)劃結(jié)果的生成過程。當(dāng)執(zhí)行失敗時(shí)，對應(yīng)于演繹樹上一個(gè)失效的葉節(jié)點(diǎn)，包含該節(jié)點(diǎn)的最小子樹被刪除，然后不完整的部分經(jīng)過HTN規(guī)劃器的求精操作變得完整，規(guī)劃修復(fù)也就完成任務(wù)。在確定最小子樹的時(shí)候，采用試錯(cuò)法逐層擴(kuò)展，直至找到解或者擴(kuò)展到整個(gè)任務(wù)網(wǎng)絡(luò)。該方法有一定應(yīng)用[31-32]，但是仍然采用試錯(cuò)法確定動(dòng)作失效范圍，影響規(guī)劃修復(fù)的效率。

2.4 狀態(tài)轉(zhuǎn)移型修復(fù)策略

動(dòng)作包含前提和效果，若其前提在某一狀態(tài)下得到滿足，那么執(zhí)行動(dòng)作就能將其效果作用于該狀態(tài)，從而實(shí)現(xiàn)不同狀態(tài)之間的轉(zhuǎn)移。在動(dòng)作執(zhí)行失敗時(shí)，通過狀態(tài)轉(zhuǎn)移，尋找合適的動(dòng)作序列，代替原效果，即完成規(guī)劃修復(fù)。例如，動(dòng)作navigate(l1,l2)表示火星車由地點(diǎn)l1前進(jìn)到l2，其前提條件包括火星車位于l1、電源充足，其效果為火星車位于l2。若在即將執(zhí)行該動(dòng)作的時(shí)候發(fā)現(xiàn)電池能量不夠，該動(dòng)作不應(yīng)被執(zhí)行。此時(shí)，若應(yīng)用狀態(tài)轉(zhuǎn)移型修復(fù)策略，需搜索效果為使電池充電的動(dòng)作，來滿足navigate的前提。如圖4所示?；谶@一思想，Guzman等[33]采用“規(guī)劃窗口”限制規(guī)劃修復(fù)的長度和深度，將整個(gè)規(guī)劃結(jié)果分成幾部分并對各部分提前計(jì)算修復(fù)結(jié)構(gòu)體。當(dāng)任務(wù)執(zhí)行失敗時(shí)，在修復(fù)結(jié)構(gòu)體中尋找一條路徑到達(dá)指定狀態(tài)；當(dāng)不存在這樣的路徑，進(jìn)行完全重規(guī)劃。

而在開始進(jìn)行修復(fù)之前，對完全重規(guī)劃策略和規(guī)劃修復(fù)策略進(jìn)行評價(jià)選優(yōu)，往往能夠提高規(guī)劃修復(fù)的效率。為此，Garrido等[34]將執(zhí)行失敗后的原規(guī)劃結(jié)果P分割成前、后兩部分，即P1和P2，通過采用忽略動(dòng)作負(fù)效果的松弛策略來分別計(jì)算完全重規(guī)劃策略的代價(jià)值Ereplan和規(guī)劃修復(fù)策略的代價(jià)值Erepair，如式(1)和式(2)所示。其中，C(X)表示計(jì)算規(guī)劃結(jié)果X的代價(jià)值函數(shù)。

Ereplan=C(P)+0

(1)

Erepair=C(P1)+C(P2)

(2)

該策略利用后向搜索，在規(guī)劃修復(fù)時(shí)速度快，但是在確定需要到達(dá)的子目標(biāo)狀態(tài)時(shí)，仍通過試錯(cuò)法嘗試，搜索效率可進(jìn)一步提高。

2.5 構(gòu)造新問題型修復(fù)策略

對于給定的任務(wù)，規(guī)劃器能夠給出該問題對應(yīng)的有序動(dòng)作解，即計(jì)劃。當(dāng)任務(wù)執(zhí)行失敗時(shí)，從原有計(jì)劃中提取相關(guān)信息構(gòu)造新問題，再次利用規(guī)劃器也可以完成規(guī)劃修復(fù)，如圖5所示。提取的信息包括可用動(dòng)作、動(dòng)作間的約束等。

2.5.1基于數(shù)字宏動(dòng)作的修復(fù)方法

宏動(dòng)作是幾個(gè)互相聯(lián)系的動(dòng)作集合。宏動(dòng)作結(jié)合數(shù)值型變量形成的數(shù)字宏動(dòng)作，可以用來處理實(shí)際任務(wù)執(zhí)行時(shí)資源消耗沖突和動(dòng)作失效的問題。例如對于觀測任務(wù)，可將姿態(tài)調(diào)整、相機(jī)校準(zhǔn)、姿態(tài)調(diào)整、目標(biāo)成像這四個(gè)動(dòng)作看成一個(gè)宏動(dòng)作，而其中每個(gè)動(dòng)作均會(huì)消耗一定的電能。類似地，從原計(jì)劃中提取若干個(gè)這樣的宏動(dòng)作集合，并把它們作為附加內(nèi)容加入到規(guī)劃領(lǐng)域動(dòng)作知識中，再利用規(guī)劃器對失敗問題求解，也可完成任務(wù)規(guī)劃修復(fù)。而關(guān)于如何提取有效的數(shù)字宏動(dòng)作，Scala[35]作了詳細(xì)的研究。

2.5.2基于PSP的修復(fù)方法

航天器的規(guī)劃結(jié)果中包含對航天器各子系統(tǒng)或其他航天器的承諾。這些承諾既包括各系統(tǒng)之間的協(xié)議，如相機(jī)工作的時(shí)候主發(fā)動(dòng)機(jī)應(yīng)關(guān)閉，也包括規(guī)劃修復(fù)技術(shù)中的穩(wěn)定性，即動(dòng)作穩(wěn)定性(新舊計(jì)劃之間的動(dòng)作序列組成盡可能相似，如火星車在前進(jìn)過程中電能不足導(dǎo)致動(dòng)作執(zhí)行失敗，未能抵達(dá)目標(biāo)位置，滿足動(dòng)作穩(wěn)定性要求的修復(fù)解應(yīng)該是打開太陽帆板，給電池儲(chǔ)能，待電充滿后，繼續(xù)執(zhí)行剩余指令)和因果鏈穩(wěn)定性(新舊計(jì)劃之間的動(dòng)作序列因果關(guān)系盡可能相似，如原計(jì)劃中航天器先轉(zhuǎn)向A方向進(jìn)行相機(jī)校準(zhǔn)再轉(zhuǎn)向B方向進(jìn)行觀測，那么滿足穩(wěn)定性要求的新計(jì)劃應(yīng)該盡可能保留這一條因果鏈)。通過搜集這些承諾信息，并把它們作為軟目標(biāo)(盡可能完成的目標(biāo))，加入新問題之中，再利用PSP規(guī)劃器進(jìn)行求解，就可以完成規(guī)劃修復(fù)[36]。

構(gòu)造新問題的規(guī)劃修復(fù)方法從原有計(jì)劃中提取有用信息，有效地縮小新舊計(jì)劃之間的差異，提高規(guī)劃穩(wěn)定性。但是對于航天器尤其是多星來說，系統(tǒng)組成復(fù)雜且耦合性強(qiáng)，若任何小錯(cuò)誤都需要利用任務(wù)規(guī)劃器來修復(fù)，無疑會(huì)增加任務(wù)規(guī)劃器的壓力。

3 航天器任務(wù)規(guī)劃穩(wěn)定性分析

動(dòng)態(tài)環(huán)境下執(zhí)行計(jì)劃可能出現(xiàn)失敗，此時(shí)規(guī)劃修復(fù)方法比完全重規(guī)劃方法更具優(yōu)勢。而規(guī)劃修復(fù)方法離不開穩(wěn)定性的要求。

定義2. (航天器任務(wù)規(guī)劃穩(wěn)定性)使用規(guī)劃修復(fù)方法來解決航天器任務(wù)規(guī)劃結(jié)果執(zhí)行失敗的問題，如果新計(jì)劃中包含原計(jì)劃的關(guān)鍵信息，如動(dòng)作的種類、順序、數(shù)量等，那么就稱該新計(jì)劃是規(guī)劃穩(wěn)定的，且新舊計(jì)劃之間相同部分越多，穩(wěn)定性越強(qiáng)。

在規(guī)劃修復(fù)時(shí)遵循穩(wěn)定性的要求，可以通過模式診斷識別動(dòng)作執(zhí)行失敗的原因，獲取關(guān)鍵的約束信息，并在無法成功修復(fù)時(shí)，保證系統(tǒng)能夠處于安全狀態(tài)[37]；也可以將原計(jì)劃中的信息作為軟約束加入到問題之中，用PSP技術(shù)進(jìn)行求解；還可以將原計(jì)劃片段化，通過組合的方式，達(dá)到充分利用原計(jì)劃信息的目的[38]。

然而這些都是定性地描述穩(wěn)定性，缺乏統(tǒng)一的定量標(biāo)準(zhǔn)來評價(jià)穩(wěn)定性大小。Fox等[39]通過定義兩個(gè)計(jì)劃之間的距離來度量修復(fù)計(jì)劃的穩(wěn)定性大小，如式(3)所示。

S(PB)=nα+nβ

(3)

式中：S(PB)表示計(jì)算計(jì)劃PB穩(wěn)定性大小的函數(shù)。若用PA表示原計(jì)劃，PB表示修復(fù)計(jì)劃，則nα表示在PA中但不在PB中動(dòng)作的數(shù)目，nβ表示在PB中但不在PA中動(dòng)作的數(shù)目。

而Garrido等[34]通過百分比的方式來度量修復(fù)計(jì)劃的穩(wěn)定性大小，即PB中屬于PA的動(dòng)作的數(shù)目nη與PB中動(dòng)作總數(shù)nω的比值，定義如下：

S(PB)=nη/nω

(4)

上述兩種定量描述穩(wěn)定性的方法雖然能夠給出規(guī)劃修復(fù)穩(wěn)定的評價(jià)標(biāo)準(zhǔn)，但并未考慮到計(jì)劃中動(dòng)作的順序關(guān)系。Scala等[25]將規(guī)劃修復(fù)看成是在原有計(jì)劃PA的基礎(chǔ)上，通過一定的修復(fù)操作得到修復(fù)計(jì)劃PB的過程。該修復(fù)操作被歸納為插入Oadd、刪除Odel、替換Oremod和交換Oswap四種，其中替換是指改變動(dòng)作的模式，交換是指改變兩個(gè)連續(xù)動(dòng)作之間的順序。每種操作依次被賦予代價(jià)值α,α,γ,θ，且滿足關(guān)系γ?α<θ<2α，那么將計(jì)劃PA轉(zhuǎn)換成PB的代價(jià)EPA→PB如式(5)所示：

EPA→PB=α·Oadd+α·Odel+γ·Oremod+θ·Oswap

(5)

若用ER表示一個(gè)參考轉(zhuǎn)換代價(jià)值，通過完全移除PA中的動(dòng)作之后，再把所有動(dòng)作插入到PB中來獲得；用Et表示所有從PA轉(zhuǎn)換成PB代價(jià)值中最小的代價(jià)值，那么PB的穩(wěn)定性大小S(PB)就被定義為：

S(PB)=(ER-Et)/ER

(6)

但是，高穩(wěn)定性不一定能夠保證高質(zhì)量的規(guī)劃結(jié)果[40]。原有計(jì)劃中除了包含動(dòng)作的種類、順序、數(shù)量等信息外，還包括因果鏈、合作關(guān)系等約束信息。因此，在以不考慮約束影響的穩(wěn)定性評價(jià)方法為導(dǎo)向的情況下，搜索規(guī)劃修復(fù)解時(shí)很有可能找到一個(gè)動(dòng)作序列相似度高但約束被極大破壞的解，影響計(jì)劃的執(zhí)行效率。

4 航天器自主任務(wù)規(guī)劃修復(fù)技術(shù)總結(jié)和發(fā)展建議

在任務(wù)執(zhí)行過程中出現(xiàn)執(zhí)行失敗情況時(shí)，航天器自主任務(wù)規(guī)劃修復(fù)面向任務(wù)目標(biāo)，應(yīng)用一定的技術(shù)方法，生成修復(fù)命令序列，使航天器恢復(fù)正常。不同的任務(wù)規(guī)劃修復(fù)方法應(yīng)用不同的策略，完成規(guī)劃修復(fù)，各自的優(yōu)缺點(diǎn)總結(jié)如表2所示。

分析各類任務(wù)規(guī)劃修復(fù)方法，不難發(fā)現(xiàn)，它們都是通過修改領(lǐng)域動(dòng)作集合和子目標(biāo)來達(dá)到任務(wù)規(guī)劃修復(fù)的目的。因此，可用規(guī)劃修復(fù)問題來統(tǒng)一描述各類規(guī)劃修復(fù)方法。

定義3.(規(guī)劃修復(fù)問題)一個(gè)規(guī)劃修復(fù)問題是一個(gè)三元組P=(O,α,γ)，其中，O表示可用操作集合，α表示動(dòng)作執(zhí)行失敗時(shí)的狀態(tài)或者未來可能會(huì)失敗的狀態(tài)，γ表示通過規(guī)劃修復(fù)能夠達(dá)到的狀態(tài)。

表2 現(xiàn)有多種規(guī)劃修復(fù)方法的優(yōu)缺點(diǎn)對比Table 2 Comparison of advantages and disadvantages of existing plan repair methods

規(guī)則匹配型修復(fù)策略中的O通過規(guī)則定義；局部調(diào)整型修復(fù)策略中的O源于歷史計(jì)劃；基于數(shù)字宏動(dòng)作的修復(fù)方法中的O是從原計(jì)劃中提取的數(shù)字宏動(dòng)作和原有動(dòng)作的組合；刪除/求精型修復(fù)策略和狀態(tài)轉(zhuǎn)移型修復(fù)策略的γ是通過試錯(cuò)法確定的、能夠使規(guī)劃修復(fù)完成的某個(gè)狀態(tài)；基于PSP修復(fù)方法中的γ是繼承原計(jì)劃約束的軟目標(biāo)。

把規(guī)劃修復(fù)方法應(yīng)用到航天領(lǐng)域，需要考慮到航天領(lǐng)域的系統(tǒng)耦合性、資源有限性等特殊性質(zhì)。從當(dāng)前的研究進(jìn)展和需要解決的問題來看，建議規(guī)劃修復(fù)技術(shù)在未來航天領(lǐng)域研究的發(fā)展方向?yàn)橄率隽鶄€(gè)方面。

1)規(guī)劃修復(fù)的可行性研究

規(guī)劃修復(fù)的可行性，即在修復(fù)之前，判斷該問題是否可以通過規(guī)劃修復(fù)方法解決。因?yàn)橐?guī)劃修復(fù)不一定能夠保證找到執(zhí)行失敗的解決方法，且航天器資源有限，同時(shí)任務(wù)有效時(shí)間確定，若花費(fèi)太多代價(jià)用于嘗試求解一個(gè)不可能通過規(guī)劃修復(fù)解決的失敗問題，勢必影響任務(wù)完成的質(zhì)量和效率。因此有必要在對執(zhí)行失敗的任務(wù)修復(fù)之前，判斷該問題的規(guī)劃修復(fù)可行性。

2)規(guī)劃修復(fù)的及時(shí)性研究

航天器資源有限且任務(wù)周期一般固定不變，當(dāng)任務(wù)出現(xiàn)執(zhí)行失敗情況時(shí)，會(huì)影響任務(wù)的完成情況。如何保證在任務(wù)截止時(shí)間之前，航天器能夠采取有效的修復(fù)方案從失敗中恢復(fù)，就需要修復(fù)的時(shí)間盡可能得短。

3)確定動(dòng)作失效范圍方法的研究

無論是刪除/求精型規(guī)劃修復(fù)方法還是狀態(tài)轉(zhuǎn)移型規(guī)劃修復(fù)方法，在尋找動(dòng)作失效范圍時(shí)，都是采用試錯(cuò)法從當(dāng)前動(dòng)作開始，刪除當(dāng)前動(dòng)作，然后嘗試求精操作。如果一個(gè)解決方法需要?jiǎng)h除原規(guī)劃結(jié)果尾部的動(dòng)作，那么通過試錯(cuò)法的方式必定要浪費(fèi)很多搜索時(shí)間。如果能夠精準(zhǔn)有效地確定動(dòng)作的失效范圍，就會(huì)大大縮短規(guī)劃修復(fù)的搜索時(shí)間，提高規(guī)劃修復(fù)的效率。

4)系統(tǒng)級規(guī)劃修復(fù)的研究

在實(shí)際環(huán)境中，尤其是動(dòng)態(tài)環(huán)境中執(zhí)行任務(wù)，當(dāng)遇到執(zhí)行失敗的情況，應(yīng)用規(guī)劃修復(fù)方法解決該問題時(shí)，存在局部和系統(tǒng)兩種策略。局部策略只修復(fù)當(dāng)前暴露的問題，修復(fù)完成后，就讓智能體開始執(zhí)行新計(jì)劃；系統(tǒng)策略此外還檢查當(dāng)前狀態(tài)下未執(zhí)行的部分是否存在隱患，并解決整個(gè)計(jì)劃的缺陷，從而使得規(guī)劃修復(fù)完成后，生成的新計(jì)劃魯棒性更強(qiáng)。目前存在的規(guī)劃修復(fù)方法大都采用局部策略，只解決當(dāng)前出現(xiàn)的問題，而對系統(tǒng)策略研究較少。

5)并行動(dòng)作、時(shí)間和資源沖突的研究

航天器實(shí)際執(zhí)行任務(wù)時(shí)，除了必要的動(dòng)作信息之外，還需要時(shí)間和資源的參與。無論資源還是時(shí)間在執(zhí)行時(shí)出現(xiàn)沖突，都會(huì)導(dǎo)致整個(gè)任務(wù)的失敗。而目前針對并行動(dòng)作、時(shí)間沖突和資源沖突的規(guī)劃修復(fù)方法研究較少，限制了自主規(guī)劃技術(shù)在實(shí)際航天任務(wù)中的應(yīng)用。

6)規(guī)劃穩(wěn)定性的評價(jià)標(biāo)準(zhǔn)研究

規(guī)劃修復(fù)方法的好壞需要通過一定的評價(jià)標(biāo)準(zhǔn)來判斷，其中一個(gè)評價(jià)標(biāo)準(zhǔn)就是規(guī)劃穩(wěn)定性。規(guī)劃穩(wěn)定性的評價(jià)既要考慮兩個(gè)計(jì)劃之間的動(dòng)作數(shù)量、動(dòng)作之間的順序關(guān)系，也要考慮到計(jì)劃中包含的約束關(guān)系，并采用定量方式以便于普遍接受。

5 結(jié) 論

航天器自主運(yùn)行是未來航天發(fā)展的必然趨勢。本文闡述了將規(guī)劃與執(zhí)行融為一體的航天器自主任務(wù)規(guī)劃修復(fù)的必要性和難點(diǎn)，將自主任務(wù)規(guī)劃修復(fù)技術(shù)歸納為規(guī)則匹配型、局部調(diào)整型、刪除/求精型、狀態(tài)轉(zhuǎn)移型和構(gòu)造新問題型五類分別進(jìn)行描述，分析了規(guī)劃穩(wěn)定性的定量評價(jià)方法，并將規(guī)劃修復(fù)技術(shù)總結(jié)為對規(guī)劃修復(fù)問題元素的部分修改。

實(shí)際的航天任務(wù)規(guī)劃與執(zhí)行是動(dòng)作、時(shí)間、資源三者相互作用的復(fù)雜過程，然而目前少有關(guān)于多因素影響下的任務(wù)規(guī)劃修復(fù)方法理論研究。因此未來的航天器自主規(guī)劃修復(fù)技術(shù)研究重點(diǎn)應(yīng)該在于動(dòng)作、資源和時(shí)間方面的復(fù)合修復(fù)策略研究、規(guī)劃修復(fù)的可行性和及時(shí)性研究、高效的失效動(dòng)作范圍確定方法研究以及規(guī)劃穩(wěn)定性的定量判定標(biāo)準(zhǔn)等研究方向。