規(guī)劃規(guī)劃：提出能達(dá)到一定目標(biāo)的行動(dòng)序列的任務(wù)基于搜索的問(wèn)題智能體邏輯規(guī)劃智能體規(guī)劃環(huán)境經(jīng)典的：完全可觀(guān)察、確定性的、有限的、靜態(tài)的以及離散的。非經(jīng)典：部分可觀(guān)察或隨機(jī)致謝：本講義部分內(nèi)容來(lái)自TomLenaert@http://iridia.ulb.ac.be/~tlenaert/teach/slides/AIMA/規(guī)劃規(guī)劃：提出能達(dá)到一定目標(biāo)的行動(dòng)序列的任務(wù)致謝：本講義部分1主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題2現(xiàn)實(shí)世界問(wèn)題的困難假設(shè)一個(gè)問(wèn)題智能使用標(biāo)準(zhǔn)的搜索算法…什么樣的行動(dòng)是相關(guān)的？例子：購(gòu)買(mǎi)“人工智能教材”，假設(shè)對(duì)于每一個(gè)10位數(shù)字的ISBN號(hào)碼都有一個(gè)購(gòu)買(mǎi)行動(dòng)遍歷搜索vs.后項(xiàng)搜索如何尋找一個(gè)好的啟發(fā)函數(shù)？例如在線(xiàn)購(gòu)買(mǎi)4本不同的書(shū)，4個(gè)步驟共有1040規(guī)劃狀態(tài)耗散的估計(jì)：所要買(mǎi)書(shū)的剩余數(shù)目應(yīng)是一個(gè)好的估計(jì)。Problem-dependentvs.

–independent：?jiǎn)l(fā)函數(shù)取未滿(mǎn)足的合取式的數(shù)目如何將問(wèn)題分解？假設(shè)大部分現(xiàn)實(shí)世界問(wèn)題是近似可分解的：需要做些附加工作來(lái)合并子規(guī)劃現(xiàn)實(shí)世界問(wèn)題的困難假設(shè)一個(gè)問(wèn)題智能使用標(biāo)準(zhǔn)的搜索算法…3PlanninglanguageWhatisagoodlanguage?Expressiveenoughtodescribeawidevarietyofproblems.Restrictiveenoughtoallowefficientalgorithmstooperateonit.Planningalgorithmshouldbeabletotakeadvantageofthelogicalstructureoftheproblem.STRIPSandADLPlanninglanguageWhatisagoo4GenerallanguagefeaturesRepresentationofstatesDecomposetheworldinlogicalconditionsandrepresentastateasaconjunctionofpositiveliterals(atomicsentences)Propositionalliterals:PoorUnknownFO-literals(groundedandfunction-free):At(Plane1,Melbourne)At(Plane2,Sydney)Closedworldassumption:conditionsnotmentionedareassumedfalseRepresentationofgoalsPartiallyspecifiedstateandrepresentedasaconjunctionofpositivegroundliteralsAgoalissatisfiedifthestatecontainsallliteralsingoal.GenerallanguagefeaturesRepre5Generallanguagefeatures(2)RepresentationsofactionsAction=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)ActionnameandparameterlistPrecondition(conj.offunction-freeliterals)Effect(conjoffunction-freeliteralsandPisTrueandPisfalse)Add-listvsdelete-listinEffectGenerallanguagefeatures(2)R6LanguagesemanticsHowdoactionsaffectstates?Anactionisapplicableinanystatethatsatisfiestheprecondition.ForFOactionschemaapplicabilityinvolvesasubstitutionforthevariablesinthePRECOND.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.LanguagesemanticsHowdoactio7Languagesemantics(2)Theresultofexecutingactionainstatesisthestates’

