Ascribing Plans to Agents

1 Introduction

Int~lligent agents who are situated in multiagent do­ mams must reason about one anothers' actions and plans. Many AI models of plan recognition have viewed It as a ~rocess of belief and intention ascription [Allen, 1?83, Litman and Allen, 1987, Schmidt et al., 1978, S1dner, 1985] . Kautz has recently criticized this body of researc~ for its failure to provide a formal analysis of the ~efeas1ble reasoning inherent in plan recognition. In particular, he notes that in the existing work "[o]nly a space of possible inferences is outlined and little or noth­ ing is said about why one should infer ~ne conclusion over another, or what one should conclude if the situation is t~uly ambiguous" [Kautz, In Press] . Kautz himself pro­ ~Ides an eleg~nt formalization of plan recognition, stated m terms of circumscription. However, his account relies upon strong assumptions; that the agent performing the plan recogni~ion (the observer) has complete knowledge ?f the domam, and that the agent whose plan is being mferred (the actor) has a correct plan. Pollack, in re­ search on plan recognition in discourse understanding, has .sh?wn that these assumptions are too strong for any realiStic, useful model of plan recognition [Pollack 1986 Pollack, In press]. ' '

*This research was supported by the Office of Naval Re­ se.arch und~r Contract No. N00014-85-C-0251, by a contract With t~e Nippon Telegraph and Telephone Corporation, and by a gift from the System Development Foundation.

. It is not obvious how to remove the strong assump­ twns from Kautz's model. 1 Consequently, we have been d.eveloping an alternative formalization of plan recogni­ tion, one in which it is not necessary to assume that the actor's plan is correct from the perspective of the ob­ server, but in which it is possible to specify in a precise way why certain conclusions should be preferred over others. This paper consitutes a preliminary report on this approach.

. I.n our vie""_', plan recognition, like model-based recog­ mtwn tasks m perceptual domains, involves the inter­ action of two types of information: local cues derived from the data, and the coherence of local information in a ?;Iobal structure. In plan recognition, the data com­ pnse (1) the actions of the actor , which in the cases we will ~onsider, are restricted to being utt~rances; and (2) prevwusly held mutual beliefs. From this data, the ob­ server can initially"derive local cues about some of the actor's beliefs and intentions. During plan recognition the observer ascribes to the actor additional beliefs and !ntentions (or what we will call "plan fragments"). Typ­ Ically, the ascription is process is local, in the sense that at each point in the process, the observer uses a smail subset of already ascribed beliefs and plan fragments as the basis of further ascription. The ascription of beliefs and the ascription of plan fragments interact with one another. For example, if the observer 0 can ascribe to the actor A a belief that another agent B has some ob­ ject Obj that A wants, then the observer is justified in asc~ibing ~o A a p!an fragment that involves asking B for ObJ. But If there IS no need to ascribe this plan fragment to A, then 0 will typically not ascribe the belief either.

Both belief and intention ascription are defeasible. Moreover, there will often be conflicts among the possi­ ?le ascriptions. We maintain that much of the complex­ Ity and subtlety of the plan recognition process comes from ways in which these conflicts are adjudicated. We give some important general principles of conflict resolu­ tion, but do not assert that these form a complete cata­ ~og: only more experience with plan recognition systems m actual use will reveal deficiencies here.

. 1 Ka~tz suggests the introduction of an "error" plan that will be mferred whenever one of the assumptions is violated. But, in general, this is insufficient, since agents need to be able not only to reason that a plan is incorrect, but also to reason about what makes it so.

WhaL role does global coherence play in the plan recognition process? It is clear that local cues must give rise to a globally coherent plan in order for such a pla11 to be attributed, but the relative strength of lo­ cal vs . global information has yet to be determined. We conjecture, however, that plan recognition is essentially a "bottom-up" recognition process, with global coher­ ence used mostly as an evaluative measure , to eliminate ambiguous plan fragments that emerge from local cues. In this paper we concentrate on the formal definition of local ascriptions, along with their interactions. For this purpose we use the direct argumentation system ARGH [Konolige, 1989]. One of the more useful features of this system is that it permits explicit statements about the resolution of conflicts between candidate ascriptions.

2 Working Assumptions

To ground our discussion, we will draw our examples in this paper from the "Robot Delivery Domain" (hence­ forth, RDD), in which a Flakey, a mobile robot, is pre­ sumed to roam the halls of an office, delivering objects to people on reques t. To behave intelligently, Flakey must attempt to recognize the plans of the people who make requests of him: in our examples, he is the observer, and the requesting agent is the actor. While we nei­ ther assume that Flakey has complete knowledge of the domain, nor that the people directing him always have correct plans, there are certain other simplifications that we make in order to focus our work.

