小天體柔性著陸任務規劃的動態時間約束推理方法

王棒，徐瑞，李朝玉，朱圣英，梁子璇

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

0 引言

小天體探測是深空探測的重要內容之一。實施小天體表面探測具有重要的科學與工程意義，對空間科學、行星科學、材料科學等領域的發展均有著促進作用［1］。迄今為止，各航天機構已實施了多項小天體探測任務，在這些任務中，有些探測器已經與小天體表面進行了接觸或者向其投放了小型探測裝置［2］。中國也以2016HO3 小行星及311P 彗星為目標推進小天體探測任務。相較于飛越和環繞探測，著陸探測無疑能夠獲得更全面和準確的小天體科學數據。

目前小天體著陸的主要難題在于其復雜弱引力環境以及未知的表面土壤性質，著陸器易發生反彈和逃逸。歐空局“羅塞塔”探測器釋放的“菲萊”著陸器［3-4］接觸到了67P 彗星的表面，但是錨定機構未能按計劃展開，在表面發生了明顯的翻滾彈跳。日本的“隼鳥”號［5］、“隼鳥”2號［6］以及美國的OSIRIS-REx 探測器［7］僅接觸小天體表面進行采樣，并未實現長時間的表面穩定著陸。為解決傳統“剛性+緩沖”及“接觸即走”著陸方式帶來的不足，崔平遠等［8］提出了柔性著陸的概念，文獻［9］圍繞該著陸方式對自主導航與制導控制等關鍵技術的研究進展與難點進行了總結和分析。如圖1 所示，著陸器由質量聚集區（節點）及智能柔性材料兩部分組成，通過增大與小天體表面的接觸面積降低傾覆翻滾的風險，同時柔性材料可消耗著陸的殘余動能，避免著陸器反彈逃逸。該著陸器具有節點間活動并行、約束耦合復雜、柔性干擾不確定等特點，因此著陸器需具備任務規劃技術以提高其自主決策能力，實現復雜小天體環境下的安全著陸。

圖1 柔性著陸器示意圖Fig.1 Illustration of the flexible multi-node lander

相較于傳統剛性著陸器，柔性連接的存在使得柔性著陸器活動間的時間約束更加嚴格、耦合。例如：t1，t2，t3分別為3 個節點的著陸時間約束，如圖2所示，為滿足柔性連接約束，在著陸整個過程中還需保證3個時間的相互差值在一定范圍內。在柔性著陸器的規劃過程中，每步規劃均是在規劃空間中搜索滿足要求的活動來改變或擴展當前的部分規劃，該過程的活動和時間約束信息是動態變化的。并且由于柔性連接約束不確定性的影響，節點的規劃序列執行過程不是完全可控的，當執行出現偏差時，需要修復當前已有規劃，對不確定性的干擾做出動態響應，快速確定規劃修復后的活動執行區間，以提高著陸任務的安全性。因此，規劃過程中時間約束推理的效率提升直接影響到規劃速度。

圖2 時間約束耦合Fig.2 Temporal constraints coupling

時間約束推理是任務規劃技術的重要組成部分，深空一號的遠程智能體證明了自主任務規劃問題中時間信息傳播高效處理的重要性［10］。目前時間約束推理方法主要包括路徑一致與弧一致兩大類。Floyd-Warshall算法［11］可以計算時間約束網絡中任意兩個頂點間的最短路徑，該方法約束傳播次數多，計算效率較低。因此部分路徑一致概念被應用于時間約束求解。ΔSTP 算法［12］以部分路徑一致求解為核心，以存儲資源為代價提高了計算效率，有效降低了約束推理次數。P3C 算法［13］采用有向路徑一致（DPC），強制執行部分路徑一致，進一步提高了時間約束推理效率。弧一致算法也通常被用于進行一致性判斷，該類算法主要包括AC-1 到AC-7、AC-2000、AC-2001等［14］。Kong等［15］提出了ACSTP算法用以解決時間約束問題，在減少約束推理次數方面優于現有算法。美國火星探測車使用的MAPGEN［16］規劃系統使用了基于弧一致的算法保證時間約束的一致，并保留了最大的時間靈活性。

但在動態的規劃過程中，對于以上方法，每添加一個活動就需要對當前網絡所有時間變量進行一次遍歷計算，隨著約束的增加，時間約束的計算量顯著增加，從而影響到規劃效率。針對這一問題，有學者提出了時間約束網絡增量式維護方法。增量全路徑一致（IFPC）算法［17］通過更新部分網絡來維護全路徑一致，增量部分路徑一致（IPPC）算法［18］在添加新約束或收緊現有約束時保持部分路徑一致性來維護當前網絡。Xu等［19］提出時間約束幾何分組動態推理（GDAC）算法，減少時間約束推理過程中的重復計算等。現有增量式方法大多以路徑一致為基礎，在計算過程中會額外增加新的約束，從而增加計算代價，基于弧一致的算法可有效避免這一缺陷。

