PlanningChapter 11Chapter 11 1Outline♦ Search vs. planning♦ STRIPS operators♦ Partial-order planningChapter 11 2Search vs. planningConsider the task get milk, bananas, and a cordless drillStandard search algorithms seem to fail miserably:. . .Buy Tuna FishBuy ArugulaBuy MilkGo To ClassBuy a DogTalk to ParrotSit Some MoreRead A Book...Go To SupermarketGo To SleepRead A BookGo To SchoolGo To Pet StoreEtc. Etc. ...Sit in ChairStartFinishAfter-the-fact heuristic/goal test inadequateChapter 11 3Search vs. planning contd.Planning systems do the following:1) open up action and goal representation to allow selection2) divide-and-conquer by subgoaling3) relax requirement for sequential construction of solutionsSearch PlanningStates Lisp data structures Logical sentencesActionsLisp code Preconditions/outcomesGoalLisp code Logical sentence (conjunction)PlanSequence from S0Constraints on actionsChapter 11 4STRIPS operatorsTidily arranged actions descriptions, restricted languageAction: Buy(x)Have(x)At(p) Sells(p,x)Buy(x)Precondition: At(p), Sells(p, x)Effect: Have(x)[Note: this abstracts away many important details!]Restricted language ⇒ efficient algorithmPrecondition: conjunction of positive literalsEffect: conjunction of literalsA complete set of STRIPS operators can be translatedinto a set of successor-state axiomsChapter 11 5Partially ordered plansPartially ordered collection of steps withStart step has the initial state description as its effectFinish step has the goal description as its preconditioncausal links from outcome of one step to precondition of anothertemporal ordering between pairs of stepsOpen condition = precondition of a step not yet causally linkedAplaniscomplete iff every precondition is achievedA precondition is achieved iff it is the effect of an earlier stepand no possibly intervening step undoes itChapter 11 6ExampleFinishStartAt(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)Sells(HWS,Drill)At(Home) Sells(SM,Ban.)Chapter 11 7ExampleBuy(Drill)Buy(Milk)Go(SM)FinishStartAt(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(HWS,Drill)At(HWS)At(x)Sells(SM,Milk)Sells(HWS,Drill)At(Home) Sells(SM,Ban.)Chapter 11 8ExampleAt(SM)At(Home)At(HWS)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartAt(Home) Have(Ban.) Have(Drill)Have(Milk)Sells(SM,Milk)At(SM)Sells(SM,Ban.)At(SM)Sells(HWS,Drill)At(HWS)Chapter 11 9Planning processOperators on partial plans:add a link from an existing action to an open conditionadd a step to fulfill an open conditionorder one step wrt another to remove possible conflictsGradually move from incomplete/vague plans to complete, correct plansBacktrack if an open condition is unachievable orif a conflict is unresolvableChapter 11 10POP algorithm sketchfunction POP(initial, goal, operators) returns planplan ← Make-Minimal-Plan(initial, goal)loop doif Solution?( plan) then return planSneed,c← Select-Subgoal( plan)Choose-Operator( plan, operators, Sneed, c)Resolve-Threats( plan)endfunction Select-Subgoal( plan) returns Sneed,cpick a plan step Sneedfrom Steps( plan)with a precondition c that has not been achievedreturn Sneed,cChapter 11 11POP algorithm contd.procedure Choose-Operator(plan, operators, Sneed,c)choose a step Saddfrom operators or Steps( plan)thathasc as an effectif there is no such step then failadd the causal link Saddc−→Sneedto Links( plan)add the ordering constraint Sadd≺ Sneedto Orderings( plan)if Saddis a newly added step from operators thenadd Saddto Steps( plan)add Start ≺ Sadd≺ Finish to Orderings( plan)procedure Resolve-Threats(plan)for each Sthreatthat threatens a link Sic−→Sjin Links( plan) dochoose eitherDemotion: Add Sthreat≺ Sito Orderings( plan)Promotion: Add Sj≺ Sthreatto Orderings( plan)if not Consistent( plan) then failendChapter 11 12Clobbering and promotion/demotionA clobberer is a potentially intervening step that destroys the conditionachieved by a causal link. E.g., Go(Home) clobbers At(Supermarket):FinishAt(Home)At(Home)Go(Home)DEMOTIONPROMOTIONGo(Supermarket)At(Supermarket)Buy(Milk)Demotion: put before Go(Supermarket)Promotion: put after Buy(Milk)Chapter 11 13Properties of POPNondeterministic algorithm: backtracks at choice points on failure:–choiceofSaddto achieve Sneed– choice of demotion or promotion for clobberer– selection of Sneedis irrevocablePOP is sound, complete, and systematic (no repetition)Extensions for disjunction, universals, negation, conditionalsCan be made efficient with good heuristics derived from problem descriptionParticularly good for problems with many loosely related subgoalsChapter 11 14Example: Blocks worldStart State Goal StateBACABCPutOn(x,y)Clear(x) On(x,z) Clear(y)~On(x,z) ~Clear(y) Clear(z) On(x,y)PutOnTable(x)Clear(x) On(x,z)~On(x,z) Clear(z) On(x,Table)+ several inequality constraints"Sussman anomaly" problemChapter 11 15Example contd.B ACABCFINISHOn(A,B) On(B,C)STARTOn(C,A) On(A,Table) Cl(B) On(B,Table) Cl(C)Chapter 11 16Example contd.B ACABCFINISHSTARTOn(C,A) On(A,Table) Cl(B) On(B,Table) Cl(C)PutOn(B,C)Cl(B) On(B,z) Cl(C)On(A,B) On(B,C)Chapter 11 17Example contd.B ACABCFINISHOn(A,B) On(B,C)STARTOn(C,A) On(A,Table) Cl(B) On(B,Table) Cl(C)PutOn(B,C)PutOn(A,B)PutOn(A,B)clobbers Cl(B)=> order after PutOn(B,C)On(A,z) Cl(B)Cl(A)On(B,z) Cl(C)Cl(B)Chapter 11 18Example contd.B ACABCFINISHOn(A,B) On(B,C)STARTOn(C,A) On(A,Table) Cl(B) On(B,Table) Cl(C)PutOn(B,C)Cl(B) On(B,z) Cl(C)PutOn(A,B)Cl(A) On(A,z) Cl(B)PutOn(A,B)clobbers Cl(B)=> order after PutOn(B,C)PutOnTable(C)PutOn(B,C)clobbers Cl(C)=> order afterPutOnTable(C)Cl(C)On(C,z)Chapter 11