of procedures in a ConGolog domain theory is referred to as
R.
We use a predicate *badSituation*(s) proposed by Reiter
(Reiter 2001) to encode the constraints in a task network.
The purpose of these constraints is to prune part of a search space similar to using temporal constraints.
To deal with partially ordered task networks, we add
two new primitive actions start(P(~v)), end(P(~v)), and two
new fluents *executing*(P(~v), s) and *terminated*(**X, s**), where P(~v) is a ConGolog procedure and X is either P(~v) or an
action a ∈ A. *executing*(P(~v), s) states that P(~v) is executing in situation s, *terminated*(**X, s**) states that X has terminated in s. *executing*(**a, s**) where a ∈ A is defined to be
false. The successor state axioms for these fluents follow.
They show how the actions start(P(~v)), end(P(~v)) change
the truth value of these fluents:
executing(P(~v), do(**a, s**)) ≡ a = *start*(P(~v))∨
executing(P(~v), s) ∧ a 6= end(P(~v))
terminated(X, do(**a, s**)) ≡ X = a∨
(X **∈ R ∧** a = end(X)) ∨ *terminated*(**X, s**)
where R is the set of ConGolog procedures in our domain.
Definition 5 (Preference-based HTN in Situation Calculus) An HTN planning problem with user preferences described as a
4-tuple P = (s0, w, D, Φhtn) is encoded in situation calculus as
a 5-tuple (D, C, ∆, δ0, Φsc) where D *is the basic action theory,*
C is the set of ConGolog axioms,∆ *is the sequence of procedure*
declarations for all ConGolog procedures in R, δ0 is an encoding
of the initial task network in ConGolog, and Φsc *is a mapping of*
the preference formula Φhtn in situation calculus. A plan ~a is a
solution to the encoded preference-based HTN problem if and *only* if:
$D\cup C=(\exists s)Do(\Delta;\delta_{0},S_{0},s)\wedge s=do(\vec{a},S_{0})$  $\wedge$ -badSituation$(s)\wedge\exists s^{\prime}.[Do(\Delta;\delta_{0},S_{0},s^{\prime})$  $\wedge$ -badSituation$(s^{\prime})\wedge pref(s^{\prime},s,\Phi_{sc})]$

## Where **Pref**(S
′**, S,** Φsc) Denotes That The Situation S
′Is Preferred To Situation S With Respect To The Preference Formula
Φsc, And Do(Δ, S0, Do(**~A, S**0)) Denotes That The Congolog
Program Δ, Starting Execution In S0 Will Legally Terminate
In Situation Do(**~A, S**0). Removing All The *Start*(P(~V)) And
End(P(~V)) Actions From ~A To Obtain ~B = (B1**, ..., B**N), A Preferred Plan For The Original Htn Planning Problem P Is A
Plan Π = (O1**, ..., O**N) Where For All 1 ≤ I ≤ N, Name(Oi)= Bi. 3 Htn Preference Specification

In this section, we describe how to specify the preference formula Φhtn. Our preference language, LPH, modifies and extends the LPP qualitative preference language proposed in (Bienvenu, Fritz, and McIlraith 2006) to capture HTN-specific preferences.

Our LPH language has the ability to express preferences over certain parameterization of a task (e.g., preferring one task grounding to another), over a certain decomposition of nonprimitive tasks (i.e., prefer to apply a certain method over another), and a soft version of the before, after, and in between constraints. A soft constraint is defined via a preference formula whose evaluation determines when a plan is more preferred than another. However, unlike the task network constraints which will prune or eliminate those plans

that have not satisfied them, not meeting a soft constraint simplify deems a plan to be of poorer quality.
Definition 6 (Basic Desire Formula (BDF)) *A basic desire*
formula is a sentence drawn from the smallest set B *where:*
1. If l *is a literal, then* l ∈ B and *final*(l) ∈ B 2. If t is a task, then occ(t) ∈ B
3. If m *is a method, and* n = **name**(m), then *apply*(n) ∈ B
4. If t1, and t2 are tasks, and l *is a literal, then*
before(t1, t2), *holdBefore*(t1, l), *holdAfter*(t1, l), holdBetween(t1**, l, t**2) *are in* B.
5. If ϕ1 and ϕ2 are in B*, then so are* ¬ϕ1, ϕ1 ∧ ϕ2, ϕ1 ∨ ϕ2,
(∃x)ϕ1, (∀x)ϕ1, next(ϕ1), always(ϕ1), *eventually*(ϕ1),
and *until*(ϕ1, ϕ2).
final(l) states that the literal l holds in the final state, occ(t)
states that the task t occurs in the present state, and **next**(ϕ1), always(ϕ1), **eventually**(ϕ1), and **until**(ϕ1, ϕ2) are basic LTL constructs. **apply**(n) states that a method whose name is n is applied to decompose a nonprimitive task. before(t1, t2)
states a precedence ordering between two tasks. holdBefore(t1, l), holdAfter(t1, l), holdBetween(t1**, l, t**2) state a soft
constraint over when the fluent l is preferred to hold. (i.e.,
holdBefore(t1, l) state that l must be true right before the last
operator descender of t1 occurs). Combining occ(t) with
the rest of LPH language enables the construction of preference statements over parameterizations of tasks.
BDFs establish properties of different states within a plan.
By combining BDFs using boolean and temporal connectives, we are able to express other properties of state. The
following are a few examples from our travel domain1.
($\exists c$).occ${}^{\prime}$(book-car($c$, Enterprise))  apply${}^{\prime}$(by-car-local(SUV, Avis))  before(_arrange-trans_, arrange-acc_)  buildBaffles($b$, $\forall b$).  
′
(*book-car*(**c, Enterprise**)) (P1)
holdBefore(**hotelReservation,** *arrange-trans*) (P4)
always(¬(occ
′
(pay(Mastercard**))))** (P5)
(∃h, r).occ
′
(*book-hotel*(**h, r**)) ∧ *starsGE*(r, 3) (P6)
(∃c).occ
′
(book-flight(c, Economy, Direct, *WindowSeat*))
∧ member(c, *StarAlliance*) (P7)
P1 states that at some point the user books a car with
Enterprise. P2 states that at some point, the *by-car-local* method is applied to book an SUV from Avis. P3 states that the *arrange-trans* task occurs before the *arrange-acc* task.
P4 states that the hotel is reserved before transportation is arranged. P5 states that the user never pays by Mastercard. P6
states that at some point the user books a hotel that has a rating of 3 or more. P7 states that at some point the user books
a direct economy window-seated flight with a Star Alliance
carrier.
To define a preference ordering over alternative properties
of states, *Atomic Preference Formulae* (APFs) are defined. Each alternative comprises two components: the property
of the state, specified by a BDF, and a *value* term which
stipulates the relative strength of the preference.
$$\begin{array}{l}{{m g e\mbox{-}t r a m s)}}\\ {{}}\\ {{}}\\ {{}}\\ {{:G E(r,3)}}\end{array}$$
$\frac{1}{2}$  3. 
1To simplify the examples many parameters have been suppressed, and we abbreviate **eventually(occ**(ϕ)) by occ′, eventually(**apply**(ϕ)) by **apply**′and refer to preferences by their labels.