Qualitative Reasoning about Perception and Belief

1 Introduction

A great deal of attention in AI has been devoted to modeling states of information, whether qualitatively through , e.g., logics of knowledge and belief (cf. [Moore, 1985; Konolige, 1986; Fagin et al., 1995]), or quantita­ tively. In contrast, relatively little attention has been paid to modeling information sources, on the basis of which the various information states are reached. In particular, there has been very little work on the re­ lationship between belief and perception, the most com­ mon source of information in everyday life. This is the topic of this paper. (We hasten to add that there cer­ tainly has been some work on this topic in AI , notably

·This work performed at Stanford University's Computer Science Department .

1This work partly supported by a National Physical Sci­ ence Consortium Fellowship.

Yoav Shoham

Computer Science Department Stanford University Stanford, CA 94305

shohamOcs.stanford.edu

by Davis [1989] and Bacchus, et al. [1995]; we discuss this work in section 5.)

The connection between belief and perception is multi­ faceted . Here we concentrate on a particular set of is­ sues, namely, the precision and accuracy of percepts and of sensors that generate them. This distinction is impor­ tant but easily glossed over; we discuss it in detail in the next section.

The contributions of this paper are as follows:

• A qualitative model of precision and accuracy.
• A logic with which to reason about certain aspects of the model. The logic contains three different but related modalities: P (for actual perception) , Cp (for the set of possible percepts), and B (for belief) . They are each defined in what by now is a standard fashion , but the combination is novel.
• A category of agent types, each defined both ax­ iomatically and model-theoretically; the types differ either on the relationship between the agent's per­ cepts and the world, or (and this is the most inter­ esting case) on the relationship between the agent's percepts and his beliefs.
• Completeness results , relating the axiomatic sys­ tems and the semantic models.

The paper is organized as follows . In section 2 we present our model of precision and accuracy, and ex­ plain it with examples. In section 3 we present the logic CPO for modeling and reasoning about perception, and present our first completeness result . We also define the first two types of agent, accurate and observant. In sec­ tion 4 we present the logic BCPO for modeling and rea­ soning about perception and belief, and present many more agent types. We provide completeness results for BCPO as well as for the various agent types. We discuss related work in section 5, and make some concluding re­ marks in section 6.

2 Qualitative model of accuracy and preciSIOn

Our starting point is a distinction between precision and accuracy, both between the precision and accuracy of a particular percept, and the precision and accuracy of a sensor.

We illustrate these notions through an example. Con­ sider a sensor that is supposed to detect the location of an object on the real line. A percept (or reading) of this sensor would be some interval such as [1, 7], meaning that the object is somewhere in that interval. Let's denote this percept by P1 . Another percept might be P2 = [3, 5] . In this case P2 is said to be more precise than P1. Sup­ pose that the actual location is 2; then P1 is said to be more accurate than P2 since P1 is right and P2 is wrong. Now consider P3 = [3, 4]. Clearly P3 is more precise than P2, but which of them is more accurate? The intuitive answer is not obvious, since they are both wrong, but in our model P3 will come out more accurate. Intuitively, P2 allows locations that are "more wrong" than does P3. Note that in order to capture "more wrong" we need to appeal to the notion of a "similarity ordering" -which of two points are closer to a third- but not necessarily an exact metric specifying the distance between two points.

The three example percepts discussed so far are re­ lated by set inclusion, but now consider P4 = [4, 6]; is it more or less precise than P2? The answer depends on whether we can appeal to metric properties or not . If we can then we can judge the two percepts equally precise. However, since we wish to capture qualitative notions, in our model the precisions of P2 and P4 will come out as non-comparable. But what about their accuracies? In our model P2 will come out as more accurate; the intuition is again that P4 allows locations that are even more wrong than does P2 .

Let us now begin to develop · a formal model; in the following definitions assume a set S (of worlds) .

Definition 1 A percept is a subset of S.

Definition 2 Percept X is said to be as precise as per­ cept Y iff X ~ Y.

Definition 3 Percept X is accurate at s E S , abbrevi­ ated s-accurate, iff s E X .

Definition 4 ·Given a set of allowable percepts A , per­ cept X is as accurate as percept Y at s E S wrt A iff VZ E A , if s E Z andY~ Z then X~ Z.

