Exploring the hierarchy: extracting and exploiting state information of compound tasks in HTN planning

Thumbnail Image

Files

Thesis_Olz.pdf (2.13 MB)

Date

2024-08-07

Authors

Olz, Cornelia

Journal Title

Journal ISSN

Volume Title

Publication Type

Dissertation

DOI

https://doi.org/10.18725/OPARU-53481

Published in

Abstract

Automated Planning is a domain-independent paradigm that can be applied to solve various problems in many areas such as robotics, autonomous factories, or assistance systems by finding a sequence of actions that an agent needs to perform in order to achieve a desired goal. In planning, the application domain is typically described using states and actions. States are represented as sets of propositional state features, and actions are characterized by their respective preconditions and effects, which in turn represent state changes. Hierarchical Task Network (HTN) planning extends this basic framework by introducing compound actions (also called abstract or compound tasks), which need to be refined into less abstract and eventually primitive actions according to predefined refinement rules. One limitation of the conventional HTN planning formalism is the lack of explicit state-change information for compound actions. These actions primarily serve as placeholders for potential sequences of primitive and compound actions, without clearly stating their implications on states. Such insights, however, can be valuable for both planning systems and domain modelers. This dissertation addresses this insufficiency by deriving state information of compound actions based on their refinements, focusing on three core contributions in total-order HTN planning: Firstly, a theoretical foundation is provided by formally defining several types of inferred preconditions and effects for compound actions and analyzing their computational complexity. The latter revealed that while directly computing these inferences is computationally intractable, an approximation exists that can be computed in polynomial time. Secondly, leveraging these inferred preconditions and effects, a look-ahead technique designed for search-based HTN planning systems has been developed. This novel technique can reduce the search space by identifying dead-ends and inevitable decomposition choices. Empirical evaluations show that incorporating this approach considerably improves the performance of state-of-the-art HTN planning systems, leading to several wins at the latest International Planning Competition. Thus, it pushes the boundaries of how quickly practical problems can be solved. Lastly, motivated by considerations for the look-ahead technique, the concept of conjunctive possible effects is introduced, which goes beyond the before-mentioned types of inferred preconditions and effects. These offer a more nuanced representation of state changes and are found to be computationally challenging even under several relaxations but fixed-parameter tractable for a fixed number of facts, making them practically useful for smaller problem instances. As a byproduct, this investigation also revealed new complexity results for the plan existence problem under precondition-relaxation.

Description

Faculties

Fakultät für Ingenieurwissenschaften, Informatik und Psychologie

Institutions

Institut für Künstliche Intelligenz

Citation

DFG Project uulm

EU Project THU

Other projects THU

Is version of

Has version

Supplement to

Supplemented by

Has erratum

Erratum to

Has Part

Conny Olz, Susanne Biundo, and Pascal Bercher. “Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis”. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021). AAAI Press, 2021, pp. 11903–11912. https://doi.org/10.1609/aaai.v35i13.17414
 Conny Olz and Pascal Bercher. “A Look-Ahead Technique for Search- Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements”. In: Proceedings of the 16th International Symposium on Combinatorial Search (SoCS 2023). AAAI Press, 2023, pp. 65–73. https://doi.org/10.1609/socs.v16i1.27284
 Conny Olz and Pascal Bercher. “Can They Come Together? A Computational Complexity Analysis of Conjunctive Possible Effects of Compound HTN Planning Tasks”. In: Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023). AAAI Press, 2023, pp. 314–323. https://doi.org/10.1609/icaps.v33i1.27209

Part of

DOI external

DOI external

Institutions

Periodical

Degree Program

DFG Project THU

item.page.thu.projectEU

item.page.thu.projectOther

Series

Keywords

AI Planning, Automated Planning, HTN Planning, Künstliche Intelligenz, Artificial intelligence, DDC 620 / Engineering & allied operations