A Representationalist Theory of Intention

1 Introduction

Formalizations of cognitive state that include inten­ tions and beliefs have appeared in the recent literature [Cohen and Levesque, 1990a; Rao and Georgeff, 1991; Shoham, 1990; Konolige and Pollack, 1989]. With the exception of the current authors, these have all employed normal modal logics (NMLs), that is, logics in which the semantics of the modal operators is defined by accessi­ bility relations over possible worlds. This is not surpris­ ing, since NMLs have proven to be a powerful tool for modeling the cognitive attitudes of belief and knowledge. However, we argue that intention and belief are very dif­ ferent beasts, and that NMLs are ill-suited to a formal theory of intention.

We therefore present an alternative model of inten­ tion, one that is representationalist, in the sense that its semantic objects provide a more direct representation of cognitive state of the intending agent . We argue that this approach results in a much simpler model of inten­ tion than does the use of an NML, and that, moreover, it allows us to capture interesting properties of intention that have not been addressed in previous work. Further, Martha E. Pollackt Dept. of Computer Science Univ. of Pittsburgh Pittsburgh, PA 15260

·supported by the Office of Naval Research under Con­ tract No. N00014-89-C-0095.

I Supported in part by a National Science Foundation Young Investigator's Award (IRI-9258392), by the Air Force Office of Scientific Research (Contract F49620-92-J-0422), and by DARPA (Contract F30602-93-C-0038) .

the relation between belief and intention is mediated by the fundamental structure of the semantics, and is inde­ pendent of any particular choice for temporal operators or theory of action. This gives us a very direct, simple, and semantically motivated theory, and one that can be conjoined with whatever temporal theory is appropriate for a given task.

In the next section (Section 2), we make the case for a representationalist theory of intention. Section 3 consti­ tutes the technical heart of our paper: there we develop our formal model of intention. Finally, in Section 4, we draw some conclusions and point the way toward further development of our logic of intention.

2 The case for representationalism

As we noted above, NMLs have been widely and suc­ cessfully used in the formalization of belief. It is largely as a result of this success that researchers have adopted them in building models of intention. However, we ar­ gue in this section that these logics are inappropriate to models of intention:

• The semantic rule for normal modal operators is the wrong interpretation for intention. This rule leads to the confusion of an intention to do ¢ with an in­ tention to do any lo~ical consequence of ¢,.called the side-effect problem lBratman, 1987]. A simple and intuitively justifiable change in the semantic rule makes intention side-effect free (and nonnormal) .
• Normal modal logics do not provide a means of re­ lating intentions to one another . Relations among intentions are necessary to describe the means-end connection between intentions.

NMLs are closed under logical consequence: given a normal modal operator L, if L¢ is true, and ¢ F '1/J, it follows that Lt/J is true. When L represents belief, consequential closure can be taken to be an idealization: although it is obviously unrealistic in general to assume that an agent believes all the consequences of his beliefs, it is reasonable to assume this property of an ideal agent , and this idealization is acceptable in many instances.

However, consequential closure cannot be assumed for intention, even as an idealization. It is clear that an agent who intends to perform an action usually does not intend all the consequences of that action, or even all the consequences he anticipates. Some of the consequences are goals of the agent, while others are "side effects" that the agent is not committed to. 1

Because NMLs are subject to consequential closure, and intention is not, several strategies are used to make the logics side-effect free . They all involve relativizing the side-effects of intentions to believed consequences. The thesis of realism is that all of an agent's intended worlds are also belief worlds [Cohen and Levesque, 1990a], that is, a rational agent will not intend worlds that he believes are not possible. Given the realism the­ sis, whenever the agent intends a and believes a :::> b, he will also intend b. Cohen and Levesque [Cohen and Levesque, 1990b] adopt the realism thesis, and rely on claims about way an agent may change his beliefs about the connection between an intended proposition and its consequences to make their theory side-effect free. In their case, an agent who always believes that a :::> b is al­ ways true will incur the side-effect problem when intend­ ing a. Also, any analytic implication (i.e., when a :::> b must be true in all possible futures) will cause problems. Two special cases are abstractions (e.g., making a din­ ner is an abstraction of making a spaghetti dinner) and conjunctions (intending a 1\ b implies intending a and intending b separately).

