SIFT researcher's paper published at 2012 Symposium on Combinatorial Search

Dr. Ugur Kuter collaborated with University of Maryland graduate students Ron Alford and Vikas Shivashankar and faculty Dr. Dana Nau on "HTN PRoblem Spaces: Structure, Algorithms, Termination" published at the 2012 Symposium on Combinatorial Search (SoCS-12), which can be accessed here: http://www.socs12.org/papers.html

This work is a purely theoretical analysis and comparison of different search spaces induced by several classes of HTN planning algorithms. In particular, 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.