Fully Observable Nondeterministic HTN Planning -- Formalisation and Complexity Results
| HTN Planning FOND Planning Planning under Uncertainty Plan Existence Problem Computational Complexity |
PaperID: 44
pdf
poster
|
| Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the complexity of HTN problems on nondeterministic domains. In this paper we renew and extend existing HTN planning formalisations to fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify intriguing similarities and differences with plans in other fields of AI planning. We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios. | |
Session 3: Hierarchical Task Networks
Block Compression and Invariant Pruning for SAT-based Totally-Ordered HTN Planning
Authors: Gregor Behnke
Keywords:
HTN PlanningSAT-based PlanningPruning
Translating Totally Ordered HTN Planning Problems to Classical Planning Problems Using Regular Approximation of Context-Free Languages
Authors: Daniel Höller
Keywords:
HTN planningplanning systemtranslationclassical planning
Fully Observable Nondeterministic HTN Planning -- Formalisation and Complexity Results
Authors: Dillon Chen and Pascal Bercher
Keywords:
HTN PlanningFOND PlanningPlanning under UncertaintyPlan Existence ProblemComputational Complexity
Loop Detection in the PANDA Planning System
Authors: Daniel Höller and Gregor Behnke
Keywords:
HTN planningloop detectiongraph search