目标内存不足

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
3,March2006,pp.
349355http://www.
jos.
org.
cnDOI:10.
1360/jos170349Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
目标间顺序关系的提取及其抽象方法李颖1,2,金芝31(中国科学院计算技术研究所,北京100080)2(中国科学院研究生院,北京100049)3(中国科学院数学与系统科学研究院数学研究所,北京100080)GoalOrderingExtractionandAbstractMethodLIYing1,2,JINZhi31(InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100080,China)2(GraduateSchool,TheChineseAcademyofSciences,Beijing100049,China)3(InstituteofMathematics,AcademyofMathematicsandSystemSciences,TheChineseAcademyofSciences,Beijing100080,China)+Correspondingauthor:Phn:+86-10-62565533ext5668,E-mail:Ly_Formal@yahoo.
com.
cnLiY,JinZ.
Goalorderingextractionandabstractmethod.
JournalofSoftware,2006,17(3):349355.
http://www.
jos.
org.
cn/1000-9825/17/349.
htmAbstract:Planningisaclassofcomplexproblem.
Itisawaytoimprovetheefficiencyofplanningalgorithminextractingandusinggoalorderings.
BecausedecidinggoalorderingsisalsoPSPACE-complete,itisnecessarytoextractgoalorderingsefficientlywhenusinggoalorderings.
Thepaperpresentsamethod,calledGOWN(goalorderingwithinvariants)andusesstateinvariantstoextractgoalorderings.
Duringtheprocessofordering,abstractionandunificationareutilizedtocontroltheincreaseofproblemsizethatimprovestheefficiencyofordering.
Keywords:planning;stateinvariants;goalordering;abstract;unification摘要:规划问题是一类复杂的问题.
由于规划问题中各个目标之间往往存在着实现上的顺序关系,发掘这种顺序关系并加以利用是提高规划算法效率的一种途径.
由于判定目标间的顺序关系同样是PSPACE完全的,因而为利用目标间的顺序关系首先需要有效地提取目标间的顺序关系.
给出了一种利用状态不变式来提取目标间顺序关系的GOWN(goalorderingwithinvariants)方法,并在比较目标间的顺序关系时,通过抽象和合一的手段,有效地控制了问题的增长规模,提高了处理效率.
关键词:规划;状态不变式;目标间顺序关系;抽象;合一中图法分类号:TP181文献标识码:A规划问题是人工智能中的一个重要研究领域.
给定初始状态﹑目标状态和一组可以引起状态变化的动作SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNos.
60233010,60496324(国家自然科学基金);theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNo.
2002CB312004(国家重点基础研究发展规划(973));theKnowledgeInnovationProgramoftheChineseAcademyofSciences(中国科学院知识创新工程)Received2004-11-23;Accepted2005-02-03350JournalofSoftware软件学报Vol.
17,No.
3,March2006的形式化描述,规划的任务在于自动找到一组动作序列,该组动作序列在初始状态下可以执行,并且最终能够实现目标状态[15].
经典的规划问题一般利用STRIPS方法[6]来描述问题,但这种形式的规划问题,其难度是PSPACE完全的[7].
当一个问题难以解决时,除却问题本身固有的复杂性以外,往往还可能是因为尚未充分发掘和利用与解决问题相关的某些信息或知识.
在一个规划问题中,各个目标之间往往存在着某种顺序关系,找到这种顺序关系并加以利用就有可能提高规划效率[813].
以积木世界为例,对于{ontable(a),on(b,a),on(c,b),on(d,c)}这样一个目标集,目标ontable(a)的实现就不应迟于on(b,a)的实现.
同样,on(b,a)应在on(c,b)前实现,on(c,b)应在on(d,c)之前实现.
已有的方法或者只是比较规划问题中的谓词公式,从而导致无法比较对同一谓词进行不同的实例化所获得的目标间的顺序关系;或者是针对具体的目标公式,但其计算量又随问题规模增长而激增,因而所能处理的问题规模较小.
本文给出了一种能够更有效地提取出目标间(实现上的)顺序关系的方法GOWN(goalorderingwithinvariants),该方法利用规划问题中所蕴含的状态不变式来快速提取目标间的顺序关系,并且在提取过程中利用抽象与合一的手段有效地控制问题规模的增长.
本文第1节介绍相关背景.
第2节阐述如何利用状态不变式来提取目标间的顺序关系以及如何进行抽象.

