James Kuffner  

Task-Level Manipulation Planning for
Autonomous Animated Characters

James Kuffner, Jr.
Jean-Claude Latombe
Stanford CS Robotics Laboratory
August 1999


Our goal is to design software that generates object grasping and manipulation motions automatically from task-level commands. We utilize several key tools and techniques originally developed in the robotics literature, to create manipulation motions for animated agents.


Inverse Kinematics and Path Planning

Algorithms in computational geometry and robotics have been developed to compute motions for manipulator arms by configuration space (C-space) path planning techniques. One can view a human arm as a robot manipulator arm with 7 degrees of freedom (DOF) from the shoulder to the wrist, and apply classic C-space path planning techniques in order to generate joint-space trajectories. However, due to the high-dimensionality of the space, brute-force search algorithms are infeasible. As an alternative, we have conducted a series of experiments utilizing randomized path planning techniques in order to quickly search the arm joint space for a path connecting an initial configuration to a goal configuration.


Early Results

In 1994, we performed the first of a series of experiments in this area, culminating in the production of the short animated film ENDGAME, which made its debut at the SIGGRAPH'94 Electronic Theater. The planning software was developed by Yotto Koga as part of his PhD thesis, and worked in conjunction with a Human Inverse Kinematics (IK) algorithm proposed by Koichi Kondo. The particular randomized path planning (RPP) technique used involved alternating between performing gradient descent motions on an artificial potential field, and executing random walks in order to escape any local minima encountered. Several complicated multi-arm regrasping motions were computed, with computation times ranging from 3 to 10 minutes. More information as well as downloadable images and movies from the ENDGAME project are available.


placing the robot

opening chess move

the endgame


Recent Results

Over the last decade, randomized search algorithms have been developed in the robotics literature to perform motion planning in high-dimensional spaces. We have adapted some of these techniques to quickly compute reaching and manipulation motions for human arms that are orders of magnitude faster than our previous experiments. In particular, we have developed the RRT-Connect heuristic intended for quickly solving single-query path planning problems in high-dimensional search spaces. Some computed examples using the planner along with a human arm model are illustrated below:


grasping a coffee pot

using the other hand

grasping a bottle

reaching for a flashlight

finalizing the grasp

completed grasp

Real-time "ENDGAME"

In order to demonstrate the speed of the new planning algorithms, we have created a software application that allows a user to play chess against an animated character interactively. All of the motions for the character to grasp, move, and release the game pieces are computed "on-the-fly", with no precomputation.


Click image to download movie
Quicktime (1.1MB)

interactive chess (left view)

interactive chess (right view)

Virtual Prototyping and Ergonomic Analysis

The planning heuristic was designed to work quickly in configuration spaces that are relatively free, with large open spaces. This is ideal for tasks such as moving chess pieces around. However, the planner can also be used to solve more complicated planning queries (e.g. queries that involve narrow passages in the configuration space), but at an increased computational cost.

Thus, the planner can be used for applications such as human ergonomic analysis for virtual prototyping, in which a designer could verify the maintainability of a product without having to build expensive mock-ups.


maintaining a virtual tractor

reaching for a tool

performing maintenance

performing maintenance (top view)

performing maintenance (closeup)


driving a virtual car

verifying the ergonomics of the
steering wheel and stick shift controls

1997 - 2009 © James Kuffner, Jr.