姜嘯，徐瑞，朱圣英

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

0 引 言

近年來(lái)，約束處理技術(shù)成為深空探測(cè)自主任務(wù)規(guī)劃研究的熱點(diǎn)。關(guān)于約束處理技術(shù)的應(yīng)用集中在對(duì)約束可滿(mǎn)足問(wèn)題（Constraint Satisfaction Problem，CSP）結(jié)構(gòu)的編碼和擴(kuò)展，以迎合規(guī)劃領(lǐng)域豐富的表現(xiàn)形式，包括：時(shí)間線(xiàn)[1]、概率性[2]、數(shù)據(jù)流[3]等。美國(guó)國(guó)家航空航天局（National Aeronautics and Space Administration，NASA）、美國(guó)國(guó)防部（Department of Defense，DOD）、歐洲航天局（European Space Agency，ESA）等很多機(jī)構(gòu)在規(guī)劃中引入了CSP技術(shù)以支持深空探測(cè)器的自主運(yùn)行，完成復(fù)雜的任務(wù)目標(biāo)，具體項(xiàng)目計(jì)劃包括美國(guó)的深空探測(cè)計(jì)劃、基于空間的觀測(cè)系統(tǒng)（如哈勃太空望遠(yuǎn)鏡）以及ESA的星載自主計(jì)劃（Project for On-Board Autonomy，PROBA）等。

NASA的深空航天器“深空1號(hào)”上使用了RA（Remote Agent）自主控制系統(tǒng)，RA是第1個(gè)在任務(wù)過(guò)程中對(duì)航天器進(jìn)行自主閉環(huán)控制的軟件[4]。它的規(guī)劃調(diào)度系統(tǒng)RAX-PS采用域描述語(yǔ)言DDL[5]描述結(jié)構(gòu)、功能、資源和各種約束條件等。規(guī)劃引擎采用各種約束傳播算法產(chǎn)生約束網(wǎng)絡(luò)，通過(guò)行徑?jīng)]有解決的沖突并使約束網(wǎng)絡(luò)一致解決沖突，直到完成任務(wù)目標(biāo)為止。規(guī)劃過(guò)程中采用啟發(fā)式函數(shù)加快求解過(guò)程。TechSat21星座中的衛(wèi)星及EO1航天器上使用了ASE（Autonomous Sciencecraft Experiment）[6]軟件，它的決策模塊連續(xù)活動(dòng)調(diào)度規(guī)劃執(zhí)行和重規(guī)劃系統(tǒng)（Continuous Activity Scheduling Planning Execution and Replanning System，CASPER）使用了局部約束處理技術(shù)進(jìn)行模型的求解，可進(jìn)行動(dòng)態(tài)連續(xù)規(guī)劃，但規(guī)劃中只能產(chǎn)生下一個(gè)飛行周期的操作計(jì)劃，不能通過(guò)全局約束及時(shí)地對(duì)實(shí)時(shí)反饋?zhàn)龀龇磻?yīng)。自主規(guī)劃和調(diào)度環(huán)境（Autonomous Planning and Scheduling Environment，ASPEN）[7-8]結(jié)合宇航器操作約束、飛行規(guī)范約束、宇航器硬件模型、科學(xué)實(shí)驗(yàn)?zāi)繕?biāo)和操作過(guò)程來(lái)自動(dòng)生成較低層次的宇航器操作序列，NASA已經(jīng)將其廣泛應(yīng)用在進(jìn)行外太空任務(wù)的宇航器上，包括Citizen Explorer、MARS-1和DS-T等一系列宇航器。NASA實(shí)現(xiàn)的可擴(kuò)展標(biāo)準(zhǔn)化遠(yuǎn)程操作規(guī)劃框架（Extensible Unification Remote Operation Planning Framework，EUROPA)[9-10]，以基于約束區(qū)間的框架描述調(diào)度問(wèn)題，以基于隨機(jī)搜索的貪婪算法求解，并考慮了觀測(cè)任務(wù)的優(yōu)先級(jí)。

