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.
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
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)
Roland Geraerts (PhD student)
under the supervision of
dr. Mark de Berg
prof. Mark Overmars.
For more information contact