Manipulator collision avoidance by dynamic programming

Abstract

Automated planning of robotic manipulators' paths through a complex workspace is a capability of great importance to industry. Increasingly complex robot applications and workspaces make trial and error human path planning unfeasible. Furthermore, off-line simulation planning decreases downtime and setup time of actual hardware, increasing utilization and profits. This thesis presents the details of a research effort to develop an antomated collision avoidance trajectory planner for robotic manipulators. The desired system would be able to automatically generate paths for a six degree-of-freedom industrial robot that would not collide with obstacles in its workspace, including fixtures, workpieces, and other manipulators. Further goals of the project were to develop a system that would be able to address any number of degrees of freedom and any type of robot joint system, that paths should be both safe and efficient, and that solutions should be robust in the face of possibly changing problem conditions. The method used was to formulate the robotic system in terms applicable to dynamic programming methodology. This involved discretizing the range of motion of the robotic system, and linking the resultant admissible states into a transition network. Penalties in the network were based upon the probability of a collision occurring at each state in the network, and upon the distances which must be travelled between the states. The principles of dynamic programming were then applied to this transition network representation. The resultant optimal policy was a list of commands which yield the optimal safe path through the network. It was found that once this optimal policy was generated, a safe path to the goal position of the manipulator had been determined for any arbitrary initial configuration of the manipulator. Furthermore, the method was equally applicable to any type of automated system. Examples are presented for a two-link planar manipulator, a planar rover free to rotate and translate in a plane, and a six-link PUMA 560 industrial manipulator. Computational burden is shown to be kept to a reasonable level by intelligent generation of the transition network with a minimum of states.