蔡敦波, 徐 勝, 趙彤洲

(1.武漢工程大學(xué)智能機(jī)器人湖北省重點實驗室， 湖北 武漢430205；2．吉林大學(xué)符號計算與知識工程教育部重點實驗室， 吉林 長春130012；3．華中科技大學(xué)自動化學(xué)院，湖北 武漢430074)/

0 引 言

“問題的結(jié)構(gòu)”是人工智能研究者面對復(fù)雜問題時希望發(fā)現(xiàn)并利用的一類信息.這些信息通常有助于研究者設(shè)計更高效的問題求解方法.如，在命題可滿足(SAT)研究領(lǐng)域，研究者發(fā)現(xiàn)了Backbone和Backdoor這兩種問題結(jié)構(gòu)信息[1]并設(shè)計了由該類信息引導(dǎo)的SAT求解算法[2]；最近，北京大學(xué)蘇開樂教授和蔡少偉博士等人利用命題變量的鄰域信息(Neighborhood)，提出了Configuration Checking(CC)策略，并開發(fā)了基于CC策略的一系列高效算法[3-5]，在國際上將SAT求解器的效率推到了更高的層次.

智能規(guī)劃研究者近年來發(fā)現(xiàn)了對應(yīng)于SAT中“Backbone”的問題結(jié)構(gòu)信息：界標(biāo)命題(Landmark Facts)和界標(biāo)動作(Landmark Actions)[6-7]，統(tǒng)稱為界標(biāo)知識(Landmark).Landmark不僅包含一系列命題和動作，而且包含它們之間的先后順序，它對于尋找“動作序列”的智能規(guī)劃問題具有重要的研究價值，激發(fā)了研究者的深入研究.在基于搜索思想的規(guī)劃方法方面，Hoffmann等人首先利用Landmark進(jìn)行規(guī)劃問題的子目標(biāo)分解，用以提高規(guī)劃算法的求解效率[7].Helmert等人利用Landmark設(shè)計STRIPS規(guī)劃問題的啟發(fā)函數(shù)，開發(fā)了相應(yīng)的規(guī)劃系統(tǒng)LAMA[8]，獲得了2008年“智能規(guī)劃系統(tǒng)國際競賽”(International Planning Competition，IPC)的冠軍，隨后，LAMA的改進(jìn)版本LAMA-2011又獲得了2011年IPC競賽的冠軍.在基于SAT技術(shù)的規(guī)劃方法方面，將Landmark編碼為子句形式的約束，加速沖突信息的傳播，在較大規(guī)模的問題實例上表現(xiàn)出了效率優(yōu)勢[9].隨著Landmark計算方法的不斷涌現(xiàn)[10]，它在“動作代價不等的規(guī)劃”、“時態(tài)規(guī)劃”和“Conformant規(guī)劃”等建模能力強(qiáng)于STRIPS規(guī)劃的問題上產(chǎn)生了研究成果[11-13]，涌現(xiàn)了一批求解效率更高的規(guī)劃系統(tǒng)，值得國內(nèi)外學(xué)者繼續(xù)深入地研究與應(yīng)用.

首先介紹Landmark的相關(guān)概念及其計算方法，之后分別介紹此類信息在STRIPS規(guī)劃、動作代價不等的規(guī)劃和時態(tài)規(guī)劃上的應(yīng)用研究成果，最后進(jìn)行總結(jié)與展望.

1 Landmark及其計算方法

首先介紹智能規(guī)劃基本概念，之后介紹Landmark及其順序的概念，最后介紹Landmark的基本計算方法.

1.1 智能規(guī)劃的基本概念

本文將依次介紹STRIPS規(guī)劃、動作代價不等的規(guī)劃和時態(tài)規(guī)劃的基本概念.

定義1.規(guī)劃任務(wù)(Planning Task)為四元組Π=，其中，V是命題變量的有限集，O是動作的有限集，I是V的子集、表示初始狀態(tài)，G是V的子集、表示目標(biāo)條件.O中每個動作o為三元組，其中pre(o),add(o),del(o)均為V的子集，分別表示動作o的前提、添加效果和刪除效果，cost(o)為實數(shù)，表示o的代價.

狀態(tài)s為V的子集，因此，狀態(tài)空間為S={s|s?V}.對于給定的s和o，如果動作o滿足pre(o)?s則稱o在s上“可用”.

