Locomotion Planning through a Hybrid Bayesian Trajectory Optimization

Tim Seyde, Jan Carius, Ruben Grandia, Farbod Farshidian, Marco Hutter

Abstract

Locomotion planning for legged systems requires reasoning about suitable contact schedules. Traditional methods either rely on brittle heuristics or solve computationally expensive mixed-integer programs. This paper proposes a bi-level optimization framework that learns contact schedule selection using Bayesian optimization. A Gaussian process (GP) model predicts the performance of trajectories generated by a lower-level nonlinear program (NLP). This approach allows the agent to reason about hybrid dynamics without explicit gradient computation for discrete variables. Results for a single-legged hopper demonstrate that the method learns intuitive gait transitions and outperforms heuristic baselines.

Introduction

Legged locomotion presents a "hybrid" dynamical challenge, requiring simultaneous decisions on discrete contact schedules (when and where to step) and continuous body trajectories. Heuristic-based stepping is fast but lacks adaptability to novel terrains. Conversely, simultaneous optimization often results in non-smooth mixed-integer problems that are computationally prohibitive. This research introduces a middle ground: an efficient bi-level framework that automates contact scheduling through learning.

The single-legged hopper model navigating a simulated rough terrain environment.

Methodology

The proposed framework utilizes a bi-level optimization strategy:

  • Lower Level (LL): A standard Nonlinear Program (NLP) uses direct collocation to find the optimal physical trajectory for a fixed contact schedule.
  • Upper Level (UL): A Bayesian Optimization (BO) loop treats the LL as a black box. It employs a Gaussian Process (GP) with an ARD-Matern3/2 kernel to model a merit function—a composite score of energy efficiency and constraint satisfaction.

The workflow begins with a task context (e.g., goal distance and terrain profile). The GP suggests a contact action (sequence of stance and flight durations), the LL optimizes the trajectory, and the resulting merit score updates the GP's internal model.

Key Insights and Results

The model was evaluated using a simulated 2D single-legged hopper on both flat and rough terrains.

Emergent Gait Intuition

A significant finding is the emergence of "natural" gait transitions without explicit programming. As the target distance ($x_{B,goal}$) increases, the GP learns to transition from simple stance phases to single and then double jumps to maintain efficiency. This behavior aligns with human intuition regarding energy-efficient locomotion over varying distances.

Learned contact schedules as a function of goal distance, showing transitions from stance (red) to flight (green) phases.

Performance and Robustness

The GP-based model consistently achieved lower merit scores (indicating higher efficiency) compared to a baseline of five hand-tuned heuristic schedules. Furthermore, models trained on rough terrain (GP-RT) exhibited greater robustness, with a failure rate of only 3% compared to 6% for models trained only on flat ground. The system demonstrated high sample efficiency, converging within a few hundred iterations using the filtered squared relative residuals (fSRR) termination criterion.

Conclusion and Future Work

By decoupling contact schedule selection from trajectory execution, this hybrid approach avoids the bottlenecks of mixed-integer optimization while maintaining the flexibility to adapt to complex environments. Future work will explore scaling the framework to 3D quadrupeds and bipeds using deep neural networks to approximate the GP model, addressing the $O(n^3)$ complexity of standard Gaussian Processes and handling higher-dimensional action spaces.

Summary updated

Abstract

Locomotion planning for legged systems requires reasoning about suitable contact schedules. The contact sequence and timings constitute a hybrid dynamical system and prescribe a subset of achievable motions. State-of-the-art approaches cast motion planning as an optimal control problem. In order to decrease computational complexity, one common strategy separates footstep planning from motion optimization and plans contacts using heuristics. In this paper, we propose to learn contact schedule selection from high-level task descriptors using Bayesian optimization. A bi-level optimization is defined in which a Gaussian process model predicts the performance of trajectories generated by a motion planning nonlinear program. The agent, therefore, retains the ability to reason about suitable contact schedules, while explicit computation of the corresponding gradients is avoided. We delineate the algorithm in its general form and provide results for planning single-legged hopping. Our method is capable of learning contact schedule transitions that align with human intuition. It performs competitively against a heuristic baseline in predicting task appropriate contact schedules.
BibTeX
@inproceedings{seyde2019locomotion,
  author = {Tim Seyde and Jan Carius and Ruben Grandia and Farbod Farshidian and Marco Hutter},
  title = {{Locomotion Planning through a Hybrid Bayesian Trajectory Optimization}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2019},
  url = {https://openreview.net/forum?id=v15Nhxx42},
}
Figure