PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Robust Controlled Invariant Sets of Linear Systems

Matthias Rungger, Paulo Tabuada

arXiv:1601.00416v2math.OCcs.SYeess.SYmath.DS

TL;DR

Computing the maximal robust controlled invariant set remains open for many constraint sets, despite its role in characterizing feedbacks that keep trajectories within state constraints. The paper proposes outer and inner approximation algorithms; the outer sequence can approach the maximal set arbitrarily closely, while the inner iteration provides invariant approximations with a feedback at each step.

  • Problem

    Computing the maximal robust controlled invariant set remains open for many constraint sets, including finite unions of polytopes.

    Source: §1 · p. 2

  • Method

    The paper modifies dynamic programming to compute outer and inner invariant approximations of the maximal robust controlled invariant set.

    Source: §1 · p. 2

  • Results

    The outer sequence can approximate the maximal set arbitrarily closely, while iteration from {0} gives invariant inner approximations with a feedback available at every iteration.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The maximal robust controlled invariant set characterizes feedbacks that keep every trajectory within the state constraints for all time.

    Source: §1 · p. 1

    The outer sequence's iterates are generally not robust controlled invariant, so they do not yield a feedback that ensures trajectories remain in the state constraint set.

    Source: §1 · p. 2

Abstract

from arXiv · show

We consider controllable linear discrete-time systems with bounded perturbations and present two methods to compute robust controlled invariant sets. The first method tolerates an arbitrarily small constraint violation to compute an arbitrarily precise outer approximation of the maximal robust controlled invariant set, while the second method provides an inner approximation. The outer approximation scheme is $\delta$-complete, given that the constraint sets are formulated as finite unions of polytopes.

1. Introduction

For linear discrete-time systems with additive perturbations, the paper studies feedbacks that keep trajectories within state and input constraints. Because computing the maximal robust controlled invariant set remains open for many constraint sets, it proposes outer and inner invariant approximations.

1. Introduction

  • The dynamics are discrete-time linear systems with additive disturbances, and the state and input signals are constrained to specified sets.The disturbance set W is added to the possible next states.Source: §1 · p. 1
  • The maximal robust controlled invariant set characterizes feedbacks that keep every trajectory inside the state constraint set for all time.Determining this set is sufficient when seeking feedbacks that enforce the state and input constraints.Source: §1 · pp. 1–2
  • The paper proposes two algorithms, based on modifications of dynamic programming, for outer and inner invariant approximations of the maximal set.Computing the set remains open for many constraint sets, including finite unions of polytopes.Source: §1 · p. 2
  • The dynamic-programming sequence can approximate the maximal set arbitrarily closely, but its iterates generally are not robust controlled invariant and yield no guaranteed safe feedback.This limits the practical usefulness of that outer approximation sequence.Source: §1 · p. 2
  • When consecutive iterations coincide, the maximal robust controlled invariant set is finitely determined; controllable systems with zero disturbance and finite unions of hyper-rectangles are one covered case.The stated case assumes the system is in Brunovsky normal form.Source: §1 · p. 2
  • Starting the iteration at {0} yields invariant inner approximations converging to the maximal set's closure, with a feedback available at every iteration.This result is described for controllable systems with zero disturbance and polytope constraints whose origin lies in the interior.Source: §1 · p. 2

X. Additionally, due to the convergence of Ri, the mismatch between Ri and R(X) decreases as the computation continues.

The paper modifies dynamic-programming iterations to obtain outer and inner robust controlled invariant approximations under compact constraints and controllable dynamics. The outer method permits arbitrarily small constraint relaxation, while the inner method guarantees an invariant iterate without requiring a convex λ-contractive subset of the state constraints.

Outer approximation

  • For every ε > 0, an iterate yields an outer approximation that is invariant under δ-relaxed constraints, with δ = cε, and converges to R(X) as ε decreases to zero.The method can stop as an anytime scheme once the relaxation is tolerable.Source: §X · p. 3

Inner approximation

  • For any ρ > 0, the modified inner iteration reaches an iterate Ri+1 that is robust controlled invariant and satisfies Ri ⊆ Ri+1 + ρB.Conditions are also provided to ensure Ri+1 is nonempty.Source: §X · p. 3

Scope and assumptions

  • Unlike earlier approaches requiring a convex λ-contractive set containing the origin or restrictions on constraint shapes, the methods allow compact constraints and general disturbance sets, including finite unions of polytopes.The inner modification extends the λ-contractive-set idea to non-convex sets and removes the origin-containing-set requirement.Source: §X · p. 3

Completeness

  • For finite unions of polytopes, the outer scheme is δ-complete: it either certifies R(X) is empty or returns a δ-relaxed robust controlled invariant set.The iterates are computable in this setting.Source: §X · p. 3

2. Outer Invariant Approximation