定義2.如果o在s上可用，則o在s上的執(zhí)行結(jié)果為s/del(o)∪add(o)，記為o(s).

動作序列π的形式為，該序列在動作s上的執(zhí)行結(jié)果為on(…o1(s)…)，記為π(s).

定義3.對于規(guī)劃任務(wù)Π=，如果動作序列π滿足π(I)?G則稱π為Π的規(guī)劃解(Plan).

為了方便論述后續(xù)內(nèi)容，定義“相對于狀態(tài)的規(guī)劃解”.

定義4.對于規(guī)劃任務(wù)Π=，狀態(tài)s?V，如果動作序列π滿足π(s)?G則稱π為“s的規(guī)劃解”(s-plan)，I-plan即為Π的規(guī)劃解.

定義6. 意規(guī)劃問題(Satisfactory Planning)要求對于給定的規(guī)劃任務(wù)Π，找到一個I-plan，或者證明不存在I-plan.

定義7. 最優(yōu)規(guī)劃問題(Optimal Planning)要求為規(guī)劃任務(wù)Π找到代價最小的I-plan，或者證明I-plan不存在.

如果在規(guī)劃任務(wù)中，動作的代價都為1，則稱該類規(guī)劃問題為STRIPS規(guī)劃問題，否則，稱之為“動作代價不等的規(guī)劃問題”.

1.2 Landmark與Landmark順序的基本定義

Landmark由“Landmark命題”和“Landmark動作”組成[6-7].

定義8. 在Π=中，若命題f∈V在每個I-plan執(zhí)行過程中的某個時刻上為真，則稱f為“Landmark命題”；如果動作o∈O存在于每個I-plan中，則稱o為“Landmark動作”.

根據(jù)定義，規(guī)劃任務(wù)中I和G中的命題都是Landmark命題.此外，還存在其他的Landmark命題.

例1.設(shè)規(guī)劃任務(wù)Π=僅有兩個I-plan：π1=，π2=，則add(o1)中的命題都是Landmark命題，因為這些命題在兩個規(guī)劃執(zhí)行過程中都有成立的時刻.o1為Landmark動作.此外，假如存在f∈(add(o2)∩add(o3))則f也是Landmark命題.

除了單個命題(動作)符合Landmark的含義外，命題集(動作集)也符合Landmark的含義，這些集稱之為“析取型Landmark”(Disjunctive Landmark)[7].

定義9.在Π=中，如果命題集V′?V在每個I-plan執(zhí)行過程中的某個時刻都使V′中的某個命題為真，則稱V′為“析取型Landmark”命題集；如果每個I-plan均包含動作集O′?O中的至少一個動作，則稱O′為“析取型Landmark”動作集.

Landmark命題和Landmark動作之間存在著一些順序關(guān)系.下面首先介紹幾個基本概念，之后介紹“Landmark命題”之間的三種順序關(guān)系[8].

定義10. 對于Π=，i∈{0,…,n}，給定動作序列π=，如果命題則f∈((I))稱f在π的第i步為真；如果f在π的第i- 1步為假，但“在π第i步為真”，則稱“f在π的第i步被添加”；如果對于j≤i-1：f在π的第j步均為假”，但f在第i步為真，則稱“f在π的第i步被首次添加”.

