PaperlayerView exact revision on arXiv

Source-linked AI summary

Technical Report: Convex Optimization of Nonlinear Feedback Controllers via Occupation Measures

Anirudha Majumdar, Ram Vasudevan, Mark M. Tobenkin, Russ Tedrake

arXiv:1305.7484v1cs.ROcs.SYeess.SYmath.OC

TL;DR

The paper addresses feedback synthesis for nonlinear systems, where open-loop plans cannot correct path deviations and underactuated systems with input limits remain challenging. It uses occupation measures to formulate BRS maximization as a linear program and approximates it with semidefinite programs. The approximations provide outer bounds on the largest achievable BRS, with conservatism that vanishes asymptotically.

  • Problem

    Feedback control for underactuated nonlinear systems with input saturation remains challenging, and open-loop motion plans typically cannot correct deviations from planned paths.

    Source: A. Our Contributions · p. 1

  • Method

    The paper poses largest-BRS feedback synthesis as an infinite-dimensional linear program over measures and constructs finite-dimensional semidefinite relaxations.

    Source: A. Our Contributions · p. 1, D. BRS via an Infinite Dimensional LP · p. 4

  • Results

    Each SDP solution outer-approximates the largest achievable BRS with asymptotically vanishing conservatism, and a subsequence weakly converges to an optimizing LP solution.

    Source: A. Our Contributions · p. 1

  • Takeaways & Limitations

    The method can augment feedback motion-planning algorithms that sequence BRSs and may reduce the required controller library, potentially to one feedback law.

    Source: §V · p. 9

Abstract

from arXiv · show

In this paper, we present an approach for designing feedback controllers for polynomial systems that maximize the size of the time-limited backwards reachable set (BRS). We rely on the notion of occupation measures to pose the synthesis problem as an infinite dimensional linear program (LP) and provide finite dimensional approximations of this LP in terms of semidefinite programs (SDPs). The solution to each SDP yields a polynomial control policy and an outer approximation of the largest achievable BRS. In contrast to traditional Lyapunov based approaches which are non-convex and require feasible initialization, our approach is convex and does not require any form of initialization. The resulting time-varying controllers and approximated reachable sets are well-suited for use in a trajectory library or feedback motion planning algorithm. We demonstrate the efficacy and scalability of our approach on five nonlinear systems.

I. INTRODUCTION

Feedback synthesis for nonlinear, underactuated systems with input saturation remains challenging: open-loop plans cannot correct deviations, and common control approaches have important limitations. The paper formulates finite-time BRS maximization as a convex measure LP and develops SDP approximations.

I. INTRODUCTION

  • Feedback control remains challenging for underactuated nonlinear systems with input saturation, while open-loop plans typically cannot correct deviations from planned paths.Linearization-based methods may be limited to local regions, and dynamic programming and Hamilton–Jacobi–Bellman methods suffer from the curse of dimensionality.Source: §I · p. 1

A. Our Contributions

  • The paper formulates time-limited BRS maximization as an infinite-dimensional measure LP, constructs SDP relaxations, and proves outer-approximation and convergence properties.The method is intended for nonlinear underactuated robotic systems with input saturation and is demonstrated on five examples.Source: A. Our Contributions · pp. 1–2

B. Relationship to Lyapunov-Based Techniques

  • Unlike Lyapunov-based SOS synthesis, which is typically non-convex and requires feasible initialization, the paper's dual measure formulation yields a convex synthesis problem.The paper notes that this approach is not easily extended to regional certificates, which are practically useful in robotics.Source: B. Relationship to Lyapunov-Based… · p. 2

B. Problem Statement

  • For polynomial control-affine dynamics, the objective is to maximize the volume of initial states that stay within the bounding set and reach the target at the finite final time.The formulation assumes compact bounding and target sets and bounded control inputs.Source: B. Problem Statement · p. 2

II. PROBLEM FORMULATION

  • The problem formulation replaces simultaneous controller and Lyapunov-function search with conditions on measures, making the synthesis formulation convex.A signed measure representation of control makes the resulting operator equation linear in its measure components and allows recovery of a control law.Source: C. Liouville’s Equation · p. 3

D. BRS via an Infinite Dimensional LP

The infinite-dimensional LP maximizes the measure of the largest achievable BRS using measures for initial states, trajectories, and controls. Its optimizer yields a BRS-maximizing controller, while the dual provides BRS approximations.

D. BRS via an Infinite Dimensional LP

  • The LP maximizes the measure of the BRS represented by the support of the initial-state measure, with slack-measure constraints enforcing the initial-state and bounded-control conditions.The constraints include λ ≥ μ0 and μ ≥ [σ+]j + [σ−]j for each control component.Source: D. BRS via an Infinite Dimensional LP · p. 4
  • P and its dual D have no duality gap, and the optimal value of P equals the Lebesgue measure of the BRS for the constructed controller.The dual uses functions to produce BRS approximations.Source: D. BRS via an Infinite Dimensional LP · p. 4
  • The dual constraints are equivalent to requiring the dynamics inequality for every admissible control, linking the dual formulation to the original control problem.The proof compares the first three constraints in D with L_fv + (L_gv)u ≤ 0 for all states, times, and admissible controls.Source: D. BRS via an Infinite Dimensional LP · p. 4
  • A controller constructed from an optimizer of P maximizes the size of the BRS among admissible control laws.Any two controllers constructed from an optimizing measure tuple agree μ*-almost everywhere.Source: D. BRS via an Infinite Dimensional LP · p. 4

