HTN Planning with Utilities

Abstract

Hierarchical Task Network (HTN) planning is a popular automated planning technique used in many real-world applications. HTN planners can be categorized depending on the search space in which they operate. Our work here analyzes and enhances an existing state-based HTN planner in order to make it deal with consumption-sensitive domains while taking the risk attitudes of the various tasks, as well as potential cycles into account. A typical planning algorithm proceeds by decomposing tasks into smaller ones. This is usually done non-deterministically by picking one of applicable decomposition methods. However, this choice may greatly affect the final planning outcome. In domains, which place a high importance on the consumption of resources, it is of utmost importance to make an informed choice of the decomposition method. We propose to choose the method that promises the best results in terms of resource consumption based on an estimation, known as the utility that is calculated in a dedicated pre-processing phase that precedes the actual planning phase. Our main utility-aware planning algorithm takes these estimations into account. Furthermore, it adapts to the existence of cycles by trying to avoid the methods that may lead to them because entering a cycle by the planning algorithm means that it may repeatedly decompose tasks that were already decomposed. If this case is not handled, the planning algorithm may loop in the cycle infinitely. We prove the validity of our approach by presenting a prototypical implementation of the proposed algorithms. Furthermore, we evaluate the performance, usability, and the quality of the resulting plans of our approach and highlight its strengths and weaknesses compared to regular HTN planning.