s’issameassexceptAnypositiveliteralPintheeffectofaisaddedtosAnynegativeliteral?PisremovedfromsExampleinpreviouspage:At(P1,SFO)At(P2,SFO)Plane(P1)Plane(P2)Airport(JFK)Airport(SFO)STRIPSassumption:avoidsrepresentationalframeproblemeveryliteralNOTintheeffectremainsunchangedSolutionisasequencesuchthatini→goalLanguagesemantics(2)Theresu8ExpressivenessandextensionsSTRIPSissimplifiedImportantlimit:function-freeliteralsAllowsforpropositionalrepresentationFunctionsymbolsleadtoinfinitelymanystatesandactionsRecentextension:ActionDescriptionlanguage(ADL)Action(Fly(p:Plane,from:Airport,to:Airport), PRECOND:At(p,from)(fromto) EFFECT:?At(p,from)At(p,to))Standardization:Planningdomaindefinitionlanguage(PDDL)ExpressivenessandextensionsS9例子：積木世界一組放在桌子上的立方體積木，積木能夠被疊放，但是只有一塊積木能夠直接放在另一塊的上面。一個(gè)機(jī)器臂能夠拿起一塊積木并把它移到別的位置，無(wú)論是在桌子上還是在另一塊積木上。機(jī)器臂每次只能拿起一塊積木。例子：積木世界一組放在桌子上的立方體積木，積木能夠被疊放，但10ExamplesofplanninginBlocksWorldInit(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)(bx)(by)(xy)

EFFECT:On(b,y)Clear(x)?On(b,x)?Clear(y)Action(MoveToTable(b,x)) PRECOND:On(b,x)

Clear(b)Block(b)(bx) EFFECT:On(b,Table)Clear(x)

