姜 嘯，徐 瑞，陳俐均

（1.北京航天控制儀器研究所，北京 100854；2.北京理工大學(xué)深空探測(cè)技術(shù)研究所，北京 100081；3.深空自主導(dǎo)航與控制工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室，北京 100081）

引 言

深空探測(cè)器自主規(guī)劃調(diào)度是利用人工智能方法，在探測(cè)器上建立遠(yuǎn)程自主系統(tǒng)，探測(cè)器能夠合理地安排動(dòng)作序列、分配星上資源，從而完成任務(wù)目標(biāo)。它的目的是在不依賴或者少依賴外界信息注入或控制的情況下，能夠準(zhǔn)確地感知自身的狀態(tài)和外部環(huán)境，并根據(jù)這些信息做出恰當(dāng)?shù)貨Q策，自主地控制探測(cè)器完成各種任務(wù)。

深空探測(cè)器自主運(yùn)行和傳統(tǒng)的遙測(cè)遙控方式有很大區(qū)別[1]。傳統(tǒng)的遙測(cè)遙控方式由地面生成指令并上傳，管理探測(cè)器的運(yùn)行。探測(cè)器缺乏決策能力。自主運(yùn)行的探測(cè)器能夠進(jìn)行決策和自我管理，提高了探測(cè)器處理故障和突發(fā)事件的速度，降低了對(duì)地面站資源占用。隨著我國(guó)對(duì)外太空探索的不斷拓展，深空探測(cè)任務(wù)在逐年增加，提高自主運(yùn)行水平是探測(cè)器發(fā)展的主要趨勢(shì)。

目前，對(duì)于深空探測(cè)器的任務(wù)規(guī)劃和調(diào)度的研究，通常將探測(cè)任務(wù)的調(diào)度過程和探測(cè)器活動(dòng)的規(guī)劃過程分別處理：①傾向于探測(cè)器任務(wù)調(diào)度問題研究，僅將探測(cè)器作為資源集合進(jìn)行建模，然而并沒有考慮到探測(cè)器上各活動(dòng)之間的約束關(guān)系，例如為DATACHASER（STS-85 的搭載飛行試驗(yàn)）有效載荷開發(fā)的DCAPS（DATA-CHASER 自主規(guī)劃與調(diào)度）系統(tǒng)[2]、法國(guó)沃瑞蒂安（Veridian）公司設(shè)計(jì)開發(fā)的GREAS（Generic Resource，Event and Activity Scheduler）系統(tǒng)[3]等；②傾向于探測(cè)器任務(wù)規(guī)劃，通常沒有考慮規(guī)劃任務(wù)與探測(cè)器活動(dòng)之間的約束關(guān)系，例如美國(guó)噴氣推進(jìn)實(shí)驗(yàn)室（Jet Propulsion Laboratory，JPL）開發(fā)的自主規(guī)劃與調(diào)度（Autonomous Planning and Scheduling ENvironment，APSEN）系統(tǒng)[5-6]、連續(xù)活動(dòng)規(guī)劃調(diào)度執(zhí)行和重規(guī)劃（Continuous Activity Scheduling Planning Execution and Replanning，CASPER）系統(tǒng)[7]、美國(guó)國(guó)家航空航天局（National Aeronautics and Space Administration，NASA）開發(fā)的科學(xué)規(guī)劃互動(dòng)的知識(shí)環(huán)境軟件（Scientific Planning Interactive Knowledge Environment，SPIKE）系統(tǒng)[8]等。這2 種方式均不利于兼顧探測(cè)器規(guī)劃與調(diào)度的過程。

從探測(cè)器的實(shí)際任務(wù)生成和運(yùn)行過程來看，存在大量復(fù)雜的約束，如探測(cè)任務(wù)對(duì)探測(cè)器載荷活動(dòng)的需求約束、探測(cè)器活動(dòng)之間的時(shí)間約束[9]、資源約束[10]等，需要對(duì)探測(cè)任務(wù)的調(diào)度過程及探測(cè)器上活動(dòng)的規(guī)劃過程進(jìn)行融合[11-12]。但考慮到規(guī)劃和調(diào)度過程的融合，需要對(duì)存在的大量復(fù)雜約束條件進(jìn)行檢查，不可避免地嚴(yán)重降低算法的效率。

