A Formal Account of Self-Knowledge and Action

1 Introduction

Doing all but the most basic actions requires knowledge. For example, in order to call somebody, one needs to know his phone number. Doing an action may have the effect that one acquires some significant new knowl­ edge. The most penetrating theory of the relatio~s~ip between knowledge and action that addresses artificial intelligence (AI) concerns is that of Moore [1985]. His framework is essentially an encoding in ordinary first­ order logic of the possible-world semantics of the combi­ nation of first-order dynamic logic with an S4 modal logic of knowledge. The central result of Moore's work is a def­ inition of the conditions under which an agent is able to achieve a goal by doing an action (CAN), where ability is understood as requiring the agent to know enough to achieve the goal, rather than it being just physically pos­ sible. The definition makes use of the fact that actions are represented by a type of term and that, since we are in a modal framework, we can distinguish between the action description or concept corresponding to an action term and the sequence of primitive actions denoted by the term in a particular possible world. In particular, it makes sense to talk about an agent knowing what an action description is or an agent having de re knowledge of an action. 1 This notion is important because an agent may well know that an action described in a given way achieves his goal without being able to do it because he does not know what primitive actions the description denotes.

The possible-world semantics' account of de re knowl­ edge is that an agent a knows of x that it is ¢ in world w iff in all worlds compatible with what a knows in w, x is ¢. Following Hintikka [1962], knowing who/what () is is taken to be equivalent to knowing of some x that it is 0. This does not however say much about what is actually required for an agent to have de re knowledge; the ques­ tion is recast into that of what is required for the same in­ dividual to exist in distinct epistemically possible worlds. Actually, Moore uses a substitutional interpretation of quantifiers, but since rigid designators are substituted for variables, this has little effect on the issue. There has been much philosophical debate on this question but the common answer in AI circles has been that knowing who someone is requires having a standard name for that person and similarly for knowin&-what [Konolidge, 1986, Levesque, 1984).2 Moore [1985J is not very clear as to whether he actually holds this view, but his assertion that "in describing standard identifiers we assumed that everyone knew what they referred to" seems to indicate that this is the case. The account works well for some kinds of objects (e.g. phones) and some tasks (e.g. ques­ tion answering) but requires some serious stretching in other contexts; for example, what are standard names for a mobile vision-equipped robot?

Moore's definition of CAN is recursive and goes as fol­ lows: an agent is able to achieve a goal by doing an action (e.g. calling a person) iff either the agent knows what the action is (e.g. knows what dialing the person's number amounts to) and knows that doing the action would re­ sult in the goal being satisfied, or the agent knows what an initial action is (e.g. knows what looking up the per­ son's number in the phone book amounts to) and knows that his doing this initial action results in him being able to achieve the goal by doing some subsequent action (e.g. dialing the person's number). Note that the agent is re­ quired to know who he is and what the initial action is. The recursive case of the definition captures the fact that the agent need not initially know all the actions that make up a successful plan as long as he knows that he will know what to do next at each step of his plan. The only way to talk about time is through the dynamic logic operators. Statements that are not in the scope of a dynamic logic operator may be thought to be about the current time. 3

1 Moore states that "knowing what action is referred to by an action description means having a rigid designator for the action described ... a rigid designator for an action must be an executable description of the action" .

2 1 think that formal study of the relationship between knowledge and action holds potential for improving our un­ derstanding of this and other epistemological questions.

One problem with Moore's definition of ability is that it ignores the fact that much of the knowledge required for action is indexical or de se rather than simply de re. 4 For example, if I am at a party, I can go and talk to the person standing by the punch bowl even if I don't know who that person is; nor do I need to know her lat­ itude and longitude or any other objective specification of where she is; all I need to know is roughly where that person is relative to me. If you are tempted to think that one knows who a person is as soon as one knows what she looks like, imagine it's a costume party. Sim­ ilarly, one can go for lunch now without knowing what time it is. Moreover, one can do both of these actions without knowing who one is - for instance if one is amnesiac. The fact that perception also yields mostly indexical knowledge is an additional reason for dealing with it. It has also been argued that indexical represen­ tations carry si&nificant efficiency advantages [Agre and Chapman, 1987j.

