Definition 1 (HTN Planning Problem) *An HTN planning problem is a 3-tuple* P = (s0**, w, D**) where s0 *is the initial state,* w is a task network called the initial task network, and D is the HTN planning domain. P *is a total-order planning problem if w and* D
are totally ordered; otherwise it is said to be partially ordered.

A *task* consists of a task symbol and a list of arguments.

A task is primitive if its task symbol is an operator name and its parameters match, otherwise it is *nonprimitive*. In our example, *arrange-trans* and *arrange-acc* are nonprimitive tasks, while *book-flight* and *book-car* are primitive tasks.

Definition 2 (Task Network) A task network is a pair w=(U, C) where U is a set of task nodes and C is a set of constraints. Each task node u ∈ U contains a task tu. If all of the tasks are ground then w is ground; If all of the tasks are primitive, then w is called primitive; otherwise is called nonprimitive. Task network w is totally ordered if C *defines a total ordering of the nodes in U.*
In our example, we could have a task network (**U, C**)
where U = {u1, u2}, u1 =*book-car*, and u2= pay, and C is a precedence constraint such that u1 must occur before u2 and a before-constraint such that at least one car is available for rent before u1.

A domain is a pair D = (**O, M**) where O is a set of operators and M is a set of methods. Operators are essentially primitive actions that can be executed in the world. They are described by a triple *o =(name(o), pre(o), eff(o))*, corresponding to the operator's name, preconditions and effects.

Preconditions are restricted to a set of literals, and effects are described as STRIPS-like Add and Delete lists. An operator o can accomplish a ground primitive task in a state s if their names match and o is applicable in s. In our example, ignoring the parameters, operators might include: pay, book-train, book-car, book-hotel, and *book-flight*.

A method, m, is a 4-tuple (*name(m), task(m),subtasks(m),*
constr(m)) corresponding to the method's name, a nonprimitive task and the method's task network, comprising subtasks and constraints. A method is *totally ordered* if its task network is *totally ordered*. A domain is a total-order domain if every m ∈ M is *totally ordered*. Method m is relevant for a task t if there is a substitution σ such that σ(t) =*task*(m).

Several different methods can be relevant to a particular nonprimitive task t, leading to different decompositions of t. In our example, the method with *name by-flight-trans* can be used to decompose the *task arrange-trans* into the *subtasks* of booking a flight and paying, with the constraint (*constr*) that the booking precede payment.

Definition 3 (Solution to HTN Planning Problem) Given HTN
planning problem P = (s0**, w, D**)*, a plan* π = (o1**, ..., o**k) is a solution for P, depending on these two cases: 1) if w is primitive, then there must exist a ground instance of (U
′
, C′*) of (U, C) and* a total ordering (u1**, ..., u**k) *of the nodes in* U
′
*such that for all* 1 ≤ i ≤ k, name(oi ) = tui
, the plan π *is executable in the state* s0, and all the constrains hold, 2) if w is nonprimitive, then there must exist a sequence of task decompositions that can be applied to w to produce a primitive task network w
′
, where π *is a solution for* w
′
.

Finally, we define the HTN preference-based planning problem. This definition appeals to two concepts that are not yet well-defined and which we defer to later sections:
definitions of the form and content of the the formula Φhtn that captures user preferences for HTN planning as well as and the precise definition of *more preferred* appears in Section 3.

Definition 4 (Preference-based HTN Planning) *An HTN planning problem with user preferences is described as a 4-tuple* P =
(s0, w, D, Φhtn) *where* Φhtn is a formula describing user preferences. A plan π is a solution to P if and only if: π *is a plan for* P
′ = (s0**, w, D**) *and there does not exists a plan* π
′
*such that* π
′
is more preferred than π *with respect to the preference formula* Φhtn.

## 2.1 Situation Calculus Specification Of Htn

We now have a definition of preference-based HTN planning. Later in the paper, we propose an approach to computing preferred plans, together with a description of our implementation. To prove the correctness and optimality of our algorithm, we appeal to an existing situation calculus encoding of HTN planning, which we augment and extend to provide an encoding of preference-based HTN planning. Since the situation calculus has a well-defined semantics, we have a semantics for our encoding which we use in our proofs. In this section, we review the salient features of this encoding.

The Situation Calculus is a logical language for specifying and reasoning about dynamical systems (Reiter 2001).

In the situation calculus, the *state* of the world is expressed in terms of functions and relations (fluents) relativized to a particular *situation* s, e.g., F(**~x, s**). A situation s is a *history* of the primitive actions, a ∈ A, performed from a distinguished initial situation S0. The function do(**a, s**) maps a situation and an action into a new situation thus inducing a tree of situations rooted in S0. A *basic action theory* in the situation calculus D includes *domain independent foundational axioms*, and *domain dependent axioms*. A situation s
′
precedes a situation s, i.e., s
′ ⊏ s, means that the sequence s
′is a proper prefix of sequence s.

Golog (Reiter 2001) is a high-level logic programming language for the specification and execution of complex actions in dynamical domains. It builds on top of the situation calculus by providing Algol-inspired extralogical constructs for assembling primitive situation calculus actions into complex actions (*programs*) δ. Example complex actions include action sequences, if-then-else, while loops, nondeterministic choice of actions and action arguments, and procedures. These complex actions serve as constraints upon the situation tree. ConGolog
(De Giacomo, Lesp´erance, and Levesque 2000) is the concurrent version of Golog in which the language can additionally deal with execution of concurrent processes, interrupts, prioritized concurrency, and exogenous actions.

A number of researchers have pointed out the connection between HTN and ConGolog. Following Gabaldon
(Gabaldon 2002), we map an HTN state to a situation calculus *situation*. Consequently, the initial HTN state s0 is encoded as the initial situation, S0. The HTN domain description maps to a corresponding situation calculus domain description, D, where for every operator o there is a corresponding primitive action a, such that the preconditions and the effects of o are axiomatized in D. Every method and nonprimitive task together with constraints is encoded as a ConGolog procedure. For the purposes of this paper, the set