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).

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 (W_{1}, W_{2}, ...) 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:

- Generate a straight-line path (s
_{1}) from the starting point (W_{1}) to the destination. - Using the collision-detection method described above, test for collisions along this path.
- If there is a collision (denoted by collision point c
_{1}), 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 (s_{2}and s_{3}) that connect a new waypoint (W_{2}) with the ends of s_{1}. - Test each new sub-path for collisions.
- If a collision is detected on either subpath (e.g., at collision point c
_{2}on s_{2}), then in the manner of step 3, generate new sub-sub paths (s_{21}and s_{22}) that connect new way point W_{3}with W_{1}and W_{2}. - 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.*