定義11. 設(shè)f和f′為Π=中兩個命題，稱f與f′具有“自然順序”(Natural Ordering)，記為f→f′，當(dāng)且僅當(dāng)：對于每個在I上“可用”的動作序列π，當(dāng)“f′在π的第i步為真”時均有“f在π的某個第j(j

根據(jù)定義10，若兩個命題具有“必然順序”或者“首次必然順序”，則它們具有“自然順序”；如果兩個命題具有“必然順序”，則它們具有“首次必然順序”.但反過來則不然，因此，“必然順序”是最嚴(yán)格的順序.此外，對于Landmark順序的理解，應(yīng)避免將其理解為數(shù)學(xué)中的“關(guān)系”，主要原因在于Landmark順序不具有傳遞性.

1.3 Landmark的計算方法

Landmark命題的計算問題為：給定規(guī)劃任務(wù)Π=，判定f∈V是否為“Landmark命題”.Porteous等人證明了該問題為PSPACE-hard難題[6-7].因此，計算Landmark命題的實用算法均為近似算法.總體上，計算Landmark的方法主要有兩種思想，一種是根據(jù)已知的Landmark通過逆向分析發(fā)現(xiàn)新的Landmark；另一種是基于反駁的方法：將某個命題(動作)從規(guī)劃任務(wù)中暫時移除，如果該規(guī)劃任務(wù)無解，則該命題(動作)必然是Landmark.下面分別介紹計算Landmark命題和Landmark動作的基本方法.

1.3.1 Landmark命題的計算方法 Porteous等人最早提出了通過構(gòu)建“松弛規(guī)劃圖”(Relaxed Planning Graph，RPG)和“Landmark生成樹”(Landmark Generation Tree，LGT)來計算Landmark命題的方法[6].針對具體的規(guī)劃任務(wù)Π=，該方法首先構(gòu)造松弛規(guī)劃圖，直到目標(biāo)集G中的命題均在該圖中出現(xiàn)，然后通過LGT記錄得到“候選Landmark”.LGT中的節(jié)點為“候選Landmark命題”，節(jié)點之間有向弧表示它們的“首次必然順序”關(guān)系.“候選Landmark命題”通過如下的命題進(jìn)行判定，該判定過程能由規(guī)劃圖算法在以動作和命題數(shù)量為參數(shù)的多項式時間內(nèi)完成[6].稱此方法為LMRPG，它本質(zhì)上根據(jù)命題1計算Landmark命題.

命題1[6]. 對于規(guī)劃任務(wù)Π，對于f∈V，定義松弛規(guī)劃問題Πf=，其中Of={|o∈O,f?add(o)}；如果Πf無解，則f為Landmark命題.

但是，LMRPG在某一層考察的動作集可能是全部可能動作的某個子集，因而該算法可能計算出一部分錯誤的Landmark順序.Porteous等人隨后提出了“首次必然順序”的一種正確計算方法[14].該方法的主要思想是：為了收集所有在命題f′之前可能執(zhí)行的動作，將任務(wù)中以f′為添加效果的動作全部移除，之后構(gòu)造規(guī)劃圖G直到G不發(fā)生變化.顯然，G的最后一層包含所有在f′之前能成立的命題，將該集記為pb(f′)；在pb(f′)上“可用”的動作集pba(f)={o|pre(o)∈pb(f′),o∈O}必然為在f′之前實際上“可用”的動作的超集.因此，pba(f′)中動作前提的交集為正確的Landmark命題，它們與f′之間的“首次必然順序”也正確.

為了發(fā)現(xiàn)更多的Landmark命題，Richter等人根據(jù)“域轉(zhuǎn)移圖”(Domain Transition Graph)的結(jié)構(gòu)特征，提出了一種能夠計算更多Landmark的方法[8].其主要思想為：對于變量v的域轉(zhuǎn)移圖DTGv，如果從v在初始狀態(tài)中的取值d0到Landmark命題v=d的所有路徑都經(jīng)過d′，則v=d′是Landmark命題.為進(jìn)行此判斷，該方法在DTGv中依次去除d′，之后判斷從d0到d′的連通性，如果不連通，則判定v=d′為Landmark命題，并且v=d′與v=d存在“自然順序”.

2 Landmark在STRIPS規(guī)劃上的應(yīng)用

由于Landmark及其順序刻畫了規(guī)劃問題實例的結(jié)構(gòu)，研究者最初利用Landmark命題順序?qū)σ?guī)劃任務(wù)的目標(biāo)進(jìn)行分解來降低規(guī)劃問題的求解難度；近來的研究主要集中于利用Landmark設(shè)計啟發(fā)函數(shù)；本文作者探索了在基于SAT的規(guī)劃框架下使用Landmark的方法.

2.1 基于Landmark的任務(wù)分解

Hoffmann等人研究了基于Landmark將規(guī)劃任務(wù)分解為規(guī)模較小的規(guī)劃任務(wù)的方法[7]，用該方法引導(dǎo)FF規(guī)劃系統(tǒng)[16]和LPG規(guī)劃系統(tǒng)進(jìn)行規(guī)劃求解.在測試的Blocksworld域、Grid域、Logistics域和Rovers域?qū)崿F(xiàn)了較大的效率提升，但是在FreeCell域和Depots域的性能相比FF和LPG均有下降[7].