III. NUMERICAL IMPLEMENTATION

The infinite-dimensional programs are approximated by SDPs using measure moments and polynomial functions. Their solutions yield controllers and outer approximations that converge to the infinite-dimensional solution.

III. NUMERICAL IMPLEMENTATION

  • Moment representations and polynomial restrictions produce a sequence of finite-dimensional SDPs whose solutions yield controllers and convergent outer approximations of the infinite-dimensional LP solution.Polynomials are used as a dense subset of the relevant function space on the compact domain.Source: §III · p. 5
  • The polynomial representation uses a monomial basis, with the degree of a polynomial defined as the smallest k for which it belongs to Rk[x].The monomial exponents index the coefficient vector.Source: §III · p. 5
  • Polynomial coefficients and moments encode measures and polynomial integration as linear functionals of the coefficients.The implementation defines truncated moment matrices from measure moments; these matrices are positive semidefinite, with localizing matrices encoding support constraints.Source: §III · p. 5

A. Approximating Problems

The approximation replaces measures with truncated moment sequences and restricts functions to polynomials, producing primal and dual SDPs. The construction also provides a polynomial controller from the primal solution.

A. Approximating Problems

  • Restricting polynomial test functions to degree 2k turns the equality constraints into a finite linear system for truncated moments of the measures.The moment sequences are collected across the measures in Γ.Source: A. Approximating Problems · p. 5
  • Support constraints on the measures and a positive-semidefinite condition define the k-th relaxed SDP Pk over truncated moment sequences.Its given data include f, g, X, and XT.Source: A. Approximating Problems · p. 5
  • The dual SDP Dk restricts the dual functions to polynomials and replaces nonnegativity constraints with sums-of-squares constraints.The SOS representation ensures nonnegativity on the specified sets.Source: A. Approximating Problems · p. 6
  • Each pair of finite-dimensional primal and dual SDPs has no duality gap.The stated justification uses bounded moment vectors and an interior point in the feasible set of Dk.Source: A. Approximating Problems · p. 6
  • A polynomial controller is constructed from the Pk solution by choosing its coefficients to satisfy the truncated analogue of the measure-based controller relation.The coefficient equations are linear in the polynomial controller components.Source: A. Approximating Problems · p. 6

B. Convergence of Approximating Problems

As the relaxation degree increases, the polynomial outer approximations approach the BRS indicator and their superlevel sets approach the largest achievable BRS in measure. The optimal values also converge monotonically to the infinite-dimensional optimum.

B. Convergence of Approximating Problems

IV. EXAMPLES

The examples use progressively more complex nonlinear systems to evaluate the approach. The experiments also include free-final-time problems, where reaching the target is allowed at any time up to T.

IV. EXAMPLES

  • Simulation controllers use the saturation of the polynomial control law derived by the method.The SDPs use a custom toolbox and YALMIP, with SeDuMi for four examples and SDPT3 for the fourth example.Source: §IV · p. 7
  • The experiments cover example systems of increasing complexity, with SDPs solved on an 8-processor, 32 GB RAM machine.The report says source code is available for download.Source: §IV · p. 7
  • Some examples use a free-final-time objective, requiring initial conditions in X to reach XT at any time t in [0, T].The corresponding BRS approximation problem is addressed in [14], and the control synthesis follows using the paper's approach.Source: §IV · p. 7

A. Double Integrator

For the double integrator, the paper compares computed outer approximations with the analytically computable BRS and evaluates the resulting controllers. The approximations improve quickly as truncation degree increases, and k=3 already gives reasonable controller performance.

A. Double Integrator

  • The double integrator has two states, one input u in [-1, 1], and dynamics ẋ1 = x2 and ẋ2 = u.The target set is the origin, and the optimal BRS can be computed analytically using a minimum-time bang-bang controller.Source: A. Double Integrator · p. 7
  • Grid-based optimal control is challenging for this system because it requires high resolution near the bang-bang control law's switching surface.Source: A. Double Integrator · p. 7
  • The outer approximations improve quickly with degree, and k=3 already achieves reasonable controller performance; solve times for k=2, 3, and 4 are 0.3s, 0.7s, and 4.2s.Figure 2 compares the approximations with the true BRS and plots controlled terminal states.Source: Figure 2 · p. 7

B. Ground Vehicle Model

