The Intentional Description of Reactive Systems

Author: Dr. Nigel Seel

1. Introduction

This is a revised and more "user-friendly" version of [Seel, 90] which wrote up my Ph.D. work for publication. The latter has more pictures, and its slightly greater austerity may please the formalist. Still all the math is still here, it's just more clearly explained!

The problem we're looking at is simply stated. Take an example: we can look at intelligent robots operating in trial-and-error mode in a local environment, and accurately describe their behaviour using sentences like "look, it didn't know there was a hole there, that's why it fell over", and "now it knows where the power supply is, it will find a direct route".

In the jargon, this use of words like "knows", along with words like "believes", "wants" to describe and predict the behaviour of agents is called intentional description. It's so natural that it's not even obvious why it should be problematic. But the designers and engineers who constructed the robot have a different story as to how it behaves. They understand the causal mechanisms underpinning its perceptual, information-storage and problem-solving abilities. They can also predict (and alter and fix) the robot's behaviour.

Engineers normally have little time for intentional descriptions, considering them as so much sentimentality and anthropomorphism. Also, they don't see how intentional descriptions could work - the casual observer doesn't, after all, know the engineering. Still, intentional descriptions do work - we use them all the time and not just for robots.

To see how it all fits together, we need to use mathematical models: both for robots and their environments (for which we use automata-type formalisms) and for intentional language (for which we use logic, namely the special modal logics of knowledge, belief and goals).

It then turns out that the relationship between the two kinds of description, intentional and engineering, comes out in the maths as a semantic relationship between formulae in the logic and the appropriate automata-structured model spaces of the logic.

