Motion Planning in Virtual Environments for Multiple Entities

Contact: Mark Overmars

Automated motion planning (also referred to as path planning) is rapidly gaining importance in various fields. Originally the applications came mainly from robotics, but in the past few years many new applications arise in fields such as animation, computer games, virtual environments, and maintenance planning and training using industrial CAD systems. One of the prime techniques currently being used is the probabilistic roadmap approach (PRM). This flexible approach has been applied to many different motion planning problems dealing for example with robot arms, car-like robots and flexible objects.

Multiple Entities

In this project, supported by NWO, we will study the planning of simultaneous motions for many entities in the same environment, in particular in the context of virtual environments and games. For example, in the picture above a large number of entities must move through a gate. They each must plan their route, avoiding collisions with the obstacles. But they also must adapt their routes to each other to avoid collisions with other entities. The computed motion must look natural, that is, similar to motions human beings would execute.

The PRM approach has been used for problems with up to six robots, but it cannot directly be applied to large collections of moving entities. Our new approach will try to combine PRM with grouping and ungrouping operations in which collections of entities can temporarily be considered as one larger entity. Also, we plan to study the combination with flocking techniques, to achieve more natural collision avoiding strategies. This should lead to a new framework for path planning with multiple entities that is well suited for the application in virtual environments.

The project will primarily be carried out by Arno Kamphuis (PhD-student) under the supervision of prof. Mark Overmars.

For more information contact
Mark Overmars