Page 279 - Introduction to Autonomous Mobile Robots

Chapter 6
264
find paths on the Voronoi road map are complete just like visibility graph methods, because
the existence of a path in the free space implies the existence of one on the Voronoi diagram
as well (i.e., both methods guarantee completeness). However, the path in the Voronoi dia-
gram is usually far from optimal in the sense of total path length.
The Voronoi diagram has an important weakness in the case of limited range localiza-
tion sensors. Since this path-planning algorithm maximizes the distance between the robot
and objects in the environment, any short-range sensor on the robot will be in danger of fail-
ing to sense its surroundings. If such short-range sensors are used for localization, then the
chosen path will be quite poor from a localization point of view. On the other hand, the vis-
ibility graph method can be designed to keep the robot as close as desired to objects in the
map.
There is, however, an important subtle advantage that the Voronoi diagram method has
over most other obstacle avoidance techniques: executability. Given a particular planned
path via Voronoi diagram planning, a robot with range sensors, such as a laser rangefinder
or ultrasonics, can follow a Voronoi edge in the physical world using simple control rules
that match those used to create the Voronoi diagram: the robot maximizes the readings of
local minima in its sensor values. This control system will naturally keep the robot on
Voronoi edges, so that Voronoi-based motion can mitigate encoder inaccuracy. This inter-
esting physical property of the Voronoi diagram has been used to conduct automatic map-
ping of an environment by finding and moving on unknown Voronoi edges, then
constructing a consistent Voronoi map of the environment [59].
6.2.1.2 Cell decomposition path planning
The idea behind cell decomposition is to discriminate between geometric areas, or cells,
that are free and areas that are occupied by objects. The basic cell decomposition path-plan-
ning algorithm can be summarized as follows [30]:

F
• Divide into simple, connected regions called “cells”.
• Determine which opens cells are adjacent and construct a “connectivity graph”.
• Find the cells in which the initial and goal configurations lie and search for a path in the
connectivity graph to join the initial and goal cell.
• From the sequence of cells found with an appropriate searching algorithm, compute a
path within each cell, for example, passing through the midpoints of the cell boundaries
or by a sequence of wall-following motions and movements along straight lines.

An important aspect of cell decomposition methods is the placement of the boundaries
between cells. If the boundaries are placed as a function of the structure of the environment,
such that the decomposition is lossless, then the method is termed exact cell decomposition.
If the decomposition results in an approximation of the actual map, the system is termed