Concept of planning ppt

explain the various steps involved in planning process and formal planning process six steps
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
Comment
Intelligent Control and Cognitive Systems brings you... Planning and Action Selection Joanna J. Bryson University of BathIntelligence Action Selection What is intelligence? Judged by expressed behaviour. Judgement by people. “Judgement” by Natural Selection. What matters: doing the right thing at the right time.Strategies of Action Selection / Outline Productions Formal / Optimal Planning Reactive / Dynamic Plans Learning PlansProductions & The Markov Assumption A production is a tuple: sensory precondition, action A production system (or expert system) is a set of productions used to solve a particular problem. Problem: much human behaviour cannot be determined only from the environment.Delivery Robot What in the office environment tells the robot where it’s meant to go? What if it’s carrying coffee? The (external) Markov Assumption only holds when each context uniquely determines an action. Internal state (memory) can help. Moravec (1998), ROBOT, page 108 Oxford University Press.From last semester / Agents x State only helps if it informs AS AS–not state–chooses the AStrategies of Action Selection / Outline Productions Formal / Optimal Planning Reactive / Dynamic Plans Learning PlansWhat Do We Want from Action Selection? OptimalityFormal Planning for Optimality Provably correct: know we can get from here to the goal. Prove we can do it in the least amount of steps. Totally impossible. (Agre 1987, Simon 1956). Satisficing HeuristicYet people keep trying... Intro to CS 541 (AI Planning) http://www.isi.edu/blythe/cs541 Jim Blythe Jose Luis Ambite Yolanda Gil With Annotations by – JJBGenerating plans ■ Given: ➤ A way to describe the world ➤ An initial state of the world ➤ A goal description ➤ A set of possible actions to change the world ■ Find: ➤ A prescription for actions to change the initial state into one that satisfies the goal 11 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningThe situation calculus (McCarthy 63) ■ Key idea: represent a snapshot of the world, called a ‘situation’ explicitly. ■ ‘Fluents’ are statements that are true or false in any given situation, e.g. ‘I am at home’ ■ Actions map situations to situations. Actions in formal planning are essentially functions used by agents to transition the world from one state to the next – JJB 12 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningS1 = result(go(store), S0) S1 ┐holds(at(home), S1) go(store) holds(at(store), S1) S0 mow_lawn() S2 holds(at(home), S0) holds(color(door, red), S0) 13 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningMy boldface – JJB Frame problem ■ I go from home to the store, creating a new situation S’. In S’: ➤ My friend is still at home ➤ The store still sells chips ➤ My age is still the same ➤ Los Angeles is still the largest city in California… ■ How can we efficiently represent everything that hasn’t changed? 14 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningSuccessor state axioms ■ Normally, things stay true from one state to the next unless an action changes them: holds(at(X),result(A,S)) iff A = go(X) or holds(at(X),S) and A = go(Y) ■ We need one or more of these for every fluent. ■ Now we can use theorem proving to deduce a plan. ■ Class dismissed 15 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningWell, not quite.. ■ Theorem proving can be really inefficient for planning ■ How do we handle concurrent events? uncertainty? metric time? preferences about plans? … 16 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningStrips (Fikes and Nilsson 71) ■ For efficiency, separates theorem-proving within a world state from searching the space of possible states ■ Highly influential representation for actions: ➤ Preconditions (list of propositions to be true) These two ➤ Delete list (list of propositions that will become false) together ➤ Add list (list of propositions that will become true) are the action My boldface – important terms. Others you might want: Production (precondition⇒action pairs), guarding (what preconditions do for actions) JJB 17 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningExample problem: Initial state: at(home), ┐have(beer), ┐have(chips) Goal: have(beer), have(chips), at(home) Actions: Buy (X): Go (X, Y): Pre: at(store) Pre: at(X) Add: have(X) Del: at(X) Add: at(Y) 18 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningFrame problem (again) ■ I go from home to the store, creating a new situation S’. In S’: ➤ The store still sells chips ➤ My age is still the same ➤ Los Angeles is still the largest city in California… ■ How can we efficiently represent everything that hasn’t changed? ➤ Strips provides a good solution for simple actions 19 USC INFORMATION SCIENCES INSTITUTE Intro to PlanningRamification problem ■ I go from home to the store, creating a new situation S’. In S’: ➤ I am now in Marina del Rey ➤ The number of people in the store went up by 1 ➤ The contents of my pockets are now in the store.. ■ Do we want to say all that in the action definition? Formal systems often assumed to be completely, logically, provably correct, Satisficing but all AI requires design & abstraction decisions. – JJB 20 USC INFORMATION SCIENCES INSTITUTE Intro to Planning