Page 276 - Introduction to Autonomous Mobile Robots

261
Planning and Navigation
Furthermore, mobile roboticists will often plan under the further assumption that the
robot is simply a point. Thus we can further reduce the configuration space for mobile robot
x
path planning to a 2D representation with just - and -axes. The result of all this simpli-
y
fication is that the configuration space looks essentially identical to a 2D (i.e., flat) version
of the physical space, with one important difference. Because we have reduced the robot to
a point, we must inflate each obstacle by the size of the robot’s radius to compensate. With
this new, simplified configuration space in mind, we can now introduce common tech-
niques for mobile robot path planning.

Path-planning overview. The robot’s environment representation can range from a con-
tinuous geometric description to a decomposition-based geometric map or even a topolog-
ical map, as described in section 5.5. The first step of any path-planning system is to
transform this possibly continuous environmental model into a discrete map suitable for the
chosen path-planning algorithm. Path planners differ as to how they effect this discrete
decomposition. We can identify three general strategies for decomposition:
1. Road map: identify a set of routes within the free space.

2. Cell decomposition: discriminate between free and occupied cells.
3. Potential field: impose a mathematical function over the space.
The following sections present common instantiations of the road map and cell decom-
position path-planning techniques, noting in each case whether completeness is sacrificed
by the particular representation.

6.2.1.1 Road map path planning
Road map approaches capture the connectivity of the robot’s free space in a network of 1D
curves or lines, called road maps. Once a road map is constructed, it is used as a network
of road (path) segments for robot motion planning. Path planning is thus reduced to con-
necting the initial and goal positions of the robot to the road network, then searching for a
series of roads from the initial robot position to its goal position.
The road map is a decomposition of the robot’s configuration space based specifically
on obstacle geometry. The challenge is to construct a set of roads that together enable the
robot to go anywhere in its free space, while minimizing the number of total roads. Gener-
ally, completeness is preserved in such decompositions as long as the true degrees of free-
dom of the robot have been captured with appropriate fidelity. We describe two road map
approaches below that achieve this result with dramatically different types of roads. In the
case of the visibility graph, roads come as close as possible to obstacles and resulting paths
are minimum-length solutions. In the case of the Voronoi diagram, roads stay as far away
as possible from obstacles.