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

Simple item page
dc.contributor.authorOlz, Cornelia
dc.contributor.refereeBiundo-Stephan, Susanne
dc.contributor.refereeNebel, Bernhard
dc.contributor.refereeHaslum, Patrik
dc.date.accessioned2024-08-07T09:34:37Z
dc.date.available2024-08-07T09:34:37Z
dc.date.created2023
dc.date.issued2024-08-07
dc.description.abstractAutomated 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.
dc.identifier.doihttps://doi.org/10.18725/OPARU-53481
dc.identifier.ppn1898077339
dc.identifier.urlhttps://oparu.uni-ulm.de/handle/123456789/53557
dc.identifier.urnhttp://nbn-resolving.de/urn:nbn:de:bsz:289-oparu-53557-9
dc.language.isoen
dc.publisherUniversität Ulm
dc.relation.haspartConny 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
dc.relation.haspartConny 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
dc.relation.haspartConny 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
dc.rightsLizenz A
dc.rights.urihttps://oparu.uni-ulm.de/handle/licenseA_v1
dc.subjectAI Planning
dc.subjectAutomated Planning
dc.subjectHTN Planning
dc.subject.ddcDDC 620 / Engineering & allied operations
dc.subject.gndKünstliche Intelligenz
dc.subject.lcshArtificial intelligence
dc.titleExploring the hierarchy: extracting and exploiting state information of compound tasks in HTN planning
dc.typeDissertation
dcterms.dateAccepted2024-04-08
uulm.affiliationGeneralFakultät für Ingenieurwissenschaften, Informatik und Psychologie
uulm.affiliationSpecificInstitut für Künstliche Intelligenz
uulm.bibliographieuulm
uulm.categoryPublikationen
uulm.thesisGrantorFakultät für Ingenieurwissenschaften, Informatik und Psychologie
uulm.typeDCMIText
uulm.updateStatusURNurl_update_general

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Thesis_Olz.pdf
Size:
2.13 MB
Format:
Adobe Portable Document Format
Download

Collections

Publikationen