小天體柔性著陸任務(wù)規(guī)劃的動態(tài)時間約束推理方法

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

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

0 引言

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

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

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

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

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

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

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

本文針對小天體柔性著陸器著陸任務(wù)規(guī)劃中的復(fù)雜時間約束推理問題，建立任務(wù)規(guī)劃中的活動時間約束網(wǎng)絡(luò)，進(jìn)而劃分約束類型，分析不同類型約束在時間網(wǎng)絡(luò)中的傳播特點(diǎn)，設(shè)計零點(diǎn)約束優(yōu)先添加策略，減小規(guī)劃過程中的時間約束傳播范圍。提出動態(tài)弧一致時間約束推理方法，局部求解時間約束網(wǎng)絡(luò)一致性，獲得著陸器系統(tǒng)可執(zhí)行活動的最小可行區(qū)間。最后構(gòu)建小天體著陸規(guī)劃場景，從多方面驗證了所提方法的有效性和高效性。

1 問題描述及模型建立

1.1 任務(wù)規(guī)劃問題描述

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

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

式中：A為著陸器節(jié)點(diǎn)集合，Sa為節(jié)點(diǎn)包含的系統(tǒng)集合，Ox為系統(tǒng)可執(zhí)行活動集合，Cx為活動的時間約束集合，Ix為系統(tǒng)初始狀態(tài)，Gx為系統(tǒng)目標(biāo)狀態(tài)。

定義2.系統(tǒng)可執(zhí)行活動oi∈Ox的時間信息可表示為如下元組：

式中：si為活動oi的開始時間點(diǎn)，ei為結(jié)束時間點(diǎn)，di為活動的持續(xù)時間，Ci為該活動與其他活動間的時間約束關(guān)系集合。

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

其中，a，b均為實(shí)數(shù)。

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

1.2 時間約束網(wǎng)絡(luò)構(gòu)建

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

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

圖3 時間約束網(wǎng)絡(luò)示例Fig.3 Temporal constraint network example

根據(jù)變量間的時間約束關(guān)系進(jìn)一步劃分約束類型，如圖4所示。As，Ae和Bs，Be分別表示活動A和活動B 的開始及結(jié)束時間點(diǎn)。其中，變量點(diǎn)與時間零點(diǎn)z間的約束稱為零點(diǎn)約束（Cz），如IzAs=[8，11]表示活動A 的開始執(zhí)行區(qū)間；同一活動的時間點(diǎn)變量間約束稱為內(nèi)部約束（CI），如IBsBe=[1.5，2]表示活動B 的可持續(xù)時間；不同活動的時間點(diǎn)變量間約束稱為外部約束（CE），如IAsBs=)[1，∞表示活動B 至少在活動A 開始執(zhí)行1 個單位時間之后再開始執(zhí)行。從而時間約束網(wǎng)絡(luò)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。時間約束一致性推理的本質(zhì)在于通過式（5）和（6）收緊原始約束，判斷是否當(dāng)前規(guī)劃的所有活動約束都得到滿足，并且求解當(dāng)前網(wǎng)絡(luò)中每個活動開始與結(jié)束的最小可行時間區(qū)間。

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

根據(jù)柔性著陸器每個系統(tǒng)的初始狀態(tài)與目標(biāo)狀態(tài)初始化時間網(wǎng)絡(luò)，隨著規(guī)劃活動的添加，逐步擴(kuò)展網(wǎng)絡(luò)規(guī)模并求解時間約束問題。

2 動態(tài)弧一致時間約束推理

柔性著陸器的規(guī)劃過程中活動和時間約束都是動態(tài)變化的，約束信息的傳播會影響當(dāng)前已有規(guī)劃活動的執(zhí)行區(qū)間，若每次改變都對全局時間網(wǎng)絡(luò)進(jìn)行一次推理，則計算效率嚴(yán)重降低，本文提出一種動態(tài)弧一致時間約束推理方法，設(shè)計零點(diǎn)約束優(yōu)先添加策略，根據(jù)添加的約束類型不同限制約束傳播范圍，僅對局部約束網(wǎng)絡(luò)進(jìn)行推理，減少規(guī)劃中活動動態(tài)變化的影響范圍，提高時間問題的求解效率。

2.1 時間網(wǎng)絡(luò)弧一致

弧一致算法僅需求解每個變量值域的最小區(qū)間。也即，僅對變量與時間零點(diǎn)間的約束區(qū)間進(jìn)行求交計算。

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

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

2.2 約束添加策略

規(guī)劃過程中的活動是逐步添加的，如圖5所示，對于當(dāng)前規(guī)劃的待添加活動oi∈Ox，需要執(zhí)行約束推理的時間網(wǎng)絡(luò)包含兩部分：當(dāng)前部分規(guī)劃中活動的時間變量和約束構(gòu)建的原網(wǎng)絡(luò)G0=以及待添加活動的時間變量和與G0中變量相關(guān)的局部約束網(wǎng)絡(luò)Gp=。

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

為實(shí)現(xiàn)時間約束網(wǎng)絡(luò)的局部動態(tài)維護(hù)，將活動oi相關(guān)的3 類約束逐條添加至原網(wǎng)絡(luò)，從而對于每條新添加的約束而言，其對應(yīng)的原網(wǎng)絡(luò)=<>為G0與已添加至G0中的前序約束的并集。定義新添加約束的兩個變量為u，v，邊為euv，則該約束與G′0存在以下3類從屬關(guān)系。

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

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

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

當(dāng)Tuv=CI或Tuv=CE時，需要分別計算變量u，v對互相值域的影響，進(jìn)而根據(jù)區(qū)間減小與否執(zhí)行約束傳播，約束推理次數(shù)為式（9）。

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

1) 零點(diǎn)約束→內(nèi)部約束→外部約束

