Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks - A Complexity Analysis
Date
2021-05-18
Authors
Olz, Conny
Biundo, Susanne
Bercher, Pascal
Journal Title
Journal ISSN
Volume Title
Publisher
The AAAI Press
Abstract
In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not show preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are "hidden" in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. The results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.
Description
Keywords
Citation
Olz, C., Biundo, S., & Bercher, P. (2021). Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11903-11912. https://doi.org/10.1609/aaai.v35i13.17414
Collections
Source
Type
Conference paper
Book Title
Entity type
Access Statement
Open Access
License Rights
Restricted until
Downloads
File
Description