| This thesis concerns the use of artificial potential functions to solve the robot navigation problem in the context of perfect information. A class of potential functions--the navigation functions--is defined and shown to represent an exact solution to the problem. Essentially, these functions must have a unique minimum at the destination, be uniformly maximal on the obstacles' boundary, and be sufficiently smooth. Once a navigation function is constructed for a given obstacle course and desired destination, there is a natural and automatic way to derive from it a bounded-torque feedback control law for the robot. The resulting closed-loop robot system is guaranteed to approach the desired destination without hitting the obstacles. This methodology constitutes the only provably correct and, in principle, completely general alternative to the currently used method of first planning a collision-free path and then "forcing" the robot to follow it.;Several theoretical insights concerning the expressive capability of potential functions are derived. First, in general, the best that can be hoped for is convergence from almost any initial position (strict global convergence is impossible using potential functions). Second, in principle, navigation functions always exist. It is then shown that navigation functions are invariant under coordinate transformation (diffeomorphism). This, in turn, affords actual construction of navigation functions as exemplified in the remainder of the thesis.;Navigation functions are constructed on n-dimensional Euclidean sphere worlds, representing ideal obstacle course for a point-mass robot. The Euclidean sphere worlds serve as a "model" for their topological equivalence class. Navigation functions on the geometrically "complicated" spaces in this topological class are then constructed by "pulling back" a suitable prior construction on the corresponding model space via coordinate transformation. Coordinate transformations are constructed for progressively more complicated classes of n-dimensional spaces: the star worlds, star worlds with semianalytic obstacles, and the forests of stars. The last class turns out to be dense in the topologically deformed sphere worlds. The rich variety of shapes obtained by forests of stars is exemplified in the "floor plan", or "maze", picture furnished in Chapter 5.;The thesis concludes with a description of research in progress, concerning the construction of navigation functions for a simple rigid body. Even the latter case is only a small portion of the most general problem of navigating a general robot amidst arbitrarily shaped obstacles. Thus, the thesis is merely a precursor to a much larger program of research committed to construction of navigation functions for progressively more realistic robotic situations. |
