基于延遲部分推理的快速前向規(guī)劃系統(tǒng)(

1、基于延遲部分推理的快速前向規(guī)劃系統(tǒng)*本課題得到國(guó)家自然科學(xué)基金重大項(xiàng)目（60496320）、國(guó)家自然科學(xué)基金（60773097，60473003，60473042，60573067）和教育部高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金（20050183065）資助蔡敦波，男，1981年生，博士研究生，主要研究領(lǐng)域?yàn)橹悄芤?guī)劃、約束滿(mǎn)足問(wèn)題e-mail：dunbocaigmailcom殷明浩，男，1979年生，博士研究生，主要研究領(lǐng)域?yàn)橹悄芤?guī)劃、規(guī)劃識(shí)別和自動(dòng)推理谷文祥，男，1947年生，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別、模糊推理及其應(yīng)用孫吉貴，男，1962年生，教授，博士生導(dǎo)師，主要研究領(lǐng)域

2、為智能規(guī)劃與自動(dòng)推理劉科成，男，1980年生，碩士，主要研究領(lǐng)域?yàn)橹悄芤?guī)劃與規(guī)劃識(shí)別蔡敦波1），2），3） 殷明浩1），2），3） 谷文祥3） 孫吉貴1），2） 劉科成4）1）（吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130012）2）（吉林大學(xué)知識(shí)工程與符號(hào)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室 長(zhǎng)春130012）3）（東北師范大學(xué)計(jì)算機(jī)學(xué)院 長(zhǎng)春 130117）4）（東北師范大學(xué)外國(guó)語(yǔ)學(xué)院 長(zhǎng)春130024）摘 要 根據(jù)動(dòng)作組件誘發(fā)關(guān)系的存在和抵制計(jì)算的必要性，提出一個(gè)計(jì)算松弛規(guī)劃解的新方法延遲部分推理該方法在考慮動(dòng)作刪除效果的假定下，構(gòu)造不包含任何互斥關(guān)系的組件規(guī)劃圖，通過(guò)定義“松弛誘發(fā)”關(guān)系預(yù)測(cè)后續(xù)規(guī)劃過(guò)程

3、中可能出現(xiàn)的組件誘發(fā)現(xiàn)象，在松弛規(guī)劃解提取階段判斷動(dòng)作組件間的“松弛誘發(fā)”關(guān)系并選擇抵制動(dòng)作避免可能發(fā)生的消極作用基于延遲部分推理方法定義了新的啟發(fā)式函數(shù)和剪枝策略，設(shè)計(jì)了規(guī)劃系統(tǒng)ffc并在多個(gè)國(guó)際通用的測(cè)試域上進(jìn)行實(shí)驗(yàn)結(jié)果表明，ffc較之fast-forward在求解效率和求解質(zhì)量方面都有顯著的提高關(guān)鍵詞 智能規(guī)劃；啟發(fā)式搜索；樸素組件規(guī)劃圖；延遲部分推理中圖法分類(lèi)號(hào) tp301fast forward planning system based on delayed partly reasoning*cai dun-bo 1），2），3） yin ming-hao 1），2），3） gu

4、wen-xiang 3） sun ji-gui 1），2） liu ke-cheng 4）1）（college of computer science and technology，jilin university，changchun 130012）2）（key laboratory of symbolic computation and knowledge engineering of ministry of education，changchun 130012）3）（college of computer science，northeast normal university，changc

5、hun 130117）4）（school of foreign languages，northeast normal university，changchun 130024）abstract heuristic based planning becomes the main trend of ai planning and has proven to be successful in almost every type of planning problemshigh quality heuristics and effective pruning methods are two keys t

6、o such planning systemsrealizing the two techniques based on relaxed-plans was first used for the fast-forward（ff）planning system and is still used by current top-performing plannersconcerning the inconsistent performance of ff in adl domains，we introduce a new method for extracting relaxed plans wh

7、ile considering the inducing relations between components and the necessity of doing confrontations that are common in adl planninga relaxed inducing relation between components is proposed to predict possible inducing relations in the actual planning processbased on actionsdelete effects and a simp

8、lified components planning graph，confrontations are done in the relaxed-plan-extraction phase to handle negative interactions between componentsboth the improved heuristic and the improved pruning technique based on the new relaxed-plan extraction method are implemented in a system called ffcexperim

9、ental results show ffc outperforms ff in several adl domains in both planning efficiency and planning qualityour work shows the subtleness of state space planning that handles conditional effects partially using an ipp method or factored expansion，and provides an efficient method to deal with such c

10、omplicacieskeywords ai planning；heuristic search；nave components planning graph；delayed partly reasoning1 引言在過(guò)去十多年中，智能規(guī)劃研究領(lǐng)域取得了巨大的突破，相對(duì)于1995年之前的智能規(guī)劃系統(tǒng)，現(xiàn)代規(guī)劃系統(tǒng)無(wú)論在規(guī)劃求解規(guī)模上還是在規(guī)劃求解效率上都有數(shù)量級(jí)的提高為了進(jìn)一步提高智能規(guī)劃系統(tǒng)的求解效率，研究人員提出了多種智能規(guī)劃求解方法，例如，基于問(wèn)題轉(zhuǎn)換的規(guī)劃方法1,2，基于啟發(fā)式搜索的規(guī)劃方法3-7，基于因果鏈接的規(guī)劃方法8,9等其中，基于啟發(fā)式搜索的規(guī)劃方法是當(dāng)前規(guī)劃研究的熱點(diǎn)該類(lèi)規(guī)劃

11、方法通過(guò)領(lǐng)域無(wú)關(guān)的啟發(fā)函數(shù)和剪枝策略等技術(shù)提高求解效率，在國(guó)際智能規(guī)劃競(jìng)賽（international planning competition，ipc）10中取得了優(yōu)異的成績(jī)，如hsp3，fast-forward（ff）4，lpg5，fast downward6和sgplan7等在多個(gè)基于啟發(fā)式搜索的規(guī)劃系統(tǒng)中，ff是表現(xiàn)最為突出的智能規(guī)劃系統(tǒng)之一該系統(tǒng)分別獲得了2000年智能規(guī)劃競(jìng)賽的“杰出性能”獎(jiǎng)和2002年智能規(guī)劃競(jìng)賽strips11規(guī)劃的“最優(yōu)性能”獎(jiǎng)10ff系統(tǒng)的核心技術(shù)包括：增強(qiáng)爬山算法（enforced hill-climbing），基于松弛規(guī)劃解（relaxed plan）的

