Planner Using Conditional Probability Guided Search
The first path planning algorithm is motivated by the need to reduce the computational burden involved in searching a graph of a deterministic representation of free configuration space available to a robot. This exact approach is practical only if the environment is static, if there are only a few degrees-of-freedom, long motion planning times are acceptable, and if fast computing resources are available.
The fast motion planning approach instead computes the probability of a successful motion of the robot through a region of space. This probability calculation is obtained from a geometric model that captures the effects of objects in the region and the kinematics of the robot arm. The notion of a Motion Transition Probability is defined, which captures the conditional probability of the robot arm moving in a collision free manner in the vicinity of a single obstacle in the environment, while ignoring the effect of all other obstacles. These conditional probablities are then used to guide an on-line search and results, in most cases, in the successful determination of a path within a reasonably short time.
The formal mathematics of this process is reminiscent of a diffusion process, and the algorithm itself can viewed as a Monte-Carlo approach to the solution of an equation for diffusion.
Planner Using Massively Parallel Energy Computations
The second path planning algorithm is motivated by similar needs and is applicable to solve the path planning problem when the robot system has a large number of degrees-of-freedom. It utilizes a massively parallel computational method suitable for implementation on a hypercube type multi-processor computer.
Each obstacle in the environment is described as the intersection of a number of bounding hyperplanes. Each hyperplane of the obstacle contributes to a potential energy term with respect to a number of control points on the robot arm. This energy term is designed such that the peak value is reached when the point on the robot arm is inside the obstacle, and tapers off in a sigmoidal manner as the point recedes from the interior of the hyperplane. A "temperature" parameter determines the rate of this decay, with a higher temperature indicated a slow decay. By taking the product of the energy terms defined for each bounding hyperplane, an overall collision energy term can be defined with respect to the obstacle.
Energy terms are computed for an entire path wherin the energy of the path is defined as the energy of the obstacle/control-point pair at each location along the path. These energy computations lend them to easy parallelization since the energy associated with each obstacle/control-point/path location set can be computed independently from parallel copies of a geometric world-model resident in each of the multi-processor nodes. A parallel gradient computation is then performed to determine repulsive forces along an initial candidate robot path. These forces push the path away from the obstacles towards collision free configurations as they work to minimize the overall path energy. To prevent the iterative process from getting stuck in local energy minima, the initial iterations of the path deformation algorithm are performed using a "high-temperature" model of the energy term. This has the effect of "smearing out" the energy landscape. The temperature parameter is then gradually cooled down as the iterations proceed, by which time local-minima are usually avoided.
The formal mathematics of this process is reminiscent of the simulated annealing method, and the energy term calculations can be thought of as mean-field approximations similar to those used in statistical mechanics.
References:
J. Balaram and H. Stone, ``Automated Assembly in the JPL Telerobot Testbed'', Intelligent Robotic Systems for Space Exploration, Chapter 8, Kluwer Academic Publishers, Norwell, MA, 1992.
Point of Contact:
J. Balaram
Mail Stop 198-219
Jet Propulsion Laboratory
4800 Oak Grove Drive
Pasadena, CA 91109
818-354-6770
j.balaram@telerobotics.jpl.nasa.gov
Telerobotics Program
page
Please email the site webmaster
with any comments, criticisms or corrections
for this page.
Maintained by: Dave Lavery
Last updated: May 10, 1996