Decomposition-based Motion Planning

Oliver Brock

To get a quick impression...

The following two videos give you an impression of what decomposition-based motion planning is about:
This video (1MB) shows a robot moving in a dynamic environment. Planning and replanning for an 11 dof manipulator are performed in real-time.
In this one (1.3MB) a second robot is moving into the path of the first one. Again, all motion in generated in real-time.
If you get curious, just read on.

Other pages:    Elastic Strips    Global Dynamic Window    Homepage

Introduction to Decomposition-based Motion Planning

Motion planning is dealing with the problem of generating a motion for a robot so that a certain task is accomplished. We are all familiar with robots assembling cars and the problem of generating motion to accomplish such a task is pretty well understood. In this particular application we can take advantage of the fact that the entire environment - in this case the factory floor - is a very controlled environment. The assumption that all obstacles and their location are known at all times is a reasonable one. If we want to use robots in environments like hospitals, construction sites, and other populated places this assumption does not hold any more. People move around, walls are built, material is unloaded and so on.

Most motion planning algorithms take a snapshot of the environment and determine a motion for this static description of reality. Since it takes them a significant amount of time to generate a motion, the environment might change even before the motion is computed. But even if we assume that it has not changed, the execution of a motion can take minutes or hours and during that period the environment has to remain unchanged for the motion to remain valid. If the environment changes, the precomputed motion might actually cause the robot to crash into an obstacle that has changed its location. This problem is particularly difficult to solve when the robot has many joints, also called degrees of freedom. The more joints a robot has, the more computation is generally needed to determine a motion. As a result, motion planning for robots with many degrees of freedom operating in dynamic environments is a difficult and so far mostly unsolved problem.

Decomposition-based motion planning is a new approach to motion planning and motion generation addressing this difficult problem. Below is a sequence of images, illustrating how this approach can generate motion for a robot moving in a dynamic environment. The robot is a free-floating Mitsubishi PA10 robot arm with a total of 11 degrees of freedom. The task is to move the robot from its initial position, shown in the first image, to the top-most corner of the example environment. The white lines indicate some intermediate computation used to determine the motion (details about how this works can be found in the papers listed below). In the second image the robot has moved along what originally was the shortest path to the goal. But now the red obstacle is blocking that path. While the robot is moving, however, an alternative path was computed, as shown in the third image. This has happened so fast that the robot did not have to stop.

The next two images show two more paths computed in real-time in reaction to obstacles blocking the previous one. The last image shows the robot at its goal configuration. This video (1MB) shows the entire motion of the robot. Notice how little time passes between the obstacles appearing and a new path being computed. Each time the white lines change, a new path has been computed.

This is another video (1.3MB) showing how decomposition-based motion planning works. This time another robot is moving through the path of the Mitsubishi PA10 and the path to the goal is recomputed during the execution of the motion.

So how does it work? How can decomposition-based motion planning compute the motion in real-time, when we said before that it takes a lot of computation, in particular for a robot with many degrees of freedom, like our free-floating PA10?

The details can be found in the papers below, but here is the basic idea: Rather than computing the motion in the high-dimensional space associated with all the degrees of freedom, the overall motion planning problem is decomposed into two problems, a low-dimensional one, which is fairly easy to solve, and a high-dimensional one, yielding a solution to the original problem. Instead of solving it from scratch, though, we can use the solution to the simpler problem to significantly reduce the computations required for the original problem. This speeds up the process so much that it can be computed in real time.

In other words, we first determine a set of homotopic paths in the workspace, without searching the configuration space. Workspace criteria based on the geometry of the robot are employed to determine whether the set is likely to contain a solution path or not. Using this set of homotopic paths the search in the high-dimensional configuration space can be restricted to a small area. Potential field-based approaches can now be used to determine a path in the joint space of the robot. Rather than exploring the entire configuration space, we reactively explore a small subset of it. This approach is obviously not complete, but we consciously trade completeness for efficiency.

Decomposition-based motion planning and elastic strips are versatile frameworks that will find application in many domains beyond robotics, like virtual prototyping, character animation, haptic display of virtual environments, multi-robot workcells, and molecular biology. The ability to generate motion for multi-link objects in dynamic environments is a big challenge in those areas, which can be addressed using these approaches.

For a similar approach by Foskey, Garber, Lin, Manocha.


Last modified on November 13, 2001 by Oliver Brock
v1 v2 v3 v4
Visitors since November 8, 2001: provided by