Research |
|
Papers |
|
Software |
|
Teaching |
|
Resume |
|
Gallery |
|
Contact |
Goal-Directed Navigation for
Animated Characters
James Kuffner, Jr.Stanford CS Robotics Laboratory
August 1999
Overview
Our goal is to design software that generates motion automatically from navigational commands specified at the task level. (i.e. "walk to the dining room", etc.) The experiments we have conducted thus far utilize cyclic motion capture data along with a fast 2D motion planner and controller to direct the character to move towards a given goal location.
 Data Flow Diagram |
The characters used in these experiments have a minimum of 17
joints arranged hierarchically with anywhere between 40-55 degrees
of freedom. The cyclic motion capture data is used to animate all of
the joints except for the character's global location
(typically determined by the hip transformation). A simple PD
controller is used to make the character globally follow a computed
path.
 Indoor navigation |  Navigating a maze |
Real-Time Path Planning
We utilize the hardware Z-buffer commonly found on graphics workstations to enable fast 2D projection for path planning. The planning algorithm works as follows: First, the character's geometry is bounded by an appropriate cylinder. By doing so, we can effectively reduce the problem to one involving path planning for a circular disc among obstacles in 2D.Next, an orthographic camera is situated above the scene. The near and far clipping planes of the camera are set to correspond to the vertical extents of the character's geometry. The camera's view of all obstacles is rendered into an offscreen bitmap. The graphics hardware enables this standard projection operation to be done very quickly. The projected obstacles are "grown" by the radius of the character's bounding cylinder to produce a final bitmap for planning.
 Projected Obstacles |  Grown Obstacles |
After the rendering and obstacle growth is complete, any
standard graph search algorithm (such as Dijkstra's algorithm or A*)
may be used to search the implicit graph defined by the rendered bitmap
for a collision-free path that connects the character's starting
position to the position of the goal marker.
 Computed Path |
Path Following
If a path to the goal exists, it is returned by the planner and passed to a simple PD controller. The controller is used to synthesize the cyclic motion capture data and animate the character as it follows the path. The equations for a simple path-following controller for an oriented disc are given below:
 State Variables |  Computing the Controls |
This algorithm has been implemented on an SGI Indigo2 running Irix
6.2 with OpenInventor. In our implementation, the algorithm runs in
about one-tenth of one second, allowing for interactive modification of
both the goal marker location, as well as the locations of obstacles in
the scene. Full planning and replanning is performed as the
controller adapts to new paths computed due to changes in the
environment and goal location. Provided the controller gains are set
appropriately in relation to the simulation time step, smooth and
continuous tracking motion will result.
 Tracking a path using a PD controller | 
Closeup of tracking performance |
Perception-based Navigation
With minor modification, the navigation algorithm can be used along with a synthetic vision module to allow a character to explore an unknown environment (for more information, see Simulated Visual Perception). A path is computed based only on the obstacles observed, and is updated as new sensory information arrives. Even if the tracked path must be altered drastically during the exploration process, the path-following controller will alway produce continuous motion.
 Exploring an unknown maze environment |
Multiple Characters
Scenes involving multiple characters are possible, since each character can utilize the same initial projected bitmap and the same path search algorithm. Different characters can be outfitted with different controllers in order to reflect their unique styles of motion or behavior (for examples, see High-Level Behaviors).
 multiple characters navigating in a maze |  multiple characters navigating in an office |
Collisions between characters can be avoided by having each
character "plan around" the others. For example, one can project the
(bounding)geometry of the other characters at their current locations,
and replan as necessary. More sophisticated schemes that account
for character motions are possible (e.g. planning around the
other characters' predicted future positions).