Definition 10 (Atomic Preference Satisfaction) Let s *be a situation and* Φ = ϕ0[v0] ≫ ϕ1[v1] ≫ ... ≫ ϕn[vn] be an
atomic preference formula. Then ws**(Φ) =** vi if i = min j**{D |**= ϕj [S0, s]}*, and* ws(Φ) = vmax if no such i *exists.*
Definition 11 (General Preference Satisfaction) Let s be a situation and Φ *be a general preference formula. Then* ws(Φ) *is defined as follows:*
- ws(ϕ0 ≫ ϕ1 ≫ ... ≫ ϕn) *is defined above*
* $w_{s}(\varphi_{0}\not\ni\varphi_{1}\not\ni...\not\ni\varphi_{n})$ is defined above * $w_{s}(\gamma:\Psi)=\left\{\begin{array}{ll}v_{min}&\mbox{if}w_{s}(\gamma)=v_{max}\\ w_{s}(\Psi)&\mbox{otherwise}\end{array}\right.$ * $w_{s}(\Psi_{0}\not\in\Psi_{1}\not\in...\not\in\Psi_{n})=\max\{w_{s}(\Psi_{i}):1\leq i\leq n\}$ * $w_{s}(\Psi_{0}\mid\Psi_{1}\mid...\mid\Psi_{n})=\mbox{min}\left\{w_{s}(\Psi_{i}):1\leq i\leq n\right\}$

## The Following Definition Dictates How To Compare Two Situations (And Thus Two Plans) With Respect To A Gpf. This
Preference Relation **Pref** Is Used To Compare Htn Plans In
Definition 5 And Provides The Semantics For *More Preferred* In Definition 4.
Definition 12 (Preferred Situations) A Situation S1 *Is At Least As*
Preferred As A Situation S2 With Respect To A Gpf Φ*, Written*
Pref(S1, S2, Φ) If Ws1
(Φ) ≤ Ws2
(Φ). 4 Computing Preferred Plan

To compute a preferred plan, we proposed a heuristicsearch, forwarding-chaining planner that searchs for the most preferred terminating state that satisfies the HTN planning problem. The search is guided by an admissible evaluation function that evaluates partial plans with respect to preference satisfaction. We use *progression* to evaluate the preference formula satisfaction over partial plans.

## 4.1 Progression

Given a situation and a temporal formula, progression evaluates it with respect to the state of a situation to generate a new formula representing those aspects of the formula that remain to be satisfied. In this section, we define the progression of the constructs we added/modified from LPP and show that progression preserves the semantics of preference formulae. To define the progression, similar to
(Bienvenu, Fritz, and McIlraith 2006) we add the propositional constants TRUE and FALSE to both the situation calculus and to our set of BDFs, where D  TRUE and D 2 FALSE
for every action theory D. We also add the BDF **occNext**(X),
and **applyNext**(P(~v)) to capture the progression of occ(X) and **apply**(P(~v)). Below we show the progression of the added constructs.

Definition 13 (Progression) Let s be a situation, and let ϕ *be a* BDF. The progression of ϕ through s, written ρs(ϕ)*, is given by:*
- If ϕ=occ*(X) then* ρs(ϕ) = occNext(X) ∧*eventually*(**terminated**(X))
•8 If ϕ = **occNext**(X*) , then*
< :
TRUE if X **∈ A ∧ D |**= ∃s
′
.s = do(**X, s**′)
TRUE if X **∈ R ∧ D |**= ∃s
′
.s = do(start(X), s′)
FALSE otherwise
- If ϕ = **apply**(P(~v)), *then* ρs(ϕ) = applyNext(P(~v)) ∧*eventually*(terminated(P(~v)))
- If ϕ = **applyNext**(P(~v)) *, then* ρs(ϕ) = *TRUE if* D |= ∃s
′
.s = do(start(P(~v)), s′)
FALSE otherwise
- If ϕ = *before*(X1, X2), *holdBefore*(X, f), *holdAfter*(**X, f**),

or holdBetween$(X_{1},f,X2)$, then_  $$\rho_{s}(\varphi)=\left\{\begin{array}{ll}\mbox{TRUE}&\mbox{if}w_{s}(\varphi)=v_{min}\\ \mbox{FALSE}&\mbox{otherwise}\end{array}\right.$$
To see how the other constructs are progressed please refer to (Bienvenu, Fritz, and McIlraith 2006).

## 4.2 Admissible Evaluation Function

In this section, we describe an admissible evaluation function using the notion of *optimistic* and *pessimistic* weights
that provide a bound on the best and worst weights of any
successor situation with respect to a GPF Φ. Optimistic
(resp. pessimistic) weights, w
opt
s (Φ) (resp. w
pess
s (Φ)) are
defined based on optimistic (resp. pessimistic) satisfaction
of BDFs. Optimistic satisfaction (ϕ[s
′, s]
opt) assumes that
any parts of the BDF not yet falsified will eventually be
satisfied. Pessimistic satisfaction (ϕ[s
′, s]
pess) assumes
the opposite. The following definitions highlight the
key differences between this work and the definitions in
(Bienvenu, Fritz, and McIlraith 2006).
$\mathbf{occ}(X)[s^{\prime},s]^{opt}\stackrel{{\mathrm{def}}}{{=}}\left\{\begin{array}{ll}do(X,s^{\prime})\sqsubseteq s\lor s^{\prime}=s&\mbox{if$\mathbf{X}\in\mathcal{A}$}\\ do(start(X),s^{\prime})\sqsubseteq s\lor s^{\prime}=s&\mbox{if$\mathbf{X}\in\mathcal{R}$}\end{array}\right.$  $\mathbf{occ}(X)[s^{\prime},s]^{press}\stackrel{{\mathrm{def}}}{{=}}\left\{\begin{array}{ll}do(X,s^{\prime})\sqsubseteq s&\mbox{if$\mathbf{X}\in\mathcal{A}$}\\ do(start(X),s^{\prime})\sqsubseteq s&\mbox{if$\mathbf{X}\in\mathcal{R}$}\end{array}\right.$  $\mathbf{apply}(P(\vec{v}))[s^{\prime},s]^{opt}\stackrel{{\mathrm{def}}}{{=}}do(start(P(\vec{v})),s^{\prime})\sqsubseteq s\lor s^{\prime}=s$
do(**X, s**′) ⊑ s ∨ s
′ = s if X ∈ A
$\mathcal{L}$, $\pi$. 
apply(P(~v))[s
′
, s]
pess def = do(start(P(~v)), s′) ⊑ s If ϕ = before(X1, X2), holdBefore(X, f), holdAfter(**X, f**)
holdBetween(X1**, f, X**2), then ϕ[s
′
, s]
opt def = ϕ[s
′
, s]
pess def = ws′ ,s(ϕ)
Theorem 1 Let sn = do([a1, ..., an], S0), n ≥ 0 be a collection of situations, ϕ be a BDF, Φ *a general preference formula, and* w opt s (Φ), w pess s (Φ) *be the optimistic and pessimistic weights of* Φ
with respect to s*. Then for any* 0 ≤ i ≤ j ≤ k ≤ n, 1. D |= ϕ[si]
pess ⇒ D |= ϕ[sj], **D 6|**= ϕ[si]
opt **⇒ D 6|**= ϕ[sj ],
2. "w opt si
(Φ) = w pess si(Φ)"⇒ wsj
(Φ) = w opt si
(Φ) = w pess si(Φ),
3. w opt si
(Φ) ≤ w opt sj
(Φ) ≤ wsk
(Φ), w pess si(Φ) ≥ w pess sj(Φ) ≥ wsk
(Φ)
Theorem 1 states that the optimistic weight is nondecreasing and never over-estimates the real weight. Thus, fΦ is admissible and when used in best-first search, the search is optimal.

Definition 14 (Evaluation function) Let s = do(**~a, S**0) *be a* situation and let Φ *be a general preference formula. Then* fΦ(s)
def = ws(Φ) if ~a *is a plan, otherwise* fΦ(s)
def = w opt s (Φ).

## 5 Implementation And Results

In this section, we describe our best-first search, orderedtask-decomposition planner. Figure 1 outlines the algorithm.

HTNPREF takes as input P = (s0**, w, D, pref**) where s0 is the initial state, w the initial task network, D is the HTN planning domain, and *pref* the general preference formula, and returns a sequence of ground primitive operators, i.e. a plan, and the weight of that plan.

The *frontier* is a list of nodes of the form [optW, *pessW*,
w, partialP, s, *pref*], sorted by optimistic weight, pessimistic weight, and then by plan length. The frontier is initialized to the initial task network w, the empty partial plan, its optW,