The ground-vehicle example applies the method to the Brockett integrator, a system with an uncontrollable linearization, using a free-final-time objective. The computed BRS approximation and feedback controller produce trajectories to the target, including a three-point turn in the original vehicle coordinates.

B. Ground Vehicle Model

  • The Dubin’s car model uses position and yaw states with forward-speed and turning-rate inputs; a coordinate change makes its dynamics polynomial.The transformed system is the Brockett integrator, a benchmark with an uncontrollable linearization that does not admit a smooth time-invariant controller making the origin asymptotically stable.Source: B. Ground Vehicle Model · p. 7
  • For the Brockett integrator, the k=5 approximation and feedback controller drive initial states to the target by T=4; solving the SDP takes 599 seconds.The target is a radius-0.12 ball, and the control inputs are restricted to [-1, 1].Source: B. Ground Vehicle Model · p. 7
  • Figure 3 shows the BRS approximation in two state-plane projections, with sampled starts ending in the target or near it; Figure 4 shows sample trajectories, including a three-point turn.Source: Figure 3 · p. 8, Figure 4 · p. 8

C. Torque Limited Simple Pendulum

The torque-limited pendulum example uses a free-final-time objective and adapts the method to trigonometric dynamics through a polynomial representation in sine and cosine. The controller swings up states near the downward position despite actuator limits and a short horizon.

C. Torque Limited Simple Pendulum

  • The pendulum dynamics include angle, angular rate, and torque input, with the torque constrained to [-3, 3].The example sets m = 1, l = 0.5, I = ml^2, b = 0.1, and g = 9.8.Source: C. Torque Limited Simple Pendulum · p. 8
  • The method handles trigonometric state dependence when the dynamics are polynomial in sine and cosine by introducing c and s with c = cos(x), s = sin(x), and c^2 + s^2 = 1.Source: C. Torque Limited Simple Pendulum · p. 8
  • The free-final-time problem uses T = 1.5, and the k=5 SDP takes 11 minutes 20 seconds.The target-set definition includes a constraint on cos(x1) and a bound on x2, although the supplied passage does not show the complete definition.Source: C. Torque Limited Simple Pendulum · p. 8
  • The controller swings up states near the downward position to the upright configuration despite stringent actuator limits and a short time horizon.Figure 5 depicts sampled initial conditions reaching the target and three sample solutions.Source: C. Torque Limited Simple Pendulum · p. 8, Figure 5 · p. 8

D. Planar Quadrotor

The planarized quadrotor example applies the proposed controller over a four-second horizon and produces a controller that stabilizes a large set of initial conditions.

D. Planar Quadrotor

  • The example uses a six-state, two-input planarized quadrotor with rotor thrust-to-weight ratio bounded at 2.5.The model parameters include rotor-arm length L = 0.25, mass m = 0.486, moment of inertia I = 0.00383, and gravity g = 9.8.Source: D. Planar Quadrotor · p. 8
  • 49 minutes: the SDP produced a controller able to stabilize a large set of initial conditions.The report illustrates representative closed-loop trajectories in Fig. 6.Source: D. Planar Quadrotor · p. 8
  • T=4: the free-final-time problem requires reaching XT = {x | ∥x∥2 ≤0.1} from X = {x | ∥x∥2 ≤1}.The controller design uses k = 2 and handles trigonometric terms as in the pendulum example.Source: D. Planar Quadrotor · p. 8

E. Satellite Attitude Control

The satellite attitude-control example demonstrates controller performance for a six-state, three-input system. The conclusion describes the convex SDP-based approach and notes that stronger convergence guarantees remain under development.

E. Satellite Attitude Control

  • The satellite example uses a six-state, three-input thruster model, diagonal inertia [2,1,1], input constraints U = [−1, 1]3, and the origin as target.The k = 3 controller design is applied to this setup.Source: E. Satellite Attitude Control · pp. 8–9
  • In the k = 3 demonstration, black points satisfy ∥x(T)∥≤0.1 and grey points satisfy ∥x(T)∥≤0.2; the SDP took approximately 6 hours.The figure shows samples from the bounding set and the set where w(x) ≤1; k = 2 took 5 minutes and yielded slightly inferior but still useful results.Source: E. Satellite Attitude Control · p. 9, Figure 7 · p. 9

V. CONCLUSION

  • Occupation-measure LPs yield finite SDP approximations, outer approximations of the largest achievable BRS, and polynomial control laws; unlike Lyapunov-based approaches, the method is convex and needs no feasible initialization.The control laws approximate the optimal control law.Source: §V · p. 9
  • The method could augment feedback motion-planning algorithms and potentially reduce the number of distinct controllers needed, in some cases to a single feedback law.The conclusion also says the algorithm should obtain improved performance during dynamic tasks while maintaining robustness.Source: §V · p. 9
  • Set-wise convergence of the generated controllers’ BRS to the largest achievable BRS remains under study; the sought guarantee is stronger than Theorem 8.The authors are also working to extend the method to hybrid dynamical systems.Source: §V · p. 9
Loading 1305.7484v1…