該分解方法的主要思想為：用LGT存儲Landmark及其順序，不斷迭代地調(diào)用“底層規(guī)劃器”(FF或者LPG)來實現(xiàn)LGT的葉子節(jié)點，直到LGT為空.在每次迭代中，首先將LGT中葉子節(jié)點對應(yīng)的命題以析取目標(biāo)(Disjunctive Goal)的形式輸入“底層規(guī)劃器”，將“底層規(guī)劃器”輸出的規(guī)劃與上一次迭代產(chǎn)生的規(guī)劃拼接，根據(jù)拼接后實現(xiàn)的命題集s′去除LGT的葉子節(jié)點，并將s′作為下一次迭代的初始狀態(tài).

在該方法中，由于每次求解的問題相當(dāng)于僅包含一個目標(biāo)命題的規(guī)劃問題，而且上一次迭代的初始狀態(tài)通常需要較少的動作即可實現(xiàn)LGT的葉子節(jié)點，因此“底層規(guī)劃器”每次求解的規(guī)劃任務(wù)較小，求解的速度較快.使用該方法后，出現(xiàn)整體性能下降的原因主要有兩方面：1)LGT中存在不正確的Landmark順序；2)對于結(jié)構(gòu)復(fù)雜的問題，如FreeCell域，Landmark不足以反映出問題的全部結(jié)構(gòu)信息.

2.2 基于Landmark計數(shù)的啟發(fā)函數(shù)

Richter和Helmert等人使用從狀態(tài)s到目標(biāo)G的過程中所需要實現(xiàn)的Landmark的數(shù)目估計狀態(tài)s與目標(biāo)的距離[8]，該啟發(fā)函數(shù)通常記為hLM.具體而言，對于規(guī)劃任務(wù)Π中的狀態(tài)s，有hLM(s,π)=|L(s,π)|=

|(LAccepted(s,π))∪ReqAgain(s,π)|

(1)

其中π為從初始狀態(tài)I到當(dāng)前狀態(tài)s的動作序列，L為該規(guī)劃任務(wù)的Landmark命題集.Accepted(s,π)為從I到s過程中“已接受”的Landmark命題集，ReqAgain(s,π)為從s向目標(biāo)前進(jìn)過程中“仍需要”的Landmark命題集.

啟發(fā)函數(shù)hLM將L(s,π)中包含的Landmark命題的數(shù)目作為狀態(tài)s的目標(biāo)距離估計.與以往的啟發(fā)函數(shù)根據(jù)“動作數(shù)目”估計目標(biāo)距離的思想不同，hLM首次使用了“命題數(shù)目”來估計目標(biāo)距離.在設(shè)計思路上，hLM不僅考慮了“未接受”的Landmark命題，而且考慮了“已接受”但“還需要”的Landmark命題，包含了較豐富的信息量.在實際性能方面，以hLM為關(guān)鍵技術(shù)的規(guī)劃系統(tǒng)LAMA獲得了2008年IPC競賽“滿意規(guī)劃”競賽組的冠軍.hLM的成功引起了智能規(guī)劃領(lǐng)域研究者的廣泛關(guān)注，隨之出現(xiàn)了多個根據(jù)Landmark提高啟發(fā)函數(shù)精度的新方法.

2.3 基于Landmark順序的啟發(fā)函數(shù)

在分析Landmark及其順序與規(guī)劃問題結(jié)構(gòu)的基礎(chǔ)上，改進(jìn)了Helmert和Geffner等人提出的“上下文信息增強(qiáng)的和代價啟發(fā)函數(shù)”(Context-enhanced Additive Heuristic)hcea，提出了考慮動作前提“優(yōu)先順序約束”(Precedence Constraints)和上下文信息的啟發(fā)函數(shù)hpcc[12].

啟發(fā)函數(shù)hcea是建立在“因果圖”(Causal Graph)和“域轉(zhuǎn)移圖”(Domain Transition Graph)上的啟發(fā)函數(shù)[12].hcea在評估狀態(tài)的目標(biāo)距離過程中，將動作前提中的一個前提假定為“核心前提”(Pivot Condition).動作的代價估計由“核心前提”的代價估計和其他前提相對于“核心前提”的代價估計組成.可見，對于任一動作，hcea假定“核心前提”優(yōu)先于其他前提成立、其他前提之間無優(yōu)先順序.顯然，hcea的假定與實際不符.在實際問題中，一個動作可以包含多個前提，其中每兩個前提之間都可能存在優(yōu)先順序.但是，“如何確定這些優(yōu)先順序”是一個難題.