12、啟發(fā)式函數(shù)和“有利動(dòng)作”剪枝策略（helpful actions），此外，為了保證系統(tǒng)的完備，在增強(qiáng)爬山算法失敗后該系統(tǒng)調(diào)用貪婪最好優(yōu)先搜索算法（greedy best-first）12由于增強(qiáng)爬山算法通常能夠成功求解，ff在多個(gè)規(guī)劃域上顯示出較高的效率4ff的設(shè)計(jì)者h(yuǎn)offmann從啟發(fā)式函數(shù)性能的角度對(duì)該現(xiàn)象進(jìn)行了詳細(xì)的實(shí)踐和理論分析13然而，在adl14語(yǔ)言描述的規(guī)劃問(wèn)題上，增強(qiáng)爬山算法存在大量失敗的情況實(shí)際上，ff性能不一致的關(guān)鍵在于“有利動(dòng)作”策略對(duì)于adl語(yǔ)言描述的規(guī)劃任務(wù)存在失效情況相對(duì)于strips語(yǔ)言，adl語(yǔ)言具有更強(qiáng)的表達(dá)能力，是一個(gè)更加方便規(guī)劃問(wèn)題建模的語(yǔ)言但是，adl

13、語(yǔ)言的復(fù)雜性對(duì)規(guī)劃系統(tǒng)的推理能力提出了更高的要求針對(duì)其中最為復(fù)雜的語(yǔ)法特性條件效果，研究者提出了多種處理方法，如全擴(kuò)展法（full expansion）15，ipp方法16和分枝擴(kuò)展法（factored expansion）17，其中，全擴(kuò)展法可能導(dǎo)致動(dòng)作數(shù)目的指數(shù)級(jí)別增加，適合在規(guī)劃求解的過(guò)程中使用；后兩種方法類(lèi)似，均采用不完全處理的方式，適合在規(guī)劃求解的過(guò)程之前使用，但是要求規(guī)劃過(guò)程更加復(fù)雜17為了在規(guī)劃系統(tǒng)的預(yù)處理階段降低規(guī)劃任務(wù)的規(guī)模以及制定目標(biāo)議程（goal agenda）18，ff在adl規(guī)劃中采用ipp方法存儲(chǔ)動(dòng)作，使用圖規(guī)劃19算法計(jì)算松弛規(guī)劃任務(wù)（忽略動(dòng)作刪除效果）的規(guī)劃解事

14、實(shí)上，經(jīng)過(guò)ipp方法和分枝擴(kuò)展法處理的動(dòng)作效果之間都存在“組件誘發(fā)”關(guān)系（one component induces other components）17松弛圖規(guī)劃算法無(wú)法處理這種關(guān)系，導(dǎo)致“有利動(dòng)作”策略產(chǎn)生錯(cuò)誤的剪枝行為，使得ff系統(tǒng)的整體性能下降針對(duì)這個(gè)難題，本文定義了組件之間的“松弛誘發(fā)”關(guān)系并提出一個(gè)稱(chēng)為延遲部分推理的方法我們首先構(gòu)造一個(gè)不包含任何互斥關(guān)系的組件規(guī)劃圖樸素組件規(guī)劃圖，在之后的松弛規(guī)劃解提取過(guò)程中判斷“松弛誘發(fā)”關(guān)系并抵制（confront）該關(guān)系可能產(chǎn)生的消極作用在松弛規(guī)劃圖的第0時(shí)間步處理“松弛誘發(fā)”關(guān)系時(shí)，將抵制動(dòng)作標(biāo)記為“有利動(dòng)作”，從而改進(jìn)了ff系統(tǒng)的“有利

15、動(dòng)作”策略在此方法中，“松弛誘發(fā)”關(guān)系能夠預(yù)測(cè)一部分可能出現(xiàn)的組件誘發(fā)關(guān)系；與已有方法在規(guī)劃圖擴(kuò)展階段處理可能誘發(fā)關(guān)系不同，我們將“松弛誘發(fā)”關(guān)系的處理推遲到規(guī)劃解提取階段因此，本文提出的延遲部分推理方法具有三個(gè)特點(diǎn)：1）通過(guò)處理一部分可能的組件誘發(fā)關(guān)系減少了“有利動(dòng)作”策略的錯(cuò)誤剪枝行為；2）計(jì)算代價(jià)低；3）提高了啟發(fā)式函數(shù)的信息量我們以ff系統(tǒng)為基礎(chǔ)，基于延遲部分推理方法，實(shí)現(xiàn)了稱(chēng)為ffc的規(guī)劃系統(tǒng)，在adl語(yǔ)言描述的多個(gè)標(biāo)準(zhǔn)測(cè)試域進(jìn)行實(shí)驗(yàn)結(jié)果表明，在大多數(shù)問(wèn)題上ffc的求解效率和求解質(zhì)量比之ff都有顯著的提高本文的組織如下：第二節(jié)分析ff在adl規(guī)劃上效率低下的原因；第三節(jié)提出“松弛誘發(fā)

16、”關(guān)系和基于樸素組件規(guī)劃圖的延遲部分推理方法；第四節(jié)在國(guó)際上通用的adl語(yǔ)言描述的規(guī)劃域上對(duì)ffc和ff進(jìn)行性能比較并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行初步的分析；最后介紹相關(guān)研究并對(duì)全文進(jìn)行總結(jié)松弛圖規(guī)劃增強(qiáng)爬山算法規(guī)劃任務(wù)狀態(tài)目標(biāo)距離估計(jì)有利動(dòng)作集合成功/失敗圖1 ff的基本系統(tǒng)結(jié)構(gòu)2 ff系統(tǒng)的局限性ff規(guī)劃系統(tǒng)的結(jié)構(gòu)如圖1所示松弛圖規(guī)劃模塊是ff系統(tǒng)的核心模塊之一，它一方面為系統(tǒng)提供當(dāng)前狀態(tài)與目標(biāo)狀態(tài)的距離估計(jì)，一方面為增強(qiáng)爬山算法提供有利動(dòng)作以裁減搜索空間一個(gè)規(guī)劃任務(wù)（planning task）對(duì)應(yīng)的松弛規(guī)劃任務(wù)（relaxed planning task）是忽略該任務(wù)中動(dòng)作刪除效果的結(jié)果ff利用圖規(guī)

17、劃計(jì)算松弛規(guī)劃任務(wù)的解，隨后，使用該解的代價(jià)估計(jì)原規(guī)劃任務(wù)的代價(jià)本文將求解松弛規(guī)劃任務(wù)的圖規(guī)劃算法稱(chēng)為松弛圖規(guī)劃（relaxed graphplan，rgp）ff使用目標(biāo)議程方法降低問(wèn)題求解難度，使用松弛圖規(guī)劃模塊提供的啟發(fā)信息引導(dǎo)搜索，并設(shè)計(jì)了高效的局部搜索算法增強(qiáng)爬山實(shí)現(xiàn)快速求解，僅在增強(qiáng)爬山算法失敗時(shí)調(diào)用貪婪最好優(yōu)先算法上述各種技術(shù)的綜合使得ff在大部分邏輯規(guī)劃問(wèn)題求解中表現(xiàn)出優(yōu)異的性能然而，我們發(fā)現(xiàn)ff系統(tǒng)在求解adl規(guī)劃問(wèn)題時(shí)，與求解strips規(guī)劃問(wèn)題相比，雖然在較小規(guī)模問(wèn)題上性能良好，但是在處理大規(guī)模問(wèn)題時(shí)效率表現(xiàn)不一致實(shí)驗(yàn)發(fā)現(xiàn)，增強(qiáng)爬山算法在其中的一些問(wèn)題上求解失敗，隨后被調(diào)用

