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
Operator-based Planning Problem Input Set of world states What assumptions are Action operators Fn: world-state>world-state Atomic time nitial state of world Goal Agent is omniscient partial state (no sensing necessary). (set of world states) Agent is sole cause of Output change Sequence of actions Actions have Complete: Achieve goals Consistent: No negative deterministic effects side-effe No indirect effects north north12 → STRIPS Assumptions Outline Operator-based Planning Graph Plan The Graph Plan Solutions Graph Construction Solution extraction Properties Termination with Failure Planning as Propositional Satisfiability
11 Operator-based Planning Problem Input Set of world states Action operators oworld-state Initial state of world Goal partial state l ) Output Sequence of actions Complete: Achieve goals side-effects What assumptions are implied? • Atomic time. • Agent is omniscient (no sensing necessary). • Agent is sole cause of change. • Actions have deterministic effects. • No indirect effects. @ STRIPS Assumptions a a a north11 north12 W0 W1 W2 Outline Operator-based Planning Graph Plan The Graph Plan Solutions Graph Construction Solution Extraction Properties Termination with Failure Fn: world-state Consistent: No negative Planning as Propositional Satisfiability (set of wor d states
Graph Plan Graphplan was developed in 1995 by Avrim blum and merrick furst, at cmu Recent implementations by other researchers have extended the capability of Graphplan to reason with temporally extended actions metrics and non -atomic preconditions and effects Approach: Graph Plan 1. Constructs compact encoding of state space from operators and initial state which prunes many invalid plans- Plan graph 2. Generates plan by searching for a consistent subgraph that achieves the goals Proposition Action Proposition Action Init State Time 1 Time 1 Time 2
Graph Plan Recent implementations by other researchers have extended the capability extended actions, metrics and non-atomic preconditions and effects. Approach: Graph Plan 1. Constructs compact encoding of state space from operators and initial state, which prunes many invalid plans – Plan Graph. 2. Generates plan by searching for a consistent Proposition Init State Action Time 1 Proposition Time 1 Action Time 2 Graphplan was developed in 1995 by Avrim Blum and Merrick Furst, at CMU. of Graphplan to reason with temporally subgraph that achieves the goals
Outline Operator-based Planning Graph Plan The Graph Plan Planning Problem Graph Construction Solution extraction Properties Termination with Failure Planning as Propositional Satisfiability Visualizing Actions in a Plan Graph Coperator cook precondition(clean Hands) effect(dinner)) dinner cleanHands=cook Coperator carry precondition :effect (:and(no Garbage)(not(clean Hands))) noGarb carry
Outline Operator-based Planning Graph Plan The Graph Plan Planning Problem Graph Construction Solution Extraction Properties Termination with Failure 16 Visualizing Actions in a Plan Graph (:operator cook :precondition (cleanHands) :effect (dinner)) (:operator carry :effect (:and (noGarbage) (not (cleanHands))) carry noGarb cleanH cook dinner cleanHands Planning as Propositional Satisfiability :precondition
Visualizing Actions in a Plan Graph Persistence actions ( Noops) Every literal has a no-op action, which maintains it from time i to i+l E. g, ( operator noop-P: precondition(P): effect(P)) A Plan in GraphPlan ets of concurrent actions performed at each time il Concurrent actions can be interleaved in any order If actions a and b occur at time i. then it must be valid to perform either a followed by b, OR b followed by a noGarb clean carry. clean cook noop-dinner nner dinne noop-present present present Prop at 1 Action at 1 Prop at 2 Action at 2 Prop at 2
17 • Persistence actions (Noops) • • E.g., (:operator noop-P (P) :effect (P)) Noop-P P P Visualizing Actions in a Plan Graph dinner present cook wrap cleanH carry quiet noGarb cleanH dinner present Prop at 1 Action at 1 Prop at 2 Action at 2 Prop at 2 noop-dinner noop-present • Sets of concurrent actions performed at each time [i] • Concurrent actions can be interleaved in any order. • If actions a and b occur at time i, then it must be valid to Actions[i] > :precondition A Plan in GraphPlan < Every literal has a no-op action, which maintains it from time i to i+1. perform either a followed by b, OR b followed by a
A Complete Consistent Plan Given that the initial state holds at time 0, a plan is a solution iff Complete The preconditions of every operator at time 1, is satisfied by a proposition at time i The goal propositions all hold in the final state · Consistent: The operators at any time i can be executed in any order, without one of these operators undoing the .preconditions of another operator at time i .effects of another operator at time 1. Example of a Complete Consistent Plan Initial Conditions:(and(clean Hands)(quiet)) (and(no Garbage)(dinner)(present) noGarb clean carry clean ok (noop dinner nner →( dinner (noop present) at 1 Action at 1 2 Action at 2 Prop at 3
A Complete Consistent Plan Given that the initial state holds at time 0, a plan is a solution iff: is satisfied by a proposition at time i. without one of these operators undoing the: •preconditions of another operator at time i. •effects of another operator at time i. dinner present cook wrap carry cleanH quiet noGarb cleanH dinner present Prop at 1 Action at 1 Prop at 2 Action at 2 Prop at 3 Example of a Complete Consistent Plan Initial Conditions: (and (cleanHands) (quiet)) Goal: • Complete: • The preconditions of every operator at time i, • The goal propositions all hold in the final state. • Consistent: • The operators at any time i can be executed in any order, (noop dinner) (noop present) (and (noGarbage) (dinner) (present))