Discovery of Complex Behaviors through Contact-Invariant Optimization

---

Discovery of Complex Behaviors through Contact-Invariant Optimization

Igor Mordatch

Emanuel Todorov

Zoran Popovi´c

University of Washington

Figure 1: A selection of motions synthesized by our algorithm.

Abstract

We present a motion synthesis framework capable of producing a

wide variety of important human behaviors that have rarely been

studied, including getting up from the ground, crawling, climbing,

moving heavy objects, acrobatics (hand-stands in particular), and

various cooperative actions involving two characters and their ma-

nipulation of the environment. Our framework is not specific to

humans, but applies to characters of arbitrary morphology and limb

configuration. The approach is fully automatic and does not require

domain knowledge specific to each behavior. It also does not re-

quire pre-existing examples or motion capture data.

At the core of our framework is the contact-invariant optimization

(CIO) method we introduce here. It enables simultaneous optimiza-

tion of contact and behavior. This is done by augmenting the search

space with scalar variables that indicate whether a potential contact

should be active in a given phase of the movement. These auxil-

iary variables affect not only the cost function but also the dynam-

ics (by enabling and disabling contact forces), and are optimized

together with the movement trajectory. Additional innovations in-

clude a continuation scheme allowing helper forces at the potential

contacts rather than the torso, as well as a feature-based model of

physics which is particularly well-suited to the CIO framework. We

expect that CIO can also be used with a full physics model, but leave

that extension for future work.

CR Categories: I.3.1 [Computer Graphics]: Three-Dimensional

Graphics and Realism—Animation

Keywords: physics-based animation, control

Links:

DL

PDF

W

EB

V

IDEO

1

Introduction

Automated synthesis of complex human behaviors is one of the

long-standing grand challenges in computer graphics, that would

also have an impact on robotics, biomechanics, and movement neu-

roscience. An automated synthesis method would ideally be capa-

ble of creating motions that span the space of all possible human

behaviors. In addition, such a method would not require expert or

labor-intensive authoring in the form of keyframes, reference trajec-

tories, or any specific details of the intended movement. It would

also not require any direct or indirect use of motion capture data. In-

stead, movement details and complexity should emerge from an au-

tomated procedure whose only inputs are intuitive high-level goals

that are easy to specify.

The most progress towards this ambitious agenda has been made in

the domain of walking. After three decades of intensive research,

we now have algorithms that can make simulated humanoids walk

robustly and realistically in response to high-level interactive inputs

such as desired body velocity and orientation. These algorithms are

successful because they exploit domain-specific knowledge: state

machines synchronized to the relatively simple and stereotypical

pattern of foot-ground contacts, reduced models based on inverted-

pendulum dynamics or other features important for walking, and

trajectory optimization methods that rely on customized cost func-

tions and manual specification of contacts. The success of these

methods comes at the price of limited generality: they provide a

unique and different type of model and solution for each of the com-

mon locomotion tasks such as walking, running and jumping. With

the current state-of-the-art in automated motion synthesis, any ad-

ditional complex behavior would require a new movement model

carefully crafted by experts from scratch. Each of these new move-

ment models would require specific domain knowledge carefully

integrated into the motion synthesis algorithm.

This behavior-specific approach to motion synthesis is at odds with

the richness and expressiveness of human motor behavior, exhibited

in seemingly infinite complex movements that do not fall into stan-

dard categories such as locomotion or reaching. Often, these be-

haviors are more challenging than locomotion in the sense that they

involve longer, more complex (spatially and temporally) movement

plans, and less stereotypical or cyclic movements. Examples in-

clude movements that use more than just legs, or just arms, but that

use other parts of the body, movements that can represent the full

space of interactions between the human body and the ground and

---

other arbitrary objects in the environment, complex manipulations

of objects by one or many humans collaboratively, hand-walking,

climbing – to name just a few.

In this paper we present a step towards a more general yet fully

automated framework for behavior synthesis, capable of produc-

ing a wide variety of less commonly studied but important human

behaviors. These include getting up from the ground, crawling,

climbing, moving heavy objects, acrobatics (hand-stands in partic-

ular), and various cooperative actions involving two characters and

their manipulation of the environment. The framework is not spe-

cific to humans, but can synthesize behaviors for other imagined

morphologies.

1.1

The key idea: Contact-Invariant Optimization (CIO)

As with prior methods for automated behavior synthesis, our CIO

method also comes down to exploiting domain-specific knowledge.

The important difference is that the domain to which our method

is tailored is much larger, and includes any behavior of any artic-

ulated character where contact dynamics are essential. This is a

very large domain because almost all limb movements performed

on land are made for the purpose of establishing contact with some

object (including the ground) and exerting forces on it. A suitable

set of contacts provides actuation: once you grasp an object you

can manipulate it; once you plant your feet on the ground you can

generate forces on your torso. Complex movements tend to have

phases within which the set of active contacts remains invariant.

Such invariance greatly reduces the space of candidate movements.

In complex behaviors and in complex environments, however, it is

difficult to know in advance what these contact sets should be and

how they should change from one phase to the next. Unlike prior

work on walking where contact information was specified manually

