规划提出能达到一定目标的行动序列的任务

规划规划：提出能达到一定目标的行动序列的任务基于搜索的问题智能体逻辑规划智能体规划环境经典的：完全可观察、确定性的、有限的、静态的以及离散的。非经典：部分可观察或随机致谢：本讲义部分内容来自TomLenaert@~tlenaert/teach/slides/AIMA/主要内容规划问题规划问题语言：语法和语义状态空间搜索规划前向、后向利用问题的表示的规划算法偏序规划命题逻辑规划规划方法分析现实世界问题的困难假设一个问题智能使用标准的搜索算法…什么样的行动是相关的？例子：购买“人工智能教材”，假设对于每一个10位数字的ISBN号码都有一个购买行动遍历搜索vs.后项搜索如何寻找一个好的启发函数？例如在线购买4本不同的书，4个步骤共有1040规划状态耗散的估计：所要买书的剩余数目应是一个好的估计。Problem-dependentvs.–independent：启发函数取未满足的合取式的数目如何将问题分解？假设大部分现实世界问题是近似可分解的：需要做些附加工作来合并子规划PlanninglanguageWhatisagoodlanguage?Expressiveenoughtodescribeawidevarietyofproblems.Restrictiveenoughtoallowefficientalgorithmstooperateonit.Planningalgorithmshouldbeabletotakeadvantageofthelogicalstructureoftheproblem.STRIPSandADLGenerallanguagefeaturesRepresentationofstatesDecomposetheworldinlogicalconditionsandrepresentastateasaconjunctionofpositiveliterals(atomicsentences)Propositionalliterals:PoorUnknownFO-literals(groundedandfunction-free):At(Plane1,Melbourne)At(Plane2,Sydney)Closedworldassumption:conditionsnotmentionedareassumedfalseRepresentationofgoalsPartiallyspecifiedstateandrepresentedasaconjunctionofpositivegroundliteralsAgoalissatisfiedifthestatecontainsallliteralsingoal.Generallanguagefeatures(2)RepresentationsofactionsAction=PRECOND+EFFECTAction(Fly(p,from,to),PRECOND:At(p,from)Plane(p)Airport(from)Airport(to)EFFECT:¬AT(p,from)At(p,to))=actionschema(模式)(p,from,toneedtobeinstantiated)ActionnameandparameterlistPrecondition(conj.offunction-freeliterals)Effect(conjoffunction-freeliteralsandPisTrueandPisfalse)Add-listvsdelete-listinEffectLanguagesemanticsHowdoactionsaffectstates?Anactionisapplicableinanystatethatsatisfiestheprecondition.ForFOactionschemaapplicabilityinvolvesasubstitutionforthevariablesinthePRECOND.Ex:At(P1,JFK)At(P2,SFO)Plane(P1)Plane(P2)Airport(JFK)Airport(SFO)Satisfies:At(p,from)Plane(p)Airport(from)Airport(to)With={p/P1,from/JFK,to/SFO}Thustheactionisapplicable.Languagesemantics(2)Theresultofexecutingactionainstatesisthestates’s’issameassexceptAnypositiveliteralPintheeffectofaisaddedtosAnynegativeliteral¬PisremovedfromsExampleinpreviouspage:At(P1,SFO)At(P2,SFO)Plane(P1)Plane(P2)Airport(JFK)Airport(SFO)STRIPSassumption:avoidsrepresentationalframeproblemeveryliteralNOTintheeffectremainsunchangedSolutionisasequencesuchthatini→goalExpressivenessandextensionsSTRIPSissimplifiedImportantlimit:function-freeliteralsAllowsforpropositionalrepresentationFunctionsymbolsleadtoinfinitelymanystatesandactionsRecentextension:ActionDescriptionlanguage(ADL)Action(Fly(p:Plane,from:Airport,to:Airport),PRECOND:At(p,from)(fromto)EFFECT:¬At(p,from)At(p,to))Standardization:Planningdomaindefinitionlanguage(PDDL)例子：积木世界一组放在桌子上的立方体积木，积木能够被叠放，但是只有一块积木能够直接放在另一块的上面。一个机器臂能够拿起一块积木并把它移到别的位置，无论是在桌子上还是在另一块积木上。机器臂每次只能拿起一块积木。ExamplesofplanninginBlocksWorldInit(On(A,Table)On(B,Table)On(C,Table)Block(A)Block(B)Block(C)Clear(A)Clear(B)Clear(C))Goal(On(A,B)On(B,C))Clear(b)definedas“thereisaclearspaceonbtoholdablock”Action(Move(b,x,y))PRECOND:On(b,x)Clear(b)Clear(y)Block(b)(bx)(by)(xy)EFFECT:On(b,y)Clear(x)¬On(b,x)¬Clear(y)Action(MoveToTable(b,x))PRECOND:On(b,x)Clear(b)Block(b)(bx)EFFECT:On(b,Table)Clear(x)¬On(b,x))Note:weintroducexytoblockspuriousactionssuchasMove(B,C,C)注意负文字主要内容规划问题规划问题语言：语法和语义状态空间搜索规划前向、后向利用问题的表示的规划算法偏序规划命题逻辑规划规划方法分析状态空间搜索规划前向搜索后向搜索启发式函数Planningwithstate-spacesearchBothforwardandbackwardsearchpossibleProgressionplannersforwardstate-spacesearchConsidertheeffectofallpossibleactionsinagivenstateRegressionplannersbackwardstate-spacesearchToachieveagoal,whatmusthavebeentrueinthepreviousstate?ProgressionandregressionProgressionalgorithmFormulationasstate-spacesearchproblem:Initialstate=initialstateoftheplanningproblemLiteralsnotappearingarefalseActions=thosewhosepreconditionsaresatisfiedAddpositiveeffects,deletenegativeGoaltest=doesthestatesatisfythegoal?Stepcost=eachactioncosts1Nofunctions…anygraphsearchthatiscompleteisacompleteplanningalgorithm.Inefficient:(1)irrelevantactionproblem(2)goodheuristicrequiredforefficientsearchRegressionalgorithmHowtodeterminepredecessors?Whatarethestatesfromwhichapplyingagivenactionleadstothegoal?Goalstate=At(C1,B)At(C2,B)…At(C20,B)Relevantactionforfirstconjunct:Unload(C1,p,B)Worksonlyifpre-conditionsaresatisfied.Previousstate=In(C1,p)At(p,B)At(C2,B)…At(C20,B)SubgoalAt(C1,B)shouldnotbepresentinthisstate.Actionsmustnotundodesiredliterals(consistent)Mainadvantage:onlyrelevantactionsareconsidered.Oftenmuchlowerbranchingfactorthanforwardsearch.Regressionalgorithm(2)GeneralprocessforpredecessorconstructionGiveagoaldescriptionGLetAbeanactionthatisrelevantandconsistentThepredecessorsisasfollows:AnypositiveeffectsofAthatappearinGaredeleted.EachpreconditionliteralofAisadded,unlessitalreadyappears.Anystandardsearchalgorithmcanbeaddedtoperformthesearch.Terminationwhenpredecessorsatisfiedbyinitialstate.InFOcase,satisfactionmightrequireasubstitution.Heuristicsforstate