Reprinted from Proceedings of the Sixth International Symposium on Methodologies for Intelligent Systems (ISMIS’91), October, 1991, Z. W. Ras and M. Zemankova, editors, Berlin: Springer-Verlag, pp. 16–31.

A Logic of Relative Desire

(Preliminary Report)

Jon Doyle MIT Laboratory for Computer Science 545 Technology Square Cambridge, MA 02139

             doyle@lcs.mit.edu

Yoav Shoham Department of Computer Science Stanford University Stanford, CA 94305

                                          shoham@cs.stanford.edu

Michael P. Wellman Wright Laboratory AI Office WL/AAA-1 Wright-Patterson AFB, OH 45433

                           wellman@wrdc.af.mil

Abstract: Although many have proposed formal characterizations of belief structures as bases for rational action, the problem of characterizing rational desires has attracted little attention. AI relies heavily on goal conditions interpreted (apparently) as absolute expressions of desirability, but these cannot express varying degrees of goal satisfaction or preferences among alternative goals. Our previous work provided a relative interpretation of goals as qualitative statements about preferability, all else equal. We extend that treatment to the comparison of arbitrary propositions, and develop a propositional logic of relative desire suitable for formalizing properties of planning and problem-solving methods.

1 Introduction

Question your desires.—William Shakespeare

Standard theories of rational action take decisions of the agent to depend on beliefs about the relative desirability of the results of its available actions [2, 3]. The predominant approach to planning in artificial intelligence represents desires by conditions on the state of the world called goals. Each goal represents a partition of possible states into those satisfying and those not satisfying the goal. Goals serve a dual role in most planning systems, capturing aspects of intentions as well as desires [1]. Besides expressing the desirability of a state, adopting a goal typically represents some commitment to pursuing that state.

In perhaps the simplest interpretation of goals as desires, the states satisfying the goal are considered desirable in an absolute sense. That is, goal conditions define a partition of states into the desirable and the undesirable. However, this crude binary distinction proves inadequate in realistic situations. These satisfy objectives to varying degrees, and an absolute notion of desire cannot distinguish among alternative plans that ensure achievement of goals, nor among plans that fail to guarantee goal achievement.

We can support finer distinctions by expressing the relative desirability of alternate states. For example, we might hold that achieving conditions p and q would be more desirable than achieving neither, but that if we can achieve only one we would prefer to achieve p. Decision-theoretic preference orders express exactly these sorts of comparisons, and in related work [7], we provide a decision-theoretic semantics for goals in terms of preference orders and multiattribute outcome spaces. In our semantics, we relativize the notion of goal by restricting preference comparisons to fixed contexts. Specifically, we call a condition p a goal or desire if and only if (iff) p is preferred to ¬p, holding all other properties constant. Unlike the absolute interpretation, this relative concept admits multiple desires or goals. That is, desiring both p and q means preferring each one to its negation, holding the other constant.

In this paper, we extend our previous work in two primary directions. First, we consider relative desire between arbitrary conditions, in addition to that between a goal condition and its negation. Second, we formalize the concept of relative desire over conditions expressed in a propositional language. The resulting logic provides a general framework for representing and reasoning about desires. While such frameworks are common for beliefs, formal theories of desires have heretofore been conspicuously absent in artificial intelligence as well as philosophy [4].

We begin by introducing the basic notion of preference over models, which serves as the fundamental concept underlying our definition of relative desire over logical sentences. We follow by developing a collection of inference rules by which relative desires among some sentences entail desires over related sentences. We further extend the formalism by considering restrictions imposed by knowledge or constitution on preferences, and how relative desire varies with these restrictions.

2 Preference over models

Let L denote a logical language over a set of atoms A and the standard connectives ¬, ∧, ∨, →, and ↔. The literals of L consist of just the atoms and their negations, that is, A ∪ {¬a | a ∈ A}. More generally, we write literals(A), for any subset A ⊆ A, to mean A ∪ {¬a | a ∈ A}. In the following, we write a, a′, … to denote atoms; l, l′, … to denote literals; c, c′, d, … to denote conjunctions of literals; and p, q, r, … to denote sentences in L. We write true and false to denote arbitrary formulas of the form p ∨ ¬p and p ∧ ¬p, respectively.

A model of L assigns truth values to all atoms of L, and so, by the usual logical rules, to all sentences in L. We represent models by complete consistent sets of literals. Thus m ⊂ literals(A) represents a model just in case exactly one of a and ¬a is in m for each a ∈ A, and we say that m makes a true (resp. false) just in case a ∈ m (resp. ¬a ∈ m). (We may thus view a conjunction c of literals over different atoms as a sentence representing a partial model.) We write M to mean the set of all models of L, and write m, m′, … to denote individual models.

