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.