Thus X is as accurate as Y iff every accurate percept which includes Y must also include X. This definition is intuitive but often quite weak. Therefore we consider ways to impose more structure upon possible percep­ tions, in particular a notion of "convexity" of the space derived from a similarity preorder.

Definition 5 A similarity ordering on S at s E S is a binary relation ::;.~ S x S ; the intuitive reading of ::;. (s1, s2), which we abbreviate s 1 ::;. S:J , is "s 1 is at least as close as s2 to s ". <. denotes the strict version of::; ·. We requi·re that::;. be a preorder {that is, reflexive and transitive), and that if s # s' then s <, s'.

Definition 6 Given ::;. as above, pe·rcept X is convex at s E S, abbreviated s-convex, iffVx , y E X, if x :Ss z ::;. y then z E X. A set of percepts A is s-convex iff every X E A is s-convex.

Definition 7 The accurate extension of a percept X at s E Sis the percept x+(s) = {y E 5 i3x EX : y ::;. x}.

Definition 8 A set of pe1·cepts A is strongly s-convex iff A is convex and VX E A : x+(s) EA.

Proposition 1 x+(s) iss-convex and s-accurate, and for any s-convex and s-accurate percept Z E A, if X ~ Z then x+ ~ z.

In the following propositions, assume A to be· strongly s-convex and X, Y EA.

Proposition 2 X is as accurate as Y at s E S wrt A iff x+(s) ~ y+(s).

Proposition 3 X is as accurate as Y at s wrt A iff Vx EX 3y E Y : x ::;. y.

Proposition 4 Let :Ss be a total preorder. X is as ac­ curate as Y at s E S wrt A iff sup(X) ::;. sup(Y), where sup( Z) is an element of set Z that is a least upper bound wrt ::;, .

Under the assumptions of this last proposition, therefore, the relation "being as accurate as" is a total preorder. Also, if A is convex but not strongly convex, then the right hand sides of these three propositions are sufficient but not necessary for X to be as accurate as Y .

So far we have discussed the relative precision and ac­ curacy of percepts; let us now turn to comparing sensors. We model a sensor by its perceptual capabilities, which, loosely speaking, means the set of percepts it is capable of delivering in any particular circumstance. Because sensors represent sets of percepts, their relative preci­ sion and accuracy can be defined in a variety of ways depending on the application. Two possibilities are as follows : (1) Sensor A is considered more precise/accurate than sensor B in some situation if every percept of which sensor A is capable is more precise/accurate than some percept sensor B could deliver. (2) Sensor A is more pre­ cise/accurate than sensor B in a situation if every per­ cept sensor A could return is more precise/accurate than any percept sensor B could return. The first case cor­ responds to a comparison of the worst case scenarios of the two sensors, whereas the second case corresponds to a guarantee on the relative precision/ accuracy of the per­ cepts actually returned. The second is obviously more restrictive, and implies the first .

Again, we illustrate these notions through an example. We will also demonstrate that not only can a given sen­ sor's capabilities change with the world, but so can the relative relationship between the capabilities of different sensors. Consider two sensors, A and B, which report on the location of some object on a line. Imagine the two sensors as located on another line (the baseline) parallel to the line the object is on (see Figure 1) .

The capabilities of sensor x (where x is A or B) are characterized by two parameters, ax and !x. ax is the angle of resolution of sensor x, whereas /x is the max­ imum angle of divergence between the orientation im­ plied by the particular reading and the sensor's actual orientation. Given these parameters, the distance of the baseline from the real line, and the location and orien­ tation of sensor x , we can compute 8x, the size of the interval it returns, and fx , the maximum displacement of the reading from the true interval. (We assume that /x is small enough compared to ax that the variation in interval length due to /x is negligible.) Let us suppose that O'B < O'A and /B < /A·

The object's location determines the world, and at a world each sensor returns one percept. To determine the percept it returns at a world, sensor A maintains a fixed orientation perpendicular to the real line, and travels back and forth along the baseline, periodically taking a reading until the object appears in its vision. Because its orientation is constant (within !A) , both oA and fA are constant. Imagine, however, that it is more expensive for sensor B to move around, so instead it remains in one location and varies its orientation by rotating, ran­ domly sampling the real line until the object appears in its vision. In this case both 88 and fB vary with the sensor's orientation, so both its accuracy and precision decrease the farther away the object is.

