Page 420 - Introduction to AI Robotics

Comparison of Methods
11.6 11.6 Comparison of Methods 403
Occupancy grid methods have their unique advantages and disadvantages.
Bayesian and Dempster-Shafer theory are formal theories, and other read-
ings from other sensor modalities, such as range from stereo or a laser, can be
easily fused as long as there is a sensor model. HIMM is limited to sonars but
it has significant computational advantages. As seen in Fig. 11.14, all three
produce similar occupancy grids, with a slight advantage going to Bayesian
and Dempster-Shafer grids. In practice, Bayesian and Dempster-Shafer have
fewer parameters to tune, making them more straightforward to adapt to
new environments.

11.6.1 Example computations

The similarities and differences between the three methods is best seen by
an example. The following example covers how to initialize the occupancy
grid, compute the score at a grid element for a sensor reading, update the
grid, and repeat for three different observations.

Step 1: Initialize the Occupancy Grid.
Consider a robot beginning to map a new area. The occupancy grid shown
in Fig. 11.15 covers an area of 12 units by 10 units. The grid is an array of
size 24 x 21, with 2 grid elements per unit of distance. The grid starts in
an initial unsensed state. In a Bayesian approach, each element in the grid
m
would be a structure P with two fields: P (Occupied ) and P (E ).The p t y
value of each field depends on the unconditional probability that the area
represented by the grid is occupied or empty. Unless there is some prior
knowledge, the assumption is that an element has equal chances of being oc-
=
cupied or empty. This translates to P (Occupied ) P (E ) :5. Every = 0
mpty
element in the grid would start with (0.5, 0.5). In a Dempster-Shafer im-
plementation, each element in the grid would be a structure Bel with three
mpty
fields: m(Occupied ); (E m) and m(dontknow ). Sincethegridrepresents
areas that have not been sensed, the entire belief mass m is initialized as
m(dontknow ) = 1:0. Every element in the grid would start with (0.0, 0.0,
1.0). Every element in a HIMM occupancy grid would be a single 8-bit inte-
ger, and would be initialized to 0.
Consider how three different sonar updates create a certainty value for a
particular grid element, g r[3][10] i d , shown in Fig. 11.15. At time t 1 , the sonar