PlanningWhat we have so farRemember: Problem-Solving AgentSimple planning agentA Simple Planning AgentSearch vs. planningSlide 7Planning in situation calculusBasic representation for planningPlanner vs. theorem proverSTRIPS operatorsTypes of plannersState space vs. plan spaceOperations on plansSlide 15Partially ordered plansPlanPOP algorithm sketchPOP algorithm (cont.)Clobbering and promotion/demotionExample: block worldExample (cont.)Slide 23Slide 24Slide 25CS 561, Session 22-231Planning•Search vs. planning•STRIPS operators•Partial-order planningCS 561, Session 22-232What 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 561, Session 22-233Remember: Problem-Solving AgentNote: This is offline problem-solving. Online problem-solving involves acting w/o complete knowledge of the problem and environmenttionCS 561, Session 22-234Simple 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 561, Session 22-235A 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 actionCS 561, Session 22-236Search vs. planningCS 561, Session 22-237Search vs. planningCS 561, Session 22-238Planning in situation calculusCS 561, Session 22-239Basic 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 561, Session 22-2310Planner 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 561, Session 22-2311STRIPS operatorsGraphical notation:CS 561, Session 22-2312Types 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 561, Session 22-2313State space vs. plan spaceSearch space of plans ratherthan of states.CS 561, Session 22-2314Operations on plans•Refinement operators: add constraints to partial plan•Modification operator: every other operatorsCS 561, Session 22-2315Types 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 561, Session 22-2316Partially ordered plansCS 561, Session 22-2317PlanWe 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 561, Session 22-2318POP algorithm sketchCS 561, Session 22-2319POP algorithm (cont.)CS 561, Session 22-2320Clobbering and promotion/demotionCS 561, Session 22-2321Example: block worldCS 561, Session 22-2322Example (cont.)CS 561, Session 22-2323Example (cont.)CS 561, Session 22-2324Example (cont.)CS 561, Session 22-2325Example
View Full Document
Unlocking...