HTN Problem Spaces: Structure, Algorithms, Termination

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.

Authors

• Ron Alford
• Vikas Shivashankar
• Ugur Kuter
• Dana S. Nau

Keywords

• HTN planning
• search spaces
• termination