An improved method has been devised for the computational prediction of a collision between (1) a robotic manipulator and (2) another part of the robot or an external object in the vicinity of the robot. The method is intended to be used to test commanded manipulator trajectories in advance so that execution of the commands can be stopped before damage is done. The method involves utilization of both (1) mathematical models of the robot and its environment constructed manually prior to operation and (2) similar models constructed automatically from sensory data acquired during operation. The representation of objects in this method is simpler and more efficient(with respect to both computation time and computer memory), relative to the representations used in most prior methods.

Figure 1. A Rodlike Robot Arm of Circular Cross Section, viewed here along its axis, can be represented by an octagonal OBP assembled from four smaller OBBs.
Figure 2. A Hierarchy of OBBs of successively finer resolution is used to represent terrain elevation as a function of horizontal coordinates.
The present method was developed especially for use on a robotic land vehicle (rover) equipped with a manipulator arm and a vision system that includes stereoscopic electronic cameras. In this method, objects are represented and collisions detected by use of a previously developed technique known in the art as the method of oriented bounding boxes (OBBs). As the name of this technique indicates, an object is represented approximately, for computational purposes, by a box that encloses its outer boundary. Because many parts of a robotic manipulator are cylindrical, the OBB method has been extended in this method to enable the approximate representation of cylindrical parts by use of octagonal or other multiple-OBB assemblies denoted oriented bounding prisms (OBPs), as in the example of Figure 1. Unlike prior methods, the OBB/OBP method does not require any divisions or transcendental functions; this feature leads to greater robustness and numerical accuracy. The OBB/OBP method was selected for incorporation into the present method because it offers the best compromise between accuracy on the one hand and computational efficiency (and thus computational speed) on the other hand.

OBBs are also used to represent the terrain and any objects on the terrain sensed by the stereoscopic vision system. A conceptual multiresolution map pyramid of the manipulator work space is computed from the stereoscopic sensory data and is then used in a coarse-to-fine sequence to detect collisions between the manipulator and terrain. As described next, tests for collisions are performed in a hierarchical sequence to minimize the amount of computation needed to detect collisions.

Starting with the second-highest level of the pyramid, each level is characterized by twice the horizontal spatial resolution of the level above it (see Figure 2). For example, at the highest level of the pyramid (coarsest resolution) there is a single terrain OBB that encloses all of the sensed data points. The model for each manipulator link is one low-resolution OBP. If no collisions between any of the OBPs and the coarsest-resolution terrain OBB are detected, then there is no need for further computation to detect collisions with terrain. On the other hand, if collisions are detected at the coarsest resolution, then tests for collisions are performed on each of the terrain OBBs at the second coarsest resolution. This process continues to successively finer levels of resolution until the finest resolution is reached or no more collisions are detected. Similar tests for collisions are performed with a similarly hierarchical model of the non-manipulator parts of the robot (body, cameras, sensors, suspension, and wheels).

This work was done by Chris Leger of Caltech for NASA’s Jet Propulsion Laboratory.