Source-linked AI summary
Simultaneous Contact, Gait and Motion Planning for Robust Multi-Legged Locomotion via Mixed-Integer Convex Optimization
Bernardo Aceituno-Cabezas, Carlos Mastalli, Hongkai Dai, Michele Focchi, Andreea Radulescu, Darwin G. Caldwell, Jose Cappelletto, Juan C. Grieco, Gerardo Fernandez-Lopez, Claudio Semini
TL;DR
Multi-legged locomotion planning must coordinate discrete gait and contact choices with continuous motion, but prior coupled methods are limited by terrain, fixed gaits, or non-convex computation. The paper formulates a mixed-integer convex planner that jointly selects contacts, gait transitions, and motion, and validates it on HyQ across challenging terrains with robust transitions and low computation time.
Problem
Existing locomotion planners often decouple contact and motion decisions, while coupled approaches may assume simple terrain or fixed gaits or require intractable non-convex optimization.
Method
The method uses one mixed-integer convex optimization problem incorporating contact locations, gait sequences, friction-cone stability, approximate torque limits, and motion.
Results
Experiments with HyQ demonstrate successful traversal of gaps, ramps, and steps, including robust gait transitions and non-coplanar contacts.
Takeaways & Limitations
The approach enables automatic gait discovery and efficient planning of stable locomotion through challenging three-dimensional terrain.
Abstract
from arXiv · showhide
Traditional motion planning approaches for multi-legged locomotion divide the problem into several stages, such as contact search and trajectory generation. However, reasoning about contacts and motions simultaneously is crucial for the generation of complex whole-body behaviors. Currently, coupling theses problems has required either the assumption of a fixed gait sequence and flat terrain condition, or non-convex optimization with intractable computation time. In this paper, we propose a mixed-integer convex formulation to plan simultaneously contact locations, gait transitions and motion, in a computationally efficient fashion. In contrast to previous works, our approach is not limited to flat terrain nor to a pre-specified gait sequence. Instead, we incorporate the friction cone stability margin, approximate the robot's torque limits, and plan the gait using mixed-integer convex constraints. We experimentally validated our approach on the HyQ robot by traversing different challenging terrains, where non-convexity and flat terrain assumptions might lead to sub-optimal or unstable plans. Our method increases the motion generality while keeping a low computation time.
I. INTRODUCTION
The paper addresses locomotion planning by combining contact selection, gait sequencing, and motion generation in one mixed-integer convex problem. This formulation targets challenging terrain while retaining dynamic feasibility and efficient optimization.
- Traditional planners separate contact selection from trajectory generation, although ignoring dynamics during contact selection can restrict later feasible motions.
- Existing coupled approaches are often limited to simple environments or fixed gaits, require intractable computation time, and use non-convex optimization without global-optimality guarantees.
- The proposed MICP simultaneously plans contacts and motions while optimizing gait sequences for non-gaited locomotion on challenging terrain.
- The formulation incorporates convex friction-cone, torque-limit, and gait-planning constraints, enabling efficient solution to a globally optimal convex optimization problem.
- The approach generates robust motions during gait transitions and non-coplanar contact scenarios, with HyQ used for validation on challenging terrains.
B. Centroidal Dynamics
The planner models quadruped motion with centroidal dynamics and embeds gait transitions through binary contact-transition variables. The resulting formulation remains convex apart from the explicitly identified angular-momentum cross product.
- B. Centroidal Dynamics: The robot is modeled with centroidal dynamics, where mass and gravity define the translational and rotational evolution of the system.
- B. Centroidal Dynamics: The dynamic formulation is entirely convex except for the cross product used to compute torque at the center of mass.
- B. Centroidal Dynamics: Contact torques are neglected because most multi-legged platforms are modeled with approximate point contacts lacking support surfaces that generate moments.
- C. Gait Sequence: Gait transitions use a binary matrix T, where T_ij = 1 assigns contact location i to time-slot j.
- C. Gait Sequence: Each contact cycle must finish before the next transfer cycle begins, and sequential ordering is enforced through timing constraints.
D. Contact Location
The formulation simplifies swing trajectories while optimizing contact locations and timing, constraining contacts to convex safe terrain surfaces. Binary surface assignments allow obstacle avoidance to be represented within the optimization.
- D. Contact Location: The planner optimizes contact locations and contact timing while representing end-effector trajectories by interpolation between adjacent contacts.
- D. Contact Location: Contact locations encode Cartesian position and trunk yaw while neglecting roll and pitch during transitions.
- D. Contact Location: Contacts are constrained to lie on one of several convex safe contact surfaces, with binary variables assigning each contact to a surface.
2) Kinematic constraints:
The formulation enforces kinematic feasibility by constraining contacts to safe surfaces and reachable leg workspaces, while using gait-defined end-effector trajectories and CoM workspace bounds.
- Kinematic constraints: Contacts are constrained to lie within convex safe contact surfaces and each leg’s reachable workspace is approximated by an inscribed square.Safe surfaces are assigned through binary decisions, while reachability uses the largest square inscribed in each leg workspace.
- Kinematic constraints: Trigonometric reachability terms are replaced with piecewise-linear approximations selected by binary segment-assignment matrices.The segment boundaries, slopes, and intersections define the linear approximations.
- End-effector trajectories: The gait transition matrix defines swing intervals and end-effector trajectories between adjacent contacts.The function γ(j,t) indexes knots within each swing time-slot.
- End-effector trajectories: When no transition occurs, the corresponding leg remains stationary throughout the swing-slot knots.The stationarity constraint equates later knots with the first knot in the slot.
- End-effector trajectories: Bounding-box constraints keep the CoM within its workspace relative to the end-effectors.The bounds are represented by d− and d+.
F. Contact Dynamics
Contact dynamics are modeled with activation and friction-cone constraints that preserve dynamic consistency and stability, including a maximized friction-cone stability margin.
- Contact activation: Activation constraints prevent contact forces from acting on a leg during swing or immediately after contact breaks.The formulation uses complementarity-like relations to activate contacts consistently with gait phases.
- Friction cones: Each contact force is constrained inside a polyhedral approximation of its surface-specific friction cone.The cone is formed from positive multipliers on its edge vectors.
- Friction-cone margin: The optimization maximizes α, the distance from the contact force to the friction-cone boundary along the normal-force direction.This increases the friction-cone stability margin while retaining convexity through linearized constraints.
- Stance consistency: During stance, the contact cone remains unchanged across succeeding knots.The constraint propagates the cone condition through all stationary knots in the slot.
G. Convex Decomposition of Angular Dynamics
The angular dynamics’ bilinear cross product is reformulated through a convex quadratic decomposition, while torque feasibility is approximated around nominal kinematics.
- Angular dynamics: The centroidal angular dynamics are non-convex because the contact-position and force terms form a cross product.McCormick-envelope alternatives increase problem complexity.
- Angular dynamics: A quadratic decomposition converts the dynamics into a mixed-integer quadratically constrained quadratic program that remains convex.The norms of u− and u+ are penalized to bound the centroidal angular-momentum rate.
- Torque limits: Torque limits are approximated under a quasi-static assumption by projecting contact forces through each leg’s nominal Jacobian and compensating gravity.This improves motion feasibility without requiring the Jacobian to be computed from unknown joint positions.
- Torque limits: The resulting constraint approximates the Actuation Wrench Polytope to define an approximation of the Feasible Wrench Polytope.The approximation is useful near nominal positions and without aggressive speeds; robust optimization could account for Jacobian variation.
I. Trajectory Optimization
Trajectory optimization combines stability, smoothness, speed, force, angular-dynamics, and goal-reaching objectives in a convex optimization formulation.
- Objective formulation: The trajectory problem is formulated as a convex optimization over running and terminal costs.The running cost evaluates the plan across knots, while the terminal cost biases it toward the goal position.
- Running objectives: The running objectives minimize CoM acceleration, contact-force magnitude, and the quadratic-dynamics bound.These terms regulate motion smoothness, force usage, and angular-dynamics rates.
- Running objectives: The optimization maximizes the friction-cone stability margin α and minimizes total execution time.These objectives favor robust and fast gait execution.
- Terminal objective: A terminal cost biases the final state toward the goal position, with a small additional velocity cost used to smooth motion.The terminal objective uses weighted squared-L2 penalties.
III. WHOLE-BODY CONTROL
The whole-body controller converts planned motions into torque commands while enforcing tracking, friction, torque, and kinematic constraints. It combines feed-forward torques from the optimized motion with feedback control for compliant execution and disturbance handling.
- III. WHOLE-BODY CONTROL: The trunk controller computes feed-forward joint torques from planned center-of-mass, body-attitude, and swing motions.These motions are controlled through reference accelerations and the optimized solution is mapped into desired torques.
- III. WHOLE-BODY CONTROL: Feedback joint torques are computed in parallel through impedance control to address unpredictable events such as foot slippage.Desired body and joint motions must remain consistent to avoid conflicts with the trunk controller.
- III. WHOLE-BODY CONTROL: A quadratic program minimizes acceleration-tracking error while enforcing friction, torque, and kinematic constraints.Generalized accelerations and contact forces are the decision variables.
- III. WHOLE-BODY CONTROL: The optimization cost combines a quadratic tracking penalty with a regularization term that keeps solutions bounded or pursues additional criteria.The tracking cost is rewritten using the contact-force-based centroidal dynamics.
- III. WHOLE-BODY CONTROL: The controller sends the combined torque command to a low-level joint-torque controller.Feed-forward torques are summed with feedback torques before transmission.
IV. EXPERIMENTAL VALIDATION
The approach was validated on the 85 kg HyQ quadruped across challenging terrains. Experiments evaluated traversal capabilities and the use of gait transitions in non-coplanar environments.
- IV. EXPERIMENTAL VALIDATION: The experiments used the 85 kg hydraulically actuated HyQ quadruped to traverse challenging terrains while optimizing gait transitions.HyQ is fully torque controlled and equipped with joint encoders, a Multisense SL sensor, and an inertial measurement unit.
- IV. EXPERIMENTAL VALIDATION: The robot successfully crossed terrains containing gaps, ramps, and steps with different terrain heights.The result relied on convex robot and terrain models, approximate torque limits, and stability maintenance for non-coplanar contacts.
1) Convex model of robot’s dynamics and terrain:
The experiments show how convex terrain and dynamics modeling, approximate torque constraints, and stability handling support locomotion over gaps, slopes, stairs, and non-coplanar contacts. The evaluation also examines gait choices and identifies scope boundaries of the convex model.
- 1) Convex model of robot’s dynamics and terrain:: The convex robot-and-terrain model avoided a local minimum and required fewer contact locations than when crossing a gap while climbing.The terrain model works well for most scenarios but may lose validity with significant nonlinear curvature.
- 2) Approximate torque constraints:: Torque constraints enabled gap crossing: without them, the robot reached torque limits three times and fell while climbing down.Both plans climbed the slope successfully, but only the torque-constrained plan crossed the gap.
- 3) Stability in non-coplanar contact conditions:: Stability handling supported traversal of gaps and stairs under non-coplanar contacts, where ZMP-based approaches cannot ensure stability.The authors experimentally found increased robustness relative to the referenced methods.
- 3) Stability in non-coplanar contact conditions:: The approach restricts trajectories to small angular-momentum changes because of limitations in the convex model.This restriction motivates reliance on a reference for robot-attitude modulation.
- Gait planning and transitions: The gait experiments compared predefined walking and trotting with an automatically optimized gait sequence on challenging terrain.The trials evaluated gait planning and transitions under non-coplanar contacts.
1) Fixed walking and trotting gaits:
The experiments show successful, robust locomotion across challenging terrains, including automatic transitions between walking and trotting. The approach also achieves substantially faster planning than prior non-convex methods, while its angular-dynamics approximation limits more dynamic gaits.
- Fixed walking and trotting gaits: 18 cm/s to 31 cm/s: trotting increased execution speed compared with walking, while the controller tracked the faster motion effectively.The walking and trotting motions were executed robustly across the entire trial despite relatively slow visual-state-estimation corrections.
- Automatic gait transitions: The planner selected walking before trotting, slowed to walking on significant terrain changes, and returned to trotting afterward.This gait sequence emerged from optimization without terrain heuristics, based on the robot’s centroidal dynamics.
- Experimental robustness: All experimental plans executed successfully, with approximate torque limits enabling walking speeds around 15 cm/s, while gait transitions remained robust on challenging terrain.The convex approximation of angular dynamics generated natural motions for the reported experiments.
- Method limitations: The angular-dynamics approximation does not extend well to bounding or pacing because it cannot impose angular-momentum limits, causing divergence.The limitation concerns more dynamic gaits than those demonstrated in the experiments.
- Computation time: At least two orders of magnitude faster: the method planned locomotion cycles faster than previous work on similar terrains.The convex MIQCQP formulation and kinematic constraints helped efficiently reject infeasible surfaces while maintaining stability through terrain changes.
- Computation-time trade-offs: Leaving gait as a decision variable increased computation time significantly, while quadratic constraints produced increases of around 500%.The authors identify these factors as important computation-time costs and suggest receding-horizon extensions.