RI | Research | Projects | Precomputed Search Trees: Planning for Interactive Goal-Driven Animation

Text only version of this site

Precomputed Search Trees: Planning for Interactive Goal-Driven Animation Heads: Manfred Lau and James Kuffner Contact: Manfred Lau (mlau@cs.cmu.edu) Mailing address: Carnegie Mellon University Robotics Institute 5000 Forbes Avenue Pittsburgh, PA 15213 Associated center: CFR Associated lab/group: Planning and Autonomy Lab For more information, see this project's homepage.

Jump to: Project Description | Personnel | Publications

Project Description

We present a novel approach for interactively synthesizing motions for characters navigating in complex environments. 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 available 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 arbitrary 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.

Personnel

	Name	Title	Email Address
	James Kuffner	Assistant Professor	kuffner@cs.cmu.edu
	Manfred Lau	PhD Student, CS	mlau@cs.cmu.edu

Publications

Note: This list may not be comprehensive. It contains only those publications in the RI publications database. Entries are listed in reverse chronological order.

• Precomputed Search Trees: Planning for Interactive Goal-Driven Animation
  M. Lau and J. Kuffner
  ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 2006. [Abstract]
  Download: pdf [2054 KB] copyrighted