An algorithm has been developed to enable a computer aboard a robot to autonomously plan the path of the manipulator arm of the robot to avoid collisions between the arm and any obstacle, which could be another part of the robot or an external object in the vicinity of the robot. In simplified terms, the algorithm generates trial path segments and tests each segment for potential collisions in an iterative process that ends when a sequence of collision-free segments reaches from the starting point to the destination. The main advantage of this algorithm, relative to prior such algorithms, is computational efficiency: the algorithm is designed to make minimal demands upon the limited computational resources available aboard a robot.

This path-planning algorithm utilizes a modified version of the collision-detection method described in "Improved Collision-Detection Method for Robotic Manipulator" (NPO-30356), NASA Tech Briefs, Vol. 27, No. 3 (June 2003), page 72. The method involves utilization of mathematical models of the robot constructed prior to operation and similar models of external objects constructed automatically from sensory data acquired during operation. This method incorporates a previously developed method, known in the art as the method of oriented bounding boxes (OBBs), in which 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).

A Multi-Segment Path is generated in an iterativeprocess of generating candidate segmentsand testing them for collisions.
A multiresolution OBB/OBP representation of the robot and its manipulator arm and a multiresolution OBB representation of external objects (including terrain) are constructed and used in a process in which collisions at successively finer resolutions are detected through computational detection of overlaps between the corresponding OBB and OBP models. For computational efficiency, the process is started at the coarsest resolution and stopped as soon as possible, preferably before reaching the finest resolution. At the coarsest resolution, there is a single OBB enclosing all relevant external objects and a single OBB enclosing the entire robot. At the next finer level of resolution, the coarsest-resolution OBB is divided into two OBBs, and so forth. If no collision is detected at the coarsest resolution, then there is no need for further computation to detect collisions. If a collision is detected at the coarsest resolution, then tests for collisions are performed at the next finer level of resolution. This process is continued to successively finer resolutions until either no more collisions are detected or the finest resolution is reached.

The path-planning algorithm operates on a representation of the robot arm and obstacles in a Cartesian coordinate system. The figure schematically depicts a simplified example of the geometric effects of the algorithm. In this example, the robot arm has been commanded to move from a starting point to a destination. The problem to be solved by the algorithm is to choose waypoints (W1, W2, ...) and straight-line path segments connecting the waypoints (including the starting point and destination as waypoints) so that there is no collision along any segment. The algorithm can be summarized as follows:

  1. Generate a straight-line path (s1) from the starting point (W1) to the destination.
  2. Using the collision-detection method described above, test for collisions along this path.
  3. If there is a collision (denoted by collision point c1), then by use of a geometry-based subalgorithm too complex to be described within the space available for this article, generate two new sub-paths (s2 and s3) that connect a new waypoint (W2) with the ends of s1.
  4. Test each new sub-path for collisions.
  5. If a collision is detected on either subpath (e.g., at collision point c2 on s2), then in the manner of step 3, generate new sub-sub paths (s21 and s22) that connect new way point W3 with W1 and W2.
  6. Test for collisions and generate new path segments in the manner described above until the starting and destination points are connected by collision-free path segments. In this example, the result is a total of seven waypoints connected by six path segments.

This work was done by Paul Backes and Antonio Diaz-Calderon of Caltech for NASA's Jet Propulsion Laboratory. The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-41697.