本文針對小天體柔性著陸器著陸任務規劃中的復雜時間約束推理問題，建立任務規劃中的活動時間約束網絡，進而劃分約束類型，分析不同類型約束在時間網絡中的傳播特點，設計零點約束優先添加策略，減小規劃過程中的時間約束傳播范圍。提出動態弧一致時間約束推理方法，局部求解時間約束網絡一致性，獲得著陸器系統可執行活動的最小可行區間。最后構建小天體著陸規劃場景，從多方面驗證了所提方法的有效性和高效性。

1 問題描述及模型建立

1.1 任務規劃問題描述

本文主要研究小天體柔性著陸器著陸任務規劃中的時間約束一致性推理問題。柔性著陸器著陸規劃需要在復雜約束條件下求解每個系統待執行活動的可行起止時間。每個活動的時間信息可以由集合{s，d，e}來表示（s，d，e分別表示活動的開始時間、持續時間、結束時間），不同活動間存在復雜時間約束關系。例如：節點相機成像活動的開始時刻必須在姿態機動活動的結束時刻之后，并且每個節點的成像活動必須同時進行，以獲得同時刻的圖像用于著陸導航。首先描述柔性著陸器任務規劃問題如下：

定義1.小天體著陸任務規劃問題ΠA可采用如下元組表示：

式中：A為著陸器節點集合，Sa為節點包含的系統集合，Ox為系統可執行活動集合，Cx為活動的時間約束集合，Ix為系統初始狀態，Gx為系統目標狀態。

定義2.系統可執行活動oi∈Ox的時間信息可表示為如下元組：

式中：si為活動oi的開始時間點，ei為結束時間點，di為活動的持續時間，Ci為該活動與其他活動間的時間約束關系集合。

定義3.柔性著陸器著陸任務規劃中的時間約束問題S=定義為一個一組有限時間點變量集合X={x1，x2，…，xn}和一組時間變量上的約束C={c1，c2，…，cm}。每個變量代表一個規劃活動的開始或結束時間點，變量間的約束代表時間點之間的關系，對于定義在連續域上的時間點變量u，v∈X，其約束關系為一組線性不等式：

其中，a，b均為實數。

若存在時間變量賦值{x1=r1，x2=r2，…，xn=rn}滿足所有約束，則當前規劃活動的時間約束問題是一致的。

1.2 時間約束網絡構建

為求解上述時間約束問題的一致性，并獲得每個活動起止時間的最小可行區間，將該問題表示為加權有向圖，也即時間約束網絡G=。V為圖的頂點集合，E為頂點間的邊集合。時間變量u∈X表示為圖中的頂點，變量間約束表示為邊。

對于時間變量u，v，約束表示為區間Iuv=[a，b]，若u，v屬于同一活動，則Iuv表示的是活動內部約束，即活動持續時長，若u，v屬于不同活動，則Iuv表示活動間約束。如圖3 所示，定義著陸任務執行的時間零點z，則活動的起止可執行時間為時間變量與時間零點間的約束關系，也即變量值域Iu=Izu，Iv=Izv。每個活動的開始時間點與結束時間點變量si，ei∈V，V={s1，e1，…，si，ei，…sn，en}∪{z}，n為當前部分規劃中包含的活動數。變量間的時間約束表示為網絡中頂點間的有向邊權重，wsiei=bsiei，weisi=-asiei或Isiei=[-weisi，wsiei]=-Ieisi。

圖3 時間約束網絡示例Fig.3 Temporal constraint network example

