Page 405 - Introduction to AI Robotics

388
Localization and Map Making
11
of to reduce confusion when belief mass is assigned to the proposition
mpty
ccupied;
fOE g.
A belief function B must l
e satisfy the following three conditions:
1. B (;) e l : This prohibits any =belief to be assigned to the empty set ; or 0
“nothing.” A sensor may return a totally ambiguous reading, but it did
make an observation. The practical ramification for occupancy grids is
that there are only 3 elements for belief: Occupied , E ,a mnd . p t y
2. B ( ) e = l1: This specifies the quantum of belief to be 1. Just as with
Bayesian probabilities where P (H) P (:H) = 1:0, Condition 2 means
+
that B (H e ) l B (:H lB 1 e l:0 + .
+ ( )=
e)
3. For every positive integer n and every collection A 1 ; n : of subsets of : ; A
:
,
X \
B (A 1 e: l n ) : : ( 1) A jIj+1 B ( eA i ) l
I f 1;::: ;n g;I6=; i I

This says that more than one belief function contributing evidence over
can be summed, and that the resulting belief in a proposition can be
higher after the summation.

j
To summarize, a belief function representing the belief that an area g r[i][ i d
]
is expressed as a tuple with three members (unlike the two in probabilities),
occupied, empty, dontknow. The belief function can be written as:
)
ccupied
B = e m(O l ); (E m m (dontknow m p ) t y
;
An occupancy grid using belief functions would have a data structure sim-
ilar to the typedef struct P used in a Bayesian grid. One possible im-
plementation is:

typedef struct {
double occupied;
double empty;
double dontknow;
} BEL;

BEL occupancy_grid[ROWS][COLUMNS];