Homepage > Motion planning > List of publications > Paper

One of the fundamental tasks robots have to perform is planning their motions while avoiding collisions with obstacles in the environment. This is the central topic of the thesis. We restrict ourselves to motion planning for two- and three-dimensional rigid bodies and articulated robots moving in static and known virtual environments.

Combining Path Planners and Motion Graphs

Generation of locomotion along a smooth obstacle-free path.

Generation of locomotion along a smooth obstacle-free path.


Natural locomotion of virtual characters is very important in games and simulations. The naturalness of the total motion strongly depends on both the path the character chooses and the animation of the walking character. Therefore, much work has been done on path planning and generating walking animations. However, the combination of both fields has received less attention. Combining path planning and motion synthesis introduces several problems. In this paper, we will identify two problems and propose possible solutions.

The first problem is selecting an appropriate distance metric for locomotion synthesis. When concatenating clips of locomotion, a distance metric is required to detect good transition points. We have evaluated three common distance metrics both quantitatively (in terms of footskating, path deviation and online running time) and qualitatively (user study). Based on our observations, we propose a set of guidelines when using these metrics in a motion synthesizer.

The second problem is the fact that there is no single point on the body that can follow the path generated by the path planner without causing unnatural animations. This raises the question how the character should follow the path. We will show that enforcing the pelvis to follow the path will lead to unnatural animations and that our proposed solution, which uses path abstractions, generates significantly better animations.


  • Ben J.H. van Basten, Arjan Egges and Roland Geraerts. Combining Path Planners and Motion Graphs. Computer Animation and Virtual Worlds (CAVW), 22(1):59-78, 2011.