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 <Actions[> 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))