Thus the specific set of possible percepts which sensor x might deliver when the object is located at l consists of the intervals [r, r + 8x] for alii- 8x - fx ~ r ~ l + fx

(corresponding to the extreme cases where the the inter­ val is fx to the left and right of the object , respectively) for r E ~ (the real numbers) . Consider the world where the object is located directly in front of sensor B. Sensor B is more precise than sensor A because all the percepts sensor B might return are more precise than all those sensor A might return. It is also more accurate (under the worst-case interpretation) than sensor A because the least accurate percept it is capable of is more accurate than some of sensor A's possible percepts.

Now suppose the object is far away from sensor B. The size of the interval returned by sensor B and the magnitude of its maximum displacement. will be much larger. In this case sensor B will be both less precise and less accurate (in the worst case) than sensor A because it will have possible percepts that are less precise and less accurate than all the percepts sensor A might return.

The definitions below extend our framework to include sensors. Assume a set of allowable percepts A as before.

Definition 9 A sensor is a function f : S -+ 2 25 that describes the set of possible percepts in a world.

Definition 10 Sensor f is worst-case as precise as sen­ sor f' at s E S iffVX E f(s) 3Y E f'(s) s.t. X is as precise as Y at s. It is guaranteed as precise as sensor f' at s wrt A iffVX E f(s) VY E f'(s), X is as precise as Y at s wrt A .

Definition 11 Sensor f is worst-case as accurate as sensor f' at s E S wrt A iffVX E f(s) 3Y E /'(s) s.t. X is as accurate as Y at s wrt A. It is guaranteed as ac­ curate as sensor f' at s wrt A iffVX E f(s) VY E /'(s), X is as accurate as Y at s wrt A .

3 A logic for perception

We now aim to construct a logic with which to reason about these aspects of perception. As the above discus­ sion illustrates, at a basic level reasoning about percep­ tion involves the counterfactual notion of what could be perceived, and it is this notion we will concentrate on. We capture it formally by introducing a logic with two modal operators , P and Cp , which represent actual per­ ception and possible perception, respectively.

This gives us a way to capture the perceptual limita­ tions of an agent . Next we want to represent the degree to which the agent is aware of these limitations. What an agent believes given some percept may depend on the agent's level of trust in the reliability of her sen­ sors, which in turn may depend to some degree on the actual percepts themselves. To be able to describe com­ plex interactions of this sort between the agent's mental state and her perceptions and possible perceptions, we also add to the formalism a modal operator, B , for be­ lief. We then use this model to define several agent types with various interesting perceptual-belief characteristics.

3.1 The logic CPO

The formulas of the language £ are obtained by closing a set of propositional symbols under the boolean connec­ tives, and under the operators P and Cp. Intuitively P¢ means "the agent perceives ¢", where ¢is some arbitrary formula. Cpc/> indicates that "the agent can perceive ¢" , meaning that her perceptual apparatus could have pro­ duced a percept that validates ¢ . We also ensure, of course, that what is perceived can be perceived .

