劉 瑩，李東兵，谷文祥

(1.長春人文學(xué)院公共計算機(jī)教研部，長春 130117; 2.長春汽車工業(yè)高等專科學(xué)校信息技術(shù)學(xué)院，長春 136000; 3.東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院，長春 130117)

智能規(guī)劃自誕生之日起就一直倍受矚目，大到航空航天、智能工廠、智能交通，小到機(jī)器人控制、作業(yè)調(diào)度、橋牌游戲，無不是智能規(guī)劃在現(xiàn)實世界中的價值體現(xiàn)。由于其重要的應(yīng)用價值，近年來已經(jīng)成為人工智能領(lǐng)域極為活躍的研究熱點。

通俗地說，規(guī)劃就是為了實現(xiàn)某項任務(wù)而進(jìn)行了一系列活動。由于在任務(wù)執(zhí)行過程中還會有這樣或那樣的約束，所以只有規(guī)劃得當(dāng)，才能更快更好地完成各種任務(wù)。具體地說，智能規(guī)劃是有組織有目的地選擇一系列動作去盡可能好地實現(xiàn)的目標(biāo)。由于現(xiàn)實世界的復(fù)雜性和應(yīng)用領(lǐng)域的不同，也衍生出許多種規(guī)劃方法，如圖規(guī)劃、概率規(guī)劃、時序規(guī)劃、啟發(fā)式規(guī)劃、感知規(guī)劃等。

1969年，由Newell和Simon設(shè)計的通用問題求解器(GPS)[1]是一款在人工智能領(lǐng)域中非常重要的求解器，它標(biāo)志著智能規(guī)劃研究的起點。同年，QA3系統(tǒng)[2]問世，它使用定理證明的方法來構(gòu)造規(guī)劃。1971年，F(xiàn)ikes 和Nilsson 共同設(shè)計了STRIPS規(guī)劃系統(tǒng)[3]，它在智能規(guī)劃領(lǐng)域中具有劃時代的意義，許多規(guī)劃方法都是在STRIPS規(guī)劃系統(tǒng)的基礎(chǔ)上進(jìn)行了擴(kuò)展。在20世紀(jì)80年代對于智能規(guī)劃的研究一度低迷，直到90年代才出現(xiàn)了三種新的規(guī)劃方法，對智能規(guī)劃的研究又一次獲得全世界的關(guān)注。這三種新方法是將規(guī)劃問題求解轉(zhuǎn)化為可滿足(SAT)問題[4-5]、圖規(guī)劃[6-7]和啟發(fā)式規(guī)劃方法[8]。近年來，在這三種方法的基礎(chǔ)上，又演變出更多更好的規(guī)劃系統(tǒng)，成功地解決了許多實際問題[9-10]。此外，自1998年開始，每兩年舉辦一次的國際規(guī)劃競賽也為世界各國的規(guī)劃系統(tǒng)提供了一個全新的舞臺[11]。

智能規(guī)劃發(fā)展至今共有三種表示方式：STRIPS[12]、ADL[13]、PDDL[14]。STRIPS操作符可以對規(guī)劃進(jìn)行清晰地描述和操作。動作描述語言(ADL)，除了具備STRIPS的表達(dá)能力外，還能表達(dá)條件效果、量化效果等。規(guī)劃領(lǐng)域定義語言(PDDL)具有超強(qiáng)的表達(dá)能力，能夠刻畫時間和數(shù)值方面的屬性，目前它已經(jīng)成為國際智能規(guī)劃競賽的公認(rèn)標(biāo)準(zhǔn)。

1 智能規(guī)劃的分類

智能規(guī)劃自誕生之日起已經(jīng)繁衍出許多種類型，經(jīng)過歸納總結(jié)，大致可分為四種，如表1所示。

1.1 經(jīng)典規(guī)劃

在經(jīng)典規(guī)劃中，一個問題被定義成一個四元組，包括一個狀態(tài)變量集合P、一個狀態(tài)I、P上的操作集合O、P上的一個命題公式G。其中，I為初始狀態(tài)，G為目標(biāo)狀態(tài)。