Rao and Georgeff [Rao and Georgeff, 1991] point out that by relaxing realism, intentions can be made side­ effect free . Weak realism is the thesis that at least one intended world is a belief world. There can thus be in­ tention worlds that are not belief worlds. Now, even though the agent believes a :::> b, b is not an intention, because there is an intended world in which a is true but not b. Weak realism seems inherently less desirable than realism (how is it possible for an agent to intend worlds he does not believe possible?), and it is still not fully side-effect free, since it is closed under conjunctions and abstractions.

These problems do not mean we have to abandon pos­ sible worlds. In fact, with the right semantics, possible worlds are an intuitively satisfying way of representing future possibility and intention for an agent. We note that intentions divide the possible futures into those that the agent wants or prefers, and those he does not . Con­ sider the diagram of Figure 1. The rectangle represents the set of possible worlds W . The scenario for a propo­ sition a is the set of worlds in W that make a true: the shaded area in the diagram. An agent that has a as an intention will be content if the actual world is any one of those in the shaded area, and will be unhappy if it is any unshaded one. The division between wanted and unwanted worlds is the important concept behind scenarios. For example, consider another proposition b that is implied by a (for concreteness, take a = "I get my tooth filled," and b = "I feel pain.") If we just look at interpretations within the shaded area, a and b both hold, and so cannot be distinguished. But the comple­ ment of these two propositions is different . A world in the area -,a, b, in which the agent feels pain but does not have his tooth pulled, is an acceptable world for the intention b, but not for a. So the interpretation rule for intention must take into account the complement of the intended worlds. As we will see in Section 3, this makes intention a nonnormal modal operator. It also makes it side-effect, abstraction, and conjunction free, whether we choose realism or weak realism.

1 For example, a.n a.gent ma.y intend to go to the dentist to get his tooth filled, believing tha.t he will feel pa.in a.s a. consequence, without being committed to feeling the pa.in. If he discovers tha.t the dental work is painless, he will not seek to experience the pa.in nonetheless. See Bra.tma.n [Bra.tma.n, 1987] a.nd Cohen a.nd Levesque [Cohen a.nd Levesque, 1990b] for further discussion.

The representationalist part of the model comes in representing the mental state of the agent using scenar­ ios. Cognitive structures, containing elements represent­ ing intentions and the relationship among intentions, are used for this purpose.

3 Cognitive structures

Our model of intention will have two components: pos­ sible worlds that represent possible future courses of events, and cognitive structures, a representation of the mental state components of an agent. We introduce com­ plications of the model in successive sections . To begin, we define the simplest model, a static representation of primary or "top-level" intentions. Primary intentions do not depend on any other intentions that the agent cur­ rently has . 2

3.1 Possible Futures

The concept of intention is intimately connected with choosing among course of future action. In the model , courses of action are represented by possible worlds. Each possible world is a complete history, specifying states of the world at all instants of time. We assume there is a distinguished moment now in all worlds that is the evaluation point for statements. 3

2 This is a. bit of a.n overstatement, since a.n agent 's in­ tentions cha.nge over time, a.nd a.n intention that begins life a.s primary ma.y la.ter also be used in support of some other intention. In such ca.ses we sa.y tha.t the intention ha.s been overloaded. Overloading is a. cognitively efficient strategy for a.n a.gent to employ [Pollack, 1991]. For the moment, how­ ever, we will not worry a.bout primary intentions that later are overloaded.

The set of possible worlds is W. For each world w E W, there is an evaluation function that determines the value of sentences in a language C, which refer to states of the world or actions that take place between states of this world. For any sentence ¢of C, w(¢) is the truth­ value of¢.

To talk about contingent and necessary facts C is ex­ tended to Co, which includes the modal operators 0 and <>. The possibility operator <> expresses the existence of a world with a given property. <>¢ says that there is a world (among W) for which ¢ is true. Its semantics is:

Definition 3.1

<> is used to specify the background of physically possi­ ble worlds under which reasoning about intention takes place, and will be important in describing the structure of a given domain. The necessity operator 0¢ is defined as....,<>....,¢.

3.2 Belief and primary intentions

We begin by defining concept of scenario.

Definition 3.2 Let W be a set of possible worlds, and ¢> any sentence of C. A scenario for ¢ is the set

A scenario for ¢> identifies ¢ with the subset of W that make¢ true.