?On(b,x))Note:weintroducexytoblockspuriousactionssuchasMove(B,C,C)注意負(fù)文字ExamplesofplanninginBlocks11主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題12狀態(tài)空間搜索規(guī)劃前向搜索后向搜索啟發(fā)式函數(shù)狀態(tài)空間搜索規(guī)劃前向搜索13Planningwithstate-spacesearchBothforwardandbackwardsearchpossibleProgressionplannersforwardstate-spacesearchConsidertheeffectofallpossibleactionsinagivenstateRegressionplannersbackwardstate-spacesearchToachieveagoal,whatmusthavebeentrueinthepreviousstate?Planningwithstate-spacesear14ProgressionandregressionProgressionandregression15ProgressionalgorithmFormulationasstate-spacesearchproblem:Initialstate=initialstateoftheplanningproblemLiteralsnotappearingarefalseActions=thosewhosepreconditionsaresatisfiedAddpositiveeffects,deletenegativeGoaltest=doesthestatesatisfythegoal?Stepcost=eachactioncosts1Nofunctions…anygraphsearchthatiscompleteisacompleteplanningalgorithm.Inefficient:(1)irrelevantactionproblem(2)goodheuristicrequiredforefficientsearchProgressionalgorithmFormulati16RegressionalgorithmHowtodeterminepredecessors?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.RegressionalgorithmHowtodet17Regressionalgorithm (2)GeneralprocessforpredecessorconstructionGiveagoaldescriptionGLetAbeanactionthatisrelevantandconsistentThepredecessorsisasfollows:AnypositiveeffectsofAthatappearinGaredeleted.EachpreconditionliteralofAisadded,unlessitalreadyappears.Anystandardsearchalgorithmcanbeaddedtoperformthesearch.Terminationwhenpredecessorsatisfiedbyinitialstate.InFOcase,satisfactionmightrequireasubstitution.Regressionalgorithm (2)Genera18Heuristicsforstate-spacesearchNeitherprogressionorregressionareveryefficientwithoutagoodheuristic.Howmanyactionsareneededtoachievethegoal?ExactsolutionisNPhard,findagoodestimateTwoapproachestofindadmissibleheuristic:Theoptimalsolutiontotherelaxedproblem.RemoveallpreconditionsfromactionsThesubgoalindependenceassumption:Thecostofsolvingaconjunctionofsubgoalsisapproximatedbythesumofthecostsofsolvingthesubproblemsindependently.Heuristicsforstate-spacesea19主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題20Partial-orderplanningProgressionandregressionplanningaretotallyorderedplansearchforms.Theycannottakeadvantageofproblemdecomposition.DecisionsmustbemadeonhowtosequenceactionsonallthesubproblemsLeastcommitmentstrategy:DelaychoiceduringsearchStartfrom“obvious”and“important”decisionsPartial-orderplanningProgress21ShoeexampleGoal(RightShoeOnLeftShoeOn)Init()Action(RightShoe, PRECOND:RightSockOn EFFECT:RightShoeOn)Action(RightSock, PRECOND: EFFECT:RightSockOn)Action(LeftShoe, PRECOND:LeftSockOn EFFECT:LeftShoeOn)Action(LeftSock, PRECOND: EFFECT:LeftSockOn)Planner:processtwoactionsequences(1)leftsock,leftshoe(2)rightsock,rightshoeindependentlyandcombinethemtogetherpartialorderplanningShoeexampleGoal(RightShoeOn22Partial-orderplanningAnyplanningalgorithmthatcanplacetwoactionsintoaplanwithoutwhichcomesfirstisaPOL.Partial-orderplanningAnyplan23POLasasearchproblemStatesare(mostlyunfinished)plans.Theemptyplancontainsonlystartandfinishactions.Eachplanhas4components:Asetofactions(stepsoftheplan)Asetoforderingconstraints:A<BCyclesrepresentcontradictions.AsetofcausallinksTheplanmaynotbeextendedbyaddinganewactionCthatconflictswiththecausallink.(iftheeffectofCis?pandifCcouldcomeafterAandbeforeB)Asetofopenpreconditions.Ifpreconditionisnotachievedbyactionintheplan.POLasasearchproblemStates24POLasasearchproblem(2)Aplanisconsistentifftherearenocyclesintheorderingconstraintsandnoconflictswiththecausallinks.Aconsistentplanwithnoopenpreconditionsisasolution.Apartialorderplanisexecutedbyrepeatedlychoosinganyofthepossiblenextactions.Thisflexibilityisabenefitinnon-cooperativeenvironmentsAlsomakeiteasyformergingsmallplanningsintoalargeplanningPOLasasearchproblem(2)Ap25SolvingPOLAssumepropositionalplanningproblems: TheinitialplancontainsStartandFinish,theorderingconstraintStart<Finish,nocausallinks,allthepreconditionsinFinishareopen.Successorfunction:picksoneopenpreconditionponanactionBandgeneratesasuccessorplanforeverypossibleconsistentwayofchoosingactionAthatachievesp.Testgoal,alsocheckifthesetofopenconditionsisempty.SolvingPOLAssumepropositiona26EnforcingconsistencyWhengeneratingsuccessorplan:ThecausallinkA--p->BandtheorderingconstraingA<Bisaddedtotheplan.IfAisnewalsoaddstart<AandA<BtotheplanResolveconflictsbetweennewcausallinkandallexistingactionsResolveconflictsbetweenactionA(ifnew)andallexistingcausallinks.EnforcingconsistencyWhengene27ProcesssummaryOperatorsonpartialplansAddlinkfromexistingplantoopenprecondition.Addasteptofulfillanopencondition.Orderonestepw.r.tanothertoremovepossibleconflictsGraduallymovefromincomplete/vagueplanstocomplete/correctplansBacktrackifanopenconditionisunachievableorifaconflictisunresolvable.ProcesssummaryOperatorsonpa28Example:SparetireproblemInit(At(Flat,Axle)At(Spare,trunk))Goal(At(Spare,Axle))Action(Remove(Spare,Trunk) PRECOND:At(Spare,Trunk)

EFFECT:?At(Spare,Trunk)At(Spare,Ground))

Action(Remove(Flat,Axle) PRECOND:At(Flat,Axle)

EFFECT:?At(Flat,Axle)At(Flat,Ground))

Action(PutOn(Spare,Axle) PRECOND:At(Spare,Groundp)?At(Flat,Axle) EFFECT:At(Spare,Axle)?Ar(Spare,Ground))Action(LeaveOvernight PRECOND: EFFECT:?At(Spare,Ground)?At(Spare,Axle)?At(Spare,trunk)?At(Flat,Ground)?At(Flat,Axle))Example:SparetireproblemIni29SolvingtheproblemIntialplan:StartwithEFFECTSandFinishwithPRECOND.SolvingtheproblemIntialplan30SolvingtheproblemIntialplan:StartwithEFFECTSandFinishwithPRECOND.Pickanopenprecondition:At(Spare,Axle)OnlyPutOn(Spare,Axle)isapplicableAddcausallink:Addconstraint:PutOn(Spare,Axle)

<FinishSolvingtheproblemIntialplan31SolvingtheproblemPickanopenprecondition:At(Spare,Ground)OnlyRemove(Spare,Trunk)isapplicableAddcausallink:Addconstraint:Remove(Spare,Trunk)

<PutOn(Spare,Axle)SolvingtheproblemPickanope32SolvingtheproblemPickanopenprecondition:At(Spare,Axle)LeaveOverNightisapplicableconflict:Toresolve,addconstraint:LeaveOverNight

<Remove(Spare,Trunk)Addcausallink:SolvingtheproblemPickanope33SolvingtheproblemPickanopenprecondition:At(Spare,Trunk)OnlyStartisapplicableAddcausallink:Conflict:ofcausallinkwitheffectAt(Spare,Trunk)inLeaveOverNightNore-orderingsolutionpossible.backtrackSolvingtheproblemPickanope34SolvingtheproblemRemoveLeaveOverNightanditscausallinksAgainchooseanapplicableactionforAt(Spare,Axle):RemoveFlatAxleischosenAddcasuallinkAddconstraintStart<RemoveFlatAxleCheckconsistencyandOkChooseStarttoobtainthepreconditionofRemoveFlatAxleFinishSolvingtheproblemRemoveLeav35Somedetails…Whathappenswhenafirst-orderrepresentationthatincludesvariablesisused?Complicatestheprocessofdetectingandresolvingconflicts.Canberesolvedbyintroducinginequalityconstrainst.CSP’smost-constrained-variableconstraintcanbeusedforplanningalgorithmstoselectaPRECOND.Somedetails…Whathappenswhe36HW11.4HW11.437PlanningwithpropositionallogicPlanningcanbedonebyprovingtheoreminsituationcalculus.Here:testthesatisfiabilityofalogicalsentence:Sentencecontainspropositionsforeveryactionoccurrence.AmodelwillassigntruetotheactionsthatarepartofthecorrectplanandfalsetotheothersAnassignmentthatcorrespondstoanincorrectplanwillnotbeamodelbecauseofinconsistencywiththeassertionthatthegoalistrue.Iftheplanningisunsolvablethesentencewillbeunsatisfiable.Planningwithpropositionallo38SATPLANalgorithmfunctionSATPLAN(problem,Tmax)return

solutionorfailure inputs:problem,aplanningproblem

Tmax,anupperlimittotheplanlength

forT=0toTmaxdo

cnf,mapping

TRANSLATE-TO_SAT(problem,T)

assignment

SAT-SOLVER(cnf) ifassignmentisnotnullthen

returnEXTRACT-SOLUTION(assignment,mapping)

returnfailureSATPLANalgorithmfunctionSATP39cnf,mapping

TRANSLATE-TO_SAT(problem,T)Distinctpropositionsforassertionsabouteachtimestep.SuperscriptsdenotethetimestepAt(P1,SFO)0

At(P2,JFK)0NoCWAthusspecifywhichpropositionsarenottrue?At(P1,JFK)0

?At(P2,SFO)0\Unknownpropositionsareleftunspecified.Thegoalisassociatedwithaparticulartime-stepButwhichone?cnf,mappingTRANSLATE-TO_SA40cnf,mapping

TRANSLATE-TO_SAT(problem,T)Howtodeterminethetimestepwherethegoalwillbereached?StartatT=0AssertAt(P1,SFO)0

At(P2,JFK)0Failure..TryT=1AssertAt(P1,SFO)1

At(P2,JFK)1…Repeatthisuntilsomeminimalpathlengthisreached.TerminationisensuredbyTmaxcnf,mappingTRANSLATE-TO_SA41cnf,mapping

TRANSLATE-TO_SAT(problem,T)HowtoencodeactionsintoPL?Propositionalversionsofsuccessor-stateaxiomsAt(P1,JFK)1

(At(P1,JFK)0

?(Fly(P1,JFK,SFO)0

At(P1,JFK)0))(Fly(P1,SFO,JFK)0

At(P1,SFO)0)Suchanaxiomisrequiredforeachplane,airportandtimestepIfmoreairportsaddanotherwaytotravelthanadditionaldisjunctsarerequiredOncealltheseaxiomsareinplace,f,mappingTRANSLATE-TO_SA42assignment

SAT-SOLVER(cnf)MultiplemodelscanbefoundTheyareNOTsatisfactory:(forT=1)Fly(P1,SFO,JFK)0

Fly(P1,JFK,SFO)0Fly(P2,JFK.SFO)0ThesecondactionisinfeasibleYettheplanISamodelofthesentenceAvoidingillegalactions:pre-conditionaxioms

Fly(P1,SFO,JFK)0

At(P1,JFK)ExactlyonemodelnowsatisfiesalltheaxiomswherethegoalisachievedatT=1.assignmentSAT-SOLVER(cnf)Mu43assignment

SAT-SOLVER(cnf)AplanecanflyattwodestinationsatonceTheyareNOTsatisfactory:(forT=1)Fly(P1,SFO,JFK)0

Fly(P2,JFK,SFO)0Fly(P2,JFK.LAX)0ThesecondactionisinfeasibleYettheplanallowsspuriousrelationsAvoidspurioussolutions:action-exclusionaxioms ?(Fly(P2,JFK,SFO)0

Fly(P2,JFK,LAX))PreventssimultaneousactionsLostofflexibilitysinceplanbecomestotallyordered:noactionsareallowedtooccuratthesametime.RestrictexclusiontopreconditionsassignmentSAT-SOLVER(cnf)A44AnalysisofplanningapproachPlanningisanareaofgreatinterestwithinAISearchforsolutionConstructivelyproveaexistenceofsolutionBiggestproblemisthecombinatorialexplosioninstates.EfficientmethodsareunderresearchE.g.divide-and-conquerAnalysisofplanningapproachP45HWCh2-Ch11學(xué)習(xí)心得HWCh2-Ch11學(xué)習(xí)心得46規(guī)劃規(guī)劃：提出能達(dá)到一定目標(biāo)的行動(dòng)序列的任務(wù)基于搜索的問(wèn)題智能體邏輯規(guī)劃智能體規(guī)劃環(huán)境經(jīng)典的：完全可觀(guān)察、確定性的、有限的、靜態(tài)的以及離散的。非經(jīng)典：部分可觀(guān)察或隨機(jī)致謝：本講義部分內(nèi)容來(lái)自TomLenaert@http://iridia.ulb.ac.be/~tlenaert/teach/slides/AIMA/規(guī)劃規(guī)劃：提出能達(dá)到一定目標(biāo)的行動(dòng)序列的任務(wù)致謝：本講義部分47主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題48現(xiàn)實(shí)世界問(wèn)題的困難假設(shè)一個(gè)問(wèn)題智能使用標(biāo)準(zhǔn)的搜索算法…什么樣的行動(dòng)是相關(guān)的？例子：購(gòu)買(mǎi)“人工智能教材”，假設(shè)對(duì)于每一個(gè)10位數(shù)字的ISBN號(hào)碼都有一個(gè)購(gòu)買(mǎi)行動(dòng)遍歷搜索vs.后項(xiàng)搜索如何尋找一個(gè)好的啟發(fā)函數(shù)？例如在線(xiàn)購(gòu)買(mǎi)4本不同的書(shū)，4個(gè)步驟共有1040規(guī)劃狀態(tài)耗散的估計(jì)：所要買(mǎi)書(shū)的剩余數(shù)目應(yīng)是一個(gè)好的估計(jì)。Problem-dependentvs.

–independent：?jiǎn)l(fā)函數(shù)取未滿(mǎn)足的合取式的數(shù)目如何將問(wèn)題分解？假設(shè)大部分現(xiàn)實(shí)世界問(wèn)題是近似可分解的：需要做些附加工作來(lái)合并子規(guī)劃現(xiàn)實(shí)世界問(wèn)題的困難假設(shè)一個(gè)問(wèn)題智能使用標(biāo)準(zhǔn)的搜索算法…49PlanninglanguageWhatisagoodlanguage?Expressiveenoughtodescribeawidevarietyofproblems.Restrictiveenoughtoallowefficientalgorithmstooperateonit.Planningalgorithmshouldbeabletotakeadvantageofthelogicalstructureoftheproblem.STRIPSandADLPlanninglanguageWhatisagoo50GenerallanguagefeaturesRepresentationofstatesDecomposetheworldinlogicalconditionsandrepresentastateasaconjunctionofpositiveliterals(atomicsentences)Propositionalliterals:PoorUnknownFO-literals(groundedandfunction-free):At(Plane1,Melbourne)At(Plane2,Sydney)Closedworldassumption:conditionsnotmentionedareassumedfalseRepresentationofgoalsPartiallyspecifiedstateandrepresentedasaconjunctionofpositivegroundliteralsAgoalissatisfiedifthestatecontainsallliteralsingoal.GenerallanguagefeaturesRepre51Generallanguagefeatures(2)RepresentationsofactionsAction=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)ActionnameandparameterlistPrecondition(conj.offunction-freeliterals)Effect(conjoffunction-freeliteralsandPisTrueandPisfalse)Add-listvsdelete-listinEffectGenerallanguagefeatures(2)R52LanguagesemanticsHowdoactionsaffectstates?Anactionisapplicableinanystatethatsatisfiestheprecondition.ForFOactionschemaapplicabilityinvolvesasubstitutionforthevariablesinthePRECOND.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.LanguagesemanticsHowdoactio53Languagesemantics(2)Theresultofexecutingactionainstatesisthestates’