Following the standard definition, we say that a model m satisfies a sentence p, written m ⊧ p, if the truth values it assigns to the atoms in p make p true; that is, m ⊧ a iff a ∈ m; m ⊧ p ∧ q iff m ⊧ p and m ⊧ q; m ⊧ ¬p iff m |̸= p, etc. As usual, we write p ⊧ q to mean that every model satisfying p also satisfies q. If every model in M satisfies p, we write ⊧ p and say that p is valid.

A proposition is a set of models. We define [[p]], the proposition corresponding to p, by

[[p]] =^{def} {m ∈ M | m ⊧ p}.

For a literal l, therefore, [[l ∈ M]] = {m | l ∈ m}.

Decision theory builds on the notion of preferences over outcomes or possible states of the world. It captures a notion of ideal rationality by requiring complete and consistent preferences, and by requiring that the agent always chooses actions leading to the most preferred outcomes.

In the logic of relative desire, we represent outcomes or states of the world by models, and so consider preferences over M. We represent the agent’s preferences by a preorder (a reflexive and transitive relation) ∼ ≻ over M, called the preference order. (We do not require here decision theory’s standard assumption making ∼ ≻ complete.) When m ∼ ≻ m′ we say that m is weakly preferred to m′, which means that m is at least as desirable as m′. The strict preference order ≻ consists of the irreflexive part of ∼ ≻, that is, m ≻ m′ (m is preferred to m′) iff m ∼ ≻ m′ but m′ ≁ ≻ m. When both m ∼ ≻ m′ and m′ ∼ ≻ m, we say the two models are indifferent, and write m ∼ m′.

Much work in decision theory concerns conditions under which one can represent ∼ ≻ by order-preserving, real-valued utility functions, and with identifying regularities in preferences that justify utility functions with convenient structural properties [3]. Although we expect that utility theory will have much to offer for a calculus of desires for reasoning systems, our logic relies only on the ordinal preference relation, not on any numerical representations.

We may lift the preference order over models to the set of propositions 2^{M} by defining P ∼ ≻ Q, for P, Q ⊆ M, to hold iff m ∼ ≻ m′ for each m ∈ P and m′ ∈ Q, and by defining the lifted relations ≻ and ∼ similarly. Clearly, if P ≻ Q, then P and Q must be disjoint. We may further translate the preference order into an order over sentences by saying that p ∼ ≻ q holds iff [[p]] ∼ ≻ [[q]].

The relation over propositions or sentences defined by simply lifting and translating the fundamental preference order, however, fails to support useful ways of combining multiple preferences, and hence cannot provide an adequate semantics for relative desires. For example, suppose we represent the desirability of p by the relation p ∼ ≻ ¬p. Then having several desirable sentences prevents us from distinguishing all but the extreme cases, as shown by the following result.

Theorem 1 (No tradeoffs) Suppose p_{i} ∼ ≻ ¬p_{i} for 0 ≤ i ≤ n, with p_{i} and p_{j} logically independent for i ≠ j. Then

1. Any model that satisfies every p_{i} is weakly preferred to any model that does not,

2. Any model that satisfies at least one p_{i} is weakly preferred to any model that falsifies every p_{i}, and

3. All models that satisfy some p_{i} and falsify some p_{j} are indifferent.

Proof: By definition, the hypothesis entails [[p_{i}]] ∼ ≻ [[¬p_{i}]] for 0 ≤ i ≤ n.

1. Let m satisfy all p_{i} and m′ falsify sentence p_{j}. Therefore m ∈ [[p_{j}]] and m′ ∈ [[¬p_{j}]], so m ∼ ≻ m′.

2. Let m satisfy sentence p_{j} and m′ falsify all p_{i}. Therefore m ∈ [[p_{j}]] and m′ ∈ [[¬p_{j}]], so m ∼ ≻ m′.

3. By pairwise logical independence, we may find a model m_{i,j} satisfying sentence p_{i} and falsifying p_{j} for any 0 ≤ i, j ≤ n, i ≠ j. Because m_{i,j} ∈ [[p_{i}]] and m_{k,i} ∈ [[¬p_{i}]], we conclude m_{i,j} ∼ ≻ m_{k,i} for all k ≠ i. Similarly, m_{k,i} ∼ ≻ m_{l,k} for all l ≠ k. By transitivity of weak preference, we have m_{i,j} ∼ ≻ m_{l,k}. A symmetric argument yields m_{l,k} ∼ ≻ m_{i,j}, hence m_{i,j} ∼ m_{l,k}. □

This result means that the simplistic translation of preference over models to desirability of sentences distinguishes only three degrees of multiple goal satisfaction: total success, partial success, and total failure. While one often wishes to consider tradeoffs among partial successes, this interpretation makes them preferentially indistinguishable.

3 Relative desire

To obtain a semantic account of desire that permits differentiation of partial satisfactions of multiple desires, we relativize the absolute interpretation to specific contexts and say that a sentence represents a desire if it is preferred to its contrary, other things equal. Understood in this way, worlds corresponding to a desire need not be preferred no matter what, only within each fixed context.