國(guó)內(nèi)針對(duì)基于約束可滿(mǎn)足的規(guī)劃問(wèn)題研究和國(guó)際上仍存在有很大差距，國(guó)內(nèi)主要集中在部分功能約束的規(guī)劃研究。仲維國(guó)研究了星載設(shè)備經(jīng)受動(dòng)態(tài)環(huán)境的多種幾何和動(dòng)力學(xué)約束時(shí)，航天器姿態(tài)機(jī)動(dòng)歷程的星上規(guī)劃方法，將姿態(tài)路徑的規(guī)劃問(wèn)題轉(zhuǎn)化為中間節(jié)點(diǎn)的規(guī)劃[11]。程小軍、崔祜濤等分析了航天器姿態(tài)機(jī)動(dòng)所受的幾何約束，設(shè)計(jì)了保守型的幾何約束表達(dá)形式[12]。陳德相、徐瑞等針對(duì)航天器自主任務(wù)規(guī)劃中的資源受限、約束復(fù)雜、活動(dòng)并行等問(wèn)題，提出了基于時(shí)間拓?fù)渑判虻暮教炱髻Y源處理方法，該方法對(duì)資源約束網(wǎng)絡(luò)的資源突變時(shí)刻進(jìn)行處理，優(yōu)化了流量推進(jìn)路徑的選擇過(guò)程[13]。伍麗華、姜云飛等提出一種對(duì)時(shí)態(tài)信息進(jìn)行表示與管理并且能夠進(jìn)行時(shí)態(tài)約束推理的一致性賦值方法，使時(shí)態(tài)推理技術(shù)能夠更好地應(yīng)用于時(shí)態(tài)規(guī)劃的求解過(guò)程中[14]。徐文明、杜智遠(yuǎn)等提出了可重復(fù)的資源約束在規(guī)劃執(zhí)行時(shí)的可分配處理方法，以及判斷資源變量是否滿(mǎn)足的可分配性條件[15]。趙凡宇、徐瑞等針對(duì)深空探測(cè)器的任務(wù)規(guī)劃過(guò)程特點(diǎn)，考慮約束的數(shù)值特性，提出一種基于規(guī)劃活動(dòng)相關(guān)度的領(lǐng)域無(wú)關(guān)啟發(fā)式規(guī)劃方法[16]。

現(xiàn)有的研究成果中僅有少量工作涉及到CSP的算法移植性研究，即如何對(duì)CSP中標(biāo)準(zhǔn)算法進(jìn)行重構(gòu)以適應(yīng)規(guī)劃時(shí)態(tài)搜索特點(diǎn)。CSP中標(biāo)準(zhǔn)的啟發(fā)式設(shè)計(jì)并不能很好的利用規(guī)劃信息引導(dǎo)搜索過(guò)程，這在一定程度上降低了搜索的效率。針對(duì)該問(wèn)題，Judge M.、Long D.等[17]給出了基于目標(biāo)指向的CSP啟發(fā)式策略。但當(dāng)問(wèn)題規(guī)模增大時(shí)解的長(zhǎng)度也隨之增加，這將很大程度上降低目標(biāo)指向約束的約束能力。

本文提出了一種以動(dòng)作約束為核心的CSP啟發(fā)式搜索策略。該方法將任務(wù)規(guī)劃中的關(guān)鍵元素映射到CSP中，并以規(guī)劃中的動(dòng)作關(guān)系為基礎(chǔ)，研究并揭示了多層變量CSP中相鄰變量的關(guān)系，據(jù)此提出了CSP中一般性動(dòng)作約束。該方法避免了當(dāng)問(wèn)題規(guī)模增大時(shí)約束能力衰減的問(wèn)題。仿真實(shí)驗(yàn)表明基于動(dòng)作約束的擴(kuò)展GAC與標(biāo)準(zhǔn)一般弧一致（General Arc Consistent，GAC）算法相比具有更好的性能。

2 問(wèn)題描述

任務(wù)規(guī)劃是關(guān)于動(dòng)作的推理，指的是通過(guò)領(lǐng)域中動(dòng)作的期望效果，選擇和組織一組動(dòng)作，其目的是盡可能好地實(shí)現(xiàn)一些預(yù)先給定的目標(biāo)。約束可滿(mǎn)足問(wèn)題由一個(gè)變量集合和一個(gè)約束集合組成。問(wèn)題的解是滿(mǎn)足所有約束的完全賦值，或更進(jìn)一步，使目標(biāo)函數(shù)最大化。本節(jié)首先對(duì)CSP和規(guī)劃進(jìn)行了定義說(shuō)明。

定義1（CSP）一個(gè)約束可滿(mǎn)足問(wèn)題由以下幾部分組成：