根據變量間的時間約束關系進一步劃分約束類型，如圖4所示。As，Ae和Bs，Be分別表示活動A和活動B 的開始及結束時間點。其中，變量點與時間零點z間的約束稱為零點約束（Cz），如IzAs=[8，11]表示活動A 的開始執行區間；同一活動的時間點變量間約束稱為內部約束（CI），如IBsBe=[1.5，2]表示活動B 的可持續時間；不同活動的時間點變量間約束稱為外部約束（CE），如IAsBs=)[1，∞表示活動B 至少在活動A 開始執行1 個單位時間之后再開始執行。從而時間約束網絡G的邊集表示為式（4），每條邊(u，v)綁定約束類型Tuv，Tuv∈{Cz，CI，CE}。

圖4 約束類型劃分Fig.4 Constraint type

對于定義在圖G上的時間變量u，v∈V，存在路徑u→v，其距離為Iuv。若存在時間變量j∈V，使得路徑u→j→v有更短的距離，則更新Iuv。時間約束一致性推理的本質在于通過式（5）和（6）收緊原始約束，判斷是否當前規劃的所有活動約束都得到滿足，并且求解當前網絡中每個活動開始與結束的最小可行時間區間。

其中，運算符?定義為[a，b]?[c，d]?[a+c，b+d]，并且[a，b]????，若存在=?，則說明當前規劃中活動的時間約束是不一致的，執行一次式（6）稱為一次約束推理。

根據柔性著陸器每個系統的初始狀態與目標狀態初始化時間網絡，隨著規劃活動的添加，逐步擴展網絡規模并求解時間約束問題。

2 動態弧一致時間約束推理

柔性著陸器的規劃過程中活動和時間約束都是動態變化的，約束信息的傳播會影響當前已有規劃活動的執行區間，若每次改變都對全局時間網絡進行一次推理，則計算效率嚴重降低，本文提出一種動態弧一致時間約束推理方法，設計零點約束優先添加策略，根據添加的約束類型不同限制約束傳播范圍，僅對局部約束網絡進行推理，減少規劃中活動動態變化的影響范圍，提高時間問題的求解效率。

2.1 時間網絡弧一致

弧一致算法僅需求解每個變量值域的最小區間。也即，僅對變量與時間零點間的約束區間進行求交計算。

定義4.對于時間約束網絡G=，u，v∈V，且值域分別為Iu，Iv，存在約束Iuv∈C。若對于任意tu∈Iu，存在tv∈Iv使得tv-tu∈Iuv，則Iuv相對于Iu和Iv是弧一致的。若對于任意約束Iuv∈C，Iuv和Ivu都是弧一致的，則約束網絡G是弧一致的。

對于變量i∈V，構建其鄰居變量集合Nei={j|(i，j)∈E}。弧一致算法在迭代中通過式（7）計算每個變量的新值域，若所有變量值域都計算完成后?i∈V，且Ii≠，則繼續下一次迭代，直到對于?i∈V滿足條件Ii=

2.2 約束添加策略

規劃過程中的活動是逐步添加的，如圖5所示，對于當前規劃的待添加活動oi∈Ox，需要執行約束推理的時間網絡包含兩部分：當前部分規劃中活動的時間變量和約束構建的原網絡G0=以及待添加活動的時間變量和與G0中變量相關的局部約束網絡Gp=。

圖5 待處理約束Fig.5 Pending constraints

為實現時間約束網絡的局部動態維護，將活動oi相關的3 類約束逐條添加至原網絡，從而對于每條新添加的約束而言，其對應的原網絡=<>為G0與已添加至G0中的前序約束的并集。定義新添加約束的兩個變量為u，v，邊為euv，則該約束與G′0存在以下3類從屬關系。

1)u，v?且euv?，該約束的添加不會對已有活動的時間可行區間造成影響，該情況下無需執行時間約束推理，約束推理次數為0。

2)u∈，v?且euv?，該情況有 兩種可能，當Tuv=Cz時，時間變量v與中任意變量都不存在約束關系，因此該約束的添加不會影響中的時間區間，無需執行時間約束推理，約束推理次數為0；當Tuv=CI或Tuv=CE時，變量u的值域通過邊euv傳播，根據Iv=Iu?Iuv推理變量v的值域，約束推理次數為1。

3)u，v∈V′0，同樣存在兩種可能，當Tuv=Cz時，根據第二種情況的分析可知，由于該活動前序約束的添加，變量v的值域Iv已通過約束推理得出，此時?euv∈。因此該約束首先與已有值域Iv進行求交計算，若計算后的值域=Iv，則該約束不影響G′0中的時間區間，約束推理次數為1；若?Iv，則該約束必定在網絡中傳播，推理變量v的鄰居變量值域，若鄰居變量值域也發生改變，則約束進一步傳播，約束推理次數為式（8）。

當Tuv=CI或Tuv=CE時，需要分別計算變量u，v對互相值域的影響，進而根據區間減小與否執行約束傳播，約束推理次數為式（9）。

根據上述3類從屬關系下約束推理次數不同的分析可知，不同類型約束的添加順序會影響約束的傳播范圍。對于活動oi∈Ox，根據定義的約束類型Tuv∈{Cz，CI，CE}，存在2 條零點約束、1 條內部約束及m條外部約束，有以下6種添加順序，其約束推理次數分別為式（10）至式（15）。

1) 零點約束→內部約束→外部約束

2) 零點約束→外部約束→內部約束

