Motion Planning in Complex CAD Models

Contact: Mark Overmars

Over the past years the functionality and use of CAD systems has rapidly increased. During the mid-80's, the first instances appeared of highly complex models that were entirely described via computer representations-for instance, the N4 model of a nuclear power plant, and the model of the Boeing 777. Since then it has become common practice to design complex models primarily by CAD systems.

Industrial Scene

Current CAD systems are mainly designed to facilitate construction and to test functionality. For the design of individual objects this suffices. When designing complex models, like complete industrial installations, however, one would like the CAD system to provide further functionality. One desirable extension of the functionality is motion support: the system should support the designer or operator to make decisions about transportation of objects through the model. This can, for example, be used to determine the feasibility of various maintenance and replacement operations.

In this project, supported by NWO, we will develop algorithmic techniques for motion support that can be used in such a system. The approach will be based on the probabilistic path planner that has been developed in Utrecht over the past years for solving motion planning problems for various robots. The probabilistic path planner consists of a local planner that solves simple, local motion planning questions, combined with a global planner that combines local solutions into a global structure. To apply the probabilistic path planner to motion support in CAD models, both the local and the global planner must be completely redesigned, leading to a large number of yet unsolved research questions:

  • Due to the complexity of the CAD models, the local planner must be extremely fast (but needs not be complete). To achieve this it is required to develop efficient collision checkers that take the type of generated paths into account, and fast algorithms for performing distance calculations. To make the local planner suitable in the application, we need to design algorithms to optimise (computer-generated or user-defined) paths, taking various quality measures into account.
  • For efficiency reasons, the global planner must carefully analyse the problem, to decided where to apply the local planner. It must also combine the motion of the object with those of the handling devices, such as mobile platforms or gantries, that move the object. Finally, it must provide feedback to the operator to assist in making decisions (like the removal of certain obstacles).

The project will lead to new algorithmic techniques for these problems and to an implementation of these techniques that is interfaced to a commercial CAD system, such that the feasibility of the approaches can be tested in practise.

The project will primarily be carried out by Herman Haverkort (PhD student) and Roland Geraerts (PhD student) under the supervision of dr. Mark de Berg and prof. Mark Overmars.

For more information contact
Mark Overmars