1）變量集X，其中：

2）值域集D，其中：對(duì)于X中的任意變量，在D中具有對(duì)應(yīng)的值域；

約束可滿(mǎn)足問(wèn)題的目標(biāo)是使每一個(gè)變量都得到一個(gè)賦值，且所有的約束都得到滿(mǎn)足。

定義2（任務(wù)規(guī)劃）一個(gè)任務(wù)規(guī)劃問(wèn)題可以表示為一個(gè)三元組Q為

其中：si表示規(guī)劃系統(tǒng)的初始狀態(tài)；sg表示規(guī)劃系統(tǒng)的目標(biāo)狀態(tài)；A為規(guī)劃系統(tǒng)中所有可執(zhí)行操作的集合。

一般而言，操作集合表示規(guī)劃中可執(zhí)行的各種動(dòng)作，任意動(dòng)作由二元組組成，其中：pre代表支持動(dòng)作執(zhí)行的前提條件，eff代表動(dòng)作執(zhí)行后產(chǎn)生的后續(xù)狀態(tài)。

在任務(wù)規(guī)劃與CSP的所有差異之中，關(guān)鍵在于任務(wù)規(guī)劃是一個(gè)動(dòng)態(tài)未知的問(wèn)題。具體而言，在規(guī)劃前決策者并不知道需要多少個(gè)動(dòng)作支持規(guī)劃的完成，規(guī)劃的長(zhǎng)度是未知量。而CSP是一個(gè)相對(duì)靜態(tài)的問(wèn)題，在約束處理過(guò)程中待求解的變量數(shù)目是可見(jiàn)的，換言之，CSP的長(zhǎng)度是可知的。為了能夠?qū)SP技術(shù)應(yīng)用于規(guī)劃問(wèn)題，Kautz與Selman提出了針對(duì)規(guī)劃問(wèn)題的定界分層方法，為基于約束可滿(mǎn)足的自主規(guī)劃技術(shù)奠定了理論基礎(chǔ)。該方法在規(guī)劃前對(duì)解的長(zhǎng)度進(jìn)行預(yù)估，例如假設(shè)該規(guī)劃問(wèn)題可用k個(gè)動(dòng)作完成，便定義CSP模型具有k層結(jié)構(gòu)，每層均是變量集和約束集的一個(gè)副本。若CSP在k層中無(wú)解，對(duì)k值迭代增加，直到獲得可行解。該方法將NP難的規(guī)劃問(wèn)題通過(guò)長(zhǎng)度限定降為一個(gè)NP問(wèn)題，從而可以通過(guò)CSP求解這種NPC問(wèn)題獲得可行解。

基于定界分層方法，對(duì)于編碼為CSP的規(guī)劃問(wèn)題本文從變量、約束和算法3個(gè)方面進(jìn)行如下設(shè)計(jì)。

1）變量

假定任意規(guī)劃問(wèn)題具有m多值狀態(tài)變量，對(duì)于規(guī)劃中任意層0 ≤≤n中每個(gè)狀態(tài)變量Vi，在對(duì)應(yīng)的CSP結(jié)構(gòu)中均包含對(duì)應(yīng)的變量V，其值域與Vi的值域一一對(duì)應(yīng)。因此，在該CSP中包含m（n+ 1）個(gè)變量。

2）約束

本文主要包含涉及規(guī)劃領(lǐng)域信息的4條約束：初始狀態(tài)約束、目標(biāo)狀態(tài)約束、動(dòng)作的前提條件約束以及動(dòng)作的效果約束。初始狀態(tài)約束限定了CSP中變量在初始層的取值范圍（k= 0），目標(biāo)狀態(tài)約束限定了CSP中目標(biāo)層變量的取值范圍。任務(wù)規(guī)劃中的動(dòng)作關(guān)系轉(zhuǎn)化為前提條件約束和效果約束。例如，動(dòng)作photo限定了探測(cè)器對(duì)某目標(biāo)進(jìn)行拍照。若該動(dòng)作在i層執(zhí)行，前提條件約束限定了photo的前提條件point-to必須于i層之前發(fā)生，保證在拍攝前探測(cè)器指向目標(biāo)。

3）算法