18、的貪婪最好優(yōu)先算法求解效率較低，因此ff的整體效率降低其原因在于，經(jīng)ipp方法處理的adl動(dòng)作包含組件誘發(fā)關(guān)系，該關(guān)系的處理需要基于動(dòng)作的刪除效果進(jìn)行推理，然而，松弛圖規(guī)劃完全忽略了動(dòng)作的刪除效果，無(wú)法進(jìn)行必要的推理，提供了不完備的有利動(dòng)作，導(dǎo)致增強(qiáng)爬山算法失敗a = a0, a1a0: pre: p effects: r (when q p) a1: pre: q effects: qi = p, q g = p, r a = a0, a1 cs = e0, e1, e2a0 = e0, e1a1= e2e0 = (p, r, )e1 = (p, q, r, p)e2 = (q, q)i =

19、 p, q g = p, r pqrpqe0e1e2facts0 c0 facts1圖 2 一個(gè)規(guī)劃任務(wù)p 圖 3 分枝擴(kuò)展法處理p的結(jié)果圖 4 狀態(tài)i對(duì)應(yīng)的松弛規(guī)劃圖我們以adl語(yǔ)言描述的一個(gè)簡(jiǎn)單規(guī)劃任務(wù)為例（見(jiàn)圖2）說(shuō)明基于松弛圖規(guī)劃的“有利動(dòng)作”策略的失效情況圖2所示的規(guī)劃任務(wù)p涉及兩個(gè)動(dòng)作a0和a1其中a0的前提為命題p，帶有兩個(gè)效果：r是一個(gè)無(wú)條件效果，表示a0執(zhí)行后命題r為真；(when q p)是一個(gè)條件效果，表示如果命題q在a0執(zhí)行前為真，則a0執(zhí)行后命題p為假在初始狀態(tài)中，命題p和q均為真，目標(biāo)條件是p和r為真分枝擴(kuò)展法將每個(gè)動(dòng)作轉(zhuǎn)化一個(gè)組件集合，其中每個(gè)組件對(duì)應(yīng)于該動(dòng)作的一

20、個(gè)（條件）效果組件的形式為e = (con(e), add(e), del(e)，其中con(e)，add(e)和del(e)均是原子命題的集合，分別表示組件e的發(fā)生條件、添加效果和刪除效果由于動(dòng)作a0包含一個(gè)無(wú)條件效果r和一個(gè)條件效果(when q p)，所以在圖3中a0包含兩個(gè)對(duì)應(yīng)的組件e0和e1對(duì)于規(guī)劃任務(wù)p，增強(qiáng)爬山算法從初始狀態(tài)i開(kāi)始搜索，首先調(diào)用松弛圖規(guī)劃計(jì)算i的目標(biāo)距離估計(jì)松弛圖規(guī)劃根據(jù)i建立的規(guī)劃圖如圖4所示（注意：組件的刪除效果被忽略），其中的虛線(xiàn)表示noop動(dòng)作本文假定組件規(guī)劃圖從時(shí)間步0開(kāi)始構(gòu)造，每個(gè)時(shí)間步包括一個(gè)命題列和一個(gè)組件列第0命題列包含命題p和q，第0組件列包含

21、組件e0、e1和e2，第1命題列包含命題r、p和q由于所有的目標(biāo)命題均在圖中出現(xiàn)，圖擴(kuò)展過(guò)程結(jié)束松弛圖規(guī)算法根據(jù)noop動(dòng)作優(yōu)先原則以及具有最小難度的動(dòng)作優(yōu)先原則4，選擇組件e0添加命題r，選擇命題p對(duì)應(yīng)的noop動(dòng)作添加命題p，最終得到一條松弛規(guī)劃，并反饋給增強(qiáng)爬山模塊如下信息：當(dāng)前狀態(tài)到達(dá)目標(biāo)狀態(tài)的距離是1，有利動(dòng)作集合為a0增強(qiáng)爬山算法應(yīng)用動(dòng)作a0轉(zhuǎn)移到狀態(tài)s = q, r由于該狀態(tài)不滿(mǎn)足目標(biāo)條件，增強(qiáng)爬山算法再次調(diào)用松弛圖規(guī)劃計(jì)算s的目標(biāo)距離估計(jì)和有利動(dòng)作集合松弛圖規(guī)劃根據(jù)s建立的松弛規(guī)劃圖達(dá)到穩(wěn)定卻不包含目標(biāo)條件p，因此，反饋給增強(qiáng)爬山算法如下信息：當(dāng)前狀態(tài)到達(dá)目標(biāo)狀態(tài)的距離為隨后，

22、增強(qiáng)爬山算法報(bào)告搜索失敗事實(shí)上，規(guī)劃任務(wù)p存在規(guī)劃解：從初始狀態(tài)出發(fā)，只要依次執(zhí)行動(dòng)作a1和a0就可以到達(dá)一個(gè)目標(biāo)狀態(tài)松弛圖規(guī)劃無(wú)法發(fā)現(xiàn)有利動(dòng)作a1的原因在于未考慮動(dòng)作a0中組件e0對(duì)組件e1的誘發(fā)（induce）關(guān)系（由于e0和e1均是動(dòng)作a0的一部分，當(dāng)a0執(zhí)行時(shí)，e0和e1都可能影響執(zhí)行結(jié)果）如果它能夠預(yù)測(cè)到在初始狀態(tài)i上執(zhí)行a0時(shí)e1將發(fā)生并且刪除已經(jīng)實(shí)現(xiàn)的目標(biāo)命題p，從而在動(dòng)作a0執(zhí)行之前選擇動(dòng)作a1來(lái)破壞組件e1的發(fā)生條件，則能夠成功地引導(dǎo)增強(qiáng)爬山算法然而，忽略動(dòng)作的全部刪除效果使得這種推理變得不可能，“有利動(dòng)作”策略不可避免地發(fā)生失誤3 樸素組件規(guī)劃圖上的延遲部分推理“有利動(dòng)作”

23、剪枝策略是ff的關(guān)鍵技術(shù)，能夠以指數(shù)級(jí)別降低搜索空間的規(guī)模避免該策略發(fā)生失誤的最簡(jiǎn)單方式是采用全擴(kuò)展法處理adl動(dòng)作，但是需要巨大的存儲(chǔ)空間當(dāng)采用ipp方法或分枝擴(kuò)展法時(shí)，避免該策略發(fā)生失誤的方法比較復(fù)雜其中的困難在于規(guī)劃算法需要估計(jì)在后續(xù)規(guī)劃過(guò)程中可能發(fā)生的所有組件誘發(fā)關(guān)系，并保留對(duì)誘發(fā)關(guān)系的消極作用進(jìn)行抵制的能力20但是，預(yù)測(cè)所有可能的組件誘發(fā)關(guān)系需要較高的計(jì)算代價(jià)，而且這些誘發(fā)關(guān)系可能分布在多個(gè)規(guī)劃解之中，而啟發(fā)函數(shù)只需要估計(jì)其中一條規(guī)劃解的長(zhǎng)度基于以上分析，我們定義了與單個(gè)松弛規(guī)劃解相關(guān)的組件誘發(fā)關(guān)系“松弛誘發(fā)”，在構(gòu)造規(guī)劃圖過(guò)程中保留動(dòng)作的刪除效果，在規(guī)劃解提取過(guò)程中判斷組件之間的松

24、弛誘發(fā)關(guān)系并進(jìn)行相應(yīng)的抵制下面，我們首先介紹處理?xiàng)l件效果的三種方法，說(shuō)明采用ipp方法或者分枝擴(kuò)展法的必要性，之后提出基于分枝擴(kuò)展法的樸素組件規(guī)劃圖及延遲部分推理方法3.1 條件效果處理方法比較和strips語(yǔ)言相比，adl語(yǔ)言具有更強(qiáng)的知識(shí)表達(dá)能力，可以描述更為復(fù)雜的世界模型其特點(diǎn)在于允許動(dòng)作模型包含全稱(chēng)量詞和條件效果目前處理?xiàng)l件效果的方法主要有三種，其一為全擴(kuò)展方法，其二為ipp方法，其三為weld等人提出的分枝擴(kuò)展法全擴(kuò)展法將一個(gè)帶有條件效果和全稱(chēng)量詞的adl動(dòng)作轉(zhuǎn)化為多個(gè)獨(dú)立的strips動(dòng)作，即，基于全擴(kuò)展法的規(guī)劃算法在狀態(tài)上應(yīng)用一個(gè)動(dòng)作時(shí)不必考慮其它動(dòng)作對(duì)狀態(tài)轉(zhuǎn)移的影響但是，該方法