To properly get the details of what follows, you need to know basic propositional modal logic as taught in introductory AI or logic courses. Despite the jargon, the paper is more interested in conceptual clarity than the use of deep or intricate mathematical techniques (in fact I don't use any). If you read the words and avoid the formulae, you still get the gist of what's going on. A shorter alternative to reading the rest of this paper is to look at (Seel, 1991).

1.1 Theorem-provers vs reactive systems

There is a view in AI that to describe an agent in intentional terms is inherently architectural, so that (for example) an agent is taken to know some state-of-affairs P just when a token syntactically expressing P is structurally present within some component ("database") of the agent [Fodor, 75; Konolige 86]. This leads to the view that an intelligent agent necessarily possesses a formula-manipulation architecture [Genesereth and Nilsson, 87 p.235]. I have never found it easy to understand how such an obviously wrong idea attained the status almost of dogma in AI circles.

A challenge to this view is provided by work in the 'reactive systems' tradition [Brooks 86;Kaelbling 86;Kaelbling 90], which has explored stimulus-response, "insect"-type architectures for autonomous agents. An example was the agent of [Horswill and Brooks, 88], which is able to follow objects in its environment. It functions by generating relatively low-level control signals from relatively low-level processing of image data picked up by its sensors: there is no need to include a gratuitous 'declarative world-model'. Similar low-level mechanisms have been discovered in the domain of biological cognition, for example in the study of frog cognitive architecture [Lettvin, Maturana, McCulloch, Pitts, 59; Winograd and Flores, 86, Chap 4].

Artificial reactive agents, and biological systems are still susceptible to description in intentional terms, however [Dennett, 78; Dennett, 87]. We would like to say that they know some things, are ignorant of others, learn, make mistakes etc. This presents us with something of a conceptual problem: we have effective methods of describing agents at both an intentional and mechanistic level. But how are these two species of description to be connected ?

The conventional "possible worlds" analysis of intentional description is of limited help as it stands. It suggests that an agent's intentional state is characterised by an observer (or agent designer) indirectly, by associating the agent 'epistemically' with possible situations ('worlds') with which it is deemed to be acquainted [Hintikka, 62; Barwise and Perry, 83]. While this is an improvement over the unconvincing position that agents could not be described intentionally unless they were built in a certain, formula- manipulating way, it still does not tell us how to connect intentional and architectural descriptions of the same agent. So this approach as such also can't be right. Let's see if we can do better.

1.2 The Skinner Box example

I have taken a very simple example of an agent in a moderately unfriendly environment, where the requirement is that the agent is obliged to learn how best to behave. In fact, I consider a laboratory rat as an agent being subjected to experiments in a Skinner Box in a Psychological Laboratory.

This problem can be modelled at the mechanistic, automaton level, in which the agent is considered a reactive system, without any special representationalist structures such as well-formed formulae, or formulae databases in its architecture. Rats are not believed to have such anyway.

The agent is initially ignorant about its environment, has some experiences good and bad, and eventually learns to behave appropriately. Hence there is also scope for an intentional level of agent description (as I have just done).

I adopt the following approach. A logic is described which can express formally the knowledge (and lack of it) of the agent at various times, and this can be used to reason about its mistakes and learning. So what is the connection between the logic and the agent-as-mechanism? Simply this: that the agent-environment structure, evolving over time, acts as a model for the logical system, so that the connection is one of satisfaction.

I will start by defining a mathematical model of reactive systems, the SRS-model. I will then briefly define a temporal logic interpreted over the SRS-model and show that it captures a behaviourist type analysis of agents (recapitulating [Seel, 89a]). Finally I will add an epistemic operator K, and show that it formalises finer grained behaviour such as learning and making mistakes, which are unrepresentable in a behaviourist account.

2. A behavioural account of an agent in its environment

In order to make the discussion more concrete, I will take as an example a class of psychological experiments in which an autonomous agent ("a lab rat") is placed in a Skinner Box [Staddon, 83, p.126] and its behaviour analysed. The Skinner Box consists of a rewarder, which can output a reward, shock, or do nothing; a light which can flash on, or be off; and a button which can be pressed by the agent, or left alone.

A protocol for an experiment is a collection of rules which tells the rewarder how to behave, conditional on the light and button behaviour. The task for the agent is to operate the button to ensure rewards, and avoid shocks.

Typically an agent is assumed not to "know" the protocol by which the box operates. By exploratory behaviour it comes to "understand" the box's functioning, and to act so as to maximise its uptake of rewards and minimise shocks. The agent in the Skinner Box is thus amenable to intentional description, but also input-output (behavioural), and to mechanism-level description. It is therefore a useful test bench for investigating formulisations of the three levels (operational, behavioural, intentional), and the connections between them.

2.1 The Synchronous Reactive System (SRS) object model

In modelling agents interacting with each other and with their environments, such as Skinner Box lights, rewarders and agents I propose to start with the notion of object. I take an object to possess a unique name, a private internal state, an external state (visible to other objects) and a next state function. The next state function can look at the names and external states of other objects and at its own private state, thereby computing its own next state.

So an object is:-

A worldstate w(i) is then a set of objects.

Given such a worldstate w(i) of m objects, it is determinate what the next worldstate, w(i+1) is, like this:

Note that this defines the "next" function over worldstates. Object names and next state functions are invariant. All that happens is each object's internal and external states get updated like this ....

Each object's next-state-function looks at its own object's name, internal and external states, plus the names and external states only of all the other objects. It then uses this information to compute the object's own next internal and external state, which it returns as the pair: (internal state, external state).

All the objects update themselves synchronously. Any particular object behaviour can be obtained by the specific definition of its own next-state-function.

If we start with some initial worldstate w(0) and keep applying "next" to get w(1), w(2), ..., then the resulting infinite sequence of worldstates is called an SRS-world (SRS stands for 'Synchronous Reactive Systems').

An SRS-world w is useful for several reasons. Firstly it can model arbitrary synchronous computational processes (there are no special restrictions on object components); secondly it is easy to implement an initial worldstate and the "next" function in a language such as Lisp (or maybe even Java?), and then run simulations; thirdly (as we shall see) SRS-worlds provide a clean semantics for modal logics.

2.2 A Propositional Temporal Logic - PTL

To support a behavioural-level analysis of object behaviour, I define a propositional temporal logic (which I will call PTL) which can be interpreted over a single SRS-world w. We will have a finite set of sentence tokens and operators O - next; [] - always; <> - eventually; and * - immediately previously.

An SRS-world can provide a semantics for PTL as follows. A collection of SRS-worldstates corresponds to a set of worlds. The sequence of SRS-Worldstates generated by "next" induces a total order over worldstates which corresponds to a temporal accessibility relation (this is a standard technique - cf [Manna and A Pnuelli, 81, p.223]).

An SRS model for PTL is then a pair (w,V), where w is an SRS-world and V is a valuation function which assigns truth values to sentence letters at particular worldstates w(i). The semantics of such a logic is completely straightforward.

If A, B are well-formed formulae (wff) of the logic, s is a sentence token of the logic, i is a natural number serving as an index identifying the worldstate w(i) of SRS-world w, then:

The other boolean connectives can be defined by the usual rules as required.

A is satisfiable iff there is some w,i so that <w, i> |= A

A is valid in an SRS-world w, (w |= A), iff <w, i> |= A for all i.

A is valid (|= A) iff w |= A for all w (in the class of models under consideration).

PTL comes with the usual logical axioms, e.g. all propositional tautologies; appropriate temporal axioms for linear temporal logic- [Manna and A Pnuelli, 81, ibid].

Now, PTL is intended to be applied to modelling agents in environments. Hence we are concerned with applied versions of PTL in which special sentence tokens name problem-specific events, and extra axioms capture the properties of problem- specific agents and objects.

In the case of the Skinner Box example sentence tokens L, P, R, S, N are used to name significant events, the connection being established by the valuation function V thus:

2.3 Axioms for the environment and agent

We need to distinguish between constraints which are just axioms, (holding uniformly),and conditional constraints which are axioms of the form where '->' is logical implies (i.e. A -> B means -A v B).

Given the evidence, a formula holding contingently, the constraint subsequently holds uniformly. This can be expressed by saying the conditional constraint becomes actual. The reason for the distinction will become clear below.

The Skinner Box scenario is described in the applied version of PTL by axioms describing the required behaviour of the light, rewarder, and agent objects. For example, the light axiom is:

which expresses the fact that the light alternates between being on and off.

2.4 Axioms for the rewarder

The rewarder is partially characterised by the following axioms Rule R1a says that in any worldstate (w, i), that if ever the light had been on, followed by a press which was then followed by a reward occurring, then always a light, followed by a press, will result in a subsequent reward. Axioms R1b and R1c below make similar assertions for the rewarder's "shock" and "do-nothing" behaviours. Axioms R2a - R4c (not transcribed here - exercise for the reader!) are similar, dealing with courses of events in which the light was on followed by a "not-press" response from the agent; where the light was not on followed by press; etc etc. These axioms, R1a - R4c, legitimise inductive learning by the agent.

Note that further axioms for the rewarder are required ensuring that in any situation just one of R, N, S will hold, and that rewards are in principle obtainable.

Note also that the rewarder axioms take the form of conditional constraints (expressing uniformity of behaviour). Whether the pattern: "light-on, followed by agent-press" is actually followed by a reward (or shock, or nothing) is a contingent feature of a particular world (recall a linear sequence of worldstates). Different worlds w, w' will correspond to different experimental protocols and histories, expressed by different rewarder set-ups and initial conditions. The same axiom set applies though.

2.5 Axioms for the agent ("the lab rat")

The agent axioms express the "law of effect" [Staddon, 83], roughly that behaviour which has been shown to lead to desirable outcomes will tend to recur in the future. Conversely behaviour which has led to undesirable outcomes will tend to be extinguished. Thus: Axiom A1a says that if ever the sequence "light-press-reward" occurs, then the stimulus of a light will always be followed by a press. Note that the exact temporal positioning of the consequent "[](*L & P)" in A1a is to permit behaviour modification to occur as rapidly as possible. Axiom A1b says that events leading to shock result in the agent changing its behaviour in future.

Axioms A2a-A4b are similar, dealing with courses of events in which the light was on followed by a not-press response from the agent; where the light was not on followed by a press etc.

The agent axioms, like the rewarder's, are conditional restraints. Due to variations in protocol between SRS-worlds, it is impossible to axiomatise a fixed and specific stimulus-response behaviour for the agent.

Although PTL is not a suitable logic for intentional systems theory, various behavioural-style results can be proved, for example that eventually the agent will always be able to get rewards, and avoid shocks: full details in [Seel, 89a].

Recall that this is what counts as success in a Skinner Box.

2.6 An SRS model for the Skinner Box example

Given we just axiomatised the required behaviour of the light and rewarder (which together constitute the Skinner Box) plus the rat-agent, how would we go about designing objects in our SRS formalism to allow a simulation of the rat in the box, so that the axioms came out true? Technically, we now want to construct a model of the axioms.

The light, rewarder and agent axioms of the applied version of PTL are valid in a special class of models, those in which the SRS objects simulate by virtue of their construction the required box and agent behaviour. It is quite straight forward to write down objects which capture the required behaviour of the light, rewarder and agent.

2.6.1 Light object

For example, a light b which flashes on and off (ignoring its environment xws) is defined as More complex lights need a more complex internal state and state-management algorithm to drive the timing protocol.

2.6.2 Rewarder object

Similarly, the rewarder is driven by a read-only internal table storing its protocol, and the previously observed light value. The table is looked-up in the context of the previously observed light value and the current agent action to determine the rewarder output. The coding is fairly obvious and is in [Seel, 89b].

2.6.3 Agent object

The agent object is only slightly more complex. A possible architecture stores within itself an ordered table of all possible "stimulus-response" pairs, using the results of perception of the light to search the table from the top to select a press/not-press action. Stimulus-response pairs which lead to shocks are deprioritised over those leading to rewards, hence the table is re-ordered and the agent learns.

Note that, critically, the agent architecture permits a process of attunement, based upon evidence, to the constraints in the agents environment, relevent to its actions. This is required to satisfy the agent axioms. Object descriptions and Lisp simulation are given in [Seel, 89b].

The link between behavioural and architectural levels of description is managed by the satisfaction relation |= between special classes of SRS models and PTL, extended with problem-oriented axioms, as discussed above.

In case you think this is all rather obvious, note that the agent of this experiment would not appear trivial to an observer. As the computer simulation shows, it would exhibit trial and error behaviour, and it would learn rapidly from experience to avoid shock-inducing activities, and to prefer reward-inducing actions. It would exhibit this behaviour in a wide variety of rewarder regimes.

3. The move to an intentional logic

Consider the following example. The behavioural psychologist sets up a Skinner Box according to the following protocol.

3.1 The experiment

Now consider the following partial transcript.

Worldstate 0. The experiment is started with initial conditions that the light is on, and the rewarder outputs nothing; the agent does nothing.

Worldstate 1. Next, the light remains on, the rewarder still does nothing, and the (bemused ?) agent presses the button.

Worldstate 2. Next, the light is still on, the rewarder gives a rewarder, while the agent does nothing.

Worldstate 3. Next, the light is still on, the rewarder gives a shock, and the agent presses.

Worldstate 4. ... ... ..

Formalising the the protocol above, we have that in all worldstates (including the initial worldstate 0) in w:

That is given previous light-on, if you press you will get a reward, and if you fail to press, you will get a shock.

Given that, we may ask.

Intuitively, we feel inclined to say that in situation 1 the rat-agent just "guessed" what to do, while in situation 3 it "knew" that if the light was previously on, the thing to do was to "press".

Similarly, we feel inclined to say that in getting shocked in situation 3 the agent is paying for the fact that in situation 2, it still "did not know" what to do, and by not pressing, "made a mistake". (Look back at the transcript above).

This is intentional reasoning, and it cannot be formalised within our current logic, PTL. I will therefore extend the logic to encompass a new operator, which formalises our "intentional intuitions". Having done so I will then formalise the above example in the extended logic, and show that our intuitions translate into theorems of the logic.

3.2 A road map to intentional reasoning

If we were just to introduce an operator for "knows" into PTL in a superficial manner, we would be immediately faced with the problem of mapping a Kripke semantics, (see for instance [Halpern and Moses, 85]), into the SRS-worlds setup. However in standard treatments, it's fairly mysterious what this apparatus of possible worlds and accessibility relations has to do with real agents and environments.

Still, the way we have set the Skinner Box model up, everything is transparent and explicit. We know what the objects are, we know their internal states at each moment of discrete time. We can run a computer simulation and print out the transcript. So if there is a way to make sense of the intentional descriptions of what's going on, it must be by a careful review of the material in front of us.

So we start by looking carefully at the mathematical model we have developed so far, to see whether a possible-worlds structure lies latent somewhere in the analysis. If we find one, it may allow us to "reverse-engineer" a logic of perception, knowledge and action. "Semantics-first"!.

So why is the agent confused in the early stages of the experiment? From the point of view of the agent-designer, the strongest constraints which could be incorporated into its design, and therefore into its design behaviour, are those guaranteed by the overall axioms: world axioms, which describe how the environment is to behave; and agent axioms, which determine how it is to behave. Looking carefully at these axioms, we see they have an inherent conditionality: they do not say:

they only say: and similarly for other patterns.

So we could partition the collection of "legal" SRS-Worlds ("legal" means which satisfy world and agent axioms for the Skinner Box application) into sub-collections, each of which comprises a number of distinct worlds, corresponding to different experimental protocols and within that different initial Skinner Box conditions.

So it is not surprising, that the agent initially could have been placed in any of these "legal" worlds. In any particular world, however, perfectly definite constraints will be in force (e.g. light-on followed by not-press will definitely and always produce a shock).

Note that these more specific constraints are NOT the axioms, they are the consequents of each conditional constraint axiom whose antecedents happened to be satisfied in this particular world.

It is clearly in the interests of the agent to determine these stronger constraints valid in its particular world as rapidly as possible. But how can it do this?

The answer is perception: the agent can perceive sequences of events, (events like reward, shock, nothing) named by sentence tokens (R, S, N) of PTL, as they occur, and this will rule out the possibility of the agent's world being a world in which different events (and more importantly, different consequential constraints) hold. Thus once the events: "light-on followed by press, followed by reward" have occurred, then the constraint: "light-on, followed by press, will always result in reward" is satisfied in this world, and this allows aspects of the future to be predicted.

Now, take any particular SRS-world w, and at any worldstate indexed by i, consider all the other worlds (NOT worldstates, but whole, infinite-sequence worlds) which shared exactly the same events in the states up to i.

Let me say that again: take the set of worlds which are event-indistinguishable over the sequence of prior world states indexed by 0 ... (i-1). This collection of past- indistinguishable worlds is the largest space of possibilities which the agent, at i, might be in, based on the evidence so far.(Because they don't differ in the evidence so far, of course). The trick now is to look at what these worlds say about the future.

If they all agree about what the agent should do next, then since the agent's actual world is certainly one of these past- indistinguishable worlds, it should feel confident that it can do that unique action. If on the other hand, the various worlds disagree, then this is an indication that not enough evidence is yet in to determine the correct actual constraint holding in the world the agent is actually in.

Since the agent has to do something, its only choice is to guess from the repertoire of "next-actions" supported by the worlds in the current collection of past-indistinguishable worlds. If it turns out that the action chosen, when combined with the constraint which actually holds in the world the agent is actually in, leads to a bad outcome for the agent, then we will say the agent made a mistake.

Now, we could carry on talking about the past-indistinguishable worlds "accessible" from any particular world w at an index i, but there is a neater option. We can exploit the similarity between "accessible past-indistinguishable worlds" and the standard Kripke semantics to induce a modal operator. Such an operator K seems to capture our intuitions about the agent knowing things, and in so far as that is the case, then we may claim to have formalised intentional descriptions and intentional reasoning.

I would like to emphasize the reverse order in which things are being done here. We do not start with pre-existing "philosophical" notions of "knowledge", "desire", which we wish to gratuitously inflict upon the SRS-model. Rather, we start from a semantic analysis, and find we need a possible SRS-worlds structure to explicate our problem-analysis. It is then convenient from the point of view of clarity in formal reasoning, to introduce a modal operator, which it appears, might have some connection with our intuitive intentional notions. Having motivated the approach at length, let us now turn to the formal details, which essentially parallel the discussion above.

3.3 Epistemic theories and epistemic alternatives

We start by collecting together into a set called WorldAxioms those PTL axioms which characterise (i) the required agent behaviour plus (ii) the legitimate environments for the agent.

The collection of SRS-Worlds which model such "legal" environments (i.e. which satisfy WorldAxioms), I will call WORLDS: see figure 1 below. So in the running Skinner Box example,

WorldAxioms = {tautologies + agent & light & rewarder axioms}.

 


figure 1. SRS-Worlds satisfying WorldAxioms, which we call WORLDS

Let w be an SRS-world in WORLDS, and i be an index into it. Because of the importance of the notion of "past- indistinguishability", I need to capture the notion of a "strict-past" formula. This is a formula whose truth or falsity can be determined by looking at worldstates with indices strictly prior to the current index. Thus if A is a strict-past formula, then

can be evaluated by considering only those indices j < i. Hence the formula for "light-on", L, is not a strict-past formula, but *L is.

Consider an agent in world w, at index i, which has access to PTL-namable information from worldstates 0 ... (i-1). We can attribute to such an agent a situated, "epistemic theory" for a world w, at index i, which will be written epistemicTheory(w,i) and will be defined as follows (see figure 2).

 


Figure 2. An epistemic theory at a world-index pair

For all w in WORLDS, i a natural number, A a PTL strict-past formula

1. All formulae in WorldAxioms belong to epistemicTheory(w,i).

2. If <w, i> |= A, then A belongs to epistemicTheory(w,i).

3. All consequence of 1 and 2, and nothing else is in epistemicTheory(w,i).

Note that epistemicTheory(w,i) is the closure under entailment of all the strict-past formulae which are satisfiable at (w, i) together with WorldAxioms, and that

The set epistemicTheory(w,i)is in general not equal to the set of PTL formulae satisfiable at (w,i) because it will omit w-contingent future formulae (i.e. those which require examination of indices >= i in their recursive satisfiability evaluation).

Why is this a useful idea? Because epistemicTheory(w,i) is the most which can in principle be known based on the experience acquired in world w, up to but not including index i. The knower here is any entity which can evaluate each sentence letter of PTL in every worldstate in the sequence w(0) - w(i-1). So we call epistemicTheory(w,i) the theory of the agent at (w,i). (Note we have assumed we have a pretty smart agent here - more about this in the conclusion below - but although it's smart, it's NOT doing any reasoning).

The set epistemicTheory(w,i) is syntactic - a set of formulae. We now use it to construct a derived semantics - the maximal collection of SRS-worlds which make epistemicTheory(w,i) true. Note that these worlds have to agree on the past at the granularity of events named by the logic PTL, i.e. the worldstates with indices < i, but they may differ in the future (worldstates with indices >= i), as epistemicTheory(w,i) is silent about these.

So consider the set of worlds (which we will call the epistemic alternatives at (w,i)) in which, at index i, epistemicTheory(w,i) is true. Define a function "epistemicAlts" which returns this set of worlds.

Another way to put this. The epistemic alternative worlds are the worlds which agree on the PTL-nameable events which have occurred so far. It's clear that the relation of being past-indistinguishable at an index i is an equivalence relation on the SRS-worlds in WORLDS. Let's call this relation E(i).

For all worlds u, v in WORLDS, u E(i) v iff it's not possible to distinguish between u and v based on the PTL-nameable events which have occurred from indices 0 to (i-1) in the two worlds. This looks a touch informal, but it's easy to see how to write a very precise definition [Seel, 89b again!].

At each index i, E(i) partitions WORLDS into equivalence classes of "indistinguishable-so-far" worlds. The function "epistemicAlts" then returns the equivalence class of any particular world w, at index i (see figure 3 below).

For example, in our running Skinner Box example, There is one equivalence class - the whole set WORLDS - for E(0) as there is no evidence at all (which is trivially satisfiable). There are no more than 12 equivalence classes generated by E(1) since in any initial worldstate (with index 0) L, P may independently have any truth value (four options) and any one of R, S and N may be true (three options).

As more evidence comes in with increasing indices, the number of equivalence classes increases as the granularity of each equivalence class gets finer. It's easy to see that the number of equivalence classes generated by E(i) is bounded above by 12i. If you know modal logic, you can probably see S5 (KT45) on the horizon already [Chellas, 80]!

Let's do it. The epistemic alternatives of world w at index i are just those worlds which are in accordance with what has been observed (or can be deduced) from the evidence so far. So things which are true in all of them seem pretty good candidates for what is knowable at (w,i) (as distinct from merely deemed possible, or impossible) by an idealised entity with PTL-complete and veridical perception.

Note that the epistemic alternatives at (w,i) will agree in the future about those constraints which have become actual already, and their consequences - that's why some knowledge of the future is possible here.

Can't resist a philosophical sideswipe. Given an S5 (or KT45) logic, it's conventional to entertain philosophical worries about the interpretation of axioms 4 and 5 (on iterated modalities). Their real effect, however is (with T) to cause the collapse of the iterated modalites [Chellas, 80, p.148] which just means they have no semantic significance. Clearly the iterated modalites don't add much to our Skinner Box scenarios!

3.4 A modal operator: K

On this basis we can extend our propositional temporal logic PTL with a new modal operator K (interpreted as, e.g. "it is knowable"). I give a conventional Kripke semantics, with E(i) as the accessibility relation, A a wff of PTL (I know we have to do this recursively - I don't need it right now, and we fix it below at the end with PETL, where M is also defined!). This says that A is knowable in world w at index i, iff in every world evidentially-indistinguishable from worldstate w(i) then A was true. Note that since E(i) is an equivalence relation, the logic is S5 (KT45) respecting the axioms K, T, 4 and 5.

For any strict-past formula B, we have

This is because as a strict-past formula, B belongs to epistemicTheory(w,i) and is therefore true in all of w's epistemic alternatives at i. However, that's the definition of KB.

Note that this axiom connects temporally-contingent formulae (= strict-past) with knowable formulae. It's not the same as the formula 'A -> KA' (A an arbitrary PTL formula) which if added as an axiom would (in conjunction with axiom T) render the operator K vacuous.

Let's batter this idea to death. If 'A -> KA' (A an arbitrary PTL formula) were an axiom, then each SRS-world w would subsist in the same equivalence class for all of its indices. This equivalence class would be just those SRS-worlds in WORLDS which were indistinguishable by any formula of PTL. This would correspond to an agent which was omniscient about both past and future events.

Note that the following axiom, E1, is valid, as K respects axiom T.

P1 and E1 together capture the relationship between perception, knowledge and action. If you're thinking this looks pretty simplistic, you're not wrong. In defence, we can put the whole analysis of syntax and semantics together in this paper in a clean way, and do the worked example below in a tidy and uncluttered way. The approach is pretty robust since the concepts are basically simple. Therefore, the approach ought to scale to more complex scenarios. Did I hear "lots about groups of rats with imperfect perception then"?? Shame!

OK. We can now check that this formal apparatus permits us to reason about agents in a manner conformant to our intuitions about intentionality. Back to the example of the Skinner Box experiment which started this section.

3.5 Modelling the experiment

As before, the behavioural psychologist sets up a Skinner Box according to the following protocol. Let w be the SRS-world in WORLDS in which the following scenario takes place (as before).

Worldstate 0. The experiment is started with initial conditions that the light is on, and the rewarder outputs nothing; the agent does nothing.

Worldstate 1. Next, the light remains on, the rewarder still does nothing, and the (bemused ?) agent presses the button.

Worldstate 2. Next, the light is still on, the rewarder gives a rewarder, while the agent does nothing.

We now formalise events so far from the vantage point of worldstate three, i.e. (w,3).

So in line 70 we see that the agent presses (for cause!) in worldstate 3 ensuring a subsequent reward (line 80) in worldstate 4.

Worldstate 3. Next, the light is still on, the rewarder gives a shock, and the agent presses.

Worldstate 4. The agent gets rewarded!

This exercise in simple formal theorem proving shows how an observer, making assumptions about the axioms describing world and agent behaviour, together with assumptions abouit the agent's perceptual and action capabilities, can undertake an epistemic analysis of the agent leading to viable predictions of agent behaviour.

Further insight can be gained by reasoning about what an agent doesn't know: consider the following. By the protocol fragment above, in world w the rewarder always gives a shock following a "light, not-press" sequence, i.e.

Thus it is formally derivable that in worldstate 3, the agent will be shocked, because: Although we, as observers, can deduce this, the agent cannot in any worldstate before 4. This is because in earlier worldstates than 4, the epistemic alternatives of w include worlds where something different than a shock occurred in worldstate 3. The constraint PF above has not yet become actual in w (figure 3).

 


Figure 3.

In worldstate 4, the fact of the shock in worldstate 3 can be perceived (uncomfortably!) and this, together with previous perceptual evidence of the light, followed by not-press can be combined with axiom R2b to deduce that in world w, light followed by not-press will always produce shocks.

This shows how the modal operator K generates a kind of 'decoupled', situated and personalised context of deduction, allowing in just the facts made available to the agent by perception within history, together with the general constraints true in all worlds in WORLDS to which the agent is attuned by design.

The logic PTL recursively augmented with the operator K can be called PETL (Propositional Epistemic Temporal Logic).

3.6 Propositional Epistemic Temporal Logic (PETL) - semantics

PETL is an applied logic, parameterised by the set of formulae WorldAxioms, which describe the intended behaviour of the agent and the environment. Recalling the valuation function V and the accessibility relation E above, a PETL model M is now a triple: M = (WORLDS, V, E).

The previous semantics for PTL are simply embedded in this more elaborate semantic space (lots of worlds structured by E, rather than just the one). So if A is an arbitrary sentence letter (e.g. L, P, R, S, N) of PETL, and recalling that O means "next", the semantics looks like this.

The semantics for the other operators is similar.

4. Conclusions

This paper develops a simplified intentional logic of perception, knowledge and action, and interpretes the logic over a semantic domain of interacting reactive systems. We are thus enabled to examine the connection between an agent "knowing" something at a particular moment in time, and its structure at that time. The connection does not require, that the agent store tokens corresponding syntactically to the argument to the "knows" operator K.

We generated the need for a "knows" operator from a consideration of the epistemic alternative worlds. These came from a consideration of those worlds which were consistent with the evidence of experience so far. So a non-trivial knowledge operator is inextricably bound up with the notion of past and future, and the unveiling of facts and contraints over time.

Strictly, there is nothing in the model outlined here which ties the K operator to the agent itself. The K operator is better interpreted as what is 'knowable'. The agent never does any deduction at all, so maybe the subject of knowledge here is the agent designer or the environment observer.

It's an interesting development of the work to consider agents with arbitrary (but not complete) perceptual abilities. Then the epistemicTheory and epistemicAlt functions are indexed by the specific agent as well as by w and i, and the semantics gets more complex. Don't see any problems in principle, however.

The direction I found most interesting was to look at situations where you have multiple agents which have to collaborate and communicate to achieve their objectives. After all, human beings are a particular case of this general problem formulation. I did some work in this direction - it's hard to make progress without the modelling collapsing into the rather well-explored domain of communication protocol design.

Home.

References

1. J Barwise and J. Perry. Situations and Attitudes. (Bradford Books/MIT Press, 1983).

2. R. A. Brooks. A Robust Layered Control System for a Mobile Robot. IEEE Journal of Robotics and Automation, RA-2 (1) (1986) 14-23.

3. B Chellas. Modal Logic: An Introduction. (Cambridge University Press, 1980).

4. D Dennett. Brainstorms. (Bradford Books/MIT Press, 1978).

5. D Dennett. The Intentional Stance. (Bradford Books/MIT Press, 1987).

6. J Fodor. The Language of Thought. (The Harvester Press, 1975).

7. M R Genesereth and N J Nilsson. Logical Foundations of Artificial Intelligence. (Morgan Kaufmann, 1987).

8. J Y Halpern and Y Moses. A Guide to the Modal Logics of Knowledge and Belief: Preliminary draft. Proceedings of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, California, (1985) 480-490.

9. J Hintikka. Knowledge and Belief. (Cornell University Press, 1962).

10. I D Horswill and R A Brooks. Situated Vision in a Dynamic World: Chasing Objects. Proceedings of the National Conference on Artificial Intelligence (AAAI-88), (1988) 2, 796-800.

11. L P Kaelbling, An Architecture for Intelligent Reactive Systems In : M P Georgeff and A L Lansky, eds, Reasoning about Actions and Plans. (Morgan Kaufmann, 1986).

12. K Konolige. A Deduction Model of Belief. (Pitman, 1986).

13. J Y Lettvin, H R Maturana, W S McCulloch and W H Pitts. (1959) What the Frog's Eye Tells the Frog's Brain. Proceeding of the Institute of Radio Engineers. (November 1959) 1940-1951.

14. Z Manna and A Pnuelli. Temporal Verification of Concurrent Programs. In: R S Boyer and J S Moore, eds, The Correctness Problem in Computer Science. (Academic Press, 1981).

15. N R Seel. A Logic for Reactive System Design. Proceedings of the Seventh Conference of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour, U K (1989a). Pp. 201- 211.

16. N R Seel. Agent Theories and Architectures. Unpublished PhD thesis. Department of Electrical and Electronic Engineering, University of Surrey, Guildford, Surrey GU2 5XH, (1989b) Also available as a technical report from the author.

17. Seel, N. R. (1990). Intentional Description of Reactive Systems. In Y. Demazeau & J-P. Muller (Eds.), Proceedings of the Second European Workshop on Modelling Autonomous Agents in a Multi-Agent World. Elsevier Science Publishers B.V./North-Holland. (This is the main technical presentation of my Ph.D work in an accessible form).

18. J E R Staddon. Adaptive Behaviour and Learning. (Cambridge University Press, 1983).

19. L Steels. Cooperation between distributed agents through self-organisation. In: Y Demazeau and J P Muller, eds, Decentralized Artificial Intelligence, Proceedings of the First European Workshop on Modelling Autonomous Agents in a Multi-Agent World. (Elsevier Science Publishers B V North-Holland, 1990).

20. T Winograd and F Flores. Understanding Computers and Cognition. (Addison-Wesley, 1986).

See also:

21. N. R.Seel (1991). The 'Logical Omniscience' of Reactive Systems . Proceedings of the Eighth Conference of the Society for the Study of Artificial Intelligence and the Simulation of Behaviour, U K (1991). Leeds, U.K.