本文采用一般弧一致GAC算法[18]作為算法框架，并在此基礎(chǔ)上對(duì)其變量選擇的啟發(fā)式進(jìn)行改進(jìn)。GAC算法的核心是檢查每個(gè)未賦值變量的值域，并剪枝不符合約束的取值。如果剪枝操作導(dǎo)致該變量值域?yàn)榭?，則算法進(jìn)行回溯。GAC對(duì)CSP中的約束進(jìn)行弧一致的檢查也采用上述策略：GAC首先檢查當(dāng)前約束中未賦值的變量并對(duì)其值域進(jìn)行剪枝，當(dāng)該變量值域剪枝至空時(shí)將所有包含該變量的約束加入GAC算法待擴(kuò)展的約束列表中。

3 動(dòng)作約束分析

當(dāng)CSP問(wèn)題規(guī)模增大時(shí)，初始狀態(tài)約束以及目標(biāo)狀態(tài)約束對(duì)整個(gè)CSP的約束能力將逐步減小。因此，本文主要對(duì)貫穿整個(gè)CSP的動(dòng)作約束進(jìn)行考察。

在規(guī)劃領(lǐng)域，動(dòng)作的前提條件與后續(xù)狀態(tài)規(guī)則如下：

在CSP中動(dòng)作常常轉(zhuǎn)化為約束的形式，并不能顯式存在于問(wèn)題處理過(guò)程之中，所以將規(guī)劃領(lǐng)域中的關(guān)鍵元素映射到CSP領(lǐng)域使之能夠符合CSP算法的處理過(guò)程十分必要。例如，符號(hào)及在規(guī)劃領(lǐng)域代表某一動(dòng)作的真值，而對(duì)應(yīng)的CSP領(lǐng)域中代表該動(dòng)作約束是否具有一致性。為了避免混淆，下文中如非特指A均代表CSP中的動(dòng)作約束。從規(guī)劃至CSP的映射關(guān)系為

在規(guī)劃中，動(dòng)作的前提條件表現(xiàn)為處于某種特殊狀態(tài)的實(shí)體。例如假定動(dòng)作pickup的前提為：球在地上；手是空的。則該動(dòng)作的前提條件表示為顯然在CSP中{ball，hand}可表示為變量，{ground，empty}為對(duì)應(yīng)的值域。廣而言之，規(guī)劃中某狀態(tài)為真，CSP表示為對(duì)應(yīng)變量的賦值，符號(hào)定義為：動(dòng)作的前提條件可表示為所有支持變量賦值的交集，符號(hào)定義為

為了闡述清晰，進(jìn)行如下兩個(gè)定義：

定義3（前件動(dòng)作約束：preaction constraints）

定義4（前件狀態(tài)變量：precondition variables）支持動(dòng)作約束一致的全體變量集，稱(chēng)為的前件狀態(tài)變量。符號(hào)定義為

根據(jù)規(guī)劃中的動(dòng)作后續(xù)狀態(tài)關(guān)系，式（2）由2部分組成。第1部分代表了存在動(dòng)作使在s－1為真，體現(xiàn)規(guī)劃中實(shí)例化的操作。第2部分代表在以前的狀態(tài)中為真同時(shí)沒(méi)有動(dòng)作使之為假，體現(xiàn)了規(guī)劃過(guò)程的連續(xù)性。然而，由于CSP是一個(gè)靜態(tài)的問(wèn)題。在多層變量的結(jié)構(gòu)中發(fā)現(xiàn)不同層之間并不存在連續(xù)性，每一層變量都需要獨(dú)立賦值。式（2）轉(zhuǎn)化為CSP結(jié)構(gòu)后只需考察第一部分即可，對(duì)應(yīng)的轉(zhuǎn)換公式為

根據(jù)式（1）～（6），可推導(dǎo)CSP中的動(dòng)作約束關(guān)系為

CSP中的繼承狀態(tài)關(guān)系為

由于在CSP中動(dòng)作表示為約束形式，并不在賦值操作中顯式表示，因此聯(lián)立式（7）～（8）進(jìn)一步推導(dǎo)為

或表示為否定形式

式（9）～（10）揭示了相鄰層變量的賦值關(guān)系：在k層的變量Vi能夠賦值，僅當(dāng)在k– 1層中，包含Vi的前件動(dòng)作約束的前件狀態(tài)變量已被賦值。

基于以上結(jié)論以及安全性考慮，根據(jù)相鄰變量關(guān)系提出了變量繼承約束：

