# On Planning With Preferences In Htn

Shirin Sohrabi and **Sheila A. McIlraith**
Department of Computer Science University of Toronto Toronto, Canada.

{shirin,sheila}@cs.toronto.edu

## Abstract

In this paper, we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich qualitative user preferences. The outcome of our work is a language for specifying user preferences, tailored to HTN planning, together with a provably optimal preference-based planner, HTNPREF, that is implemented as an extension of **SHOP**2.

To compute preferred plans, we propose an approach based on forward-chaining heuristic search. Our heuristic uses an admissible evaluation function measuring the satisfaction of preferences over partial plans. Our empirical evaluation demonstrates the effectiveness of our **HTNPREF** heuristics.

We prove our approach sound and optimal with respect to the plans it generates by appealing to a situation calculus semantics of our preference language and of HTN planning. While our implementation builds on **SHOP**2, the language and techniques proposed here are relevant to a broad range of HTN
planners.

## 1 Introduction

Hierarchical Task Network (HTN) planning is a popular and widely used planning paradigm, and many domainindependent HTN planners exist (e.g., **SHOP**2, SIPE-2, IX/I-PLAN, O-PLAN) (Ghallab, Nau, and Traverso 2004). In HTN planning, the planner is provided with a set of tasks to be performed, possibly together with constraints on those tasks. A plan is then formulated by repeatedly decomposing tasks into smaller and smaller subtasks until primitive, executable tasks are reached. A primary reason behind HTN's success is that its task networks capture useful procedural control knowledge—advice on how to perform a taskdescribed in terms of a decomposition of subtasks. Such control knowledge can significantly reduce the search space for a plan while also ensuring that plans follow one of the stipulated courses of action. However, while HTNs specify a family of satisfactory plans, they are, for the most part, unable to distinguish what constitutes a high-quality plan.

In this paper, we address the problem of generating preferred plans by augmenting HTN planning problems with rich qualitative user preferences. User preferences can be arbitrarily complex, often involving combinations of conditional, interacting, and mutually exclusive preferences that can range over multiple states of a plan. This makes finding an optimal plan hard. There are two aspects to addressing the problem of preference-based planning with HTNs. The first is to propose a preference specification language that is tailored to HTN planning. The second, is to generate preferred, and ideally optimal, plans efficiently.

To specify user preferences, we augment a rich qualitative preference language, LPP, proposed in
(Bienvenu, Fritz, and McIlraith 2006) with HTN-specific constructs. LPP specifies preferences in a variant of linear temporal logic (LTL). Among the HTN-specific properties that we add to our language, LPH, is the ability to express preferences over how tasks in our HTN are decomposed into subtasks, preferences over the parameterizations of decomposed tasks, and a variety of temporal and nontemporal preferences over the task networks themselves.

To compute preferred plans, we propose an approach based on forward-chaining heuristic search. Key to our approach is a means of evaluating the (partial) satisfaction of preferences during HTN plan generation based on progression. The optimistic evaluation of preferences yields an admissible evaluation function which we use to guide search.

We implemented our planner, **HTNPREF**, as an extension to the **SHOP**2 HTN planner. Our empirical evaluation demonstrates the effectiveness of **HTNPREF** heuristics in finding high-quality plans. We provide a semantics for our preference language in the situation calculus (Reiter 2001) and appeal to this semantics to prove the soundness and optimality of our planner with respect to the plans it generates. This paper omits a number of technical details that can be found in a longer paper describing this work.

## 2 Htn Planning

In this section, we provide a brief overview of both HTN
planning, following (Ghallab, Nau, and Traverso 2004), and our situation calculus encoding of preference-based HTN
planning.

Travel Example: Consider a simple HTN planning problem to address the task of arranging travel. This task can be decomposed into arranging transportation, accommodations, and local transportation. Each of these tasks can again be decomposed based on alternate modes of transportation and accommodations, reducing eventually to primitive actions that can be executed in the world. Further constraints can be imposed to restrict decompositions.