The OxSim Planner Framework

Research into motion planning has occupied many researchers for some years; still commercial uses of automated motion planning are few and far between. Two reasons for this are as follows:

Speed. Motion planning has a reputation for being slow. Although motion planners have increased significantly in speed over the last few years, speed is still not at the level to make potential users embrace the technology.
Utility. Potential users are potential users because they have hard motion planning problems to solve. These problems are complex because of the clearances required - they can't easily solve the problem by looking at a motion simulation - or because of the sheer geometric complexity of the problem, or both. The practical needs of these users must be addressed if motion planning is to leave the research laboratory.

We contend that these problems can be addressed by separating out the issues of geometry and geometric calculation from those of planning. For example, a simple planning strategy for a robot manipulator first decides how we would like to move the payload, and then tackles the problem of moving the links of the manipulator in order to move the payload. In turn, when moving the manipulator we might come up with a strategy like "keep all of the links above the objects on the table, until we want to move the payload down, when we keep links 2 and 3 between objects 3 and 7". Further, this strategy should work for a reasonable range of complexity of the shapes of the interesting objects and links; only the geometric calculations involved will get harder.

We have designed the OxSim framework in order to test this contention. OxSim assumes that a high-level planner exists that is capable of planning strategies, and that to test the strategies the high-level planner will call a low-level planner within the core of OxSim. The figure here shows these components, and several different combinations of high-level and low-level planners have been tested within the framework. To handle the geometry, we import geometric models and rely on a module that can calculate efficiently the minimum distance between parts of the robot and parts of its environment to act as the glue between geometry and planning.

So far OxSim has proved to us the utility of separating geometry from planning in this way. New path planning systems can be quickly prototyped, and tested on scenes of realistic geometric complexity - here and here are two snapshots of the output of OxSim when planning paths for an unusual manipulator (a mechanical digger), and an MPEG movie is also available (64223 bytes) for a motion that took 20s to plan on an SGI Indy R4600. The motion goal is the red dot in the trench to the left of the picture. The steelwork around the digger has been especially chosen to make the planner's work difficult. A coarse sequence of via points is provided for the shovel; the planner attempts to find a path that takes the shovel near to the via points, whilst keeping the rest of the digger collision-free.

The planner above uses our virtural springs local planner. We have also been experimenting with other local and high-level planners, and MPEG movies are available that show planners based on simulated annealing [92232 bytes, 17s planning time] and on a directed search with backtracking [68839 bytes, 7s planning time]. These planners work fast when they succeed, but the plans would require smoothing before execution on a real robot.

Although our current system uses polyhedral models, all that should be required to move to scenes with curved geometry would be to provide new distance functions that work on that geometry. (Constructing such distance functions is an open research issue that we are starting to tackle.)

We expect to experiment more with OxSim over the coming few months, a to produce some form of public release in the late summer of 1996. OxSim is written in C++.

References

Towards Efficient Motion Planning for Manipulators with Complex Geometry, ISATP'95, August 1995. [isatp95.ps.gz: 131069 bytes compressed postscript].
Dealing with Geometric Complexity in Motion Planning, part of the Workshop on Practical Motion Planning in Robotics which was held in conjunction with ICRA 96, Minneapolis, 23rd April 1996. [icra96.ps.gz: 271592 bytes compressed postscript].
Building Bridges, a short essay on why we should be striving for simplicity in our robotic planning systems.