TL;DR
This paper introduces a convex optimization framework for designing controllers for "hybrid" robots—systems that switch between different physical behaviors, such as a legged robot making and breaking contact with the ground. By using occupation measures and semidefinite programming (SDP), the authors synthesize simple polynomial control policies that automatically manage mode transitions and cover large regions of the state space more effectively than traditional methods like Model Predictive Control (MPC).
What Problem Does This Paper Address?
Controlling robots that interact with their environment is notoriously difficult because their dynamics are "hybrid." For example, a walking robot's physics change abruptly the moment its foot touches the floor.
Traditional control methods struggle here:
- Linear Quadratic Regulators (LQR): Only work for smooth, local dynamics and can't "see" a mode switch coming.
- Trajectory Optimization: Often requires the designer to pre-specify the sequence of contacts (e.g., "step left, then step right"), which is limiting.
- Dynamic Programming: Suffers from the "curse of dimensionality," becoming computationally impossible as the number of robot joints increases.
The authors aim to find a scalable, convex approach that designs a feedback policy for the entire reachable state space without requiring a pre-defined sequence of mode switches.
Methods
The authors model the robot as a discrete-time hybrid polynomial system. The state-input space is partitioned into regions (cells), each with its own polynomial dynamics.
The core technical innovation is the use of occupation measures. Instead of looking for a control law directly, the authors look for a "measure" that describes the distribution of time a robot spends in different states and actions.
- Liouville Equation: They use a discrete-time version of this equation to describe how the state distribution evolves over time.
- Infinite-Dimensional LP: The control problem is first formulated as a linear program (LP) over measures. While theoretically elegant, this is impossible to solve directly because it has infinite dimensions.
- SDP Relaxations: To make it solvable, they apply the "moment-SOS (Sum-of-Squares) hierarchy." This approximates the infinite LP with a sequence of finite-dimensional Semidefinite Programs (SDPs).
- Controller Extraction: Once the SDP is solved, they extract a simple polynomial feedback policy from the resulting "moments" of the measures.
Datasets
The paper evaluates the method on two simulated robotics benchmarks:
- Linear Inverted Pendulum with an Elastic Wall: A classic hybrid system where a pendulum can bounce off a wall.
- Variable Height Inverted Pendulum: A model representing a legged robot where the center of mass height can change and the "foot" can be placed in different discrete locations.
Key Insights and Ideas
- Convexity is the Secret Sauce: By shifting the problem from "finding a function" to "finding a measure," the non-convex control problem becomes a convex optimization problem. This ensures that if a solution is found, it is globally optimal for that level of approximation.
- Automatic Mode Discovery: The optimizer "decides" when it is best to hit the wall or switch feet to reach the target. The user doesn't have to hard-code the contact sequence.
- Simplicity in Execution: While the offline optimization is complex, the resulting controller is just a set of simple polynomial equations. This makes it incredibly fast to run on real-time hardware.
- Polynomial Complexity: For a fixed degree of approximation, the computational complexity grows polynomially with the number of states and inputs, offering a more scalable path than traditional grid-based dynamic programming.
Key Results
- Superior Reachability: In the pendulum-with-wall example, the proposed method found a controllable region larger than that of a standard MPC approach with a 10-step horizon. Specifically, it could stabilize states that MPC deemed "uncontrollable."
- Computational Efficiency: For the legged robot model (4 states, 2 inputs), the offline synthesis took about 10 minutes. Once synthesized, the online controller is "negligible" in terms of computation time, whereas an equivalent MPC would require solving a complex Mixed-Integer Quadratic Program (MIQP) every few milliseconds.
- Simpler Policies: The method produced a simple piecewise-affine controller that performed as well as or better than much more complex, computationally heavy alternatives.
Limitations and Future Work
- No Stability Guarantees: The process is currently heuristic; while it often produces stable controllers, there is no formal proof that the resulting closed-loop system will always be stable. Stability must be checked after the controller is generated.
- Numerical Sensitivity: The SDP solvers can sometimes struggle with numerical stability if the state space isn't scaled correctly or if the polynomial degree is too high.
- Parameter Tuning: Beyond choosing the degree of the polynomial, there are few "knobs" for the designer to turn to fine-tune the behavior, making it a bit of a "black box" once the optimization starts.
- Future Directions: The authors suggest exploring ways to rescale state constraints and system dynamics to improve solver reliability.
Summary updated