General techniques for constrained motion planning

This report presents automatic motion planning algorithms for robotic manipulators performing a variety of tasks. Given a task and a robot manipulator equipped with a tool in its hand, the motion planners compute robot motions to complete the task while respecting manipulator kinematic constraints and avoiding collisions with objects in the robot`s work space. To handle the high complexity of the motion planning problem, a sophisticated search strategy called SANDROS is developed and used to solve many variations of the motion planning problem. To facilitate systematic development of motion planning algorithms, robotic tasks are classified into three categories according to the dimension of the manifold the robot tool has to travel: visit-point (0 dimensional), trace-curve (1 dimensional) and cover-surface (2 dimensional) tasks. The motion planner for a particular dimension is used as a sub-module by the motion planner for the next-higher dimension. This hierarchy of motion planners has led to a set of compact and systematic algorithms that can plan robot motions for many types of robotic operations. In addition, an algorithm is developed that determines the optimal robot-base configuration for minimum cycle time. The SANDROS search paradigm is complete in that it finds a solution path if one exists, up to a user specified resolution. Although its worst-case time complexity is exponential in the degrees of freedom of the manipulator, its average performance is commensurate with the complexity of the solution path. Since solution paths for most of motion planning problems consist of a few monotone segments, the motion planners based on SANDROS search strategy show approximately two-orders of magnitude improvements over existing complete algorithms