Project number:
Project acronym:
Title: / IST-2001-39250
MOVIE
Motion Planning in Virtual Environments
Deliverable No: D 1.14: Project presentation
Short description:
This deliverable gives a project presentation, consisting of a two-page document describing the project and two PowerPoint slides.
Due month:
Delivery month:
Partners owning:
Partners contributed:
Classification: / 6
6
UU/CNRS-LAAS/TELAVIV/KINEO
UU/CNRS-LAAS/TELAVIV/KINEO
Internal


Project funded by the European Community under the “Information Society Technologies” Programme (1998-2002).

MOVIE is a shared-cost RTD (FET-Open) project from the Information Society Technologies (IST) programme from the European Community under contract number: IST-2001-39250.

Project Presentation

Project abstract

Motion planning, also termed path planning, plays an increasingly important role in virtual environment applications. Multiple autonomous entities must navigate through virtual worlds and need to plan their own routes and motions. The goal of this project is to develop motion planning techniques that are suitable for these applications. The developed techniques will need to have real-time performance and deal with

  • large, complex environments
  • dynamic changes in the environment
  • the complicated kinematic structure of some of the entities
  • simultaneous planning for multiple moving entities
  • path quality and natural constraints on the allowed motions

Objectives

The overall objective of this project is to develop motion planning techniques that can compute in real time visually-convincing motions for multiple autonomous entities that navigate through complex virtual worlds. To this end we will develop new motion planning algorithms that

  • after pre-processing have real-time performance in large and complex environments
  • can deal with dynamic changes in the environment
  • can plan simultaneous motions of large groups of moving entities
  • can plan motions for highly-articulated bodies and other complicated kinematic structures
  • create effective and visually-convincing motions

The algorithms will be integrated in a demonstrator and evaluated on realistic scenarios.

Description of the work

Motion planning, also termed path planning, plays an increasingly important role in virtual environment applications. Multiple autonomous entities must navigate through virtual worlds and need to plan their own routes and motions. The goal of this project is to develop new motion planning techniques that are suitable for these applications. Although the current motion planning techniques are capable of planning motions in fairly complex environments, the applications in virtual environments are much more demanding than what the current technology can offer, and new algorithms need to be developed to deal with their specific constraints. In particular we will study the following aspects:

Robust real-time motion planningIn virtual environment applications, after pre-processing, real-time performance is required, while the environments are large and often dynamic. The techniques must be robust in the sense that they capture the possible motions well. Also, the resulting motions must look natural and be short. We will develop new, improved planning approaches to reach these objectives.

Planning in dynamic environmentsAlthough virtual environments are largely static, dynamic changes in the environment do occur, e.g. a door is opened or a fire appears. To handle such changes at interactive rates we will develop dynamic algorithms for motion planning that can incorporate such changes at little cost.

Coordinated motion for multiple entitiesMultiple entities must often navigate through the same environment. Rather than computing the motions for the individual entities we need to treat the group as a whole to obtain natural group behavior. To this end we will develop hybrid techniques than combine flocking approaches with motion planning.

Highly-articulated bodiesEntities in virtual environments, like animated human characters, can have a complex kinematic structure with cycles. External navigational motion must be combined with internal articulated motion in a natural way. We will study techniques to create natural looking motion for such entities.We will also develop techniques for planning simple manipulation operations.

To solve these problems we will use a combination of techniques from motion planning, computational geometry, and combinatorial algorithms. The algorithms will be integrated in a demonstrator which will be evaluated on realistic scenarios through a number of industrial contacts. When the project is successful, the resulting techniques will become applicable in computer games, safety training applications, walkthroughs for architectural design and urban planning, training and planning for surgical procedures, and the design and maintenance of installations using CAD systems.

Milestones and expected results

The following results are expected

  • robust real-time motion planning algorithms that deal with complicated scenes
  • algorithms that can handle dynamic changes in the environment
  • algorithms that plan paths for multiple moving entities
  • algorithms that compute motions for complex articulated bodies
  • a demonstrator integrating these techniques
  • evaluation results on realistic scenarios

Participating sites

The following sites participate in the project:

  • UtrechtUniversity, Utrecht, the Netherlands, site leader: Mark Overmars
  • CNRS-LAAS, Toulouse, France, site leader: ThierrySimeon
  • TelAvivUniversity, Tel Aviv, Israel, site leader: Dan Halperin
  • Kineo-CAM, Toulouse, France, site leader: Carl van Geem

Support

This work is partially supported by the IST Programme of the European Union:

Total cost: 1,200,000 Euro

Community funding: 825,000 Euro

Project start:Jan 1st 2003

Duration:36 months

Coordinator contact details

Mark H. Overmars
Institute of Information and Computing Sciences, Utrecht University
P.O.Box 80.089, 3508 TB Utrecht, the Netherlands
email: tel. +31-30-2533736