实验结果在第3节给出.
第4节将本文工作与相关工作进行比较.
最后是总结.
1规划问题与目标间的顺序关系1.
1规划问题与STRIPS方法STRIPS方法是规划问题中一种常用的问题描述方法,其相关定义如下.
定义1(STRIPS状态).
在基于封闭世界假设的前提下,STRIPS方法中对状态的描述为一组闭原子的集合,代表这些原子的合取.
定义2(STRIPS动作模式).
一个利用STRIPS方法描述的动作模式可记为一个四元组(Para,Pre,Add,Del),其中(Pre,Add,Del)这3部分都通过正的谓词公式来表示,Para则为(Pre,Add,Del)公式中所涉及到的参数.
定义3(STRIPS动作).
动作是对动作模式中所含的变量参数进行实例化以后得到的.
其语义为:对于一个状态s和一个动作o,如果Pre(o)s,则动作o在状态s可执行,并且do(s,o)=s∪Add(o)/Del(o),其中Del(o)Pre(o),do(s,o)表示在状态s下执行动作o所得到的后续状态.
而规划问题则是给定初始状态、目标状态和动作集,找到一个在初始状态下可执行的动作序列(即规划),通过执行该动作序列可以实现目标状态.
其形式化定义如下:定义4(规划问题).
规划问题可描述为一个三元组(O,I,G),其中1)O为动作集;2)I为初始状态;3)G为目标状态.
如果存在一个动作序列o1,…,on(若n=0,则为一个空的动作序列),oi∈O,该动作序列在初始状态下可以执行,并且Gdo(s,o1,…,on),则该动作序列为一个合适的规划,记为PO.
1.
2目标间的顺序关系对一个规划问题而言,目标集中各个目标之间往往不是相互独立、毫无关联的,彼此之间可能存在实现上的顺序关系,提取这种顺序关系并加以利用是提高规划效率的一种途径.

文献[8]给出了目标间顺序关系的一种定义.
定义5(ReasonableOrdering≤r).
(O,I,G)为一个规划问题,若s(B,A):POB:A∈do(s(B,A),POB),则称A,B之间存在≤r顺序关系,记为A≤rB.
其中OB={o∈O|BDel(o)};POB则代表由动作集OB中的动作构成的动作序列.
定义5的直观解释是:在一个规划问题中,对于任意状态s(B,A),即在状态s中,B成立,A不成立.
由该状态李颖等:目标间顺序关系的提取及其抽象方法351出发,若要实现A必将删除B,那么则认为A≤rB.
在文献[8]中已证明判定目标间的顺序关系的难度与规划问题一样,即难度为PSPACE难的.
2目标间顺序关系的提取及抽象方法2.
1目标间顺序关系的提取本文所给出的提取目标间顺序关系的方法将利用规划问题中所蕴含的状态不变式[1416].
定义6(状态不变式).
对于规划问题(O,I,G),若P为该问题所蕴含的状态不变式,则IP,且do(I,o1,…,on1)P.
即状态不变式是指在初始状态以及任何由初始状态可达的状态中都满足的状态约束.

