Page 404 - Introduction to AI Robotics

387
11.4 Dempster-Shafer Theory
may provide direct evidence for an event H, but, due to occlusions, it may
not be perceiving the entire object. Therefore, there is a possibility that the
evidence could be higher than was reported. The possibilistic belief func-
tions, also called Shafer belief functions, are combined used Dempster’s rule
of combination. The rule of combination is very different from Bayes’ rule,
although they provide similar results. Unlike Bayes’ rule, Dempster’s rule
has a term which indicates when multiple observations disagree. This con-
flict metric can be used by the robot to detect when its occupancy grid may
be subject to errors.

11.4.1 Shafer belief functions

Belief is represented by Shafer belief functions in Dempster-Shafer theory.
The belief functions serve the same purpose as probabilities in Bayesian evi-
dential reasoning, although they are quite different in flavor. Instead of mea-
suring the probability of a proposition, belief functions measure the belief
mass, m. Each sensor contributes a belief mass of 1.0, but can distribute that
mass to any combination of propositions. This can be illustrated by a direct
comparison with probabilities.
A probability function quantifies the evidence for a set of outcomes, H =
fH :Hg. A belief function calls the set of propositions the frame of discern-
;
ment, signifying what can be discerned (or observed) by an observer or sen-
sor. The frame of discernment is either abbreviated by FOD or represented
by capital theta, . The frame of discernment for an occupancy grid is:
ccupied;
fOE g =
mpty
Unlike in probability theory, H = does not have to be composed of mu-
tually exclusive propositions. A belief function can represent that the sensor
had an ambiguous reading, that it literally doesn’t know what is out there.
The sensor can distribute some of its quanta of belief mass to the proposition
that the area is occupied, but it can also mark a portion of its belief mass to
being unable to tell if the area is occupied or empty.
The number of all possible subsets that the belief mass can be distributed to

by a belief function is 2 or 2 raised to the power of the number of elements
in the set . For thecaseofan occupancygrid, thepossible subsets are:
g
f
ccupied;
E
fO c c u p i e d g, fOE g, and the empty set ;. Belief that
mpty
,
mpty
an area is fOccupied;Empty g means that it is either Occupied or Empty. This
is thesameset as , and represents the “don’t know” ambiguity (if any)
associated with a sensor observation. The term dontknow will be used instead