變量繼承約束：k層變量能夠賦值僅當(dāng)k– 1層中全部變量已完成賦值。符號(hào)表示如下

4 基于變量繼承約束的算法設(shè)計(jì)

本文基于GAC算法框架并加入約束（11）進(jìn)行改進(jìn)，改進(jìn)后的算法偽代碼圖1所示。

圖1 擴(kuò)展GAC算法偽代碼Fig. 1 Pseudo code for extended GAC algorithm

在變量選擇環(huán)節(jié)，算法首先記錄每個(gè)變量涉及到的約束數(shù)目，該數(shù)據(jù)用于對(duì)相同啟發(fā)值的候選解做進(jìn)一步的區(qū)分。接下來(lái)算法從層數(shù)為1開(kāi)始挑選變量。在該環(huán)節(jié)中，采用了動(dòng)態(tài)變量排序以及最大約束變量啟發(fā)式技術(shù)。在當(dāng)前層中的變量都完成賦值后，算法將擴(kuò)展至下一層，并重復(fù)上述過(guò)程。

算法中改進(jìn)式的變量挑選方法優(yōu)勢(shì)包括：

1）該約束對(duì)于所有約束可滿(mǎn)足編碼的規(guī)劃問(wèn)題具有一般性。

本文提出的變量繼承約束是由式（9）～（10）推導(dǎo)出的，在式（9）～（10）的推導(dǎo)過(guò)程中其理論基礎(chǔ)來(lái)源于規(guī)劃領(lǐng)域的動(dòng)作前件/后件關(guān)系以及CSP編碼的多層變量框架。變量繼承約束為規(guī)劃領(lǐng)域基礎(chǔ)的邏輯關(guān)系，后者為所有CSP編碼規(guī)劃問(wèn)題均采用的框架結(jié)構(gòu)，因此式（11）對(duì)于所有的CSP編碼規(guī)劃問(wèn)題都具有一般性。

2）該約束下的變量選擇方法具有更好的時(shí)間復(fù)雜度。

改進(jìn)GAC算法根據(jù)約束式（11）挑選出候選變量，鑒于約束式（11）基于動(dòng)作邏輯關(guān)系推導(dǎo)，因此該候選變量在約束傳播過(guò)程中不會(huì)再次違反規(guī)劃的動(dòng)作邏輯關(guān)系。這極大減少了潛在的回溯次數(shù)，降低了無(wú)效的約束檢查次數(shù)。

3）該約束能夠降低算法中無(wú)效的約束檢查次數(shù)。

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

本文的實(shí)驗(yàn)環(huán)境為微軟Visual Studio開(kāi)發(fā)環(huán)境，Intel 3.5 GHz CPU，1 GB RAM。測(cè)試算例采用國(guó)際規(guī)劃大賽（International Planning Competitions，IPC）經(jīng)典算例，測(cè)試算法的一般性以及深空探測(cè)器觀測(cè)數(shù)傳事件測(cè)試算法的實(shí)用性。測(cè)試應(yīng)用的IPC算例包括：BlockWorld，Grid，Gripper，Logistics以及Mystery。

表1展示了對(duì)IPC算例測(cè)試中GAC與其擴(kuò)展算法約束檢查數(shù)目的對(duì)比。在測(cè)試的5個(gè)算例中，擴(kuò)展算法均降低了約束檢查的數(shù)目，在某些算例中尤為明顯。例如，在Grid算例中，為解決該規(guī)劃問(wèn)題GAC算法需進(jìn)行39 214 667次約束檢查；而包含動(dòng)作約束的改進(jìn)GAC算法僅需要6 527 187次。

表1 約束檢查數(shù)目對(duì)比Table 1 Comparison of number of constraint checks

由于動(dòng)作約束的引導(dǎo)，擴(kuò)展GAC算法能夠“避開(kāi)”大量的無(wú)效約束檢查操作，因此問(wèn)題求解效率也得到極大提高。表2展示了求解IPC算例的平均時(shí)間對(duì)比，由于擴(kuò)展GAC有著更高效的變量選取已經(jīng)回避了大量的無(wú)效約束檢查，其求解效率遠(yuǎn)高于標(biāo)準(zhǔn)GAC算法。

表2 搜索時(shí)間對(duì)比Table 2 Comparison time for Gripper domain s

