智能規(guī)劃的研究與發(fā)展

劉 瑩，李東兵，谷文祥

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

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

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

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

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

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

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

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

在經(jīng)典規(guī)劃中，一個(gè)問(wèn)題被定義成一個(gè)四元組，包括一個(gè)狀態(tài)變量集合P、一個(gè)狀態(tài)I、P上的操作集合O、P上的一個(gè)命題公式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ī)劃，其中的操作符同時(shí)顯式地指明了前提和效果，可以前向或后向構(gòu)建搜索。而在規(guī)劃空間規(guī)劃中，規(guī)劃器搜索的是規(guī)劃空間，規(guī)劃定義成具有一定順序并被變量綁定的規(guī)劃操作集合，它不一定對(duì)應(yīng)一個(gè)動(dòng)作序列[9]。

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

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

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

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

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

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

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

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

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

1.3 不確定規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)和展望

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