In robotics, one popular way of treating the motion planning problem is to map the robot to a point in an appropriate configuration space (Udupa 1977, Lozano-Perez 1981), representing the robot's kinematic state. For example, the robot manipulator's configuration space can be the joint angles defining its kinematic state. Using this representation, the path planning problem involves going from a starting configuration (a point in configuration space) to an ending configuration. The robot path planning problem is reformulated as the problem of moving a point in configuration space to some goal state.

Obstacles can be mapped from their positions in Cartesian space to sets of points in configuration space. Because a robot, in a given configuration, actually occupies a volume in space, obstacles must be dilated appropriately if we wish to plan a path for a single point in configuration space. In practice, we can use a fixed lookup table, describing the inverse kinematics of the robot in question, to do this. If a point in Cartesian space is occupied by an obstacle, this table identifies all configurations of the robot that intersect the obstacle.

To generate a reach, or to navigate a mobile robot, we use a harmonic potential function defined on a discrete configuration space grid in which obstacles are held at a potential of 1, and goals are held at a potential of 0. The function used is called harmonic because its value at any point is the average of values in the immediate neighborhood (Connolly and Grupen 1993). The resulting function behaves like a rubber sheet. Its only minima are at the goal points. This function also has an important probabilistic interpretation for robot control: the value of the function at any point is the hitting probability, i.e. the probability of hitting an obstacle before reaching a goal if the robot where to execute a random walk (Connolly 1994). Therefore, descending the steepest gradient in the harmonic potential function minimizes the probability of hitting an obstacle before reaching the goal.

Here's a Mathematica plot of a harmonic function:

In this function, there are three goals pulled down to a potential of 0. The outer rim plus a rectangular "obstacle" near the middle are pulled up to a potential of 1. Harmonic functions are examples of minimal surfaces. These are surfaces whose mean curvature vanishes everywhere.

Gradient descent of the function produces paths through the configuration space. For a robot arm, this is a collision-free reach, for a mobile robot, the motion is an obstacle-avoiding trajectory across terrain. Wheeled vehicles present some special problems, since they are examples of nonholonomic mechanical systems, but this same basic approach can be used there as well. Harmonic functions can be computed using resistive networks. This basic idea forms the foundation for a neuroscientific model of motion control in the basal ganglia in the animal brain. For more information, consult the lab publications .

Back to the LPR Research Glossary