Review for the Final ExamWhat We’ve CoveredChapter 1: Introduction and Overview2: Representations for Classical PlanningChapter 3: Complexity of Classical PlanningChapter 4: State-Space PlanningChapter 5: Plan-Space PlanningChapter 6: Planning-Graph Techniques7: Propositional Satisfiability TechniquesChapter 16: Planning Based on MDPs17: Planning based on Model CheckingChapter 9: Heuristics in PlanningChapter 10: Control Rules in PlanningChapter 11: HTN PlanningChapter 14: Temporal PlanningThe ExamStudying for the ExamMiscellaneousDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/1Review for the Final ExamDana S. NauUniversity of Maryland10:20 AM January 14, 2019Lecture slides forAutomated Planning: Theory and PracticeDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/2What We’ve CoveredChapter 1: IntroductionChapter 2: Representations for Classical PlanningChapter 3: Complexity of Classical PlanningChapter 4: State-Space PlanningChapter 5: Plan-Space PlanningChapter 6: Planning-Graph TechniquesChapter 7: Propositional Satisfiability TechniquesChapter 16: Planning based on MDPsChapter 17: Planning based on Model CheckingChapter 9: Heuristics in Planning*Chapter 10: Control Rules in Planning*Chapter 11: Hierarchical Task Network Planning*Chapter 14: Temporal Planning** These weren’t on the midtermDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/3Chapter 1: Introduction and Overview1.1: First Intuitions on Planning 1.2: Forms of planning 1.3: Domain-Independent Planning 1.4: Conceptual Model for Planning 1.5: Restricted Model 1.6: Extended Models 1.7: A Running Example: Dock-Worker Robots No questions on Chapter 1Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/4No questions on these topics unless they were covered in other chapters:2: Representations for Classical Planning2.1: Introduction 2.2: Set-Theoretic Representation 2.2.1: Planning Domains,Problems, and Solutions 2.2.2: State Reachability 2.2.3: Stating a Planning Problem 2.2.4: Properties of theSet-theoretic Representation 2.3: Classical Representation 2.3.1: States 2.3.2: Operators and Actions 2.3.3: Plans, Problems, & Solutions2.3.4: Semantics of Classical Reps2.4: Extending the Classical Rep.2.4.1: Simple Syntactical Extensions 2.4.2: Conditional Planning Operators 2.4.3: Quantified Expressions 2.4.4: Disjunctive Preconditions 2.4.5: Axiomatic Inference 2.4.6: Function Symbols 2.4.7: Attached Procedures 2.4.8: Extended Goals 2.5: State-Variable Representation 2.5.1: State Variables 2.5.2: Operators and Actions 2.5.3: Domains and Problems 2.5.4: Properties 2.6: ComparisonsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/5Chapter 3: Complexity of Classical Planning3.1: Introduction 3.2: Preliminaries 3.3: Decidability and Undecidability Results 3.4: Complexity Results 3.4.1: Binary Counters 3.4.2: Unrestricted Classical Planning 3.4.3: Other results 3.5: Limitations You don’t need to know the details of the complexity tables, but you should know the basic concepts, e.g.:- What does it mean to allow or disallow function symbols, negative effects, etc.?- What’s the difference between giving the operators in the input or in advance?Dana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/6Chapter 4: State-Space PlanningNo questions on this topicDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/75.1: Introduction 5.2: The Search Space of Partial Plans 5.3: Solution Plans 5.4: Algorithms for Plan Space Planning 5.4.1: The PSP Procedure5.4.2: The PoP Procedure 5.5: Extensions 5.6: Plan Space Versus State Space Planning Chapter 5: Plan-Space PlanningNo questions on these topicsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/8Chapter 6: Planning-Graph Techniques6.1: Introduction 6.2: Planning Graphs 6.2.1: Reachability Trees 6.2.2: Reachability with Planning Graphs 6.2.3: Independent Actions and Layered Plans 6.2.4: Mutual Exclusion Relations 6.3: The Graphplan Planner 6.3.1: Expanding the Planning Graph 6.3.2: Searching the Planning Graph 6.3.3: Analysis of Graphplan 6.4: Extensions and Improvements of Graphplan 6.4.1: Extending the Language 6.4.2: Improving the Planner 6.4.3: Extending the Independence Relation use my lecture notesrather than the bookNo questions on these topicsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/97: Propositional Satisfiability Techniques7.1: Introduction 7.2: Planning problems as Satisfiability problems 7.2.1: States as propositional formulas 7.2.2: State transitions as propositional formulas 7.2.3: Planning problems as propositional formulas 7.3: Planning by Satisfiability 7.3.1: Davis-Putnam 7.3.2: Stochastic Procedures7.4: Different Encodings 7.4.1: Action Representation 7.4.2: Frame axioms No questions on these topicsNo questions on these topicsDana Nau: Lecture slides for Automated PlanningLicensed under the Creative Commons Attribution-NonCommercial-ShareAlike License: http://creativecommons.org/licenses/by-nc-sa/2.0/10Chapter 16: Planning Based on MDPs16.1: Introduction 16.2: Planning in Fully Observable Domains 16.2.1: Domains, Plans, and Planning Problems 16.2.2: Planning