and left outside the scope of numerical optimization, discovering

suitable contact sets is the central goal of optimization in our ap-

proach. Once this is done, optimizing the remaining aspects of the

movement tends to be relatively straightforward.

Intuitively, CIO is a way of reshaping a highly discontinuous and

local-minima-prone search space of movements and contacts, into

a slightly larger but much better-behaved and continuous search

space that enables optimization strategies to find good solutions.

The main technical innovation in the CIO method is the introduc-

tion of scalar variables that indicate whether a potential contact

should be active in a given phase. These auxiliary variables affect

not only the cost function but also the dynamics (by enabling and

disabling contact forces), and are optimized together with the move-

ment trajectory. In this way we provide the optimizer with abstract

but nevertheless useful information: namely that movements should

have phases, and that the contact set should remain invariant within

each phase. The specific sets of active contacts that are suitable for

each phase of each behavior are then discovered by the optimizer

fully automatically. Additional innovations include a continuation

scheme allowing helper forces at the potential contacts rather than

the torso, as well as a feature-based model of physics which is par-

ticularly well-suited to the CIO framework.

2

Related Work

Early approaches to synthesizing human motion have been able to

produce a wide repertoire of skills [Hodgins et al. 1995; Hodgins

and Pollard 1997; Wooten and Hodgins 2000], but required expert

manual specification for each new task. Since then, a lot of fruitful

work has focused specifically on the task of locomotion. Simpli-

fied dynamical systems representing walking [Kajita et al. 2001;

Kuo et al. 2005], running [Seipel and Holmes 2005], push recovery

[Pratt et al. 2006] and uneven terrain navigation [Manchester et al.

2011] have been proposed that are well suited to analysis and con-

trol. The results were extended to full-detail bipeds [Yin et al. 2007;

chi Wu and Popovic 2010; de Lasa et al. 2010] and quadrupeds

[Coros et al. 2011]. [Srinivasan and Ruina 2005; Mordatch et al.

2010] have tried to capture different modes of locomotion within

a single controller, though they still assume a fixed pattern of foot

contacts that are specific to locomotion. Others proposed to in-

telligently combine individual controllers [Faloutsos et al. 2001;

da Silva et al. 2009; Coros et al. 2009; Muico et al. 2011], although

they still rely on existence of base controller libraries.

A more general approach to motion synthesis has been to pose

the problem as trajectory optimization, subject to user constraints

[Witkin and Kass 1988]. However, for all but the simplest problems

the energy landscape of the optimization is very high-dimensional,

prone to many local minima, and even discontinuous due to contact

phenomena. To alleviate these issues, many approaches make use

of human motion capture data to restrict the search space around

stereotypical motions and pre-specify contact events [Popovic and

Witkin 1999; Kalisiak and van de Panne 2001; Fang and Pollard

2003; Safonova et al. 2004; Liu et al. 2005]. [Liu et al. 2006]

adapts motion capture data and contacts to multi-character inter-

actions. By optimizing contact times for cyclic patterns, [Wampler

and Popovic 2009] is able to synthesize gaits for a wide variety of

non-humanoid characters from scratch.

Rather than placing restrictions on the optimization problem, sev-

eral methods have focused on shaping the energy landscape to be

smoother and better behaved. To widen the solution feasibility re-

gion, [Van De Panne and Lamouret 1995] initially use unphysical

helper forces to aid the character and reduce them as optimization

progresses, while [Yin et al. 2008] parametrizes the difficulty of

the task itself. [Brubaker et al. 2009; Todorov 2011] reformulate

contact as a smooth, rather than discontinuous phenomenon, where

contact forces are always active, but smoothly diminish with the

distance to the ground. The latter method has demonstrated success

for continuous optimization of cyclic gaits [Erez et al. 2011]. [Jain

and Liu 2011] accurately models characters with soft tissue, and

shows improvements in stability and robustness for simple track-

ing algorithms. However, applying these formulations to general

trajectory optimization problems remains difficult, because contact

decisions are made implicitly as a (highly non-linear) function of

the character’s pose. Some methods such as [Muico et al. 2009;

Ye and Liu 2010; Liu 2009] directly include contact forces as vari-

ables to be optimized, but they only have limited ability to manip-

ulate contact state. By contrast, our contact variables make contact

decisions explicit in the optimization.

Reasoning about contact events for navigation and object manipu-

lation has also been considered by several planning approaches in

robotics. [Kuffner et al. 2003; Chestnutt 2007; Hauser et al. 2008;

Kolter et al. 2008; Bouyarmane and Kheddar 2011] decompose the

problem into two stages, first planning foot or hand placements and

then synthesizing a motion trajectory that follows those placements.

The two stages are only loosely coupled, and may not always pro-

duce the most efficient strategies. By contrast, our approach jointly

plans both the contact events and the motion trajectory, and is able

to exploit any synergies between the two.

The importance of temporally-extended actions and their poten-

tial to speed up optimization has been recognized in Reinforce-

ment Learning, and has led to the Options framework [Sutton et al.

1999]. In that framework however the temporally-extended actions

(loosely corresponding to our movement phases) have to be speci-

fied in advance, while we discover them automatically.

---