s’issameassexceptAnypositiveliteralPintheeffectofaisaddedtosAnynegativeliteral?PisremovedfromsExampleinpreviouspage:At(P1,SFO)At(P2,SFO)Plane(P1)Plane(P2)Airport(JFK)Airport(SFO)STRIPSassumption:avoidsrepresentationalframeproblemeveryliteralNOTintheeffectremainsunchangedSolutionisasequencesuchthatini→goalLanguagesemantics(2)Theresu54ExpressivenessandextensionsSTRIPSissimplifiedImportantlimit:function-freeliteralsAllowsforpropositionalrepresentationFunctionsymbolsleadtoinfinitelymanystatesandactionsRecentextension:ActionDescriptionlanguage(ADL)Action(Fly(p:Plane,from:Airport,to:Airport), PRECOND:At(p,from)(fromto) EFFECT:?At(p,from)At(p,to))Standardization:Planningdomaindefinitionlanguage(PDDL)ExpressivenessandextensionsS55例子：積木世界一組放在桌子上的立方體積木，積木能夠被疊放，但是只有一塊積木能夠直接放在另一塊的上面。一個(gè)機(jī)器臂能夠拿起一塊積木并把它移到別的位置，無(wú)論是在桌子上還是在另一塊積木上。機(jī)器臂每次只能拿起一塊積木。例子：積木世界一組放在桌子上的立方體積木，積木能夠被疊放，但56ExamplesofplanninginBlocksWorldInit(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)(bx)(by)(xy)

EFFECT:On(b,y)Clear(x)?On(b,x)?Clear(y)Action(MoveToTable(b,x)) PRECOND:On(b,x)

Clear(b)Block(b)(bx) EFFECT:On(b,Table)Clear(x)

?On(b,x))Note:weintroducexytoblockspuriousactionssuchasMove(B,C,C)注意負(fù)文字ExamplesofplanninginBlocks57主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題58狀態(tài)空間搜索規(guī)劃前向搜索后向搜索啟發(fā)式函數(shù)狀態(tài)空間搜索規(guī)劃前向搜索59Planningwithstate-spacesearchBothforwardandbackwardsearchpossibleProgressionplannersforwardstate-spacesearchConsidertheeffectofallpossibleactionsinagivenstateRegressionplannersbackwardstate-spacesearchToachieveagoal,whatmusthavebeentrueinthepreviousstate?Planningwithstate-spacesear60ProgressionandregressionProgressionandregression61ProgressionalgorithmFormulationasstate-spacesearchproblem:Initialstate=initialstateoftheplanningproblemLiteralsnotappearingarefalseActions=thosewhosepreconditionsaresatisfiedAddpositiveeffects,deletenegativeGoaltest=doesthestatesatisfythegoal?Stepcost=eachactioncosts1Nofunctions…anygraphsearchthatiscompleteisacompleteplanningalgorithm.Inefficient:(1)irrelevantactionproblem(2)goodheuristicrequiredforefficientsearchProgressionalgorithmFormulati62RegressionalgorithmHowtodeterminepredecessors?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.RegressionalgorithmHowtodet63Regressionalgorithm (2)GeneralprocessforpredecessorconstructionGiveagoaldescriptionGLetAbeanactionthatisrelevantandconsistentThepredecessorsisasfollows:AnypositiveeffectsofAthatappearinGaredeleted.EachpreconditionliteralofAisadded,unlessitalreadyappears.Anystandardsearchalgorithmcanbeaddedtoperformthesearch.Terminationwhenpredecessorsatisfiedbyinitialstate.InFOcase,satisfactionmightrequireasubstitution.Regressionalgorithm (2)Genera64Heuristicsforstate-spacesearchNeitherprogressionorregressionareveryefficientwithoutagoodheuristic.Howmanyactionsareneededtoachievethegoal?ExactsolutionisNPhard,findagoodestimateTwoapproachestofindadmissibleheuristic:Theoptimalsolutiontotherelaxedproblem.RemoveallpreconditionsfromactionsThesubgoalindependenceassumption:Thecostofsolvingaconjunctionofsubgoalsisapproximatedbythesumofthecostsofsolvingthesubproblemsindependently.Heuristicsforstate-spacesea65主要內(nèi)容規(guī)劃問(wèn)題規(guī)劃問(wèn)題語(yǔ)言：語(yǔ)法和語(yǔ)義狀態(tài)空間搜索規(guī)劃前向、后向利用問(wèn)題的表示的規(guī)劃算法偏序規(guī)劃命題邏輯規(guī)劃規(guī)劃方法分析主要內(nèi)容規(guī)劃問(wèn)題66Partial-orderplanningProgressionandregressionplanningaretotallyorderedplansearchforms.Theycannottakeadvantageofproblemdecomposition.DecisionsmustbemadeonhowtosequenceactionsonallthesubproblemsLeastcommitmentstrategy:DelaychoiceduringsearchStartfrom“obvious”and“important”decisionsPartial-orderplanningProgress67ShoeexampleGoal(RightShoeOnLeftShoeOn)Init()Action(RightShoe, PRECOND:RightSockOn EFFECT:RightShoeOn)Action(RightSock, PRECOND: EFFECT:RightSockOn)Action(LeftShoe, PRECOND:LeftSockOn EFFECT:LeftShoeOn)Action(LeftSock, PRECOND: EFFECT:LeftSockOn)Planner:processtwoactionsequences(1)leftsock,leftshoe(2)rightsock,rightshoeindependentlyandcombinethemtogetherpartialorderplanningShoeexampleGoal(RightShoeOn68Partial-orderplanningAnyplanningalgorithmthatcanplacetwoactionsintoaplanwithoutwhichcomesfirstisaPOL.Partial-orderplanningAnyplan69POLasasearchproblemStatesare(mostlyunfinished)plans.Theemptyplancontainsonlystartandfinishactions.Eachplanhas4components:Asetofactions(stepsoftheplan)Asetoforderingconstraints:A<BCyclesrepresentcontradictions.AsetofcausallinksTheplanmaynotbeextendedbyaddinganewactionCthatconflictswiththecausallink.(iftheeffectofCis?pandifCcouldcomeafterAandbeforeB)Asetofopenpreconditions.Ifpreconditionisnotachievedbyactionintheplan.POLasasearchproblemStates70POLasasearchproblem(2)Aplanisconsistentifftherearenocyclesintheorderingconstraintsandnoconflictswiththecausallinks.Aconsistentplanwithnoopenpreconditionsisasolution.Apartialorderplanisexecutedbyrepeatedlychoosinganyofthepossiblenextactions.Thisflexibilityisabenefitinnon-cooperativeenvironmentsAlsomakeiteasyformergingsmallplanningsintoalargeplanningPOLasasearchproblem(2)Ap71SolvingPOLAssumepropositionalplanningproblems: TheinitialplancontainsStartandFinish,theorderingconstraintStart<Finish,nocausallinks,allthepreconditionsinFinishareopen.Successorfunction:picksoneopenpreconditionponanactionBandgeneratesasuccessorplanforeverypossibleconsistentwayofchoosingactionAthatachievesp.Testgoal,alsocheckifthesetofopenconditionsisempty.SolvingPOLAssumepropositiona72EnforcingconsistencyWhengeneratingsuccessorplan:ThecausallinkA--p->BandtheorderingconstraingA<Bisaddedtotheplan.IfAisnewalsoaddstart<AandA<BtotheplanResolveconflictsbetweennewcausallinkandallexistingactionsResolveconflictsbetweenactionA(ifnew)andallexistingcausallinks.EnforcingconsistencyWhengene73ProcesssummaryOperatorsonpartialplansAddlinkfromexistingplantoopenprecondition.Addasteptofulfillanopencondition.Orderonestepw.r.tanothertoremovepossibleconflictsGraduallymovefromincomplete/vagueplanstocomplete/correctplansBacktrackifanopenconditionisunachievableorifaconflictisunresolvable.ProcesssummaryOperatorsonpa74Example:SparetireproblemInit(At(Flat,Axle)At(Spare,trunk))Goal(At(Spare,Axle))Action(Remove(Spare,Trunk) PRECOND:At(Spare,Trunk)

EFFECT:?At(Spare,Trunk)At(Spare,Ground))

Action(Remove(Flat,Axle) PRECOND:At(Flat,Axle)

EFFECT:?At(Flat,Axle)At(Flat,Ground))

Action(PutOn(Spare,Axle) PRECOND:At(Spare,Groundp)?At(Flat,Axle) EFFECT:At(Spare,Axle)?Ar(Spare,Ground))Action(LeaveOvernight PRECOND: EFFECT:?At(Spare,Ground)?At(Spare,Axle)?At(Spare,trunk)?At(Flat,Ground)?At(Flat,Axle))Example:SparetireproblemIni75SolvingtheproblemIntialplan:StartwithEFFECTSa