Page 219 - Introduction to Autonomous Mobile Robots

204

start 8 Chapter 5
7 17

9 10

5
1 6 18

14
4 15
2
3
16
11 12 13
goal

Figure 5.14
Example of exact cell decomposition.

Figure 5.14 depicts an exact decomposition of a planar workspace populated by polyg-
onal obstacles. The map representation tessellates the space into areas of free space. The
representation can be extremely compact because each such area is actually stored as a
single node, resulting in a total of only eighteen nodes in this example.
The underlying assumption behind this decomposition is that the particular position of
a robot within each area of free space does not matter. What matters is the robot’s ability
to traverse from each area of free space to the adjacent areas. Therefore, as with other rep-
resentations we will see, the resulting graph captures the adjacency of map locales. If
indeed the assumptions are valid and the robot does not care about its precise position
within a single area, then this can be an effective representation that nonetheless captures
the connectivity of the environment.
Such an exact decomposition is not always appropriate. Exact decomposition is a func-
tion of the particular environment obstacles and free space. If this information is expensive
to collect or even unknown, then such an approach is not feasible.
An alternative is fixed decomposition, in which the world is tessellated, transforming the
continuous real environment into a discrete approximation for the map. Such a transforma-
tion is demonstrated in figure 5.15, which depicts what happens to obstacle-filled and free
areas during this transformation. The key disadvantage of this approach stems from its inex-
act nature. It is possible for narrow passageways to be lost during such a transformation, as
shown in figure 5.15. Formally, this means that fixed decomposition is sound but not com-
plete. Yet another approach is adaptive cell decomposition, as presented in figure 5.16.