基于STRIPS语言的经典规划资料下载.pdf
- 文档编号:5972468
- 上传时间:2023-05-05
- 格式:PDF
- 页数:10
- 大小:277.37KB
基于STRIPS语言的经典规划资料下载.pdf
《基于STRIPS语言的经典规划资料下载.pdf》由会员分享,可在线阅读,更多相关《基于STRIPS语言的经典规划资料下载.pdf(10页珍藏版)》请在冰点文库上搜索。
2Planning语言语言2.1STRIPS在介绍经典规划之前我们先介绍一下规划语言。
最初描述规划问题是用情形演算的语言,情形演算是一种特殊的一阶语言,它设置了一些特定的语法对象以描述行动和状态变化。
不过情形演算有一个致命的缺憾框架问题。
框架问题分为表示框架问题和推理框架问题,虽然在情形演算中用后继状态公设取代效果公设和框架公设而解决了表示框架问题,但是却无法解决推理框架问题。
STRIPS语言是R.File&
Nilsson在1971年提出的表示规划问题的一种简洁的形式化语言,它是一种能够描述范围很宽的各种问题的语言。
STRIPS语言成功地解决了推理框架问题,在说明它是怎么解决这个问题之前,先介绍STRIPS的相关知识。
STRIPS语言定义了以下表示1:
?
状态:
在规划问题中,用一个文字的合取式表示世界中的某一状态。
我们采用一阶文字表示这种状态,在一阶状态描述中,这些文字必须是基项(ground),而且必须是无函数的。
另外,还采用了封闭世界假设:
在一个状态中没有提到的条件被认为是假的!
行动(Action):
一个行动是由前提(Precondition)和效果(Effect)来表示和决定的。
其中,前提是执行这个行动所必须满足的条件,效果是执行行动之后引起状态的变化,效果一般用删除表(D)和添加表(A)表示。
表示一个积木世界中的行动把积木x从积木y上搬到z上如下图所示。
准确地说它表示的是一个行动模式,它包含的意义是指一系列不同的行动,这些行动可以通过把变量x,y,z实例化成不同的常量而得到。
)()(),(:
)(),(:
),(FclearyclearzxonAzclearyxonDzclearxclearyxonPCzyxMove?
目标:
其实目标表示也应包括在状态表示中,之所以把它单独提出来,是因为目标仅是用正文字的合取式表示的,而且,一个状态S满足目标G(Goal)当且仅当状态S包含G的所有原子。
说明:
注意这里有一个很重要的假设-无函数假设,之所以使用这个假设,是因为无函数假设保证了任何问题的行动模式都可以被命题化,而不会无限的迭代下去,以至于规划器无法处理。
我们知道在情形演算中使用了fluent(变式),fluent是指其值依赖于情形的谓词和函数,如:
我们在积木世界中表达B在A上这个状态On(B,A,S),注意这里每一个状态表示都与某一“时刻”的状态S联系在一起,正是因此才导致了框架问题(更多细节参见参考书目1的第十章),相对而言,在STRIPS中状态表示为On(B,A),这样,执行某一个行动后原状态未改变的逻辑公式就可以直接“复制”下来,而在情形演算中是必须通过框架公设或后继状态公设来得到的。
下面通过一个具体例子来说明STRIPS是如何解决框架问题的。
例1:
如图1所示的积木世界状态S,S用STRIPS语言表示为:
)()(),(),(),(FclearBclearFConCAonABonS=现执行行动Move(B,A,F),此行动的表示如下:
),(FclearAclearFBonAFclearABonDFclearBclearABonPCFABMove行动的执行:
若状态S中有删除表D中的某一公式,则删除之;
若状态S中没有添加表A中的某一公式,则添加之。
对于行动的添加表A和删除表D中没有提到的S中的公式,STRIPS语言使其直接复制到下一状态S,这一处理过程可以用集合运算来形式化表示:
对应到这里的行动ADSSU)(0=)()(),()(),(:
),(FclearAclearFBonFclearABonSSFABMove=U得到)()()(),(),(),(FclearBclearAclearFBonFConCAonS=,如图1所示。
而在情景演算里,用效果公设、领域知识和框架公设来推理:
),(,()(),(),(,()(),(),(,),(,()(),(),(),(),(,()(),(),(),(),(,()(),(),(),(),(,()(),(),(),(SFABMovedoFConBCSFConSFABMovedoCAonBASCAonSFclearSSFABMovedoFclearFBSFclearSBclearSABonSFABMovedoAclearFBSFclearSBclearSABonSFABMovedoABonFBSFclearSBclearSABonSFABMovedoFBonFBSFclearSBclearSABon=其中,显然,在情形演算中与一个行动不相关的状态较多的话,Agent处理这些没有被行动所改变状态的复杂程度是相当大的,这就是框架问题。
而在前面STRIPS语言用集合运算就非常简单地处理了。
),(SFABMovedoS=由此分析可以很清楚的看到,STRIPS语言非常容易的解决了“执行一个行动后原状态未改变的逻辑公式的表示”的问题,即是解决了框架问题,这也是STRIPS语言成为规划中最重要也是影响最大的语言之一的原因。
2.2ADL和和PDDL语言语言1986,Pedanault在STRIPS的基础上提出了ADL语言,ADL语言继承了STRIPS语言的知识,并且放松了STRIPS语言的一些限制,使得规划语言更加灵活,而且应用范围也更加广泛。
1998年,Ghallab等人提出问题域描述语言PDDL,它是一种更加完善的语言系统,能够表示STRIPS、ADL以及其他语言,目前是国际上公认的标准规划问题描述语言。
3规划算法规划算法3.1全序规划全序规划全序规划是指这样的规划:
它们搜索的是与起始状态或目标相关的严格线性行动序列。
下面所要介绍的状态空间搜索算法就是这样的全序规划算法。
状态空间搜索是规划算法中最直接的方法,因为规划语言中描述行动的时侯同时用到了前提和效果,所以我们可以考虑从两个方向进行搜索:
从初始状态开始的前向状态空间搜索和从目标状态开始的后向状态空间搜索。
3.1.1前向状态空间搜索和后向状态空间搜索这里只简单介绍一下这两种规划搜索算法的思想并提供一个前向搜索算法。
前向搜索(又称前行规划)从初始状态S开始,考虑那些前提得到满足的行动a,并把他们加入到规划行动集合A中去;
再通过修改当前状态S(增加S中没出现的a中的添加表文字和删除S中出现的a中的删除表文字),并把行动a添加到A中去;
最后通过判断S的相容性的和是否包含目标状态的所有文字来确定是否是规划问题的一个解。
相反,后向搜索(又称为回归规划)是从目标状态开始,考虑那些正效果中出现而负效果中不出现当前状态的文字的行动,把此行动添加到规划行动集合中去,再在S中添加此行动的前提和删除此行动的正效果。
最后也是通过判断S的相容性和初始状态是否包含S的所有文字来确定是否得到规划问题的一个解。
先对几个符号说明一下:
S0:
初始状态,G:
目标状态,表示行动集。
前向规划算法:
)返回)()中出现;
中的文字在和;
包含于,和替换)找出一个行动模式;
,);
)3,5;
SS4PCADSPC:
.S,R3|S2,10UURADtADPCreturnGIfSS=3.1.2启发式在搜索算法中的应用不论是前向还是后向搜索,如果没有一个好的启发式的话,都不是高效的。
启发式应用于搜索算法中,可以使搜索速度大大加快。
下面就介绍一些常用的求可采纳的启发式的方法:
1)删除每个行动的前提以得到松弛规划问题,然后求此松弛规划问题的最优解耗散,并以此作为一个可采纳的启发式。
2)假设子目标独立,以每个子问题耗散的总和为启发式。
在实际的应用中,经常是把上面两种方法结合起来使用,即先假设子目标独立,然后写出松弛问题,再把每个子问题的最优解耗散求和,以此作为规划问题的启发式。
为了得到更加精确的启发式,我们还可以更进一步的只删除每个行动的前提和负效果,以此得到松弛规划问题,再以此松弛问题的最优解作为启发式。
另外,还可以只删除负效果而不删除前提来生成松弛问题(此方法得到的启发式称作清空删除表启发式),这种方法得到的启发式更加精确。
3.1.3前向搜索和后向搜索的比较从以上的描述来看,因为后向搜索只需要考虑相关的行动,不必对所有可能的行动进行搜索,而前向搜索需要考虑所有可能的行动,由此产生的分支太多,搜索时间消耗自然也就随之而大大增加了,因此后向搜索在理论上要比前向搜索更好,而且一般情况下也确实如此。
不过,规划算法的速度很大程度上依赖于启发式的应用,所以这种比较就只有理论上的意义。
注:
这里的相关行动是指效果中包含目标文字或者是搜索中当前状态的文字的行动,可能行动是指前提被满足的行动。
下面用一个简单的图示(图2)来说明前行规划和回归规划的区别:
初始状态S0为:
At(P1,A)At(P2,A);
目标状态G为:
At(P1,B)At(P2,B)。
这里我们不必细究这些公式的具体含义,仅从图2中可以很明显的看出前行规划和回归规划的搜索区别:
前行规划从初始状态出发,使用问题的行动向前搜索目标状态,回归规划从目标状态出发,使用行动的逆,向后搜索初始状态。
3.2偏序规划偏序规划偏序规划是指任何能够将两个行动放在一个规划中而不指定哪一个在前的规划算法。
简单的来说,偏序规划允许两个或多个行动无严格先后顺序。
一个偏序规划包含以下内容1:
1)行动:
一组行动是组成规划的步骤。
此处需要特别说明的是Start行动和Finish行动,空规划只包含Start和Finish行动。
Start行动没有前提而且将规划问题的初始状态中的文字作为其效果,Finish行动没有效果且将规划问题的目标文字作为其前提。
2)定序约束:
形如:
,表示行动a必须在行动b之前执行。
这里还需说明的是规划中不能包含可以造成循环的定序,如:
和。
bapbapabp3)因果连接(因果链):
,表示p是行动a的效果同时是行动b的前提,且保证了p在从执行行动a的时刻到执行行动b的时刻这段时间内为真即“保护”p的真值。
bap4)开放前提:
表示不能从规划中的一些行动中得到的前提,在不引起冲突的情况下,规划算法会尽力缩小开放前提直到使得它为空集。
我们在这里引入开放前提是为了便于表达下面所要介绍的POP算法。
规划的一致性是指在规划的定序约束中没有循环而且与因果连接无冲突。
开放前提是空集的一致性规划是规划问题的一个解,这也就是POP算法所致力要达到的目标。
POP算法的思想:
31)初态:
初始规划包含Start和Finish,并加上定序,并将Finish的所有前提当作开放前提。
FinishpStart2)扩展规划:
在已经添加到规划中行动a的开放前提中选取一个元素p,并选择一个满足一致性要求且正效果中包含p的行动b通过如下方式扩展和保证一致性:
i.因果连接和定序添加到规划中。
如果行动a未在规划中出现,把它添加到规划中,同时也添加入和.bapbapaStartpFinishapii.如果我们在添加行动c的时候与某一因果连接发生冲突,我们可以通过添加或之一来解决。
bapacpcbp3)目标测试:
由于在扩展过程中始终保持了一致性,所以只需要检验开放前提是否为空集!
下面通过一个积木世界的例子来具体分析一下偏序规划的POP算法。
例2,初始状态(Init)是积木A,B,C都放在桌面(F)上,目标状态(Goal)是积木A在B上,B在C上。
如图3所示:
图3clear(F)clear(y)z)on(x,Aclear(z)y)on(x,Dclear(z)clear(x)y)on(x,PC:
z)y,Move(x,ActionC)on(B,B)on(A,Goal)(C)clear(B)clear(A)F)on(C,F)on(B,F)on(A,Init:
Fclearclear对解的搜索从初始规划开始,然后挑选一个开放前提和能够得到这个前提的行动,以生成后继规划,重复此过程直至得到规划解。
这里我们可以附带分析帮助决策的启发式函数在偏序规划搜索中的应用。
下面是POP算法的事件序列:
1)初始规划包括Start和Finish,定须约束,没有因果连接,并将Finish状态的所有前提当作开放前提。
FinishpStart2)初始规划的开放前提集为:
on(A,B),on(B,C)。
不妨选择后继行动Finish的开放前提on(A,B),这时可选的行动有Move(A,F,B)和Move(A,C,B),因为选择Move(A,F,B)可以使开放前提集缩小,所以我们优先选择行动Move(A,F,B),并把定序和因果连接添加到规划中去。
如图4所示:
FinishBFAMoveBFAMoveStartpp),(),(、FinishBFAMoveBAon),(),(3)此时开放前提集为:
on(B,C),选择后继行动Finish的开放前提on(B,C),这时可选的行动有Move(B,F,C)和Move(B,A,C),同理优先选择Move(B,F,C),并把定序和因果连接FinishCFBMoveCFBMoveStartpp),(),(、FinishCFBMoveCBon),(),(添加到规划中去,此时行动Move(B,F,C)的前提clear(B)和因果连接的公式on(A,B)发生冲突,解决这个冲突的办法是添加定序)(若添加必然产生矛盾)。
FinishBFAMoveBAon),(),(,(),(BFAMoveCFBMovep),(CFBMoveFinishp4)此时得到的开放前提集为空集,由此我们得到一个偏序规划解:
),(),(),(),(),(),(),(),(),(),(FinishCFBMoveBFAMoveCFBMoveFinishBFAMoveFinishCFBMoveCFBMoveStartFinishBFAMoveBFAMoveStartCBonBAon、ppppp这个解如图5所示:
5)现在回来看看第3)的行动选择,如果我们选择Move(B,A,C),此时得到的开放前提集为on(B,A),一个好的规划算法应该优先选择使开放前提集变小的行动,不过并不是所有的偏序规划器都能做到这点或者会选择这么做。
所以有必要考虑选择行动Move(B,A,C)的情况,此时得到开放前提on(B,A)。
选择行动Move(B,A,C)的开放前提on(B,A),可选的行动有Move(B,F,A)和Move(B,C,A)。
若选择前者,则得到为空的开放前提集,由此也得到一个规划解,非形式化的简单表示为:
),(),(),(),(),(),(FinishBFAMoveBFAMoveCABMoveCABMoveAFBMoveAFBMoveStartpppp、第4)步得到的解与这个解相比显然更优。
这个解如图6所示:
若选择后者Move(B,C,A),得到的开放前提集为:
on(B,C),此时的开放前提与第3)步相比完全相同,即是陷入了循环状态,而这恰恰是规划所应该避免的。
根据上面的分析,我们可以看出对行动的选择算法(启发式函数的应用)是多么的重要,应用一个好的帮助决策的启发式函数可以大大提高规划算法的运行效率。
6)现在还得回到第2)步看看行动的选择,若选择的是行动Move(A,C,B),把定序和因果连接添加到规划中去。
这样得到开放前提on(B,C),on(A,C),下一步选择行动Finish的开放前提on(B,C),此时可选行动有Move(B,F,C)和Move(B,A,C),不论是是选择哪一个行动,都会产生冲突,且冲突无法通过添加定序来解决,所以若这样选择必然会导致回溯。
FinishBCAMoveBCAMoveStartpp),(),(、FinishBCAMoveBAon),(),(7)现在回到在第2)步中的开放前提的选择。
若选择行动Finish的开放前提on(B,C),此时可选的行动有Move(B,F,C)和Move(B,A,C),由前面的分析可知,应该优先选择Move(B,F,C),并把定序和因果连接添加到规划中去。
如图7所示:
FinishCFBMoveCFBMoveStartpp),(),(、FinishCFBMoveCBon),(),(8)此时得到的开放前提集为:
on(A,B),选择行动Finish的开放前提on(A,B),此时可选的行动有Move(A,F,B)和Move(A,C,B),按前面的分析,这里应该优先选择Move(A,F,B),并把定序和因果连接添加到规划中,又因为行动Move(B,F,C)的前提clear(B)和因果连接的on(A,B)产生冲突,所以把定序添加到规划中以保证规划的一致性(若添加显然矛盾)。
如图8所示:
FinishBFAMoveBFAMoveStartpp),(),(、FinishBFAMoveBAon),(),(FinishBFAMoveBAon),(),(),(),(BFAMoveCFBMovep),(CFBMoveFinishp此时得到为空的开放前提集,即求得一个规划解,而且这个解与图5所示的解相同。
如果这里选择Move(A,C,B),则此行动必然与行动Move(B,F,C)产生冲突,而且无法通过添加定序来解决,因此必然会回溯。
),(),(),(),(BCAMoveCFBMoveCFBMoveBCAMovepp或9)现在还需考虑的情况是第7)步中若选择行动Move(B,A,C),此时的搜索过程与前面的叙述相似,这里就不再赘述了,最后得到的规划解与图6所示的解一样。
10)综合以上搜索分析,POP算法搜索过程可以用下图表示。
事实上偏序规划只会搜索下图中的左半图或右半图,因为最初选择开放前提是选择on(A,B)和on(B,C)之一,具体选哪个取决于规划器。
a)规划算法中对开放前提和行动的选择很灵活,他们之间的搜索顺序对规划解并没有实质性的影响,因为之后都可以通过添加定须约束来改变它们的执行顺序,而在全序规划的状态空间搜索中行动的搜索顺序就直接决定了规划中行动执行的顺序,因此偏序规划的搜索复杂度(分支数和分支深度)比前行规划明显低很多。
如图9所示,图9显示了全序规划的搜索状态空间图,可见前行规划复杂度比POP算法更高。
b)如果把目标规划问题分解为两个子问题:
on(A,B)和on(B,C),则每个子问题都只需一步就可搜索到解,再把两个子问题合并,通过添加定序避免合并时产生的冲突,这样就得到了图5所示的解,而且这个解也是最优解。
),(),(BFAMoveCFBMovep3.3全序规划和偏序规划的比较1)描述全序规划用的是“状态”、“目标”和“行动”等,而偏序规划用的是“定序”、“因果链”、“保护”等,明显可以看出,用后者的语言完全可以描述前者,反之则不行。
所以,偏序规划的描述语言比全序规划更细致、更深刻、更本质,表达能力更强,所表达的内容也更接近实际的规划行动之间的关系4。
2)偏序中使用了灵活的定序,这就使得偏序规划中将小规模规划合并到大的规划中变得更加容易,这是因为:
偏序规划中每个小规划的行动序列可以视大规划的要求(如避免与其他的小规划发生冲突)而重新排列,因此只要满足小规划中的定序就行了。
而我们知道,在规划问题中,一个非常重要的思想就是把问题分解,而偏序规划在这方面就很明的体现出了它的优势!
3)偏序因为使用了灵活的定序而使其具有了能将问题分成子问题的优点,但是也正是这个定序的使用导致了它不能直接表示状态,所以很难估计偏序规划距离获得一个规划解还有多远,这就影响了启发式在偏序规划中的使用,因此偏序规划启发式研究的比较少。
在实际应用中,全序规划中的状态空间搜索大量的使用精确的启发式,这使得搜索的效率比理论上预期的有很大的提高。
4感谢感谢学校和系里给我们一个做暑期大学生研究计划的机会,同时也感谢陈小平教授及其实验室的老师和研究生在这个暑假中对我的指导,还有一起做大研的同学对我的帮助。
-参考书目:
参考书目:
【1】ArtificialIntelligence:
AModernApproach(中文版),StuartRussell.PeterNorvig,1stedition,人民邮电出版社;
【2】ArtificialIntelligence:
ANewSynthesis(英文版),NilsJ.Nilsson,1stedition,机械工业出版社1999.9。
【3】STRIPS,中国科大人工智能网站Seminar课程行动推理资料;
【4】Partial-OrderPlanning,中国科大人工智能网站Seminar课程行动推理资料。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 STRIPS 语言 经典 规划