圖2以Gripper領(lǐng)域?yàn)槔故玖藰?biāo)準(zhǔn)GAC算法與本文提出的基于變量繼承約束的擴(kuò)展GAC算法在問(wèn)題規(guī)模逐步擴(kuò)大情況下CPU運(yùn)行時(shí)間的對(duì)比。圖中表明隨著問(wèn)題規(guī)模變大，擴(kuò)展GAC算法能夠在動(dòng)作約束中獲得更大的收益，其規(guī)劃時(shí)間的增長(zhǎng)速度遠(yuǎn)小于GAC算法的增長(zhǎng)速度。

圖2 Gripper領(lǐng)域時(shí)間對(duì)比Fig. 2 Comparison time for Gripper domain

不僅如此，大量的冗余計(jì)算將占用計(jì)算設(shè)備大量的存儲(chǔ)空間。隨著問(wèn)題規(guī)模逐步擴(kuò)大，將導(dǎo)致問(wèn)題求解的失敗。例如，GAC算法僅能求解Mystery領(lǐng)域的前3個(gè)算例，當(dāng)Mystery問(wèn)題規(guī)模變大時(shí)，GAC將無(wú)法得到規(guī)劃解。而擴(kuò)展GAC由于減少了大量的冗余計(jì)算，其求解結(jié)果如圖3所示。

圖3 擴(kuò)展GAC在Mystery域的搜索時(shí)間Fig. 3 Search time of extended GAC algorithm in Mystery domain

在對(duì)算法工程適用性的考察中，本文選取了深空探測(cè)活動(dòng)中典型的對(duì)目標(biāo)拍照并對(duì)地?cái)?shù)傳事件，忽略上傳動(dòng)作的簡(jiǎn)化MEX模型[19]。該模型為2012年國(guó)際知識(shí)工程規(guī)劃調(diào)度大賽模型中基于火星快車(chē)任務(wù)的算例，涉及到地面站、觀測(cè)器、內(nèi)存、溫控器以及姿控系統(tǒng)等多種活動(dòng)單元，各單元涉及到的動(dòng)作如表3所示。

表3 拍照數(shù)傳算例的變量及活動(dòng)Table 3 The variables and activities for the example of taking photos

針對(duì)拍照數(shù)傳活動(dòng)本文根據(jù)不同數(shù)目的子系統(tǒng)進(jìn)行了10組仿真測(cè)試，子系統(tǒng)的數(shù)量以及目標(biāo)數(shù)隨算例逐漸增加，每組的算例如表4所示。例如算例4表示探測(cè)器存在4個(gè)目標(biāo)需要拍照，探測(cè)器上攜帶2個(gè)相機(jī)，2個(gè)內(nèi)存用于存儲(chǔ)數(shù)據(jù)，2個(gè)對(duì)應(yīng)的溫控裝置用于調(diào)節(jié)相機(jī)的溫度，以及一個(gè)地面站接受數(shù)據(jù)。10組仿真測(cè)試結(jié)果如圖4所示，可以看到擴(kuò)展GAC求解問(wèn)題的時(shí)間均少于GAC算法。

表4 10組拍照數(shù)傳算例展示Table 4 The test instances of ten taking photos

圖4 拍照數(shù)傳算例時(shí)間對(duì)比Fig. 4 Time comparison of the example of taking photos

6 結(jié) 論

本文提出了一種以動(dòng)作為中心的約束可滿(mǎn)足技術(shù)用于深空探測(cè)規(guī)劃問(wèn)題。研究表明，通過(guò)充分利用任務(wù)規(guī)劃的特點(diǎn)改進(jìn)標(biāo)準(zhǔn)約束可滿(mǎn)足算法可以獲得較好的效率。通過(guò)將任務(wù)規(guī)劃問(wèn)題中的動(dòng)作關(guān)系映射到CSP中，揭示了多層變量CSP結(jié)構(gòu)中相鄰層間變量的關(guān)系。在此基礎(chǔ)上提出的動(dòng)作約束使得CSP中的變量選擇更為合理，能夠有效地減少變量選擇的時(shí)間消耗以及無(wú)效的約束檢查數(shù)。理論分析表明，該方法適用于一般的約束規(guī)劃問(wèn)題。仿真實(shí)驗(yàn)驗(yàn)證了基于動(dòng)作約束的擴(kuò)展GAC與標(biāo)準(zhǔn)GAC算法相比具有更好的性能，未來(lái)可應(yīng)用到工程實(shí)踐中。