A computer program implements stochastic evolutionary algorithms for planning and optimizing collision-free paths for robots and their jointed limbs. Stochastic evolutionary algorithms can be made to produce acceptably close approximations to exact, optimal solutions for path-planning problems while often demanding much less computation than do exhaustive-search and deterministic inverse-kinematics algorithms that have been used previously for this purpose. Hence, the present software is better suited for application aboard robots having limited computing capabilities (see figure). The stochastic aspect lies in the use of simulated annealing to (1) prevent trapping of an optimization algorithm in local minima of an energylike error measure by which the fitness of a trial solution is evaluated while (2) ensuring that the entire multidimensional configuration and parameter space of the path-planning problem is sampled efficiently with respect to both robot joint angles and computation time. Simulated annealing is an established technique for avoiding local minima in multidimensional optimization problems, but has not, until now, been applied to planning collision-free robot paths by use of low-power computers.

A comparison of Digital Terrain Maps shows reachability of targets with the FIDO robotic arm. Green (light) areas are reachable, with arm path solutions. Grey areas are not reachable and red (dark) areas indicate no data available for a solution. (Note: FIDO is Field Integrated Design and Operations.)

This program was written by Wolfgang Fink, Hrand Aghazarian, Terrance Huntsberger, and Richard Terrile of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Software category.

This software is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42206.

This Brief includes a Technical Support Package (TSP).
Stochastic Evolutionary Algorithms for Planning Robot Paths

(reference NPO-42206) is currently available for download from the TSP library.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the September, 2006 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.