A cognitive structure consists of the background set of worlds, and the beliefs and intentions of an agent. 4

Definition 3.3 A cognitive structure is a tuple (W, E, I) consisting of a set of possible worlds W, a sub­ set of W {E, the beliefs of the agent} and a set of sce­ narios over W (I, the intentions of the agent).

We extend Co to C1 by adding the modal operators B for belief and I for intentions. The beliefs of an agent are taken to be the sentences true in all worlds of E . 5 For simplicity, we often write E as a set of sentences of Co, so that Mr. is the corresponding possible worlds set .

Definition 3.4

3 This definition of possible worlds is the one usually used in the philosophical literature, but differs from that of Moore in [Moore, 1980], where possible worlds are identified with states at a particular time.

4 ln this paper, we deal only with the single agent case, and thus we neither explicitly indicate the name of the (un­ ambiguous) agent associated with any cognitive structure, nor include an agent argument in our intention or belief predicates.

5 This enforces the condition of logical omniscience [Levesque, 1984] on the agent's beliefs, which is not a realis­ tic assumption. We could chose a different form for beliefs, say a set of sentences of Cr that is not closed with respect to consequence; but it would obscure the subsequent analysis.

The beliefs of an agent are always possible, that is, they are a subset of the possible worlds. This also means that an agent cannot be wrong about necessary truths. A more complicated theory would distinguish an agent's beliefs about what is possible from what is actually pos­ sible. The key concept is that intentions are represented with respect to a background of beliefs about possible courses of events (represented by <>), as well as beliefs about contingent facts (represented by B). Stated in C1, the following are theorems:

Of course, beliefs about contingent facts can still be false, since the real world does not have to be among the be­ lieved ones. The B operator represents ·all futures the agent believes might occur, including those in which he performs various actions or those in which he does noth­ ing. The beliefs form a background of all the possibilities among which the agent can choose by acting in particu­ lar ways.

The third component of a cognitive structure for an agent, an intention structure, is a set of scenarios Mq,. Intuitively, an agent's intention structure will include one scenario for each of his primary intentions. We write I as a set of sentences of Co, where each sentence ¢> stands for its scenario Mq,.

Definition 3.5

This definition bears an interesting relation to the se­ mantics of normal modal operators. Each primary inten­ tion (i.e., each element of I) acts like a separate modal operator. A normal modal operator I.p for the element M.p would be defined using:

just as for belief. The semantic rule for I is similar, but uses equality between the scenarios instead of subset, so that the worlds not in M.p must satisfy ....,¢. By identify­ ing intentions with scenarios, we explicitly encode in the semantics the distinction between preferred and rejected possible worlds. If we were to use the weaker form of the semantic rule for I(¢) (i.e., M.p ~ Mq,), then there could be some world w which satisfies ¢ but is not a world satisfying the agent's intention. This is contrary to our reading of intention as a preference criterion di­ viding possible worlds. 6

From this formal definition, it is easy to show that I(¢>) will hold just in case ¢ is equivalent to some proposition 1/J E I, given the background structure W.

Proposition 3.1 For any structure (W, E,I),

6 0ur semantics is also equivalent to the minimal model semantics of Chellas [Chellas, 1980]. In the minimal model semantics, the accessibility relation is from a world to a set of sets of worlds, i.e., a set of propositions. As Chellas shows, such logics are nonnormal, a.nd the simplest system, E, con­ tains only the inference rule ¢J = t/1 /I ¢J = I t/1 .

The I operator is true precisely of the individual top­ level intentions the agent has. It is not subject to closure under logical consequence or under the agent's beliefs. To see this, consider the cognitive structure (W, E, {a}), i.e., the agent has the single intention to perform a. As­ sume that a logically implies b, but not the converse, i.e.,

Then Ma ::/= Mb, because there is a world in which b is true but a is not. From the semantics of I, we have

This shows that I is not closed with respect to valid con­ sequence. To distinguish the intention of a from its nec­ essary consequence b, there must be at least one possible world in which b is true but a is not . As a particular in­ stance of this, our theory does not equate an intention to perform a conjunction with a conjunction of intentions. Assume that the set of possible worlds distinguishes a and b, i.e., W F O(aA-,b)AO(-,aAb) . Now consider two agents: the first has the single primary intention a A b, and the second has exactly the two primary intentions a and b. Then:

The reason for this is clear from the diagram of Figure 2. The scenario MaAb excludes all interpretations outside of the overlap area in the figure; hence it is not equivalent to Ma, for which a perfectly acceptable world could contain a and -,b; nor is it equivalent to Mb .

On the other hand, taking the two scenarios Ma and Mb singly, acceptable worlds are in the respective re­ gions a and b. Thus the most acceptable worlds are in the overlap region. However, if one of the goals becomes impossible, say a, then any world in b is acceptable, un­ like the case with the conjunctive scenario MaAb .

A similar story can be told for side effects and ab­ straction. The ability to distinguish between an inten­ tion and its side effects, abstractions, and conjunctions is basic to the semantics given in Definition 3.5, and does not require any further axioms or stipulations, nor any commitment to a particular temporal logic.

An alternative .to the reading of "intention" as sepa­ rate primary intentions is the reading as conjoined inten­ tion, i.e., "¢is intended if it is the intersection of worlds of some set of primary intentions." We use the operator r(¢) for this reading.

Definition 3.6

I· can be characterized by the following axioms.

Proposition 3.2 The following are theorems of C1 .

So r sanctions the conjoining of separate intentions , but not the splitting of an intention that is a conjunction. 7

3.3 Rationality constraints: intention and belief

So far we have not related the agent's intentions to his beliefs. Consider the diagram of Figure 3, for which the cognitive structure is (W, E, {a, b}) . The agent 's two in­ tentions are jointly possible, since the overlapping area contains at least one world in which they both hold. However, based on the contingent facts of the situation, the agent does not believe that they will actually occur, since his beliefs, given by the set E, fall outside the over­ lap area. A rational agent will not form intentions that he does not believe can be jointly executed. Further , in­ tentions should be nontrivial, in the sense that the agent intending <P should not believe that <P will occur without the intervening action of the agent . To enforce ratio­ nality, we define the following conditions on cognitive structures.

Definition 3. 7 A cognitive structure (W, E, I) is ad­ missible iff it is achievable:

and nontrivial:

This condition leads immediately to the following conse­ quences.

7 In terms of Chellas' minimal models, the semantics of I" is for models that are closed under intersection. This makes sense: r represents any intersection of intentions.

Proposition 3.3 These sentences are valid zn all ad­ missible structures.

A rational agent , characterized by achievable structures, does not believe that his joint intentions represent an impossible situation: this is the theorem of Joint Epis­ temic Consistency. This theorem can be stated using either reading of intention.

In addition, the nontriviality condition on models means that the agent does not believe that any one of his intentions will take place without his efforts (Epis­ temic Indeterminacy). Recall that the B operator repre­ sents all futures the agent believes might occur, including those in which he performs various actions or does noth­ ing. The beliefs form a background of all the possibilities among which the agent can choose by acting in particu­ lar ways . If in all these worlds a fact <P obtains, it does no good for an agent to form an intention to achieve </l, even if it is an action of the agent , because it will occur without any choice on the part of the agent . So, for ex­ ample, if the agent believes he will be forced to act at some future point, perhaps involuntarily (e.g., by sneez­ ing), it is not rational for the agent to form an intention to do that .

Note that in our logic, the realism thesis is expressed using beliefs about what is possible. This is because we distinguish beliefs about contingent facts ("Nixon was president" ) from the background possibilities an agent believes could occur , but haven't or won't . Realism fol­ lows directly from Joint Consistency and the simplifying assumption (1) that all worlds Ware possibilities for the agent .

In this logic, we are deliberately leaving the temporal aspects vague until they are necessary. At this level of abstraction, different kinds of goals can be treated on an equal basis. For example, goals of prevention , which are problematic for some temporal logic accounts of inten­ tion , are easily represented. For an agent to prevent a state p from occurring, he must believe both p and ·p to be possible at some future state. The agent 's intention is the scenario consisting of worlds in which p is always t rue.

3.4 Relative intentions