First, we simplify the form of some of the intentions that Flakey reasons about. The plans he infers may in­ clude actions done by the requesting agent, as well as actions done by Flakey himself. Strictly speaking, one agent cannot have an intention that has as its object an action of another agent-although one may have an in­ tention to cause some other agent to perform an action [Castaneda, 1975). We will finesse this distinction in this paper .

Second, we bound the number of nested beliefs that Flakey needs to consider. In our examples, Flakey can reason about his own beliefs, and about the actor's be­ liefs about the world or about other agents. However, we rule out the need for Flakey to reason explicitly about the actor's beliefs about Flakey's own beliefs. This amounts to an assumption that Flakey believes that the actor's beliefs about his (Flakey's) own beliefs are cor­ rect. This assumption is not essential to our account, but it simplifies the subsequent discussion.

Third, we avoid the "Dudley Doright" problem [Mc­ Dermott, 1982], by assuming that there is a distinction between what agents expect to achieve as a result of their intended actions, and what they believe is or will be true independent of their actions. We use the term achieve to represent the former, and believe to represent the lat­ ter. If an agent either will achieve some proposition or believes it will be true, then we say that he expects it.

Finally, while recognizing that the temporal aspects of a plan can be the subject of complex reasoning in their own right, we simplify the structure of time by adopt­ ing the situation calculus view of single atomic actions occuring between discrete situations, with propositions being true at. a situation.

3 The Structure of Plans

Because plan ascription involves reasoning about the be­ liefs and intentions of agents, we define a language £ containing operators whi ch express these concepts:

INT(a, o·) agent a intends plan fragment a

BEL( a, p) agent a believes proposition p

ACH(a ,p) agent a will achieve proposition p

EXP( a, p) agent a expects proposition p to be true

These, together with truth (T), constitute the operators of£. £also contains constants denoting the agents in the domain: F denotes Flakey, and II denotes Harry. Also, R denotes a (particular) report and 0 denotes Harry's office; the initial situation is 50 , followed by 51 and 5 2 .

In our examples, Flakey must infer Harry's plans, which may include actions done by Flakey. Flakey thus needs to represent his own beliefs about the world, as well as his beliefs about Harry's intentions and beliefs. In turn, Harry's beliefs may themselves concern the be­ liefs and intentions of Flakey. In a more general setting we would need to represent all of these constructs; here, however, we bound the number of nested beliefs that Flakey needs to reason about, as noted above. Flakey represents the truth of the proposition p as T(p), and he represents Harry's belief in pas BEL(H,p). Similarly, we bound the number of nested intentions: Flakey need only reason about Harry's intentions (usually that Flakey per­ form some act), which we represent as INT(H, a).

Finally, we need constructions for propositional ex­ pressions (pexp) and plan-fragment expressions (plan­ exp ), which can serve as arguments to the operators of £. Propositional expressions are formed from a property name and parameters, which usually include parameters for the situation (or time) at which the property holds. For our examples, we need only two properties:

at( a, l, t) agent a is at location l at timet

has( a, o, t) agent a possesses object oat timet

There are two kinds of plan-fragment expressions. The simpler kind are similar to propositional expressions: they are formed from an action name and parameters, which, again, usually include parameters for the situ­ ation at which the action commences. Plan-fragment expressions also include a parameter for the agent per­ forming the action. We can call this simple kind of plan­ fragment expression an action expression (actexp) . In the RDD we need the following actions:

get( a, o, t) agent a gets object o at time t

move( a, d, t) agent a moves to location d at timet

trans( a, o, d, t) agent a transports object o to location d at timet

bring( a, o, b, t) agent a brings object o to agent b timet

We allow implicit coercion of actexp's so that they can serve as propositions. Thus we can can say that Flakey believes that an action specified by the expression a oc­ curred (or will occur) by using T(a); that the agent a be­ lieves this by BEL( a, a). Of course, we can a.Iso say that Fla.key belives that a intends to perform a by INT(a, a).

!\![ore complex plan-fragment expressions can be built using the operators BY and TO:

BY(actexp, actexp,pexp) the complex plan fragment, consisting of doing the second actexp, by doing the first actexp while the pexp is true

TO( actexp, pexp) the complex plan fragment, consisting of making the pexp true by doing the actexp

When we write INT(a, BY(a,f3,p)), we mean that agent a expects p and intends to do {3; moreover, a intends to do f3 by doing a. When we write INT(a, TO(a,p)), we mean that a intends a, as a way of achieving p. As before, we allow for implict coercion from planexp's to pexp's. This enables us to specify that an agent a be­ lieves that a given relationship holds among actions: for example, BEL( a, BY(a, {3,p)) denotes a's belief that if p is true, the occurrence of a guarantees the occurrence of {3. A similar coercion applies to TO, so, for example, we represent Flakey's belief that when an agent gets an object, he then has the object, as follows:

Axioms such as this will be introduced as needed in Sec­ tion 5.

4 An Argumentation System for Plan Ascription

In this section we give a brief overview of the defeasible argumentation system ARGH [Konolige, 1989]. ARGH is a formal system, in the sense that its elements are for­ mal objects, and the processes that manipulate them could be implemented on a computer. It is similar in many respects to so-called justification-based Truth Maintenance Systems [Doyle, 1979], but differs in the diversity of argumentation allowed , and the fact that arguments for a proposition and its negation may co­ exist without contradiction. It also differs from formal nonmonotonic logic approaches, such as circumscription [McCarthy, 1984] or default logic [Reiter , 1980], in that it makes arguments the direct subject matter of the sys­ tem. Finally, it differs from other direct argumenta­ tion systems (for example, those of [Horty et al. , 1988, Loui, 1987, Poole, 1985]) in that it has an explicit notion of argument support independent of belief, and allows a flexible specification of domain-dependent conditions of adjudication among arguments.

The purpose of argumentation is to formulate connec­ tions between propositions, so that an agent can come to plausible conclusions based on initial data. Formally, an argument is a relation between a set of propositions (the premises of the argument), and another set of proposi­ tions (the conclusion of the argument). For example, an argument that Flakey's beliefs are also Harry's beliefs could be stated as:

Arguments are normally specified by schemata, in which we allow free variables to stand for arbitrary terms . Here p is a. schema variable for an arbit.ra.ry propositional ex­ pression. V·/e will generally use lowercase roman letters to indicate schema variables. Classes of arguments in ARGH are given names. All arguments of a. schema must belong to the same class: the schema. above defines part of the belasc (belief ascription) class of arguments.

In the process of argumentation, we start with an ini­ tial set of facts (which we call a world) describing the sit­ uation in question . We then use argument schemata to construct plausible arguments based on the initial facts. The process of deciding which arguments are valid ones from a given world makes direct argumentation systems interesting and complex. In ARGH , the concepts by which we express the validity of the conclusions of ar­ guments are support, conflict, defeat and acceptance.

• Support. The conclusion of an argument is supported by a world if the premises of the argument are sup­ ported, provided the argument is not defeated (see below). All initial facts of a world are supported. To eliminate circularity in the support relation, we demand that no argument be used in the support of its own premises. Note that a proposition and its negation may both be supported, if there are valid arguments for both of them.

Conflict. Two propositions are said to conflict if they are in some way opposites. Generally, a proposition and its negation conflict. For a particular domain we will often specify explicitly which propositions conflict, without necessarily deriving the negations. A proposition that does not conflict with any sup­ ported proposition in a world is called uncontested.

Acceptance. If a proposition is supported by an argu­ ment whose premises are accepted, and it is uncon­ tested, then it is accepted. By definition, a propo­ sition and its negation can never be simultaneously accepted. vVe consider accepted propositions to be valid conclusions about a world. By fiat, all initial facts of a world are accepted, and cannot be con­ tested.

Defeat. An argument is defeated in a world if the condi­ tions of its defeat hold in that world. We will define such conditions below; generally, they are used to specify which of two arguments supportihgconflict­ ing propositions is to prevail. Defeat is what makes arguments defeasible, and is one of the most com­ plicated and interesting parts of defining a domain.

Unfortunately, these definitions do not guarantee that for any world there will be a single consistent assignment of support and acceptance. For example, it is possible for the arguments to two conflicting propositions to be mutually defeating, so that we could consistently assign acceptance to either of the propositions. In this case, there is a genuine ambiguity in the acceptance process, and although ARGH allows us to conclude either one, we prefer to remain skeptical of both. This problem is similar to that of deciding among multiple competing extensions in typical nonmonotonic formalisms [Horty et al., 1988].

5 Ascribing Beliefs and Plan Fragments

In our model of plan recognition , the initial world con­ sists of the beliefs and intentions that can be directly "read off" the actor's utterances, along with any previ­ ously held mutual beliefs. 2 The argumentation system is then used to discover the actor 's intended plan. It does this by applying arguments to discover plan frag­ ments that can be ascribed to the agent, some of which will eventually be labeled accepted by the argumenta­ tion system. V·/e now present some specific arguments for local ascription, and illustrate their use with some examples from the RDD.

5.1 Belief Ascription Arguments

The problem of deciding what beliefs to ascribe to agents is a complex one, and beyond the scope of this paper . Rather , we will use the simple defeasible rule that agents are likely to know the true facts about the general effects and relations of actions, as well as the particular facts that are true of a given situation:

Since the reasoning is being done from Flakey's point of view, this essentially ascribes to other agents all of Flakey's beliefs about the domain. Belief ascription is defeasible, so specific information about other agents' beliefs can override this rule.

The other rules of belief ascription that we need en­ code the fact that either believing or achieving pis a way of expecting p:

5.2 Plan-Fragment Ascription Arguments

These arguments are used to ascribe BY or TO plan fragments to the actor, based upon what the observer already believes he intends. · Vve start with an argument that ascribes a TO fragment:

This schema says that, if an agent a believes that p is an effect of performing a, and he intends to do a and to achieve p, then it is plausible that his reason for doing a is to achieve p. Instances of this rule are used to coa­ lesce plan fragments. A similar rule coalesces fragments involving the BY relation:

2 This then implies that the agents in our domain com­ municate with one another in a formal language that pre­ cludes indirection. In a model of plan recognition in natural­ language discourse, the initial facts would be that the ut­ terances themselves were observed, and one of the tasks for plan recognition would be the derivation of the intentions and beliefs encoded in those utterances.

Note that in the BY relation, the enabling condition p is expected : it can be either already believed to hold, or achieved by some other plan fragment .

EXAMPLE 5.1 Harry requests that Fla.key get there­ port so that Flakey will have it. 3 The initial facts consist of the following intentions and beliefs derived directly from Harry's request :

as well as Fla.key's a priori beliefs about domain plan relations, one of which is relevant here:

From this world, the belasc schema. is used to gen­ erate support for

BEL(H, TO(get(F, R, So), has(F, R, S1))). The tol schema can then be used to support INT(H, TO(get(F, R, S0 ), has(F, R, S1))) . Since there is no conflict, these propositions are also ac­ cepted.

Additional arguments extend ascribed plan fragments. The following schema provides support for an intended TO relation when its precipitating action is observed:

This rule is intuitively weaker than the tol rule because it uses less evidence. VV!=!aker still would be an argu­ ment in which an intended TO relation was inferred simply from the expectation of its effects. (This would correspond to a traditional "backward-chaining rule", while the to2 schema corresponds to a "forward-chaining rule .") The reason this would be such a weak rule is that there are usually very many ways of achieving a propo­ sition, and context-dependent information is required to focus on the likely intended way. We will return to this problem below (Section 5.3).

There are also fragment extension arguments for the BY relation:

3 It may perhaps seem odd that Harry would be so ex­ plicit in specifying his request. To some extent this is true, but we intend this very simple example to illustrate the basic elements of belief ascription and recognition of the relation among known intended actions. Also, it is worth noting that study of human conversation shows that in fact people pro­ vide a great deal of explicit information about their plans when they are communicating [Pollack, 1986]. In addition, one might imagine a variant in which Harry says "Get the report so that you'll have it when Sue calls for it," a quite natural-sounding request .

We are generally willing to infer an intended BY relation from knowledge of any two of its components. With more contextual information, it may also be possible to infer this from one component.

5.3 Context-Dependent Ascription

Consider the following example:

EXAMPLE 5.2 Harry requests that Flakey get the re­ port so that he (Harry) can have it, i.e., the intial world includes:

The obvious implication, in the context of Flakey as a delivery service, is that Flakey should bring the re­ port to Harry. However, there is no way of generating INT(H ,bring(F,R,H,S')) from ACH(H,ha.s(H,R,S)) - the to2 argument works in the other direction. As we have argued, there could be many ways of achieving a proposition, and in order to infer which of these is the correct one (that is, which one Harry has in mind) it is necessary to use contextual information. In any given domain , there are certain "normal" or "typical" ways to do things , which are more likely than their alternatives . In the RDD a request by an agent to Flakey is usually an attempt to get Flakey to deliver something. In this case, we would have the following context-dependent rule:

We do not have a theory of how Flakey would arrive at a set of such rules; but supposedly it would involve knowledge of the frequency with which certain types of requests are made, the utility and cost of various alter­ native actions, and so on.

6 Adjudicating Local Ascriptions

One common result of having many local ascription rules is that their conclusions will often conflict. Often, it is possible to adjudicate these conflicts on the basis of local information, thus sharply limiting ambiguity in ascrip­ tion. In this section we examine two types of local adju­ dication. First, however, we define conditions of conflict in the RDD.

6.1 Conflicting Propositions

For the examples in this paper we will need only two kinds of conflict. If an agent expects to achieve p by per­ forming some action, he generally will not believe that p will become true if he does not act. Similarly, if he believes p will be true regardless of his actions, he will generally not plan to achieve p. So we have:

A second kind of conflict arises when two intended ac­ tions would occur at the same time and have the same effect. Thus Flakey bringing Harry the report, and Harry getting it himself (in the same time interval) are conflict­ ing intended actions.

6.2 Initial Fact Defeat

Our first defeat rule acknowledges t he importance of ini­ tial facts :

Initial Fact Defeat An initial fact of a world defeats any argument supporting a conflicting proposition.

EXAMPLE 6.1 Consider a slight variation of Example 5.1. Harry makes the same request as before, but this time Flakey already has the report. Conse­ quently, to the initial world given above we add the statement:

By belief ascription , there should be support for BEL(H, has(F, R, S1)) . However , this conflicts with ACH(H, ha.s(F, R, 51)) . Because the latter is an initial fact- it was derived directly from Harry's request-it defeats the belief ascription argument . Harry's beliefs are hence judged to be different from Flakey's.

Example 6.1 provides a very simple example of an ac­ tor with an incorrect plan . Here, the problem with the plan is that it relies on an incorrect situational belief. In other cases, actors' plans may rely upon incorrect beliefs about the relations between actions (represented with BY or TO statements) . To handle these cases, we can in­ troduce additional plan-fragment ascription rules, mod­ eled on those developed by Pollack [Pollack, 1986], along with defeat principles that adjudicate between compet­ ing plan-fragment ascription rules . For example, argu­ ments that ascribe belief in incorrect relations are gen­ erally defeated by those that ascribe correct belief.

6.3 Purposeful Action Defeat

ExAMPLE 6.2 This time all that Harry requests is that Flakey get the report: he does not assert why he wants him to do that. And Flakey already has the report. So the initial world is:

As in Example 6.1, belief ascription leads to sup­ port for BEL(H, has(F, R, S1)). But it is also the case that the to2 rule results in support for ACR(H,ha.s(F,R,S1)) , and as before these two facts conflict . The natural conclusion is that Harry wants to achieve Flakey's having the report: he does not realize that Flakey already has it. The argument using the to2 schema defeats the belief ascription argument .

We thus propose the following defeat principle:

Purposeful Action Defeat If x ~ ACH(a,p) is an argument whose premises x are supported, and so is y b~c BEL(a,p), then the belief ascription ar­ gument is defeated.

The name of this defeat principle reflects the fact that it encodes a presumption that agents engage in purpose­ ful actions: they do not typically intend actions whose effects they already believe to be true.

ln the RDD the Purposeful Action Defeat principle results in natural conclusions. However, in more com­ plex domains, this rule would have to be complicated. To see why, imagine a case in which an intended action o· could be used to achieve more than one proposition. If t.he observer believes that one of these, say p, is already t.rue, while another, say q, is not, he may be justified in inferring that the actor intends to do a in order to achieve q. He does not then need to ascribe to the actor a mistaken belief that p is not true. Balancing such con­ siderations requires the use of experiential, or context­ dependent knowledge: such reasoning should be used only if q is a likely intended result of a. We now turn our attention to another way in which context-dependent knowledge can affect plan recognition.

7 Evaluative Methods

As we indicated earlier, local ascription is only part of the process of plan recognition. Local information that can plausibly be ascribed to an actor must be evaluated to determine whether it forms a globally coherent struc­ ture.

7.1 Conflicting Action Defeat

In addition to the kinds of local defeat rules presented above, one can distinguish among alternative plan­ fragment ascriptions by using the context of the other ascribed fragments. That is, if there are competing al­ ternative actions, and one of them is part of a coher­ ent set of ascribed plan fragments while the other is not , then we prefer the former. To illustrate this princi­ ple, recall Example 11, in which Flakey needs to derive INT(H, bring(F, R, H, S')) from ACH(H, has(H, R, S)). Now consider what happens if he makes use of the fol­ lowing reasonable argument schema:

While still context-dependent, this rule is more general than to3, since it supports ascribing an intention to do any action which leads to an agent having an object.

Flakey can use to4 to infer support for both INT(H, bring(F, R, H, Sl)) and INT(H,get(H, R, S1)); these intentions conflict, because they occur at the same time and lead to Harry having the report. (Recall, from Section 6.1, that in the RDD, two intended actions con­ flict if they would occur at the same time and have the same effect.) This conflict means that Flakey will not be able to accept either intention, although both are sup­ ported.

How can we distinguish the correct inference, that Flakey should bring Harry the report? As we noted above, this intention differs from Harry's intention to get the card himself in that it is connected by plan fragments to another initial fact: Harry's intention that Flakey get the report . Let us define the support set of a proposi­ tion as those initial fact INT and ACH predicates which are used as premises in some argument chain that sup­ ports the proposition. Then we can state the preference for the more-connected intention as the following defeat principle.

Conflicting Action Defeat If a and f3 are conflicting actions, and INT( a, a) and INT( a, /3) have argu­ ments with supported premises, and the support set of the former is a proper superset of the support set of the latter, then any argument to INT( a., /3) is de­ feated .

7.2 Limits of Global Evaluation

Global evaluation may itself be a complicated process, involving many different coherency rules; Conflicting Ac­ tion Defeat is only one example. Moreover, global eval­ uation may fail: the observer may not be able to view the locally ascribed beliefs and intentions as a globally coherent plan. Consider one more example:

Ex AMPLE 7.1 Harry requests that Flakey get the re­ port so that he will win a bet he made with Sue. (It will suffice for our purposes to repre­ sent this last proposition as winbet(H,S1).) The initial world includes INT(H, get(F, R, S0 )) and ACH(H, winbet(H, S1)). Flakey may believe that Harry intends for there to be some connection be­ tween these two facts: he could come to this belief through the use of arguments derived from the Co­ operative Principle of Conversation [Grice, 1975), which we do not present in this paper. However, Flakey is unable to determine precisely what con­ nection Harry intends: in a very real sense, Flakey is unable to recognize Harry's plan. He may need to ask him what he has in mind.

In this example, Flakey is not able to find a single coherent plan that explains Harry's request. 4 He cannot relate the asserted intended action and the asserted goal; in particular, he cannot infer INT(H, TO(get(F, R, S0), winbet(H, S1))). When the locally ascribed beliefs and intentions do not form a glob­ ally coherent structure, further interaction between ob­ server and actor may be necessary.

8 Conclusion

We have presented a direct argumentation model of plan recognition which we are currently developing. We be­ lieve that plan recognition is especially well suited to this approach, for several reasons. First, knowing enough to engage in plan recognition means not only knowing what kinds of arguments there are for belief and intention as­ cription, but also knowing about the relative strength of these arguments. The defeat principles described in this paper are examples of this. Direct argumentation sys­ tems provide a. natural way of representing such knowl­ edge. Second, in direct argumentation systems, the ar­ guments used to arrive at any conclusion are readily available for inspection-and cooperative interaction re­ quires that agents reason about the correctness of the plans they ascribe to others. Finally, direct argumen­ tation systems are incremental, in the sense that one can add a single argument at a time. This means that when resource limits are encountered, the argumenta­ tion process can stop, and return the best conclusion so far derived. This contrasts with indirect systems for de­ feasible reasoning, such as circumscription, which rely on some kind of global minimization [Konolige, 1988]. Although we have not focused on this aspect of plan recognition in this paper, the ability to cope with re­ source limitations during reasoning is crucial for agents situated in dynamic, multiagent environments-the very agents most likely to make plans and reason about one anothers' plans [Bratman et al., 1988] .

4 In our account, such a plan would consist of a set of intended BY and TO relations that connected all the as­ serted intentions and goals, and that also connected those to a likely domain goal. Deciding what constitutes a likely domain goal-i.e., deciding when to terminate the plan recog­ nition process-is, in general, a difficult problem. Existing systems have either assumed that there is a very small set of goals [Allen, 1983, Kautz, In Press, Litman and Allen, 1987] or else that the actor makes his goal explicit [Pollack, 1986].

Acknowledgements

We would like to thank Ray Perrault for his comments on this work.