3) 內部約束→零點約束→外部約束

4) 內部約束→外部約束→零點約束

5) 外部約束→零點約束→內部約束

6) 外部約束→內部約束→零點約束

其中，n0為活動oi添加前的時間約束網絡中變量數；ax(x=0，1，…，m)表示第x條外部約束添加后值域發生改變的變量；b0，bin，均為布爾值，分別表示零點約束、內部約束及第j條外部約束添加后是否改變原網絡中的變量值域，若發生改變，則為1，反之則為0(x=0，1，…，m)分別表示未添加內部約束和已添加內部約束時，第x條外部約束添加后第i個變量的鄰居變量集合。

計算上述6 種添加順序下的約束推理次數，易得式（16）。

對于r1，r2而言，分3種情況討論：

1) 最小時間網絡來自于內部約束傳播，則外部約束的添加不會改變原網絡中的變量值域，即=0，式（17）成立。

2) 最小時間網絡來自于外部約束傳播，則內部約束的添加不會改變原網絡中的變量值域，即bin=0，式（18）成立。

3) 最小時間網絡來自于零點約束，也即初始值域為最小值域，約束不傳播，bin==0，式（19）成立。

內部約束與外部約束添加造成的約束傳播范圍與實際問題中的約束關系和約束數值有關，理論推導無法比較r1，r2的大小。因此，提出動態時間約束推理中的零點約束優先策略，以盡可能減小規劃活動的約束傳播范圍，內部約束及外部約束可隨機添加。針對柔性著陸器著陸任務，考慮規劃過程中逐步添加的16個系統活動，包括96條約束。圖6顯示了6 種添加順序下的約束推理次數曲線，進一步驗證了所提策略的有效性。

圖6 6種添加順序下的約束推理次數Fig.6 Number of constraint reasoning in six add orders

2.3 動態約束推理

綜合上述分析及約束添加策略，根據新約束變量與原網絡變量的從屬關系以及新約束的類型，判斷新約束在原網絡中的傳播范圍，僅執行必要的局部約束傳播，減少無效的一致性計算，有效降低約束推理次數，進而提出動態弧一致時間約束推理方法（DAC），逐步動態維護當前部分規劃的時間約束網絡一致性，并快速求解每個活動執行起止時間的最小可行區間，時間約束推理流程見圖7，其中具體步驟如下：

圖7 動態弧一致算法流程圖Fig.7 Flow chart of dynamic arc-consistent algorithm

1) 構建當前部分規劃所包含活動的時間約束網絡G0以及下一步規劃待添加活動的局部網絡Gp。

2) 按照零點約束優先策略生成待添加活動的約束集合，并順序取出添加至約束網絡G0。

3) 判斷約束類型及變量與G0的從屬關系，若u，v?V0或u∈V0，v?V0且Tuv=Cz，無需執行約束推理，執行步驟4；若u∈V0，v?V0且Tuv=CI或CE，則計算變量v的值域，執行步驟4；若u，v∈V0，則執行步驟5。

4) 判斷待處理約束集合是否為空，若為空則輸出每個活動執行起止時間的最小可行區間，否則執行步驟2。

5) 首先求解新添加約束對其兩個變量的值域影響（假設影響變量v），若=?，說明變量v不存在取值滿足當前規劃的時間約束，也即時間約束不一致，則執步驟7；若=Iv，說明當前添加的約束不會影響變量v的時間區間，無需進一步推理，執行步驟4；若?Iv且≠?，則該約束在網絡中傳播，將變量v加入變量值域更新列表Q，并執行步驟6。

6) 通過列表Q對約束傳播進行判斷，計算新約束影響范圍內的變量值域，判斷變量計算后值域削減與否來限制約束傳播，縮小約束傳播范圍，減少時間約束推理次數，節省著陸器有限的計算資源，提高復雜時間約束推理效率。將Q賦值給列表Qk，遍歷所有變量i∈Qk，計算值域Ii對所有鄰居變量值域Ij，j∈Nei的影響，若Ij=?，則時間約束不一致，執行步驟7；若I′j?Ij且Ij≠?，約束繼續傳播，將變量j加入Q。當集合Nei遍歷完成后，將變量i移出集合Q并判斷Q是否為空，若Q=?，約束傳播結束，所有變量的值域都已計算至最小，執行步驟4；若Q≠?，Q中變量值域繼續傳播，重新執行步驟6。

7) 重新進行規劃搜索選取合適的活動，執行步驟1。

該方法以網絡弧一致為基礎，通過對規劃過程中待添加活動的時間約束類型劃分以及零點約束優先添加策略，在推理過程中無需增加額外的網絡邊，同時盡可能限制約束的傳播范圍，減少規劃中時間約束推理耗時，有效提高柔性約束下柔性著陸器著陸任務規劃的實時性。

