Continuation methods for adapting simulated skills

KangKang Yin, Stelian Coros, Philippe Beaudoin, Michiel van de PanneACM Trans. Graphics 2008 · DOI

TL;DR

This paper introduces continuation methods to adapt physics-based character controllers for new tasks, like climbing stairs or pushing furniture, by progressively transitioning from a known solution to a desired one. They evaluate several continuation strategies, finding that a hybrid approach offers a good balance of solution quality and computational efficiency.

What Problem Does This Paper Address?

Creating realistic and responsive animated characters that can interact with complex environments is a significant challenge. While resequencing motion capture data is common, it often lacks the flexibility to adapt to novel situations. Physics-based controllers offer more adaptability but are difficult to design and tune for diverse tasks. This paper addresses the problem of automatically adapting a pre-existing physics-based walking controller to significantly different environmental challenges, such as varying step heights, obstacles, inclines, or slippery surfaces, without requiring manual re-engineering of the controller for each new scenario.

Methods

The core idea is to use continuation methods, which solve a difficult problem by starting from a related, easier problem and progressively adapting the solution. The authors frame this as finding a path through a parameter space where one dimension represents the environmental change (e.g., step height) and another represents the controller parameters.

They explore and compare three main continuation strategies:

  • GRAD (Gradient Descent): Advances the continuation parameter by a fixed step and uses gradient descent to optimize the controller's "style" (e.g., naturalness, desired step length). This is a straightforward but potentially slow and failure-prone method.
  • STOC (Stochastic Local Search): Couples advancement and style optimization by adding a reward term to the objective function for making progress in the continuation parameter. They test three variations (STOC1, STOC2, STOC3) with different weights for this reward, aiming for faster but potentially less optimal or more erratic solutions.
  • HYBRID: Combines elements of GRAD and STOC. It uses a linearly predicted parameter value as a starting point for gradient descent and allows for adaptive step sizes in the continuation. This method aims to improve upon GRAD's speed and robustness.

The controller itself is based on a four-state finite-state machine (FSM) with PD controllers for joint torques, and includes feedback gains for balance. The optimization targets a subset of joint target angles and feedback parameters.

Datasets

Not discussed in the paper. The paper focuses on adapting a single controller to various simulated environmental challenges rather than training on a dataset of motions. The "datasets" are effectively the five simulated scenarios: STEPUP, STEPOVER, PUSH, HILL, and ICE.

Key Insights and Ideas

  • Continuation as a Generalization Tool: The paper demonstrates that continuation methods are a powerful and unified framework for adapting physics-based controllers to a wide range of environmental variations, from simple geometry changes to physics property alterations (like friction).
  • Trade-offs in Continuation Strategies: There's a clear trade-off between speed, solution quality, and robustness. Pure gradient descent is robust but slow. Stochastic methods can be faster but may yield less optimal or more erratic results. The HYBRID method offers a compelling middle ground.
  • The Importance of "Shaping" Terms: For tasks like STEPUP and STEPOVER, adding "shaping" terms to the objective function (e.g., desired swing-foot height relative to the step) significantly helps guide the optimization and improve the quality of the resulting motion.
  • Parameterization for Interpolation: The continuation path naturally generates a family of controllers. Linear interpolation between adjacent points on this path allows for real-time adaptation of the character's behavior to dynamically changing environments.
  • Controller Representation Matters: The choice of controller representation (here, an FSM with PDs and feedback gains) and the specific parameters chosen for optimization significantly influence the adaptability and the resulting motion styles.

Key Results

  • Successful Adaptation: All tested continuation methods were able to adapt the walking controller to the five example problems (STEPUP, STEPOVER, PUSH, HILL, ICE) to varying degrees.
  • HYBRID Outperforms: The HYBRID method generally produced the best quality solutions across all problems, as measured by the objective function and visual inspection, while remaining computationally feasible.
  • GRAD Limitations: The GRAD method often failed or stalled at relatively early stages of the continuation (e.g., failing at 11cm for STEPUP, 7cm for STEPOVER, 22° for HILL).
  • STOC Variations: STOC methods showed varying performance. STOC2 and STOC3 were often competitive with HYBRID in terms of advancement speed, though STOC3 sometimes produced more erratic motions. STOC1 was often too slow due to insufficient continuation reward.
  • Computational Efficiency: Simulations ran at near real-time rates. The wall-clock time for 1000 objective function evaluations varied from 27-54 minutes, indicating that these methods are feasible for offline adaptation.
  • Visual Quality: Figures and videos demonstrate successful adaptations, showing characters climbing large steps, stepping over obstacles, pushing furniture, walking up inclines, and on ice.

Limitations and Future Work

  • Parameter Tuning: The STOC methods require careful tuning of the continuation reward parameter ($c_0$), which is a disadvantage.
  • Multidimensional Continuation: The paper acknowledges the need to investigate multidimensional continuation methods to handle more complex scenarios with multiple interacting environmental variables (e.g., step height, distance, backpack weight, friction simultaneously).
  • Factorization and Superposition: Exploring factorizations of multidimensional continuations to enable linear superposition of effects would be beneficial for handling complex variations.
  • Optimization Parameter Selection: The choice of which controller parameters to optimize is problem-specific and requires experimentation.
  • Robustness and Naturalness: Future work aims to make motions more natural and optimize for robustness in addition to style.
  • Local Search Window: The STOC methods are limited by their search window size, potentially missing solutions in topologically isolated regions.
  • Understanding Failure: The paper notes that understanding why a continuation gets stuck at a limiting value of a parameter is complex and reflects the intricate interactions within the simulation.

Summary updated

BibTeX
@article{yin2008continuation,
  author = {KangKang Yin and Stelian Coros and Philippe Beaudoin and Michiel van de Panne},
  title = {{Continuation methods for adapting simulated skills}},
  journal = {ACM Trans. Graphics},
  year = {2008},
  doi = {10.1145/1360612.1360680},
}
Figure