Space-time Group Motion Planning

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


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 on different scenarios and evaluate the results from our simulations using a number of quantitative quality metrics. In practice, our system runs at interactive rates and can solve complex planning problems involving one or multiple groups.
Original languageEnglish
Title of host publicationAlgorithmic Foundations of Robotics X
Subtitle of host publicationProceedings of the Tenth Workshop on the Algorithmic Foundations of Robotics
EditorsE Frazzoli, T. Lozano-Perez, N. Roy, D. Rus
Number of pages17
Publication statusPublished - 2013

Publication series

NameSpringer Tracts in Advanced Robotics


Dive into the research topics of 'Space-time Group Motion Planning'. Together they form a unique fingerprint.

Cite this