（計算機(jī)軟件與理論專業(yè)論文）一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn).pdf

中山大學(xué)碩士論文一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 論文題目：一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 專業(yè)：計算機(jī)軟件與理論 碩士生：歐陽亞雄 指導(dǎo)教師：姜云飛教授 摘要 智能規(guī)劃( a ip l a n n i n g ) 是人工智能領(lǐng)域的一個重要分支，它的主要思想是：對周圍 環(huán)境進(jìn)行認(rèn)知與分析，根據(jù)指定的目標(biāo)，對若干可供選擇的動作及資源限制實行推理， 綜合制定出實現(xiàn)目標(biāo)的規(guī)劃( p l a n ) 。近十幾年來，智能規(guī)劃的理論研究取得了巨大的進(jìn) 步，出現(xiàn)了一些優(yōu)秀的規(guī)劃方法，其中圖規(guī)劃( 6 r a p h p l a n ) 由于其簡單、高效而成為 一個非常有吸引力的規(guī)劃方法。許多研究者對圖規(guī)劃方法作了大量的研究和改進(jìn)，并基 于此方法實現(xiàn)了優(yōu)秀的規(guī)劃系統(tǒng)。本文深入研究了圖規(guī)劃方法之后提出了一些優(yōu)化方 法，并基于該方法實現(xiàn)了規(guī)劃n z s o p 。本文給出了圖規(guī)劃的基本算法和優(yōu)化技巧的的實 現(xiàn)思路，并提出t z s u p 未來仍需改進(jìn)的方面。 【關(guān)鍵詞】人工智能，智能規(guī)劃， 圖規(guī)劃，規(guī)劃器 中山大學(xué)碩士論文 一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) t i t l e ：a ni m p l e m e n t a t i o no fp l a n n e rb a s e do ng r a p h p l a n m a j o r ：c o m p u t e rs c i e n c e n a m e ：y a x i o n go u y a n g s u p e r v i s o r ：p r o f y u n f e ij i a n g a b s t r a c t a ip l a n n i n gi sa ni m p o r t a n tb r a n c hi na if i e l d t h em a i ni d e ao fa ip l a n n i n g i st os y n t h e s i z eap l a nt oa c h i e v ed e s i r e dg o a l sb yr e c o g n i z i n ge n v i r o n m e n t s a n de h o o si n ga v a il a b l ea c ti o n su n d e rr e s o u r c ec o n s t r a i n t s i nr e c e n td e c a d e o fy e a r s ，t h e r eh a v eb e e nd r a m a t i ca d v a n c e si n p l a n n i n ga l g o r i t h m s s o m e e x c e l l e n ta l g o r i t h m sa p p e a r e di n c l u d eg r a p h p l a n 。g r a p h p l a ni sa s i m p l e ， e l e g a n ta l g o r i t h mt h a ty i e l d se x t r e m e l ys p e e d yp l a n n e r a f t e rs t u d i e d g r a p h p l a n ，w eg i v es o m eo p t i m i z a t i o n sa n di m p l e m e n tap l a n n e rz s u pb a s e do n i t a l s ow es u g g e s tf u t u r ew o r ka b o u tz s u p 【k e y w o r d s ：a i ，p l a n n i n g ，g r a p h p l a n ，p l a n n e r 中山大學(xué)碩士論文一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 引言 智能規(guī)劃是人工智能研究中應(yīng)用性很強(qiáng)的一個研究領(lǐng)域，例如工廠作業(yè)調(diào)度( j o b s h o ps c h e d u i n g ) 。車輛調(diào)度( v e h i c l es c h e d u l i n gp r o b l e m ) 等等。智能規(guī)劃技術(shù)應(yīng)用 在這些領(lǐng)域往往能為公司或者工廠帶來可觀的經(jīng)濟(jì)效益。正因為智能規(guī)劃有如此廣泛的 應(yīng)用，所以人工智能專家m c d e r m o t t 指出“智能規(guī)劃調(diào)度問題大量地出現(xiàn)在工業(yè)領(lǐng)域， 規(guī)劃質(zhì)量的改進(jìn)，哪怕是一點小小的改進(jìn)，都會節(jié)約大量的時間，帶來上百萬美元的效 益” 1 。 圖規(guī)劃方法作為智能規(guī)劃技術(shù)當(dāng)中一種優(yōu)秀的規(guī)劃方法，能夠產(chǎn)生具有很強(qiáng)規(guī)劃 能力的規(guī)劃系統(tǒng)，國外許多優(yōu)秀的規(guī)劃系統(tǒng)都是采用或者結(jié)合圖規(guī)劃方法而實現(xiàn)，研究 如何實現(xiàn)并優(yōu)化基于圖規(guī)劃方法的規(guī)劃器具有重要的意義。本文詳細(xì)的介紹了圖規(guī)劃方 法的理論，并提出了一些優(yōu)化方法，并介紹了基于該方法的規(guī)劃器z s u p 的設(shè)計思路。 最后本文給出了z s u p 與g r a p h p l a n 比較的實驗結(jié)果，以及z s u p 未來需要完善的地方。 中山大學(xué)碩士論文一種基于圖規(guī)杰! 思想的規(guī)劃囂的實現(xiàn) 1 1 概述 第一章智能規(guī)劃簡介 智能規(guī)劃( a ip l a n n i n g ) 的研究從二十世紀(jì)5 0 年代開始，它與人工智能的研究 幾乎一樣早，但最初階段由于理論和應(yīng)用的限制，智能規(guī)劃的發(fā)展比較緩慢。近4 0 年來由于應(yīng)用需要的推動，吸引了眾多的研究者加入了這個研究領(lǐng)域，使得智能規(guī)劃 的發(fā)展越來越快，成為了人工智能研究的熱點 1 。 智能規(guī)劃本質(zhì)上屬于人工智能的一種問題求解方法，1 9 5 7 年n e w e l l 和s i m o n 的問題求解程序( g p s ) 其實就是最早的智能規(guī)劃系統(tǒng)，因此智能規(guī)劃系統(tǒng)可以被看 作是一個問題求解系統(tǒng)。 采用智能規(guī)劃系統(tǒng)求解復(fù)雜的問題，得到的結(jié)果是個動作序列，依次執(zhí)行此 動作序列能完成指定的具體任務(wù)，從而達(dá)到指定的目標(biāo)。顧名思義，規(guī)劃，就是給 定一個待解決的實際問題，在執(zhí)行一系列動作之前，事先制定出動作的計劃，即先 對闖題做出規(guī)劃，然后執(zhí)行規(guī)劃。 最初研究者對智能規(guī)劃系統(tǒng)的研究起源于問題求解，但隨著規(guī)劃研究的發(fā)展， 使得規(guī)劃比常規(guī)的問題求解更加注重于解決具體的實際問題，而并非抽象的數(shù)學(xué)模 型【6 】。 智能規(guī)劃也不并僅限于給出動作的執(zhí)行順序，還要求能夠監(jiān)視動作序列的執(zhí)行 過程，如果動作執(zhí)行的結(jié)果出現(xiàn)意外并且影響后續(xù)的動作執(zhí)行，則要求規(guī)劃系統(tǒng)能 夠進(jìn)行適當(dāng)?shù)母深A(yù)并重新作出合理的規(guī)劃。 在現(xiàn)實世界中，當(dāng)人類面對復(fù)雜的實際問題時，首先是對問題進(jìn)行周密的考慮， 制定一個可行的規(guī)劃，然后按照這個規(guī)劃執(zhí)行，在執(zhí)行的過程中如果出現(xiàn)問題或意 外情況，還會對未執(zhí)行的計劃進(jìn)行修正甚至重新規(guī)劃，直到達(dá)到目標(biāo)為止。智能規(guī) 劃實際上就是模擬了人類處理復(fù)雜的實際問題的這樣一個過程。 中山大學(xué)碩士論文 種基于圈規(guī)劃思想的規(guī)劃器的實現(xiàn) 1 2 主要思想 智能規(guī)劃的主要思想：對周圍環(huán)境進(jìn)行認(rèn)知與分析，根據(jù)需要實現(xiàn)的目標(biāo)及當(dāng)前的 狀態(tài)，對若干可供選擇的動作及所提供的資源限制施行推理，綜合制定出實現(xiàn)目標(biāo)的 規(guī)劃( p l a n ) 1 智能規(guī)劃研究的主要目的是建立高效實用的智能規(guī)劃系統(tǒng)( p l a n n e r ) 。該系統(tǒng)的主 要功能可以描述為： 給定問題的形式化描述： 1 初始狀態(tài)的形式化描述 2 目標(biāo)狀態(tài)的形式化描述 3 對可實施的動作的形式化描述( 通常也稱為領(lǐng)域知識) 3 智能規(guī)劃系統(tǒng)能夠根據(jù)該問題的形式化描述給出從初始狀態(tài)轉(zhuǎn)換到目標(biāo)狀態(tài)的一 個動作序列( p l a n ) ，即規(guī)劃解。 問題的形式化描述通常采用命題邏輯或者一階謂詞邏輯的形式化語言，例如：積木世 界問題的形式化描述如下： ( p r e c o n d s ( o n - t a b l eb l o c k a ) ( o n t a b l eb l o c k b ) ( o nb l o c k cb l o e k a ) ( c l e a rb l o c k s ) f d e a l b l o c k c ) ( a m - e r u p t y ) ) ( e f f e c t s ( o nb l o c k a b l o c k b ) ( 0 nb l o c k bb l o c k c ) ) 廣初始狀態(tài)， p 目標(biāo)狀態(tài) ( o p e r a t o rp 動作( 算子) ， p i c k - u p 0 a l a m s ( o b l o b j e c t ) ) ( p r e e o n d s ( c l e a r ) ( o n - t a b l e ) ( a r m - e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) ( o p e r a t o r p u p d o w n ( p a r a m s ( o s j e c r ) ) 中山大學(xué)碩士論文一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) r e c o n d s ( h o l d i n g d ( e f f e c t s ( c l e a r ( o b ) ( a r m - e m p t y ) ( o n - t a b l e o b ) ) ) 智能規(guī)劃系統(tǒng)的復(fù)雜性和系統(tǒng)所處的環(huán)境以及a g e n t 的功能有關(guān)，為了簡化規(guī)劃問 題，經(jīng)典的規(guī)劃做出如下假設(shè) 1 3 。 1 環(huán)境的狀態(tài)的改變完全由a g e n t 的動作的效果造成的，排除外界的影響和干 擾。 2 a g e n t 的動作的效果是完全確定的。 3 ，a g e n t 能夠感知環(huán)境和動作的效果。 具有上述假設(shè)的規(guī)劃問題叫做經(jīng)典規(guī)劃問題。 通常，我們把滿足以上假設(shè)的規(guī)劃稱之為“經(jīng)典的規(guī)劃”( c l a s s i c a lp l a n n i n g ) ， 例如地圖著色問題、積木世界問題等都是經(jīng)典的規(guī)劃問題。現(xiàn)在大多數(shù)研究者仍然采 納此假定。由于現(xiàn)實世界的復(fù)雜性，實際問題往往并不能滿足上述條件，許多研究者 也正在研究不限制于此假定的規(guī)劃，例如在環(huán)境不斷變化情況下的規(guī)劃問題。不滿足 此假定的規(guī)劃問題稱之為“非經(jīng)典的規(guī)劃”( n o n c l a s s i c a lp l a n n i n g ) 6 。本文設(shè) 計的規(guī)劃系統(tǒng)針對的是經(jīng)典的規(guī)劃問題。 1 3 智能規(guī)劃方法 1 3 1 基于定理證明的規(guī)劃方法 基于定理證明的規(guī)劃系統(tǒng)本質(zhì)上是基于消解原理( r e f u t a t i o nr e s o l u t i o n ) 6 ， 它采用定理證明的方法，把規(guī)劃求解的過程看成是一個證明過程，該證明過程試圖證明 由初始狀態(tài)和動作序列等構(gòu)成的命題表達(dá)式能夠推導(dǎo)出目標(biāo)狀態(tài)為真，其證明的過程就 是規(guī)劃解?；诙ɡ碜C明的規(guī)劃方法以命題邏輯、一階謂詞邏輯等規(guī)范邏輯和各種菲規(guī) 范邏輯如缺省推理( d e f a u l ti n f e r e n c e ) 、或然推理( p l a u s i b l ei n f e r e n c e ) 、時序邏 輯( t e m p o r a ll o g i c ) 、內(nèi)涵邏輯( i n t e n t i o n a ll o g i c ) 、非單調(diào)邏輯( n o n - m o n o t o n el o g i c ) 4 中山大學(xué)碩士論文 種基于酉規(guī)劃思想的規(guī)劃囂的實現(xiàn) 和模糊邏輯( f u z z yl o g i c ) 等為其理論基礎(chǔ)。較為典型的系統(tǒng)是g 1 r e r n s t 和a n e w e l l 設(shè)計的通用問題求解系統(tǒng)( g p s ，g e n e r a lp r o b l e ms o l v e r ) 和g r e e n 的q a 3 系統(tǒng)。 基于定理證明的規(guī)劃方法在求解規(guī)劃問題方面有固有的先天性不足，它會產(chǎn)生一 些異常模型( a n o m a l o u sm o d e l s ) ：即存在這樣的模型，它們滿足定理，但卻找不到和 模型相對應(yīng)的有效的規(guī)劃解 1 。c h a p m a n 深入地研究了模型和規(guī)劃解的對應(yīng)關(guān)系，給 出了模型對應(yīng)規(guī)劃解的充分條件，并且給出了證明過程。 因此研究者普遍認(rèn)為：規(guī)劃問題必須采用特定目的的定理證明器來解決，通用的定 理證明器不能有效的求解規(guī)劃問題，而且通用的定理證明器無法增加領(lǐng)域( 啟發(fā)式) 知 識或者在加入一些推理的策略。 1 3 2 基于搜索的規(guī)劃方法( p l a n n i n ga ss e a r c h ) 基于搜索的規(guī)劃方法通常是在問題的狀態(tài)空間上進(jìn)行搜索，例如：n i l s s o n 和他的 斯坦福研究院人工智能研究組設(shè)計的s t r i p s 系統(tǒng)( s t a n f o r dr e s e a r c hi n s t i t u t e p r o b l e ms o l v e r ) 就是典型的基于搜索的規(guī)劃方法 3 。尤其值得一提的是，s t r i p s 系 統(tǒng)提出的s t r i p s 算子對動作的表達(dá)能力非常適用，后來的很多規(guī)劃系統(tǒng)都采用了 s t r i p s 風(fēng)格的表達(dá)方式。 在s t r i p s 系統(tǒng)中，動作算子可以改變問題空間的狀態(tài)，而對規(guī)劃的求解就是利用 算子改變狀態(tài)空間，并搜索狀態(tài)空間直到搜索到目標(biāo)的狀態(tài)空間。搜索的方式通常有前 向搜索( f o r w a r ds e a r c h ) ，反向搜索( b a c k w a r ds e a r c h ) 或者兩種方式結(jié)合在一起。 1 3 3 半序規(guī)劃方法( p a r t i a l - o r d e rp l a n n i n g ) 半序規(guī)劃方法是對操作序列加上一組半序約束，滿足這些約束的動作序列叫 做候選規(guī)劃。它是一個全序的操作序列，但是在半序上與約束的要求完全一致，在 數(shù)據(jù)結(jié)構(gòu)課程中，也把這個過程叫做拓?fù)渑判?1 。 規(guī)劃的過程可以看成是“排除”和“分裂”的過程?！芭懦钡倪^程就是增加 約束，排除掉那些不能成為解的候選規(guī)劃?！胺至选钡倪^程就是在規(guī)劃中插入新的操 作，搜索那些滿足條件的解。 中山大學(xué)碩士論文一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 按約束要求給出操作序列的過程也叫做線性化，安全的線性化不但要滿足對 操作的半序約束，而且要滿足輔助約束。半序規(guī)劃實際上代表了一組動作序列，任 何與上述半序規(guī)劃的序相符合的全序動作序列都是strips 系統(tǒng)的規(guī)劃。 半序規(guī)劃的求精策略 可以把半序規(guī)劃的求精看成是一個過程，也可以看成一個映射r ，它把一個規(guī) 劃約束集合p 映成為另一個規(guī)劃約束集合p ，使得p 的候選規(guī)劃集是p 的候選規(guī)劃 集的子集。如果p 包含了p 的所有的解，則r 稱作是完各的( c o m p l e t e ) 。如果p 的候選規(guī)劃集是p 的候選規(guī)劃集的真子集， 則r 稱作是前進(jìn)的( p r o g r e s s i v e ) 1 。 如果沒有操作序列屬于具有p 的一個以上約束的候選規(guī)劃集，則稱r 具有系統(tǒng)性 ( s y s t e m a t i c ) 。完備性保證我們在求精的過程中不會丟失解，前進(jìn)性保證我們在求 精的過程中會有效地剪掉不是解的候選規(guī)劃，系統(tǒng)性保證我們在求精的過程中只能對 同一個候選解考慮一次。 求精策略可分為正向和反向兩種。正向策略從初始狀態(tài)出發(fā)，不斷增加約束，一 直到目標(biāo)狀態(tài)得到滿足為止。反向策略則從目標(biāo)出發(fā)增加約束，知道動作的前提條件 都被問題的初始條件包含為止。因為反向策略產(chǎn)生的分支數(shù)比較少，因而在規(guī)劃系統(tǒng) 中使用的比較多。 最小承諾策略 最小承諾就是在規(guī)劃的求精過程中，對規(guī)劃個體所加的約束盡可能的少，以免 過多的約束造成規(guī)劃步驟聞的不相容，從面導(dǎo)致不必要的回溯。例如，如果在規(guī)劃 的求精過程中有兩個可供選擇的操作，一個需要間隔保持約束，而另一個不需要，則 我們應(yīng)該選擇后一種求精過程。在比如，如果兩個供選擇的操作中，一個是抽象的 動作( 由若干具體簡單動作抽象得來) ，而另一個是具體的動作，則我們應(yīng)該選擇抽 象的操作。 最小承諾與問題領(lǐng)域有很強(qiáng)的依賴性，一般說來，承諾相當(dāng)于增加了約束，這 樣容易識別半序規(guī)劃是否包含解，但是增加了回溯的次數(shù)。因此對于問題的解比較少 的問題領(lǐng)域，晟小承諾比較有效，而對于解比較多的問題領(lǐng)域，效果差一些。 中山大學(xué)碩士論文 一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 1 3 4 圖規(guī)劃( g r a p h p l a n ) 方法 b l u m 和f u r s t 的圖規(guī)劃方法是最近幾年智能規(guī)劃最具吸引力的一種方法。因為圖 規(guī)劃方法作為一個簡單、高效的方法能夠產(chǎn)生非?？焖俚囊?guī)劃器，而且在圖規(guī)劃方法中 采用的知識表達(dá)方式也成為基于s a t ( 約束可滿足) 規(guī)劃的知識編碼的基礎(chǔ)。本文設(shè)計 的規(guī)劃系統(tǒng)就是基于圖規(guī)劃方法。第二章將會詳細(xì)介紹圖規(guī)劃方法。 1 3 5 基于約束可滿足的方法( s a t ) 基于約束可滿足規(guī)劃是h e n r yk a u t z 和b a r ts e l m a n 深入地分析了傳統(tǒng)的基于定理 證明的規(guī)劃以后提出來的完全不同于以往演繹技術(shù)的一種特殊的規(guī)劃方法，它克服了傳 統(tǒng)規(guī)劃器的異常( 每一個模型不一定對應(yīng)一個有效的規(guī)劃解) 情況，使得每一個正確模 型都有一個有效的規(guī)劃解與其相對應(yīng) 3 。 圖2 _ 6 s a t 規(guī)劃的體系結(jié)構(gòu)如圖2 6 所示，編譯器( c o m p i l e r ) 的輸入是規(guī)劃問題( 包 括初始狀態(tài)、目標(biāo)狀態(tài)和動作集合) ，它首先猜測規(guī)劃解的長度，產(chǎn)生一個邏輯命題公 式，如果邏輯命題公式是可滿足的，它蘊(yùn)涵著規(guī)劃解是存在的：符號表( s y m b o lt a b l e ) 記錄了命題變量和規(guī)劃實例之間的對應(yīng)：簡化器( s i m p l i f i e r ) 運(yùn)用較快( 通常為線性 時間) 的技術(shù)( 如單元子句法，純文字消去法等) 等來降低c n f 公式的規(guī)模；求解器 ( s o l v e r ) 運(yùn)用系統(tǒng)或統(tǒng)計的方法來找到一個滿足的賦值；解碼器( d e c o d e r ) 用符號 表把賦值轉(zhuǎn)換成一個規(guī)劃解。如果求解器發(fā)現(xiàn)公式是不可滿足的，那么編譯器就會產(chǎn)生 新的編碼( 代表更長的規(guī)劃解) 。 由基于s a t 的規(guī)劃的體系結(jié)構(gòu)可以看到，這種規(guī)劃方法關(guān)鍵在于兩個環(huán)節(jié)，一個是 編碼方式，另一個是求解方式。有關(guān)第一個問題的研究取得了一系列的進(jìn)展，由于基于 7 中山大學(xué)碩士論文一種基于圈規(guī)劃思想的規(guī)劃器的實現(xiàn) s a t 的規(guī)劃算法是基于s a t 算法來實現(xiàn)的，所以第二個問題其實就是選擇好的s a t 算法， 而可滿足性( s a t ) 問題是人工智能研究領(lǐng)域中的一個基本理論問題，最近幾年來，每 年都有新的s a t 算法問世，人們設(shè)計各種各樣的技術(shù)來提高解決s a t 問題的效率，這幾 年來主要有g(shù) s a t 算法和w a l k s a t 算法，但是這兩個算法都不是完備的，一個比較經(jīng)典 的完備s a t 算法是d p 算法。 總結(jié)g r a p h p l a n 和s a t p i a n 的相同點和異同點： 共同點：s a t p i a n 和g r a p h p l a n 都分兩階段進(jìn)行： ( 1 ) 建立一個命題結(jié)構(gòu)( ap r o p o s i t i o n a ls t r u c t u r e ) ：在圖規(guī)劃中是規(guī)劃圖， 在s a t 規(guī)劃中是c n fw f f 。 ( 2 )在第一步所建立的結(jié)構(gòu)中搜索規(guī)劃解。 異同點： 圖規(guī)劃( g r p h p l a n ) 用的實例化命題結(jié)構(gòu)算法較好。 s a t 規(guī)劃( s a t p l a n ) 的搜索算法更加強(qiáng)大。 結(jié)合以上兩種算法的優(yōu)點，k a u t z 和s e l m a n 于1 9 9 8 年在a i p s 上提出了b l a c k b o x 規(guī)劃算法，此系統(tǒng)分三個步驟進(jìn)行工作： 1 把一個規(guī)劃問題( 以標(biāo)準(zhǔn)的s t r i p s 形式描述的) 轉(zhuǎn)化為一個規(guī)劃圖。 2 把第一步中生成的規(guī)劃圖轉(zhuǎn)化成一個c n fw f f 。 3 運(yùn)用最快的s a t 引擎解決w f f 。 1 3 6 其它規(guī)劃方法 除了上述的規(guī)劃方法外，還有基于事例( c a s e - b a s e d ) 的規(guī)劃方法、基于約束 ( c o n s t r a i n t - b a s e d ) 的規(guī)劃方法、互操作( r e a c t i v ea p p r o a c h e s ) 規(guī)劃方法、分 布式規(guī)劃( d i s t r i b u t e dp l a n n i n g ) 、骨架式規(guī)劃( s k e l e t a lp l a n n i n g ) 、概率( 機(jī)遇) 式規(guī)劃( o p p o r t u n i s t i cp l a n n i n g ) 、線形規(guī)劃( l i n e a rp l a n ) 、層次規(guī)劃( h i e r a r c h y p l a n n i n g ) 、非線形規(guī)劃( n o n l i n e a r p l a n ) 、啟發(fā)式規(guī)劃( h e u r i s t i cp l a n n i n g ) 等等 6 ， 這里就不一一贅述了。 8 中山大學(xué)碩士論文一種基于圈規(guī)劃思想的規(guī)劃器的實現(xiàn) 1 4 目前的研究背景 1 在最近的7 - 8 年，許多智能規(guī)劃系統(tǒng)的規(guī)劃能力有了非常大的提高。過去的 智能規(guī)劃系統(tǒng)只能產(chǎn)生出5 _ 6 個動作的規(guī)劃，且需花費(fèi)幾分鐘的時間：而現(xiàn)在 同樣的時間內(nèi)卻能夠產(chǎn)生超過1 0 0 個動作的規(guī)劃。 2 智能規(guī)劃的理論研究有了太幅度的進(jìn)展。例如：把智能規(guī)劃問題和約束可滿足 問題聯(lián)系起來進(jìn)行研究，取消了智能規(guī)劃和調(diào)度問題的區(qū)別，利用領(lǐng)域知識進(jìn) 行規(guī)劃的方法等等【1 5 ，6 1 。 3 智能規(guī)劃系統(tǒng)能力的提高，使智能規(guī)劃在實際應(yīng)用領(lǐng)域得到了廣泛的應(yīng)用。 例如：在工業(yè)、交通、信息、機(jī)器人、航空航天等領(lǐng)域。 4 在國外，近年來成立了許多專門從事智能規(guī)劃方面研究的協(xié)會和聯(lián)盟，如歐 洲智能規(guī)劃網(wǎng)p l a n e t ( e u r o p e a nn e t w o r ko fe x c e l l e n c ei na ip l a n n i n g ) ，英 國諾丁漢大學(xué)a s a p 研究組( a u t o m a t e ds c h e d u l i n g , o p t i m i s a t i o na n d p l a n n i n g ) 以及美國亞利桑那州立大學(xué)砌1 a l l 研究組1 1 】 5 一些國際知名期刊發(fā)表的關(guān)于智能規(guī)劃方面的論文呈逐年增長的趨勢。如 a r t i f i c i a li n t e l l i g e n c e 近年來發(fā)表了許多篇智能規(guī)劃方面的文章，在1 9 9 5 , 2 0 0 3 都出版了關(guān)于智能規(guī)劃的?？?。 6 在一些大學(xué)里，不僅有越來越多的研究人員從事智能規(guī)劃方面的研究工作，還 在大學(xué)生和研究生中開設(shè)了智能規(guī)劃方面的課程。 7 近十幾年來，智能規(guī)劃方面的學(xué)術(shù)會議也越來越多，u c a i ( i n t e r n a t i o n a lj o i n t c o n f e r e n c eo n a r t i f i c i a li n t e l l i g e n c e ) p 0 0 1 年召開智能規(guī)劃與機(jī)器人”( h a r m i n g a n dr o b o t i c s ) 專題的研討會：國際智能規(guī)劃與調(diào)度研討會a i p s ( a r t i f i c i a l i n t e l l i g e n c ep l a n n i n g s c h e d u l i n g ) 已經(jīng)舉辦到1 2 屆：歐洲智能規(guī)劃研討會 e c p ( e u r o p e a nc o n f e r e n c eo np l a n n i n g ) 已經(jīng)舉辦到第5 屆；其中在2 0 0 3 年 a i p s 和e c p 合并為屬于i e e e 下的國際智能規(guī)劃與調(diào)度研討會i c a p s ( i n t e r n a t i o n a lc o n f e r e n c e0 1 1 a u t o m a t e dp l a n n i n g s c h e d u l i n g ) 【1 】。 中山大學(xué)碩士論文 種基于田規(guī)劃思想的規(guī)劃器的實現(xiàn) 2 1 圖規(guī)劃簡介 第二章圖規(guī)劃方法 圖規(guī)劃( g r a p h p l a n ) 方法是近十年來智能規(guī)劃研究中發(fā)展非?？斓囊环N方法， 它最初是由a v r i ml b u m 和m e r r i c kl f u r s t 4 提出來，而后，很多研究者在這 個基礎(chǔ)上提出了許多改進(jìn)和優(yōu)化。目前主要基于圖規(guī)劃方法的規(guī)劃系統(tǒng)有美國卡乃 基一梅隆大學(xué)( c a r n e g i e m e l l o n u n i v e r s i t y ) 的圖規(guī)劃器g r a p h p l a n ( b l u m l f n r s t ) 、 德國的i p p 、英國的s t a n 、美國華盛頓大學(xué)( u n i v e r s i t yo fw a s h i n g t o n ) 的 s g p ( d a n i e ls w e l d 等) 3 。 2 2 基本概念和定義 2 2 1s 嘲p s 算子 1 9 7 1 年，f i k e s n i t s s o n 7 在他們開發(fā)的智能規(guī)劃系統(tǒng)s t r i p s 當(dāng)中提出了一 種算子，由于該算子在表達(dá)動作方面具有很好的適用性，后來的許多規(guī)劃系統(tǒng)大多采用 類s t r i p s 風(fēng)格的算子。 一個s t r i p s 算子由三部分組成： 1 ) 集合p c ，稱為算予的前提條件( p r e c o n d i t i o n s ) 的基本文字。即當(dāng)p c 中的所 有文字都在當(dāng)前狀態(tài)描述中時，動作才能被執(zhí)行。 2 ) 集合d ，稱為刪除列表( d e l e t e1 i s t ) 的基本文字。 3 ) 集合a ，稱為加入列表( a d dl i s t ) 的基本文字。 為了生成動作后的狀態(tài)描述，刪除動作前狀態(tài)出現(xiàn)在d 集合中的所有文字，加入a 中的所有文字，在d 中沒有提到的文字延續(xù)至動作后狀態(tài)描述中，這種延續(xù)是為了解決 框架問題的種方法。 例如： 中山大擘碩士論文一種基于萄授劃思想韻覯捌器的實現(xiàn) m o v e ( x ，y ，z ) p c ：o n ( x ，y ) a n dc l e a r ( x ) a n dc l e a r ( z ) d ：c l e a r ( z ) o n ( x ，y ) a ：o n ( x ，z ) ，c l e a r ( y ) ，c l e a r ( f 1 ) 在圖規(guī)劃系統(tǒng)中采用了兩種算子表達(dá)方式：( 1 ) p r o d i g y ( 2 ) n o n p r o d i g y 。 p r o d i g y 的表達(dá)方式將增加效應(yīng)和刪除效應(yīng)的命題合并在一起，給刪除效應(yīng)命題加 上特殊的前綴，例如”d e l “，使得系統(tǒng)能夠分辨出增加效應(yīng)和刪除效應(yīng)。 n o n - p r o d i g y 的表達(dá)方式?jīng)]有給出刪除效應(yīng)，刪除效應(yīng)由前提條件和增加效應(yīng)的集 合差表達(dá)，即前提條件沒有顯式出現(xiàn)在效果的命題里被默認(rèn)為屬于刪除的命題。這種表 達(dá)方式簡潔有效，適合大多數(shù)常用的領(lǐng)域。本文所研究的動作實例化方法是基于這種表 達(dá)類型的算子。 例如： ( o p e r a t o r p i e k - u p ( p a r a m s ( o b j e c t ) ) ( p r e c o n d s ( c l e a r ) ( o n - t a b l e ) ( a r l l l e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) 算子本質(zhì)上是一種動作模式( a c t i o ns c h e m a t a ) 3 ，它是為了簡化對規(guī)劃問題 的動作的表達(dá)。在規(guī)劃問題里存在若干個對象，如果采用具體的動作表達(dá)方式，將 使得規(guī)劃系統(tǒng)變得很龐大，它需要為每個可能的對象生成具體的動作，這使得規(guī)劃 問題的表達(dá)變得很繁瑣。因此，將大量的具體的動作抽象成若干種動作模式就能簡 化規(guī)劃動作的表達(dá)。算子包含自由變量，而不是實際的對象。若存在替換 ( s u b s t i t u t i o n ) 使得算子的自由變量替換成實際的對象，那么該算子變成一個具體 的動作，這稱為動作實例化。 例如下面給出了一個積木世界算子實例化為具體動作的例子。 當(dāng)前狀態(tài)為： ( o n - t a b l eb l o c k a ) 1 1 中山大學(xué)碩士論文 一種基于圖規(guī)劃思想的規(guī)劃囂的實現(xiàn) ( o n - t a b l eb l o c k b ) ( o nb l o c k cb l o c k a ) r c l e a tb l o c k b ) ( e l e a tb l o c k c ) ( a r m e m p t y ) 對于算予p i c k - u p ( o p e r a t o r p i c k - u p ( p a r a m s ( o b j e c t ) ) ( p r e t e n d s ( c l e a r ) ( o n t a b l e ) ( a t m - e m p t y ) ) ( e f f e c t s ( h o l d i n g ) ) ) 可以實例化為動作：p i c k - u pb l o c k b p r e c o n d s ：( c l e a rb l o c k b ) ( o n - t a b l eb l o e k b ) ( a r m e m p t y ) e f f e c t s ：( h o l d i n gb l o c k b ) 2 2 2 有效規(guī)劃解( v a l i dp l a n ) 通常來講一個有效的規(guī)劃解是一個動作序列，它包括一個動作的集合，且指定每個動 作執(zhí)行的順序。其中有些動作可以并發(fā)的執(zhí)行，有些動作則不行。在線性規(guī)劃里，可以 并發(fā)執(zhí)行的動作可以采用任意的順序執(zhí)行【4 】。 2 2 3 規(guī)劃圖( p l a n n i n gg r a p h ) 圖規(guī)劃方法提出了規(guī)劃圖這樣一種數(shù)據(jù)結(jié)構(gòu)，它將規(guī)劃問題編碼為規(guī)劃圖，利用規(guī) 劃圖來搜索規(guī)劃解 3 。 規(guī)劃圖( p l a n n i n gg r a p h ) 是一個具有兩類節(jié)點和三類邊的有向分層圖 1 ，2 。規(guī)劃 圖各層依次由命題層( p r o p o s i t i o nl e v e l s ) 和動作層( a c t i o nl e v e l s ) 交替出現(xiàn)，命 中山大學(xué)碩士論文 一種基于圖規(guī)劃思想的規(guī)劃器的實現(xiàn) 題層包含命題節(jié)點( 一些命題為標(biāo)記) ，動作層包含動作節(jié)點( 一些動作為標(biāo)記) 。 如圖2 ，黑色圓圈表示命題節(jié)點，方框節(jié)點表示動作節(jié)點。動作結(jié)點與上一層的命 題結(jié)點的線段表示這些命題是該動作的前提條件：動作結(jié)點與下一層的命題層結(jié)點的線 段表示這些命題是該動作的效果( 包括增加效果和刪除效果) 。上一層命題層結(jié)點與下 層命題結(jié)點直接相連的線段表示沒有任何動作實施使得狀態(tài)延續(xù)，這能夠解決框架公理 ( f r a m ea x i o m ) 問題。 0i 1ii + 1 - 圖2 - i 2 2 4 規(guī)劃圖的互斥關(guān)系 圖規(guī)劃方法的最重要的特征就是發(fā)現(xiàn)和記錄動作結(jié)點或者命題結(jié)點間的互斥關(guān) 系，通過互斥關(guān)系，可以顯著減少搜索的開銷【4 】。 互斥關(guān)系的定義：給定某一動作層的兩個動作，如果不存在一個有效的規(guī)劃解包含 這兩個動作，那么這兩個動作互斥；給定某一命題層的兩個命題，如果不存在一個有效 的規(guī)劃解使得這兩個命題同時為真，那么這兩個命題互斥【4 】。 圖規(guī)劃方法通過一些簡單的規(guī)則來發(fā)現(xiàn)和延續(xù)這些互斥關(guān)系，以下給出了這些簡 單的規(guī)則： 兩個動作在第i 層互斥當(dāng)且滿足以下規(guī)則： ( 1 )效果不相容( i n c o n s i s t e n te f f e c t s ) = 一個動作的效果是另外一個動作的效果 的反命題，或者說一個動作增加的效果恰恰是另外一個動作刪除的效果。 ( 2 ) 沖突國t e r f e r e n c e ) ：一個動作的效果刪除了另外一個動作的前提 中山大學(xué)硬士論文一種基于圖規(guī)劃思想舯規(guī)劃囂的實現(xiàn) ( 3 ) 競爭所需( c o m p e t i n gn e e d s ) ：兩個動作的前提的命題在i - 1 層互斥 兩個命題在第i 層互斥當(dāng)滿足以下規(guī)則： ( 1 ) 一個命題是另外一個命題的取反 ( 2 ) 獲得一個命題的所有動作解與獲得另外一個命題的所有動作解兩兩互斥。 在解提取過程中，可以充分利用規(guī)劃圖構(gòu)造的動作結(jié)點和命題結(jié)點的互斥關(guān)系，減 少解的搜索過程，例如在解的反向搜索過程中，當(dāng)某一個子目標(biāo)與另外一個子目標(biāo)互斥， 則不需要再對這個子目標(biāo)繼續(xù)搜索?；蛘弋?dāng)為某個子目標(biāo)選取動作解時，如果該動作 與已經(jīng)選擇的動作解互斥，則不需要選擇該動作，而繼續(xù)搜索其他的動作或者回溯。 2 2 5 規(guī)劃圖的定理 ( 1 )如果存在一個小于或者等于t 步的有效規(guī)劃解，那么這個規(guī)劃解一定是規(guī)劃圖 的子圖。 ( 2 ) 假設(shè)一個具有n 個物體，初始命題具有p 個文字、1 1 1 個s t r i p s 算子的規(guī)劃問 題，假設(shè)l 等于最長的算子a d d l i s t 的長度，那么創(chuàng)建t 層的規(guī)劃圖的時間是n , m ，p ，1 ，t 的多項式。 證明： 假設(shè)k 是最長的算子參數(shù)的長度，由于算子不能創(chuàng)建對象，因此能夠被一 個算子增加的命題數(shù)量為o ( 1 n 。) ，因此規(guī)劃圖的任意命題層的結(jié)點數(shù)不超過 0 0 + m 1 i 國，由于每個算子最多能被實例化為o ( n b + ，因此規(guī)劃圖的任意動作層的結(jié) 點數(shù)不超過o ( mn k ) 。因此規(guī)劃圖的大小是n , m ，p ，l ，t 的多項式( k 通常是個常量) 。 2 3 圖規(guī)劃過程 規(guī)劃圖的第一層( 初始層) 是命題層，該層包含規(guī)劃問題的初始條件下的所有命題。 圖規(guī)劃在兩個階段( p h a s e s ) 交替進(jìn)行：圖擴(kuò)展( g r a p he x p a n s i o n ) 和解提取( s o l u t i o n e x t r a c t i o n ) 。 ( 1 ) 開始時構(gòu)造只有第一層命題層的規(guī)劃圖，這第一層命題層包含初始狀態(tài)的命題 1 4 中山大學(xué)碩士論文一種基于圈規(guī)劃思想的規(guī)劃囂的實現(xiàn) ( 2 ) 然后遞歸的擴(kuò)展規(guī)劃圖，假設(shè)在第i 步 ( 3 ) g r a p h p l a n 把第i - 1 步的規(guī)劃圖作為輸入 ( 4 ) 把該規(guī)劃圖擴(kuò)展一個動作層和一個命題層 ( 5 ) 然后在擴(kuò)展后的規(guī)劃圖提取長度為i 的規(guī)劃解 ( 6 ) g r a p h p l a n 或者搜索到一個長度為i 的規(guī)劃解或者無解。 ( 7 ) 如果無解，則i i i + 1 ，繼續(xù)( 3 ) ( 8 ) 結(jié)束 2 3 1 圖擴(kuò)展 圖擴(kuò)展階段分為兩個步驟： ( 1 ) 假設(shè)當(dāng)前層為第i 層，對于每一個算子，選取所有可能的對象將算子實例 化為動作，如果當(dāng)前命題層滿足該動作的前提條件且前提條件不互斥，那么將 動作插入規(guī)劃圖的第i + l 層即動作層，同時插入無動作結(jié)點( n o 0 1 3 ) ，該結(jié)點表 示持續(xù)效果，即命題沒有施加任何動作，狀態(tài)持續(xù)不變。然后插入前提條件的 邊：檢查每個動作結(jié)點，根據(jù)2 2 4 提到的規(guī)劃圖的互斥關(guān)系規(guī)則，為每個動作 創(chuàng)建一個互斥鏈表，該鏈表記錄所有與該動作互斥的動作。這個步驟完成了第 i + l 層的規(guī)劃圖的創(chuàng)建，包括結(jié)點和邊。 ( 2 ) 檢查第i + 1 層的動作結(jié)點的增加效果( 包括無動作結(jié)點) ，把這些增加效 粟命題插入到第i + 2 層的命題層( 無動作結(jié)點的增加效果就是前提條件) ，然后 插入增加效果或者刪除效果的邊，如果所有到達(dá)第i + 2 層的兩個命題的動作解 兩兩互斥，則標(biāo)記這兩個命題互斥。 2 3 2 解提取 給定一個規(guī)劃圖，g r a p h 采用反向鏈接( b a c k w a r d - c h a i n i n g ) 策略從規(guī)劃圖中提取 出規(guī)鯔解，這個過程就是解提取過程。解提取過程反向搜索是逐層迸行，這是為了能充 分利用每一層的互斥關(guān)系c 4 。 給定一個第t 步的目標(biāo)集合，解提取嘗試在t - 1 步發(fā)現(xiàn)一個動作的集合( 包括無動 作) ，使得這些動作的增加效果就是該目標(biāo)集合。而這些動作的前提條件又形成第t - 1 中山大學(xué)碩士論文一種基于圈規(guī)劃思想的規(guī)生! 器的實現(xiàn) 步的子目標(biāo)。如果這些t 一1 步的子目標(biāo)不存在有效的規(guī)劃解，那么解提取嘗試在t 一1 步發(fā)現(xiàn)另外的一個動作集合，持續(xù)直到成功地獲得規(guī)劃解或者證明無解。這個過程是一 個遞歸的過程。 為了實現(xiàn)上述策略，g r a p h p l a n 采用如下遞歸的搜索方法： ( 1 )依次選擇第t 步的每個目標(biāo)，選擇第t - 1 步的動作能達(dá)到這個目標(biāo)，且該 動作不與已經(jīng)選擇的動作互斥。持續(xù)遞歸的選擇第t 步的下一個目標(biāo)；如 果該目標(biāo)已經(jīng)存在于已經(jīng)選擇的動作的增加效果，則不需要加入這個動作 jo ( 2 ) 如果選擇動作失敗，就嘗試另外的動作以達(dá)到當(dāng)前的目標(biāo)。如果所有的動 作都嘗試過但仍然互斥，則返回失敗。 ( 3 ) 如果第t 步的目標(biāo)都能夠達(dá)到，那么所選動作的前提作為新的子目標(biāo)集合， 即t - 1 步的目標(biāo)。 g r a p h p l a n 在解提取過程中提到了一個重要的優(yōu)化過程：m e m o r i z a t i o n ：當(dāng)解提 取過程時，如果發(fā)現(xiàn)在t 步時間里發(fā)現(xiàn)某目標(biāo)子集無解，則先將該目標(biāo)子集存入哈 希表中，如果下次搜索到第t 步的目標(biāo)子集，首先尋找哈希表中是否存在該目標(biāo)子 集，如果存在則無需再搜索。 2 3 3 無解的判定 如果不存在規(guī)劃解，規(guī)劃圖將會無限制的擴(kuò)展，為了解決這個問題，m 印h p l 紐 給出了無解的判定條件： 假設(shè)一個問題無解，那么在不斷的擴(kuò)展規(guī)劃圖中，一定存在一個命題層p 使得p 以后的命題層和p 一樣，具有同樣的命題結(jié)點和同樣的命題互斥關(guān)系。我們稱之為l e v e l o f f , 可以理解為規(guī)劃圈擴(kuò)展的飽和狀態(tài)。如圖2 - 1 ： 審山大學(xué)磺士論文一種基于圈規(guī)劃思想的規(guī)劃器的實現(xiàn) 個 數(shù) 時間 圖2 1 個數(shù) 關(guān)系個數(shù) 證明： 規(guī)劃圖存在無動作結(jié)點，即上一層的命題層結(jié)點持續(xù)到下一層命題結(jié)點，由于 基于s t r i p s 風(fēng)格的算子所增加的命題集合是有限的，因此一定存在命題層o ，o 以后 的命題層與q 具有同樣多的命題結(jié)點。由于存在無動作結(jié)點，如果某一層命題p 和q 不互斥，那么p , q 延續(xù)到下一層一定也不互斥，即互斥關(guān)系在q 之后定是單調(diào)非遞增。 因此，一定存在命題層p 在q 以后，所有的命題具有同樣的互斥關(guān)系。 l e v e lo f f ，即飽和狀態(tài)是無解的必要條件。 在解提取過程中，g r a p h p l a n 記住哪些被確定為無規(guī)劃解的目標(biāo)子集。假定s ! 表示 經(jīng)過第t 步，第i 層的被判定為無解的目標(biāo)子集的集合( t i ) 。換句話說，在第t 層的 規(guī)劃圖進(jìn)行反向提取時，在第i 層確定無解的目標(biāo)子集。g r a p h p l a n 此時能夠判定兩個 事實 ( 1 ) 如果存在t 步或者更少的規(guī)劃解，那么該規(guī)劃解至少能夠使得g 中的一個子 集為真。 ( 2 ) s j 的任一個子集在第i 步時是無解的。 假設(shè)規(guī)劃圖在第n 步達(dá)到l e v e l o f f * t 態(tài)，如果經(jīng)過t 步( 1 n ) ，滿足i 4 i = i s ：l ， 那么該規(guī)劃問題無解。這是無解的充分條件。 中山大學(xué)碩士論文 種基于圈規(guī)龍! 思想的魏射囂的實現(xiàn) 2 4 圖規(guī)劃的優(yōu)化 解的提取過程的優(yōu)化：f o r w a r dc h e c k i n g ，m e m o r i z a t i o n ， e x p l a n a t i o n b a s e d l e a r n i n g 圖擴(kuò)展過程的優(yōu)化：h a n d l i n g t h ec l o s e d w o r l da s s u m p t i o n ，c o m p i l a t i o no fa c t i o n s c h e m a t a t y p ea n a l y s i s ， s i m p l i f i c a t i o n ， r e g r e s s i o nf o c u s i n g ，a n di n p l a c e g r a p he x p a n s i o n 。 以上提到的圖規(guī)劃的優(yōu)化都能夠或多或少的提高規(guī)劃系統(tǒng)的效率，限于篇幅，本文 這里介紹幾個主要的優(yōu)化方法，詳細(xì)的資料可以查看參考文獻(xiàn) 3 ( 1 ) m e m o r i z a t i o n ： 在反向搜索解的過程中，如果在時問t 的子目標(biāo)被確定為無解，則 g r a p h p l a n 將該子目標(biāo)記錄下來。如果在下一次時間t 創(chuàng)建了子目標(biāo)，首先檢 查該子目標(biāo)是否已被記錄為無解，如果是，則直接回溯而無需繼續(xù)搜索。 ( 2 ) f o r w a r dc h e c k i n g ： f o r w a r dc h e c k i n g 優(yōu)化技巧來源于c s p ( 約束可滿足問題) ：當(dāng)給一個變量 賦值時，c s p 解答系統(tǒng)只是簡單的保證該值與已賦值是一致的。而f o r w a r d c h e c k i n g 作為更好的一種技巧則首先檢查未賦值的變量，刪除掉那些與已賦值不一 致的值，如果未分配的變量的值域為空( 說明不存在與已賦值一致的值