例如,利用TIM[15]在积木世界问题中可提取出这样的状态不变式:x:T0.
((clear(x)∧ontable(x))∧holding(x)).
利用不变式提取目标间顺序关系的主要思想见定理1.
定理1.
给定一个规划问题(O,I,G),A,B∈G,OB={o|BDel(o)},P为该问题所蕴含的状态不变式,如果o∈OB,其中OB={o∈O|BDel(o)},若A∈Add(o),有Pre(o),BP,则A≤rB.
证明:假设(A≤rB).
根据定义5,s(B,A),P=o1,…,on,oi∈OB,A∈do(s(B,A),P).
不妨设i≤n1,Ado(s(B,A),o1,…,oi),则有A∈Add(on),所以Pre(on)do(s(B,A),o1,…,on1).
又因为B∈do(s(B,A),o1,…,on1),且根据定义6有do(s(B,A),o1,…,on1)P.
这与Pre(o),BP矛盾.
所以命题得证.
定理1说明,对于两个目标A,B,如果从状态s(B,A)出发,除非破坏B,否则不可能实现一个状态s′,在状态s′下能够执行一个可实现A且不会破坏B的动作,那么就有顺序关系A≤rB.
2.
2抽象方法在提取目标间的顺序关系时,并非每一次比较都必须借助于定理1所示的过程,因为新目标对的比较可以借助已比较的结果.
例如,对目标集{ontable(a),on(b,a),on(c,b),on(d,c)},无论是on(b,a)与on(c,b)之间的比较,还是on(c,b)与on(d,c)之间的比较,都可以抽象为on(y,x)与on(z,y)之间的比较.
本文正是通过对目标对进行抽象与合一,利用已比较的结果来获取新的目标对之间的顺序关系.
定义7(抽象).
A,B为一个公式对,将公式对中的相同常量以相同的、未在公式对中出现的新变量替换,不同的常量以不同的新变量替换,所得到的公式对称为A,B的抽象.
定义8(合一).
A1,B1与A2,B2为两个谓词公式的有序对,如果存在替换s,使得A1,B1/s=A2,B2,即A1/s=A2,且B1/s=B2,则称A1,B1可与A2,B2合一.
A1,B1可与A2,B2合一意味着A2,B2所有可能的实例化都将被A1,B1的实例化所包含.

定理2.
给定一个规划问题(O,I,G),A,B,C,D∈G,P为该问题所蕴含的状态不变式,其中A,B,C,D中没有在P中出现的常量.
A′,B′为A,B的抽象,且A′,B′/s=C,D.
如果o∈OB:A∈Add(o),有Pre(o),BP,则C≤rD.

证明:已知A′,B′/s=C,D,从而有A′/s=C,B′/s=D.
对于o∈OD:C∈Add(o),其中OD={o∈O|DDel(o)}.
o′∈OB:A∈Add(o′),Pre(o′)/s′=Pre(o),Add(o′)/s′=Add(o),并且A′/s′=C,B′/s′=D.

