搜索
28720057CHINESEJOURNALOFCOMPUTERSVol.28No.7July2005(230027):2003212225;:2005203218.(60275024)(2001AA4222).,,1976,,.E2mail:xlee@mail.ustc.edu.cn.,,1955,,,,.,.,.(POMDP)(PRS),POMDPRS.PRS,,POMDP;,POMDPPRS,.;;PRS;POMDP;POMDPRSTP18AReal2TimePlanningSysteminDynamicNondeterministicEnvironmentsLIXiangCHENXiao2Ping(DepartmentofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230027)AbstractPlanningisamainresearchfieldinartificialintelligence,whichhasabroadapplicationbackground.Inrecentyears,thefocushasshiftedtotheproblemofplanningindynamicnonde2terministicenvironments.Thispaperpresentsanovelcontinualplanningsystem,POMDPRS,whichcombinesPOMDPandPRStogainstrongerabilitiesofadaptingtodynamicnondeterminis2ticenvironments.InthissystemauthorssubstitutetheprobabilisticdistributionbeliefmodelandthemaximumutilityprincipleofPOMDPforthefirst2orderlogicbeliefrepresentationandplanselectionmechanismofPRS;ontheotherhand,adoptthecontinualplanningmechanismofPRS,whichinterleavesplangenerationandexecution,tomakethePOMDPdecisionindynamicenvi2ronmentsmoreefficientundersomeconditions.Keywordscontinualplanning;dynamicnondeterministicenvironment;PRS;POMDP;POMDPRS1.(),,.:(1).(Agent),,.(2).,.(3).,,.,STRIPS,GraphPlan,,:;;[1,2]..,(HTN),,[3].,.,,,.PRS(ProceduralReasoningSystem),NASA[4].PRS,dMARS[5]UM2PRS[6].Rao[7],Wooldridge[8]PRS.PRS,.,,().PRS,.,PRS.,POMDP(PartiallyObservableMarkovDecisionProcess)[2,9,10].POM2DP.Markov,,.,POMDP,.Value2iteration.Cassandra[11],Kaelbling[9],Zhang[12]Pineau[13],.Pineau.,POMDP,.PRSPOMDP.POMDPPRSPOMDPRS,.,POMDP(),;POMDP,PRS;PRS,,,..2POMDPRS,;3,;4;,5.22.1POMDPRSS,A,G,P,,T,O,R,.S,|S|=N.A.,().G,.P(2.2)..T:S(AG)(S).T(s,a,s)sas.T(s,g,s)sgs.O:s()..O(o,s)so.R:S(AG)R.R(s,a)sa,R(s,g)sg...2.2,POMDPRS46112005ProceduralReasoningSystem:UsersGuide,ArtificialIn2telligenceCenter,SRIInternational,2001MurphyK..AsurveyofPOMDPsolutiontechniques.U.C.Berkeley:TechnicalReport,2000PineauJ.,ThrunS..High2levelrobotbehaviorcontrolu2singPOMDPs.In:AAAIWorkshopNotes,MenloPark,CA,2002.(1).(Var)(Func)(Pred)(?)(ground,achieve,notice).(2)(Term)..Term=Var|Func(Term,,Term).(3)(Atom).(Pred(t),t=t1,t2,,tn).Atom=Pred(Term,,Term).(4)(Literal)..Literal=Atom|?Atom.(5)(State)..State={groundLiteral}.(6)(Observation)..Observation={groundLiteral}.(7)(Goal).Goal=achieveGoalCond,GoalCond,.2.3POMDPRSPRS,5(1).1POMDPPRS(1).,.B={b(s1),b(s2),,b(sN)},siS,Ni=1b(si)=1(1)b(s)s.(2).,,.(3)....,..,..A,,..,.,.().app,cpipi,p-(cpi)pcpi.2.3.2.(4).()..(5).,,,.3PRS,POMDPRS.,.3.1B:(1).B=a(B,a)BaB.b(s)B,b(s)B,b(s)=sST(s,a,s)b(s)(2)56117:(2).B=o(B,o)BoB.,oBW(B,o)=sSO(o,s)b(s)(3)O(o,s).W(B,o)E,.b(s)B,b(s)B,b(s)=O(o,s)b(s)(4),Ni=1b(si)=1.W(B,o),.:(1),.(2),..,,.,,,.,,.W(B,o)Mod(o,B).,O(|S|).,..,O(|S|).3.2og,notice(o)g=achieve(l).enotice(o),pnotice(t),qAomgut=q,pe.eachieve(l),pachieve(t),qAlmgut=q,pe.Be,pe,cpp.sSb(s)[scp]E(5)pe;[scp]=1,vqqAs,vmguq=cp0,(6);,.pBV(B,p)V(B,p)=R(B,ap)+mi=1iV(a(B,ap),p-(cpi))(7)R(B,ap)=sSR(s,ap)b(s)(8)iapi,.b(s)a(B,ap)s,i=sSb(s)[scpi](9)i=i,iE0,(10)viE,ii=1.(7)a(B,ap),ap,a(B,ap)(2).ap,B=a(B,ap):b(s)B,b(s)B,b(s)=sST(s,ap,s)b(s)(11)Bb(s)=1,s=s0,sS-{s},V(s,p)=V(B,p).a(8),(7)V(B,p)=R(B,ap)+mi=1iV(a(B,ap),p-(cpi))=sSR(s,ap)b(s)+mi=1isSV(s,p-(cpi))b(s)=sSR(s,ap)b(s)+mi=1isSV(s,p-(cpi))sST(s,ap,s)b(s)=sS[R(s,ap)+mi=1isSV(s,p-(cpi))T(s,ap,s)]b(s)=sSV(s,p)b(s)(12),ps,sV(s,p).V(s,p)p.3.3POMDPRS.,.,66112005.,..:loopifeifeeendififeePA={p1,p2,,pk}.ifPAÁforpiPAV(B,pi)endforV(B,pi)piendifendifendifforfori=1tok(k,cpi)i:W(B,cpi)=sSb(s)[scpi](13)endforifW(B,cpi),elseW(B,cpi)amaxifamaxamaxelseamax.amax.endifendifendforendloop44.1POMDPRSPRS,,,p.a,a,;p,,p,pp.,POMDPRS.,,,.,POMDPRS,.,,.4.2POMDPRS,,...TB2update2o,TB2update2a,TSelectPlan,TChooseNextStep.,Tcircle=TB2update2o+TSelectPlan+kTChooseNextStep+TB2update2a,k.,TB2update2oO(|S|),TB2update2aO(|S|2).(7)(12),TSelectPlanO(|S||P|).(13),TChooseNextStepO(|S|).,.,O(|S|2).,..h,m,(7),V(s,p)O(mh-1|S|).O(mh-1|S|2).,,.,,.4.3,PRS76117:.POMDPRSPOMDP.(1)POMDPRSSA(S).,,,.(2)S,,TO.,.,().,.POMDPRSW(B,o).,.,.,POMDPRS...,;,.5RoboCup[14],,.RoboCup,POMDPRS.:,.,:SeeBall,NearBall,BallPos(pos),SeeBall,NearBall,.BallPos(pos),posL,M,R,,,.,S:S={{SeeBall,NearBall,BallPos(L)},{SeeBall,NearBall,BallPos(R)},{SeeBall,NearBall,BallPos(M)},{SeeBall,?NearBall,BallPos(L)},{SeeBall,?NearBall,BallPos(R)},{SeeBall,?NearBall,BallPos(M)},{?SeeBall,NearBall,BallPos(L)},{?SeeBall,NearBall,BallPos(R)},{?SeeBall,NearBall,BallPos(M)},{?SeeBall,?NearBall,BallPos(L)},{?SeeBall,?NearBall,BallPos(R)},{?SeeBall,?NearBall,BallPos(M)}},s1,s2,,sN,N=12.={{SeeBall,NearBall,BallPos(L)},{SeeBall,NearBall,BallPos(R)},{SeeBall,NearBall,BallPos(M)},{SeeBall,?NearBall,BallPos(L)},{SeeBall,?NearBall,BallPos(R)},{SeeBall,?NearBall,BallPos(M)},{?SeeBall}},o1,o2,,oL,L=7.A={WalkForward,TurnLeft,TurnRight,LeftKick,RightKick,StraightKick,HeadReset,HeadTurn,TraceBall},WalkForward,TurnLeft30,TurnRight30,LeftKick,RightKick,StraightKick.Head2Reset,HeadTurn45,TraceBall.O:s(),O12345678910111210.9500.050000.030.030.03000200.950.050000.030.030.0300030.050.050.90000.030.030.0300040