Abstract
We consider the feedback design for stabilizing a rigid body system by making and breaking multiple contacts with the environment without prespecifying the timing or the number of occurrence of the contacts. We model such a system as a discrete-time hybrid polynomial system, where the state-input space is partitioned into several polytopic regions with each region associated with a different polynomial dynamics equation. Based on the notion of occupation measures, we present a novel controller synthesis approach that solves finite-dimensional semidefinite programs as approximations to an infinite-dimensional linear program to stabilize the system. The optimization formulation is simple and convex, and for any fixed degree of approximations the computational complexity is polynomial in the state and control input dimensions. We illustrate our approach on some robotics examples.
Introduction: The Challenge of Hybrid Dynamics
Controlling robots that interact with their physical environment—such as legged robots or manipulators—is notoriously difficult because their dynamics are "hybrid." A walking robot's physics change abruptly the moment its foot touches the floor, creating discontinuities that traditional control methods struggle to manage.
Linear Quadratic Regulators (LQR) typically only work for smooth, local dynamics and cannot anticipate mode switches. Trajectory optimization often requires designers to pre-specify the exact sequence of contacts (e.g., "step left, then step right"), which limits flexibility. Meanwhile, global methods like Dynamic Programming suffer from the "curse of dimensionality," becoming computationally impossible as the number of robot joints increases. This paper introduces a convex optimization framework that synthesizes simple polynomial control policies capable of automatically managing mode transitions across large regions of the state space.
Methodology: From Measures to Moments
The authors model the robot as a discrete-time hybrid polynomial system, where the state-input space is partitioned into regions, each governed by its own polynomial dynamics. The core technical innovation is the shift from searching for a control law directly to searching for occupation measures.
Instead of finding a function, the approach looks for a "measure" that describes the distribution of time a robot spends in different states and actions.
- Liouville Equation: A discrete-time version of this equation is used 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 infinite-dimensional and unsolvable directly.
- SDP Relaxations: To make it solvable, the authors 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, a simple polynomial feedback policy is extracted from the resulting "moments" of the measures.
Experimental Benchmarks
The framework was evaluated on two simulated robotics benchmarks: a linear inverted pendulum with an elastic wall and a variable height inverted pendulum representing a legged robot.
Key Insights and Results
By shifting the problem to measure-based optimization, the non-convex control problem becomes a convex one. This ensures that any solution found is globally optimal for that specific level of approximation.
- Automatic Mode Discovery: The optimizer autonomously "decides" when it is best to hit a wall or switch feet to reach the target. The user does not have to hard-code the contact sequence.
- Superior Reachability: In the pendulum-with-wall example, the proposed method found a controllable region significantly larger than that of a standard Model Predictive Control (MPC) approach with a 10-step horizon. It successfully stabilized states that MPC deemed "uncontrollable."
- Computational Efficiency: For a 4-state legged robot model, offline synthesis took approximately 10 minutes. Once synthesized, the resulting online controller is a set of simple polynomial equations that execute with negligible latency, whereas an equivalent MPC would require solving complex optimization problems every few milliseconds.
Limitations and Future Outlook
While the method is powerful, it currently lacks formal stability guarantees; the resulting closed-loop system must be verified after the controller is generated. Additionally, SDP solvers can be sensitive to numerical stability if the state space is not scaled correctly or if the polynomial degree is too high. Future research will explore automated ways to rescale state constraints and system dynamics to improve solver reliability and robustness.
Summary updated