Graph-based Planning Brian C. Williams October 8 th , 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 Self-diagnosing Self-repairing RECOVERY P L A N N I N G E X E C U T ION 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 ? * 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 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 (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: N o te : s tr ip s d o e s n ’ t a l l o w d e r iv e d e f f e c ts ; y o u m u s t b e c o m p le t e ! } ?var denotes a free variable 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, 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 W2W1 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 ? ? 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 ? 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 17 Persistence actions (Noops) E.g., (:operator noop-P (P) :effect (P)) Noop-P PP Visualizing Actions in a Plan Graph 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 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: 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)) ? ? state. ? Graph includes, as a subset, all plans that are complete and consistent. ? ? Graph treated as a kind of constraint satisfaction problem (CSP). ? Selects whether or not to perform each action at each time point, by assigning CSP variables and testing consistency. Outline ? Operator-based Planning ? Graph Plan ? The Graph Plan Planning Problem ? Graph Construction ? Solution Extraction ? Properties ? Termination with Failure ? GraphPlan Algorithm Phase 1 – Plan Graph Expansion Creates graph encoding pairwise consistency and reachability of actions and propositions from initial Planning as Propositional Satisfiability Phase 2 - Solution Extraction Example: Graph and Solution noGarb cleanH quiet dinner present carry dolly cook wrap carry dolly cook wrap cleanH quiet noGarb cleanH quiet dinner present 1 Prop 1 Action 2 Prop 2 Action 3 Prop Graph Properties A Plan graph ? compactly encodes the space of consistent plans, ? while pruning . . . 1. partial states and actions at each time i that are not reachable from the initial state. 2. pairs of actions and propositions that are mutually inconsistent at time i. 3. plans that cannot reach the goals. ? Plan graphs are constructed in polynomial time and are of polynomial in size. ? The plan graph does not eliminate all infeasible plans. ?Plan generation still requires focused search. Graph Properties Constructing the planning graph…(Reachability) ? Initial proposition layer ? Contains propositions in initial state. Example: Initial State, Layer 0 cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Constructing the planning graph…(Reachability) ? Initial proposition layer ? Contains propositions in initial state ? Action layer i ? If all action’s preconditions are consistent in i-1 ? Then add action to layer i ? Proposition layer i+1 ? For each action at layer i ? Add all its effects at layer i+1 Example: Add Actions and Effects noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Constructing the planning graph…(Reachability) ? Initial proposition layer ? Write down just the initial conditions ? Action layer i ? If all action’s preconditions appear consistent in i-1 ? Then add action to layer i ? Proposition layer i+1 ? For each action at layer i ? Add all its effects at layer i+1 ? Repeat until all goal propositions appear Can a solution exist? noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Do all goal propositions appear? Constructing the planning graph…(Consistency) ? Initial proposition layer ? Write down just the initial conditions ? Action layer i ? If action’s preconditions appear consistent in i-1 (non-mutex) ? Then add action to layer i ? Proposition layer i+1 ? For each action at layer i ? Add all its effects at layer i+1 ? Identify mutual exclusions ? Actions in layer i ? Propositions in layer i + 1 ? Repeat until all goal propositions appear non-mutex 33 Mutual Exclusion: Actions ? Actions A,B are mutually exclusive at level i if no valid plan could possibly contain both at i: ? They have inconsistent effects, ? A deletes B’s effects, ? interfere with preconditions or ? A deletes B’s preconditions, or ? Vice versa or ? compete for needs ? A and B have inconsistent preconditions What causes the exclusion? noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet What causes the exclusion? 1 Prop 1 Action 2 Prop 2 Action 3 Prop noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet What causes the exclusion? 1 Prop 1 Action 2 Prop 2 Action 3 Prop noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet What causes the exclusion? 1 Prop 1 Action 2 Prop 2 Action 3 Prop 38 Mutual Exclusion: Actions ? Actions A,B are mutually exclusive at level i if no valid plan could possibly contain both at i: ? They Interfere ? A deletes B’s preconditions, or ? Vice versa ? They have inconsistent effects: ? A deletes B’s effects, or ? Vice versa ? They have competing needs: ? A & B have inconsistent preconditions Layer 1: complete action mutexs noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop 40 Mutual Exclusion: Proposition Layer Propositions P,Q are inconsistent at i ? if no valid plan could possibly contain both at i ? If at i, all ways to achieve P exclude all ways to achieve Q P Q A1 A2 M N Layer 1: add proposition mutexs noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop None! Can a solution exist? noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Do all goal propositions appear non-mutex? Outline ? Operator-based Planning ? Graph Plan ? The Graph Plan Planning Problem ? Graph Construction ? Solution Extraction ? Properties ? Termination with Failure ? 44 Graphplan ? Create plan graph level 1 from initial state ? Loop ? If goal ? propositions of the highest level (nonmutex) ? Then search graph for solution ? ? Else extend graph one more level A k in d o f d o u b le s ea r c h : fo r w a r d d ir e c ti o n ch e c k s n e c e s s a r y (b u t in s u ff icie n t) c o n d iti o n s fo r a s o lu ti o n , .. . B a c k wa r d s e a r c h v e r if ies .. . Planning as Propositional Satisfiability If solution found, then return and terminate 45 Searching for a Solution Recursively find consistent actions achieving all goals at t, t-1, . . . : ? For each goal proposition G at time t ? For each action A making G true at t ? ? Then select it ? Finally, ? If no action of G works, ? Then backtrack on previous G. ? Finally ? If action found for each goal at time t, ? ? Avoiding redundancy ? No-ops are always favored. ? guarantees that the plan will not contain redundant actions. Then recurse on preconditions of actions selected, t-1, Else backtrack. If A isn’t mutex with previously chosen action at t, Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Select action achieving Goal noGarb Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Select action achieving Goal dinner, Consistent with carry? Backtrack on noGarb Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Select action dolly to achieve goal noGarb Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Select action achieving Goal dinner, Which is consistent with dolly Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop Select action achieving Goal present, consistent w dolly, cook wrap is inconsistent Searching for a solution noGarb cleanH quiet dinner present carry dolly cook wrap cleanH quiet 1 Prop 1 Action 2 Prop 2 Action 3 Prop No other choices for present Backtrack dinner … no choices Backtrack noGarb … no choices. Layer fails Extend Plan Graph noGarb cleanH quiet dinner present carry dolly cook wrap carry dolly cook wrap cleanH quiet noGarb cleanH quiet dinner present 1 Prop 1 Action 2 Prop 2 Action 3 Prop level 2: 1 st consistent assignment is carrry, noop-dinner, noop-present noGarb cleanH quiet dinner present carry dolly cook wrap carry dolly cook wrap cleanH quiet noGarb cleanH quiet dinner present 1 Prop 1 Action 2 Prop 2 Action 3 Prop Level 1: dinner & present are uniquely achieved by cook & wrap noGarb cleanH quiet dinner present carry dolly cook wrap carry dolly cook wrap cleanH quiet noGarb cleanH quiet dinner present 1 Prop 1 Action 2 Prop 2 Action 3 Prop Outline ? Operator-based Planning ? Graph Plan ? The Graph Plan Planning Problem ? Graph Construction ? Solution Extraction ? Properties ? Termination with Failure ? Planning as Propositional Satisfiability Plan Graph Properties ? Propositions monotonically increase ? successive layers; ? ? ? decrease ? if a goal set is achievable at a layer Then it will be achievable at all successive layers. ?The graph will eventually reach a fix point, that is, Fix point Example: Door Domain A B once they are added to a layer they are never removed in Mutexes monotonically decrease once a mutex has decayed it can never reappear; Memoized sets (to be discussed) monotonically a level where facts and mutexes no longer change. Fix point Example: Door Domain Move from room 1 to room 2 ? pre: robot is in 1 and the door is open ? add: robot is in 2 ? del: robot is in 1 Open door ? pre: door is closed ? add: door is open ? del: door is closed Close door ? pre: door is open ? add: door is closed ? del: door is open noop noop Move Move Open noop Close noop In(B) In(A) Closed Opened Layer 4 N In(A) Closed Layer 1 Open noop noop In(A) Closed Opened Layer 2 In(B) noop noop Move Open noop Close In(A) Closed Opened Layer 3 Layer 4 is the fixed point (called level out) of the graph Graph Search Properties ? fix point to find a solution. ? Why? Gripper Example Move from one room to another ? pre: robot in the first room ? add: robot in the second room ? del: robot in the first room Pick a ball up in a gripper ? pre: robot has a free gripper and is in same room as ball ? add: robot holding the ball ? del: gripper free, ball in room. Drop a ball in a room ? ? add: ball in destination room, gripper free. ? del: ball being held. Graphplan may need to expand well beyond the pre: robot holding the ball, robot in destination room Gripper Example ? In Gripper, the fix point occurs at layer 4, ? all facts concerning the locations of the balls and the ? The distance to the solution layer depends on the number of balls to be moved. ? copies of the same layers repeatedly. ? For example, for 30 balls ? ? Search Properties (cont) ? Plans do not contain redundant steps. ? By preferring No-ops ? ? The plan will take as short a time as possible. ? optimality ? with fewer actions at that layer. ? exists. robot are pairwise non-mutex after 4 steps. For large numbers of balls Graphplan searches the solution layer is at layer 59, 54 layers contain identical facts, actions and mutexes. Graphplan guarantees parallel optimality. Graphplan doesn’t guarantee sequential Graphplan returns failure if and only if no plan Might be possible to achieve all goals at some layer Outline ? Operator-based Planning ? Graph Plan ? The Graph Plan Planning Problem ? Graph Construction ? Solution Extraction ? Properties ? Termination with Failure ? Simple Termination ? If the fix point is reached and either: ? One of the goals is not asserted or ? Two of the goals are mutex any search at all. ? Else there may be higher order exclusions ?Requires more sophisticated additional test for termination. Planning as Propositional Satisfiability Then Graphplan can return "No solution" without which Graphplan cannot detect Why Continue After the Fix Point? ? after the fix point, ? ? New layers add time to the graph. ? Time allows actions to be spaced so that N-ary ? While new things can happen between two successive layers progress is being made. ? ? Terminate on their fix point. Termination ? A goal set at a layer may be unsolvable ? Example, in Gripper. ? If a goal set at layer k cannot be achieved, ? To prevent wasted search effort ? Checks each new goal set at k against memos of k for infeasibility. ? If an additional layer is built and searching it creates no new memos, then the problem is unsolvable. N-ary exclusions DO change. mutexes have time to decay. Track n-ary mutexes. Memoization and Then that set is memoized at layer k. facts, actions and mutexes no longer change Recap: Graph Plan ? Blum and Merrick Furst, at CMU. ? the state space from the operators and initial state, which prunes many invalid plans, ? Recent implementations by other researchers reason with temporally extended actions, metrics and non-atomic preconditions and effects. Outline ? Operator-based Planning ? Graph Plan ? The Graph Plan Planning Problem ? Graph Construction ? Solution Extraction ? Properties ? Termination with Failure ? Graphplan was developed in 1995 by Avrim Graphplan searches a compact encoding of violating reachability and mutual exclusion. have extended the capability of Graphplan to Planning as Propositional Satisfiability Planning as Satisfiability axiom schemas instantiated propositional clauses satisfying model plan mapping length problem description SAT engine(s) instantiate interpret Planning as Satisfiability 1. Constrain problem to finite horizon (fixed # of steps). 2. Encode state for each time step with propositions ? state predicates: indexed by time at which they hold ? action predicates: indexed by time at which action begins ? each action takes 1 time step ? many actions may occur at the same step 3. Encode Problem as Clauses ? Initial and Final State as Clauses ? Instantiate operators for every time step ? Select operator at time step with proposition 4. Generate plan by searching for a consistent truth assignment. Proposition Init State Action Time 1 Proposition Time 1 Action Time 2 Encoding Conventions ? Actions imply preconditions and effects fly(x,y,i) ? at(x,i) & route(x,y) & at(y,i+1) ? Conflicting actions cannot occur at same time (A deletes a precondition of B) fly(x,y,i) & yzz ??fly(x,z,i) ? If something changes, an action must have caused it (Explanatory Frame Axioms) at(x,i) & ?at(x,i+1) ?y . route(x,y) & fly(x,y,i) ? Initial and final states hold at(NY,0) & ... & at(LA,9) & ... Appendix Termination Test ? If the Graph leveled off at layer n, and a search stage, t >n, has passed in which the memoized sets at n+1 are the same as at layer n, Layer n Layer Layer t S t n = S t n+1 Where S m k = the sets of goals found unsolvable at layer k during search from m Termination Property ? problem is unsolvable. ? Proof: If the problem is unsolvable Graphplan returns with failure. The number of sets found unsolvable at layer n from layer t will never be smaller than the number at n from layer t+1, and there is a finite maximum number of goal sets. This means that, if the problem is unsolvable, eventually two successive layers will contain the Then Graphplan can output "No Solution". Claim: Graphplan returns with failure iff the same memoized sets. n + 1