

![0_image_0.png](0_image_0.png)

## 2. Background And Notation

Given a planning problem with the set of solution plans S, a user preference *model* is a transitive, reflextive relation in S×S, which defines an ordering between two plans p and p
′in S. Intuitively, p  p
′ means that the user prefers p at least as much as p
′. Note that this ordering can be either partial (i.e. it is possible that neither p  p
′ nor p
′  p holds—in other words, they are incomparable), or total (i.e. either p  p
′ or p
′  p holds). A plan p is considered more preferred than a plan p
′, denoted by p ≺ p
′, if p  p
′, p
′ 6 p, and they are equally preferred if p  p
′
and p
′  p. A plan p is an optimal (i.e., most preferred) plan if p  p
′for any other plan p
′. A
plan set **P ⊆ S** is considered more preferred than P
′ ⊆ S, denoted by **P ≺ P**′, if p ≺ p
′for any p ∈ P and p
′ ∈ P′, and they are incomparable if there exists p ∈ P and p
′ ∈ P′such that p and p
′are incomparable.

The ordering  implies a partition of S into disjoint plan sets (or *classes*) S0, S1, ... (S0 ∪
S1 ∪ ... = S, Si ∩ Sj = ∅) such that plans in the same set are equally preferred, and for any set Si, Sj , either Si ≺ Sj , Sj ≺ Si, or they are incomparable. The partial ordering between these sets can be represented as a Hasse diagram (Birkhoff, 1948) where the sets are vetices, and there is an (upward) edge from Sj to Siif Si ≺ Sj and there is not any Sk in the partition such that Si ≺ Sk ≺ Sj . We denote l(Si) as the "layer" of the set Siin the diagram, assuming that the most preferred sets are placed at the layer 0, and l(Sj ) = l(Si**) + 1** if there is an edge from Sj to Si. A plan in a set at a layer with the smaller value, in general, is either more preferred than