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
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