Graph-based Planning Slides based on material from: Prof Dan Weld (Univ Washington)and Brian c。 Willams Prof. Maria Fox(Durham, UK) October 8th. 2003 16。410-13 autonomous Agents eIf-diagnosing Self-repairing RECOVERY Commanded at Mission level Engineering level Cor Fault protection Attitude control Mission goal scenario
Graph-based Planning Brian C. Williams October 8th, 2003 16.410 - 13 Slides based on material from: Prof. Maria Fox Monitors Autonomous Agents Command dispatch Fault protection Attitude control Mission Goal Scenario Self-commanding commanding Self-diagnosing diagnosing Self-repairing repairing RECOVERY PLANNING EXECUTION Commanded at: • Mission level • Engineering level Slides based on material from: Prof. Dan Weld (Univ. Washington) and Prof. Maria Fox (Durham, UK)
Readings for Planning Lectures Today: Graph-based Planning AIMA Chapter 11 AlMA="Artificial Intelligence: A Modern Approach by Russell and Norvig Outline Operator-based Planning Graph plan The Graph Plan Planning Problem Graph Construction Solution extraction Properties Termination with Failure Planning as Propositional Satisfiability
Readings for Planning Lectures Today: Graph-based Planning AIMA Chapter 11 * AIMA = “Artificial Intelligence: A Modern Approach,” by Russell and Norvig. Outline Operator-based Planning Graph Plan The Graph Plan Planning Problem Graph Construction Solution Extraction Properties Termination with Failure Planning as Propositional Satisfiability
Operator-based Planning Problem state A consistent conjunction of propositions(positive literals) E.g,(and(cleanhands)(quiet)(dinner)(present)(no Garbage) All unspecified propositions are false initial state Problem state at time i=0 E. g,and(clean Hands)(quiet)) Goal state A partial state E.g.,(and (noGarbage)(dinner)(present)) The planner must put the system in a final state that satisfies conjunction Operator-based Planning Problem (:operator carry precondition effect (:and(no Garbage)(not(clean Hands)) Preconditions: propositions that must be true to apply operator A conjunction of propositions(no negated propositions) Effects: Propositions that operator changes, given preconditions A conjunction of propositions(called adds)and their negation(called deletes)
5 Operator-based Planning Problem • State • • E.g., (and (cleanhands) ( • All unspecified propositions are false • Initial State • Problem state at time i = 0 • E.g., (and (cleanHands) (quiet)) • Goal State • A partial state • E.g., (and (noGarbage) (dinner) (present)) • The planner must put the system in a final state that satisfies the conjunction. 6 Operator-based Planning Problem (:operator carry :precondition :effect (:and (noGarbage) (not (cleanHands))) : Preconditions: propositions that must be true to apply operator. • A conjunction of propositions (no negated propositions). Effects: Propositions that operator changes, given preconditions. • A conjunction of propositions (called adds) and their negation (called deletes). A consistent conjunction of propositions (positive literals) quiet) (dinner) (present) (noGarbage))
Example: Dinner Date Problem Initial Conditions:(and(clean Hands)(quiet)) (and(no Garbage)(dinner)(present) effectand (no Garbage)(not(clean Hands))) C operator dolly precondition effectand(no Garbage)(not(quiet))) Coperator cook precondition(clean Hands effect(dinner)) Coperator wrap precondition(quiet) effect(present) (Parameterized)Operator Schemata Instead of defining pickup-A and pickup-B and Define a schema ?var denotes a free variable parameters(block ob1)) precondition(and(clear obl) (on-table obl) (arm-empty)) ffect(and (not(clear obl)) (not(arm-empty)) (holding obl))
Example: Dinner Date Problem Initial Conditions: (and (cleanHands) (quiet)) Goal: (and (noGarbage) (dinner) (present)) Actions: (:operator carry :precondition :effect (and (noGarbage) (not (cleanHands))) (:operator dolly :precondition :effect (and (noGarbage) (not (quiet))) (:operator cook :precondition (cleanHands) :effect (dinner)) (:operator wrap :precondition (quiet) :effect (present)) + noops (Parameterized) Operator Schemata (:operator pick-up :parameters ((block ob1)) :precondition (and (clear ob1) (on-table ob1) (arm-empty)) :effect (and (not (clear ob1)) (not (on-table ob1)) (not (arm-empty)) (holding ob1))) Instead of defining: pickup-A and pickup-B and … Define a schema: Note: strips doesn’t allow derived effects; you must be complete! } ?var denotes a free variable
Operator Execution at Time i If all propositions of: precondition appear in the state at 1, Then create state at i+l from state at i, by adding to i, all"add"propositions in effects removing from i, all"delete" propositions in ( operator dolly precondition effect(and(no Garbage)(not(quiet))) (clean Hands (cleanHands) (quiet) doy→≯ (no Garbage) Operator Execution at Time i If all propositions of precondition appear in the state at i, Then create state at i+1 from state at i by adding to i, all"add propositions in effects removing from i, all"delete" propositions in ffects C operator cook preconditionclean Hands) effect(dinner)) (clean Hands (cleanHands (quiet) cook→ (quiet) (dinner
9 Operator Execution at Time i Then create state at i+1 from state at i, by • adding to i, all “add” propositions in :effects, • removing from i, all “delete” propositions in :effects. (:operator dolly :precondition :effect (and (noGarbage) (not (quiet))) (cleanHands) (quiet) (cleanHands) (noGarbage) dolly 10 Operator Execution at Time i Then create state at i+1 from state at i, by • adding to i, all “add” propositions in :effects, • removing from i, all “delete” propositions in :effects. (:operator cook :precondition (cleanHands) :effect (dinner)) (cleanHands) (quiet) (cleanHands) (quiet) (dinner) cook If all propositions of :precondition appear in the state at i, If all propositions of :precondition appear in the state at i