Page 418 - Introduction to AI Robotics

401
11.5 HIMM
]
j
cupancy grid. The center of the mask fits directly over g r[i][ i d.In this case,
the mask is a 3x3 mask; it has 3 columns and 3 rows. A 3x3 mask represents
j
]
that g r[i][ i dhas 8 neighbors that should be considered. Masks of larger
sizes can be applied using the same method; larger sizes will grow the score
of clusters of occupied regions much quicker since it considers the influence
of more neighbors.
j
]
While the more occupied neighbors g r[i][ i dhas should increase the score,
the increase should also be affected by neighbor’s score. For example, the fact
that l has an occupied neighbor should increase the score, but if the score of
the neighbor is low, g r[i][ i d’s score shouldn’t increase very much. Therefore
]
j
each element of the mask contains a weighting factor. In Fig. 11.12, the mask
W has a center with 1.0 and the surrounding elements are 0.5. When g r[i][ i d
]
j
is updated as occupied, the update now has essentially two steps:
]
]
j
I
g r[i][ i d g r[i][ i d = +
j
This is the standard HIMM updating, but now it only produces a tempo-
rary value for g r[i][ i dthat will be used in the next step. The second step is
]
j
to apply the weighting specified by the mask, W.
X
]
g r[i][ i d g =r[i][ i d W [i + p][ j + q]
j
j
]
p;q = 1::: 1
: is telling the
Note that the mask W is given indices from 1 : 1. This :
program to start with the element 1 row “up” and 1 column “to the left” of
the grid element. This expands to:
1][
j
g r[i][ i d = (g r[i i d j 1] 0:5 g r[i i d j] )0:5)+ + (
]
1][
j
(g r[i i d j + 0:5 g r[i][ i d 1] )0:5)+ 1 + ] (
1][
(g r[i i d j] 1:0 g r[i][ i d+ )0:5)+ + 1 ] (
j
1][

(g r[i + 1] 0:5 g r[i + 1 )0:5)+ + ] [ (
1][
i d j
i d j]
i d j +
(g r[i + 0:5) 1 1 ] ] [
Fig. 11.13 shows the difference in the final occupancy grid if GRO is used
instead of the basic HIMM in Fig. 11.11. The resulting occupancy grid now
shows that there is definitely an obstacle present. In 8 readings, GRO was
able to reflect the presence of an obstacle that the basic HIMM updating rule
could have only approached with 40 readings.