根據(jù)Landmark命題的順序以及對Landmark命題的支持動作的分析，探索了“確定動作前提優(yōu)先順序”的方法.如方法中的一個規(guī)則為：對于動作o的兩個前提p和q，如果q和p之間不存在Landmark順序，但是，存在Landmark順序f→gnq，并且添加f的所有動作都使p為假，則“先計算實現(xiàn)q的代價再根據(jù)該計算過程結(jié)束時變量的取值情況計算p的代價”.根據(jù)此類規(guī)則，我們?yōu)槊總€動作前提的代價評估確定計算順序，定義了啟發(fā)函數(shù)hpcc.實驗結(jié)果表明，在許多問題上由hpcc引導(dǎo)的搜索算法的求解效率明顯優(yōu)于hcea.

2.4 基于Landmark順序改進(jìn)SatPlan

探索了Landmark在基于SAT的規(guī)劃方法中的應(yīng)用.將Landmark命題和Landmark順序轉(zhuǎn)化為子句的形式，稱這些子句為“Landmark子句”.分析并證明了“Landmark子句”不能全部由常用的預(yù)處理推理過程，如“單元傳播”(Unit Propagation)、“二元?dú)w結(jié)”(Binary Resolution)、或者“超歸結(jié)”(Hyper Resolution)推導(dǎo)出，說明了“Landmark子句”相對于常用的預(yù)處理過程在邏輯上“不是”冗余的子句，進(jìn)而表明了“Landmark子句”對SAT求解器的有用性[9].根據(jù)Landmark命題及其順序生成“Landmark子句”的方法見文獻(xiàn)[9].如，其中的一條規(guī)則為：若Landmark命題p和q存在順序p→q，則對于每個時間步i∈{1...k}生成子句：qi∨pi-1∨…∨p1.

“Landmark子句”對SAT求解算法的主要影響包括以下兩點：1)相對于其他命題，Landmark命題受到的約束較多，在變量選擇過程中或許被更早選擇；2)由于“Landmark子句”的加入，約束傳播的深度增加，使求解器在約束傳播過程中發(fā)現(xiàn)沖突的頻率增加，進(jìn)而減少進(jìn)入無用搜索區(qū)域的次數(shù).我們在SatPlan、MiniSat和LAMA等推理工具的基礎(chǔ)上，實現(xiàn)了使用Landmark子句的規(guī)劃系統(tǒng)SatPlanLM.實驗結(jié)果表明，SatPlanLM在Blocks域、OpenStacks域、Pipesworld-notankage域、Pipesworld-tankage域和TPP域的困難問題上，相對SatPlan有成倍的效率提高.

3 Landmark在動作代價不等規(guī)劃上的應(yīng)用

針對動作代價不等的規(guī)劃問題，Karpas等人首先在2009年的“人工智能國際聯(lián)合大會”(IJCAI)上發(fā)表了使用Landmark設(shè)計可納啟發(fā)函數(shù)(Admissible Heuristic Function)的工作[11].他們將動作a的代價“劃分”到a能添加的Landmark命題上，使用類似LAMA的方法記錄從當(dāng)前狀態(tài)s到目標(biāo)的路徑上所需要成立的Landmark命題，定義了如下的啟發(fā)函數(shù)：

hL(s,π)=cost(L(s,π))=∑p∈L(s,π)cost(p)

(2)

將動作代價“劃分”給Landmark命題的思想如下：設(shè)動作a的代價為cost(a)，記Landmark命題p的代價為cost(p)，用cost(a,p)表示a“劃分”給p的代價；Landmark命題的代價通過滿足如下約束條件的動作代價劃分得出：

(3)

(4)

在hLA提出之后，出現(xiàn)了許多基于Landmark設(shè)計可納啟發(fā)函數(shù)的工作.Helmert等人提出了結(jié)合圖論中“切”概念和Landmark的啟發(fā)函數(shù)hLM-cut[17-18]，Helmert和Haslum等人提出了結(jié)合圖論中“碰集”概念和Landmark的啟發(fā)函數(shù).這些工作極大縮小了當(dāng)前的啟發(fā)函數(shù)與理想的啟發(fā)函數(shù)h+的差距，Bonet等人在總結(jié)可納啟發(fā)函數(shù)相對誤差時指出：未利用Landmark的可納啟發(fā)函數(shù)hmax和additivehmax相對h+的誤差分別為68.5%和25.2%，而結(jié)合了Landmark的可納啟發(fā)函數(shù)hLA和hLM-cut相對h+的誤差分別提高到9.5%和2.5%.可見，Landmark對于提高可納啟發(fā)函數(shù)信息量的重要作用.

