HTN Problem Spaces: Structure, Algorithms, Termination

Authors

  • Ron Alford University of Maryland, College Park
  • Vikas Shivashankar University of Maryland, College Park
  • Ugur Kuter SIFT, LLC
  • Dana Nau University of Maryland, College Park

DOI:

https://doi.org/10.1609/socs.v3i1.18239

Keywords:

HTN planning, search spaces, termination

Abstract

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