又因为根据已知有o∈OB:A∈Add(o),Pre(o),BP,且A,B中不包含P中的常量.
所以X.
(Pre(o′),B′)P,其中X为Pre(o′)和B′中所含变量.
所以Pre(o′)/s′,B′/s′P,即Pre(o),DP.
所以C≤rD.
定理2说明,在比较两个目标之间的顺序关系时,无须每次都重复定理1所示的过程.
如果已比较的目标对的抽象可与待比较的目标对合一,则意味着在前二者之间存在的顺序关系,在后二者之间同样存在.
当已知两个352JournalofSoftware软件学报Vol.
17,No.
3,March2006目标间不存在顺序关系的比较结果时,同样也可以利用,见定理3.
定理3.
给定一个规划问题(O,I,G),A,B,C,D∈G,P为该问题所蕴含的状态不变式,其中A,B,C,D中没有在P中出现的常量.
C′,D′为C,D的抽象,且C′,D′/s=A,B.
如果o∈OB:A∈Add(o),有Pre(o),BP,则o∈OD:C∈Add(o),有Pre(o),DP.
证明:与定理2类似.
定理3则说明,如果新的待比较目标对的抽象可与已知不存在顺序关系的目标对合一,那么利用定理1也将无法判断新的目标对之间的顺序关系.
在提取目标间的顺序关系时,目标数的增长只是问题规模增长的一部分,因规划问题所涉及到的个体数的增加而引起动作数的增加也是导致问题规模增长的重要原因.
从定理1可以看出,在利用该定理提取目标间的顺序关系时,需要对动作集进行考察,而通过对动作进行抽象,则可以有效地控制动作集的规模.
在此,不妨将一个动作模式o看成一个谓词公式,该谓词公式的参数即为动作模式中所包含的变量参数,于是,动作则可以看作是对变量实例化以后的原子公式.
定理4.
给定一个规划问题(O,I,G),A(C1),B(C2)∈G,A(X1),B(X2)为A(C1),B(C2)的抽象.
其中,C1,C2和X1,X2分别表示谓词公式中所包含的常量和变量,O为动作模式集,P为状态不变式.
o∈O,A在Add(o)中出现,对o中的变量参数进行部分实例化得到o′,使得A(C1)∈Add(o′):1)如果B在Del(o′)中出现,Z.
(Pre(o′)∧X(X=C2)),B(C2)P,其中Z为Pre(o′)中所含变量,X(X=C2)表示有xi∈X,ci∈C2,xi≠ci,其中i表示变量或常量在公式中所处的位置;2)如果B不在Del(o′)中出现,有Z.
Pre(o′),B(C2)P.
则A(C1)≤rB(C2).
证明:由已知可得对o′中的任何一个抽象动作进行完全的实例化所得到的动作都能实现A(C1).
所以,定理中的1),2)都只是为了限制对o′进行实例化后所得到的任何动作o,都应有B(C2)Del(o).
根据定理4,在比较两个目标间的顺序关系时,就无须针对具体的动作集(由完全实例化后的动作组成),而只需对部分参数进行实例化后的动作模式集进行考察即可,而该集合不会像动作集那样随着规划问题所涉及的个体数的增加而激增.
2.
3算法对所有的目标进行比较的整体流程如下所示,过程GOWN将对目标集中的所有可能的目标对进行比较:ProcedureGOWN输入:Goals目标集,GoalNum目标数输出:GoalOrder用以保存目标对之间的顺序关系1)for(i=0;i在过程GOWN中,对选定的两个目标将从两个方向进行比较,以分别判断Goals[i]≤rGoal[j]和Goals[j]≤rGoal[i]是否成立.
当比较完Goals[i],Goal[j]后,如果Goals[i],Goal[j]不可与Goals[j],Goal[i]合一,则再比较Goals[j],Goal[i],如4),5)所示.
在3)和5)中的OrderTwo(A,B,GoalOrder)则是对选定的两个目标进行比较,其算法过程如下所示:ProcedureOrderTwo(A,B,GoalOrder)输入:A待比较的目标,B待比较的目标输出:GoalOrder用以存储目标对之间的顺序关系李颖等:目标间顺序关系的提取及其抽象方法3531)ifGoalOrder中有C,D可与A,B合一,且C≤rD2)保存A≤rB到GoalOrder中;3)elseifA,B可与GoalOrder中的C,D合一,且(C≤rD)4)保存(A≤rB)至GoalOrder中;5)elseOrder(A,B,P,GoalOrder);在过程OrderTwo(A,B,GoalOrder)中,将首先借助目标对之间的合一关系来判断新的两个目标之间的顺序关系,过程中的1),2)和3),4)分别对应定理2和定理3;而当不存在合一关系时,则利用状态不变式来比较两个目标间的顺序关系,即过程Order(A,B,P,GoalOrder),该过程与定理4对应,在此省略其具体过程.
3实验结果文献[8]给出了两种提取目标间顺序关系的方法.
由于第2种方法比第1种方法更有效,并且该方法在文献[9,10]中都得到了很好的应用,所以在进行实验时,本文只与第2种方法进行比较,在下文中以HO(heuristicordering)简称.
在实验时,本文所给出的GOWN方法借助于工具TIM[15]自动地提取状态不变式.
测试数据来源于AIPS[17]所提供的Benchmarks问题中所有STRIPS形式的规划问题.
运行环境为64M内存,CPU为600MHZ.
表1显示的是对Hanoi塔问题的测试结果.
Table1Hanoi表1Hanoi塔问题ObjectsGoalsOrderingsTime(millisec.
)HOTime(millisec.
)GOWN101095010202019250303030297816040403918621305050491178723060605962670370表2显示的是对积木世界问题的测试结果.
Table2Blocksworld表2积木世界问题ObjectsGoalsOrderingsTime(millisec.
)HOTime(millisec.
)GOWN20212050204041401803060616042060808180711901001011001071160相对于Hanoi塔问题,积木世界问题中HO方法的计算量随问题规模增长的增幅不太迅猛,这主要是因为在积木世界问题中,对动作模式的Add部分中的公式而言,动作模式往往不包含冗余的变量,即对于一个动作模式o,若有A(X)∈Add(o),则在动作模式o的参数中不会包含比X更多的变量,这意味着为实现一个具体的目标,只需利用该目标所涉及的常量对动作模式进行实例化,从而缩小了动作集的规模随问题中个体数增长而增长的幅度.
而一旦将积木世界中的动作模式转换为如图1所示的描述形式(这种转换并未改变积木世界问题的本质,从而也不影响目标间所存在的顺序关系),则HO方法的计算量也将迅猛增长.
而GOWN方法则由于采取了对动作的抽象策略,从而很好地控制了动作集的增长速度,具体测试结果见表3(表中"…"表示内存不足,无法计算).
354JournalofSoftware软件学报Vol.
17,No.
3,March2006(:actionmove:parameters(obfromto):precondition(and(onobfrom)(clearob)(clearto)):effect(and(onobto)(clearfrom)(not(onobfrom))(not(clearto))))(:actionmovefromtab:parameters(obto):precondition(and(on-tableob)(clearob)(clearto)):effect(and(onobto)(not(clearto))(not(on-tableob))))(:actionmovetotab:parameters(obfrom):precondition(and(onobfrom)(clearob)):effect(and(on-tableob)(clearfrom)(not(onobfrom)))))Fig.
1Operatorsofthenewblocksworld图1新积木世界的动作模式集Table3Newblocksworld表3新积木世界问题ObjectsGoalsOrderingsTime(millisec.
)HOTime(millisec.
)GOWN20212042020404140262573060616026649360808180…90100101100…1604相关工作比较提取目标间顺序关系的研究,可以说与规划问题的研究一样悠久,也提出了大量的方法.