4 Landmark在時態(tài)規(guī)劃上的應(yīng)用

在時態(tài)規(guī)劃問題上，探索了使用Landmark設(shè)計啟發(fā)函數(shù)的方法[12]，通過擴(kuò)展STRIPS規(guī)劃上的啟發(fā)函數(shù)hpcc，定義了適用于時態(tài)規(guī)劃的啟發(fā)函數(shù)htpcc.該函數(shù)在估算動作前提的實現(xiàn)代價過程中使用Landmark順序預(yù)測動作前提的合理實現(xiàn)順序.htpcc的計算不僅涉及預(yù)測布爾變量的合理順序，而且需要預(yù)測布爾變量和數(shù)值變量的合理實現(xiàn)順序.使用htpcc擴(kuò)展了時態(tài)規(guī)劃系統(tǒng)Temporal FastDownward(TFD)，實現(xiàn)了“LMTD”的時態(tài)規(guī)劃系統(tǒng).在IPC競賽的時態(tài)規(guī)劃標(biāo)準(zhǔn)測試用例上比較了LMTD和TFD的性能，結(jié)果表明LMTD比TFD能多求解11個問題實例[19].

5 總結(jié)與展望

國內(nèi)研究者已經(jīng)重視了對界標(biāo)知識的研究，取得了一些成果.如，北京大學(xué)金芝教授指導(dǎo)的研究組開發(fā)了計算界標(biāo)命題順序的新方法[20]，中山大學(xué)姜云飛教授指導(dǎo)的課題組提出了基于目標(biāo)順序設(shè)計信息量較大啟發(fā)函數(shù)的新方法[21].

介紹了界標(biāo)知識的基本概念與成果.然而，隨著界標(biāo)知識的相關(guān)概念與方法的發(fā)展，將能對規(guī)劃問題進(jìn)行更豐富的刻畫，從而激發(fā)更多的應(yīng)視角.如，界標(biāo)命題間在時態(tài)上的距離可用于設(shè)計時態(tài)規(guī)劃問題上的啟發(fā)函數(shù)；界標(biāo)動作的順序結(jié)構(gòu)可在基于動作序列空間的規(guī)劃方法上用于構(gòu)造初始節(jié)點、引導(dǎo)相鄰節(jié)點的選擇；界標(biāo)知識在機(jī)器人規(guī)劃[22-23]中的應(yīng)用。目前，還未發(fā)現(xiàn)此類方面的工作.

鑒于界標(biāo)知識在“STRIPS規(guī)劃”、“動作代價不等的規(guī)劃”和“時態(tài)規(guī)劃”上的研究成果，隨著界標(biāo)知識計算方法的發(fā)展、應(yīng)用領(lǐng)域和應(yīng)用角度不斷擴(kuò)展，其應(yīng)用將取得更多、更大的成功.

致 謝

衷心感謝國家自然科學(xué)基金委的資助！

參考文獻(xiàn):

[1] Kilby P， Slaney J， Thiébaux S， et al. Backbones and backdoors in satisfiability[C]//Proceedings of the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference. Pittsburgh， Pennsylvania， USA：AAAI，2005(5)： 1368-1373.

[2] Zhang W.Configuration landscape analysis and backbone guided local search：Part I：Satisfiability and maximum satisfiability[J]. Artificial Intelligence， 2004， 158(1)： 1-26.

[3] Cai S， Su K， Chen Q. Ewls： A new local search for minimum vertex cover[C]//Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence. Atlanta， Georgia， USA ：AAAI，2010： 45-50.

[4] Cai S， Su K， Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover[J]. Artificial Intelligence， 2011， 175(9)： 1672-1696.

[5] Cai S， Su K. Configuration checking with aspiration in local search for SAT[C]// Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Toronto， Ontario， Canada ：AAAI，2012：434-440.

[6] Porteous J， Sebastia L， Hoffmann J. On the extraction， ordering， and usage of landmarks in planning[C]//Proceedings of 6th European Conference on Planning. Toledo， Spain：Springer-Verlag. 2001：109-120.