深空探測(cè)器任務(wù)規(guī)劃和調(diào)度方案的制定，需要考慮探測(cè)任務(wù)及探測(cè)器活動(dòng)中存在的多類型復(fù)雜約束。但目前對(duì)探測(cè)器任務(wù)規(guī)劃和調(diào)度的研究多采用約束較少、探測(cè)器活動(dòng)規(guī)劃過程與探測(cè)任務(wù)調(diào)度過程分離的方式。對(duì)于具有復(fù)雜約束的深空探測(cè)器任務(wù)，將規(guī)劃和調(diào)度過程同時(shí)考慮，其約束處理和規(guī)劃調(diào)度算法都具有復(fù)雜性，還需要進(jìn)行深入的研究。

為解決這些問題，本文從約束處理的角度入手，將智能規(guī)劃理論與約束可滿足技術(shù)相結(jié)合，采用約束可滿足技術(shù)提高深空探測(cè)器的約束處理能力，在可編碼為約束可滿足問題（Constraint Satisfaction Problem，CSP）的規(guī)劃研究基礎(chǔ)上[13]，研究多層約束規(guī)劃模型中約束的動(dòng)態(tài)特征，提出了基于動(dòng)態(tài)約束表的外延約束快速過濾算法，根據(jù)領(lǐng)域信息中活動(dòng)間的沖突性判定對(duì)新加入的活動(dòng)進(jìn)行分類，并對(duì)于約束表中變量進(jìn)行一致性檢查。結(jié)果表明該算法能夠有效地降低約束處理中無效約束檢查次數(shù)，降低問題處理過程中的算法回溯，提高規(guī)劃的效率和成功率。

1 深空探測(cè)活動(dòng)約束分析

在規(guī)劃過程中，每當(dāng)有新活動(dòng)加入時(shí)，使用約束網(wǎng)絡(luò)的一致性[13]檢查新加入的活動(dòng)是否滿足已有部分規(guī)劃的一致性。然而，在探測(cè)器任務(wù)規(guī)劃過程中也可以使用探測(cè)器本身固有的先驗(yàn)知識(shí)進(jìn)行檢查，通過分析探測(cè)器的規(guī)劃領(lǐng)域信息，設(shè)計(jì)更加高效的領(lǐng)域相關(guān)約束削減算法。深空探測(cè)器規(guī)劃活動(dòng)約束的特性包括以下2個(gè)方面。

1）規(guī)劃過程中活動(dòng)逐步添加

規(guī)劃的過程即逐步選擇活動(dòng)并檢查約束的過程。由活動(dòng)的定義可知，星上活動(dòng)一般由特定的子系統(tǒng)執(zhí)行（例如拍照活動(dòng)綁定于相機(jī)系統(tǒng)、加熱活動(dòng)綁定于溫控系統(tǒng)），在添加活動(dòng)的過程中，可以逐步計(jì)算新添加活動(dòng)對(duì)約束網(wǎng)的影響。

2）部分活動(dòng)間具有沖突關(guān)系且沖突關(guān)系僅限于本層活動(dòng)之間

規(guī)劃中動(dòng)作可編碼為CSP中的外延約束[14]，而動(dòng)作的一致性由外延約束的變量決定，當(dāng)滿足約束一致性的相同變量取值發(fā)生沖突時(shí)，對(duì)應(yīng)的約束（即活動(dòng)）之間也產(chǎn)生了沖突關(guān)系。同時(shí)，編碼為CSP的規(guī)劃問題為多層變量模型，不同的變量層為具有相同變量集合的副本。同層之間由于對(duì)相同變量的賦值爭(zhēng)奪能夠產(chǎn)生約束沖突，而不同變量層間由于不存在變量賦值爭(zhēng)奪，不會(huì)產(chǎn)生約束沖突。因此對(duì)于活動(dòng)約束間沖突關(guān)系的查考，應(yīng)該根據(jù)多層變量的模型逐層進(jìn)行。

通過對(duì)探測(cè)器約束網(wǎng)絡(luò)一致性檢查進(jìn)行約束過濾與削減的目的在于刪除變量值域或約束賦值中冗余的取值，從而減小其搜索空間。約束過濾削減的前提必須保證探測(cè)任務(wù)轉(zhuǎn)化的CSP 在被削減后仍為等價(jià)的CSP，即兩者具有相同的變量集與相同的解集。

定義1：一個(gè)約束可滿足問題P=(Z,D,C)被削減至P′ =(Z′,D′,C′)當(dāng)且僅當(dāng)