3 仿真實驗

3.1 場景設計

為了說明所提DAC 方法的效果，設計柔性著陸器著陸任務進行仿真。著陸器包含3 個節點，每個節點包含若干分系統。以規劃中的成像系統為例，每個節點均攜帶光學相機，在著陸器著陸過程中獲取小天體表面信息，提取規劃問題中3 個相機的成像準備和成像工作兩個活動，其初始時間約束關系如圖8 所示，圖中xs，xe分別表示活動x的開始時間點與結束時間點變量，其余類推。

圖8 三個相機的活動時間約束Fig.8 Temporal constraints of three cameras’ activities

隨著規劃搜索的進行，在成像系統的部分規劃中動態添加上述兩個活動，并進行時間約束網絡的一致性判斷，求解每個活動執行起止時間的最小可行區間，部分規劃活動的甘特圖如圖9所示，滿足相機A、B 同時開始工作的約束，活動的最小可行區間如圖10所示，結果證明了DAC方法的有效性。

為進一步證明DAC 算法對于柔性著陸器在不同任務場景下的適應性，以公開的時間網絡數據集為基礎［20］，設計著陸器著陸任務規劃中活動間時間約束關系數值，分3種不同情況進行仿真對比，多方面驗證DAC 算法效率，從而體現DAC 算法的動態性能。

情況一：驗證規劃過程中新添加的活動數對時間約束推理效率的影響。活動數體現了著陸任務的復雜度，著陸器在相同目標狀態下改變著陸過程中各系統所需執行的任務，并生成具有不同活動數和不同約束數的數據集，如表1所示。

情況二：驗證系統間時間約束耦合程度對時間約束推理效率的影響。假設著陸器節點總共具有16 個系統，每個系統具有10 個不同的可執行活動，對于同一著陸任務，改變系統間的約束數，如表2所示。

表2 系統間約束數Table 2 Number of inter-system constraints

情況三：驗證著陸器節點不同系統組成對時間約束推理效率的影響。每個系統同樣具有10個可執行活動，改變單個節點包含的系統數，系統間約束數M與系統數N滿足關系M=50(N-1)。如表3所示。

表3 單節點包含的系統數Table 3 Number of systems contained in a single node

3.2 對比分析

為了驗證時間約束推理方法的高效性，本節將所提的DAC 算法與NASA 建立的EUROPA 規劃器中采用的動態適應單源最短路徑時間約束推理算法（ABF）［20］進行比較。

如圖11所示，當規劃過程中新添加活動數不同時，DAC 算法相較EUROPA 算法，運行時間平均減少90.7%，且隨著活動數的增加，差距進一步增大，DAC 算法耗時增長更慢。圖12 顯示了108 個活動下每條約束添加至原網絡中時，執行約束推理所需的時間，虛線表示單條約束平均推理時間，實線表示單條約束推理時間的標準差，DAC 算法效率顯著提高，且算法穩定性更好。

圖11 不同活動數的算法運行時間Fig.11 Running time of the algorithms with different number of activities

圖12 單步約束推理時間（108個活動）Fig.12 Single-step constraint reasoning time（108 activities）

對于不同系統間約束數，DAC 算法平均效率提高78.8%，如圖13 所示。當系統數不同時，DAC算法效率依然占優，平均提高78.5%，且隨著系統數的增多，優勢更加明顯，如圖14所示。柔性著陸器相較于傳統單體著陸器具有系統多、約束耦合強、規劃活動多的特點，因此，DAC算法能夠更好地適應柔性著陸器著陸任務，提高任務規劃過程中的時間約束推理效率，進而增強著陸器著陸任務規劃的實時性。

圖13 不同約束數的算法運行時間Fig.13 Running time of the algorithms with different number of constraints

圖14 不同系統數的算法運行時間Fig.14 Running time of the algorithms with different number of systems

4 結論

本文針對小天體柔性著陸器的復雜時間約束推理問題，提出動態弧一致時間約束推理方法。提取規劃活動的時間約束信息，構建部分規劃與待添加活動的時間約束網絡；分析活動約束與時間網絡的從屬關系，避免無效推理；設計了零點約束優先添加策略，進一步減小時間約束的傳播范圍，從而實現規劃過程中動態活動添加的局部時間約束推理，提高了約束推理效率。本文提出的方法能夠快速判斷時間約束一致性并求解規劃活動可執行的最小可行區間，可為提高柔性著陸器著陸任務規劃的實時性、增強著陸器自主決策能力提供技術支持。