經(jīng)典規(guī)劃的求解方法，主要可以歸為兩大類：狀態(tài)空間規(guī)劃和規(guī)劃空間規(guī)劃。狀態(tài)空間規(guī)劃主要是將狀態(tài)空間搜索技術(shù)應(yīng)用于規(guī)劃，其中的操作符同時顯式地指明了前提和效果，可以前向或后向構(gòu)建搜索。而在規(guī)劃空間規(guī)劃中，規(guī)劃器搜索的是規(guī)劃空間，規(guī)劃定義成具有一定順序并被變量綁定的規(guī)劃操作集合，它不一定對應(yīng)一個動作序列[9]。

1.2 現(xiàn)代經(jīng)典規(guī)劃

與經(jīng)典規(guī)劃一樣，現(xiàn)代經(jīng)典規(guī)劃也是受限的狀態(tài)轉(zhuǎn)換系統(tǒng)，它將搜索空間的每個結(jié)點看作成幾個部分規(guī)劃的集合。把這個集合當(dāng)成一個搜索結(jié)點時，該集合在數(shù)據(jù)結(jié)構(gòu)上或者是顯式的，或者是隱含的，但有一點事實是顯然的：在現(xiàn)代經(jīng)典規(guī)劃方法中，不是每一個結(jié)點的動作都出現(xiàn)在從該結(jié)點開始的可達(dá)解規(guī)劃中?，F(xiàn)代經(jīng)典規(guī)劃技術(shù)的發(fā)展，給規(guī)劃帶來了新的搜索空間和搜索算法，擴(kuò)大了可解的經(jīng)典規(guī)劃問題的規(guī)模。在現(xiàn)代經(jīng)典規(guī)劃技術(shù)中，主要有圖規(guī)劃技術(shù)、命題可滿足技術(shù)和約束可滿足技術(shù)[19]。本文著重介紹圖規(guī)劃及其擴(kuò)展技術(shù)。

1.2.1 圖規(guī)劃 圖規(guī)劃系統(tǒng)(Graphplan)是世界上第一個采用圖來解決規(guī)劃問題的方法。圖規(guī)劃求解方法主要有：擴(kuò)展規(guī)劃圖和搜索規(guī)劃圖兩個步驟。圖的擴(kuò)展和搜索迭代循環(huán)進(jìn)行，直到找到一個有效規(guī)劃，或滿足終止條件為止。圖規(guī)劃從初始狀態(tài)構(gòu)成的命題層出發(fā)，在動作集合找到每個命題需要的支撐動作，構(gòu)成動作層，通過添加每個動作執(zhí)行的效果再次構(gòu)成命題層，就這樣向后擴(kuò)張規(guī)劃圖，當(dāng)所有目標(biāo)都出現(xiàn)在命題列時，立即從后往前搜索有效規(guī)劃。由于引入了命題結(jié)點和動作結(jié)點互斥的概念，有效地縮小了規(guī)劃圖的搜索空間，求解能力也得到了很大的提升。

圖規(guī)劃是公認(rèn)的經(jīng)典而優(yōu)雅的算法，自其問世以來，吸引了越來越多的目光，研究者們也對其展開了相當(dāng)多的研究，做了不少的改進(jìn)與擴(kuò)展，形成了一個龐大的圖規(guī)劃家族。

1.2.2 圖規(guī)劃的擴(kuò)展 最小承諾的圖規(guī)劃[20]是在圖規(guī)劃的基礎(chǔ)進(jìn)行了擴(kuò)展，其算法也包括圖擴(kuò)張和解搜索兩個階段。采用該方法在搜索空間上比較緊湊，目標(biāo)出現(xiàn)早，提高了求解的效率。試驗表明，在經(jīng)典規(guī)劃域中，最小承諾的圖規(guī)劃算法能夠比圖規(guī)劃以及圖規(guī)劃家族的其它規(guī)劃器解決更多的問題。

為了使圖規(guī)劃可以處理更具表達(dá)力的語言和更復(fù)雜的規(guī)劃問題，在規(guī)劃中加入條件效果。帶有條件效果的圖規(guī)劃方法主要有全擴(kuò)展法[21]、要素擴(kuò)展法[22]和IPP擴(kuò)展法等。2003年，劉日仙等人在此基礎(chǔ)上提出了利用兄弟元件改進(jìn)的要素擴(kuò)展法[23]，該方法將帶有條件效果的動作分解成元件，還利用了獨立集選擇的啟發(fā)式提高了搜索的效率。

