Translating Totally Ordered HTN Planning Problems to Classical Planning Problems Using Regular Approximation of Context-Free Languages
| HTN planning planning system translation classical planning |
PaperID: 38
pdf
poster
|
| There have been several approaches to use techniques from classical planning in HTN planning. While a direct translation is in general not possible due to the different expressiveness, there have been translations of bounded HTN problems and approaches to use classical heuristics in HTN search procedures. In this paper, we introduce a different approach. We exploit methods from the field of Computational Linguistics introduced to approximate Context-Free Languages by Finite Automata. We use them to approximate the decomposition structure of totally ordered (TO) HTN planning problems by classical problems. The resulting problem can then be solved using standard classical planning systems. A subset of TOHTN problems can be translated exactly, i.e., without changing the set of solutions. For problems where an approximation is necessarily, we use an overapproximation, i.e., the set of solutions to the classical problem is a superset of that of the HTN problem. We then use plan verification to check whether a solution is valid and thus obtain a sound and complete overall solver. The resulting system outperforms the state of the art on the IPC 2020 benchmark set in terms of coverage. | |
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