《一种基于流演算的动态规划程序设计语言.doc》由会员分享，可在线阅读，更多相关《一种基于流演算的动态规划程序设计语言.doc（17页珍藏版）》请在三一文库上搜索。
1、一种基于流演算的动态规划程序设计语言doi:10.3969/j.issn.1001-3695.2010.07.053 Dynamic planning programming language based on fluent calculus LIU Yi-song1, LI Ming-yue1, ZHU Mang2 (1. School of Computer Science & Telecommunication Engineering, Jiangsu University, Zhenjiang Jiangsu 212013, China; 2. Management Dept. of
2、Drainage, Zhenjiang Jiangsu 212013, China ) Abstract:This paper proposed a dynamic planning programming language based on fluent calculus, which was called DPPLFC. It could describe complex action such as sequence, concurrence, nondeterministic branch by defining action expression and solved the pro
3、blem that the users wrote applications inconveniently. Then gave a dynamic planning operator of DPPLFC. It implemented off-line execution again according to differences of the on-line execution state and previous corresponding off-line execution state and improved dynamic planning operator based on
4、situation calculus. DPPLFC described a new off-on line execution and deals with exogenous actions immediately. Presented the composition and semantics and implementation of DPPLFC. An elevator example indicates that the feasibility and effectiveness of DPPLFC. Key words:fluent calculus; FLUX; dynami
5、c planning operator; off-on line execution; programming language 0 引言 智能规划1是人工智能研究的一个重要领域,具有突出的理论和应用价值。其所要解决的问题是:在给定的已知条件(初始状态)下,如何通过产生式规则(领域动作)获得所需要的结论(目标状态)。 Golog2、ConGolog3、IndiGolog4均是基于情景演算的可以用于智能规划的语言。Golog、ConGolog 采用离线执行方式;IndiGolog通过动态规划算子将离线执行方式改进为在线执行方式,但均采用情景演算的回归推理机制,执行效率较低;且IndiGolog的
6、动态规划算子无法完整地描述动态环境下的再次离线规划机制。 流演算5源于经典情景演算,采用前推推理机制对状态和动作进行推理,其推理效率优于采用回归推理机制的情景演算。FLUX6是流演算执行器,采用前推推理机制,比Golog 、ConGolog、IndiGolog等有更高的执行效率,但FLUX因缺乏顺序、不确定选择、并发等语言结构而不便于用户编写应用程序。 本文的前期工作7,8对FLUX进行扩充,提出了一种真并发程序设计语言CONPFLUX,并成功地应用到智能虚拟人动画中,但均未讨论再次离线规划的问题。 本文基于流演算理论,提出了一种动态规划程序设计语言DPPLFC,该语言通过定义动作表达式来描述
7、顺序、并发、非确定选择等语言结构。DPPLFC的动态规划算子较为完整地描述了动态环境下的再次离线规划机制。DPPLFC采用流演算的前推推理机制具有较高的执行效率。 1 DPPLFC语言的组成 DPPLFC由初始状态、前提条件公理集、状态知识更新公理集、策略集四部分组成,其形式规范如下: program:=initial state,precondition axioms,state knowledge update axiom,strategies。 各组成部分含义如下:initial state(初始状态)表示初始情景下对应的状态;precondition axioms(前提条件公理集)用于
8、描述原子动作可以执行的条件;state knowledge update axiom(状态知识更新公理集)用于描述原子动作对状态的影响情况;strategies(策略集)表示一个命名的复杂动作称为策略,类似于过程性程序设计语言中的过程和函数。 2 DPPLFC程序的语义及动态规划算子 本文利用动作表达式来描述DPPLFC程序中的顺序、并发、非确定选择等复杂动作,从而给出DPPLFC语言的语法。 定义1 (动作表达式) 由以下规则生成: := |a |?|1;2 |1|2 |(x)(x)|*|E() |1 |2| 12| if then 1 else 2 endif | while do end
9、while 其中:表示空动作;a为原子动作;? 为测试动作;1;2表示顺序执行;1|2 表示非确定选择;(x)(x)为参数非确定选择;*表示非确定迭代,即可能重复执行0次或多次;E()表示过程,可理解为策略,E为过程名,为过程参数;1|2表示并发执行;if then 1 else 2 endif表示分支结构;while do endwhile表示循环结构。 2.1 DPPLFC程序的语义 ConGolog通过两个特殊谓词Trans和Final被赋予了一种“单步变迁”的结构化操作语义。为了描述DPPLFC程序的语义,本文基于流演算理论,对Trans和Final重新定义,给出了DPPLFC程序的语
10、义。引入两个保留关系符号Trans(, z, h, ,z,hl, hr)和Final(,z,h)。其中:、为动作表达式,hr为只含1个或0个原子动作的动作序列(即a或)。Trans(,z,h,z,hl,hr)表示在状态z,动作历史h下能够执行一步hr使得状态改变为z,生成新的动作历史hl,并余下未执行。Final(,z,h)表示在状态z、动作历史h下能够终止执行。 定义2 递归定义七元谓词Trans(,z,h, z,hl,hr)和三元谓词Final(,z,h)如下: a)空动作,=,则 Trans(,z,h,z,hl,hr)FalseFinal(,z,h)True b)原子动作,=a,则 Tr
11、ans(a,z,h,z,hl,hr)Poss(az,z)= s.State(s)=zz=State(Do(az,s)hr=azFinal(a,z,h)False c)测试动作,=?,则 Trans(?,z,h,z,hl,hr)z=z=zhl=hhr=Final(?,z,h)False d)顺序动作,=1;2,则 Trans(1;2,z,h,z,hl,hr) (?靓莫?1).=(1;2)Trans(1,z,h,1,z,hl,hr) Final|(1,z,h)Trans(2,z,h,z,hl,hr)Final(1;2,z,h)Final(1,z,h)Final(2,z,h) e)非确定选择,=1|
12、2,则 Trans(1|2,z,h,z,h,z,hl,hr) Trans(1,z,h,z,hl,hr)Trans(2,z,h,z,hl,hr)Final(1|2,z,h)Final(1,z,h)Final(2,z,h) f)参数非确定选择(v)(v) Trans(v.,z,h,z,hl,hr) x.Trans(vx,z,h,z,hl,hr)Final(v.,z,h)(x)Final(vx,z,h) (v)(v)的直观含义是非确定选择参数v的一个值x,并执行动作表达式(v)。 g)非确定迭代,=*,则 Trans(*,z,h,z,hl,hr) ?靓?.=;*Trans(,z,h,z,hl,hr)
13、Final(*,z,h)True h)并发,=1|2,则 Trans(12,z,h,z,hl,hr)r.(=r2) Trans(1,z,h,r,z,hl,hr) r.(=1r)Trans(2,z,h,r,z,hl,hr)Final(12,z,h)Final(1,z,h)Final(2,z,h) i)为复杂动作,= E(),则 Trans(E(),z,h,z,hl,hr)Trans(),z,h,z,hl,hr) Final(E(,z,h)Final(),z,h) Pro E(),() endPro if-then、while-do通过下列定义解释为特殊的复杂动作: if then 1 else
14、2endif=def(?;1 )|(?;2) while do endwhile =def(?;)*|? 定义3 的整体语义可利用宏Done表示: Done(,z,h,z,hl,hs)=def(?靓摹?)(Trans*(,z,h,z,hl,hs)Final(,z,hl) Trans*是Trans的自反传递闭包,Done(,z,h, z,hl,hs)表示在状态z下通过执行动作序列hs达到目标状态z。 2.2 基于流演算的动态规划search算子 文献4通过动态规划search算子将原来的离线执行方式改进为在线执行方式。其search算子描述如下: Trans(,s,s)?靓谩?.=Trans(,
15、s,s)?靓谩?,s.Trans*(,s,s)Final(,s) 上述search算子对于search(a1;a2|a1;a3)的情形,若因外部动作的发生需对剩余程序search(a2)再次离线规划,而此时若a2不能执行,则整个规划失败,即使a3是下一个可执行的动作,上述search算子也无法完成对a3的再次离线规划。 针对上述search算子的不足,本文基于流演算理论,借鉴文献9,给出了一种动态规划算子。其语义描述如下: Trans(search(),z,h,z,hl,hr)Trans(search(,z,h),z,h,z,hl,hr)(1)Trans(search(,i,zi,hi),z,
16、j,z,hl,hr)(?靓?,).=search(,i,zi,hi)Trans*(exoi,zi,hi,exo,z,h,hr)Trans(,z,h,z,hl,hr)(?靓谩?,z,hl).Trans*(,z,hl,z,hl,hr) Final(,z,hl)(2) Final(search(),z,h,)Final(search(,z,h),z,h)(3)Final(search(,i,zi,hi),z,h)(?靓?).Trans*(exoi,zi,hi,exo,z,h)Final(,z,h)(4) where exo=def(a)Exo(a)?;a;a)*(5) 式(1)(3)重写search
17、()为search(,z,h),以存储初始搜索块程序、初始状态z和初始动作历史h。式(2)中第一条Trans语句描述了从初始状态zi、初始动作历史hi到达当前状态z、当前动作历史h的变迁过程,且当有外部动作发生时,使外部动作程序与初始搜索块程序并发执行;第二条Trans语句意为,当不涉及外部动作的初始程序经多次单步变迁执行完成时,即到达目标状态z。 式(4)定义Final,程序正常终止,当且仅当不涉及外部动作的初始程序经多次单步变迁在当前状态下可执行完成。式(5)给出了外部动作的形式化描述。 对比文献4,本文的search算子存储了初始搜索块程序、初始状态和初始动作历史,且当有外部动作发生时,
18、使外部动作程序与初始搜索块程序并发执行。对于search(a1;a2|a1;a3)的情形,程序解释器将会选择第一个分支,并执行动作a1。若因外部动作的发生使得search(a2)不能执行,第一个分支执行失败,但a3可能是下一个可执行的动作;此时可根据初始搜索块程序、初始动作历史和初始状态,将已执行的动作历史和外部动作未执行前存储的动作历史进行匹配,再次进行离线规划以生成新的可执行的动作序列,从而更有效地实现了再次离线规划机制。 对比文献9,本文search算子是当在线执行的状态与前一次离线执行相对应的状态不同时,才会对进行再一次离线执行,有利于提高动态规划的效率。 本文search算子体现的是
19、一种离/在线执行方式,即通过离线规划获得一个可行的动作序列,再对动作序列的每一个动作依次实施在线执行。 3 DPPLFC程序的解释器 在参考IndiGolog解释器的基础上,利用约束逻辑程序设计语言ECLiPSe实现了DPPLFC程序的解释器。限于篇幅,下面只给出复杂动作中的顺序动作以及动态规划search算子的实现代码: a)顺序动作,=1;2 trans(A1|A2, Z, H, Ar, Zr, HL, Hr) :- final(A1,Z, H), trans(A2, Z, H, Ar, Zr, HL, Hr); trans(A1, Z, H, A1r, Zr, HL, Hr), Ar =
20、 A1r|A2. final(A1|A2,Z,H) :-final(A1,Z,H), final(A2,Z,H). b)基于流演算的动态规划search算子 trans(search(A), Z, H, followpath(P,A,Z,H),Zr,HL,Hr):- %1 findpath(,A, Z,H, P0, L), trans(followpath(P0,A,Z,H),Z,H,followpath(P,A,Z,H),Zr,HL,Hr),printPath(L),nl. final(search(A),Z, H) :-final(A,Z,H). %2 trans(followpath(t
21、rans(A,Z,H,Ar,Zr,HL,Hr)|P,A0,Z0,H0),Z, H,followpath(P,A0,Z0,H0), Zr,HL,Hr):-!.%3 trans(followpath(trans(A,Z,H,Ar,Z,H,Hr)|P,A0,Z0,H0), CZ,CH, followpath(P,A0,Z0,H0),CZ,CH ,Hr):-%4 possPath(trans(A,Z,H, Ar, Zr, H, Hr)|P, CZ, CH),!. final(followpath(final(A, Z,H),A0,Z0,H0),Z,H):-!.%5 trans(followpath(t
22、rans(A,Z,H,Ar,Z,E|H,Hr)|P,A0,Z0, H0),CZ,CH,followpath(P,A0,Z0,H0),CZ,E|CH,Hr):- %6 possPath(trans(A,Z,H, Ar, Zr,E|H,Hr)|P, CZ, CH),!. final(followpath(final(A,Z,H),A0,Z0,H0),CZ,CH):%7 final(A,CZ,CH),!. trans(followpath(trans(A,Z, H, Ar, Zr, _, Hr)|P,A0,Z0,H0), CZ, CH,followpath(P1,A0,Z0,H0),Z1,HL,H1
23、):-%8 reverseList(CH,L),!,findpath(L,A0,Z0,H0,CP,CL), printPath(CL),nl,trans(followpath(CP,A0,Z0,H0),CZ,CH,followpath(P1,A0,Z0,H0),Z1,HL,H1). final(followpath(final(A,Z,H)|P,A0,Z0,H0),CZ,CH):- %9 reverseList(CH,L),!, findpath(L,A0,Z0,H0,final(A,Z1,H1),CL). 其中:谓词findpath/6用于判断A是否可以合法终止(是否可行),即对A的离线执行
24、。谓词printPath/1输出离线执行得到的动作序列。谓词reverseList/2用于得到在线执行的动作序列。子句%3、%5表示对A的在线执行。子句%4、%6、%7表示当在线执行的状态与前一次离线执行相对应的状态不同时(即发生了A之外的动作),对A进行重新离线执行。子句%8、%9是子句%6、%7再次离线规划失败时,根据初始状态、初始搜索块程序、初始动作历史再次离线执行。 4 电梯程序实例 电梯的例子被许多文章引用,这里给出DPPLFC语言编写的电梯控制程序的主要部分。 a)precondition axioms(前提条件公理集) poss(up,Z):- knows_val(M,curre
25、ntFloor(M),Z),M= =6. poss(down,Z):- knows_val(M,currentFloor(M),Z),M =1. poss(open,Z). poss(close,Z). poss(turnoff(N),Z):-knows(on(N),Z), knows_val(M,currentFloor(M),Z),N= =M. poss(request(N),Z):-knows_not(on(N),Z). b)state knowledge update axiom(状态知识更新公理集) state_update(Z1,up,Z2) :- knows_val(M,curr
26、entFloor(M),Z1), N is M+1, update(Z1,currentFloor(N),currentFloor(M),Z2. state_update(Z1,down,Z2) :- knows_val(M,currentFloor(M),Z1), N is M-1, update(Z1,currentFloor(N),currentFloor(M),Z2). state_update(Z1,open,Z2):-update(Z1,Z2). state_update(Z1,close,Z2):-update(Z1,Z2). state_update(Z1,turnoff(N)
27、,Z2) :- knows(on(N),Z1),update(Z1,on(N),Z2). state_update(Z1,request(N),Z2) :- knows_not(on(N),Z1),update(Z1,on(N),Z2). c)strategies(策略集) proc(below_floor(N),/复杂测试动作过程 ksome(M,currentFloor(M) & MN). proc(go_floor(N), /while循环 while(n(currentFloor(N),if(below_floor(N),up,down). proc(serve_floor(N),/顺
28、序 go_floor(N), open, close, turnoff(N). proc(handle_reqs(Max), /(参数)非确定选择、测试动作 ?(-(ksome(n,on(n)/ pi(n,pi(m,?(ksome(n,on(n)& ksome(F,currentFloor(F)& m is Max-abs(F-n), ?(m 0),serve_floor(n), handle_reqs(m) ). proc(minimize_motion(Max), handle_reqs(Max) / pi(m,?(m is Max+1),minize_motion(m) proc(con
29、trol, search(minimize_motion(0) ). 程序在ECLiPSe5.8中调试运行成功。 设初始条件情形为currentFloor(2)(当前电梯在2楼)on(3),on(5)(3、5楼有请求),运行结果如下: a)无外部动作时,离线规划的动作序列为 path: upopencloseturnoff(3)upupopencloseturnoff(5) b)在线执行至动作turnoff(3)后,发生外部动作request(2),即2楼有请求,此时必须再次离线规划,得到如下动作?蛄?: path: downopencloseturnoff(2)upupupopenclose
30、turnoff(5) 即转而执行2楼的请求。再执行5楼的请求,在程序运行过程中,根据已执行的动作序列upopenclose turnoff(3)和初始状态,再次进行离线规划以生成新的可执行的动作序列。 对比IndiGolog和DPPLFC编写的电梯程序的执行时间,可知DPPLFC具有较高的执行效率。 5 结束语 本文提出并实现了一种基于流演算的动态规划程序设计语言DPPLFC。该语言通过定义动作表达式对FLUX进行扩充,能够描述顺序、并发、非确定选择等复杂动作,方便用户编写应用程序。通过重新定义谓词Trans和Final,给出了DPPLFC程序的语义。DPPLFC语言的动态规划算子高效地实现了动态环境下的再次离线规划机制。DPPLFC语言为动态环境下的智能机器人的动态规划提供了一种解决方案。实例证明了DPPLFC语言的可行性和高效性。