Simultaneous Contact, Gait, and Motion Planning for Robust Multilegged Locomotion via Mixed-Integer Convex Optimization

Bernardo Aceituno-Cabezas, Carlos Mastalli, Hongkai Dai, Michele Focchi, Andreea Radulescu, Darwin G. Caldwell, José Cappelletto, Juan C. Grieco, Gerardo Fernández-López, Claudio SeminiIEEE RA-L 2018 · DOI

TL;DR

This paper presents a novel Mixed-Integer Convex Optimization (MICP) framework that simultaneously plans contact locations, gait transitions, and whole-body motion for legged robots. This unified approach allows for computationally efficient and robust locomotion planning on challenging, uneven terrains without relying on pre-defined gaits, significantly outperforming traditional decoupled methods.

What Problem Does This Paper Address?

Planning robust and dynamic locomotion for multi-legged robots, especially on uneven terrain, is a complex challenge. Traditional approaches often break this problem into separate stages: first planning where the robot's feet should land (contact planning), and then generating the robot's body trajectory and joint movements. This decoupling can lead to suboptimal or unstable motions because it doesn't fully account for the interplay between contact forces, body dynamics, and the robot's physical limitations (like joint torques) during the initial planning phase. Furthermore, existing methods often assume flat terrain or fixed gait sequences, limiting their applicability to real-world scenarios. The authors aim to bridge this gap by developing a single, integrated optimization framework that considers all these aspects simultaneously.

Methods

The core of the paper is a Mixed-Integer Convex Optimization (MICP) formulation. Here's a breakdown of their key techniques:

  • Unified Planning: Instead of separate stages, they formulate a single MICP problem that jointly optimizes:
  • Contact Locations: Where the robot's feet will touch down.
  • Gait Transitions: When and how the robot switches between different leg movements (e.g., from walking to trotting).
  • Motion Planning: The robot's body trajectory and joint movements.
  • Centroidal Dynamics Model: They use a simplified model that focuses on the robot's center of mass (CoM) and angular momentum, which is computationally efficient.
  • Convex Approximations: To maintain convexity (essential for efficient optimization), they employ several approximations:
  • Friction Cone Stability: They represent friction cone constraints (ensuring feet don't slip) using piecewise linear approximations and incorporate a margin for robustness.
  • Torque Limits: They approximate joint torque limits using a quasi-static assumption, which helps prevent the robot from exceeding its physical capabilities.
  • Angular Dynamics: They use a convex decomposition technique to handle the non-linear cross-product terms in the angular dynamics, transforming a non-convex problem into a convex one.
  • Gait Planning as Integer Variables: Gait transitions are encoded using binary integer variables, allowing the planner to discover optimal gait sequences dynamically.
  • Terrain Representation: The terrain is represented by a convex segmentation, allowing the planner to find safe contact regions.

Datasets

Not discussed in the paper. The experiments were conducted on the HyQ robot in various real-world challenging terrains.

Key Insights and Ideas

  • The Power of Unification: The most significant insight is that simultaneously planning contacts, gait, and motion leads to demonstrably more robust and efficient locomotion than traditional decoupled approaches. This holistic view allows the planner to make better trade-offs between different objectives.
  • MICP as a Practical Tool: The paper showcases MICP not just as a theoretical possibility but as a practical tool for real-time motion planning in robotics, achieving low computation times.
  • Robustness through Explicit Margins: Incorporating explicit stability margins (like the friction cone margin) directly into the optimization problem leads to more reliable locomotion, especially in challenging conditions where traditional methods might fail.
  • Automatic Gait Discovery: The ability to plan gait transitions dynamically, rather than relying on pre-programmed gaits, allows the robot to adapt its locomotion strategy to changing terrain, leading to more natural and efficient movement.

Key Results

  • Computation Time: The proposed MICP approach plans motion at least two orders of magnitude faster than previous non-convex methods on similar terrains. For example, locomotion cycles were planned in less than a second.
  • Robustness: The method successfully navigated challenging terrains, including gaps, ramps, and stairs, with improved robustness compared to ZMP-based approaches.
  • Performance on HyQ Robot: Experimental validation on the HyQ robot demonstrated the effectiveness of the approach in real-world scenarios, achieving faster walking speeds than previous methods.
  • Gait Transition Handling: The approach successfully handled gait transitions robustly, even on difficult terrain, and could automatically discover optimal gait sequences based on terrain and dynamics.

Limitations and Future Work

  • Angular Momentum Divergence: The convex approximation of angular dynamics works well for simpler motions but can lead to divergence of angular momentum for more aggressive gaits (e.g., bounding).
  • Torque Limit Approximation: The current approximation of torque limits is based on a nominal operational space Jacobian. This approximation loses validity for more aggressive motions or when joint positions vary significantly.
  • Future Work:
    • Explore more advanced models for angular dynamics to handle aggressive behaviors.
  • Investigate more accurate approximations for torque limits, potentially using robust optimization.
  • Extend the approach to receding horizon planning for even faster real-time adaptation.
  • Relax friction cone constraints to vertex-based ZMP constraints to further improve computation time, albeit with potential sacrifices in stability guarantees.

Summary updated

BibTeX
@article{aceitunocabezas2018simultaneous,
  author = {Bernardo Aceituno-Cabezas and Carlos Mastalli and Hongkai Dai and Michele Focchi and Andreea Radulescu and Darwin G. Caldwell and José Cappelletto and Juan C. Grieco and Gerardo Fernández-López and Claudio Semini},
  title = {{Simultaneous Contact, Gait, and Motion Planning for Robust Multilegged Locomotion via Mixed-Integer Convex Optimization}},
  journal = {IEEE RA-L},
  year = {2018},
  doi = {10.1109/lra.2017.2779821},
}
Figure