-P與P′等價(jià)；

-D′中每個(gè)變量值域?yàn)镈中對(duì)應(yīng)值域的子集；

-C′中約束的限制范圍大于或者等于C，例如滿足C′的所有賦值對(duì)均滿足C。

其中：Z代表CSP 的變量集；D代表值域集；C代外延約束集；solution_tuple代表該CSP的約束解；符號(hào)定義P至P′的削減關(guān)系為reduce(P,P′)。

CSP的削減包括變量的值域削減和約束的可行賦值對(duì)削減兩部分。在值域中一個(gè)取值是冗余的，當(dāng)且僅當(dāng)該取值不屬于任意解集，可以通過形式化描述為

其中：projection代表解集T包含賦值對(duì)＜x,v＞。這類取值被稱為“冗余的”，因?yàn)閯h除該取值不會(huì)影響對(duì)應(yīng)CSP的任何解。

同理，約束CS中的一個(gè)賦值對(duì)是冗余的，當(dāng)且僅當(dāng)任何解集都不包含該賦值對(duì)

2 動(dòng)態(tài)約束集構(gòu)建

通過對(duì)深空探測(cè)任務(wù)模型分析可知，規(guī)劃中動(dòng)作之間存在明顯的互斥關(guān)系（即2 個(gè)動(dòng)作不能同時(shí)發(fā)生）。2個(gè)動(dòng)作發(fā)生互斥/沖突分為以下3種情況。

動(dòng)作沖突判定1：動(dòng)作a與動(dòng)作b的前提條件互斥。例如，“探測(cè)器降軌”動(dòng)作的前提條件探測(cè)器位于高軌位置，而“著陸器分離電纜切割”動(dòng)作需要探測(cè)器在低軌執(zhí)行該操作，這個(gè)動(dòng)作由于前提條件的矛盾而產(chǎn)生互斥，不能同時(shí)操作。

動(dòng)作沖突判定2：動(dòng)作a的后續(xù)狀態(tài)/前提條件與動(dòng)作b的前提條件/后續(xù)狀態(tài)互斥。例如，動(dòng)作“探測(cè)器升軌”導(dǎo)致探測(cè)器升至高軌位置，而動(dòng)作“對(duì)行星表面拍攝”需求探測(cè)器維持在低軌位置。當(dāng)探測(cè)器執(zhí)行升軌動(dòng)作后，升軌產(chǎn)生的后續(xù)狀態(tài)將刪除“對(duì)行星表面拍攝”動(dòng)作的前提條件而導(dǎo)致拍攝動(dòng)作不能執(zhí)行，因此這2個(gè)動(dòng)作不能同時(shí)執(zhí)行。

動(dòng)作沖突判定3：動(dòng)作a與動(dòng)作b的后續(xù)狀態(tài)互斥。例如，“探測(cè)器降軌”動(dòng)作導(dǎo)致探測(cè)器降至低軌位置，而“探測(cè)器升軌”動(dòng)作導(dǎo)致探測(cè)器升至高軌位置。兩個(gè)動(dòng)作的前提條件可以相同，但動(dòng)作執(zhí)行的結(jié)果顯然相互矛盾，表明由于后續(xù)狀態(tài)矛盾而產(chǎn)生互斥不能同時(shí)操作。

對(duì)深空探測(cè)任務(wù)編碼時(shí)將動(dòng)作編碼為約束的形式，于是動(dòng)作之間的互斥轉(zhuǎn)化為約束間的互斥。對(duì)于具有多層變量的CSP，每一層的約束主要由動(dòng)作約束組成且這些約束存在互斥關(guān)系不能同時(shí)得到滿足。因此在規(guī)劃執(zhí)行前需要對(duì)約束進(jìn)行削減，生成內(nèi)部不包含互斥關(guān)系的約束集合。

構(gòu)建動(dòng)態(tài)約束集主要考慮以下要點(diǎn)：①每個(gè)動(dòng)態(tài)約束集合的編號(hào)等于對(duì)應(yīng)的層號(hào)；②動(dòng)態(tài)約束集內(nèi)部的約束是非互斥的；③對(duì)動(dòng)態(tài)約束集合進(jìn)行操作時(shí)，新加入的約束不能改變已有變量的賦值關(guān)系；④由于規(guī)劃中非互斥的動(dòng)作可以同時(shí)執(zhí)行，同層不互斥的動(dòng)作約束可以同時(shí)滿足。

