GraphPlan Algorithm Phase 1-Plan Graph Expansion Creates graph encoding pairwise consistency and reachability of actions and propositions from initial state Graph includes, as a subset, all plans that are complete and consistent Phase 2- Solution Extraction 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 Planning as Propositional Satisfiability
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 noGarb carry carry clean clean clean doll doll. uiet let dinner wrap 1 Prop Action op 2 Action 3 Prop Graph Properties A Plan graph compactly encodes the space of consistent plans while pruning 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 plans that cannot reach the goals
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
Graph Properties 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 Constructing the planning graph.(Reachability) Initial proposition layer Contains propositions in initial state
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