靈活圖規(guī)劃方法(FGP)[24-25]彌補(bǔ)了圖規(guī)劃對獲取現(xiàn)實世界中的某些細(xì)節(jié)不充分的缺陷，對原有的規(guī)劃定義進(jìn)行了擴(kuò)展，并且提升了規(guī)劃問題求解綜合效率。它可以處理更為復(fù)雜的現(xiàn)實問題，更加貼近人們的生活。靈活圖規(guī)劃中增加了滿意度和主觀真值度的定義，顯示出在求解過程中更加重視規(guī)劃的質(zhì)量，在某種程度上不惜以規(guī)劃長度來換取規(guī)劃質(zhì)量。2005年，徐麗提出了以目標(biāo)為導(dǎo)向的靈活圖規(guī)劃算法(GDFGP)[26]，從目標(biāo)開始逆向擴(kuò)張規(guī)劃圖，并且避免了滿意度傳播這一復(fù)雜過程。對靈活圖規(guī)劃的研究還有很多，如基于啟發(fā)式搜索的靈活規(guī)劃算法[27]、基于軟約束的多Agent靈活規(guī)劃[28-29]等。

數(shù)值圖規(guī)劃可以解決帶有資源約束的規(guī)劃問題。Koehler提出的規(guī)劃系統(tǒng)Resource-IPP[30]就可以有效地解決這類問題，它也是數(shù)值圖規(guī)劃的代表。任斐在數(shù)值圖規(guī)劃的基礎(chǔ)上，提出了嵌入模糊部件的數(shù)值圖規(guī)劃生成算法[31]，通過引入模糊部件，重新定義互斥關(guān)系及滿意度在規(guī)劃圖中的傳播方法來提高規(guī)劃系統(tǒng)的工作效率。

時序圖規(guī)劃就在圖規(guī)劃的基礎(chǔ)上增加了時序的要求，TGP和TPSYS[32-33]就是性能比較優(yōu)秀的兩款時序圖規(guī)劃器。在現(xiàn)實世界中，動作的完成時間可能是并行的，也可能是重疊的，并具有不同的持續(xù)時間，而經(jīng)典STRIPS域規(guī)劃模型的表達(dá)是完全不夠的，而時序圖規(guī)劃恰好可以解決這類問題。

1.3 不確定規(guī)劃

在紛雜的現(xiàn)實世界中，總會存在這樣或那樣的不確定性，想要得到所有確定的信息幾乎是不可能的，這就需要不確定規(guī)劃來實現(xiàn)。

馬爾可夫決策過程(MDP)是將規(guī)劃看成一個最優(yōu)化問題，可以比較高效地處理多種不確定規(guī)劃問題。利用MDP求解智能規(guī)劃問題時，每個動作都會有多種可能的輸出，通過輸出的概率值、目標(biāo)和效用值進(jìn)行計算，最后規(guī)劃算法搜索出效能函數(shù)值最大的規(guī)劃方案。

基于符號模型檢測[34]的規(guī)劃方法可以處理涉及概率分布的和部分可觀察的規(guī)劃問題，它將規(guī)劃領(lǐng)域看成是一個不確定的狀態(tài)轉(zhuǎn)換系統(tǒng)，動作的多個效果被表示為多個不同的狀態(tài)，其規(guī)劃目標(biāo)也按照不同的強(qiáng)度來表示，并使用有序二元決策圖(OBDD)[35]的符號處理技術(shù)來實現(xiàn)算法。

概率規(guī)劃、一致圖規(guī)劃和感知圖規(guī)劃都是基于圖規(guī)劃的不確定規(guī)劃。概率規(guī)劃PGP[36]算法采用概率分布的方式來描述動作結(jié)果的不確定性，可以在給定的最大時間步T內(nèi)找到成功概率最大的最優(yōu)規(guī)劃。一致圖規(guī)劃CGP[37]可以感知動作的效果，可以在初始條件及動作效果不確定的情況下，可以找到規(guī)劃解。感知圖規(guī)劃SGP[38]可以處理初始狀態(tài)不確定，動作帶有條件效果且具有感知動作的規(guī)劃問題。

1.4 啟發(fā)式規(guī)劃