基于上述動(dòng)態(tài)約束的要點(diǎn)，設(shè)計(jì)構(gòu)建動(dòng)態(tài)約束集的算法如圖1所示。

圖1 動(dòng)態(tài)約束集構(gòu)建方法Fig.1 Construction method for dynamic constraint set

算法中l(wèi)ayer k表示模型中的k層約束。CSP 中變量在每層中均具有相同的數(shù)據(jù)結(jié)構(gòu)，在變量選擇過程中，動(dòng)作的前提條件總要先于后續(xù)狀態(tài)進(jìn)行選擇。因此，約束集的層數(shù)編號(hào)可以等于前提條件變量的層數(shù)，避免了約束集分層的混亂，這里稱動(dòng)作的前提條件變量為驅(qū)動(dòng)變量，后續(xù)狀態(tài)變量為響應(yīng)變量。

算法中，函數(shù)isconsisitent（）是判定當(dāng)前動(dòng)作約束能否加入動(dòng)態(tài)約束集的核心。根據(jù)約束集構(gòu)建要點(diǎn)，考察該約束是否與其它約束產(chǎn)生沖突。動(dòng)作約束的驅(qū)動(dòng)變量代表該動(dòng)作的前提條件，若兩個(gè)動(dòng)作約束具有相同的驅(qū)動(dòng)變量，但相同的驅(qū)動(dòng)變量具有不同的賦值，可以認(rèn)為這個(gè)動(dòng)作的前提條件互斥。根據(jù)沖突判定1，前提條件互斥的兩個(gè)動(dòng)作互斥。

若兩個(gè)動(dòng)作約束的前提條件不發(fā)生沖突，則需要根據(jù)沖突判定2和3進(jìn)一步考察。根據(jù)之前對(duì)約束表特征的研究，表頭中變量可分為可變量與不變量，分別反映在相鄰層之間該變量的變化情況。本文根據(jù)驅(qū)動(dòng)變量的變化情況分類討論，可分為表1 中的4 種情況。

表1 CSP中動(dòng)作約束的互斥關(guān)系判定Table 1 Mutual exclusion determination of action constraints in CSP

在第1 種情況中，2 個(gè)約束中的驅(qū)動(dòng)變量賦值相同，但是C1中驅(qū)動(dòng)變量為可變量，C2中的驅(qū)動(dòng)變量為不變量，顯然對(duì)應(yīng)的響應(yīng)變量賦值將不會(huì)相同。這代表外延約束C1與約束C2的后續(xù)狀態(tài)互斥，符合互斥判定3，因此兩個(gè)約束互斥。在第2 種情況中，兩個(gè)約束中的驅(qū)動(dòng)變量具有可變量，因此需要進(jìn)一步考慮對(duì)應(yīng)的響應(yīng)變量是否相同才能判定約束C1和C2是否互斥。

圖2 多層結(jié)構(gòu)CSP相鄰層賦值示意Fig.2 Adjacent layer assignment of multilayer CSP structure

若多層結(jié)構(gòu)中CSP 的賦值如圖2 所示逐層進(jìn)行，那么當(dāng)前層只有驅(qū)動(dòng)變量的賦值有可能與之前的響應(yīng)變量賦值產(chǎn)生沖突。對(duì)于沖突判定2只需考察驅(qū)動(dòng)變量即可。針對(duì)動(dòng)態(tài)約束集構(gòu)建要點(diǎn)3，若約束中的驅(qū)動(dòng)變量取值范圍與已有賦值對(duì)沖突，則該約束不能加入動(dòng)態(tài)約束集合；反之，該約束可以加入動(dòng)態(tài)約束集合。

3 基于動(dòng)態(tài)約束集的快速過濾方法

3.1 算法設(shè)計(jì)

由于外延約束自身表達(dá)直觀以及對(duì)可行解的枚舉特性，外延約束自然地應(yīng)用于配置問題（Configuration Problem）中。工程中的各種資源相容性配置問題，可以很直觀通過列表的形式表達(dá)出來。例如，在k個(gè)衛(wèi)星中組合選擇構(gòu)成星座的問題，通過列表可以根據(jù)不同標(biāo)準(zhǔn)枚舉所有的可行方案。外延約束中的數(shù)據(jù)同樣可以很容易通過數(shù)據(jù)庫(kù)獲取，數(shù)據(jù)庫(kù)查詢的結(jié)果有時(shí)也表現(xiàn)為數(shù)量表的形式。在文獻(xiàn)[15]中介紹了數(shù)據(jù)庫(kù)處理與外延約束可滿足具有很緊密的理論聯(lián)系。

