The Optimization of Robot Motion in the Presence of Obstacles.

摘要

In this thesis we develop a general algorithm for optimizing robot motion in the presence of obstacles. It can incorporate useful measures of system performance, accurate descriptions of motion, fixed or time-dependent boundary conditions, general state and control constraints, and most importantly, obstacle avoidance. The main idea is to express obstacle avoidance in terms of the Euclidean distance between potentially colliding objects. The mathematical properties of the distance as a function of system configuration are studied, and it is seen that various types of derivatives are easily characterized. The results lead to the formulation of optimal-path planning as a problem in optimal control. Our solution approach is straightforward. It relies on a spline function representation of paths in configuration space to parameterize the problem and exactly satisfy both the equations of motion and the boundary conditions. The constraints on the state and control and those corresponding to obstacle avoidance are easily evaluated in terms of the spline parameters, and are imposed using penalty methods. Local solutions are obtained using a modified BFGS optimization algorithm. As part of the optimal-path planning procedure, we develop an efficient and reliable (in the presence of round-off errors) algorithm for computing the distance between objects in three-dimensional space. For convex polytopes with known vertices, the algorithm terminates after a finite number of steps with highly accurate results and exhibits only small linear growth in computational time as the total number of vertices in a polytope pair is increased. The main advantages of the presented algorithmic approach to optimal-path planning is its generality, its comprehensive treatment of obstacles and its production of a smooth approximation to the optimal configuration and input time histories. The computations are expensive, but realistic and practical results are achieved. Examples are given which include minimum-energy and minimum-time problems involving a Cartesian manipulator and a system of two cylindrical manipulators cooperatively interacting in a three-dimensional workspace.