[7] Hoffmann J， Porteous J， Sebastia L. Ordered landmarks in planning[J]. Journal of Artificial Intelligence Research， 2004(22)： 215-278.

[8] Richter S， Helmert M， Westphal M. Landmarks revisited[C]//Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence. Chicago， Illinois， USA：AAAI， 2008(8)： 975-982.

[9] Cai D， Yin M. On the utility of landmarks in SAT based planning[J]. Knowledge-Based Systems， 2012(36)：146-154.

[10] Bonet B， Castillo J. A complete algorithm for generating landmarks[C]//Proceedings of 21st International Conference on Automated Planning and Scheduling. Freiburg， Germany ：AAAI，2011：315-318.

[11] Karpas E， Domshlak C. Cost-optimal planning with landmarks[C]//Proceedings of the 21st International Joint Conference on Artificial Intelligence， Pasadena， California， USA：AAAI，2009： 1728-1733.

[12] Hu Y， Yin M， Cai D. On the Discovery and Utility of Precedence Constraints in Temporal Planning[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco， California， USA ：AAAI，2011：1788-1789.

[13] Nguyen H K， Tran D V， Son T C， et al. On improving conformant planners by analyzing domain-structures[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco， California， USA：AAAI，2011： 998-1003.

[14] Porteous J， Cresswell S. Extending landmarks analysis to reason about resources and repetition[C]//Proceedings of the 21st Workshop of the UK Planning and Scheduling Special Interest Group. Delft The Netherlands，2002： 45-54.

[15] Haslum P， Slaney J， Thiébaux S. Minimal landmarks for optimal delete-free planning[C]//Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling. Atibaia， Sáo Paulo， Brazil：AAAI，2012：353-357.

[16] Nebel B.The FF Planning System： Fast Plan Generation Through Heuristic Search[J].Journal of Artificial Intelligence Research， 2001(14)：253-302.

[17] Helmert M，Domshlak C.Landmarks，Critical Paths and Abstractions：What's the Difference Anyway[C]//Proceedings of the 19th International Conference on Automated Planning and Scheduling. Thessaloniki， Greece：AAAI，2009：162-169.

[18] Pommerening F， Helmert M. Optimal Planning for Delete-Free Tasks with Incremental LM-Cut[C]//Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling.Atibaia， Sáo Paulo， Brazil： AAAI，2012：363-367.

[19] 胡艷梅.時序規(guī)劃問題中帶優(yōu)先約束的啟發(fā)式方法研究[D].長春：東北師范大學(xué)，2012.

Hu Yan-mei. Research on Heuristics with Precedence Constraints for Temporal Planning[D].Changchun：Northeast Normal University，2012.(in Chinese)

[20] 李穎， 金芝. 目標(biāo)間順序關(guān)系的提取及其抽象方法[J]. 軟件學(xué)報， 2006，17(3)： 349-355.

Li Y， Jin Z. Goal ordering extraction and abstract method. Journal of Software， 2006，17(3)：349?355.(in Chinese)

[21] 梁瑞仕， 姜云飛， 邊芮， 等. 智能規(guī)劃中的可納子目標(biāo)排序[J]. 軟件學(xué)報， 2011， 22(5)： 914-928.

Liang R S， Jiang Y F， Bian R，et al.Admissible subgoal ordering for automated planning[J]. Journal of Software， 2011， 22(5)：914-928.(in Chinese)

[22] 張彥鐸， 李哲靖， 魯統(tǒng)偉. 機(jī)器人世界杯足球錦標(biāo)賽中多機(jī)器人對目標(biāo)協(xié)同定位算法的改進(jìn)[J]. 武漢工程大學(xué)學(xué)報， 2013， 35(2):69-73.

ZHANG Yan-duo，LI Zhe-jing，LU Tong-wei.Improvements of collaborative localization algorithm of multi-robot on target in ROBOCUP[J]. Journal of Wuhan Institute of Technology， 2013， 35(2):69-73.(in Chinese)

[23] 魯統(tǒng)偉， 林芹， 李熹， 等. 記憶運(yùn)動方向的機(jī)器人避障算法[J]. 武漢工程大學(xué)學(xué)報， 2013， 35(4):66-70.

LU Tong-wei， LIN Qin， LI Xi， et al. Obstacle avoidance algorithm of robot based on recording move direction[J]. Journal of Wuhan Institute of Technology， 2013， 35(4):66-70.(in Chinese)