It is arguable that all aspects of the indexicality of be­ lief may be reduced to two primitives: 'he himself' or 'I', which stands for the agent of the belief, and 'the current time' or 'now', which stands for the time of the belief (this seems to be the view of Lewis [1979]) . 'Here' can be taken to stand for 'the location of he himself now'. 5 Demonstratives, such as 'this person', may be viewed as abbreviations for descriptions involving 'he himself' and 'now', such as 'the person· at such and such relative lo­ cation from he himself now'. This is the approach we adopt in developing our account.

While it is difficult to deny that one may ignore what time it is or where one is, one may be more skeptical about the possibility of ignoring who one is. It may be argued that one needs not have any objective way of referring to oneself in order to know who one is. But the subjective sense of knowing-who in which this may be the case seems quite distinct from that appealed to in the party example and commonly explained in terms of knowing a standard name. Imagine an agent whose only knowledge was a list associating each person, rep­ resented by a standard name, with his salary. Would such an agent know how much he himself was making? It does not seem so. Or putting it another way, if one were to claim against common intuition that 'oneself' is a standard name, would it be legitimate to expect that all other coreferential standard names would be known to be coreferential? In developing our theory, we will adopt an interpretation of knowing-who and de re belief that requires the object to be known under an appropriate objective description. 6

3 Morgenstern [1987] extends Moore's account to more general actions and plans involving several agents. She gives a consistent account of belief as a syntactic predicate, which results in a more complex but more expressive language. Self­ referential beliefs are expressible, which gives rises to para­ doxical statements such as "This sentence is known to be false" . But these extensions seem largely orthogonal to the issues that concern us here.

4 Failure to appreciate this has also lead to the neglect of indexical knowledge in AI theories of knowledge and belief.

5 It is possible to take 'here' as a primitive instead and define 'he himself' as 'the agent located here now'. We prefer the first alternative because it seems more natural to take beliefs to be properties of agent-states rather than locations where an agent is and times.

There has been disagreement among philosophers on the adequacy of standard possible-world semantics to handle de se attitudes. Our analysis of these issues has lead us to conclude that while standard possible-world semantics is able to distinguish between de se and non­ de se belief (as argued by Stalnaker [1981]), it fails to characterize the purely internal aspects of a belief state - what two agents have in common when the world appears the same when viewed from their distinct per­ spective. Since it is these internal aspects of belief states that play a causal role in determining action, a semantics which provides such a characterization would definitely be superior. 7

