We present a new methodology for exact robot motion planning and control that unifies the purely kinematic path planning problem with the lower level feedback controller design. Complete information about the freespace and goal is encoded in the form of a special artificial potential function – a navigation function – that connects the kinematic planning problem with the dynamic execution problem in a provably correct fashion. The navigation function automatically gives rise to a bounded-torque feedback controller for the robot’s actuators that guarantees collision-free motion and convergence to the destination from almost all initial free configurations. Since navigation functions exist for any robot and obstacle course, our methodology is completely general in principle. However, this paper is mainly concerned with certain constructive techniques for a particular class of motion planning problems. Specifically, we present a formula for navigation functions that guide a point-mass robot in a generalized sphere world. The simplest member of this family is a space obtained by puncturing a disc by an arbitrary number of smaller disjoint discs representing obstacles. The other spaces are obtained from this model by a suitable coordinate transformation that we show how to build. Our constructions exploit these coordinate transformations to adapt a navigation function on the model space to its more geometrically complicated (but topologically equivalent) instances. The formula that we present admits sphere-worlds of arbitrary dimension and is directly applicable to configuration spaces whose forbidden regions can be modeled by such generalized discs. We have implemented these navigation functions on planar scenarios, and simulation results are provided throughout the paper.
a subsidiary of the Penn Engineering GRASP Lab