Contact: Mark Overmars
Virtual Environments are used increasingly in a variety of applications, ranging
from CAD/CAM and simulation to computer-aided instruction and computer entertainment.
In many of these environments entities need to move around. For example, in
maintenance operations in factories we want to use the CAD models
to plan the removal of malfunctioning parts, in large scale computer simulations
there are computer controlled entities whose motion needs to be planned, and in
games the motions of (large groups of) opponents must be determined. Such motions
need to be effective and natural to enhance the feeling of immersion of the user/student/player.
The motion planning problem is a difficult one to solve. We created a
to give people a feeling of how difficult motion planning is. You can download it for free.
(It actually makes an interesting game.) In our research we adapt techniques for motion planning,
originally developed for robot motion planning, to problems in virtual environments. In particular
we use the probabilistic roadmap planning approach which we developed over the past couple
of years in collaboration with Stanford University and LAAS in Toulouse.
The MOVE-ME project,
funded by NWO, studies motion planning in virtual environments for multiple entities.
The goal is to develop techniques that make it possible to automatically plan the motion
of a large number of entities through a virtual environment. The motions should be
effective and natural.
The MOCCAM project,
funded by NWO/EW, deals with motion planning problems in huge CAD models.
Emphasis lies on efficient algorithms and data structures for e.g. collision detection and on
techniques for more efficiently computing paths. Also we will work on planning manipulation
The MOVIE project,
funded by the EU, is a new project that has started on January 1st, 2003.
It is a collaboration between four groups in the Netherlands, France and Israel. The
project is aimed at providing a framework for motion planning in virtual environments dealing
with real-time planning, dynamically changing scenes, multiple entities, and articulated motion
and manipulation problems.
studies the use of motion planning techniques to steer cameras in virtual
environments. These techniques releave the use of e.g. architectural walk-throughs of the need
to directly control the camera using the mouse or keyboard. Instead they can specify goal
positions and a smooth motion for the camera is automatically computed.
MOLOG project, funded by the EU, is a collaboration between
four groups in the Netherlands, France and the UK, to apply motion planning technology to
maintenance tasks in industrial CAD models. An important role for our group in this project
is to deal with the quality (length, smoothness) of the resulting motions. As part of this
project we developed a software environment (called SAMPLE) for easy implementation and testing
of motion planning algorithms. The project was concluded early 2002.
The following people are involved in this research area:
Here you find a list of recent publications in this area:
D. Niewenhuisen, M.H. Overmars,
Motion planning for camera movements in virtual environments.
Algorithms for motion and navigation in virtual environments and games,
Proceedings WAFR 2002,
R. Geraerts, M.H. Overmars,
A comparative study of probabilistic roadmap planners,
Proceedings WAFR 2002,
Motion planning in virtual environments,
E. Deprettere, A. Belloum, J. Heijnsdijk, F. van der Stappen (Eds.):
Proceedings ASCI 2002,
2002, pp. 15-21.
Recent developments in motion planning,
P.Sloot, C. Kenneth Tan, J, Dongarra, A. Hoekstra (Eds.):
Computational Science - ICCS 2002, Part III,
Springer-Verlag, LNCS 2331, 2002, pp. 3-13.
M. de Berg, M. Katz, M.H. Overmars, A.F. van der Stappen, J. Vleugels,
Models and motion planning,
Comput. Geom.: Theory and Applications,
23 (2002), pp. 53-68.
P. Agarwal, M. de Berg, J. Gudmundsson, M. Hammar, H.J. Haverkort,
Box-trees and R-trees with near-optimal query time,
Proceedings of the 17th ACM Symposium on Computational Geometry,
2001, pp. 124-133.
D. Sent, M.H. Overmars,
Motion planning in an environment with dangerzones,
Proc. IEEE Intern. Conf. on Robotics and Automation,
2001, pp. 1488-1493.
V. Boor, M.H. Overmars, A.F. van der Stappen,
The Gaussian sampling strategy for probabilistic roadmap planners,
Proceedings IEEE Intern. Conf. on Robotics and Automation,
1999, pp. 1018-1023.
R.-P. Berretty, M.H. Overmars, A.F. van der Stappen,
Dynamic motion planning in low obstacle density environments,
Comput. Geom.: Theory and Applications
11 (1998), pp. 157-173.
A.F. van der Stappen, M.H. Overmars, M. de Berg, J. Vleugels,
Motion planning in environments with low obstacle density,
Discr. Comput. Geometry
20 (1998), pp. 561-587.
S. Sekhavat, P. Svestka, J.-P. Laumond, M.H. Overmars,
Multilevel path planning for nonholonomic robots using semiholonomic subsystems,
Int. Journal of Robotics Research
17 (1998), pp. 840-857.
P. Svestka, M.H. Overmars,
Coordinated path planning for multiple robots,
Robotics and Autonomous Systems
23 (1998), pp. 125-152.
P. Svestka, M.H. Overmars,
Probabilistic path planning,
in: J.-P. Laumond (ed): Robot Motion Planning and Control,
Lect. Notes in Control and Information Sciences 229, Springer-Verlag, 1998, pp. 255-304.
For implementation and testing we have a
available with modern top-end PC workstations with stereo
viewing facilities. This lab was partially donated by Microsoft.
There are ample opportunities for students to do master projects in this area.
The list above gives a number of research themes. The projects can both be
theoretically oriented and more experimental in nature.
The lab is available for the students to work in. If you are interested, contact
For more information see the
webmaster: Mark Overmars