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.
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?
Overview
The document discusses the application of evolutionary computation technologies in the design and optimization of complex space systems, particularly focusing on the work conducted by the Evolvable Computation Group at NASA's Jet Propulsion Laboratory (JPL). The group employs biologically inspired techniques, such as genetic algorithms and simulated annealing, to enhance the design processes of spacecraft and robotic systems.
The introduction outlines the challenges of complex engineering design, which often involves multi-parameter optimizations where traditional physics models predict outcomes based on various input parameters. The document emphasizes that directly deriving optimal solutions from these models is often impractical. Instead, the group advocates for a parallelized approach that mimics biological evolution, utilizing a large population of varying input parameters to explore design spaces more effectively than human designers or deterministic algorithms could.
The document details the development of tools that automate innovation and design, significantly reducing redesign costs and schedules. By leveraging evolutionary computation, the group has demonstrated improvements in human design capabilities for space systems, showcasing the potential for automated systems to adapt and optimize during missions.
Additionally, the document highlights the novel capability of fully automated gyro tuning, which allows ultra-low mass and ultra-low-power Inertial Measurement Unit (IMU) systems to calibrate themselves autonomously during missions, such as those involving the Mars Ascent Vehicle. This advancement represents a significant step forward in the autonomy and efficiency of space missions.
The acknowledgments section credits the support from NASA's Research and Technology Development Program and other funding sources, underscoring the collaborative nature of the research. The references provided at the end of the document include foundational texts and previous studies that inform the current research, illustrating the ongoing evolution of computational techniques in aerospace applications.
In summary, the document presents a comprehensive overview of how evolutionary computation can revolutionize the design and optimization of space systems, enabling more efficient, autonomous, and innovative solutions for future missions. The work at JPL exemplifies the intersection of biology, engineering, and computer science in addressing complex challenges in aerospace technology.