The support of a sentence p, denoted support(p), consists of the minimal set of atoms determining the truth value of p, for example, the atoms appearing in an irredundant sumof-products sentence logically equivalent to p (that is, a sentence in which each product term is a prime implicant of p and in which removing any product term destroys the logical equivalence with p). We say that specific sentences have disjoint support if their respective supports do not overlap.

Definition 1 (Model equivalence) We say that m and m′ are equivalent modulo p, written m ≡ m′ mod p, iff they are the same outside of support(p), or formally

m \ (literals(support(p)) = m′ \ (literals(support(p)).

Definition 2 (Model modification) The set of modifications of a model m making p true, written m[p], is the set of models of p which assign the same truth values as m to all atoms other than those on which p depends, or formally,

m[p] =^{def} {m′ ∈ [[p]] | m ≡ m′ mod p}.

Definition 3 (Relative desire) We say that p is desired over q, written p ≥ q and read briefly as “p over q,” iff for each m ∈ M, m′ ∈ m[p ∧ ¬q], and m′′ ∈ m[¬p ∧ q] we have m′ ∼ ≻ m′′. We say that p is strictly desired over q, written p > q, iff p ≥ q but not q ≥ p.

That is, p is desired over q just in case any model making p true and q false is weakly preferred to any model making p false and q true, whenever the two models assign the same truth values to all atoms not relevant to those supporting p and q. Furthermore, p is strictly desired over q just in case this preference is strict for some pair of models.

Theorem 2 (Logical invariance) If ⊧ p ↔ p′, then m[p] = m[p′], and if ⊧ q ↔ q′ as well, then p ≥ q iff p′ ≥ q′.

We omit the obvious proof and a few other proofs due to space limitations.

Theorem 3 (General contraposition) If p ∧ r ≥ q ∧ r, then ¬q ∧ r ≥ ¬p ∧ r.

Theorem 4 (General reflexivity) If ⊧ p → p′, then p ≥ p′ and p′ ≥ p.

This means that relative desire does not distinguish sentences from stronger or weaker conditions (including true and false), so the interesting cases of relative desire all concern relations among logically independent conditions.

We extend the model modification operation to sets of models M ⊆ M by defining

M[p] =^{def} ⋃_{m∈M} m[p].

We may thus write serial modifications by left-associating the modification operator, with m[p][q] = (m[p])[q].

Lemma 5 (Covering) If support(p) ⊆ support(q) and m ≡ m′ mod p, then m ≡ m′ mod q and m[q] = m′[q].

Proof: Suppose support(p) ⊆ support(q). Since

m \ literals(support(p)) = m′ \ literals(support(p)),

it follows that m \ literals(support(q)) = m′ \ literals(support(q)),

hence m[q] = m′[q]. □

Lemma 6 (Reduction) support(p) ⊆ support(q) iff for all m, m[p][q] = m[q].

Lemma 7 (Conjunctive decomposition) If p and p′ have disjoint support, then

m[p ∧ p′] = m[p][p′] = m[p′][p].

Proof: Expanding the definitions yields

m[p ∧ p′] = {m′ ∈ [[p]] ∩ [[p′]] | m ≡ m′ mod p ∧ p′}, and
m[p][p′] = {m′′ | m′ ∈ [[p]] ∧ m′′ ∈ [[p′]] ∧ m ≡ m′ mod p ∧ m′ ≡ m′′ mod p′}.

Because p and p′ have disjoint support, the conditions in the second expression entail m′′ ∈ [[p]] and m ≡ m′′ mod p ∧ p′, making the two expressions equivalent. A symmetric argument yields equality with m[p′][p]. □

One cannot drop the hypothesis of disjoint support since the equalities fail when p = ¬p′ or when p = l ∨ l′ and p′ = l ∨ l′′.

Lemma 8 (Disjunctive decomposition) If p and p′ have disjoint support, then

m[p ∨ p′] = m[p ∧ p′] ∪ m[p ∧ ¬p′] ∪ m[¬p ∧ p′].

Proof: According to the definition,

m[p ∨ p′] = {m′ ∈ [[p]] ∪ [[p′]] | m ≡ m′ mod p ∨ p′}.

By the assumption of disjoint support and Lemma 5, model equivalence modulo p ∨ p′ is identical to equivalence modulo p ∧ p′, as well as equivalence modulo p ∧ ¬p′ and ¬p ∧ p′. Noting that

[[p]] ∪ [[p′]] = ([[p]] ∩ [[p′]]) ∪ ([[p]] ∩ [[¬p′]]) ∪ ([[¬p]] ∩ [[p′]]),

we can decompose the expression for m[p∨p′] into three conjunctive parts as required. □

One cannot drop the hypothesis of disjoint support since the equality fails when p = ¬p′.

Lemma 9 (Unique modification) If p and c have disjoint support and m ⊧ c, then m[p ∧ c] = m[p].

Proof: By Lemma 7, we have m[p ∧ c] = m[p][c]. Since m′[c] consists of a singleton for every m′ ∈ M, and since c ⊆ m for every m ∈ [[c]], we have m′ ∈ m[p] iff m′[c] = {m′}. □

Using these results, we can derive a canonical expression for any model modifications over a sentence expressed as a disjunction of conjunctions with disjoint support.

Theorem 10 (Amalgamation) Suppose p and q have support disjoint from r. If p∧r ≥ q ∧ r and p ∧ ¬r ≥ q ∧ ¬r, then p ≥ q.

Proof: By Lemma 7 and disjoint support, the hypothesized relative desires imply, for all m, that m[r][p ∧ ¬q] ∼ ≻ m[r][¬p ∧ q] and m[¬r][p ∧ ¬q] ∼ ≻ m[¬r][¬p ∧ q]. Then given m′, choose m such that m′ ∈ m[r] (if m′ ∈ [[r]]) or m′ ∈ m[¬r] (if m′ ∈ [[¬r]]). In either case, m′[p ∧ ¬q] ∼ ≻ m′[¬p ∧ q], and so p ≥ q. □

Theorem 11 (Refinement) If p, q, and c have disjoint support, then p ∧ c ≥ q ∧ c whenever p ≥ q.

Proof: The relation p ∧ c ≥ q ∧ c holds if m[p ∧ ¬q ∧ c] ∼ ≻ m[¬p ∧ q ∧ c] for each m. By Lemma 7 and disjoint support, this condition reduces to m[c][p ∧ ¬q] ∼ ≻ m[c][¬p ∧ q]. Because c is a conjunction of literals, Lemma 9 indicates the modification m[c] is unique for any m; let that model be m′. The hypothesis p ≥ q entails that for all m′, m′[p∧¬q] ∼ ≻ m′[¬p ∧ q], and hence the conclusion is established. □

Theorem 12 (Conditional transitivity) Assuming that c, c′, and p have disjoint support, if c ≥ p and p ≥ c′, then c ∧ p ≥ c′ ∧ p.

Proof: By Theorem 11, c ≥ p entails c ∧ c′ ≥ p ∧ c′, and p ≥ c′ entails p ∧ c ≥ c′ ∧ c. Thus for all m, m[c ∧ c′ ∧ ¬p] ∼ ≻ m[¬c ∧ c′ ∧ p] and m[c ∧ ¬c′ ∧ p] ∼ ≻ m[c ∧ c′ ∧ ¬p], so by transitivity of ∼ ≻, we have m[c ∧ ¬c′ ∧ p] ∼ ≻ m[¬c ∧ c′ ∧ p], exactly the condition needed for c ∧ p ≥ c′ ∧ p. □

Theorem 13 (Literal transitivity) Assuming that l, l′, and p have disjoint support, if l ≥ p and p ≥ l′, then l ≥ l′.

Proof: Assume that l ≥ p and p ≥ l′. By Theorem 12, l ∧ p ≥ l′ ∧ p. By applying the same theorem to the contraposition of the hypothesized desires, we obtain ¬l′ ∧ ¬p ≥ ¬l ∧ ¬p. By Theorem 3, this yields l ∧ ¬p ≥ l′ ∧ ¬p. Amalgamating these two cases by Theorem 10 results in l ≥ l′. □

Note that transitivity does not hold in general. For example, by Theorem 4, we have p ≥ true and true ≥ q for any p and q. But if A = {p, q} and {¬p, q} ≻ {p, ¬q}, then p ≥ q is false. (Assuming p ≥ (p ∨ r) ∧ q and (p ∨ r) ∧ q ≥ r provides a less trivial example.)

We obtain transitivity in Theorems 12 and 13 by restricting the form and interrelations of the sentences involved. The proofs of these results exploit such restrictions to ensure the uniqueness of modifications to a given model. We impose similar restrictions in application of the inference rules sanctioned by Theorem 11 and other results below.

In [8] we present an alternative formalization which requires that modifications of models minimize the changes made in the initial model. In the simplest case, this means using a model rather than its modifications when the model already makes the sentence true. In more complex cases, we want to pick out worlds in the modification that change as small a set of literals as possible (small in the set inclusion sense). More generally, we employ comparative similarity orders like those used in theories of counterfactuals and belief revision. Elsewhere, we relate the notion of relative desire to formalizations of conditional and deontic logics.

4 Propositional desires

In our semantics for goals viewed as desires [7], we represent states as vectors of attributes. We designate particular conditions as binary attributes, and define goalhood as preference for those conditions, holding all other attributes constant. We may reformulate that semantics in the logic of relative desire to obtain meanings for individual propositional desires, which we represent as sentences desired over their negations.

Definition 4 (Propositional desire) We say that p is a desire, and write desire(p), just in case p ≥ ¬p. We say that p is a strict desire, and write DESIRE(p), just in case p > ¬p.

Thus this definition picks out desires by comparing all of the possible ways of making sentences true and false while holding all else equal.

Corollary 14 (Logical invariance) If ⊧ p ↔ q, then desire(p) iff desire(q).

Corollary 15 (Negation of desires) If desire(p), then not DESIRE(¬p).

Corollary 16 (Trivial desires) The extremal sentences p ∨ ¬p and p ∧ ¬p are desires but not strict desires.

It remains to be seen whether any reasonable semantics can be found which does not make desires of true and false.

Theorem 17 (Sets of desires) Suppose p̂ = {p_{0}, …, p_{n}} and desire(p_{i}) (or equivalently, p_{i} ≥ ¬p_{i}) for 0 ≤ i ≤ n, where p_{i} and p_{j} have disjoint support for i ≠ j. Then

1. Any model m is weakly preferred to any m′ obtained by modifying m to falsify some desires (i.e., if p̂′ ⊆ p̂ and m′ ∈ m[¬ ⋁ p̂′], then m ∼ ≻ m′), and

2. For any pair of models m and m′ not related by such a modification (i.e., if p̂′ ⊆ p̂, then m′ ∉ m[¬ ⋁ p̂′]), there is some preference order ∼ ≻ compatible with the desires such that m ≻ m′.

Proof: 1. We proceed by induction on the size of p̂′. In the base case, |p̂′| = 0, so m′ = m, and hence m ∼ ≻ m′ by the reflexive property of weak preference. For the inductive step, suppose the result holds for |p̂′| ≤ k ≤ n. Choose a set p̂′ of size k, and an element p^{∗} from p̂\ p̂′. Let p̂′′ = p̂′ ∪ {p^{∗}}, and note that m[¬ ⋁ p̂′′] = m[(¬ ⋁ p̂′) ∧ ¬p^{∗}], which, by disjoint support and Lemma 7, is equivalent to m[¬ ⋁ p̂′][¬p^{∗}]. Therefore, for any m′′ ∈ m[¬ ⋁ p̂′′], there is some m′ ∈ m[¬ ⋁ p̂′] such that m′′ ∈ m′[¬p^{∗}]. Because m′ ∈ m′[p^{∗}] (since p^{∗} is satisfied in m and not falsified by p̂′), m′′ ∈ m′[¬p^{∗}], and m′ ≡ m′′ mod p^{∗}, desire(p^{∗}) directly entails m′ ∼ ≻ m′′. By the inductive step we have m ∼ ≻ m′, and so by transitivity m ∼ ≻ m′′.

2. We show that the first part of the theorem exhausts the requirements on ∼ ≻. The conditions desire(p_{i}) require that m′ ∼ ≻ m′′ whenever m′ ∈ m[p_{i}], m′′ ∈ m[¬p_{i}], and m′ ≡ m′′ mod p_{i}. But in this case, m′′ ∈ m′[¬p_{i}], and so this requirement is covered by the modification relation. To account for the reflexive property of weak preference, note that m ∈ m[¬ ⋁ ∅], and hence this is also covered by the condition. Finally, we consider transitivity. If m′′ ∈ m′[¬ ⋁ p̂′′] and m′ ∈ m[¬ ⋁ p̂′], then m′′ ∈ m[¬ ⋁(p̂′ ∪ p̂′′)]. Thus, no new preferences are drawn from transitivity, and the consequences are exhausted. Therefore we are free to order arbitrarily any pair of models m, m′ such that m′ ∉ m[¬ ⋁ p̂′]. □

Comparing this result with Theorem 1 highlights the difference between relative desire and absolute preference among model sets. Whereas absolute preference collapses partially satisfied models into a single indifference class, relative desire allows for finer distinctions. The weak constraints placed by desires on preference orders mean that desires do not, by themselves, prescribe a unique choice of action in all circumstances. If one seeks to ensure unique rational choices, one must augment the desires with more detailed specifications of relative desires among propositions.

Theorem 18 (Entailment of desires) If desire(l) and l′ ≥ l, then desire(l′).

Proof: If l = l′ or l = ¬l′, the result holds trivially. Otherwise, l and l′ have disjoint support. By Lemma 7, m[l ∧ l′] = m[l′][l], and m[¬l ∧ l′] = m[l′][¬l]. Since m[l′] is unique, from desire(l) it follows that m[l′][l] ∼ ≻ m[l′][¬l]. From l′ ≥ l (and Lemma 7), we have m[l′][¬l] ∼ ≻ m[¬l′][l]. A transitive combination of these preferences yields m[l′][l] ∼ ≻ m[¬l′][l], and rearranging, m[l][l′] ∼ ≻ m[l][¬l′]. A symmetric argument, exploiting the uniqueness of m[¬l′], yields m[¬l][l′] ∼ ≻ m[¬l][¬l′]. Since for every m′ there is some m such that m′ ∈ m[l] or m′ ∈ m[¬l], the two cases entail desire(l′). □

One may use the logic of relative desire to investigate principles for designing and analyzing planning systems. For example, many planners produce new goals by introducing and eliminating conjunctions and disjunctions of existing goals. Given the logic of relative desire, we may ask whether such operations are sound with respect to our semantics, when goals are interpreted as desires. In fact, the logic reveals that these operations are not always valid. For example, if A = {p, q} and {p, q} ≻ {¬p, ¬q} ≻ {p, ¬q} ≻ {¬p, q}, then desire(p ∧ q) but neither desire(p) nor desire(q) holds. If the planner uses unsound operations on goals, then either it risks making choices during plan execution that conflict with the underlying preferences, or its operations introduce new assumptions that implicitly change the underlying preference order.

Theorem 19 (Combination) If c, l, and d have disjoint support, c ≥ d, l ≥ d, and desire(c), then c ∧ l ≥ d.

Proof: By definition, c∧l ≥ d holds iff m[c∧l∧¬d] ∼ ≻ m[¬(c∧l)∧d] for all m. According to Lemma 8, the latter expression can be decomposed into the union of m[¬c ∧ l ∧ d], m[c ∧ ¬l ∧ d], and m[¬c ∧ ¬l ∧ d]. We establish the preference of m[c ∧ l ∧ ¬d] over each of these. First,

m[c ∧ l ∧ ¬d] = m[l][c ∧ ¬d] ∼ ≻ m[l][¬c ∧ d] = m[¬c ∧ l ∧ d],

by c ≥ d, disjoint support, Lemma 7, and the uniqueness of m[l]. Similarly,

m[c ∧ l ∧ ¬d] = m[c][l ∧ ¬d] ∼ ≻ m[c][¬l ∧ d] = m[c ∧ ¬l ∧ d],

by l ≥ d, disjoint support, Lemma 7, and the uniqueness of m[c]. Chaining this result with

m[c ∧ ¬l ∧ d] = m[¬l ∧ d][c] ∼ ≻ m[¬l ∧ d][¬c] = m[¬c ∧ ¬l ∧ d],

which holds by virtue of desire(c), disjoint support, Lemma 7, and the uniqueness of m[¬l ∧ d], yields m[c ∧ l ∧ ¬d] ∼ ≻ m[¬c ∧ ¬l ∧ d], the final condition we require. □

Theorem 20 (Conjunction of desires) If c and c′ have disjoint support, desire(c), and desire(c′), then desire(c ∧ c′).

Proof: We need to show that m[c∧c′] is preferred to any model in m[c∧¬c′], m[¬c∧c′], or m[¬c ∧ ¬c′]. First,

m[c ∧ c′] = m[c][c′] ∼ ≻ m[c][¬c′] = m[c ∧ ¬c′],

by desire(c′), disjoint support, Lemma 7, and the uniqueness of m[c]. A symmetric argument with c and c′ switched yields m[c ∧ c′] ∼ ≻ m[¬c ∧ c′]. Finally, let m′ ∈ m[c ∧ c′] and m′′ ∈ m[¬c∧¬c′]. Note that m ≡ m′ mod c∧c′, and thus by Lemma 5, m[¬c∧¬c′] = m′[¬c ∧ ¬c′]. Therefore, m′′ ∈ m′[¬c ∧ ¬c′], and thus by the first part of Theorem 17, m′ ∼ ≻ m′′. □

Theorem 21 (Disjunction of desires) If p and p′ have disjoint support, desire(p), and desire(p′), then desire(p ∨ p′).

Proof: The disjunctive desire holds iff m[p ∨ p′] ∼ ≻ m[¬p ∧ ¬p′] holds for all m. Let m′ ∈ m[p∨p′] and m′′ ∈ m[¬p∧¬p′]. Note that m ≡ m′ mod p∨p′, and thus by Lemma 5 and disjoint support, m[¬p ∧ ¬p′] = m′[¬p ∧ ¬p′]. Therefore, m′′ ∈ m′[¬p ∧ ¬p′], and so m′ ∼ ≻ m′′ by the first part of Theorem 17. □

Theorems 20 and 21 provide conditions under which conjoining and disjoining desires produces more complex desires. However, their converses do not generally hold. Thus subgoaling on conjunctions and disjunctions in AND/OR search need not always produce bona fide desires. Viewed semantically, the subgoals may have undesirable properties (“side-effects”) in addition to their relation to the compound desire. In general, preferences over complex sentences tell us little about preferences over their constituent parts.

Although one cannot usually justify common goal manipulations due to the many preference orders compatible with desires alone, these operations can sometimes be validated conditional on additional restrictions, such as assumptions of preferential independence given combinations of conditions.

5 Restricted relative desire

We have defined relative desire in terms of preferences over the set of all models M, but in many cases the knowledge available to the planner or used in the planner’s construction rules out the occurrence of some of these interpretations. That is, some logically possible models may be epistemically or constitutionally impossible. In such cases, we should not demand that the planner express preferences over the irrelevant logically possible models, but only require a preference order over the models that represent epistemically or constitutionally possible situations or outcomes.

To make the logic of relative desire more practical in this way, we restrict all the previous definitions to a set M ⊆ M representing the epistemically or constitutionally possible models. We define m[p]^{M}, the modifications of m by p restricted to M, by

m[p]^{M} =^{def} m[p] ∩ M,

and define restricted relative desire among sentences as follows.

Definition 5 (Restricted relative desire) We say that p is desired over q when restricted to M, written p ≥^{M} q and read briefly as “p over q in M,” iff for each m ∈ M, m′ ∈ m[p ∧ ¬q]^{M}, and m′′ ∈ m[¬p ∧ q]^{M} we have m′ ∼ ≻ m′′. We say that p is strictly desired over q when restricted to M, written p >^{M} q, iff p ≥^{M} q but not q ≥^{M} p.

This definition characterizes restricted relative desire in exactly the same way as relative desire, except that one considers only models and modifications in M rather than M. In other words, p ≥ q just means p ≥^{M} q.

We further extend the preceding definition by defining relative desire restricted by sentences and theories. We write p ≥^{r} q, read “p over q given r”, to mean p ≥^{[[r]]} q, and p ≥^{T} q to mean p ≥^{[[T]]} q, where [[T]] = ⋂_{r∈T} [[r]]. Thus p ≥ q iff p ≥true q.

Theorem 22 (Strengthening) If ⊧ r′ → r, then p ≥^{r} q implies p ≥^{r′} q.

Proof: Suppose ⊧ r′ → r and p ≥^{r} q. Let m ∈ [[r′]], m′ ∈ m[p ∧ ¬q] ∩ [[r′]], and m′′ ∈ m[¬p∧q]∩[[r′]]. Since ⊧ r′ → r, [[r′]] ⊆ [[r]], so m ∈ [[r]]. Since m[p∧¬q] ∼ ≻ m[¬p∧q] by hypothesis, we have m′ ∼ ≻ m′′. □

Corollary 23 (Arbitrary restrictions) p ≥ q iff p ≥^{r} q for every r.

Theorem 24 (Incompatible restrictions) If ⊧ p → ¬r or ⊧ q → ¬r, then p ≥^{r} q

Proof: If ⊧ p → ¬r, then m[p∧¬q]∩[[r]] = ∅, while if ⊧ q → ¬r, then m[¬p∧q]∩[[r]] = ∅. In either case, the stated relation holds trivially. □

In particular, p ≥false q for all p, q.

Lemma 25 (Restricted modifications) If p and r have disjoint support, it follows that m[p]^{r} ⊆ m[p ∧ r].

Proof: Assuming disjoint support, support(p) ⊆ support(p ∧ r). If m′ ∈ m[p]^{r}, then m′ ⊧ p ∧ r and m ≡ m′ mod p ∧ r, so m′ ∈ m[p ∧ r]. □

Theorem 26 (Explicit restriction) If p ∧ r ≥ q ∧ r and r has support disjoint from p and from q, then p ≥^{r} q.

Proof: Assume p ∧ r ≥ q ∧ r and disjoint support. By simplifying the definition, we obtain m[p ∧ ¬q ∧ r] ∼ ≻ m[¬p ∧ q ∧ r] for each m ∈ M. To show that p ≥^{r} q, assume that m ∈ [[r]], m′ ∈ m[p∧¬q]^{r}, and m′′ ∈ m[¬p∧q]^{r}. By Lemma 25, m[p∧¬q]^{r} ⊆ m[p∧¬q ∧r] and m[¬p ∧ q]^{r} ⊆ m[¬p ∧ q ∧ r], so m′ ∼ ≻ m′′, as desired. □

The converse does not hold. To see this, suppose that p, q, r_{1}, r_{2} ∈ A and r = r_{1} ∨ r_{2}. The assumption that p ≥^{r} q amounts to requiring that {p, ¬q, r_{1}, r_{2}} ∼ ≻ {¬p, q, r_{1}, r_{2}}, {p, ¬q, r_{1}, ¬r_{2}} ∼ ≻ {¬p, q, r_{1}, ¬r_{2}}, and {p, ¬q, ¬r_{1}, ¬r_{2}} ∼ ≻ {¬p, q, ¬r_{1}, ¬r_{2}}. If we have {¬p, q, r_{1}, ¬r_{2}} ≻ {p, ¬q, r_{1}, r_{2}} in addition, then p ∧ r ≥ q ∧ r does not hold.

Restricted relative desire captures part of the notion of framing defined in [7]. Rather than beginning by supposing a set of atomic sentences and their models, our treatment there follows decision theory by supposing a set Ω of possible outcomes and then representing these outcomes as vectors of attributes by means of a one-to-one framing function ϕ : Ω → ∏_{i=1}^{n} A_{i}. The image ϕ(Ω) of outcomes under the framing constitutes the set of possible attribute vectors. The logical formalization of relative desire presented here specializes the original semantics by representing outcomes by vectors of binary attributes rather than by vectors of arbitrary attributes, that is, choosing ϕ : Ω → M. Restricting relative desire to a set of models M then corresponds to choosing the framing so that ϕ(Ω) = M.

Framings and their corresponding restrictions on possible outcomes play important roles in reasoning because they can, in some cases, determine which sentences represent desires. In other words, the set of sentences representing desires can change as one changes knowledge or constitution to make different outcomes possible. For example, suppose that A consists of the two independent sentences: p, “I wear a raincoat”, and q, “I stand in the rain.” We assume that ¬q is preferred to q, all else equal, and that p is preferred to ¬p given q, but the preference is reversed given ¬q, again all else equal. We then have the intuitive result that ¬q represents a desire, but neither p nor ¬p does. Yet p represents a desire if we assume q holds; that is, p ≥^{q} ¬p. This relativity of desire occurs quite easily, as shown by the following result.

Theorem 27 (Relativity of desire) If p ≥ q does not hold, then q >^{r} p for some r.

Proof: Suppose that p ≥ q does not hold. By Corollary 23, choose r so that p ≥^{r} q does not hold. We may then find m ∈ [[r]], m′ ∈ m[p ∧ ¬q], and m′′ ∈ m[¬p ∧ q] so that m′′ ≻ m′. Let r′ = (⋀ m′) ∨ (⋀ m′′), and verify that q >^{r′} p, as desired. □

In particular, if p is not a desire, then ¬p is sometimes a strict desire, and if neither p nor ¬p are desires, then one can find different restrictions making each a strict desire.

6 Conclusion

We have presented a logic of relative desire in which desires have a nontrivial semantics in terms of preferences over models, and in which one may construct preferences corresponding to specific sets of desires. The definition of desires formalizes the intuition that goals are propositions that are preferred to their opposites, other things being equal. The logic extends our previous work [7] by considering relative desire between arbitrary conditions expressed in a propositional language, and we provided a collection of inference rules that support reasoning about relative desire. We showed that while this logic displays some intuitive properties, it also reveals that desirability sometimes depends on knowledge or the possible states of the world, and that some common and seemingly natural goal operations are not always valid. Designers of planning architectures wishing to justify the behavior of their systems must therefore either provide further constraints on the meaning of desires, find other means for expressing preference information, or justify unsound manipulations on heuristic grounds. This highlights the importance of developing more refined languages for specifying the objectives of planning agents.

Ordinary desires can depend on probability judgments as well as preferences. Unlike other approaches to reasoning about desirability (e.g., Jeffrey’s [2]), our inference rules do not depend on probability distributions. We could strengthen these rules to take advantage of probabilistic information when available, but some situations call for an ability to reason about desires separate from beliefs.

Further work will focus on strengthening and expanding the set of inference rules. The numerous restrictions on the form and and interrelations among sentences limit the applicability of the initial inference rules presented here. We expect that some of these restrictions may be alleviated by applying less ambiguous model modification rules, perhaps based on minimality criteria from the theory of conditionals and belief revision.

The logic presented here constitutes part of a comprehensive decision-theoretic account of planning (see also [6]), and a more thorough treatment of the issue of goals and utilities is in preparation [8]. The formal treatment of desire also plays an important role in the framework of agent-oriented programming (AOP), proposed in [5]. AOP—a specialization of object-oriented programming—views agents as modifying their mental states as a result of informing one another, requesting information, and performing other kinds of communicative acts. In current AOP setups, the mental state of an agent consists of “motivation-free” components: beliefs, commitments, choices, and capabilities. The logic of relative desire positions us to enrich the mental state of agents, thus expanding the AOP framework. In general, we expect that much might be learned by developing planning architectures which combine desires and goals with other preferences in a manner faithful to the logic of relative desire.

Acknowledgement: Jon Doyle is supported by the USAF Rome Laboratory and DARPA under contract F30602-91-C-0018, and by National Institutes of Health Grant No. R01 LM04493 from the National Library of Medicine.

References

[1] J. Doyle. A model for deliberation, action, and introspection. AI-TR 581, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, Cambridge, MA, 1980.

[2] R. C. Jeffrey. The Logic of Decision. University of Chicago Press, Chicago, second edition, 1983.

[3] R. L. Keeney and H. Raiffa. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. John Wiley and Sons, New York, 1976.

[4] J. Marks. Introduction: On the need for theory of desire. In J. Marks, editor, The Ways of Desire. Precedent Publishing, Chicago, 1986.

[5] Y. Shoham. Agent-oriented programming. Technical Report STAN-CS-90-1335, Stanford University Computer Science Department, 1990.

[6] M. P. Wellman. Formulation of Tradeoffs in Planning Under Uncertainty. Pitman and Morgan Kaufmann, 1990.

[7] M. P. Wellman and J. Doyle. Preferential semantics for goals. In Proceedings of the National Conference on Artificial Intelligence, 1991.

[8] M. P. Wellman, J. Doyle, and T. Dean. Goals, preferences, and utilities: A reconciliation. in preparation, 1991.