ALPINE方法[11]针对Prodigy系统[12]来提取抽象公式间的顺序关系.
在该方法中,A,B之间的顺序定义为如果为实现公式B必须首先实现公式A,那么A应排在B之前.
但由于该方法完全只针对动作模式和谓词公式,所以它无法区分对同一个谓词公式不同的实例化之间的顺序关系.
以积木世界为例,on(b,c)和on(c,d)之间的顺序关系在该方法中就无法区分.
文献[8]对目标间两种实现上的顺序关系给出了严格的定义,并给出两种方法来提取≤r关系:第1种方法是通过构造一个具体的规划问题的规划图(PlanGraph)[18]来提取目标间的顺序关系.
相对现有的提取状态不变式的方法[1416],构造PlanGraph的方法过于繁琐,并且在该方法中是利用PlanGraph获得的二元互斥关系(即两个原子不能在同一个状态中共存)来提取目标间的顺序关系.
而在状态不变式中可以发掘出规划问题中蕴含的多元互斥关系(即多个原子不能共存在同一个状态中),从而可能更加充分地提取出目标间的顺序关系.
但在现有的Benchmark问题中尚未体现出这一优势;第2种方法中所假设的前提条件在很多Benchmark问题中都不成立,并且这一前提条件破坏了顺序关系的传递性,从而也不满足文献[8]中所给出的顺序关系使用方法的要求.
此外,文献[8]中的方法针对的都是具体的目标集和动作集,所以计算量会随问题规模的增长而激增,所能处理的问题规模较小.
本文所提出的GOWN方法的不足之处在于,由于受制于目前的提取状态不变式的方法,所以GOWN尚只能处理STRIPS形式的规划问题.
文献[13]利用与文献[8]中类似的方法提取所有的原子公式间的顺序关系,所以相对于本文中所提出的方法,存在着与文献[8]类似的不足之处.
5总结及下一步工作发掘和利用目标间实现上的顺序关系有可能提高规划的效率,而如何有效地提取出顺序关系则成为关键.

