A nonmonotonic observation logic.
A variant of Reiter's default logic is proposed as a logic for reasoning with (defeasible) observations. Traditionally, default rules are assumed to represent generic information and the facts are assumed to represent specific information about the situation, but in this paper, the specific information derives from defeasible observations represented by (normal free) default rules, and the facts represent (hard) background knowledge. Whenever the evidence underlying some observation is more refined than the evidence underlying another observation, this is modelled by means of a priority between the default rules representing the observations. We thus arrive at an interpretation of prioritized normal free default logic as an observation logic, and we propose a semantics for this observation logic. Finally, we discuss how the proposed observation logic relates to the multiple extension problem and the problem of sensor fusion.
Introduction
In this paper we propose a variant of Reiter's default logic [8] as a logic for reasoning
with (defeasible) observations. A default theory consists of a set of facts and a set of
default rules. Traditionally, default rules are assumed to represent general, or generic,
information, such as 'typically, birds fly' and the facts are assumed to represent specific
information about the situation, such as 'Tweety is a bird'. However, in this
paper we consider the case where the specific information derives from defeasible ob-
servations, and the general information denotes (hard) background knowledge. These
The investigations were carried out as part of the PIONIER-project Reasoning with Uncertainty,
subsidized by the Netherlands Organization of Scientific Research (NWO), under grant pgs-22-262.
characteristics apply, for example, to the situation of an autonomous robot navigating
through an environment using an a priori given map and its not completely reliable
sensors.
The nonmonotonic logic proposed in this paper is motivated by the logic of vision
proposed in [5], where perception reports are interpreted in inverse systems of first-order
models approximating reality. A perception of OE is modelled as the truth of
OE given some approximation plus a defeasible expectation that OE will also be true in
more refined approximations. Perceptions based on more refined evidence can defeat
this expectation.
We abstract from the particular language of [5] and propose prioritized normal free
default logic for reasoning with defeasible observations. Each observation is modelled
by a normal free default rule, i.e., a default rule which has a single justification
equivalent to its consequent and a tautology as prerequisite. To take account of
the fact that an observation can be defeated by another observation based on more
refined evidence, we add a preference order on the default rules.
The remainder of this paper is organized as follows. In sections 2 and 3, we
briefly review some basic properties of default logic, and in particular of the special
case where default rules are normal and free. In section 4, we describe how normal
priorities between default rules can be interpreted as a logic
for defeasible observations. A semantics for this observation logic is then presented
in section 5. Finally, we discuss how the proposed observation logic relates to the
multiple extension problem and the problem of sensor fusion.
We repeat some definitions and results (without proof) from [8]. Let L be some
ordinary first-order language, and let Th denote an ordinary first-order consequence
operation for that language. (The dependence on L and Th of the definitions and
results below will mostly remain implicit.) Formulas of L are denoted by ff; In
examples, propositional letters are used, which are supposed to be included in
the language.
rule is an expression of the form:
The formula ff is called the prerequisite, fi are called the justifications, and !
the consequent of the default rule. A default rule is called closed iff all the formulas
appearing in the rule are closed. If D is a set of default rules, then CONSEQ(D)
denotes the set of consequents of the default rules of D.
The default rule ff : has the following intended meaning: If ff can
be derived and each of the consistent with what is derivable, then derive
!. (This is the standard interpretation. Our interpretation of the default rules
representing observations will be slightly different. See section 7.)
theory D is a pair hD; \Gammai, where D is a set of default rules
and \Gamma is a set of sentences of L. A default theory is called closed iff all its default
rules are closed.
Definition 3 An extension of the closed default theory hD; \Gammai is a fixed point of the
(\Sigma) is the smallest set such that
An extension of a default theory hD; \Gammai is intended to represent a reasonable state
of belief based on the default rules in D and facts in \Gamma. Below, we give a more
informal characterization of default extensions, which is essentially a reformulation of
the semantics for default logic given in [3]
Let \Sigma be a logically closed set of sentences of L. The default rule ff :
is called applicable in \Sigma iff ff 2 fi 1 and for every fi i , :fi i 62 \Sigma. If
is applicable in \Sigma, then the result of applying d to \Sigma is the set Th(\Sigma [ f!g). An
extension E of a closed default theory hD; \Gammai is the result of sequentially applying
to Th(\Gamma) the default rules of a subset D 0 of D such that every default rule of D 0 is
applicable in E, and E contains the consequent of each default rule applicable in E.
D 0 is called the set of generating default rules of E.
A default theory may have more than one extension, and there exist default theories
without extensions. For example, has two extensions,
namely Th(fpg) and Th(f:pg), and hf? : :p=pg; ;i does not have an extension.
So far, we have only defined the notion of extension for closed default theories.
In general, the extensions of a default theory hD; \Gammai are defined to be the extensions
of the closed default theory hD roughly speaking, D 0 is obtained from D
by taking all closed instances of D. (See [8, 10] for details.) From now on, we will
assume, without loss of generality, that default theories are closed.
We have seen that not every default theory has an extension. However, there is a
natural class of default theories with at least one extension:
Definition 4 A default rule is called normal iff it has a single justification and this
justification is equivalent (in first-order logic) to its consequent. A default theory is
called normal iff all its default rules are normal.
Proposition 1 (existence of extensions) Every normal default theory has an extension

In addition to having at least one extension, a normal default theory has several
other nice properties. Some of these properties are listed below. None of the listed
properties holds for arbitrary default theories.
Proposition 2 (orthogonality of extensions) If E and F are distinct extensions
of a normal default theory, then E [ F is inconsistent.
Proposition 3 (uniqueness of extensions) If hD; \Gammai is a normal default theory
has a unique extension.
Proposition 4 (semi-monotonicity) Let D and D 0 be sets of normal defaults such
that D ' D 0 , and let E be an extension of hD; \Gammai. Then hD has an extension
3 Free Default Logic
In this section, we consider a fragment of default logic in which the prerequisite of a
default rule is assumed to be a tautology. Such a rule is called (prerequisite-)free.
Definition 5 A default rule is called its prerequisite is a tautology (in first-order
logic). A default theory is called its default rules are free.
Free default theories have been studied in [1, 9, 10]. (In [1] the free default rules
are also assumed to be normal, which is the case we are especially interested in.)
In [9, 10] it is argued that rational agents adhering to Savage's `sure-thing principle'
should be willing to replace arbitrary default rules by free default rules. In general,
the resulting default theory will not be equivalent to the original one. However, it is
not hard to show that any default theory is equivalent to a free default theory.
An advantage of free default logic is that it allows reasoning by cases.
Example 1 Let ;i. The default theory D does not allow the
obvious conclusion q since its unique extension is Th(;). In [9, 10] it is proposed to
replace D by hf? which has the unique extension
Th(fqg).
In this paper, we are interested in normal free default logic, which is a particularly
well-behaved fragment of default logic. For example, the extensions of normal free
default theories have a relatively simple characterization.
Proposition 5 Let be a normal free default theory. Then E is an extension
of D iff such that
Proof. The result immediately follows from the informal characterization of extensions
given in section 2 and from the fact that a normal free
applicable in \Sigma iff \Sigma [ f!g is consistent.
Corollary 6 If is a normal free default theory and E is an extension of
D, then E is complete with respect to CONSEQ(D). That is, if
then either
Another interesting property of normal free default logic is that it induces a cumulative
consequence operation. The fact that the consequence operation induced by
unrestricted default logic is not cumulative has been considered a drawback of default
logic, and several authors have looked at ways to modify default logic to make its
consequence operation cumulative.
is called a cumulative consequence operation
for L iff it satisfies the following four properties, for arbitrary \Gamma; \Delta ' L.
Th-invariance
cumulative
cumulative
Definition 7 For any set D of default rules and for any set \Gamma of sentences of L,
define CnD is an extension of hD; \Gammaig.
CnD (\Gamma) is the set of sceptical, or cautious, conclusions of hD; \Gammai. It is shown in [6]
that for arbitrary normal default rules CnD does not satisfy cumulative monotonicity.
However, this property does hold if one additionally assumes the default rules to be
free.
Proposition 7 Let D be a set of normal free default rules. Then CnD is a cumulative
consequence operation for L.
Proof. That CnD satisfies inclusion and Th-invariance is immediate. In [6] it is
shown that CnD satisfies cumulative transitivity (even without assuming the defaults
of D to be normal and free). To prove cumulative monotonicity, assume that \Gamma '
(\Gamma), and that E is an extension of hD; \Deltai. It is sufficient to show that E is
also an extension of hD; \Gammai.
By proposition 5, such that
Let D 00 ' D 0 be a maximal subset of D such that \Gamma [ CONSEQ(D 00 ) is consistent.
is an extension of hD; \Gammai. We have
since otherwise there would
be a default rule in D 00 \Gamma D 0 such that its consequent is consistent with E, but not
included in E. It follows that E is also an extension of hD; \Gammai.
In the following section, we argue that an prioritized version of normal
logic can be interpreted as a logic for defeasible observations.
Consider a robot making an observation. In order to (symbolically) reason with the
observation, the subsymbolic information acquired by the sensors has to be translated
into a symbolic language. We assume that the observation systems of the robot
translate the raw sensory data into propositions expressed in a first-order language
L. Each observation is based on evidence which is limited in range and resolution,
and which is therefore only directly related to (part of) an approximation of reality.
An observation induces an expectation that what is observed will also hold for more
refined approximations, but this expectation can be defeated by observations based
on more refined evidence.
Let OE e denote the observation that OE based on evidence e. We can interpret this,
analogous to the rendition of perception reports in [5], as OE being true given the
approximation of reality induced by e plus a defeasible expectation that OE will also
be true in more refined approximations, including reality itself. For example, assume
we have the observations OE e and / e 0 , where OE and / are incompatible (given the a
priori knowledge) and e 0 is more refined than e. Then the expectation induced by OE e
is defeated by / e 0 .
The (defeasible) expectation accompanying the observation OE e intuitively seems
to imply the (normal) default rules OE e : OE e 0 =OE e 0 , for each e 0 that is more refined than
e. Since these default rules are only added to the theory when also the prerequisite
OE e is added, one can use the normal free In the case
of the observations OE e and / e 0 , where OE and / are incompatible and e 0 is more refined
than e, it then is clear that the expectation of OE e is blocked by the truth of / at the
approximation of reality induced by e 0 .
If we abstract in our formal language from the evidence on which the observation
is based, then an observation can simply be modelled as a normal free
OE=OE. To properly capture the interaction of different observations, one can mirror the
relation between the underlying bodies of evidence in an ordering on the corresponding
default rules.
prioritized default theory is a triple hD; \Gamma; !i, where hD; \Gammai is a
default theory and ! is a well-founded strict partial order on D. (That is, ! is an
irreflexive, transitive relation with no infinite descending chain
Definition 9 An observation theory is a prioritized normal free default theory.
If d and d 0 are default rules, then the intended meaning of d ! d 0 is that d is
stronger than d 0 because d represents an observation based on evidence which is more
refined than the evidence on which the observation represented by d 0 is based. (This
reading of ! is in accordance with the usually chosen direction of prefence relations
in preferential semantics, where the preferred models are traditionally called minimal
models. Unfortunately, if one has the context of information orderings in mind, then
it is natural to expect the reverse reading.)
The assumption of ! being well-founded is necessary for the definitions of extension
given below. The assumption (essentially the same as stopperedness of [6] and
smoothness of [4]) seems not too restricitive for our purpose, since it is automatically
satisfied if D is finite, and at any time a robot can have made only a finite number
of observations. We first repeat from [2] the general definition of an extension of a
prioritized default logic using a well-ordering OE compatible with !.
well-ordering OE on D is a well-founded (complete) order on D. A
well-ordering OE on D is called compatible with ! on D iff for every d; d
implies d OE d 0 .
Definition 11 Let hD; \Gamma; !i be a prioritized default theory. The set E is called an
!-compatible extension of hD; \Gamma; !i iff E is an extension of hD; \Gammai generated by a
well-ordering OE compatible with !.
Intuitively, an extension of hD; \Gammai generated by a well-ordering OE is obtained by
sequentially applying, starting from Th(\Gamma), the OE-minimal default rule among the
non-applied applicable default rules of D. (See [2, 7] for details.) By choosing a well-ordering
compatible with !, the stronger defaults (with higher priorities) are applied
first, thereby making weaker incompatible defaults non-applicable.
Example 2 Consider the observations p e and q e 0 , and assume that it is a priori
known that p and q are incompatible, i.e., :(p-q). Further assume that e 0 is more refined
evidence than e. This situation is modelled by the observation theory D consisting
of the default theory hf?
The unique extension of D is Th(f:p; qg). Without the priority, both Th(f:p; qg) and
Th(f:q; pg) would have been extensions.
To make the example more concrete, suppose that p e denotes a robot's observation,
based on some sonar readings, that a particular door is closed, and that q e 0 denotes
the observation, based on a videocamera image in addition to the previously mentioned
sonar readings, that the door is open. Then the robot should of course conclude that
the door is open.
In the above example, the same conclusion is warranted if the evidence e 0 is just
stronger or more reliable than e, rather than more refined. However, as we will illustrate
later on, these different interpretations of the orderings can result in different
conclusions in more complex examples.
On can imagine that having different interpretations of the ordering between default
rules results in having different definitions of extensions of a prioritized default
theory. In fact, the above standard definition of !-compatible extension will not be
used as our notion of extension for observation theories.
Before we discuss which notion of extension we regard as appropriate for our pur-
pose, let us consider an alternative way of obtaining extensions of prioritized default
theories, namely by first computing an (ordinary default) extension using only the
(unordered) default rules with maximal priority, and subsequently computing an extension
using the default rules of the next priority level, et cetera. For observation
theories this can be made more precise as follows.
be an observation theory. Define D
let, for i - 1, D i be the set of !-minimal elements of . The set
Th(\Gamma) is called an 0-extension of D. For called an i-extension of D iff
of D, and some maximal
called a layered
extension of D iff is an i-extension of D and
The set of layered extensions of an observation theory hD; \Gamma; !i is a subset of its
set of !-compatible extensions.
Proposition 8 Let be an observation theory. Every layered extension
of D is a !-compatible extension of D.
Proof. Let E be a layered extension of be obtained from
by sequentially applying the default rules from a set D 0 ' D such that for every
implies that d is applied before d 0 . Moreover, for any d 2 D \Gamma D 0 , its
justification is inconsistent dg.
Let OE be a well-ordering obtained by refining ! in such a way that. whenever d
and d 0 are incomparable according to ! and d 2 D 0 and d 0 62 D 0 , it should hold
that d OE d 0 . The order between other pairs of !-incomparable default rules can be
chosen arbitrarily. Then E is an extension of hD; \Gammai generated by OE, and since OE is
compatible with !, E is a !-compatible extension of D.
The following example shows that the reverse of this proposition is not true.
Example 3 Consider the observations assume that it is a priori
known that p; q and r are jointly incompatible, i.e., :(p-q-r). Further assume that e 0
is more refined evidence than e (and e 00 is incomparable to the other bodies of evidence).
This situation is modelled by the observation theory D consisting of the default theory
p=p. The
unique layered extension of D is Th(f:p; q; rg). However, both Th(f:p; q; rg) and
Th(fp; q; :rg) are !-compatible extensions.
The following example indicates a problem with both layered extension and !-
compatible extensions in case d ! d 0 is interpreted to mean that default rule d is based
on more refined evidence than d 0 .
Example 4 Consider the observations assume that it is a priori
known that q is incompatible both with p and with r, i.e., :(p-q) and :(r-q). Further
assume that e 00 is more refined evidence than e 0 and e 0 is more refined evidence than e.
This situation is modelled by the observation theory D consisting of the default theory
This theory has one !-compatible extension Th(fp; :q; rg) and this
extension is also layered.
To make the example more concrete, consider a robot in the process of finding
out whether a particular door is open. Let us say that the door has to be open at
least 70 degrees to be called open, since otherwise the robot cannot safely pass the
door. Suppose that p e denotes the robot's observation, based on some videocamera
image taken from considerable distance from the door, that the door is 84 degrees
open, that q e 0 denotes the observation based on some sonar readings in addition to
the videocamera image, that the door is closed, and that r e 00 denotes the observation,
based in addition to the previously mentioned sensor information on a videocamera
image taken at close proximity to the door, that the door is open (without being able
to specify the exact angle of the door). Then both !-compatible and layered extensions
allow the conclusion that the door is 84 degrees open.
The problem with this conclusion is that the observation p e is defeated by q e 0 , and
it is not clear whether the fact that q e 0 is in turn defeated by r e 00 justifies re-establishing
the conclusions based on p e . In fact, if e 00 is more refined than e, then the information
supporting p in the first observation is also present in e 00 . Therefore, if one assumes
that r is the most specific proposition (relative to the background knowledge) supported
by the observation r e 00 , then p should not be derivable.
It is important to note that in the above example we introduced the assumption
that the proposition mentioned in the observation is the most specific proposition
(relative to the bacground knowledge) that is justified given the evidence on which
the observation is based. This assumption and its relation to the treatment of the
problem of sensor fusion will be discussed in more detail in section 6.
Given the above assumption, it is natural to consider only the default rules in
the top layer of the ordering, and propose 1-extensions (as defined in definition 12)
as the appropriate extensions of an observation theory. Of course, any 1-extension of
an observation theory hD; \Gamma; !i is equivalent to an (ordinary Reiter) extension of the
is the set of !-minimal default rules of
D, as defined in definition 12.
At first sight, one might think that, by the semi-monotonicity of normal default
logic (see proposition 4), the resulting logic will have a monotonic behaviour. However,
this is prevented by the ordering on defaults, since adding an observation does not
necessarily result in a monotonic increase in the !-minimal default rules.
Example 5 Consider the situation of example 4. The observation theory D consisting
of the default theory hf?
has a unique 1-extension, namely Th(fr; :qg). If we
consider the situation without the observation modelled by ? : r=r, then the resulting
observation theory has the unique 1-extension Th(f:p; q; :rg). That is, without the
evidence of the videocamera at close proximity to the door, the conclusion that the
door is closed would be justified.
In fact, the logic obtained by considering 1-extensions of observation theories is an
interesting nonmonotonic formalism, in which it is for example possible to 'withdraw'
an observation p e (where p cannot be deduced from the background knowledge) by
adding the observation ? e 0 with e 0 more refined than e. (More generally, any OE e 0 , where
OE together with the background knowledge does not imply p and e 0 more refined than
e has a similar effect.)
However, since the assumption underlying the choice for 1-extensions may not
be appropriate in all circumstances, we propose in the next section a rather general
semantics for observation theories that allows us to consider different variants of
observation logic next to the logic induced by 1-extensions.
An observation theory hD; \Gamma; !i is called consistent iff \Gamma is consistent. Unless stated
otherwise, we will from now on assume that observation theories are consistent, and
moreover, we will assume that for any observation theory hD; \Gamma; !i the facts \Gamma are
consistent with every consequent of a default rule d 2 D. These assumptions are in
accordance with our treatment of \Gamma as 'hard' background knowledge.
As models of observation theories we essentially use directed sets of first-order
models, where the ordering between the first-order models representing the observations
reflects the (refinement) ordering of (the evidence underlying) the observations.
As a reminder we include the definition of a directed set.
- be a partial order on the set X. Then hX; -i is called a directed
set iff every finite subset of X has an upper bound in X, i.e., for every finite Y ' X,
there exists an element x 2 X such that for every y 2 Y , x - y.
be an observation theory. An observation model
M of D is a tuple hM;-; obsi, where hM;-i is a directed set of first-order models
satisfying \Gamma, and obs is an injection D ! M such that the following conditions are
ffl obs(d) satisfies the consequent of d
For any first-order sentence OE, we say that there exists a model M 2 M
such that every model M 0 - M satisfies OE. For any set S of observation models, we
write Th(S) for the set of first-order formulas that are valid in every model of S.
There are many different ways to extend the scope of the satisfaction relation to
include the default rules. Perhaps the most straightforward way is to define, for any
default rule d 2 D, M j= d iff every model M - obs(d) satisfies the consequent of d.
Observation models where the satisfaction relation is thus extended are called straight.
More generally, observation models where the satisfaction relation is (in some way)
extended to include default rules are called extended.
An observation model is not a classical first-order model. In fact, an observation
model plays a role which is roughly similar to a possible worlds, or Kripke, model in
modal namely as a model of an agent's belief set such that the agent's
set corresponds to the set of formulas valid in all its models. More precisely,
an observation model of an observation theory models the beliefs of an agent who
believes all the facts and a subset of the conclusions of the default rules present in the
observation theory. Since we consider agents who, by default, believe the observations,
we will be interested in observation models which maximize the set of valid default
conclusions, or rather, the set of applied or valid default rules.
Notice that the second condition of definition 14 involves a change in direction of
the orderings. We feel this is appropriate, since the ordering on the models should be
viewed as an information ordering. The intuitive reading of M 0 ? M is that M 0 is
more refined than M. Notice however, that we have not implemented a formal notion
of refinement as in the inverse refining systems of models of [5]. An (information)
ordering between models mirroring the preference relation ! between default rules
will be called an information image of !.
Definition 15 If is an observation theory, then a partial order ? 0
on the set M of first-order models of an observation model M of D is called an
information image of ! iff it holds that obs(d) ?
It is clear that there are two kinds of observation models. An observation model
hM;-; obsi either has a top, i.e., a model M? 2 M which is more refined than any
other element of M , or M contains for any of its elements an infinite sequent of
refinements. In the latter case, we call the observation model top-less. These top-
less observation models are more like the refining inverse systems of models of [5]
than the observation models with a top are. In [5], each first-order model in the
refining system is viewed as an approximation to reality which itself is assumed to be
infinitely precise and to refine each of the models in the refining system. However, in
an observation model the top (or any other element) does not represent the reality
(or an approximation of it) but (a partial description of) a world considered possible
by the observing agent.
It is easy to see that in definition 14 we could have restricted ourselves to top-
less observation models, since any observation model is equivalent to a top-less one.
(Just add an infinite sequence of copies of the top-element on top of the top-element.)
However, below we will consider observation models where the satisfaction of default
rules is defined differently than for the straight observation models of definition 14,
and for some of these variants it does make a difference whether observation models
have a top or not.
The directedness condition ensures that default rules interact in the sense that
a set of incompatible default rules cannot be satisfied in an observation model. As
mentioned before, the most interesting observation models are those in which the set
of valid default rules are maximized. In accordance with tradition, we will call these
observation models minimal.
Definition be a straight observation model of
dg. M is called minimal iff there exists no straight observation model
M 0 of D such that M(D) ae M 0 (D). We write [M]D for the equivalence class of straight
observation models M 0 of D such that M 0
The above defined notions can be defined analogously for types of extended observation
models other than the straight observation models. The following property
is suggested as a minimal requirement on ways to extend the satisfaction relation of
observation models to default rules.
Definition 17 A class of extended observation models M of called
regular iff for every element M of the class, Th([M]D
Lemma 9 The class of straight observation models of an observation theory is regular

Proof. Assume M is a straight observation model of We will first show
that Th(\Gamma [CONSEQ(M(D))) ' Th([M]D ). Suppose OE 2 Th(\Gamma [CONSEQ(M(D))).
Then OE 2 Th(\Sigma), for some finite subset \Sigma of \Gamma[CONSEQ(M(D)). By the directedness
any M 0 2 [M]D contains a model M such that for all M 0 - M, M 0
and therefore M 0
To prove the inclusion in the other direction, it is sufficient to show that for any
first-order model M of \Gamma [ CONSEQ(M(D)), there exists a first-order equivalent
observation model in M(D). This is easy, since adding M as top to any element of
M(D) will give the desired observation model equivalent to M.
We now introduce an alternative kind of observation models, called the one level
observation models, in order to model the 1-extensions of observations theories.
Definition be an observation theory. An one level observation
model M of D is an observation model hM;-; obsi where we say that M j= d iff every
model M - obs(d) satisfies the consequent of d, and there exists no d 0 2 D such that
Analogous to the proof of lemma 9 it can be shown that the class of one level
observation models of an observation theory is regular. More importantly, there is an
exact correspondence between minimal one level observation models of an observation
theory and its 1-extensions.
Proposition 10 The 1-extensions of an observation theory correspond with its minimal
one level observation models. That is, E is an 1-extension of
one level observation model M of D.
Proof. Let E be an 1-extension of
for some maximal D 0 ' !-minimal g such that \Gamma [CONSEQ(D 0 )
is consistent. By the consistency of \Gamma [CONSEQ(D 0 ) there exists an one level observation
model M of D such that M(D) =D 0 . By the maximality of D 0 , M is minimal, and
by the regularity of one level observation models, Th([M]D
To prove the other direction, suppose one level
observation model M of D. Then, by the regularity of one level observation models,
By the directedness condition, \Gamma [CONSEQ(M(D))
is consistent, and by the minimality of M, there does not exist a set D 00 such that
is consistent. It follows that E is an
1-extension of D.
Since the notion of satisfying a default rule is more straightforward in the case
of straight observation models than in the case of one level observation models, it is
interesting to determine the kind of extensions corresponding with minimal straight
observation models.
be an observation theory. A set D 0 ae D is called
blocked iff there exists a d 2 D such that \Gamma [CONSEQ(D 0 [ fdg) is inconsistent and
for every d 0 2 D 0 , d ! d 0 . A set D 0 ' D is called unblocked iff D 0 contains no blocked
subset.
be an observation theory. The E is called an unblocked
extension of D iff unblocked
Proposition 11 The unblocked extensions of an observation theory correspond with
its minimal straight observation models. That is, E is an unblocked extension of
straight observation model M of D.
Proof. The proof is completely analogous to the proof of proposition 10. The only
difference is that one now should use the fact that D 0 is a set of default rules satisfied
by some straight observation model iff D 0 is unblocked and CONSEQ(D 0 ) is consistent,
and let the unblocked sets play the role that subsets of the !-minimal default rules
play in the case of proposition 10.
The difference between 1-extensions and unblocked extensions is that in the first
case, an observation is assumed to defeat all observations based on less refined evi-
dence, whereas in the latter case, observations that are not based on maximally refined
evidence can still play a role (as long as they are not blocked by some incompatible
observation based on more refined evidence).
Example 6 Consider the situation of example 4, but without the second observation
That is, we have the observations p e and r e 00 , where e 00 is more refined evidence
than e. This situation is modelled by the observation theory D consisting of the default
theory This theory has one one
level extension Th(frg) and one unblocked extension Th(fp; rg).
In the concrete interpretation of a robot in the process of finding out whether a
particular door is open, p e denotes the robot's observation, based on some videocamera
image taken from considerable distance from the door, that the door is 84 degrees open,
and r e 00 denotes the observation, additionally based on a videocamera image taken at
close proximity to the door, that the door is open (without being able to specify the exact
angle of the door). In that case, the one level extension only allows the conclusion that
the door is open (without being able to specify the exact angle), whereas the unblocked
extension allows the more specific conclusion that the door is 84 degrees open.
The above example provides another illustration of our previously mentioned opinion
that one level extensions are only appropriate under the assumption that observations
mention the most specific proposition. If one uses unblocked extensions, one
does not need this assumption, but it is not exactly clear how to justify the fact that
an observation that itself is defeated can still defeat some observations. (In the original
situation of example 4, the observation q e 0 blocks p e , although q e 0 is defeated by
the observation r e 00 . Thus the unique unblocked extension coincides with the one level
extension Th(frg).)
If one believes that observations should not be blocked by defeated observations,
then one should not use unblocked extensions. In that case, !-compatible extensions
seem to be an obvious choice. In order to obtain a semantics for !-compatible extensions
in terms of observation models, we should no longer require M j= d to imply that
every model M - obs(d) satisfies the consequent of d. (Otherwise, a default rule d is
automatically blocked by an incompatible default rule d 0 such that obs(d
A first idea is to allow a finite number of exceptions (i.e., models ? obs(d) not
satisfying the consequent of d) in the satisfaction clause for default rules. This does
not work, since a finite extended observation model of hD; \Gamma; !i would then satisfy
all default rules of D. Thus the minimal extended observation models would satisfy
all the default rules, whether the rules are compatible or not. It is immediate that, in
general, the class of the thus obtained extended observation models of an observation
theory would not be regular.
Even if we restrict ourselves to top-less observation models, we do not obtain a
semantics for !-compatible extensions, since the effect of the ordering is completely
lost as soon as a finite number of exceptions is allowed in the satisfaction clause for
default rules. In fact, in that case, we get a semantics for the underlying default
theory, without the priorities.
be an observation theory. A cofinal observation
model M of D is an extended top-less observation model hM;-; obsi of D, where we
say that M j= d iff all but a finite number of the models M - obs(d) satisfy the
consequent of d.
It can be shown that the class of cofinal observation models of an observation
theory is regular. (The proof of lemma 9 has to be slightly amended, since after
adding a top to a cofinal model it is no longer top-less, and therefore no longer cofinal.
However, instead of adding a single first-order model as a top, one can simply add an
infinite sequence of copies of the first-order model.)
Proposition 12 Let be an observation theory. The minimal cofinal
observation models of D correspond with the (ordinary Reiter) extensions of hD; \Gammai.
That is, E is an extension of hD; \Gammai iff cofinal
observation model M of D.
Proof. The proof is completely analogous to the proof of proposition 10. The only
difference is that one now should use the fact that D 0 is a set of default rules satisfied
by some cofinal observation model of D
these compatible sets of default rules play the role that subsets of the !-minimal
default rules play in the case of proposition 10.
If one tries to model the situation where observations are not blocked by defeated
observations, then one should not allow arbitrary exceptions in the satisfaction clause
for default rules, but only allow exceptions among the first-order models representing
defeated observations. This suggests a definition of the satisfaction of a default rule
along the lines of M satisfies the consequent of
d or there exist a d 0 2 D such that
notation for 'd 0 is defeated'.
The problem with this approach is that the satisfaction and defeat of default rules
interact in intricate ways, since the more default rules are satisfied, the more default
rules are defeated, and vice versa. Therefore, it is not immediately clear what the
correct definition of defeat would have to be. A simple solution is to introduce in the
extended observation models an additional parameter for a particular well-ordering
OE compatible with the partial order ! on default rules.
Definition 22 Let be an observation theory. A !-compatible observation
model M- of D is an extended observation model hM;-; obsi of D, where -
is an information image of a !-compatible well-ordering OE, and the satisfaction and
defeat of default rules are defined as follows.
satisfies the consequent of d or there
exists a d 0 2 D such that
inconsistent.
Here (as before) M- dg, and we define [M- ] D to be the the
equivalence class of !-compatible observation models M 0
- 0 of D such that M 0
M- (D).
Notice that in the above definition the notions of satisfaction and defeat of default
rules are well defined since their respective clauses only refer to other default rules
that are more preferred according to OE. Analogous to the proof of lemma 9 it can be
shown that the class of !-compatible observation models of an observation theory is
regular.
Proposition 13 The minimal !-compatible observation models of an observation
theory correspond with the !-compatible extensions of D. That is, E
is a !-compatible extension of D iff
observation model M- of D.
Proof. Suppose E is a !-compatible extension of is an
extension of hD; \Gammai generated by some !-compatible well-ordering OE. It follows that
such that d 62 D 0 implies that \Gamma [
inconsistent. Consider the class of !-compatible
observation models M- of D where - is an information image of OE. For every M- in
this class, the defeated default rules are exactly the elements of D \Gamma D 0 . Let M- be
a model of this class with a maximal set of satisfied defaults. Then M- is minimal,
by regularity, Th([M-
To prove the other direction, let
observation model M- of D. Suppose - is the information image of the !-compatible
well-ordering OE of D. By the minimality of M- , M- (D) is the complement of
the set of defeated default rules. Therefore, d 62 M- (D) implies that the set \Gamma [
CONSEQ(fdg[fd inconsistent. Thus Th(\Gamma[CONSEQ(M - (D)))
is a !-compatible extension of D. By the regularity of !-compatible observation mod-
els, it then follows that E is a !-compatible extension of D.
We conclude that the proposed observation models can provide a flexible semantics
for different observation logics. In the following section we discuss in more detail the
matter under what circumstances the different observation logics are most appropriate,
and we relate this matter to the much discussed problem of sensor fusion in robotics.
6 The Sensor Fusion Problem
Evidence from one particular, isolated sensor reading is relatively well understood.
One usually has at least sufficient partial or approximate knowledge of the behaviour,
and in particular of the reliability, of a sensor to confidently relate possible sensor
readings to conclusions about the state of the world. Unfortunately, since sensors are
never completely reliable and often quite unreliable, these conclusions are typically
fairly weak. Therefore, multiple sensor readings need to be combined in order to
justify strong conclusions.
The problem with combining, or fusing, the evidence obtained from multiple sensor
readings is that it is difficult to assess the interaction between multiple pieces of
evidence acquired from different sensors, from different readings of the same sensor
obtained at different locations, or even from readings of the same sensor obtained at
the same location.
Typically, one uses some numeric uncertainty formalism, such as probability the-
which allows the reinforcement of conclusions whenever sensor readings agree and
(partial) cancelling out of the individual effects of disagreeing sensor readings. This
probabilistic, or in general numeric, reasoning is very powerful, but it requires a lot
of data or strong assumptions. Since often the required data is insufficiently available
and the chosen assumptions cannot adequately be justified, the conclusions obtained
by numeric reasoning cannot always be trusted.
Since we use non-numeric default rules to represent observations, we cannot expect
the same subtle reasoning. But default reasoning still may give reasonable and useful
results, and, in particular in situations where the numeric data required for numeric
reasoning cannot easily be obtained, the results of default reasoning are not necessarily
inferior to those of the numeric approaches.
Let us briefly comment on the relation between expressing an observation in terms
of (normal free) default rules and the representation of an observation in numeric,
say probabilistic, terms. At first sight, it might seem reasonable to assume that
a defeasible observation that OE, represented by ? : OE=OE, has a roughly equivalent
probabilistic interpretation of the form that, given the evidence, OE is the most likely, or
most probable, possibility. The problem with this assumption is t hat either the most
likely possibility is trivially ?, or one has to compare only possibilities corresponding
to elementary events or, more generally, possibilities corresponding to some partition
of the sample space, and it is difficult to fix in advance an appropriate partition.
Example 7 In the situation of example 4, the observation r e 00 , based on a videocamera
image taken at close proximity to the door, supports the possibility that the door is open
(without supporting any exact angle of the door). This could be interpreted to mean
that 'open' is the most likely element of f `open', 'closed' g. However, the observation
based on some videocamera image taken from considerable distance from the door,
supports the possibility that the door is 84 degrees open. If this possibility is supposed
to be the most likely one given the evidence e, then possibilities are compared that are
not elements of the set f 'open', `closed' g used in the case of r e 00 .
An alternative probabilistic interpretation of the default rule representing
a defeasible observation is to say that it is roughly equivalent to saying that, given
the evidence, the probability of OE is sufficiently high. It is well known that, unless
sufficiently high is interpreted as arbitrarily close to 1, both interpretations support
different sets of inference rules. For example, whenever OE and / are compatible,
together support OE-/, whereas in the probabilistic interpretation
this inference is not valid, since the probability of the conjunction OE - / may be
significantly lower than the probabilities of the individual conjuncts.
In spite of the fact that no exact agreement exists between the conclusion supported
by default rules and those supported by the above mentioned probabilistic
interpretation of default rules, we still think the interpretation is at least useful as a
heuristic. For example, the fact that evidence that does not support a rather specific
proposition (such as 'the door is 84 degrees open') can still support a less specific
proposition (such as 'the door is open') is quite clear under the probabilistic interpretation

For an adequate evaluation of the usefulness of the interpretation of observations
by means of default rules, it is important to know how multiple observations are
combined. To get an overview of how the choice for a particular notion of extension
effect the combination behaviour, we summarize in table 1 the conclusions supported
by the different defeasible observation logics in several examples.
It is easy to see that the conclusions supported by 1-extensions are included in the
set of conclusions supported by layered extensions, since for every layered extension
E of an observation theory D there exists an 1-extension E 0 of D such that E 0 ' E. It
follows from the examples summarized in table 1 that, in general, the set of conclusions
supported by 1-extensions is not necessarily weaker (or stronger) than the set of
conclusions supported by !-compatible, unblocked, or unprioritized extensions.
In example 6, all the discussed types of extensions, except the 1-extensions, support
the conclusion that the door is 84 degrees open. As mentioned before, this strong
conclusion is no longer justified if the observation that the door is open is assumed
to be based on evidence which is really more refined than (and therefore includes)
the evidence underlying the observation that the door is 84 degrees open, and if one
additionally assumes that 'the door is open' is the most specific conclusion supported
extensions example 4 example 6 new example
1-extensions open open 79 degr. open
!-compatible 84 degr. open 84 degr. open 79 or 84 degr. open
unblocked open 84 degr. open 79 or 84 degr. open
layered 84 degr. open 84 degr. open 79 degr. open
without priorities closed or 84 degr. open 84 degr. open 79 or 84 degr. open

Table

1: A comparison of the conclusions supported by different notions of extensions.
In example 4 we have a refining sequence of observations that the door is 84 degrees
open (videocamera, great distance), that the door is closed (sonar), and that the door
is open (videocamera, small distance). Example 6 is the same, but without the sonar-based
observation that the door is closed. In the new example, we add to example 6 a
new observation that the door is 79 degrees open, and we assume that this observation
is incomparable to both other observations.
by the more refined evidence.
Assuming that the evidence e underlying the observation that the door is open
is more refined than the evidence e 0 underlying the observation that the door is 84
degrees open implies that e does not consist only of the videocamera image taken
near the door, but also incorporates the videocamera image taken from considerable
distance (e 0 ). In other words, more refined evidence combines the less refined evidence
(possibly) with new sensory information.
Although usually the evidence from one particular observation or sensor reading is
better understood than the combined effect of several observations, it is also sometimes
the case that in order to express a particular observation in an abstract, symbolic
language, one has to take into account several other observations. For example, when
interpreting a videocamera image and concluding from it that the door is open, one
typically uses information obtained by other sensor readings about matters like the
approximate distance between the camera and the door. Therefore, even if at one
level of description sensor readings are initially interpreted in isolation, it may be
the case that at some more abstract level, observations often refine other (previous)
observations.
The pieces of evidence underlying incomparable (maximally preferred) observations
can be viewed as pieces of evidence that (as yet) have not been combined, and
the defeasible observation logic using 1-extensions can be viewed as a logic providing
(defeasible) statements of what the results of the combination of these pieces of evidence
are expected to be. In fact the process of combining two observations OE e and
can be represented by adding an observation based on evidence refining both e
and e 0 . Since it is not necessary for this latter observation to incorporate some new
sensory information, one might consider the sensor fusion process itself as a kind of
'observation'.
It should be noted that, although we have used the sceptical, or cautious, interpretation
of default consequence, it is not the case that the expectations concerning the
results of combining evidence as expressed by the observation logic using 1-extensions
are the weakest possible, or most cautious.
Example 8 Consider two observations OE e and / e 0 , where OE denotes that the door is
84 degrees open and / denotes that the door is 79 degrees open, and where e and e 0
are incomparable. The observation logic using 1-extensions supports the conclusion
that the door is 79 or 84 degrees open. However, after proper combination of e and
might be the case that both pieces of evidence are considered unreliable, and it
might even become unclear whether the pieces of evidence provide any information
concerning the state of the door at all.
We conclude that reasoning with the observation logic using 1-extensions should
not replace a careful sensor fusion process. However, as long as the defeasible conclusions
of the observation logic are recognized as defeasible expectations, they form a
potentially useful supplement to the conclusions based on the (at any particular time,
probably incomplete) process of careful combination of obtained evidence.
Using !-compatible, unblocked, and layered extensions does not seem compatible
with a reading of ! as a refining relation. In that case, ! is more naturally interpeted
as a relation expressing relative strength or reliability of pieces of evidence. The observation
logics using these different notions of extensions implement different intuitions
concerning the issue of how to combine observations, but they all, in a sense, replace
a careful sensor fusion process, rather than supplement it.
However, since we believe that, in general, a careful combination of the observations
cannot adequately be represented, or even approximated, by a systematic inter-action
between the default rules representing the observations, we prefer 1-extensions
above the other mentioned notions of extension.
7 The Multiple Extension Problem
The standard explanation of the meaning of a normal, free
the derivation of !, provided ! is consistent with what is derivable. Assuming that
an extension is intended to represent a reasonable set of conclusions of the default
theory, the existence of multiple extensions constitutes a problem, since any choice
for a particular extension is arbitrary in the sense that it does not follow from the
theory.
The problem does not disappear in case the intersection of all extensions is proposed
to be the set of conclusions of a default theory. The diffculty with this cautious
or sceptical approach is that in general the intersection is itself not an extension and
not closed under the default rules.
Example 9 Consider the default theory consisting of the two default rules
knowledge :(p - q). This default theory has two extensions:
Th(fp; :qg) and Th(f:p; qg). The intersection of the extensions is Th(fp $ qg). If
this intersection is supposed to be the set of all derivable conclusions, then, under the
standard interpretation of default rules, ? : p=p is applicable, and p is derivable. In
the same way, ? : q=q allows the derivation of q. But Th(fp $ qg) contains neither
nor q.
A possible solution of the problem is to come up with an alternative interpretation
of default rules, where the justification does not refer to the set of derivable
conclusions. When default rules are used to represent defeasible observations, such
an alternative interpretation is actually rather natural.
An observation OE e is a reason to conclude that OE, and this reason is sufficient, unless
other (incomparable or more refined) observations provide reasons against OE. If these
other observations are based on more refined evidence than e, then the observation
OE e is defeated. If the other observations are incomparable to OE e , then the supported
conclusion is weaker than OE, but OE should still be considered possible. Thus, the
representing OE e supports the conclusion OE only in case all evidence
against OE is less refined than e.
Given the interpretation of a (normal, free) default rule as a (not necessarily
sufficient) reason to conclude the consequent of the rule, the sceptical approach to
default logic seems quite sensible. In the sceptical approach, extensions should not
be interpreted as reasonable sets of conclusions of a default theory, but as maximally
consistent sets of conclusions, mirroring the interaction between the default rules.
For example, the intersection Th(fp $ qg) of the extensions Th(fp; :qg) and
Th(f:p; qg) seems to be a reasonable set of conclusion in case of example 9. The fact
that there is a reason for believing p and a reason for believing q is compatible with
this set of conclusions, since the reasons are only considered sufficient for actually
drawing the conclusions in case all conflicting evidence is less refined.
If default rules are used to represent defeasible observation, then there is a second
solution to the multiple extension problem. Since multiple extensions only occur
in the presence of conflicting default rules, one can simply avoid the formalization
of conflicting observations. For example, one can apply a process of sensor fusion
to harmonize conflicting observations, before translating the observation into default
rules. The resulting observation logic will have a unique extension.
In the context of 1-extensions, it is always possible to 'weaken' several conflicting
observations to their disjunction. For example, p e and q e 0 , with p and q incompatible
and e and e 0 incomparable, can be replaced by (p - q) e 00 , with e 00 more refined than e
and e 0 . This can be viewed as a particular method of combining (possibly conflicting)
observations, but the conclusions resulting from harmonizing conflicting observations
with this particular method of sensor fusion are in general weaker than the conclusions
supported by taking the intersection of all 1-extensions of the original observation
theory.
Consider the default theory consisting of the three default rules
knowledge :(p - q - r). This default theory has
three extensions: Th(fp; q; :rg), Th(fp; :q; rg), and Th(f:p; q; rg). Each of these
extensions contains the formula :p ! (q - r), but this formula is not contained in
which is the unique 1-extension of the observation theory
obtained from the original default theory by adding a default rule
refining the original three default rules.
One can of course try to represent other, perhaps more complex, sensor fusion
methods in observation logic, but we will not pursue this matter here.
Conclusions
We have shown how defeasible observations can be formalized using prioritized normal
observation logic. Several notions of extension for this special
case of default logic have been discussed, and it has been argued that the notion of
1-extension is the most appropriate, provided the priority relation is assumed to be a
refining relation, and the formula mentioned in an observation statement is maximally
specific, or informative.
The proposed semantics for observation logic is loosely based on the refining systems
for the logic of vision presented in [5], and is sufficiently general to cover several
variants of observation logic induced by various notions of extension. The difference
between 1-extensions and the other notions is caused by a difference in the way the
satisfaction relation of an observation model is extended to include default rules.
We argued that the observation logic induced by 1-extensions cannot replace a
careful sensor fusion process, but that it can supplement sensor fusion by giving some
statements of the expected combined effect of observations before the underlying pieces
of evidence are actually combined in a careful (but difficult) sensor fusion process.
Finally, we claim that the existence of multiple extensions of an observation theory
does not consitute a problem for observation logic, since the default rules representing
defeasible observations have a natural interpretation where the justification of a
default rule does not refer to the set of conclusions of the observation theory.



--R

An Introduction to Default Logic (Springer
An extended logical framework for default reasoning
Reasoning with Incomplete Information (Pitman
Artificial Intelligence 44
A logic of vision
General theory of cumulative inference.
Nonmonotonic Logic.
A logic for default reasoning

As Far as I Know.
--TR
General theory of cumulative inference
Nonmonotonic reasoning, preferential models and cumulative logics
theories of Poole-type and a method for constructing cumulative versions of default logic
logic
Introduction to Default Logic
Reasoning with Incomplete Information
defeasible observations;nonmonotonic logic;multiple extension problem;prioritized default logic;sensor fusion;free default logic