Page 282 - Introduction to Autonomous Mobile Robots

267
Planning and Navigation
three polygons. The rectangle is recursively decomposed into smaller rectangles. Each
decomposition generates four identical new rectangles. At each level of resolution only the
cells whose interiors lie entirely in the free space are used to construct the connectivity
graph. Path planning in such adaptive representations can proceed in a hierarchical fashion.
Starting with a coarse resolution, the resolution is reduced until either the path planner iden-
tifies a solution or a limit resolution is attained (e.g, k • size of robot). In contrast to the
exact cell decomposition method, the approximate approach can sacrifice completeness,
but it is mathematically less involving and thus easier to implement. In contrast to the fixed-
size cell decomposition, variable-size cell decomposition will adapt to the complexity of
the environment, and therefore sparse environments will contain appropriately fewer cells,
consuming dramatically less memory.

6.2.1.3 Potential field path planning
Potential field path planning creates a field, or gradient, across the robot’s map that directs
the robot to the goal position from multiple prior positions (see [21]). This approach was
originally invented for robot manipulator path planning and is used often and under many
variants in the mobile robotics community. The potential field method treats the robot as a
point under the influence of an artificial potential field Uq() . The robot moves by follow-
ing the field, just as a ball would roll downhill. The goal (a minimum in this space) acts as
an attractive force on the robot and the obstacles act as peaks, or repulsive forces. The
superposition of all forces is applied to the robot, which, in most cases, is assumed to be a
point in the configuration space (see figure 6.5). Such an artificial potential field smoothly
guides the robot toward the goal while simultaneously avoiding known obstacles.
It is important to note, though, that this is more than just path planning. The resulting
field is also a control law for the robot. Assuming the robot can localize its position with
respect to the map and the potential field, it can always determine its next required action
based on the field.
The basic idea behind all potential field approaches is that the robot is attracted toward
the goal, while being repulsed by the obstacles that are known in advance. If new obstacles
appear during robot motion, one could update the potential field in order to integrate this
new information. In the simplest case, we assume that the robot is a point, thus the robot’s
θ
orientation is neglected and the resulting potential field is only 2D xy,( ) . If we assume
a differentiable potential field function Uq() , we can find the related artificial force F q()
,
acting at the position q = ( x y) .
F q() = – ∇ Uq() (6.1)

where Uq()∇ denotes the gradient vector of U at position . q