啟發(fā)式規(guī)劃將規(guī)劃問題看作是一個搜索問題，運(yùn)用啟發(fā)式搜索技術(shù)朝著可能的目標(biāo)結(jié)點方向進(jìn)行搜索找到目標(biāo)結(jié)點。啟發(fā)式的設(shè)計原則就是放松，即對原來的問題做一些簡化假設(shè)和放松某些約束而得到一個更簡單的問題。在求解方法中，啟發(fā)式搜索可以和其它的方法結(jié)合使用，大大地提高了規(guī)劃系統(tǒng)的效率。文獻(xiàn)[39]將圖規(guī)劃下的啟發(fā)式搜索方法進(jìn)行了綜述，比較分析了多種啟發(fā)式方法。

HSP[40]是一款基于啟發(fā)式搜索思想的域獨立規(guī)劃器，通過累加啟發(fā)值(hadd)計算目標(biāo)實現(xiàn)的代價。1998年，HSP在世界規(guī)劃大賽中超越了GraphPlan和SatPlan，贏得了冠軍。就解決問題的數(shù)量而言，HSP無疑是最優(yōu)秀的規(guī)劃器，但速度較慢、規(guī)劃的長度較長，且不能保證規(guī)劃解的質(zhì)量是它的不足之處。

HSP-r[41]利用啟發(fā)值指導(dǎo)進(jìn)行后向搜索，可以訪問到更多的狀態(tài)，能夠在較短的時間內(nèi)產(chǎn)生更優(yōu)的規(guī)劃解。HSP-r采用了同Graphplan相同互斥思想來進(jìn)行剪枝，但是與同域指定的搜索算法相比，速度還是比較慢。

FF(Fast-Forward)[42-43]是最成功的啟發(fā)函數(shù)設(shè)計方法之一。它采用加強(qiáng)爬山算法，在每個搜索狀態(tài)中都會調(diào)用放松圖規(guī)劃，從而獲得一個關(guān)于估計的目標(biāo)距離的信息以及一個當(dāng)前狀態(tài)的最有希望的后繼狀態(tài)。FF還采用目標(biāo)刪除和目標(biāo)日程兩種技術(shù)成功地避免了找不到解和浪費(fèi)很多時間去找排在后面的目標(biāo)的情況，大大地提升了求解的質(zhì)量和速度。

LPG[44]是一款采用局部搜索來解決規(guī)劃圖問題的快速規(guī)劃器。它能夠使用各種基于參數(shù)化的目標(biāo)函數(shù)的啟發(fā)式。LPG充分運(yùn)用了規(guī)劃圖結(jié)構(gòu)，搜索空間由規(guī)劃圖的特殊子圖——動作圖構(gòu)成，能夠處理考慮到動作執(zhí)行代價的規(guī)劃問題，得到優(yōu)質(zhì)解。實驗表明，LPG非常高效，在很多著名問題的解決上優(yōu)于規(guī)劃圖類算法。

2 智能規(guī)劃與規(guī)劃識別的聯(lián)系

規(guī)劃識別是將行動者執(zhí)行的一個動作序列作為輸入，觀察者將根據(jù)觀察到的動作進(jìn)行推理，最后推測出執(zhí)行者的最終目標(biāo)，而智能規(guī)劃是尋找能夠?qū)崿F(xiàn)給定目標(biāo)的動作序列，由此可見，智能規(guī)劃是規(guī)劃識別的反向推導(dǎo)過程，二者聯(lián)系極其密切。若將智能規(guī)劃與規(guī)劃識別統(tǒng)一起來，就可以解決更多更復(fù)雜的問題，這也是未來一個重要而熱門的研究難點。

2.1 規(guī)劃識別即是智能規(guī)劃

規(guī)劃識別是逆向規(guī)劃，在規(guī)劃中，尋求實現(xiàn)目標(biāo)的動作序列，而在規(guī)劃識別中，尋求解釋所觀察到動作的目標(biāo)。這兩種任務(wù)都具有誘導(dǎo)性，需要采用一些假設(shè)來解釋給定的信息：規(guī)劃解釋目標(biāo)，目標(biāo)解釋部分觀察到的規(guī)劃。

