Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Space-time Group Motion Planning

Our technique can successfully handle such challenging scenarios by planning in both space and time.


We present a novel approach for planning and directing heterogeneous groups of virtual agents based on techniques from linear programming. Our method efficiently identifies the most promising paths in both time and space and provides an optimal distribution of the groups' members over these paths such that their average traveling time is minimized. The computed space-time plan is combined with an agent-based steering method to handle collisions and generate the final motions of the agents. Our overall solution is applicable to a variety of virtual environment applications, such as computer games and crowd simulators. We highlight its potential through a wide range of test-case scenarios and evaluate the results from our simulations using a number of quantitative quality metrics. In practice, our system runs at interactive rates and generates smooth and optimal crowd flows under a variety of conditions.


  • Ioannis Karamouzas, Roland Geraerts and A. Frank van der Stappen. Space-time Group Motion Planning. In Workshop on the Algorithmic Foundations of Robotics (WAFR2012), Algorithmic Foundations of Robotics X, Springer Tracts on Advanced Robotics Vol 86, pp. 227-243, 2013.

    Full text Full text YouTube


The method is demonstrated in the following movie.

Space-time Group Motion Planning.