PlanningWhat we have so farExample: Robot ManipulatorsRemember: Problem-Solving AgentSimple planning agentA Simple Planning AgentSearch vs. planningSlide 8Planning in situation calculusBasic representation for planningPlanner vs. theorem proverSTRIPS operatorsTypes of plannersState space vs. plan spaceOperations on plansSlide 16Partially ordered plansPlanPOP algorithm sketchPOP algorithm (cont.)Clobbering and promotion/demotionExample: block worldExample (cont.)Slide 24Slide 25Slide 26CS 460, Session 201Planning•Search vs. planning•STRIPS operators•Partial-order planningCS 460, Session 202What we have so far•Can TELL KB about new percepts about the world•KB maintains model of the current world state•Can ASK KB about any fact that can be inferred from KBHow can we use these components to build a planning agent,i.e., an agent that constructs plans that can achieve its goals, and that then executes these plans?CS 460, Session 203Example: Robot ManipulatorsExample: Robot Manipulators•Example: (courtesy of Martin Rohrmeier) •Puma 560•Kr6CS 460, Session 204Remember: Problem-Solving AgentNote: This is offline problem-solving. Online problem-solving involves acting w/o complete knowledge of the problem and environmenttionCS 460, Session 205Simple planning agent•Use percepts to build model of current world state•IDEAL-PLANNER: Given a goal, algorithm generates plan of action•STATE-DESCRIPTION: given percept, return initial state description in format required by planner•MAKE-GOAL-QUERY: used to ask KB what next goal should beCS 460, Session 206A Simple Planning Agentfunction SIMPLE-PLANNING-AGENT(percept) returns an actionstatic: KB, a knowledge base (includes action descriptions)p, a plan (initially, NoPlan)t, a time counter (initially 0)local variables:G, a goalcurrent, a current state descriptionTELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))current  STATE-DESCRIPTION(KB, t)if p = NoPlan thenG  ASK(KB, MAKE-GOAL-QUERY(t))p  IDEAL-PLANNER(current, G, KB)if p = NoPlan or p is empty thenaction  NoOpelseaction  FIRST(p)p  REST(p)TELL(KB, MAKE-ACTION-SENTENCE(action, t))t  t+1return actionLike popping from a stackCS 460, Session 207Search vs. planningCS 460, Session 208Search vs. planningCS 460, Session 209Planning in situation calculusCS 460, Session 2010Basic representation for planning•Most widely used approach: uses STRIPS language•states: conjunctions of function-free ground literals (I.e., predicates applied to constant symbols, possibly negated); e.g.,At(Home)  Have(Milk)  Have(Bananas)  Have(Drill) …•goals: also conjunctions of literals; e.g.,At(Home)  Have(Milk)  Have(Bananas)  Have(Drill) but can also contain variables (implicitly universally quant.); e.g.,At(x)  Sells(x, Milk)CS 460, Session 2011Planner vs. theorem prover•Planner: ask for sequence of actions that makes goal true if executed•Theorem prover: ask whether query sentence is true given KBCS 460, Session 2012STRIPS operatorsGraphical notation:CS 460, Session 2013Types of planners•Situation space planner: search through possible situations•Progression planner: start with initial state, apply operators until goal is reachedProblem: high branching factor!•Regression planner: start from goal state and apply operators until start state reachedWhy desirable? usually many more operators are applicable to initial state than to goal state.Difficulty: when want to achieve a conjunction of goalsInitial STRIPS algorithm: situation-space regression plannerCS 460, Session 2014State space vs. plan spaceSearch space of plans ratherthan of states.CS 460, Session 2015Operations on plans•Refinement operators: add constraints to partial plan•Modification operator: every other operatorsCS 460, Session 2016Types of planners•Partial order planner: some steps are ordered, some are not•Total order planner: all steps ordered (thus, plan is a simple list of steps)•Linearization: process of deriving a totally ordered plan from a partially ordered plan.CS 460, Session 2017Partially ordered plansCS 460, Session 2018PlanWe formally define a plan as a data structure consisting of:•Set of plan steps (each is an operator for the problem)•Set of step ordering constraintse.g., A  B means “A before B”•Set of variable binding constraintse.g., v = x where v variable and x constant or other variable•Set of causal linkse.g., A Bmeans “A achieves c for B”cCS 460, Session 2019POP algorithm sketchCS 460, Session 2020POP algorithm (cont.)CS 460, Session 2021Clobbering and promotion/demotionCS 460, Session 2022Example: block worldCS 460, Session 2023Example (cont.)CS 460, Session 2024Example (cont.)CS 460, Session 2025Example (cont.)CS 460, Session 2026Example