Exploiting the structure of hierarchical plans in temporal constraint propagation

This paper describes a means to exploit the structure of a HTN plan in performing temporal propagation on an associated Simple Temporal Network, and results indicate an order of magnitude improvement on real-world plans.

Abstract

Quantitative temporal constraints are an essential requirement for many planning domains. The HTN planning paradigm has proven to be better suited than other approaches to many ap-plications. To date, however, efficiently integrating temporal reasoning with HTN planning has been little explored. This paper describes a means to exploit the structure of a HTN plan in performing temporal propagation on an associated Simple Temporal Network. By exploiting the natural restriction on permitted temporal constraints, the time complexity of prop-agation can be sharply reduced, while completeness of the inference is maintained. Empirical results indicate an order of magnitude improvement on real-world plans.