25、的缺點(diǎn)在于轉(zhuǎn)化后的動(dòng)作數(shù)目隨著原問(wèn)題包含的對(duì)象數(shù)目和動(dòng)作效果數(shù)目呈指數(shù)級(jí)別增長(zhǎng)，需要大量的存儲(chǔ)空間ipp方法和分枝擴(kuò)展法均采用部分處理的方式，將一個(gè)adl動(dòng)作的不同效果分離，存儲(chǔ)空間需求隨著原問(wèn)題涉及的對(duì)象數(shù)目和動(dòng)作效果數(shù)目呈線(xiàn)性級(jí)別增長(zhǎng)在本文，我們采用分枝擴(kuò)展法分枝擴(kuò)展的主要思想是將動(dòng)作所有的效果條件化，根據(jù)每個(gè)效果構(gòu)造一個(gè)動(dòng)作組件（component），一個(gè)組件由三部分構(gòu)成：發(fā)生條件、添加效果和刪除效果組件的發(fā)生條件是被轉(zhuǎn)化動(dòng)作的前提和對(duì)應(yīng)的條件效果前提的合取，組件的添加效果和刪除效果根據(jù)對(duì)應(yīng)的條件效果生成例如，在圖2的規(guī)劃任務(wù)中動(dòng)作a0被分枝擴(kuò)展法處理為如圖3所示的兩個(gè)組件e0和e1我們

26、一般稱(chēng)組件e0和e1來(lái)自（屬于）動(dòng)作a0ipp方法和分枝擴(kuò)展方法在顯著減少動(dòng)作數(shù)目的同時(shí)給規(guī)劃算法帶來(lái)額外的困難，其主要原因是組件誘發(fā)關(guān)系的存在17以圖規(guī)劃方法為例規(guī)劃圖的擴(kuò)展算法基于組件進(jìn)行推理，而不是基于動(dòng)作的推理；但最終的規(guī)劃解由動(dòng)作構(gòu)成，而不是由組件構(gòu)成這使得在規(guī)劃圖構(gòu)造過(guò)程中，需要使用復(fù)雜的規(guī)則計(jì)算組件間可能存在的互斥關(guān)系；在規(guī)劃解提取過(guò)程中，需要做出抵制決策（confrontation）來(lái)避免組件之間由于相互誘發(fā)而產(chǎn)生的消極作用，此類(lèi)回溯點(diǎn)的增加降低了回溯算法的效率3.2 樸素組件規(guī)劃圖組件規(guī)劃圖由weld等人提出，用于擴(kuò)展圖規(guī)劃方法處理adl規(guī)劃問(wèn)題的能力17它的構(gòu)造方法和規(guī)劃圖

27、的構(gòu)造方法類(lèi)似，區(qū)別在于前者由命題列和組件列交替構(gòu)成本文假定組件規(guī)劃圖從時(shí)間步0開(kāi)始構(gòu)造，每個(gè)時(shí)間步包含一個(gè)命題列和一個(gè)組件列對(duì)于組件c，當(dāng)它的所有發(fā)生條件都在第i命題列出現(xiàn)并且不存在兩兩互斥時(shí)被加入第i組件列，其添加命題被加入第i+1命題列在組件規(guī)劃圖的擴(kuò)展過(guò)程中計(jì)算如下的互斥關(guān)系和組件誘發(fā)關(guān)系17：定義 3.1 設(shè)cn和cm是兩個(gè)組件，如果（1）cn和cm來(lái)自?xún)蓚€(gè)不同的動(dòng)作，并且組件cn刪除組件cm的發(fā)生條件或者添加效果，或者（2）cn的某個(gè)前提和cm的某個(gè)前提在第i命題列互斥，或者（3）存在第三個(gè)組件ck，ck由cn在第i列誘發(fā)，且ck和cm互斥，則稱(chēng)組件cn和cm在第i組件列（第i時(shí)間

