界標知識及其應用研究進展

蔡敦波, 徐 勝, 趙彤洲

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

0 引 言

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

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

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

1 Landmark及其計算方法

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

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

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

定義1.規(guī)劃任務(Planning Task)為四元組Π=，其中，V是命題變量的有限集，O是動作的有限集，I是V的子集、表示初始狀態(tài)，G是V的子集、表示目標條件.O中每個動作o為三元組，其中pre(o),add(o),del(o)均為V的子集，分別表示動作o的前提、添加效果和刪除效果，cost(o)為實數，表示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í)行結果為s/del(o)∪add(o)，記為o(s).

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

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

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

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

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

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

如果在規(guī)劃任務中，動作的代價都為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動作”.

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

例1.設規(guī)劃任務Π=僅有兩個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動作之間存在著一些順序關系.下面首先介紹幾個基本概念，之后介紹“Landmark命題”之間的三種順序關系[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. 設f和f′為Π=中兩個命題，稱f與f′具有“自然順序”(Natural Ordering)，記為f→f′，當且僅當：對于每個在I上“可用”的動作序列π，當“f′在π的第i步為真”時均有“f在π的某個第j(j

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

1.3 Landmark的計算方法

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

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

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

但是，LMRPG在某一層考察的動作集可能是全部可能動作的某個子集，因而該算法可能計算出一部分錯誤的Landmark順序.Porteous等人隨后提出了“首次必然順序”的一種正確計算方法[14].該方法的主要思想是：為了收集所有在命題f′之前可能執(zhí)行的動作，將任務中以f′為添加效果的動作全部移除，之后構造規(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ā)現更多的Landmark命題，Richter等人根據“域轉移圖”(Domain Transition Graph)的結構特征，提出了一種能夠計算更多Landmark的方法[8].其主要思想為：對于變量v的域轉移圖DTGv，如果從v在初始狀態(tài)中的取值d0到Landmark命題v=d的所有路徑都經過d′，則v=d′是Landmark命題.為進行此判斷，該方法在DTGv中依次去除d′，之后判斷從d0到d′的連通性，如果不連通，則判定v=d′為Landmark命題，并且v=d′與v=d存在“自然順序”.

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

由于Landmark及其順序刻畫了規(guī)劃問題實例的結構，研究者最初利用Landmark命題順序對規(guī)劃任務的目標進行分解來降低規(guī)劃問題的求解難度；近來的研究主要集中于利用Landmark設計啟發(fā)函數；本文作者探索了在基于SAT的規(guī)劃框架下使用Landmark的方法.

2.1 基于Landmark的任務分解

Hoffmann等人研究了基于Landmark將規(guī)劃任務分解為規(guī)模較小的規(guī)劃任務的方法[7]，用該方法引導FF規(guī)劃系統[16]和LPG規(guī)劃系統進行規(guī)劃求解.在測試的Blocksworld域、Grid域、Logistics域和Rovers域實現了較大的效率提升，但是在FreeCell域和Depots域的性能相比FF和LPG均有下降[7].

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

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

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

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

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

(1)

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

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

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

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

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

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

2.4 基于Landmark順序改進SatPlan

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

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

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

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

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

(2)

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

(3)

(4)

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

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

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

5 總結與展望

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

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

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

致 謝

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

參考文獻:

[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].長春：東北師范大學，2012.

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

[20] 李穎， 金芝. 目標間順序關系的提取及其抽象方法[J]. 軟件學報， 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ī)劃中的可納子目標排序[J]. 軟件學報， 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] 張彥鐸， 李哲靖， 魯統偉. 機器人世界杯足球錦標賽中多機器人對目標協同定位算法的改進[J]. 武漢工程大學學報， 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] 魯統偉， 林芹， 李熹， 等. 記憶運動方向的機器人避障算法[J]. 武漢工程大學學報， 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)