Course on Hierarchical Planning

This is a course that I held at Ulm University in Winter Term 2018/2019 as a (fresh-baked) post-doc. I conceptualized it completely by myself and from scratch. Note though that my former colleagues Gregor Behnke and Daniel Höller also held guest lectures, which they in turn created by themselves.

Although this course is not taught anymore I still occasionally use some of their slides for guest lectures etc. Thus: Should you find any error, no matter how tiny, please let me know so that I can correct it. :)

  • Chapter 1: Introduction to Non-Hierarchical Planning (Slides (handout) (single))
    • Introduction
    • Classical (STRIPS) Planning
    • Partial Order Causal Link (POCL) planning
  • Chapter 2: Uninformed Search (Slides (handout) (single))
    • Breadth-First Search (BFS)
    • Depth-First Search (DFS)
    • Uniform Cost Search (UCS)
  • Chapter 3.a: Classical Planning as Search (Slides (handout) (single))
    • State-Based Progression Search
    • POCL Planning
    • Planning as Refinement Search
  • Chapter 3.b: Classical Planning Heuristics (Slides (handout) (single))
    • Relaxed Planning Graph
    • the h+, max, Add, and FF heuristics
    • the Add and FF heuristics for POCL planning
    • Complexity result: h+ is NP-complete.
  • Chapter 4: Classical Planning via SAT-Solving (Slides (handout) (single))
    • SAT Modeling, Background
    • Transforming Classical Problems into SAT
    • Invariants
    • All (Universal), and Exists Encoding
  • Chapter 5: Problem Compilations for Classical Planning (Slides (handout) (single))
    • Lifted Models
    • Negative Preconditions
    • Conditional Effects
    • Disjunctive Preconditions
    • Quantifiers
    • Complexity Result: Delete-free Problems without Negative Preconditions are in P
    • Complexity Result: Delete-free Problems with Negative Preconditions are NP-complete
  • Chapter 6: Introduction to HTN Planning (Slides (handout) (single))
    • Motivation: Why Adding a Task Hierarchy?
    • Problem Definition (published IJCAI 2011)
    • Decomposition Trees (published IJCAI 2011)
    • Formalization Choices in HTN Planning
  • Chapter 7: Expressivity Analysis of Planning Formalisms (Slides (handout) (single))
    • Formal Grammars and Languages Recap
    • Expressivity Analysis of Classical and HTN Planning Formalisms (published ECAI 2014 and ICAPS 2016)
  • Chapter 8: HTN planning as Search (Slides (handout) (single))
    • HTN Progression Search (published in ICAPS 2018 (best student paper award), IJCAI 2019, JAIR 2020)
    • Hybrid HTN Search in the Space of POCL Plans (published SoCS 2014)
  • Chapter 9: Hierarchical Planning Heuristics (Slides (handout) (single))
    • The Task Decomposition Graph (TDG) (published IJCAI 2017)
    • Landmarks: Computation and Complexity Results (published AAAI 2021)
    • TDG-based heuristics (published IJCAI 2017)
    • HTN-heuristics via Compilation into STRIPS (published in ICAPS 2018 (best student paper award), IJCAI 2019, JAIR 2020)
  • Chapter 10: Plan Recognition in Hierarchical Planning (Slides (handout) (single))
    • Plan Recognition in Classical Planning
    • Plan Recognition in HTN Planning (published ICTAI 2018 (best paper award))
  • Chapter 11.a: Complexity Results for HTN Plan Verification (Slides (handout) (single))
    • Recap Complexity Theory
    • Complexity Result: Verifying a plan for a Classical Problem is in P
    • Complexity Result: Verifying a plan for a Hierarchical Problem is NP-complete
  • Chapter 11.b: Complexity Results for HTN Plan Existence (Slides (handout) (single))
    • Problem Class Definitions for HTN Planning (Special cases like total order)
    • Complexity Results for all these Classes (published ICAPS 2016 and IJCAI 2016)
  • Chapter 12: HTN Planning via SAT-Solving (Slides (handout) (single))
    • Compactifying Decomposition Trees
    • SAT encoding of Decomposition and Executability
    • Evaluation
  • Chapter 13: Further Hierarchical Planning Formalizations (Slides (handout) (single))
    • Hybrid Planning and Legality Criteria on Decomposition Methods (published ECAI 2016)
    • Complexity Results: Hybrid Planning is Undecidable (published ECAI 2016)
    • Decompositional Planning
  • Chapter 14: Planning Capabilities Motivated by Real-World Applications (Slides (handout) (single))
    • Plan Repair (published KI 2020 (nominated for Best Paper Award))
    • User-Friendly Plan Linearizations
    • Plan Explanations (published ICAPS 2014)
    • An Example Assistant Integrating these Techniques (published ICAPS 2014, AAAI 2015)