PhD Project: Generating Abstract Plans in HTN Planning

Description

Hierarchical Planning is a planning formalism that's concerned with the step-wise refinement of abstract tasks until a primitive plan is found -- so hierarchical planning is completely similar formal grammars, where an initial non-terminal is refined into a sequence of terminal symbols. The main differences are that (a) primitive tasks (corresponding to terminal symbols) have preconditions and effects, to not every plan is executable and (b) the means to refine compound tasks (which correspond to production rules from formal grammars) are only partially ordered rather than totally as in formal grammars.

Solution plans in HTN planning are, similar to formal grammars, totally ordered primitive action sequences (that are executable). However, such solutions are often generated by relying on *search* in the space of task networks that still contain non-primitive tasks. It is of practical interest to find criteria that allow to stop search with such a partially abstract, partially primitive task network, i.e., before every an *actual* solution has been generated. This is called an abstract plan (or abstract solution). Usually only such abstract plans are returned for which it can be proved that a solution will be found eventually. For that purpose abstract tasks are often associated with preconditions and effects, and they are exploited to investigate their impact on the states produced by the respective plans.

This thesis will cover theoretical foundations as well practical implementations (with a focus on the former) related to the endeavor of creating abstract solution plans when abstract tasks use preconditions and effects.

Goals

  • Survey the existing Literature related to this topic
  • Review existing criteria for which is can be proved that a partially abstract plan can be turned into a solution and set it into the context of new research results and develop new criteria under which this can be guaranteed
  • Investigate the theoretical complexity of the arising decision problems
  • Implement a planning system that exploits the developed techniques

Requirements

  • A solid understanding of the basics of computational complexity (e.g., the classes P, NP, NP-complete, etc.)
  • Knowledge in Classical Planning and Artificial Intelligence search (such as A*)
  • Prior Knowledge in Hierarchical Planning is useful, bot not required

Background Literature

  • Pascal Bercher, Ron Alford, Daniel Höller: A Survey on Hierarchical Planning – One Abstract Idea, Many Concrete Realizations. IJCAI 2019, p.6267-6275. ijcai.org
  • Pascal Bercher, Daniel H{\"o}ller, Gregor Behnke, and Susanne Biundo. More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks. ECAI 2016
  • Bhaskara Marthi and Stuart J. Russell and Jason Wolfe. Angelic Semantics for High-Level Actions. ICAPS 2007.
  • Bhaskara Marthi and Stuart Russell and Jason Wolfe. Angelic Hierarchical Planning: Optimal and Online Algorithms. ICAPS 2008.
  • Stuart Russell and Peter Norvig. Artificial Intelligence - A modern Approach (newest version). (Bookchapter on Angelic Semantics)
  • Fahiem Bacchus and Qiang Yang. Downward refinement and the efficiency of hierarchical problem solving. Artificial Intelligence 1994
  • Craig A. Knoblock. Automatically Generating Abstractions for Planning. Artificial Intelligence 1994
  • Qiang Yang. Formalizing Planning Knowledge for Hierarchical Planning. Computational Intelligence 1990

Gain

  • Pursue state-of-the-art research in Artificial Intelligence Planning
  • Conduct both theoretical investigation and get practical experience in programming high-performance code

Keywords

  • Complexity Theory
  • Artificial Intelligence
  • Automated Planning

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing