Reasoning about Noisy Sensors in the Situation Calculus

1 Introduction

An intelligent agent interacting with a dynamic and incom­ pletely known world faces two special sorts of reasoning prob­ lems. First, because the world is dynamic, it will need to rea­ son about change: how its actions and the actions of others af­ fect the state of the world. For example, an agent will need to reason that if a fragile object is dropped then it will break, and regardless of what else happens, the object will remain broken until it is repaired. Second, because the world is incompletely known, the agent will need to make do with partial descrip­ tions of the state of the world. As a result, the agent will of­ ten need to augment what it knows by performing perceptual actions. For example, a robotic agent may not know initially how far away it is from the nearest wall, but may have a sensor that it can use to obtain information about this distance. How­ ever, because sensors are inherently noisy, it may be necessary to read this sensor (or additional sensors) a number of times to get a sufficiently reliable measurement. In this paper, we pro­ pose a representational formalism for dealing with both sorts of reasoning problems.

Somewhat surprisingly, although the importance of deal­ ing with dynamic and incompletely known worlds has long

· The work of Fahiem Bacchus and Hector Levesque was sup­ ported in part by the. Canadian government through their NSERC and IRIS programs. Hector Levesque is a Fellow of the Canadian Insti­ tute for Advanced Research. The work of Joseph Halpern supported in part by the Air Force Office of Scientific Research (AFSC), under Contract F49620-91-C-0080.

Hector J. Levesque

Dept. Computer Science University of Toronto Toronto, Ontario Canada, M5S IA4

hector@cs.toronto.edu

been argued within AI, very few adequate representation for­ malisms have emerged. We can classify existing ones into two broad camps. On the one hand, we have probabilistic formalisms such as Bayesian nets [Pea88] for dealing with uncertainty in general, and the uncertainty that would arise from noisy sensors in particular. However, with the excep­ tion noted below, these probabilistic formalisms have not at­ tempted to incorporate a general model of action, i.e., repre­ senting what does and does not change as the result of per­ forming an action. In addition, while it is possible to express in these formalisms probabilistic dependencies among vari­ ables, which are in essence atomic propositions, it is not easy to deal with many other forms of incomplete knowledge about the state of the world. For example, it is difficult to say that one of two conditions holds, or that all objects of a certain type have a certain property when it is not known what those ob­ jects are. Logical formalisms, on the other hand, with features like disjunction and quantification, are well suited for express­ ing incomplete knowledge of this type. Moreover, logical for­ malisms like dynamic logics, process logics, or the situation calculus, allow us to reason about the prerequisites and effects of actions. However, none of these logical formalisms allow us to represent what an agent would need to know about sen­ sors, and how the beliefs of the agent should evolve as there­ sult of taking multiple sensor readings. Furthermore, although it is becoming clear that it is possible to combine reasoning from both the probabilistic and logical camps within a single framework [Bac90, Hal90], actions have not yet been incor­ porated into this framework.

Thus it appears that as yet there is no representational for­ malism that would allow us to reason in a general way about both ordinary actions that change the world as well as percep­ tual actions involving noisy sensors. An exception to this is the action network formalism [GD94]. Action networks ex­ tend Bayesian nets to allow probabilistic reasoning about ac­ tion and observation sequences and their effects. However, like Bayesian nets, they have difficulties in dealing with fea­ tures like disjunction and quantification.

In this paper, we propose another formalism for reasoning about actions including sensor-based perceptual ones. Rather than building on Bayesian nets and this form of probabilistic reasoning, our solution builds on a logical formalism for rea­ soning about action. Specifically, we use a variant of the situation calculus [MH69] that incorporates a solution to the frame problem proposed by Reiter [Rei91] for reasoning about ac­ tion, and has been augmented to include perceptual actions by Scher! and Levesque [SL93].

There are several reasons for going this way. First of all, our solution ends up being remarkably simple: all we need to do is to extend the Scher! and Levesque work to ground per­ ceptual actions on noisy sensors. We then preserve the ability to express incomplete knowledge about the state ofthe world, as well as inheriting the solution to the frame problem for rea­ soning about both ordinary and perceptual actions. As we shall show, the resulting formalism also allows certain forms of probabilistic reasoning to emerge as logical consequences.

Compared to other logics of action, the situation calculus itself has proved to be a very convenient formalism for mod­ eling actions, their prerequisites, and effects. Although Re­ iter's solution to the frame problem is limited in a number of ways, it has been extended to handle aspects of the ramifi­ cation problem [LR94], agent ability [LLLS95], and contin­ uous time [Pin94]. Another extension of the theory to deal with complex actions (sequence, iterations, concurrency, non­ determinism, etc.), briefly described in Section 2, has led to a novel logic programming language called GOLOG. GOLOG has proven to be useful for describing high-level robot and softbot control [LLR95]. An implementation of GOLOG ex­ ists at the University of Toronto, and a number of small sample programs (including an elevator controller and a mail delivery robot) currently run in simulation mode. By casting our work within this framework we hope to take advantage of these par­ allel developments.

The format of the rest of the paper is as follows. In the next section, we briefly review the theory of action in terms of which our account is formulated: the situation calculus, the solution to the frame problem proposed by Reiter, and the ex­ tension, proposed by Scher! and Levesque, for dealing with knowledge. In Section 3, we consider how knowledge is af­ fected by readings from noisy sensors. In Section 4, we aug­ ment the framework with probabilities, and present a simple formalization within the situation calculus of the degree of be­ lief an agent has in propositions expressed as logical formu­ las. This allows us to formalize in more quantitative terms the changes in belief that arise from readings of noisy sensors. Examples of the formalism at work are presented in Section 5, and some conclusions are drawn in Section 6.

2 A Theory of Action

Our account of sensors is formulated as a logical theory T in an extended version of the situation calculus [MH69]. The sit­ uation calculus is a many-sorted dialect of the predicate cal­ culus, containing sorts for (among other things) situations, which are like the possible worlds of modal logic, for prim­ itive deterministic actions, and, since we will be dealing with probabilities, for real numbers. We assume the reader is fa­ miliar with the basic intuitions underlying the situation calcu­ lus; we briefly review the main ideas here.

2.1 The situation calculus and the frame problem

In this formalism, the world is taken to be in a certain state (or situation). Changes to the world arise only as the result of actions. This is modeled by having actions map situations to new situations using a special binary function symbol do. This function maps action-situation pairs to new situations, i.e., s' = do( a, s) means that s' is the new situation that is the outcome of performing a in situations. Predicates and func­ tions whose values vary from situation to situation are called fluents and, by convention, take a situation as their last argu­ ment. We read, e.g., P(x, s) as "x has property Pin situation s".l

The background theory T will contain axioms for the usual arithmetic operations on the real numbers, unique name ax­ ioms for actions, and various other foundational axioms for the situation calculus that need not concern us here. The domain-dependent part ofT consists of axioms characterizing the initial state of the world 50 , and the following: for every action type a, a precondition axiom of the form

where s is the only situation term mentioned in the formula II a ( s); for every fluent P, a successor-state axiom of the form

where s is the only situation term mentioned in the formula <Pp(x, a, s). 2

For example, the precondition axiom for the drop ac­ tion might assert that it is possible for the agent to drop an object x in situation s iff the agent is holding x in s: Poss(drop(x), s) = Holding(x, s). For the fluent Broken, a successor-state axiom might assert that x is broken after the action a iff x was fragile and the agent dropped it, or x was broken and the agent did not repair it: Poss(a, s) J Broken(x,do(a,s)) = (a = drop(x) 1\ Fragile(x,s)) V (Broken(x, s) 1\ a =F repair(x)).

These axioms incorporate a treatment of the classic frame problem [MH69] proposed by Reiter [Rei91], extending pre­ vious proposals by Pednault [Ped89], Schubert [Sch90] and Haas [Haa87]. In particular, Reiter shows how the successor­ state axioms above can be automatically generated from a col­ lection of simple effect axioms describing only the changes that result from performing an action. Frame axioms need not be enumerated since they are entailments of the successor­ state axioms. 3

Reiter's solution to the frame problem applies only to prim­ itive deterministic actions. However, Levesque et al. [LLR95] show how, as in dynamic logic [Har79], primitive actions can be composed in various ways to generate an expressive class of complex actions. Specifically, they show that there is a sit­ uation calculus formula, which we abbreviate by Do( A, s, s'), that expresses the proposition that s' is one of the possible out­ comes of doing complex action A starting in situations. Here we only need one type of complex action: the nondeterminis­ tic choice of an action from a parameterized family of actions. Let a( x) be a family of primitive actions parameterized by x. For example, a might be the action "approach the wall" and x might be a numeric parameter specifying the distance to be moved. The complex action ( rrx) .a, can be read as "perform primitive action a( x) for some nondeterministically selected value of x", and it is defined as follows:

1 Of course, in a modal logic, the possible worlds are not part of the syntax, and we would writes f= P(x) rather than P(x, s).

2 This is the axiom for predicate fluents; the axiom for functional fluents would be analogous.

3 Reiter's solution ignores the ramification problem; a treatment compatible with the approach has been proposed by Lin and Reiter [LR94].

Note that since complex actions ultimately reduce to primitive ones, their preconditions, effects and non-effects are automat­ ically entailed.

2.2 Knowledge and action

Scher! and Levesque [SL93] provide another extension toRe­ iter's basic approach by incorporating an epistemic state for the agent. To characterize this epistemic state in the language of the situation calculus, they follow Moore [Moo85] and in­ troduce a new binary fluent I<. The I< fluent acts as a binary relation on situations, just like the accessibility relation be­ tween possible worlds in modal logics. Intuitively, I< ( s', s) holds if in situation s, the agent considers the situation s' to be possible. As in modal logic, knowledge is defined as truth in all accessible situations. And we define the following ab­ breviation:

where we assume that the situation argument has been re­ moved from the fluents in ¢> and ¢>[ s'] is the result of intro­ ducing s' as a new situation argument. Thus, for example, KNOW( ·Broken(x ), s) is an abbreviation for Vs' .I<(s', s) :J ·Broken(x, s'). For simplicity, we take I< to be transitive and Euclidean, which ensures that the agent always knows whether or not it knows something (i.e., the agent has the power of positive and negative introspection).

In Scher! and Levesque's treatment many actions affect knowledge in a particularly simple way: the agent knows that the action has been performed and thus comes to know that the action's preconditions must have held prior to its execu­ tion. Actions such as drop and repair are examples of such ac­ tions, which we call ordinary actions. Ordinary actions have a uniform effect on knowledge, and this effect can be captured by a single clause appearing in I<'s successor state axiom. Some actions, however, have effects on the agent's knowl­ edge that go beyond simple awareness of their execution, and we call such actions knowledge-producing actions. For ex­ ample, the agent might have available an action exactRead, whose effect is to change the agent's knowledge state so that it comes to know the exact distance to the wall in front of it.

For each knowledge-producing action we must have a clause in I<'s successor state axiom that characterizes its effect on the agent's knowledge. For example, if exact Read is the only knowledge-producing action, we end up with the following successor-state axiom for I<:

This entails

after doing exact Read , the agent knows the distance to the wall. To see this, consider the situations that are I< -related to do( exact Read , s), the successor of s. All such situations s' have the property that they are the successor states of some other situations" in which the distance to the wall is the same as it is in s. Since, exactRead does not change the distance to the wall, the successor-state axiom for wallDist ensures that wal!Dist( s') = wallDist( s"). Hence, all of the situations I<­ related to do( exact Read , s) have the same value for this flu­ ent, and our observation follows.

3 Sensors and Noise

One problem with the Scher! and Levesque account is that it is unrealistic to assume that an agent has available an exact Read action that allows it to learn the exact distance to the wall. A more realistic assumption is that the agent is in possession of a number of sensors, that give it some information about, but not exact knowledge of, various fluents. We expect a sen­ sor reading to be correlated with, but not a deterministic func­ tion of, the quantity being measured. For example, we might imagine that there is a sonar sensor that can be used to mea­ sure the distance to the nearest wall. There might also be a laser range finder used to measure the distance to the wall, but it might be correlated with the actual distance in a different way.

There are various ways of modeling this. We present one here, motivated by our desire to have the basic actions be de­ terministic (and thus preserve the simple solution to the frame problem). Assume we have an action of the form observe(x), that occurs whenever the agent observes reading x on the sonar. If we assume that the sonar reading is always within b units of the true distance to the wall (rather than being equal to the distance to the wall, as in the previous example), then we get the following precondition axiom: 4

If we now assume, as did Scher! and Levesque, that an agent learns that an action is possible by successfully performing it, it will follow that after an observe action, the agent will learn the distance to the wall to within b units. In other words, the Scherl and Levesque successor-state axiom for I< from the previous section entails Poss (observe( x), s) :J KNow(lwallDist- xl :S b, do( observe(x), s)), by an argu­ ment analogous to the one for exact Read, but now using the Poss predicate. In this case, with a precondition axiom as above, it is not necessary to treat observe, or similar observa­ tion actions from other sensors, any differently from ordinary actions such as drop and repair.

4 This particular precondition axiom only mentions the error bound, but other conditions can be included here as well.

Of course it is somewhat odd to say that the agent performs an action such as observe(3. 7), as if it had the choice of per­ forming, say, observe(3.6) instead. What we would prefer to say is that the agent decides to read the sonar, and that what happens is that 3.7 is observed.

This can be modeled by using a nondeterministic composi­ tion of the primitive observe( x) actions. We define a complex action read as follows:

Given the abbreviation Do defined above, this means that

Using the successor-state axiom for I<, we get the following:

So reading the sonar in s entails getting to a state where the agent has observed a (non-deterministically selected) consis­ tent sonar value x. Moreover, the agent knows in that state an appropriate bound on the true distance to the wall. It is easy to check that doing several consecutive sonar readings can increase the agent's knowledge about the true distance to the wall (i.e., tighten the interval that the agent knows con­ tains the true distance to the wall) and never decrease it. Sim­ ilar considerations apply to other sensors whose read actions would be defined analogously.

4 Probability

Suppose we have a sensor with an error bound of b = 2, and we make a number of readings of a particular fluent using the sensor, all of which are clustered around the value 3. For con­ creteness, suppose they are all between 2.8 and 3.1. As far as knowledge goes, all the agent will be able to conclude is that he knows the fluent to have a value in the range [1.1,4.8]. Get­ ting numerous readings of 3 will not change this knowledge. Yet, even if the agent is using a cheap sensor, we might hope that getting such readings would increase the agent's degree of belief that the true value of the fluent is very close to 3.

To formalize these intuitions, we introduce a probability distribution over the agent's set of I< -related states. In par­ ticular, we associate with each situation in this set a relative weight. Intuitively, the relative weight measures the degree to which the agent believes that situation to in fact be the real sit­ uation. However, it is convenient to avoid forcing this weight to be a probability; instead we only require that these weights be non-negative and that their sum over all of the J{ -related states be finite. To obtain a true probability, we will simply normalize these weights so that they do in fact sum to 1.

Syntactically, we introduce a new functional fluent p( s', s) whose value is the weight the agent assigns to situation s' when it is in situation s. This weight is unnormalized, and we introduce an abbreviation BEL(¢, s) to refer to the agent's probabilistic degrees of belief. Specifically, BEL(¢, s) is a number from 0 to 1 that is intended to stand for the agent's degree of belief in the assertion expressed by ¢, when it is in situations. As with KNOW, the first argument to BEL will be a formula containing fluents that are missing a situation argu­ ment, and we use the notation ¢[s'] as before for the formula that results when s' is introduced as the new situation argu­ ment. Informally, BEL(¢, s) will be defined to be the sum of the p weights of the accessible situations where ¢ holds, di­ vided by the sum of the p weights of all accessible situations:

These summations can be formalized within the situation cal­ culus. In conjunction with Equation 2 below, the logical con­ sequence of this formalization is that BEL is a probability dis­ tribution. The details of this development will be provided in a later full report on this work. For now, what matters is that we have something of the form

and that BEL(·, s) is a probability distribution over the situa­ tions I< -related to s.

To ensure that BEL is in fact a probability requires a con­ straint on the values of pin the initial state So. The following constraint must be added to the background theory T:

Since p is a fluent, we need to say how it is affected by ac­ tions. As with our treatment of every other fluent, we want to develop a successor-state axiom for p. Many actions will have only an indirect effect on the agent's beliefs; the agent will only come to know that the action was successfully per­ formed and this will affect its beliefs about the fluents changed by the action. For such actions, we want

This simply projects the relative degree of belief in s" to its successor s'.

Notice that in making the projection we are transferring the agent's beliefs to situations with different properties. (This is

5 This, of course, is an abbreviation for the formula

We continue to use such abbreviations below.

related to Lewis's notion of imaging [Lew76].) In these new situations, all of the changes due to action a have occurred. For example, say that approachW( x) is the action "move pre­ cisely x units towards the wall". In this case, the above equa­ tion will imply

Thus, if the agent believed it highly likely that she was 10 units from the wall in situation s, then she would believe it just as likely that she was 9 units from the wall after moving towards the wall 1 unit.

Things are a little more complicated when we have to deal with primitive actions like observe(x) . As we mentioned be­ fore, we do not really think of this as an action that the agent performs; the agent is actually performing the read action. Al­ though we have modeled read as a nondeterministic choice among observe( x) actions, it is actually better thought of as a probabilistic choice. Moreover, the probability of getting x as the reading depends on the situation and the accuracy of the sensor. In the simplest case, we would expect that in situation s, the smaller lwallDist(s)-xl is, the greater the probability of observe( x); the exact distribution, however, will depend on the sensor.

To make this precise, we propose that for every sensor i, there is a likelihood function f.;, where f.; ( x , s) denotes the probability of obtaining a reading of x from sensor i in situation s. Different applications will want to characterize these likelihood functions values differently, dependent on how complicated a model of sensor error is desired; here we simply assume that for each sensor i, the background theory T contains a sensor noise axiom characterizing each likelihood function, having the form

where r ; ( x, s) is a term whose value is always between 0 and 1, and is equal to 0 when X exceeds the error bounds Of the sensor (if there are any error bounds).

For example, we might want to say that the likelihood of getting a sonar reading of x depends only on the difference between x and the current wallDist, and that this difference, i.e., the sonar's noise, is normally distributed with mean 0 and standard deviation u . In this case, we would have an axiom of the form

where Normal( z) is a (discrete version of) the normal density function with mean 0 and standard deviation 1. This function could be defined in T by a simple table of values. 6

Given such a function, for a situation s' = do( observe( x), s") accessible from do(observe(x) , s), we want to weigh the degree of belief in s' by f. sonar ( x, s"). That is, we want

6 Here we are using the standard transformation: Normal((z + m) / u) is the density function of a normal distribution with mean m and standard deviation u.

More generally, if observe1, ... , observek are the only sens­ ing actions, then to get this property for these actions along with the one above for ordinary actions, we use the following general successor-state axiom for p , which we include as part of the background theory T:

where

This completes our formal characterization of adding prob­ ability to the situation calculus. So apart from the abbrevi­ ations noted above, we have exactly 3 situation calculus ax­ ioms: the Scher! and Levesque successor-state axiom for f{, a constraint on p in the initial state, and a successor-state ax­ iom for p.

5 Properties of the Formalization

Our formalization of noisy sensors in the situation calculus is extremely simple. We have modeled the agent reading its sensors as the execution of read, a nondeterministic choice among observe(x) actions. It would seem to be more appro­ priate to model read as a probabilistic action, since in each situation the probability of observe(x) varies with x. Proba­ bilistic actions have been explored in other works, e.g., the ap­ proach of Halpern and Tuttle [HT93]. Nevertheless, although we did not model read as a probabilistic action, the varying probabilities of its different nondeterministic outcomes are captured in our model. This is accomplished by the likelihood functions used in our definition of the successor-state axiom for p . In fact, we can show an exact correspondence between the probabilities over situations generated by our approach and those that would be generated by a probabilistic read ac­ tion using the framework of Halpern and Tuttle [HT93]. Fur­ thermore, as we show below, our formalism has a number of other appealing properties.

Observations. In our framework, it can be shown that the agent updates its beliefs after making an observation via standard Bayesian conditioning. First consider the standard Bayesian model of sensors.

The standard model assumes two pieces of probabilistic information: a prior distribution Pr(t) on the value t being sensed, and a conditional distribution Pr( x It) that gives us the probability of sensing x given that the true value is t . Fur­ thermo~e, the standard model requires the assumption that the value read from the sensor is dependent only on the true value, and is thus independent of other factors given this value.

Bayes' Rule is now applied to obtain a posterior probability Pr(t lx) over the values t given that the sensor read the value x: Pr(t!x) = Pr(x!t) Pr(t)j Pr(x) . The denominator is the only expression we do not know, but it can be easily com­ puted. Since :Z:::::t' Pr ( t'l x) = 1, we must take Pr ( x) to be the normalizing factor :Z:::::t' Pr(x!t') Pr(t'). The key factor is the numerator Pr(xjt) Pr(t) that describes the relative probabil­ ity of different values oft given the observation x.

If we make a similar set of assumptions in our framework we obtain exactly this probabilistic model of the effect of sens­ ing on the agent's beliefs. Let I be a set of sensor noise axioms of the form f; (x, s) = Err; (x , e; ( s) ), where e; is the fluent that is sensed by sensor i and Err; ( x, e) is some expression with just two free variables (both numeric), x and e. By us­ ing a sensor noise axiom of this form, we capture in the lan­ guage of the situation calculus the assumption that the proba­ bility of obtaining a reading of x from sensor i in situation s, i.e.,£; ( x, s), is dependent only on the value (ins) of the fluent being sensed. That is, no other properties of s affect this prob­ ability. In this case we get the following as a consequence:

Proposition 1 Let T be the background theory that includes the axioms given in Eq. 1-3. Then T U If=

. Again, the denominator here is simply a normalizing factor. If the sensor is informative, i.e., if it is more likely to read val­ ues closer to the true value than values further away, then this proposition ensures that the agent's beliefs about the fluent he is sensing will become sharpened about the sensed value.

Looking at things more generally, the probability of sens­ ing a particular value x could depend on many other features, not just the fluent's true value. For example, this probability could depend on the time the sensor was last calibrated. This generality is allowed for in our framework, as the likelihood functions £; ( x, s) can in general depend on complicated fea­ tures of the situations. Nevertheless, it is not difficult to see that an analogue of Proposition 1 still holds, and what is oc­ curing is simply Bayesian conditioning.

Example 5.1: Suppose that the agent is sensing the distance to the wall, wallDist, using a read of its sonar sensor. Let fsonar(x, s) = Err(x- wallDist(s)) . That is, not only do we assume that the sonar's error is dependent only on the true value of the fluent being sensed (assumption I above), but we also assume that this error is characterized by a simple noise model: the sonar reads the true value plus a noise component. Hence, the probability of obtaining the reading x given that the true value is wallDist( s) is a function of the difference be­ tween the two (i.e., a function of the noise). For definiteness, let Err(O) = 0.5, Err(-1) = 0.25, and Err(1) = 0.25. (Thus, the probability is zero that the sonar will read a value that is more than 1 unit away from the true value.) Let the agent's beliefs about wallDist in S0 , for y = 11, 12, 8, and 9, be BEL(wallDist = y, So) = 1/8, and BEL(wallDist = 10, So) = 1/2. Initially, the agent does not ascribe positive probability to any other possible value for the distance. This distribution of beliefs for the various values of wallDist in So are shown in Figure 1 .

Suppose that the agent reads its sonar and observes the value 11. In the new situation 51 = do(observe(ll), 50), a simple calculation using Equation 4 shows how the agent's be­ liefs have been altered. The new distribution is shown in the figure. Since the sonar has probability zero in being more than 1 unit away from the true value, the agent now has zero degree of belief in the values 8 and 9.7

Note that Figure 1 shows that the agent still believes that wallDist = 10 is the most likely value, even though its sonar returned the value 11. This arises from the agent's high prior belief in wallDist = 10. I

Sequences of sensor readings of the same fluent, including sequences of readings from different sensors, are also handled correctly in our framework. Such sequences correspond to se­ quences of sensing actions, and thus are handled by a simple iteration ofEq. 4. The independence of a sensor reading from all of the previous readings is implied by assumption I and by the fact that the sensors do not change the value being ob­ served (this is captured in the successor-state axiom for the sensed fluent) . As a result, after a sequence of sensing actions, the agent will come to have greater or less certainty about the value of the sensed fluent, dependent on whether or not these­ quence of readings agree or not.

Example 5.2 : Suppose that the agent executes another read action in the state 51 . Further, suppose that the agent observes the same value as before 11, and let 52 = do( observe(ll), Sl). Then, another application of Eq. 4 (ap­ plied to the agent's beliefs in sl ), yields the belief distribution shown in Figure 1. That is, the agent's beliefs have converged more tightly around the value 11, since it has now sensed that value twice. I

This example of sensor fusion is simplified by the discrete nature of the agent's initial beliefs and likelihood function. Nevertheless, more practical models are easily accommo­ dated. For example, if the agent's initial beliefs about wallDist are characterized by a Gaussian, and the sensor yields a linear transform of wallDist plus some. Gaussian noise factor, then the agent's beliefs about wallDist after doing some sequence of observations will continue to be characterized by a Gaus­ sian. Furthermore, the mean and variance of this Gaussian can easily be computed. 8

Actions. As mentioned briefly in the previous section, the manner in which probability mass is transferred when ordi­ nary actions like approachW also yields appropriate changes to the agent's beliefs.

Example 5.3 : Suppose that the agent is in state 52 , and then moves exactly 2 units closer to the wall. Let S3 =

7 If the agent knows these error bounds, i.e., if these bounds are part of the preconditions for the sonar, it will come to know that wallDist is in the range 10-11. On the other hand, if the agent only has zero degree of belief in these outcomes, it will come to believe with degree 1 that wallDist is in that range. That is, our framework can distinguish between full belief and knowledge.

8 This corresponds to a trivial case of Kalman filtering, where the value being sensed is static [DW91].

do(approachW(2), 52). Then, the successor-state axiom for p and wallDist imply that the agent's beliefs are shifted to worlds in which it is 2 units closer to the wall. Hence, for all y, BEL(wallDist = y- 2, S3) = BEL(wallDist = y, 52). The agent's shifted beliefs are shown in Figure 1. This is ex­ actly how one would expect the agent's beliefs to change after moving closer to the wall. I

Furthermore, changes in the agent's beliefs due to ordinary actions integrate correctly with sensing actions.

Example 5.4 : Suppose that the agent again executes a read action in 53 and observes the value 9. Let S4 do( observe(9), 53 ) . This reading is consistent with its previ­ ous readings of 11 since the agent has moved 2 units closer to the wall. Hence, as shown in Figure 1, it results in a further tightening of the agent's beliefs, around the value 9. If the agent subsequently moves back from the wall by 2 units, executing an approachW( -2) action, so that 55 = do( approachW(-2), 54), its beliefs will then be clustered around 11, as shown on the figure.

Intuitively, since the agent's approachW action incurs no error, we would expect that if the agent had sensed the value 11 in situation s2, then its beliefs about the distance to the wall should not change after moving forwards and backwards an equal distance. Our model respects this intuition, as indicated in the figure by the diagonal arrow from S2 to Ss. I

Finally, we can observe that if the agent executes an action that has no effect on a particular fluent, then that action will cause no change in the agent's beliefs about that fluent. For example, if the agent executes a drop action that has no effect on its distance to the wall, it will have exactly the same be­ liefs about the distance to the wall in the successor state. This again arises from the direct transfer of probability mass to the successor states, all of which have exactly the same distance to the wall as before.

6 Conclusion

We have demonstrated that noisy perception can be modeled in the situation calculus by a simple extension of previous work. Although the resulting formalism is limited in some ways, e.g., currently we do not handle noisy effectors, it does succeed in providing an interesting integration of noisy per­ ception and ordinary actions. In particular, from the succes­ sor state axiom for p, Eq. 3, and a constraint on its values in S0 , Eq. 2, we obtain as consequences what many have argued to be the natural models for belief update from per­ ception (Bayesian conditioning) and from actions (a form of Lewis's imaging) [Pea95]. Most importantly, our formalism succeeds in capturing some key features of the interaction be­ tween these two models for belief change.

Much of our approach can be exported to alternate for­ malisms. For example, instead of the situation calculus a modal logic could have been used. Similarly, the probabilis­ tic component could be replaced with an alternate formalism, like Dempster-Shafer belief functions [Sha76] or possibility measures [DP88] . All that would be required is to replace the functional fluent p and axioms for BEL with fluents and ax­ ioms to support an alternate measure of belief. The likelihood functions could then be replaced with non-probabilistic func­ tions to support an alternate rule of belief update.

As for future work, apart from addressing limitations of the formalism, there is its application in high-level agent control. In the GO LOG work mentioned in the introduction, the ability of an agent to execute a program depends on what it knows about the truth value of the test conditions in that program [LLLS95] . When an agent only has a degree of belief in the truth of a test condition in a program, it is much less clear what it ought to do. A suitable programming formalism in this case remains to be developed.