對(duì)探測(cè)器的規(guī)劃問題進(jìn)行約束削減，必須保證最終的約束規(guī)劃為弧一致的狀態(tài)。結(jié)合CSP中的點(diǎn)一致與弧一致，對(duì)外延約束中的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了定義，提出了基于動(dòng)態(tài)約束集的快速表過濾算法。

在深空探測(cè)任務(wù)中，動(dòng)作約束表的解集通常成組出現(xiàn)。例如，深空探測(cè)采樣任務(wù)動(dòng)作約束表如表2所示，若賦值對(duì)＜rock,rock1 ＞被剪枝后，表2 中的賦值解{1,2,5,6}由于不再滿足弧一致同樣需要移除約束的可行解集。

表2 探測(cè)器采樣任務(wù)動(dòng)作約束表Table 2 Action constraint table sampling task

針對(duì)深空任務(wù)中可行解成組出現(xiàn)的特性，本節(jié)設(shè)計(jì)基于動(dòng)態(tài)約束集的外延約束快速過濾算法，通過將約束表中成組的可行解集集中管理，便于對(duì)算法進(jìn)行搜索和回溯管理，偽代碼如圖3 所示。對(duì)于圖3算法中scp（c）代表外延約束中組成表頭的變量集合，定義table（c）為包含外延約束c中所有可行賦值解的集合。

圖3 外延約束快速過濾算法偽代碼Fig.3 Pseudo code for filtering algorithm of extensional constraint

對(duì)于n元變量集合以及對(duì)應(yīng)的n元賦值集合τ{a1,…,an}，每一個(gè)賦值ai可以定義為ai=τ[xi]。因此一個(gè)外延約束的元數(shù)等于scp（c）的大小。

算法在第1步、第8步以及第15步通過循環(huán)檢查移除未賦值變量中的冗余值域。其中第1 步中的past（P）代表當(dāng)前CSP 中已被實(shí)例化（賦值）的變量集合。由于在算法開始執(zhí)行時(shí)，還沒有賦值對(duì)被證明為弧一致，步1、步2 中將gacValue初始化為空值。在第4步至第13步的循環(huán)中對(duì)當(dāng)前約束C中所有的解集進(jìn)行處理：若解τ被證明為可行的（第7 步isValidtuple（ ）），則第 9 步、第 10 步記錄τ中所有的賦值；若τ不可行，則將τ移至表的底層并修改current index與search level的數(shù)據(jù)。當(dāng)該循環(huán)結(jié)束后，約束中所有的解集都進(jìn)行了處理，x中所有的不被支持的賦值都被剪枝移除。 此時(shí)Unsupport=dom/gacValue。

第17 步對(duì)CSP 中削減后新的值域進(jìn)行了更新，并18 步檢查x的新值域是否為空。若x的值域?yàn)榭?，則算法返回不一致標(biāo)志；若x的值域不為空，返回新的值域并可用于進(jìn)一步的約束處理。

算法中第1步、第4步以及第15步中循環(huán)的時(shí)間復(fù)雜度分別為O(r')，O(r')，O(rt')，O(r'd)，其中r'=|scp/past|代表了scp中未實(shí)例化的變量數(shù)目。t'代表c的元數(shù)。因此對(duì)于任意約束c，在最惡劣情況下算法的時(shí)間復(fù)雜度為O（r'd+rt'）。

3.2 算法分析

以表2為例，算法的通用數(shù)據(jù)結(jié)構(gòu)如圖4所示。其中：position[i]代外延約束表中第i個(gè)可行的解集。Current index標(biāo)志當(dāng)前表中最后一個(gè)可行的解集。在圖5 中， 當(dāng)前最后的可行解為position[8]={rock2robot loc2 0right1}。

圖4 外延約束快速過濾算法數(shù)據(jù)結(jié)構(gòu)Fig.4 The data structure of the extensional constrained filtering algorithm

圖5 外延約束快速過濾算法數(shù)據(jù)結(jié)構(gòu)Fig.5 The data structure of the extensional constrained filtering algorithm

