Reliable robot motion planning

This thesis examines motion planning for robot manipulators and for free bodies, with an emphasis on reliable motion planning. An algorithm is reliable if its parameters may be specified to guarantee desired levels of performance. This enables a user or high-level planner to use an algorithm with confidence--a requirement for autonomous robotic systems. The objective of the thesis is the development of mathematical and algorithmic tools for analyzing the performance of planning algorithms. The basis for the study of reliable planning is the systematic analysis of approximation errors, which are common in planning and control algorithms. Fundamental to this study are bounds on the kinematics and dynamics of open-kinematic-chain manipulators. To express the bounds, we develop easily-computed, configuration-independent formulas. These allow the rigorous study of approximation errors for general manipulators and should prove useful for a wide variety of problems. General methods are presented to decompose planning and control tasks into sub-problems to which the bounds may be applied. These we demonstrate while presenting solutions to the following problems: the reliable interpolation of kinematic and torque trajectories, the generation of a free-space representation, and the analysis of nonlinear control algorithms. In addition, we present the first provably-good approximation algorithm finding a minimal-time trajectory for a manipulator subject to actuator torque constraints. The algorithm generates a trajectory that lags behind a globally optimal trajectory by a specified time-factor and is based on discretizing time and joint accelerations. We analyze this algorithm by treating the dynamics as being locally constant, with bounds on the error of this approximation. The above represent only a small number of the possible applications of our methods to the analysis of reliable algorithms. The thesis also investigates the geometrically complex problem of planning good orientation trajectories, given the orientation and angular velocity at certain times. Hence, splines are studied; in this case, however, the usual concepts are extended to curved spaces. This allows an intrinsic formulation for problems such as maneuvering a spacecraft or an undersea robot.