28、步）互斥其中由（1）、（2）和（3）引起的三類(lèi)互斥關(guān)系分別稱(chēng)為干擾效果（interference effects)、競(jìng)爭(zhēng)需要（competing needs）和誘發(fā)組件（induced components）誘發(fā)的定義如下：定義 3.2 設(shè)cn和ck是兩個(gè)組件，如果（1）cn和ck來(lái)自同一個(gè)動(dòng)作，并且（2）cn和ck不互斥，并且（3）con(ck)中的每個(gè)命題的否定在第i命題列不被滿(mǎn)足，則稱(chēng)組件cn在第i組件列（第i時(shí)間步）誘發(fā)組件ck組件cn誘發(fā)組件ck意味著cn的執(zhí)行必然伴隨ck的執(zhí)行我們簡(jiǎn)要介紹組件誘發(fā)的含義設(shè)組件cn和ck均來(lái)自動(dòng)作a，且動(dòng)作a執(zhí)行前的狀態(tài)為s， con(cn)和con

29、(ck)分別表示cn和ck的發(fā)生條件cn誘發(fā)ck的情況可以分為兩種：一種情況為，當(dāng)con(ck) con(cn)時(shí)cn必然誘發(fā)ck；另一種情況為，當(dāng)con(cn) con(ck)且con(ck) s時(shí)cn條件誘發(fā)ck稱(chēng)后一種誘發(fā)是條件的，因?yàn)檎T發(fā)的發(fā)生與動(dòng)作a執(zhí)行前的狀態(tài)s相關(guān)如果存在命題pcon(ck)且ps，則cn的發(fā)生不會(huì)誘發(fā)ck的發(fā)生在規(guī)劃過(guò)程中，如果發(fā)現(xiàn)cn誘發(fā)ck但不希望ck發(fā)生，則有兩種選擇：當(dāng)cn必然誘發(fā)ck時(shí)，可以選擇放棄cn；當(dāng)cn條件誘發(fā)ck時(shí)，可以嘗試抵制ck的發(fā)生抵制組件ck發(fā)生的簡(jiǎn)單方法是使某個(gè)命題p(con(ck)-con(cn)在動(dòng)作a執(zhí)行之前為假，即選擇一個(gè)在

30、s中可應(yīng)用的動(dòng)作a刪除命題p而不阻礙組件cn的發(fā)生我們通常稱(chēng)a這類(lèi)動(dòng)作為抵制動(dòng)作抵制過(guò)程是基于因果鏈接的規(guī)劃方法的重要部分8,9定義3.1中的三種互斥關(guān)系在組件規(guī)劃圖的擴(kuò)展階段計(jì)算，反映規(guī)劃解中動(dòng)作和命題的相互影響基于忽略動(dòng)作刪除效果的假定，ff系統(tǒng)的松弛圖規(guī)劃不需要計(jì)算任何互斥關(guān)系然而正如在本文的第二節(jié)所述，完全忽略這三種互斥關(guān)系將導(dǎo)致“有利動(dòng)作”策略失效，從而引起增強(qiáng)爬山算法的失敗避免這種失敗的一個(gè)方案是考慮動(dòng)作的刪除效果并在規(guī)劃圖構(gòu)造的過(guò)程中計(jì)算上述三種互斥關(guān)系然而，互斥關(guān)系的計(jì)算和檢查需要大量的計(jì)算時(shí)間20，而在提取規(guī)劃解的過(guò)程中進(jìn)行組件抵制的嘗試也可能導(dǎo)致大量的回溯17為了設(shè)計(jì)一個(gè)能

31、夠產(chǎn)生有效的啟發(fā)式信息而且計(jì)算費(fèi)用相對(duì)較低的推理方法，我們對(duì)定義3.1中的三種互斥關(guān)系進(jìn)一步劃分顯然，前兩種互斥關(guān)系在strips和adl規(guī)劃中均存在，我們稱(chēng)為必然互斥，第三種互斥關(guān)系僅在adl規(guī)劃中存在，我們稱(chēng)為條件互斥在strips規(guī)劃問(wèn)題中，松弛圖規(guī)劃雖然完全忽略了必然互斥關(guān)系，但是ff在幾乎所有的規(guī)劃任務(wù)上表現(xiàn)優(yōu)異基于這個(gè)觀察，我們希望新設(shè)計(jì)的計(jì)算松弛規(guī)劃解的方法能夠在strips域上與松弛圖規(guī)劃具有相同的特點(diǎn)因此，我們提出的方法僅考慮誘發(fā)組件型互斥關(guān)系pqrpqe0e1e2facts0 c0 facts1圖 5 狀態(tài)i對(duì)應(yīng)的樸素組件規(guī)劃圖為了計(jì)算誘發(fā)組件型互斥關(guān)系，我們構(gòu)造一個(gè)簡(jiǎn)化的

32、組件規(guī)劃圖樸素組件規(guī)劃圖（nave components planning graph， ncpg）樸素組件規(guī)劃圖是一種不包含任何互斥關(guān)系的組件規(guī)劃圖，其中每個(gè)動(dòng)作都保留刪除效果（圖5顯示了第二節(jié)中規(guī)劃任務(wù)p的初始狀態(tài)對(duì)應(yīng)的樸素組件規(guī)劃圖，其中點(diǎn)劃線(xiàn)指向組件的刪除命題）當(dāng)樸素組件規(guī)劃圖構(gòu)造完畢后，我們使用下面提出的延遲部分推理方法考慮誘發(fā)組件型互斥關(guān)系，計(jì)算松弛規(guī)劃解基于樸素組件規(guī)劃圖的延遲部分推理方法（delayed partly reasoning on a nave components planning graph，dpr-ncpg）與基于松弛規(guī)劃任務(wù)的圖規(guī)劃方法（松弛圖規(guī)劃）主要存在

33、兩點(diǎn)差別：（1）前者基于原始的規(guī)劃任務(wù)，采用簡(jiǎn)化的計(jì)算過(guò)程，而后者基于簡(jiǎn)化的規(guī)劃任務(wù)，采用標(biāo)準(zhǔn)的計(jì)算過(guò)程（2）前者考慮一部分互斥關(guān)系，后者忽略全部互斥關(guān)系下面介紹dpr-ncpg計(jì)算松弛規(guī)劃解的過(guò)程3.3 延遲部分推理延遲部分推理方法是一種與圖規(guī)劃類(lèi)似的回溯式搜索算法，在搜索的過(guò)程中計(jì)算一部分組件互斥關(guān)系延遲部分推理方法計(jì)算的組件互斥關(guān)系通過(guò)“松弛誘發(fā)”和“松弛互斥”概念刻畫(huà)首先提出兩個(gè)限定：（1）在樸素組件規(guī)劃圖上計(jì)算規(guī)劃解的過(guò)程中假定組件所屬于的動(dòng)作的執(zhí)行順序就是組件被選擇的順序；（2）在規(guī)劃求解的過(guò)程中僅考慮在已定的動(dòng)作執(zhí)行順序下存在的誘發(fā)組件互斥關(guān)系定義3.3 在延遲部分推理的求解過(guò)程

34、中，設(shè)cn和ck為第i組件列屬于同一個(gè)動(dòng)作的兩個(gè)組件，稱(chēng)cn松弛誘發(fā)ck，如果con(cn) con(ck)且pcon(ck)滿(mǎn)足下列條件之一：（1）p被i列已經(jīng)選擇的組件添加；（2）p為j列(j i)的目標(biāo)；（3）pcon(cn)；（4）i = 0，并且p出現(xiàn)在第0命題列延遲部分推理方法在選擇一個(gè)組件cn之前檢查該組件與已選擇組件的松弛互斥關(guān)系并進(jìn)行相應(yīng)的處理定義3.4 在延遲部分推理的求解過(guò)程中，設(shè)第i組件列已被選擇的組件序列為sci = ，稱(chēng)組件ck與sci存在松弛互斥關(guān)系，如果組件cn松弛誘發(fā)組件ck，并且ck刪除第i1命題列已被添加的目標(biāo)或者刪除第j（j i）命題列的目標(biāo)松弛互斥關(guān)系

35、與求解過(guò)程相關(guān)，隨著規(guī)劃解的變化而變化它預(yù)測(cè)單個(gè)規(guī)劃解中可能存在的組件誘發(fā)關(guān)系及其消極作用當(dāng)發(fā)現(xiàn)組件ck與sci存在松弛互斥時(shí)，延遲部分推理方法嘗試對(duì)ck進(jìn)行抵制以避免其消極作用抵制的方法為：選擇某個(gè)命題p(con(ck) - con(cn)且p不是（子）目標(biāo)，之后選擇一個(gè)第j（j i）列的組件刪除pfunction pinduce( cn, ck, i )1. for each fact p con( ck )2. if p is not true at facts level i + 13. if p is not a goal at facts level j (j i)4. if p

36、con( cn )5. if i = 0 and p is not at facts level 0 6. return fasle7. return trueprocedure confrontcheck( cn, i )1. confronted = false2. let c = ck | ck and cn belong to the same action a, and con(cn) con(ck) 3. for each ckc4. if pinduce( cn, ck, i )5. if ck deletes a goal g, which is true at facts l

37、evel i + 1 or appears at ji6. confronted = false7. for each fact q con( ck ) con(cn) and !confronted8. for each component cm, s.t., level(cm) =i, such that q del( cm )9. if not deletegoal( cm, i )10. add action a to which cm belongs, into the current relaxed plan11. update the heuristic estimation12

38、. if ( i = 1 )13. add a to the helpful actions set14. confronted = true15. break圖 6 dpr-ncpg方法的兩個(gè)模塊：松弛誘發(fā)判斷和抵制檢查圖6給出dpr-ncgp中實(shí)現(xiàn)定義3.3和3.4以及進(jìn)行抵制處理的算法dpr-ncgp的整體過(guò)程類(lèi)似于圖規(guī)劃的回溯算法dpr-ncgp為第i+1命題列的一個(gè)目標(biāo)命題g尋找支持組件時(shí)，如果g存在于某個(gè)動(dòng)作組件的添加效果，則該組件成為備選組件仍然使用noop優(yōu)先原則和具有最小難度的動(dòng)作優(yōu)先原則為目標(biāo)g在多個(gè)備選組件中選擇一個(gè)支持組件若一個(gè)組件被選定，則這個(gè)組件所來(lái)自的動(dòng)作被加入最

39、終的松弛規(guī)劃解如前所述，我們認(rèn)為規(guī)劃解的多個(gè)動(dòng)作是串行執(zhí)行的，假定動(dòng)作的執(zhí)行順序是它們被選擇的順序因此，當(dāng)?shù)趇組件列的組件cn被選擇以支持第i+1列的目標(biāo)命題g時(shí)，如果某個(gè)命題pcon(cn)被時(shí)間步i已經(jīng)選擇的組件添加，則不再將p作為第i命題列的目標(biāo)在一個(gè)選定的組件cn加入第i組件列已經(jīng)選擇的支持組件序列sci之前，調(diào)用過(guò)程confrontcheck()對(duì)cn進(jìn)行松弛誘發(fā)關(guān)系檢查和處理confrontcheck()過(guò)程逐個(gè)考察與cn來(lái)自同一個(gè)動(dòng)作的每個(gè)組件ck首先調(diào)用函數(shù)pinduce()判斷在當(dāng)前的組件執(zhí)行順序下組件cn是否松弛誘發(fā)組件ck若cn誘發(fā)ck，并且cn和sci存在松弛互斥關(guān)系，

40、則對(duì)ck進(jìn)行抵制：選擇某個(gè)命題p(con(ck) - con(cn)，對(duì)于命題p，選擇一個(gè)刪除p但不刪除時(shí)間步i已經(jīng)實(shí)現(xiàn)目標(biāo)的組件cm，若不存在這樣的cm，則放棄抵制ck若存在這樣的cm，則將cm加入sci，將cm的前提作為第i命題列的子目標(biāo)向前傳遞此過(guò)程的一個(gè)重要步驟為：若cm在時(shí)間步0的組件列，則將cm所屬于的動(dòng)作加入有利動(dòng)作集下面以圖5的樸素組件規(guī)劃圖為例介紹dpr-ncpg方法計(jì)算松弛規(guī)劃解的大致過(guò)程當(dāng)dpr-ncpg為時(shí)間步1的目標(biāo)r選定支持組件e0后，在將e0加入已選擇組件集sc0之前，調(diào)用confrontcheck()對(duì)e0進(jìn)行處理由于組件e1和e0來(lái)自同一個(gè)動(dòng)作a，處理過(guò)程首先

41、考察組件e1組件e1由組件e0松弛誘發(fā)而且e1刪除第0列的目標(biāo)p，因此e1與sc0松弛互斥confrontcheck()算法選擇e2刪除命題q以避免e1的消極作用，將e2加入sc0，同時(shí)將e2所屬于的動(dòng)作a1加入有利動(dòng)作集由于動(dòng)作a0不存在其它需要檢查的組件，confrontcheck()過(guò)程結(jié)束dpr-ncpg將組件e0加入sc0最終，dpr-ncpg計(jì)算的松弛規(guī)劃為：，有利動(dòng)作集合為a1，a0容易看出，增強(qiáng)爬山算法得到由dpr-ncpg反饋的有利動(dòng)作集合后，能夠擴(kuò)展到存在解的狀態(tài)空間，實(shí)現(xiàn)成功求解相比之下，松弛圖規(guī)劃算法無(wú)法發(fā)現(xiàn)有利動(dòng)作a1與松弛圖規(guī)劃相比，dpr-ncpg考慮組件之間的動(dòng)

42、態(tài)互斥關(guān)系，最終獲得的啟發(fā)式函數(shù)所含的信息量更大另一方面，樸素組件規(guī)劃圖的構(gòu)造過(guò)程不需要計(jì)算互斥關(guān)系，延遲部分推理方法僅考慮一部分互斥關(guān)系，因此dpr-ncpg的計(jì)算代價(jià)較低從剪枝策略角度看，松弛誘發(fā)關(guān)系和松弛互斥關(guān)系的判斷隨著松弛規(guī)劃解的不同而變化，能夠預(yù)測(cè)后續(xù)規(guī)劃過(guò)程中松弛誘發(fā)關(guān)系產(chǎn)生的消極影響；抵制處理算法為后續(xù)規(guī)劃保留了處理該類(lèi)消極影響的動(dòng)作因此，基于dpr-ncpg的啟發(fā)式函數(shù)和“有利動(dòng)作”策略都具有更好的性能4 實(shí)驗(yàn)結(jié)果與分析我們以ff的最新版本ff-v23 http:/members.deri.at/joergh/ff.html為基礎(chǔ)，設(shè)計(jì)了基于dpr-ncpg方法的規(guī)劃系統(tǒng)ff

43、c本節(jié)將從規(guī)劃效率和規(guī)劃質(zhì)量（規(guī)劃解長(zhǎng)度）兩個(gè)方面比較ff和ffc實(shí)驗(yàn)在一臺(tái)配置為奔騰4 2.5ghz處理器，256m內(nèi)存，運(yùn)行l(wèi)inux操作系統(tǒng)的機(jī)器上進(jìn)行我們使用國(guó)際通用的adl規(guī)劃域：briefcase world、schedule和elevator，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了初步分析在以下各圖表中，“bf”代表貪婪最好優(yōu)先算法，“ehc”代表增強(qiáng)爬山算法，“sl”是解長(zhǎng)度（solution length）的縮寫(xiě)，“ss”代表訪(fǎng)問(wèn)的狀態(tài)數(shù)目，“tm”代表花費(fèi)的總時(shí)間，“us”代表無(wú)解表 1 briefcase world域?qū)嶒?yàn)對(duì)比f(wàn)fffcproblemslsstm(s)slsstm(s)brf

