Page 415 - Introduction to AI Robotics

398

t3
t1 t2 11 Localization and Map Making

t1 t2 t3

Figure 11.10 HIMM updating example for a wall a.) when velocity and update rates
are well matched, and b.) when update rate is slower than velocity, leading to holes.

returned by the sonar is always 3 grid elements long: therefore 1 element will
be scored as occupied and 2 elements will scored as empty. Also, the robot’s
motions are such that the sonar is always facing “up” and aligned with the
grid. The grid is initialized to 0, indicating that the robot assumes that the
world is empty.

11.5.2 Growth rate operator

A disadvantage of HIMM is that the scattered sampling means that a par-
j
ticular element g r[i][ i dmay get only one or two updates. This has two
]
ramifications. First, it means the values in the grid tend to be low; an el-
ement that is occupied and only has two updates has a score of 6, which
is less than half of the maximum score of 15 for occupancy. Second, small
obstacles such as poles or chairs which present a small profile to the sonar
versus a wall never receive a high score. One way to handle this is to change
the scoring increments. If this is done, the updating process tends to produce
maps with many phantom obstacles.
Another approach is to consider nearby grid elements. A heuristic is that
the more neighbors an element has which are occupied, the more likely there
is something really there and its score should be increased. Note that this
is handled in evidential methods by having a sonar model with a large .