Motion Planning in Virtual Environments

Contact: Mark Overmars

Student projects

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 demonstration program 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 tasks.
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.
The CAVE project 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.
The 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. Technical Report
  • M.H. Overmars, Algorithms for motion and navigation in virtual environments and games, Proceedings WAFR 2002, 2002.
  • R. Geraerts, M.H. Overmars, A comparative study of probabilistic roadmap planners, Proceedings WAFR 2002, 2002, Technical Report
  • M.H. Overmars, Motion planning in virtual environments, E. Deprettere, A. Belloum, J. Heijnsdijk, F. van der Stappen (Eds.): Proceedings ASCI 2002, 2002, pp. 15-21.
  • M.H. Overmars, 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. Technical Report
  • 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. Technical Report
  • 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. Technical Report
  • D. Sent, M.H. Overmars, Motion planning in an environment with dangerzones, Proc. IEEE Intern. Conf. on Robotics and Automation, 2001, pp. 1488-1493. Technical Report
  • 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. Technical Report
  • 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. Technical Report
  • 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. Technical Report
  • 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. Technical Report
  • P. Svestka, M.H. Overmars, Coordinated path planning for multiple robots, Robotics and Autonomous Systems 23 (1998), pp. 125-152. Technical Report
  • 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. Technical Report

For implementation and testing we have a lab available with modern top-end PC workstations with stereo viewing facilities. This lab was partially donated by Microsoft.

Student projects
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 Mark Overmars. For more information see the education page.

webmaster: Mark Overmars