44、513740.015210.15brf10334350.62422010.31brf154712387.66634373.6brf2059197689.858189566.72brf25793600492.978854990.62brf26812889428.9190570108.74brf27852958457.6697756160brf28904130754.211001243347.5brf298651961160.41051558417.66brf309543491085.41202412723.914.1 briefcase world域briefcase world域是一個(gè)經(jīng)典的a

45、dl規(guī)劃域該域使用一個(gè)公文包將物品從其初始地運(yùn)送到其目的地物品可以放入（put-in）公文包中也可以從公文包中取出（take-out）當(dāng)使用move動(dòng)作移動(dòng)公文包時(shí)，放于公文包內(nèi)的物品伴隨著公文包移動(dòng)（條件效果）在briefcase world域進(jìn)行規(guī)劃的難點(diǎn)在于處理move動(dòng)作的條件效果并判斷其引發(fā)的消極作用，規(guī)劃算法需要在合適的時(shí)間使用take-out動(dòng)作避免條件效果的消極作用以該域的一個(gè)簡(jiǎn)單問(wèn)題為例初始狀態(tài)為物品o1和o2在公文包中并且公文包在l地，物品o1的目的地為地點(diǎn)l，物品o2的目的地為地點(diǎn)l從直觀上看，o1已經(jīng)處于目的地，不需要任何處理；僅需要將公文包從l地移動(dòng)到l地來(lái)運(yùn)送o2然