For semantics , we define a P-structure as a tuple M = (5, N, I, 11') where S is a set of states or worlds, 71' is a truth assignment 71' : S -+ 2.c , N is a relation N : S -+ 2 25 mapping each world to a set of sets of worlds, and 1 is an accessibility relation I : S -+ 2 5 mapping each world to a set of worlds.

The satisfaction relation is defined as usual. Only the truth conditions for the operators P and Cp are of inter­ est. They are:

Thus P uses the standard semantics for necessity oper­ ators in modal logic, whereas Cp uses a variant of neigh­ borhood (or minimal model) semantics [Chellas, 1980]. ForsE S, we use the notation N(s) ={X ~ S I (s, X) E N}, and I(s) = {t E S I (s , t) E I}. The idea is that N(s) represents the set of possible percepts at a world, and the set A of allowable percepts referred to in the pre­ vious section includes all these possible percepts from all worlds. In a domain that is strongly s-convex, A would also include all the accurate extensions of these percepts, although these extensions may not be actually perceiv­ able from any world .

We are interested in the class M c p of P-structures for perception satisfying the following conditions:

Condition (CP3) is the most interesting one. It re­ quires every actual percept to be a possible percept, and corresponds to axiom A4 below. (CPl) and (CP2) cor­ respond , in turn, to axioms A2 and A3, respectively.

Let CPO be the following set of axioms and rules of inference:

Al. All tautologies of propositional calculus.

A2. Cptrue

A3. ·Cvfalse

A4. P¢ :J Cv¢>

A5. (P'Ij! 1\ P( 1/1 :J ¢)) :J P¢>.

Rl. From 1/J and 1/J :J ¢ infer¢.

R2 . From 1/J :J ¢infer Cp .,P :J C'p¢·

R3. From 1/; infer P lj;.

Theorem 1 CPO is a sound and complete ax·iomati::a­ tion of the class M c p of ?-structures for perception.

Proposition 5 These formulas are valid in .M cp:

1. Cv(¢> 1\ 1/;) :J (Cpc/> 1\ Cp.,P). 2 . ...,p fal se.

Thus CPO includes only some weak consistency condi­ tions on Cp, namely A2 and A3, and on P, in addition to the aforementioned restriction that actual percepts must be possible percepts. On the other hand, the system does not sanction the axiom {Cp 1/J 1\ Cp¢) :J Cp ( 1/J 1\ ¢>): for ex­ ample, it may be possible for me to perceive some object as either blue or red depending on lightning conditions , but this does not mean that I can perceive the object as both red and blue.

3.2 Accurate and observant agents

Various agent types can be defined to capture varying assumptions about the application domain. Most defi­ nitions refer to the relationship between perception and belief, a topic we have not yet addressed. However, some types are defined in terms of the relationship between perception and objective facts in the world, independent of the belief modality. Thus we give them here.

We first consider observant agents, those from whose perception nothing escapes. Formally, the agent is said to be observant if the following schema is valid :

Similarly, the agent is said to be accurate if the schema

is valid .

The schema corresponding to the observant agent is clearly very strong, unlikely to be applicable to agents in more complex environments, since nothing perceptu­ ally escapes the agent . Yet it is possible to think of simple agents for which it makes sense, such as, for ex­ ample, a device continuously and accurately monitoring some variable, and whose model of the world consists exclusively of the possible values the variable can take.

We can also consider similar properties for the C'p modality. The agent is potentially observant iff she can perceive any (true) fact, i.e. iff the following schema is valid :

An agent is said to be necessarily accurate, on the other hand, if anything she can perceive is true, i.e. iff the following schema is valid:

4 A logic for perception and belief

We are now interested in what the agent should be­ lieve, given what she perceives. It might be tempting to make the assumption that anything perceived is also believed. However , in (common) cases where the sen­ sors might not be completely accurate, and in which the agent might know this, the assumption would be inap­ propriate. Sometimes the converse assumption is more adequate: one doesn't believe in anything without hav­ ing perceived it. Keeping this in mind, we begin with the most general case, in which the relation between percep­ tion and belief is unconstrained, and which can be cap­ tured in a straightforward manner. We will then identify a number of special cases with further properties.

4.1 The logic BCPO

We expand CPO to include an operator B. A PB­ structure is a tuple M = (5, N, I , R, rr), where 5, N, and I and rr are as before (in particular (CP1)- (CP3) are satisfied), and R is a serial, transitive and Euclidean relation over 5. That is, we are characterizing belief with the standard KD45 system. In addition, we require the agent to be aware of her perceptions, by imposing the following semantic condition (which corresponds to axioms AlO and All below) :

Let M BC p be the class of such structures. The se­ mantics of the B operator are given as usual by:

The system BCPO consists of all the axioms and rules of CPO together with:

A6. (Bl/; 1\ B( l/; =:> ¢)) =:> B¢.

A8. Bl/; =:> BE¢.

AlO. Pl/; =:> BPl/;.

R4. From '1/J infer B lj;.

The following result should be obvious:

Proposition 6 BCPO is a sound and complete axiom­ atization of the class MBcP of PB-structures for per­ ceptzon and belief.

Note that the formula BPl/; = Pl/; follows from AlO and All, and is therefore a theorem ofBCPO. Although one can easily think of counterexamples, e.g. ambient noise, or sensory overload, where percepts are filtered out so that the agent is not aware of what she is perceiving, we have elected to adopt_ this assumption to simplify the remaining discussion . It is easy to weaken the formalism to deal with this situation if desired.

Given this logic, we can make additional inferences about perception and belief. For example, the formula

\ is valid in BCPI'J .. We can read this as saying that if the agent perceives ¢ and she believes she could not have perceived that in a world in which 1/J holds , then she be­ lieves that 1/; is false. We can obtain stronger results by imposing additional conditions on the agent. This moti- · vates the definition of a number of agent types according to the connections between the various modalities. We do this in the next section.

4.2 More agent types

By placing additionaljoint restrictions on I , N , and R, it is possible to capture different ways in which perceptions and perceptual capabilities can be related to the agent's beliefs and to the environment. There are a number of basic dimensions to. consider. In a previous section we appealed to the relationship between perception and the environment in defining the accurate and observant agents, and also between perceptual capabilities and the environment; we also decided to build into the logic the introspect ive abilities of the agent with respect to per­ ception through axioms AlO and All. In addition we may now consider the introspect ive abilities of the agent with respect to her perceptual capabilities, and the con­ fidence that the agent places in her perceptions. As was discussed in the previous section, a third dimension- the correctness of the agent 's beliefs about her percept ions­ is built into the logic. Table 1 defines the various agent types along these dimensions in terms of the validity of certain (not necessarily independent) axiom schemas, and Table 2 identifies certain classes of PB-structures for perception and belief in terms of restrictions on I, N, and R. The correspondence between the axiom schemas and the corresponding classes of structures is given in the soundness and completeness results in the next the­ orem, where BCPO+i refers to the system composed of BCPO and the ith axiom schema in Table 1.

Theorem 2 BCPO + 1 (respectively + 2, + 3 1 , + 4, + 5, + 6, + 7, + 8, + 9) is a sound and complete axiomatization of the class of PB­ structures for perception and belief M observant (re­ spectively Maccurate, M cp-observant, M cp- accurate, M cp-aware(+)> M cp- aware(- )> M conjident , M cautious, M sib)

1 The completeness proof for the potentially observant agent assumes a finite propositional vocabulary.

5 Related work

There has been relatively little work relating perception and belief; here are the closest of which we are aware.

First, related to our paper is Davis' earlier work [Davis, 1989] on belief and perceptual acuity. Davis' work, however, like some other work in related fields (cf., [Parikh, 1983]), is firmly based on modeling met­ ric spaces, and is thus quantitative in nature. Davis' logic contains only notions analogous to our P and B, and does not have a way of specifying the perceptual capabilities of the sensor. He was thus not able to differ­ entiate in the logic between precision and accuracy, and ran into some paradoxes as a result.

Recently, Bacchus, et al. (1995] have worked on repre­ senting the effects of readings from noisy sensors on the belief state and subsequent actions of agents. They em­ ploy a formalism that combines a probabilistic definition of belief with a situation calculus framework. However, our approach, . while remaining amenable to probabilis­ tic extensions, is able to capture qualitative effects of perception as well. Their work also does not address preCISIOn.

6 Discussion

We have presented a formalism to reason about percep­ tion and belief, an under-explored area of investigation. We started by distinguishing between precision and accuracy, notions that are often conflated. We proposed what to our knowledge is the first qualitative definition of these notions.

We then provided a model in which to represent an agent's perceptions and beliefs, and a logic with which to reason about the model. We explored possible relations between an agent's perceptions, perceptual capabilities, and beliefs, and between these and the environment . Be­ cause no type of agent among those defined is likely to be useful in all scenarios, we have mentioned some cir­ cumstances in which different types might be used.

The formalism we have presented seems natural and well-behaved, but more research is needed on applying it, whether in general formulations of common-sense rea­ soning or in more specific applications. It would also be interesting to study extensions of the language that incorporate more specific domain structure (such as a metric space), and relate them to perceptual indistin­ guishability. Temporal and multi-agent aspects are also of interest, as well as the problem of updating the beliefs of the agent in the light of perceptually acquired informa­ tion. Indeed, we view sensors as a source of information, and precision/ accuracy as measures of that source's com­ petence. We intend to apply this theory more generally to reason about multiple, partially-trusted information sources.

Acknowledgements We would like to thank the mem­ bers of the Nobots research group at Stanford Univer­ sity for their helpful comments, as well as the referees for constructive critique on the paper.