姜 嘯，徐 瑞，陳俐均

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

引 言

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

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

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

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

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

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

1 深空探測活動約束分析

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

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

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

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

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

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

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

-P與P′等價；

-D′中每個變量值域為D中對應(yīng)值域的子集；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在第1 種情況中，2 個約束中的驅(qū)動變量賦值相同，但是C1中驅(qū)動變量為可變量，C2中的驅(qū)動變量為不變量，顯然對應(yīng)的響應(yīng)變量賦值將不會相同。這代表外延約束C1與約束C2的后續(xù)狀態(tài)互斥，符合互斥判定3，因此兩個約束互斥。在第2 種情況中，兩個約束中的驅(qū)動變量具有可變量，因此需要進(jìn)一步考慮對應(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ū)動變量的賦值有可能與之前的響應(yīng)變量賦值產(chǎn)生沖突。對于沖突判定2只需考察驅(qū)動變量即可。針對動態(tài)約束集構(gòu)建要點3，若約束中的驅(qū)動變量取值范圍與已有賦值對沖突，則該約束不能加入動態(tài)約束集合；反之，該約束可以加入動態(tài)約束集合。

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

3.1 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

3.2 算法分析

以表2為例，算法的通用數(shù)據(jù)結(jié)構(gòu)如圖4所示。其中：position[i]代外延約束表中第i個可行的解集。Current index標(biāo)志當(dāng)前表中最后一個可行的解集。在圖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ī)劃活動中賦值對＜rock,rock1 ＞被剪枝，則表中的賦值解{1,2,5,6}由于不再滿足弧一致被移除。將無效解移至表的底端后當(dāng)前表的數(shù)據(jù)結(jié)構(gòu)如圖6所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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