Research Project: On the Relationship between HTN planning and Formal Grammars

People

Supervisor

Description

Hierarchical Task Network (HTN) planning problems are well-known to be closely related to formal (context-free) grammars. The main difference is two-fold:

  • In HTN planning, primitive actions have preconditions and effects (i.e., they are actions which are ony applicable in certan world states), whereas terminal symbols in formal grammars are not. Otherwise terminal symbols correspond to actions. Likewise, compound HTN tasks are identical to non-terminal symbols. And, finally, decomposition methods correcpond to production rules.
  • The second difference is that decompostiion methods in HTN planning map to a partial order of tasks, whereas production rules map to a total order of symbols.

This very close relationship was already studied in detail int the literature, showing that total-order HTNs are equivalent to context-free grammars, and arbitrary HTN problems lie strictly between context-free and context-sensitive languages.

In this work, these similarities should be studied further. In particular, we are going to investigate:

  • Closedness properties (e.g., it's known that context-free languages are closed under intersection, which therefore holds for totally ordered problems as well -- but this is not yet clear for other classes of HTN problems)
  • Normal forms, i.e, the goal is to find out how hard it is to check whether a certain HTN problem (satisfying certan requirements, like being acyclic etc.) can be transformed into a more restricted form. This shall be studied in theory (i.e., check its computational complexity) and in practice, i.e., make the respective transformations.

Goals

  • Analyze theoretical properties of the language induced by various forms on HTN planning problems (depending on enforced restrictions)

Requirements

  • A solid understanding of formal grammars and the basics of computational complexity (e.g., the classes P, NP, NP-complete, etc.)
  • Having fun in formalizing!
  • Knowledge in Classical Planning in particular or Articial Intelligence in general is very helpful, but not required.
  • For this very project (for other projects it's definitely different) I will only accept students who have clearly straight HD grades, in particular in all theory-related courses.
  • I also accept Mathematicians, as long as you have a solid understanding of related content, such as graph theory.

Please send me:

  • The course code.
  • The URL of your course.
  • The number of points your course has (i.e., 6, 12, 24, or 24 honours final project).
  • When you would like to do your project.

Background Literature

  • The two papers by Daniel Höller et al. from ECAI 2014 and ICAPS 2016. Im a co-author, so you'll find both in my publication list.

Gain

  • A deeper understanding of HTN planning and formal grammars, including being able to conduct formal proofs.
  • This work should be published at an A*/top-tier conference or journal.

Keywords

  • Complexity Theory
  • Formal Grammars, Formal Languages
  • Theoretical Computer Science
  • Artificial Intelligence
  • Automated Planning

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing