Planning and ActingChapter 12Chapter 12 1Outline♦ The real world♦ Conditional planning♦ Monitoring and replanningChapter 12 2The real world~Flat(Spare) Intact(Spare) Off(Spare) On(Tire1) Flat(Tire1)START FINISHOn(x) ~Flat(x)Remove(x)On(x)Off(x) ClearHubPuton(x)Off(x) ClearHubOn(x) ~ClearHubInflate(x)Intact(x) Flat(x)~Flat(x)Chapter 12 3Things go wrongIncomplete informationUnknown preconditions, e.g., Intact(Spare)?Disjunctive effects, e.g., Inflate(x) causesInflated(x) ∨ SlowHiss(x) ∨ Burst(x) ∨ BrokenP ump ∨ . . .Incorrect informationCurrent state incorrect, e.g., spare NOT intactMissing/incorrect postconditions in operatorsQualification problem:can never finish listing all the required preconditions andpossible conditional outcomes of actionsChapter 12 4SolutionsConformant or sensorless planningDevise a plan that works regardless of state or outcomeSuch plans may not existConditional planningPlan to obtain information (observation actions)Subplan for each contingency, e.g.,[Check(T ire1), if Intact(T ire1) then Inflate(T ire1) else CallAAAExpensive because it plans for many unlikely casesMonitoring/ReplanningAssume normal states, outcomesCheck progressduring execution, replan if necessaryUnanticipated outcomes may lead to failure (e.g., no AAA card)(Really need a combination; plan for likely/serious eventualities,deal with others when they arise, as they must eventually)Chapter 12 5Conformant planningSearch in space of belief states (sets of possible actual states)LRL RSL RS SS SRLS SLRRLRLChapter 12 6Conditional planningIf the world is nondeterministic or partially observablethen percepts usuallyprovide information,i.e.,split up the belief stateACTIONPERCEPTChapter 12 7Conditional planning contd.Conditional plans check (any consequence of KB +) percept[. . . , if C then P lanAelse P lanB, . . .]Execution: check C against current KB, execute “then” or “else”Need some plan for every possible percept(Cf. game playing: some response for every opponent move)(Cf. backward chaining:some rule such that every premise satisfiedAND–OR tree search (very similar to backward chaining algorithm)Chapter 12 8ExampleDouble Murphy: sucking or arriving may dirty a clean square8 3 6 8 7 1 5 7 8 4 2 Left SuckRight Suck Left SuckGOALGOALLOOPLOOPChapter 12 9ExampleTriple Murphy: also sometimes stays put instead of moving8 Left Suck6 3 7 GOAL[L1: Left, if AtR then L1else [if CleanL then [ ] else Suck]]or [while AtR do [Left], if CleanL then [ ] else Suck]“Infinite loop” but will eventually work unless action always failsChapter 12 10Execution Monitoring“Failure” = preconditions of remaining plan not metPreconditions of remaining plan= a ll preconditions of remaining steps not achieved by remaining steps= all causal links crossing current time pointOn failure, resume POP to achieve open conditions from current stateIPEM (Integrated Planning, Execution, and Monitoring):keep updating Start to match current statelinks from actions replaced by links from Start when doneChapter 12 11ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartSells(SM,Milk)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)At(Home)Sells(SM,Ban.)Sells(HWS,Drill)Chapter 12 12ExampleAt(SM)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartSells(SM,Milk)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)Sells(SM,Ban.)Sells(HWS,Drill)At(HWS)At(Home)Chapter 12 13ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartAt(HWS)Have(Drill)Sells(SM,Ban.)Sells(SM,Milk)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)Chapter 12 14ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartHave(Drill)Sells(SM,Ban.)Sells(SM,Milk)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)At(SM)Chapter 12 15ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartHave(Drill)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)At(SM)Have(Ban.)Have(Milk)Chapter 12 16ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartHave(Drill)At(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)Have(Ban.)Have(Milk)At(Home)Chapter 12 17Emergent behaviorSTARTGet(Red)Color(Chair,Blue) ~Have(Red)Paint(Red)Have(Red)FINISHColor(Chair,Red)FAILURE RESPONSEHave(Red) PRECONDITIONSFetch more redChapter 12 18Emergent behaviorSTARTGet(Red)Color(Chair,Blue) ~Have(Red)Paint(Red)Have(Red)FINISHColor(Chair,Red)FAILURE RESPONSE PRECONDITIONSColor(Chair,Red) Extra coat of paintChapter 12 19Emergent behaviorSTARTGet(Red)Color(Chair,Blue) ~Have(Red)Paint(Red)Have(Red)FINISHColor(Chair,Red)FAILURE RESPONSE PRECONDITIONSColor(Chair,Red) Extra coat of paint“Loop until success” behavior emerges from interaction between monitor/replanagent design and uncooperative environmentChapter 12