本文给出了一种利用状态不变式提取目标间顺序关系的方法,并且通过抽象与合一的策略,使得在提取顺序关系时,可以充分利用已比较的结果,用一个更为容易的判断合一的过程来获得新的目标对间的顺序关系.
而通过对动作的抽象,有效地控制了待考察的动作集的规模.
李颖等:目标间顺序关系的提取及其抽象方法355由于受目前已有的提取状态不变式方法的限制,本文工作尚只能处理STRIPS形式的规划问题,下一步工作将把本文所给出的方法推广到ADL形式的规划问题.
References:[1]RussellS,NorvigP.
ArtificialIntelligence:AModernApproach.
Beijing:Posts&TelecommunicationsPress,[2]WeldDS.
RecentadvancesinAIplanning.
AIMagazine,1999,20(2):93123.
[3]LuRQ.
ArtificialIntelligence.
Beijing:SciencePress,2000(inChinese).
[4]DingDL,JiangYF.
Researchonintelligentplanningandapplication.
ComputerScience,2002,29(3):100103(inChinesewithEnglishabstract).
[5]WuKH,JiangYF.
Planningwithdomainconstraintsbasedonmodel-checking.
JournalofSoftware,2004,15(11):16291640(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/15/1629.
htm[6]FikesRE,NilssonNJ.
STRIPS:Anewapproachtotheapplicationoftheoremprovingtoproblemsolving.
ArtificialIntelligence,1971,2(34):189208.
[7]ErolK,NauDS,SubrahmanianVS.
Onthecomplexityofdomain-independentplanning.
In:SwartoutWR,ed.
Proc.
ofthe10thAAAINationalConf.
SanJose:AAAIPress/TheMITPress,1992.
381386.
[8]KoehlerJ,HoffmannJ.
Onreasonableandforcedgoalorderingsandtheiruseinanagenda-drivenplanningalgorithm.
JournalofArtificialIntelligenceResearch,2000,12:338386.
[9]HoffmannJ.
Utilizingproblemstructureinplanning:Alocalsearchapproach.
LNAI2854,Springer-Verlag,2003.
[10]ChenYX,HsuCW,WahBW.
SGPlan:Subgoalpartitioningandresolutioninplanning.
In:Proc.
ofthe4thInt'lPlanningCompetition,Int'lConf.
onAutomatedPlanningandScheduling.
2004.
3032.
[11]KnoblockCA.
Automaticallygeneratingabstractionsforplanning.
ArtificialIntelligence,1994,68(2):243302.
[12]FinkE,VelosoM.
Prodigyplanningalgorithm.
TechnicalReport,CMU-94-123,CarnegieMellonUniversity,1994.
[13]PorteousJ,SebastiaL,HoffmannJ.
Ontheextraction,ordering,andusageoflandmarksinplanning.
In:Proc.
ofthe6thEuropeanConf.
onPlanning(ECP01).
2001.
3748.
[14]GereviniA,SchubertL.
Inferringstateconstraintsfordomain-independentplanning.
In:Proc.
ofthe15thNationalConf.
onAIandthe10thConf.
onInnovativeApplicationsofAI.
AAAIPress/TheMITPress,1998.
905912.
[15]FoxM,LongD.
TheautomaticinferenceofstateinvariantsinTIM.
JournalofArtificialIntelligence,1998,9:367421.
[16]RintanenJ.
Aniterativealgorithmforsynthesizinginvariants.
In:Proc.
ofthe17thNationalConf.
onAIandthe12thInnovativeApplicationofAI.
AAAIPress/TheMITPress,2000.
806811.
[17]TheInt'lConf.
onAutomatedPlanningandScheduling.
http://www.
icaps.
org/[18]BlumA,LangfordJC.
Fastplanningthroughplanninggraphanalysis.
JournalofArtificialIntelligence,1997,90(12):281300.
附中文参考文献:[3]陆汝钤.
人工智能.
北京:科学出版社,2000.
[4]丁德路,姜云飞.
智能规划及其应用的研究.
计算机科学,2002,29(3):100103.
[5]吴康恒,姜云飞.
基于模型检测的领域约束规划.
软件学报,2004,15(11):16291640.