Partial Order PlanningThe Planning ProblemRepresentation for states and goalsRepresentations for actionsSearch through World SpaceSearch through the Space of PlansRepresentation of PlansPowerPoint PresentationSlide 9Plans,Causal Links and ThreatsSlide 11Slide 12Slide 13Slide 14Resolving ThreatsSlide 16Slide 17Slide 18Partial Order PlanningThe Planning ProblemFormally a planning algorithm has three inputs:1. A description of the world in some formal language,2. A description of the agent’s goal in some formal language, and3. A description of the possible actions that can be performed.The planner’s o/p is a sequence of actions which when executed in any world satisfying the initial state description will achieve the goal.Representation for states and goalsIn the STRIPS language, states are represented by conjunctions of function-free ground literals, that is, predicates applied to constant symbols, possibly negated. For example,At(Home)^ ¬ Have(Milk)^ ¬ Have(Bananas)^ ¬ Have(Drill)^….Goals are also described by conjunctions of literals. For example,At(Home)^Have(Milk)^ Have(Bananas)^ Have(Drill)Goals can also contain variables. For example, the goal of being at a store that sells milk would be represented asRepresentations for actionsOur STRIPS operators consist of three components:• the action description is what an agent actually returns to the environment in order to do something.• the precondition is a conjunction of atoms (positive literals) that says what must be true before the operator can be applied.• the effect of an operator is a conjunction of literals (positive or negative) that describes how the situation changes when the operator is applied.Here’s an example for the operator for going from one place to another:Op(Action:Go(there), Precond:At(here)^Path(here, there), Effect:At(there)^ ¬At(here))Search through World SpaceThe simplest way to build a planner is to cast the planning problem as search through the space of world states. Each node in the graph denotes a state of the world, and arcs connect worlds that can be reached by executing a single action. We would call it a situation space planner because it searches through the space of possible situations.There are two types of planners:Progression Planner: it searches forward from the initial situation to the goal situation. Regression Planner: it searches backward from the goal situation to the initial situation.Search through the Space of PlansAn alternative is to search through space of plans rather than space of situations i.e plan-space node denote plans • Start with a simple partial plan•Expand the plan until the complete plan is developed•Operators in this step:•Adding a step•Imposing an ordering that puts one step after another•Instantiating a previously unbound variable•The solution  final plan Path  irrelevantRepresentation of PlansConsider a simple problem:•Putting on a pair of shoes•Goal RightShoeOn ^ LeftShoeOn•Four operators:•Op(Action:RightShoe,PreCond:RightSockOn,Effect:RightShoeON)•Op(Action:RightSock , Effect: RightSockOn)•Op(Action:LeftShoe, Precond:LeftSockOn, Effect:LeftShoeOn)•Op(Action:LeftSock,Effect:LeftSockOn)Least Commitment –One should make choices only about things that you currently care about ,leaving the others to be worked out later.Partial Order Planner –A planner that can represent plans in which some steps are ordered (before or after) w.r.t each other and other steps are unordered.Total Order Planner—Planner in which plans consist of a simple lists of stepsLinearization of P—A totally ordered plan that is derived from a plan P by adding constraintsLeft SockStartFinishRight ShoeLeft ShoeRight SockStartRight SockFinishLeftShoeRightShoeLeft SockStart Start Start Start StartRight SockRight SockRight SockRight SockRight SockLeft SockLeft SockLeft SockLeft SockLeft SockLeft SockRightShoeRightShoeRightShoeRightShoeRightShoeLeftShoeLeftShoeLeftShoeLeftShoeFinish Finish Finish Finish FinishLeft Shoe onRight Shoe onLeft Sock on Right Sock onPartial Order Plans:Total Order Plans:Plans,Causal Links and ThreatsRepresenting a Plan as a three tuple :-- <A,O,L>•A  Set of Actions•L  Set of Causal Links•O  Set of Ordering constraints over AIf A ={A1,A2,A3} then O might be set{A1<A3,A2<A3}These constraints specify a plan in which A3 is necessarily the last action but does not commit to a choice of which of the three actions comes first .As least commitment planners refine their plans, they must do constraint satisfaction to ensure consistency of OStartBuy(bananas)FinishBuy(Milk)Buy(Drill)At(s),Sells(s,Drill)At(s),Sells(s,Milk) At(s),Sells(s,Bananas)Have(Drill),Have(Milk),Have(Bananas),At(Home)StartBuy(bananas)FinishBuy(Milk)Buy(Drill)At(HWS),Sells(HWS,Drill)At(SM),Sells(SM,Milk) At(SM),Sells(SM,Bananas)Have(Drill),Have(Milk),Have(Bananas),At(Home)StartBuy(bananas)FinishBuy(Milk)Buy(Drill)Have(Drill),Have(Milk),Have(Bananas),At(Home)Go(HWS) Go(SM)At(HWS),Sells(HWS,Drill)At(SM),Sells(SM,Milk)At(SM),Sells(SM,Bananas)At(Home)At(Home)StartBuy(bananas)FinishBuy(Milk)Buy(Drill)Have(Drill),Have(Milk),Have(Bananas),At(Home)Go(HWS) Go(SM)At(HWS),Sells(HWS,Drill)At(SM),Sells(SM,Milk)At(SM),Sells(SM,Bananas)At(x)At(x)Causal Links— A Causal Links is written as Si c Sj and read as “ Si achieves c for Sj “.Causal Links serve to record the purpose of steps in the plan:here a purpose of Si is to achieve the precondition c of Sj Threat –Causal Links are used to detect when a newly introduced action interferes with past decision. Such an action is called a Threat.Let At be a different action in A : we sat that A t threatens Ap Q Ac when the two criteria are met:•O U{Ap<At<Ac} is consistent•At has ¬Q as an effect.Resolving ThreatsWhen a plan contains a threat , then there is a danger that the plan won’t work as anticipated i.e. We have reached a dead-end in the search.The causal link S1 c S2 is threatened by a new step S3 because one effect of S3 is to delete c. The way to resolve the Threat is to add ordering constraints to make sure that S3 does not intervene between S1 and S2Demotion -- S3 is placed before S1 .Promotion – S3 is placed after S2.S1S3S2S1S2S3S3S1S2C¬C¬C¬CCCStartBuy(bananas)FinishBuy(Milk)Buy(Drill)Have(Drill),Have(Milk),Have(Bananas),At(Home)Go(HWS)