Page 281 - Introduction to Autonomous Mobile Robots

Chapter 6
266
large. Thus the representation will be efficient in the case of large, sparse environments.
Practically speaking, due to complexities in implementation, the exact cell decomposition
technique is used relatively rarely in mobile robot applications, although it remains a solid
choice when a lossless representation is highly desirable, for instance to preserve complete-
ness fully.

Approximate cell decomposition. By contrast, approximate cell decomposition is one of
the most popular techniques for mobile robot path planning. This is partly due to the pop-
ularity of grid-based environmental representations. These grid-based representations are
themselves fixed grid-size decompositions and so they are identical to an approximate cell
decomposition of the environment.
The most popular form of this, shown in figure 5.15 of chapter 5, is the fixed-size cell
decomposition. The cell size is not dependent on the particular objects in an environment
at all, and so narrow passageways can be lost due to the inexact nature of the tessellation.
Practically speaking, this is rarely a problem owing to the very small cell size used (e.g.,
5 cm on each side). The great benefit of fixed size cell decomposition is the low computa-
tional complexity of path planning.
For example, NF1, often called grassfire, is an efficient and simple-to-implement tech-
nique for finding routes in such fixed-size cell arrays [96]. The algorithm simply employs
wavefront expansion from the goal position outward, marking for each cell its distance to
the goal cell [79]. This process continues until the cell corresponding to the initial robot
position is reached. At this point, the path planner can estimate the robot’s distance to the
goal position as well as recover a specific solution trajectory by simply linking together
cells that are adjacent and always closer to the goal.
Given that the entire array can be in memory, each cell is only visited once when looking
for the shortest discrete path from the initial position to the goal position. So, the search is
linear in the number of cells only. Thus complexity does not depend on the sparseness and
density of the environment, nor on the complexity of the objects’ shapes in the environ-
ment. Formally, this grassfire transform is simply breadth-first search implemented in the
constrained space of an adjacency array. For more information on breadth-first search and
other graph search techniques, refer to [30].
The fundamental cost of the fixed decomposition approach is memory. For a large envi-
ronment, even when sparse, this grid must be represented in its entirety. Practically, due to
the falling cost of computer memory, this disadvantage has been mitigated in recent years.
The Cye robot is an example of a commercially available robot that performs all its path
planning on a 2D 2 cm fixed-cell decomposition of the environment using a sophisticated
grassfire algorithm that avoids known obstacles and prefers known routes [42].
Figure 5.16 of chapter 5 illustrates a variable-size approximate cell decomposition
method. The free space is externally bounded by a rectangle and internally bounded by