假設(shè)在規(guī)劃活動(dòng)中賦值對(duì)＜rock,rock1 ＞被剪枝，則表中的賦值解{1,2,5,6}由于不再滿足弧一致被移除。將無效解移至表的底端后當(dāng)前表的數(shù)據(jù)結(jié)構(gòu)如圖6所示。

search level[i]=j記錄在第i層的削減操作中，約束表中第j個(gè)賦值解為第一個(gè)無效解。在上面的例子中，在第0層沒有進(jìn)行削減操作，因此search level[0]記為-1；在第1 次削減操作中第1 個(gè)無效解記錄在約束表的第8 層，因此search level[1]= 8。若再次進(jìn)行約束削減，例如移除無效賦值對(duì)＜gripper,left＞，則表的數(shù)據(jù)結(jié)構(gòu)如圖7所示。

在算法控制過程中對(duì)約束表中有效解/無效解進(jìn)行區(qū)分保存不僅有利于數(shù)據(jù)的儲(chǔ)存與搜索，在算法回溯時(shí)也同樣提供了便利。上面的例子中，當(dāng)動(dòng)作約束表需要分別對(duì)賦值對(duì)＜gripper,left＞，＜rock,rock1 ＞進(jìn)行回溯時(shí)，僅需修改current index與search level的指針標(biāo)志，即可得到圖7中的結(jié)果。注意到進(jìn)行算法回溯后position表中存儲(chǔ)的數(shù)據(jù)順序與原表中有所不同。由于表中數(shù)據(jù)在初始存儲(chǔ)時(shí)并未采用特定順序排序，對(duì)表中數(shù)據(jù)的搜索又采用枚舉遍歷的方式，數(shù)據(jù)存儲(chǔ)順序的改變并不會(huì)對(duì)算法的搜索產(chǎn)生影響。

圖6 外延約束過濾算法數(shù)據(jù)結(jié)構(gòu)Fig.6 The data structure of the extensional constrained filtering algorithm

圖7 外延約束過濾算法數(shù)據(jù)結(jié)構(gòu)Fig.7 The data structure of the extensional constrained filtering algorithm

4 仿真實(shí)驗(yàn)

為了驗(yàn)證本文提出的過濾算法對(duì)整體規(guī)劃效率的影響，仿真實(shí)驗(yàn)環(huán)節(jié)采用CSP 中常用的一般弧一致（General Arc Consistency，GAC）算法[16]與基于動(dòng)態(tài)約束集的外延約束快速過濾算法（后文簡(jiǎn)稱動(dòng)態(tài)約束集算法）進(jìn)行對(duì)比。在算法仿真實(shí)驗(yàn)中選取4種不同的規(guī)劃任務(wù)Rover、Satellite、Driverlog、Zene，并通過計(jì)算機(jī)隨機(jī)生成初始數(shù)據(jù)考察規(guī)劃中處理的約束數(shù)量，在統(tǒng)一的前向搜索方法下搜索時(shí)間，分別對(duì)兩種約束過濾方法進(jìn)行比較分析。實(shí)驗(yàn)的環(huán)境配置為Intel Core i5-2450 CPU（2.5 GHz），4GRAM，Win7 操作系統(tǒng)，編程語言為C/C++語言。

圖8 記錄了不同任務(wù)，不同變量數(shù)下基于動(dòng)態(tài)約束集的快速表過濾算法與GAC 算法在探測(cè)器規(guī)劃任務(wù)中處理的約束數(shù)量。由于在約束可滿足的處理過程中對(duì)于問題的削減同樣會(huì)占用算法的運(yùn)行時(shí)間，當(dāng)削減算法設(shè)計(jì)不當(dāng)時(shí)將嚴(yán)重影響搜索效率。對(duì)比算例中GAC 算法并沒有考慮規(guī)劃問題中活動(dòng)層面的沖突，由圖8 可以發(fā)現(xiàn)，GAC 算法考察了大量冗余的沖突約束，因此也對(duì)大量的冗余變量進(jìn)行了值域削減處理，占用了算法大量的時(shí)間。而將約束層面的沖突降至變量層解決，部分變量在不同約束的限制下被過度削減到值域?yàn)榭?，?dǎo)致算法產(chǎn)生回溯。而本文提出的快速過濾外延約束算法在對(duì)約束的預(yù)處理過程中根據(jù)規(guī)劃的領(lǐng)域信息將約束分類，減少了需要處理的約束數(shù)量，由圖8 中可以發(fā)現(xiàn)，在對(duì)于不同變量數(shù)的問題規(guī)模時(shí)，處理的約束數(shù)均少于GAC 算法。

