Hierarchical Planning

The lecture covers all foundations of hierarchical planning (including the relevant foundations of non-hierarchical planning, i.e., no further lectures are required for participation). It's the lecuture's goal to enable its students to apply the hiearchical planning approach in practice.

For this, the lecture introduces various variants of hierarchical planning. It will make clear which formalism is the most appropriate for any given problem at hand. The students will be able to model a problem in the respective formalism and analyze its computational hardness. This allows, among others, to choose a suitable planning approach and heuristic, such that the modeled problem can be solved quickly.

Furthermore, the students will be able to use additional hierarchical planning capabilities, which allow them to realize intelligent assistant systems. They display plans on different levels of abstraction and rely on plan explanation and plan repair to provide flexible decision support to its users.

Contents

  • Foundations of *non-hierarchical* planning: STRIPS formalism, informed search, basic heuristics.
  • Formalization of different variants of hierarchical planning, in particular of the respective solution criteria.
  • Modeling of hierarchical planning problems.
  • Investigation of the expressivity via complexity analysis. Here, we will explore the differences of the expressivity compared to non-hierarchical planning.
  • Algorithms for solving hierarchical planning problems: state-based progression search and plan-based decompositional search.
  • State-of-the-art heuristics for the before-mentioned solution procedures of hierarchical planning.
  • User-centered extensions of hierarchical planning: plan explanation, plan repair, and visualization of plans for human users.

Recommended Literature

  • S. Russell, P. Norvig: Artificial Intelligence - A Modern Approach, Prentice Hall, 2010
  • Q. Yang: Intelligent Planning - A Decomposition and Abstraction Based Approach, Springer, 1997
  • M. Ghallab, D. Nau, P. Traverso: Automated Planning: Theory and Practice, Morgan Kaufmann, 2004
  • M. Ghallab, D. Nau, P. Traverso: Automated Planning and Acting, Cambridge University Press, 2016

Lecture Material and Further Information

  • The lecture will take place every Tuesday from 14:15 - 15:45 and Thursday from 16:15 - 17:45 in O27, 2202 (see LSF)
  • All materials will be made available in moodle. (You can not yet register for the lecture.)

Lecturer

Dr. Pascal Bercher

The lecture will be in english. If you have any further questions, please drop me an email.