Page 221 - Introduction to Autonomous Mobile Robots

206

start Chapter 5

goal

Figure 5.16
Example of adaptive (approximate variable-cell) decomposition of an environment [21]. The rectan-
gle, bounding the free space, is decomposed into four identical rectangles. If the interior of a rectangle
lies completely in free space or in the configuration space obstacle, it is not decomposed further. Oth-
erwise, it is recursively decomposed into four rectangles until some predefined resolution is attained.
The white cells lie outside the obstacles, the black inside, and the gray are part of both regions.

of each sensor, combined with the absolute position of the robot, can be used directly to
update the filled or empty value of each cell.
In the occupancy grid, each cell may have a counter, whereby the value 0 indicates that
the cell has not been “hit” by any ranging measurements and, therefore, it is likely free
space. As the number of ranging strikes increases, the cell’s value is incremented and,
above a certain threshold, the cell is deemed to be an obstacle. The values of cells are com-
monly discounted when a ranging strike travels through the cell, striking a further cell. By
also discounting the values of cells over time, both hysteresis and the possibility of transient
obstacles can be represented using this occupancy grid approach. Figure 5.17 depicts an
occupancy grid representation in which the darkness of each cell is proportional to the value
of its counter. One commercial robot that uses a standard occupancy grid for mapping and
navigation is the Cye robot [163].
There remain two main disadvantages of the occupancy grid approach. First, the size of
the map in robot memory grows with the size of the environment and if a small cell size is
used, this size can quickly become untenable. This occupancy grid approach is not compat-
ible with the closed-world assumption, which enabled continuous representations to have
potentially very small memory requirements in large, sparse environments. In contrast, the