Precomputed Search Trees: Planning for Interactive Goal-Driven Animation

Manfred Lau and James Kuffner
ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 2006.


Download
  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
We present a novel approach for interactively synthesizing motions for characters navigating in complex environ- ments. We focus on the runtime efficiency for motion generation, thereby enabling the interactive animation of a large number of characters simultaneously. The key idea is to precompute search trees of motion clips that can be applied to arbitrary environments. Given a navigation goal relative to a current body position, the best avail- able solution paths and motion sequences can be efficiently extracted during runtime through a series of table lookups. For distant start and goal positions, we first use a fast coarse-level planner to generate a rough path of intermediate sub-goals to guide each iteration of the runtime lookup phase.

We demonstrate the efficiency of our technique across a range of examples in an interactive application with multiple autonomous characters navigating in dynamic environments. Each character responds in real-time to ar- bitrary user changes to the environment obstacles or navigation goals. The runtime phase is more than two orders of magnitude faster than existing planning methods or traditional motion synthesis techniques. Our technique is not only useful for autonomous motion generation in games, virtual reality, and interactive simulations, but also for animating massive crowds of characters offline for special effects in movies.


Notes
Associated Center(s) / Consortia: Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Planning and Autonomy Lab
Associated Project(s): Precomputed Search Trees: Planning for Interactive Goal-Driven Animation
Number of pages: 10

Text Reference
Manfred Lau and James Kuffner, "Precomputed Search Trees: Planning for Interactive Goal-Driven Animation," ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 2006.

BibTeX Reference
@inproceedings{Lau_2006_5508,
   author = "Manfred Lau and James Kuffner",
   title = "Precomputed Search Trees: Planning for Interactive Goal-Driven Animation",
   booktitle = "ACM SIGGRAPH / Eurographics Symposium on Computer Animation",
   year = "2006",
}