1Partial-Order Planning2State-Space vs. Plan-Space•State-space (situation space) planning algorithms searchthrough the space of possible states of the world searchingfor a path that solves the problem.•They can be based on progression: a forward search fromthe initial state looking for the goal state.•Or they can be based on regression: a backward searchfrom the goals towards the initial state•STRIPS is an incomplete regression-based algorithm.•Plan-space planners search through the space of partialplans, which are sets of actions that may not be totallyordered.•Partial-order planners are plan-based and only introduceordering constraints as necessary (least committment) inorder to avoid unecessarily searching through the space ofpossible orderings.3Partial Order Plans•Plan in which not all actions are orderedStartStartStartTotal Order Plans: Partial Order Plan:StartLeftSockLeftShoeSockRightShoeRightFinishStartFinishSockRightShoeRightSockLeftShoeLeftStartLeftSockShoeRightFinishRightSockLeftShoeFinishSockLeftRightSockShoeLeftRightShoeShoeRightFinishSockRightLeftSockLeftShoeFinishSockRightShoeLeftLeftSockRightShoeLeftSockOn RightSockOnLeftShoeOn, RightShoeOnStartSockRightShoeRightSockLeftShoeLeftFinish4Plans, Causal Links, and Threats•A plan is a three tuple <A, O, L>-A: A set of actions in the plan, {A1,A2,...An}-O: A set of ordering constraints on actions{Ai<Aj, Ak<Al,...Am<An}. These must be consistent, i.e.there must be at least one total ordering of actions in A that satisfy all the constraints.-B: A set of variable binding constraints {v=x,...}-L: a set of causal links showing how actions support each other•A causal link, Ap→QAc, indicates that action Ap has aneffect Q that achieves precondition Q for action Ac.•A threat, is an action At that can render a causal linkAp→QAcineffective because:-O ∪ {AP< At< Ac} is consistent-At has ¬Q as an effect5Threat Removal•Threats must be removed to prevent a plan from failing.•Demotion adds the constraint At< Apto prevent clobbering,i.e. push the clobberer before the producer.•Promotion adds the constraint Ac< At to preventclobbering, i.e. push the clobber after the consumer.cLcLcLc cc(a) (b) (c)S2S3S2S3S2S3S1S11S6Initial (Null) Plan•Initial plan has-A={ A0, A∞}-O={A0< A∞}-L ={}•A0(Start) has no preconditions but all facts in the initial stateas effects.•A∞ (Finish) has the goal conditions as preconditions and noeffects.Op( Action: Go(there); Precond: At(here); Effects: At(there), ¬At(here) )Op( Action: Buy(x), Precond: At(store), Sells(store,x); Effects: Have(x) )FinishStartHave(Drill) Have(Milk) Have(Banana) At(Home)At(Home) Sells(SM,Banana) Sells(SM,Milk) Sells(HWS,Drill)7POP Algorithm•Stated as nondeterministic algorithm where choices mustbe made. Various search methods can be used (e.g.breadth-first, depth-first iterative deepening etc.) to explorethe space of possible choices.•Maintains agenda of goals that need to be supported bylinks, where an agenda element is a pair <Q,Ai> where Q isa precondition of Aithat needs supporting.•Initialize plan to null plan and agenda to conjunction ofgoals (preconditions of Finish).•Done when all preconditions of every action in plan aresupported by causal links which are not threatened.8POP(<A,O,L>, agenda)1) Termination: If agenda is empty, return <A,O,L>. Usetopological sort to determine a totally ordered plan.2) Goal Selection: Let <Q,Aneed> be a pair on the agenda3) Action Selection: Let Aadd be a nondeterministicallychosen action that adds Q. It can be an existing action in Aor a new action. If there is no such action return failure. L´ = L ∪ {Aadd→QAneed} O´ = O ∪ {Aadd< Aneed} if Aadd is newthen A´ = A ∪ {Aadd} and O´=O´ ∪ {A0< Aadd<A∞} else A´ = A4) Update goal set: Let agenda´= agenda − {<Q,Aneed>}If Aaddis new then for each conjunct Qiof its precondition,add <Qi, Aadd> to agenda´5) Causal link protection: For every action At thatthreatens a causal link Ap→QAc add an ordering constraintby choosing nondeterministically either (a) Demotion: Add At< Apto O´ (b) Promotion: Add Ac< Atto O´If neither constraint is consistent then return failure.6) Recurse: POP(<A´,O´,L´>, agenda´)9Example•Add three actions to achieve basic goals. Use initial state toachieve the Sells preconditions.•Bold links are causal, regular are just ordering constraintsAt(s), Sells(s,Drill) At(s), Sells(s,Milk) At(s), Sells(s,Bananas)FinishStartBuy(Drill) Buy(Milk) Buy(Bananas)Have(Drill), Have(Milk), Have(Bananas), At(Home)At(HWS), Sells(HWS,Drill) At(SM), Sells(SM,Milk) At(SM), Sells(SM,Bananas)FinishStartBuy(Drill) Buy(Milk) Buy(Bananas)Have(Drill), Have(Milk), Have(Bananas), At(Home)10Example (cont)At(SM), Sells(SM,Bananas)At(SM), Sells(SM,Milk)At(x)At(x)At(HWS), Sells(HWS,Drill)Have(Drill) , Have(Milk) , Have(Bananas) , At(Home)FinishGo(HWS)Buy(Drill) Buy(Milk) Buy(Bananas)Go(SM)StartAt(SM), Sells(SM,Bananas)At(SM), Sells(SM,Milk)At(HWS), Sells(HWS,Drill)Have(Drill) , Have(Milk) , Have(Bananas) , At(Home)FinishGo(HWS)Buy(Drill) Buy(Milk) Buy(Bananas)Go(SM)StartAt(Home)At(Home)11Example (cont)•Cannot resolve threat to At(Home) preconditions of bothGo(HWS) and Go(SM).•Must backtrack to supporting At(x) precondition of Go(SM)from intial state At(Home) and support it instead from theAt(HWS) effect of Go(HWS).•Since Go(SM) still threatens At(HWS) of Buy(Drill) mustpromote Go(SM) to come after Buy(Drill). Demotion is notpossible due to causal link supporting At(HWS)precondition of Go(SM)At(SM), Sells(SM,Bananas)At(SM), Sells(SM,Milk)At(HWS), Sells(HWS,Drill)Have(Drill) , Have(Milk) , Have(Bananas) , At(Home)At(Home) At(HWS)At(SM)FinishGo(HWS)Buy(Drill) Buy(Milk) Buy(Bananas)Go(SM)StartGo(Home)12Example (cont)•Add Go(Home) action to achieve At(Home), use At(SM) toachieve its precondition, and order it after Buy(Milk) andBuy(Banana) to resolve threats to At(SM).At(SM)At(Home)At(HWS)Have(Milk) At(Home) Have(Ban.) Have(Drill)Buy(Drill)Buy(Milk) Buy(Ban.)Go(Home)Go(HWS)Go(SM)FinishStartAt(HWS) Sells(HWS,Drill)At(SM) Sells(SM,Milk)At(SM) Sells(SM,Ban.)13Planning Conclusions•Experiments confirm that in most cases partial-orderplanning is more efficient than total order.•Planning techniques have been applied to a number ofrealistic tasks:-Logistics planning for Desert Storm-Scheduling for the Hubble Space Telescope-Planning ground operations for