As we discussed earlier, one of the primary character­ istics of intentions is that they are structures: agents often form intentions relative to pre-existing intentions. That is , they "elaborate" their existing plans. There are various ways in which a plan can be elaborated. For in­ stance, a plan that includes an action that is not directly executable can be elaborated by specifying a particular way of carrying out that action ; a plan that includes a set of actions can be elaborated by imposing a temporal order on the members of the set; and a plan that includes an action involving objects whose identities are so far un­ derspecified can be elaborated by fixing the identities of one or more of the objects. As Bratman [Bratman, 1987, p.29] notes, "[p]lans concerning ends embed plans con­ cerning means and preliminary steps; and more general intentions ... embed more specific ones." The distinc­ tion between these two kinds of embedding recurs in the AI literature. For instance, Kautz [Kautz, 1990] iden­ tifies two relations: ( 1) decomposition, which relates a plan to another plan that constitutes a way of carrying it out (means and preliminary steps), and (2) abstrac­ tion, which relates a specific plan to a more general one that subsumes it. It is useful to have a term to refer to the inverse relation to abstraction: we shall speak of this as specialization.

Both kinds of elaboration are represented in the cog­ nitive structure by a graph among intentions. The graph represents the means-ends structure of agent intentions. For example, suppose the agent intends to do a by do­ ing b and c. Then the cognitive structure contains the graph fragment Mb, Me - Ma. As usual, in the cog­ nitive structure we let the propositions stand for their associated scenarios.

Definition 3.8 An elaborated cognitive structure con­ sists of a cognitive structure and an embedding graph - among intentions: (W, E, I,-). The graph is acyclic and rooted in the primary intentions.

Remarks. The reason we need both primary intentions and the graph structure is that, while every root of the graph must be a primary intention, primary intentions can also serve as subordinate intentions. Consider the masochistic agent with a tooth cavity: he both intends to feel pain, and intends to get his tooth filled. His cognitive structure would be:

Also note that a scenario of the graph may serve to elab­ orate more than one intention; Pollack [Pollack, 1991] calls this overloading.

The embedding graph - is the most strongly repre­ sentationalist feature of the model. It represents the structure of intentions in a direct way, by means of a relation among the relevant scenarios. A normal modal logic is incapable of this, because its accessibility rela­ tion goes from a single world (rather than a scenario) to a set of possible worlds.

In the language, LJ is extended to include a modal operator By( o: ; /31, · · · f3n ), where the f3i together are an elaboration of o: .

Definition 3.9

For rational agents, intention elaborations will have the same properties vis-a-vis belief as top-level inten­ tions. So, in admissible structures we insist on the con­ dition that any scenario of - is part of the achievable and nontrivial intentions.

Definition 3.10 A cognitive structure (W, E,I) is ad­ missible iff it is achievable:

and nontrivial:

This semantic constraint has the immediate consequence that all By-arguments are conjoined intentions, and share in all their properties.

Proposition 3.4

But there is an additional constraint on the elaboration of intentions, having to do with their means-end rela­ tion. An agent should believe that if the elaboration is achieved, the original intention will be also. Consider the diagram of Figure 4, in which the agent has the inten­ tion to achieve a by achieving b; for concreteness, take the example of calling the telephone operator by dialing 0. There can be possible worlds in which b does not lead to a : for example, in using the internal phone system of a company. The correct rationality condition for an agent is that he believe, in the particular situation at hand, that achieving b will achieve a. This is represented by the set E of belief worlds, in which b ::> a holds.

We call a model embedded if it satisfies this constraint on belief and intention structure.

Definition 3.11 A cognitive structure is embedded iff whenever bt · · · bn -+a, n7= 1 Mb, ~ Ma .

It can be easily verified that this condition leads to the following theorem.

Proposition 3.5 In all embedded cognitive structures (W, E,T,-+},

While the embedding graph semantics is simple, it leads to interesting interactions in the statics of inten­ tion and belief. For example, in plan-recognition it can be used to determine if a recognized plan is well-formed. It is also critical to the theory of the dynamics of inten­ tion and belief. We have a preliminary theory of this dynamics expressed as a default system.

4 Conclusion

We have concentrated on the static relation between in­ tention and belief, and shown how the relationship be­ tween these two can be represented simply by an ap­ propriate semantics. The static formalism is useful in task such as plan recognition, in which one agent must determine the mental state of another using partial in­ formation .

More complex applications demand a dynamic theory, which is really a theory of belief and intention revision. The formalism of cognitive structures can be extended readily to time-varying mental states, by adding a state index to the model. However, the theory of revision is likely to be complicated, even more so than current belief revision models [Gardenfors and Makinson, 1990], and will probably involve elements of default reasoning.