46、而，在移動(dòng)公文包之前，如果未將o1從公文包中取出，則o1將隨著公文包被運(yùn)送到l地（move動(dòng)作的條件效果）如果規(guī)劃算法希望在運(yùn)送o2時(shí)不影響o1的位置，則必須在移動(dòng)公文包之前采用一個(gè)take-out動(dòng)作將o1從公文包中取出在該領(lǐng)域的大多數(shù)問(wèn)題實(shí)例上，ff系統(tǒng)的rgp模塊無(wú)法計(jì)算條件效果產(chǎn)生的消極影響以及避免該消極影響的動(dòng)作，產(chǎn)生的“有利動(dòng)作”策略總是丟棄take-out動(dòng)作，從而引起增強(qiáng)爬山算法的失敗，隨后的求解過(guò)程主要由貪婪最好優(yōu)先算法完成，耗費(fèi)時(shí)間較長(zhǎng)相對(duì)而言，ffc系統(tǒng)的dpr-ncgp引導(dǎo)增強(qiáng)爬山算法在所有的測(cè)試問(wèn)題上求解成功，表現(xiàn)出較好的性能本文使用ff系統(tǒng)提供的問(wèn)題生成器 http

47、:/members.deri.at/joergh/ff-domains.html生成隨機(jī)的測(cè)試問(wèn)題表1顯示了ff與ffc的對(duì)比實(shí)驗(yàn)結(jié)果，從中可以看出，在小規(guī)模問(wèn)題上ffc的效率優(yōu)勢(shì)不明顯，但是隨著問(wèn)題規(guī)模的增加，ffc的效率比之ff具有成倍的提升4.2 schedule域schedule域也是一個(gè)由adl語(yǔ)言描述的規(guī)劃域，其中的動(dòng)作包含條件效果該域建模一類(lèi)加工器件的生產(chǎn)調(diào)度問(wèn)題，即，使用多個(gè)車(chē)床加工一定數(shù)量的器件，可以采用拋光（polish），打孔（punch hole），碾壓（roll）和涂漆（painting）等操作對(duì)器件進(jìn)行處理schedule域是一個(gè)較難處理的規(guī)劃域13本文采用的測(cè)試問(wèn)

48、題取自aips2000規(guī)劃競(jìng)賽10在多數(shù)問(wèn)題的求解過(guò)程中，啟發(fā)式函數(shù)涉及的松弛規(guī)劃任務(wù)包含大量的并行動(dòng)作，松弛規(guī)劃圖一般只需要擴(kuò)展三個(gè)時(shí)間步，因此，ff系統(tǒng)的啟發(fā)函數(shù)對(duì)增強(qiáng)爬山算法的引導(dǎo)能力不強(qiáng)，而“有利動(dòng)作”策略成為ff在此域高效求解的主要因素（僅有約2%的可用動(dòng)作被標(biāo)記為有利動(dòng)作）4在ffc系統(tǒng)中，延遲部分推理方法由于考慮一部分組件誘發(fā)關(guān)系提高了啟發(fā)函數(shù)和剪枝策略的性能圖7和圖8分別顯示了ff和ffc在規(guī)劃效率和規(guī)劃質(zhì)量方面的對(duì)比結(jié)果表明，無(wú)論在rgp的引導(dǎo)下還是在dpr-ncpg的引導(dǎo)下，增強(qiáng)爬山搜索在幾乎所有的問(wèn)題上都能夠成功但是如圖7和圖8所示，在大多數(shù)問(wèn)題中，增強(qiáng)爬山算法在dpr-