The outer scheme augments finite-horizon reachable-set iterates with null-controllable sets to produce a robust controlled invariant set under slightly relaxed constraints. As ε decreases, the approximation converges to the maximal robust controlled invariant set in Hausdorff distance.

2. Outer Invariant Approximation

  • The stopping test (8) is reached after finitely many iterations for every ε > 0.This follows from the convergence of the iterates used in the proof of Lemma 1.Source: §2 · p. 4
  • Controllability supports constructing the added sets N_i^δ, which contain states that can be driven to the origin under δ-sized state and input constraints.The sets are computable by polyhedral projection and intersection; the proof bounds finite-horizon states and inputs using controllability.Source: §2 · p. 4
  • The constructed set R lies in X + δB and is robust controlled invariant with inputs in U + δB.The construction combines iterates with δ-constraint null-controllable sets.Source: §2 · p. 5
  • As ε → 0, the constructed sets converge to R(X) in Hausdorff distance; an empty approximation implies R(X) is empty.Here δ = cε, with c satisfying the stated bound condition.Source: §2 · p. 5
  • For polyhedral disturbances and constraints, iterates and the inclusion test are computable, but their worst-case complexity grows exponentially with the iteration index.The paper reports a nontrivial example where the algorithm runs to termination.Source: §2 · p. 6

3. Inner Invariant Approximation

The inner method uses tightened constraints and a robust invariant set for a perturbed system to obtain an inner approximation. Its iteration has a finite stopping index, and the construction yields a set contained in the maximal robust controlled invariant set.

3. Inner Invariant Approximation

  • For every ρ > 0, the iteration reaches a stopping index at which R_i+1^ρ is robust controlled invariant.The existence of the stopping index follows by the same arguments as for Lemma 1.Source: §3 · p. 6
  • For a suitable ρ, any robust controlled invariant set R̄_ε within the tightened state constraints and using tightened inputs is contained in R^ρ.The tightened sets require ε-balls around states and inputs to remain inside X and U, respectively.Source: §3 · p. 6
  • The construction enlarges R̄_ε by adding δ-constraint null-controllable sets, with δ = ε/n and cρ = δ.The proof chooses ρ using the constant c from Lemma 2.Source: §3 · p. 6
  • The resulting set K remains inside X and is robust controlled invariant for the perturbed system with inputs in U.The proof combines a control for R̄_ε with controls for the added null-controllable components.Source: §3 · p. 6

4. An illustrative example

The example computes outer and inner invariant approximations of a maximal robust controlled invariant set that is not finitely determined. The outer approximation becomes visually indistinguishable from the target at i = 3, while the inner method produces invariant approximations for two values of ρ.

Set computation

  • For this example, the set iterations are computed analytically as polytopes using the Pontryagin difference R_i ∼ W and projection.The iteration's limit is represented as R(X) = {x ∈ R2 | Hx ≤ h}.Source: §4 · p. 7

Example scope

  • The example's R(X) is not finitely determined, and W is nonzero, so cited methods for invariant approximation do not apply.The constraint set X contains the origin in its interior.Source: §4 · p. 7

Outer approximation

  • At i = 3, the outer approximation is visually indistinguishable from R(X) with δ = 8/243.The example uses c = 2 in the outer stopping construction.Source: §4 · pp. 7–8, Figure 2 · p. 8

Inner approximation

  • The inner-approximation procedure computes predecessors using the Pontryagin difference R_i ∼ (W + ρB).It displays invariant inner approximations for ρ = 1 and ρ = 1/10.Source: §4 · p. 8, Figure 3 · p. 8

5. Numerical Experiments

The numerical experiments approximate the invariant set for a four-state rotor-craft model with obstacle constraints and bounded perturbations. Across the tested perturbation and obstacle settings, the authors report successful approximation without the predicted exponential increase in half-spaces.

System model

  • The tested model is a four-state rotor craft whose first two states are position, last two are velocity, and acceleration is the input.The differential-inclusion parameters include τ = 2.6 seconds.Source: §5 · p. 8

Constraints and setup

  • The state constraint set includes obstacle regions, and the input is bounded by U = [−a_max, a_max].Obstacle count varies across the experiments; obstacle centers are randomly generated in their first two coordinates.Source: §5 · p. 9

Stopping criterion

  • For the unperturbed system, all states in the unit cube can be steered to the origin in two steps without leaving the cube.This gives c = 1 and permits the stopping criterion R_i ⊆ R_{i+2} + εB.Source: §5 · p. 9

Results

  • The experiments successfully approximate R(X) without observing the exponential half-space growth predicted by worst-case estimates.They vary perturbation level over 0, 0.1, and 0.2 and obstacle count over 0, 5, and 10, with ε = 0.01.Source: §5 · p. 9, Figure 4 · p. 9
Loading 1601.00416v2…