In the next section, we propose a logic that handles de se knowledge and belief together with a semantics that characterizes the action-determining internal aspects of belief states. We take the belief accessibility relation B to hold over belief indices, which are world-agent-time triples. ((w, a, t), (w', t', a')) E B if world w' is compati­ ble with what agent a believes at time t in world w if he assumes that he is a' and the current time is t'. Thus, the belief state of an agent at a time in a world is mod­ eled by a set of belief indices, each of which contains an agent that he thinks he might be, a time that he thinks might be current, and a way the world might be if he is that agent at that time. A belief index characterizes both a world and the perspective from which it is viewed. This treatment of de se belief was inspired by informal proposals by Perry [1979] and especially Lewis [1979]. 8

The logic includes temporal operators that allow one to assert that a state of affairs holds at a given time in­ stant (this was implicit in the discussion of belief) and that an agent does an action from one instant to an­ other (adapted from [Rescher and Urquhart, 1971]) . But any characterization of the ability of agents to achieve goals by doing actions requires consideration of possible courses of events that differ from the actual course of events in the way the future unfolds. 9 In the dynamic logic framework adopted by Moore, the modal charac­ ter in this kind of consideration is combined with the temporal aspect, as is made explicit by the 'branching time' semantics of the framework. This limits the ex­ pressive power of the formalism: one cannot really say that an object has a property at a given time, only that the object has the property in the state that results from doing some sequence of actions; there is no way to say that two actions would be completed at the same time or to say that something actually occurred. Our seman­ tic account of de se belief requires a distinction between time and possible worlds and this distinction must be preserved when one allows consideration of different pos­ sible courses of actions. Due to this, in addition to the temporal operators, modal operators for 'historical' ne­ cessity and possibility are included (this aspect of the formalism is adapted from [Thomason, 1984]). 10 Using these operators one can state that an action is possible for an agent at a time, in the sense that all its physical prerequisites are satisfied, 11 or that some effects neces­ sarily hold at the conclusion of an action.

6 Our appeal to the standard name account of knowing­ who in the above argument should not be taken to imply un­ reserved acceptance of the account or necessary dependence of our theory upon it.

7 See [Lesperance, 1989] for a more detailed discussion of these issues.

8 The indexicality of belief discussed here is a very distinct phenomenon from the self-referentiality allowed by Morgen­ stern [1987] . We are not aware of any account that would reduce the former to the latter.

We describe our framework more precisely in the next section. A revised definition of CAN is then proposed. This definition requires the agent to have de se knowl­ edge instead of knowing who he is. Finally, we illustrate through an example how actions should be formalized in the framework to avoid making unrealistic demands upon the agent's knowledge and how the theory can be used to prove that an agent can achieve a goal by doing an action if he knows certain facts.

2 Elements of a formal theory

The following is an abbreviated description of the the­ ory of self-knowledge and action. Further details can be found in [Lesperance, 1989].

2.1 Syntax

Our language is an extension of a first-order language with equality. There are four sorts of terms: individ­ ual terms, agent terms, which are a subclass of individ­ ual terms, action terms, which denote simple actions, and temporal terms, which denote instants. Compound terms of the first three sorts may be formed; the argu­ ments must be individual terms. self, now, and then are distinguished indexical terms, which denote the current agent, the current time, and a contextually determined future time respectively. Variables are written in lower case, while function symbols and predicate constants are written in upper case.

9 No metaphysical commitment is implied here; there should be some naturalistic explanation of such 'ability talk'.

10 This may not be a good name for the brand of necessity under consideration; Thomason seems to take it in a nar­ rower sense than ours - he seems to take only what has already happened to be necessary; perhaps 'causal-historical' necessity is better.

11 This should not be confused with ability, which requires the agent to know of the action that it is possible and has the goal as an effect.

One asserts that a simple action ac is done by an agent ag with the atomic formula ag 8 ac ( 8 is a distinguished predicate constant) . Such an event is assumed to occur from now to then (temporal operators that shift these contextual parameters are introduced below) . Other predicates are taken to denote static relations between their arguments, which are assumed to hold now. We as­ sume a linear ordering on times and the usual relational operators can be used.

Temporal operators can be used to shift the context against which a formula is interpreted, i.e. the times re­ ferred to by now and then: ¢@t means that ¢ holds at or occurs from t, now being coreferential with t in the scope of the @ operator; ¢@@t means that ¢ occurs up to time t, then being coreferential with t in the scope of the @@ operator. We take the temporal operators to have higher precedence than-.. Complex actions are represented us­ ing indexical formulas (action formulas) where self, now, and then stand for the agent, starting time, and com­ pletion time parameters respectively. These parameters can then be bound by shifting the context. All the dy­ namic logic modes of composition except repetition (se­ quential composition, nondeterministic choice, and test actions) can be encoded using the constructs already in the logic. Shorthand forms are provided for readability. Concurrent actions and plans involving multiple agents are expressible in the logic.

0 ¢ means that ¢ is necessary given everything that has already happened; possibility ( ()) is defined in the usual way. BEL( ag, ¢) means that ag believes ¢; if ¢ contains an occurrence of self that is not in the scope of a nested BEL operator or an occur­ rence of now not in the scope of a BEL or @ oper­ ator, the formula is taken to attribute a de se belief to the agent. We define KNOW(ag, ¢) to stand for BEL(ag, ¢) 1\ 3ag'(ag' = ag 1\ ¢'), where ag' is a variable variable that does not occur free in ¢ and ¢' is the result of substituting ag' for all occurrences of self in ¢ that are not in the scope of a BEL operator. 12 CAN(ag,a, ,B) means that ag is able to achieve the goal ,8 by doing ac­ tion a, where a is an action formula and ,8 is a goal for­ mula. A goal formula is an indexical formula where the now contextual parameter stands for the time at which the goal is achieved.

2.2 Semantics

A semantic structure M is a tuple (Agents, Objects, Times, Actions, W, -(, B, ~. ct>, H). The first four com­ ponents are (non-empty) domains for the appropriate sorts; the domain Individuals is Agents U Objects. W is a set of temporally extended possible worlds. -( is a strict total order on Times. B ~ (W x Agents x Times ) 2 is the belief accessibility relation. The rationale behind this formulation was explained in the introduction. B must be euclidean, transitive and serial; this corresponds to the modal system known as weak-S5 or KD45.

~ is a family of accessibility relations - one for each time instant - that is used to interpret the 'historical' necessity operator 0. Intuitively, w ~~ w' if w and w' differ only in what happens after t. ~ must satisfy the following constraints: firstly, for all t E Times, ~t must be an equivalence relation - this implies that at any given instant, D and () obey the principles of the modal system S5; and secondly, for all w, w' E W and t, t' E Times, if w ~t w and t' :j t, then w ~t' w', i.e. possibilities do not increase as time passes.

12 This treatment of knowledge is adopted for its simplicity in spite of its well known inadequacies.

The denotation of terms and the satisfaction of formu­ las are defined relative to indices. An evaluation index is a 4-tuple E W x Agents x Times 2 , where the agent component is the denotation of the indexical self, the first time component is the denotation of now, and the second time component is the denotation of then.

ci> gives the extension of predicate constants and func­ tion symbols at an index. We require that ci> satisfy the following constraints: firstly, for any predicate or func­ tion f, 4>(E,w,a,tl,t2) = cl>(E,w,a',tl,t~), i.e. the de­ notation assigned by ci> to any symbol is constant with respect to the agent and second time components of indices; and secondly, for any predicate or function f, w,w' E W,a E Agents,t1,t~,t2 E Times, if w ~t1 w' and t~ :j t1, then ci>( f, w, a, t~, t2) = 4>( f, w', a, tL t2), i.e. ci> must ensure that historical alternatives up to t1 differ only in what happens after t1.

H C Actions x Indices determines which actions are done ~t which indices; (c, w, a, it, t2) E H iff action c is done by agent a from times t1 to t 2 in world w. We require that starting times always be prior to or equal to ending times, i.e. for all (c, w, a, t1, t2) E H, t1 :; t 2. Finally, for all e E Actions, w, w' E W, a E Agents, t1, t2, t~ E Times, if w ~t2 w' and t~ :; t2, then H(e, w, a, t1, t~) iff H(e, w', a, t1, t~), again to ensure that historical alternatives up to t2 differ only in what hap­ pens after t2.

An assignment is a function that maps variables into elements of the domain appropriate to them. g[vfe] is the assignment that is identical tog except that it maps variable v into the entity e.

The denotation of a term 0 in a structure M at an index L = (w, a, t1, t2) under an assignment g, written [0]~ is defined in the standard way for variables and rec~rsively for compound terms; for the indexicals, we have [self]~= a, [now]~= t1, and [then]~= t 2 .

We can now define what it means for a formula¢ to be satisfied by a structure M, an index L = (w, a, t1, t 2), and an assignment g, which we write M, i, g f= ¢. For conciseness, we omit the standard part of the definition that deals with constructs of first-order logic with equal­ ity; for the rest of the language, we have:

• M, t; g f= ag 0 ac iff H([ac]~, w, [ag]~, t1, t2)
• M, L, g F= tl < t2 iff [tl]~ -< [t2]~
• M, L, g f= c/J@t iff M, (w, a, [t]~, t2), g f= ¢
• M, L, g f= c/J@@t iff M, (w, a, t 1 , [t]~), g f= ¢
• M, L, g f= D ¢ iff for all w' E W such that w ~t 1 w', M,(w',a,t1,t2),g f=¢
• M, L, g f= BEL(ag, ¢)iff for all a' E Agents, t' E Times, w' E W, such that ( (w, [ag]~, t1), (w', a', t')) E B, M,(w',a',t',t2),g f= ¢

Note that the definition of BEL makes then epistemically rigid. 13

A formula ¢ is satisfiable iff there is at least one struc­ ture M, index t, and assignment g, such that M, L, g f= ¢. A formula ¢ is valid (written f= ¢) iff it is satisfied by all structures, indices, and assignments.

2.3 A definition of CAN

Our definition of satisfaction for the CAN operator goes as follows:

This definition is recursive, and similar in structure to that of Moore [1985]. The first disjunct handles the base case: an agent ag can achieve a goal/ by doing an action a in a structure M, at an index t, under an assignment g, if he knows of some simple action ac that whenever he himself does ac starting now, 14 he also necessarily does a starting now (1st. conjunct), that it is possible for him to do ac starting now (2nd. conjunct), and that whenever he himself does ac starting now, the goal/ is necessarily achieved at the completion time of ac (3rd. conjunct).

The second disjunct handles the recursive case: ag can achieve 1 by doing action a at M, L, and g if he knows of some simple action ac that whenever he himself does ac from now to some intermediate time ti followed by some other actions described by a' from ti to t, he also necessarily does a from now to t (1st. conjunct), that it is possible for him to do ac starting now (2nd. conjunct), and that whenever he himself does ac starting now, it is necessary that he can achieve 1 by doing a' at the completion time of ac (3rd. conjunct). 15 Note that only action formulas that encode dynamic logic forms are presently handled by the definition.

The definition differs from that of Moore primarily in requiring that the agent have de se knowledge of the agent (self) and starting time (now) of the actions in­ volved. Other discrepancies arise from differences in our treatment of time, necessity, and complex actions. The definition still requires the agent to know what the next action is and what its arguments are if it has any. In section 3, we show that if actions are correctly specified, this does not require agents to know more than they actually need to.

13 This means that in spite of our intuitions, 3tBEL(AG, t =then) is valid. This will be rectified in future versions of the theory. Usually, it does not cause problems because we quantify existentially over the completion time of actions.

HRemember that formulas that do not mention time refer implicitly to the current time.

15 This formulation, like that of Moore, may be criticized on the following two grounds. Firstly, it fails to characterize the knowledge that the agent must have about what to do after the initial action in terms of his knowing what sequences of simple actions lead to states where the goal is achieved; this knowledge is only characterized in terms of a sentence (a') that describes these action sequences. One shouldn't have to appeal to such syntactic objects in characterizing ability semantically. Secondly, there is nothing that requires the definition to bottom out; an agent that indefinitely does an action known to be always possible is judged to be able to achieve any goal by repetitively doing the action.

2.4 Some properties of the theory

We have an axiomatization of the theory that is sufficient for proving most results of practical interest, such as the example given in the next section. We plan to investigate completeness issues. Due to space limitations, we will only discuss a few properties of the part of the theory that deals with belief.

Since we take knowing-who to mean having a standard name, and standard names are- context independent, it seems reasonable to have an agent know that he is him­ self without knowing who he is. He may even believe that he is someone else (e.g. a lunatic who thinks he is Napoleon). The following proposition shows that the theory respects these intuitions.

Proposition

I= Vag BEL(ag, self= self) 3ag·BEL(ag, ag =self) is satisfiable :Jag BEL( ag, ·ag = self) is satisfiable

Thus, self and now behave essentially like constants.

This affects the way introspection should be character­ ized in the theory. One must say that if an agent believes 1/J, then he must believes that he himself believes 1/J, and similarly for negative introspection. One cannot replace 'self' in the following proposition by a quantified-in vari­ able unless the agent knows who he is.

Proposition

I= Vag[·BEL(ag, t/J) :::l BEL(ag, ·BEL( self, tjJ)))

I= Vag[BEL( ag, tjJ) :::l BEL( ag, BEL( self, tjJ))]

The theory accounts properly for indexical beliefs in­ volving several agents. It distinguishes between alterna­ tive interpretations of 'John believes that Paul believes that he himself is tall',

BEL(JOHN, BEL(PAUL, TALL(self))) and BEL( JOHN, 3ag(ag =self /1. BEL( PAUL, TALL(ag)))),

the first involving John's attribution of a self-belief to Paul and the second involving John's belief about a belief of Paul that is about himself.

3 An example

We will now illustrate through an example how the the­ ory can be used to formalize a simple situation and prove that an agent is able to achieve a goal by doing an action given that he knows certain facts . The example involves the ability of an agent to make a phone call. A high­ level view of this action takes calling to be a procedure involving a source phone and a destination phone. A di­ rect formalization of this would require an agent to know what phones were involved. It is not obvious what de re knowledge of a phone should amount to, perhaps know­ ing the complete number of the phone including area code, or knowing its absolute location. But no mat­ ter what interpretation we take, the requirement seems clearly too strong. Firstly, if the agent knows that the call is local, i.e. his own area code is the same as that of the phone he wants to call, he does not need to know what either area code is in order to be able to make the call. Secondly, the agent only needs to know where the source phone is relative to himself We will show how the calling action can be defined in terms of lower-level actions within our framework in order to avoid making unrealistic demands upon the agent's knowledge.

For simplicity, we will assume that any call to a phone in the same area is a local call (i.e. no need to dial '1 ') and ignore international calls. We start by making var­ ious assumptions 16 about the types of action involved. The action DIALLOC consists of an agent dialing a local call on a phone that is within reach; the action takes the number to be dialed and the location of the phone relative to the agent as parameters. The prerequisites of DIALLOC are as follows: it is possible for any agent ag to DIALLOC any phone number n at a location RLOC(p,ag) relative to ag between now and some future time t if some unused phone p is at location RLOC(p,ag) relative to ag and p is within reach. 17

Formally, this becomes:

Assumption 1: Prerequisites of DIALLOC I= Vag, n, p[ISPHNO(n) /1. PHONE(p) /1. ·INUSE(p)/1. INREACH(p, ag) :::l 3t0ag 0 DIALLOC(n, RLOC(p, ag))@@t)

Now for the effects of DIALLOC: if any agent ag makes a local dialing of the number of a destination phone Pd at a relative location RLOC(ps, ag) from now to time t , and an unused reachable source phone Ps is located at RLOC(ps, ag) relative to ag, and the area code of the location of p5 is the same as that of Pd, this necessarily results in Ps being connected to Pd at time t (this may cause ringing or a busy signal).

Assumption 2: Effects of DIALLOC I= Vag, Ps, Pd, t D [ PHONE(ps) /1. PHONE(pd)/1. ·INUSE(p5 ) /I.INREACH(ps, ag)/1. AREACODE(LOC(p5)) = AREACODE(LOC(pd))/1. ag 0 DIALLOC(NOOF(p~), RLOC(ps, ag))@@t :::l CONNECTED(ps, Pd)@tj

We must also assume that any agent knows what the action of making a local dialing of a number n at a reach­ able relative location I is if he knows what n and I are.

16 That is, we will only deal with semantic structures where the assumptions come out true. Note that due to this, as­ sumptions not only hold now, but at all times, and it is com­ mon knowledge that this is the case.

17 RLOC(x,ag) can be defined as ROTATE(ALOC(x)­ ALOC(ag),FACING(ag)) in a two-dimensional world, i .e. the vector difference between the absolute locations of x and ag rotated by the angle between the direction ag is facing and the absolute frame of reference; INREACH(x,ag) can be de­ fined as LENGTH(RLOC(x, ag)):::; REACH(ag), i.e. pis within reach of agent ag if the length as a vector of the location of p relative to ag is less or equal to the reach of ag.

Assumption 3: DIALLOC is epistemically rigid f= Vag, n, I(KNOW(ag,ISPHNO(n)A LENGTH(I) ~ REACH(self)) :::> 3ac KNOW(ag, ac = DIALLOC(n, I))]

We make similar assumptions concerning the prerequi­ sites, effects, and epistemic rigidity of the action of mak­ ing a long-distance dialing (DIALLD). This action takes the area code of the location of the destination phone as an argument in addition those of DIALLOC. ISAC(c) means that c is an area code.

Assumption 4: Prerequisites of DIALLD f= Vag, c, n, p(ISAC(c) A ISPHNO(n) A PHONE(p)A --,JNUSE(p) A INREACH(p, ag) :::> 3t0ag 0 DIALLD( c, n, RLOC(p, a g) )@@t] Assumption 5: Effects of DIALLD f= Vag, Ps, Pq· t 0 [ PHONE(ps) A PHONE(pd)A --,JNUSE(ps) A INREACH(ps, ag)A ·AREACODE(LOC(ps)) = AREACODE(LOC(pd))A ag 0 DIALLD(AREACODE(LOC(pd)), NOOF(pd), RLOC(ps, ag))@@t :::> CONNECTED(ps, Pd)@t] Assumption 6: DIALLD is epistemically rigid F Vag, c, n, I[KNOW(ag,ISAC(c) A ISPHNO(n)A LENGTH(!) ~ REACH(self)) :::> 3ac KNOW( ag, ac = DIALLD( c, n, I))]

We can now define calling (CALL) as a conditional action in terms of DIALLOC and DIALLD. Note that self, now and then respectively stand for the agent, starting time, and completion time of the action in such complex action definitions. An agent self calls a destination phone Pd from a source phone Ps (from now to then) when he makes a local dialing of the number of Pd at the relative location of Ps if the area codes of the locations of Ps and the destination phone Pd are the same, and makes a long-distance dialing of the area code of the location of Pd and number of Pd at the relative location of Ps otherwise. 18 .

Definition 1: Action CALL self 0 CALL(ps, Pd) = IF(AREACODE(LOC(ps)) = AREACODE(LOC(pd)), self 0 DIALLOC(NOOF(pd), RLOC(ps, self)), self 0 DIALLD(AREACODE(LOC(pd)), NOOF(pd), RLOC(ps, self)))

We also assume that the area code of the location of a phone that is within reach of an agent is the same as that of the location of the agent. Finally, we assume that n is a phone number if it is the number of some phone and that c is an area code if it is the area code of the location of something.

Assumption 7

F Vp, ag[PHONE(p) A INREACH(p, ag) :::>

AREACODE(LOC(p)) = AREACODE(LOC(ag))]

Assumption 8

F=Vn[3p(PHONE(p) An= NOOF(p)) :::> ISPHNO(n)]A Vc[3x c = AREACODE(LOC(x)) :::> ISAC(c)]

Given these assumptions, the theory allows us to prove proposition El, which says that if an agent AG now knows what the location of an unused reachable phone Ps is relative to himself, and knows what the number of another phone P d is, and either knows that his own area code is the same as that of P d or knows that they are different and knows what the area code of P d is, then he can achieve the goal of establishing a connection be­ tween Ps and P d (at some future time) by calling P d from Ps at the current time (see [Lesperance, 1989] for the proof).

Proposition El

F=31, n KNOW(AG,PHONE(Ps) A ·INUSE(Ps)A I = RLOC(Ps, self) A INREACH(Ps, self) APHONE(P d) An = NOOF(P d))A (KNOW(AG,AREACODE(LOC(self)) = AREACODE(LOC(P q)))V 3c KNOW(AG,AREACODE(LOC(self)) :/; AREACODE(LOC(P ci))A c = AREACODE(LOC(P d)))] :::> CAN(AG, self 0 CALL(Ps, P d), CONNECTED(Ps, P d))

Note that the agent only needs to have de re knowl­ edge of the relative location of the source phone and the number and possibly area code of the destination phone; he needs not have de re knowledge of either phone. The phones are arguments of the high-level action CALL, but these absolute references disappear when CALL is mapped into the lower-level actions DIALLOC and 01ALLD in definition 1. It is important that this be done if the requirement for an agent to know what the initial action is in the definition of CAN is not to be overly re­ strictive. Note also how no requirement is made that the agent know who he is; all the knowledge that the agent is required to have about himself, such as whether his area code is the same as that of the destination phone and where the source phone is relative to him, is de se rather than de re.

4 Discussion

Agents act upon and perceive the worJd from a partic­ ular perspective. It is important to recognize this per­ spectival relativity if one is not to be overly demanding in specifying what they need to know in order to be able to achieve goals through action. They need not know very much about the objects they act upon be­ cause these objects are close at hand. And perception yields just the kind of agent-relative knowledge that is needed for action. We have developed a formal theory of knowledge and action that takes this relativity into account. The logic of belief proposed accommodates the indexical knowledge required for action and supplied by perception. The semantic account of belief given clas­ sifies agents not only in terms of what worlds are com­ patible with their beliefs, but also in terms of what their perspective upon these worlds must be. We have pro­ posed a definition of ability that does not require the agent to know in an absolute sense who he is and what time it is. Through an example, it was shown how ac­ tions can be formalized so that an agent does not have to know in an absolute sense which objects are acted upon, but only such facts as where the objects are relative to him. It was also shown how the theory ~ogether with such a formalization can be used to prove that an agent can achieve a goal by doing an action if he knows certain facts.

We are investigating the adequacy of the theory for characterizing agents with different kinds of action reper­ tories at various levels of abstraction. We have advo­ cated a strategy calling for the replacement of the re­ quirements for agents to know what the objects they act upon are by requirements to "know where these objects are relative to them" or "know how to access these ob­ jects". We have shown how this strategy can be followed in the example of the previous section. This suggests that it might at least in principle be possible to system­ atically reduce explanations of ability involving knowl­ edge of the objects acted upon to explanations involving only knowledge of primitive actions and other entities whose characterization as mental representations is un­ problematic, such as relative locations, joint rotation an­ gles, phone numbers, etc. If this characterization of the requirements action puts upon knowledge is correct, it should be possible to produce a revised definition of abil­ ity that embodies it. Preliminary examinations indicate that this is the case for various simple domains involv­ ing agents with limited action repertories, for example, a robot navigating in a simple world and manipulating objects.

However, this approach has some counter intuitive consequences: there is no requirement to even appeal to knowledge of relatively high-level entities such as rel­ ative locations; ability to do high-level actions, such as sending an electronic message to someone giving a talk at a remote institution, can be reduced to knowledge of what primitive actions to do in what circumstances, such as knowing what finger movements to do. But a real person would be prepared to deal with a huge number of unforeseen eventualities arising during the execution of his plan to send a message; he might have to track down the speaker who has moved, etc. It seems that for agents with open-ended action repertories, the flexibil­ ity of behavior cannot be explained without appealing to knowledge of at least some of the objects acted upon, for example, without the agent at some point knowing who the speaker was. The reduction does not capture the right generalizations. But if de re knowledge of objects is required in these cases, what does it really amount to and how is it related to the kind of agent-relative knowl­ edge described earlier, which seems equally required for action. We will describe the result of our investigations of these issues in [Lesperance, 1990].

Acknowledgements

Hector Levesque has been an invaluable source of advice and support. Graeme Hirst , Joe Nunes, Jim des Riv­ ieres, Calvin Ostrum, David Israel , and John Perry have provided useful discussion and/or advice. The referees' comments were also helpful.