49、ncpg引導(dǎo)下耗費(fèi)的時(shí)間較少，而且可以獲得較好的規(guī)劃解圖 7 schedule域規(guī)劃效率對(duì)比（時(shí)間軸為對(duì)數(shù)坐標(biāo)）圖 8 schedule域規(guī)劃質(zhì)量對(duì)比4.3 miconic-adl域miconic-adl域建模一類(lèi)使用電梯運(yùn)送乘客的問(wèn)題，其中的動(dòng)作包含復(fù)雜的前提和條件效果運(yùn)送乘客時(shí)，需要考慮多種約束，例如，必須首先為vip乘客服務(wù)，在運(yùn)送某些乘客的過(guò)程中電梯不能停止，某些乘客需要服務(wù)員陪同等等當(dāng)電梯停在某一樓層時(shí)（stop動(dòng)作），所有目的地為該樓層的乘客走出電梯，所有在該樓層等候的乘客進(jìn)入電梯（條件效果）顯然，電梯移動(dòng)時(shí)，其中的乘客將隨著電梯移動(dòng)，類(lèi)似于briefcase world域中物品隨

50、公文包移動(dòng)的現(xiàn)象，但是該域與briefcase world域的差別在于電梯中的乘客在電梯停止時(shí)自動(dòng)地走出電梯，規(guī)劃算法不需要采用某個(gè)動(dòng)作來(lái)達(dá)到這個(gè)結(jié)果，因此基于rgp的“有利動(dòng)作”策略較少引發(fā)增強(qiáng)爬山算法的失敗在miconic-adl域，我們使用aips2000的測(cè)試問(wèn)題集實(shí)驗(yàn)數(shù)據(jù)見(jiàn)圖9圖中標(biāo)有“ehc”的列標(biāo)記增強(qiáng)爬山算法是否搜索成功，“t”代表搜索成功，“f”代表搜索失敗在ff系統(tǒng)中，由rgp引導(dǎo)的增強(qiáng)爬山算法在該域的一些問(wèn)題上求解失敗實(shí)驗(yàn)結(jié)果表明，dpr-ncpg和rgp對(duì)增強(qiáng)爬山算法的影響不同從結(jié)果可以看出，在一些問(wèn)題上（如，問(wèn)題f12-1和f14-2）增強(qiáng)爬山算法在rgp引導(dǎo)下失敗，

51、在dpr-ncpg引導(dǎo)下取得成功；當(dāng)增強(qiáng)爬山算法在rgp引導(dǎo)下搜索成功時(shí)，在dpr-ncpg引導(dǎo)下仍然搜索成功表2 miconic-adl域?qū)嶒?yàn)對(duì)比f(wàn)fffcproblemslsstmehcslsstmehcf10-0341037613.43f355941.41ff10-133920.62t321340.78tf10-2ususf10-3341378217.19f3455337.82ff10-4351030.63t31690.62tf11-034710.62t33680.93tf11-1371320.93t381380.78tf11-233680.63t32680.78tf11-3328482

52、.03f325351.41ff11-4361480.94t35980.78tf12-0431040.94t431091.1tf12-13913504.21f431761.25tf12-242860.94t42861.1tf12-3385792.03f4038429.37ff12-439770.94t39771.09tf13-041971.1t421061.25tf13-1391331.26t391301.41tf13-2385732.18f406232.35ff13-3481601.41t461151.25tf13-438670312.97f402385247.03ff14-0426332.9

53、7f426113.12ff14-1401551.72t483252.34tf14-2436833.12f471631.56tf14-3491781.71t461521.56tf14-4471121.41t481131.56t5 結(jié)語(yǔ)ff作為一個(gè)啟發(fā)式搜索方法應(yīng)用于規(guī)劃問(wèn)題的典型系統(tǒng)，自從出現(xiàn)以來(lái)，一直受到研究者的關(guān)注hoffmann對(duì)松弛圖規(guī)劃和增強(qiáng)爬山算法結(jié)合的方法從實(shí)驗(yàn)角度和理論角度給予了深入的分析ff最突出的特點(diǎn)是使用松弛圖規(guī)劃產(chǎn)生的規(guī)劃解的長(zhǎng)度作為估計(jì)值，使用“有利動(dòng)作”策略裁剪搜索空間其它的研究者從這兩個(gè)方面借鑒ff的思想并提出多種改進(jìn)的方法如，helmert針對(duì)松弛圖規(guī)劃忽略動(dòng)作刪

54、除效果時(shí)估計(jì)偏差過(guò)大的不足，提出了基于因果圖分析（casual graph analysis）的啟發(fā)式函數(shù)和稱(chēng)為“有利轉(zhuǎn)移”（helpful transitions）的剪枝策略6，設(shè)計(jì)的fast downward規(guī)劃系統(tǒng)在strips規(guī)劃域的性能優(yōu)于ff但是，fast downward在schedule域的效率明顯低于ff，其中的原因有待進(jìn)一步研究此外，“有利轉(zhuǎn)移”策略通常存在過(guò)度剪枝的情況；vidal提出的補(bǔ)救動(dòng)作（rescue actions）和前瞻（look ahead）方法9，既彌補(bǔ)了松弛圖規(guī)劃提供不完全有利動(dòng)作的不足又利用了松弛規(guī)劃解的信息，提高了規(guī)劃求解效率然而，該方法存在規(guī)劃解質(zhì)量較低的不足；姜云飛等人從提高啟發(fā)函數(shù)的信息量的角度，通過(guò)計(jì)算經(jīng)典的組件規(guī)劃圖，提高ff識(shí)別僵局（dead end）的能力21，然而，構(gòu)造經(jīng)典組件規(guī)劃圖需要大量的計(jì)算代價(jià)而且無(wú)法預(yù)測(cè)所有的死點(diǎn)，此外，有利動(dòng)作的不完全問(wèn)題仍然存在據(jù)我們所知，研究者尚未發(fā)現(xiàn)ff系統(tǒng)中基于松弛圖規(guī)劃的“有利動(dòng)作”策略失效的主要原因本文的研究指出，在ff使用分枝擴(kuò)展法處理?xiàng)l件效果的同時(shí)，松弛圖規(guī)劃完全忽略了分枝擴(kuò)展法所帶來(lái)的復(fù)雜性，在必須處理誘發(fā)組件互斥關(guān)系的規(guī)劃任務(wù)上無(wú)法發(fā)現(xiàn)使增強(qiáng)爬山算法擴(kuò)展到解空間的有利動(dòng)作，進(jìn)而喪失了提供有效引導(dǎo)信息的作用，導(dǎo)致ff的效率急劇降低針