Overview

Having seen the difficulty of explicitly representing the configuration space, an alternative is to develop search algorithms that incrementally "explore" free space while searching for a path. Already, we have seen that the Bug algorithms maneuver through free space without constructing the configuration space, but the Bug algorithms are limited to simple two-dimensional configuration spaces. Therefore, this chapter introduces navigation planners that apply to a richer class of robots and produce a greater variety of paths than the Bug methods, i.e., they apply to a more general class of configuration spaces, including those that are multidimensional and non-Euclidean.

A potential function is a differentiable real-valued function . The value of a potential function can be viewed as energy and hence the gradient of the potential is force. The gradient is a vector which points in the direction that locally maximally increases U. See appendix C.5 for a more rigorous definition of the gradient. We use the gradient to define a vector field, which assigns a vector to each point on a manifold. A gradient vector field, as its name suggests, assigns the gradient of some function to each point. When U is energy, the gradient vector field has the property that work done along any closed path is zero.

The potential function approach directs a robot as if it were a particle moving in a gradient vector field. Gradients can be intuitively viewed as forces acting on a positively charged particle robot which...