2) 零點(diǎn)約束→外部約束→內(nèi)部約束

3) 內(nèi)部約束→零點(diǎn)約束→外部約束

4) 內(nèi)部約束→外部約束→零點(diǎn)約束

5) 外部約束→零點(diǎn)約束→內(nèi)部約束

6) 外部約束→內(nèi)部約束→零點(diǎn)約束

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

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

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

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

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

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

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

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

2.3 動態(tài)約束推理

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

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

1) 構(gòu)建當(dāng)前部分規(guī)劃所包含活動的時間約束網(wǎng)絡(luò)G0以及下一步規(guī)劃待添加活動的局部網(wǎng)絡(luò)Gp。

2) 按照零點(diǎn)約束優(yōu)先策略生成待添加活動的約束集合，并順序取出添加至約束網(wǎng)絡(luò)G0。

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

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

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

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

7) 重新進(jìn)行規(guī)劃搜索選取合適的活動，執(zhí)行步驟1。

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

3 仿真實(shí)驗

3.1 場景設(shè)計

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

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

隨著規(guī)劃搜索的進(jìn)行，在成像系統(tǒng)的部分規(guī)劃中動態(tài)添加上述兩個活動，并進(jìn)行時間約束網(wǎng)絡(luò)的一致性判斷，求解每個活動執(zhí)行起止時間的最小可行區(qū)間，部分規(guī)劃活動的甘特圖如圖9所示，滿足相機(jī)A、B 同時開始工作的約束，活動的最小可行區(qū)間如圖10所示，結(jié)果證明了DAC方法的有效性。

為進(jìn)一步證明DAC 算法對于柔性著陸器在不同任務(wù)場景下的適應(yīng)性，以公開的時間網(wǎng)絡(luò)數(shù)據(jù)集為基礎(chǔ)［20］，設(shè)計著陸器著陸任務(wù)規(guī)劃中活動間時間約束關(guān)系數(shù)值，分3種不同情況進(jìn)行仿真對比，多方面驗證DAC 算法效率，從而體現(xiàn)DAC 算法的動態(tài)性能。

情況一：驗證規(guī)劃過程中新添加的活動數(shù)對時間約束推理效率的影響。活動數(shù)體現(xiàn)了著陸任務(wù)的復(fù)雜度，著陸器在相同目標(biāo)狀態(tài)下改變著陸過程中各系統(tǒng)所需執(zhí)行的任務(wù)，并生成具有不同活動數(shù)和不同約束數(shù)的數(shù)據(jù)集，如表1所示。

情況二：驗證系統(tǒng)間時間約束耦合程度對時間約束推理效率的影響。假設(shè)著陸器節(jié)點(diǎn)總共具有16 個系統(tǒng)，每個系統(tǒng)具有10 個不同的可執(zhí)行活動，對于同一著陸任務(wù)，改變系統(tǒng)間的約束數(shù)，如表2所示。

表2 系統(tǒng)間約束數(shù)Table 2 Number of inter-system constraints

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

表3 單節(jié)點(diǎn)包含的系統(tǒng)數(shù)Table 3 Number of systems contained in a single node

3.2 對比分析

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

如圖11所示，當(dāng)規(guī)劃過程中新添加活動數(shù)不同時，DAC 算法相較EUROPA 算法，運(yùn)行時間平均減少90.7%，且隨著活動數(shù)的增加，差距進(jìn)一步增大，DAC 算法耗時增長更慢。圖12 顯示了108 個活動下每條約束添加至原網(wǎng)絡(luò)中時，執(zhí)行約束推理所需的時間，虛線表示單條約束平均推理時間，實(shí)線表示單條約束推理時間的標(biāo)準(zhǔn)差，DAC 算法效率顯著提高，且算法穩(wěn)定性更好。

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

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

對于不同系統(tǒng)間約束數(shù)，DAC 算法平均效率提高78.8%，如圖13 所示。當(dāng)系統(tǒng)數(shù)不同時，DAC算法效率依然占優(yōu)，平均提高78.5%，且隨著系統(tǒng)數(shù)的增多，優(yōu)勢更加明顯，如圖14所示。柔性著陸器相較于傳統(tǒng)單體著陸器具有系統(tǒng)多、約束耦合強(qiáng)、規(guī)劃活動多的特點(diǎn)，因此，DAC算法能夠更好地適應(yīng)柔性著陸器著陸任務(wù)，提高任務(wù)規(guī)劃過程中的時間約束推理效率，進(jìn)而增強(qiáng)著陸器著陸任務(wù)規(guī)劃的實(shí)時性。

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

圖14 不同系統(tǒng)數(shù)的算法運(yùn)行時間Fig.14 Running time of the algorithms with different number of systems

4 結(jié)論

本文針對小天體柔性著陸器的復(fù)雜時間約束推理問題，提出動態(tài)弧一致時間約束推理方法。提取規(guī)劃活動的時間約束信息，構(gòu)建部分規(guī)劃與待添加活動的時間約束網(wǎng)絡(luò)；分析活動約束與時間網(wǎng)絡(luò)的從屬關(guān)系，避免無效推理；設(shè)計了零點(diǎn)約束優(yōu)先添加策略，進(jìn)一步減小時間約束的傳播范圍，從而實(shí)現(xiàn)規(guī)劃過程中動態(tài)活動添加的局部時間約束推理，提高了約束推理效率。本文提出的方法能夠快速判斷時間約束一致性并求解規(guī)劃活動可執(zhí)行的最小可行區(qū)間，可為提高柔性著陸器著陸任務(wù)規(guī)劃的實(shí)時性、增強(qiáng)著陸器自主決策能力提供技術(shù)支持。