HTN Problem Spaces: Structure, Algorithms, Termination
DOI:
https://doi.org/10.1609/socs.v3i1.18239Keywords:
HTN planning, search spaces, terminationAbstract
For HTN planning, we formally characterize and classify four kinds of problem spaces in which each node represents a planning problem or subproblem. Two of the problem spaces are searched by current HTN planning algorithms; the other two problem spaces are new.This enables us to provide:
- Sufficient (and in one case, necessary) conditions for finiteness of each kind of problem space. The conditions can be evaluated up-front to see if an HTN planning problem is finite.
- Loop-detection tests that can be used in HTN planners to ensure termination when the problem space is finite.
- A way to compute the correct value for an upper-bound parameter in an HTN-to-PDDL translation algorithm published in IJCAI-2009.
- Planning algorithms that utilize the two new problem spaces to guarantee termination on broader classes of planning problems than previous HTN planning algorithms.
Downloads
Published
2021-08-20
Issue
Section
Full Papers