圖8 處理約束數(shù)對(duì)比Fig.8 Comparison of processing constraints

表3～6記錄了上述4個(gè)算例在約束求解中分別產(chǎn)生的規(guī)劃時(shí)間對(duì)比。從計(jì)算結(jié)果可以發(fā)現(xiàn)，在相同搜索算法框架下，由于快速外延約束過濾方法產(chǎn)生更好的過濾效果，從而降低了搜索時(shí)變量的處理規(guī)模，減少了搜索用時(shí)。同時(shí)，由于快速外延約束過濾方法需要提取規(guī)劃問題中的領(lǐng)域信息引導(dǎo)削減過程，隨著問題規(guī)模的增加快速外延約束過濾方法能夠更加便利地利用領(lǐng)域信息，提高規(guī)劃效率。

為了直觀比較過濾算法對(duì)成功率的影響，對(duì)固定數(shù)量變量，在初值變化的情況下通過50 次實(shí)驗(yàn)統(tǒng)計(jì)進(jìn)行對(duì)比。深空探測(cè)器在任務(wù)規(guī)劃與調(diào)度過程中，由于約束網(wǎng)絡(luò)通常會(huì)出現(xiàn)較多的變量，因此選擇了變量的數(shù)量為100進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)結(jié)果如表7所示。

根據(jù)統(tǒng)計(jì)數(shù)據(jù)可知，在前向搜索算法框架以及變量數(shù)量為100的前提條件下，基于動(dòng)態(tài)約束集的外延約束快速過濾算法的規(guī)劃成功率較GAC 算法有了進(jìn)一步的提升。因此在具有大量變量的約束規(guī)劃模型中，快速表過濾算法更能夠穩(wěn)定地獲得規(guī)劃解，更適用于復(fù)雜的深空探測(cè)器系統(tǒng)。

表3 算例1規(guī)劃時(shí)間對(duì)比Table 3 Planning time comparison of example 1 s

表4 算例2規(guī)劃時(shí)間對(duì)比Table 4 Planning time comparison of example 2 s

表5 算例3規(guī)劃時(shí)間對(duì)比Table 5 Planning time comparison of example 3 s

表6 算例4規(guī)劃時(shí)間對(duì)比Table 6 Planning time comparison of example 4 s

表7 深空探測(cè)器任務(wù)規(guī)劃與調(diào)度成功率對(duì)比Table 7 Comparison of mission planning and scheduling success rate

結(jié)合對(duì)比結(jié)果，表8進(jìn)一步對(duì)比不同方法生成的解的質(zhì)量，評(píng)價(jià)標(biāo)準(zhǔn)包括完成任務(wù)所需時(shí)間以及規(guī)劃中的空閑時(shí)間。通過對(duì)比分析可以直觀地反應(yīng)不同規(guī)劃解安排規(guī)劃活動(dòng)的緊密程度。在不同算例的對(duì)比中，本文提出的動(dòng)態(tài)約束集算法具有較好的任務(wù)完成時(shí)間與最小的空閑時(shí)間，表明在規(guī)劃解中規(guī)劃活動(dòng)安排較為緊密，在相同規(guī)劃周期中能夠完成更多的規(guī)劃任務(wù)。

表8 解質(zhì)量對(duì)比Table 8 Quality comparison of different methods s

5 結(jié) 論

本文在分析深空探測(cè)器約束規(guī)劃模型特點(diǎn)的基礎(chǔ)上，提出了一種分層變量的動(dòng)態(tài)約束集構(gòu)建方法，并設(shè)計(jì)了外延約束過濾算法。該算法對(duì)活動(dòng)外延約束進(jìn)行分析，根據(jù)領(lǐng)域信息中活動(dòng)間的沖突性判定對(duì)新加入的活動(dòng)進(jìn)行分類，從而形成一致性的約束集合。

對(duì)于約束表中變量一致性檢查，設(shè)計(jì)了快速表過濾算法，通過對(duì)變量的聚類管理，能夠有效地提高一致性檢查以及問題回溯的效率。最后的算法仿真實(shí)驗(yàn)表明相較于GAC 算法，基于動(dòng)態(tài)約束集的快速過濾算法能夠有效地降低約束處理中無效的約束檢查數(shù)目，降低問題處理過程中的回溯次數(shù)。