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