實際上，規(guī)劃識別的工作是獨立于規(guī)劃進(jìn)行的，主要使用與規(guī)劃無關(guān)的手工庫或算法。因此，Miquel Ramírez等[45-46]通過利用近代經(jīng)典規(guī)劃算法的功能和通用性來消除規(guī)劃識別和規(guī)劃之間的隔閡，從而實現(xiàn)對給定域理論的一系列觀察結(jié)果的識別。該模型比基于庫的方法更加靈活，并允許一些簡單的擴(kuò)展，如處理通量的觀察、處理執(zhí)行時必須觀察的操作以及對觀察的部分排序。然而，該模型的一個重要方面是，它并不對可能的假設(shè)(目標(biāo))進(jìn)行加權(quán)，而只是對它們進(jìn)行過濾。

2.2 基于智能規(guī)劃、規(guī)劃識別與解析的啟發(fā)式方法

2016年Miquel Ramírez 等又提出了基于智能規(guī)劃、規(guī)劃識別與解析的啟發(fā)式方法[45]。該方法通過將規(guī)劃庫編譯為STRIPS理論，證明了該公式包含了庫規(guī)劃識別的標(biāo)準(zhǔn)公式。這些庫對應(yīng)于可能是循環(huán)的與或圖，其中與節(jié)點的子節(jié)點可能是部分有序的。這些庫將上下文無關(guān)語法作為一種特殊情況，在這種情況下，規(guī)劃識別問題變成了帶有丟失標(biāo)記的解析問題。對于標(biāo)準(zhǔn)庫的規(guī)劃識別可以成為任何現(xiàn)代規(guī)劃器都能輕松解決的規(guī)劃問題。而對于更為復(fù)雜的規(guī)劃庫的識別，即包括上下文無關(guān)語法，則說明了當(dāng)前規(guī)劃啟發(fā)式的局限性，并提出了可能提高其他規(guī)劃問題的建議。

2.3 基于規(guī)劃識別與智能規(guī)劃構(gòu)建有幫助的虛擬智能體

2016年，Geib等[47]提出了一種基于規(guī)劃識別和智能規(guī)劃交互的協(xié)同行為模型?；趯Α鞍l(fā)起者”Agent的行為的觀察，“支持者”Agent使用規(guī)劃識別來假設(shè)發(fā)起者的規(guī)劃和目標(biāo)。然后“支持者”Agent提出并規(guī)劃一組它將實現(xiàn)的子目標(biāo)來幫助發(fā)起者。該方法假設(shè)“發(fā)起者”Agent和“支持者”Agent在談判中使用的術(shù)語之間有密切的對應(yīng)關(guān)系。因為Agent之間的知識重疊程度越高，用于識別領(lǐng)域概念的名稱之間的對應(yīng)越緊密，就會出現(xiàn)合作更容易協(xié)商的情況。

主要思想是規(guī)劃識別和規(guī)劃組件的成功集成以規(guī)劃識別器進(jìn)行適當(dāng)?shù)淖幽繕?biāo)識別為中心，并結(jié)合輕量級的協(xié)商過程，生成目標(biāo)供規(guī)劃器用于構(gòu)建適當(dāng)?shù)膭幼餍蛄小Ｔ摲椒ㄔ谝粋€開放源代碼的虛擬機(jī)器人平臺上進(jìn)行了演示，并獲得了成功，充分展示了這種方法的潛力，未來這些技術(shù)將被擴(kuò)展到更為復(fù)雜的現(xiàn)實情況。

3 結(jié)語和展望

智能規(guī)劃一直以來都是人工智能的一個重要研究方向。隨著科技的不斷創(chuàng)新與發(fā)展，它已經(jīng)逐漸地深入到我們的生活與生產(chǎn)當(dāng)中。大到航空航天、生產(chǎn)調(diào)度，小到網(wǎng)絡(luò)游戲、電子導(dǎo)航，其應(yīng)用不勝枚舉[48-49]。本文從智能規(guī)劃的起源講到分類，并詳細(xì)地對各種目前比較成功的規(guī)劃進(jìn)行了對比與說明。最后對智能規(guī)劃與規(guī)劃識別的關(guān)系進(jìn)行了闡述，并列舉分析了幾種先進(jìn)的研究方法。“路漫漫其修遠(yuǎn)兮，吾將上下而求索”，相信在智能規(guī)劃的研究路途中，會涌現(xiàn)出更多更好的規(guī)劃方法，為人們的生活帶來更多的便利和樂趣。