Source-linked AI summary
A Duality-Based Optimization Formulation of Safe Control Design with State Uncertainties
Xiao Tan, Rahal Nanayakkara, Paulo Tabuada, Aaron D. Ames
TL;DR
State uncertainty complicates safety-critical control because standard CBF conditions presume perfect state information, while robust alternatives can be conservative. The paper analyzes the CBF-coefficient image of the possible-state set and uses duality for tractable reformulations; simulations report less conservative safety control than the alternatives discussed.
Problem
Standard CBF methods assume perfect state information, but safety with state uncertainty requires the CBF inequality to hold over the entire set of possible states.
Source: §I · p. 1Method
The method formulates a robust safety filter using the image of the possible-state set under CBF dynamics, proves convexification preserves feasible inputs, and applies duality for polytopic or ellipsoidal hulls.
Source: §I · p. 1, A. Exactness of the Convex Hull… · p. 3, B. Polytopic Uncertainty · p. 4Results
The method maintains h(x) ≥ 0 for all tested uncertainty magnitudes δ with minimal conservatism, while regular CBFs fail for δ > 0 and MR-CBF becomes infeasible for δ > 0.1.
Source: §IV · p. 5Takeaways & Limitations
Polytopic or ellipsoidal over-approximations can eliminate the need for Lipschitz-constant estimates and yield less conservative solutions than prior methods.
Source: §V · p. 6Guaranteeing recursive feasibility of the closed-loop system remains an open problem.
Source: §V · p. 6
Abstract
from arXiv · showhide
State estimation uncertainty is prevalent in real-world applications, hindering the application of safety-critical control. Existing methods address this by strengthening a Control Barrier Function (CBF) condition either to handle actuation errors induced by state uncertainty, or to enforce stricter, more conservative sufficient conditions. In this work, we take a more direct approach and formulate a robust safety filter by analyzing the image of the set of all possible states under the CBF dynamics. We first prove that convexifying this image set does not change the set of possible inputs. Then, by leveraging duality, we propose an equivalent and tractable reformulation for cases where this convex hull can be expressed as a polytope or ellipsoid. Simulation results show the approach in this paper to be less conservative than existing alternatives.
I. INTRODUCTION
State uncertainty makes standard CBF safety control depend on an unknown true state, requiring the CBF condition to hold across all possible states. The paper proposes a robust filter based on the uncertainty image under CBF dynamics and a duality-based reformulation.
I. INTRODUCTION
- The standard CBF framework assumes perfect state information, while observer bounds can provide a deterministic set guaranteed to contain the true state.Safety under this uncertainty requires satisfying the CBF inequality over that entire set.Source: §I · p. 1
- Prior deterministic approaches either bound state-dependent coefficients with Lipschitz constants or address actuation errors; the paper focuses on deterministic state uncertainty, not probabilistic guarantees.The cited Lipschitz approach is described as overly conservative, with feasibility largely unanswered.Source: §I · p. 1
- The proposed safety filter enforces a CBF constraint across the entire set of possible states.The paper frames this as a robust optimization problem.Source: §I · p. 1
- Convexifying the image of state uncertainty under the CBF coefficient maps preserves the feasible solutions of the robust optimization problem.The paper then treats cases where the convex hull is a polytope or ellipsoid.Source: §I · p. 1
- For polytopic or ellipsoidal convex hulls, duality yields an equivalent reformulation that is efficient to solve online.The paper contrasts its uncertainty-set computation with the coarse Lipschitz-constant over-approximation used in.Source: §I · p. 1
II. PRELIMINARIES
The preliminaries introduce notation and the assumed control system. They define norms, Lie derivatives, Minkowski sums, and class K functions, and specify the state, input, and regularity assumptions.
II. PRELIMINARIES
- The notation defines the Euclidean norm and the L∞ norm for essentially bounded signals.The latter is expressed as an essential supremum over time.Source: §II · p. 1
- The preliminaries define L_f h as a Lie derivative, A ⊕ B as a Minkowski sum, and class K functions by monotonicity and their value at zero.An extended class K function is also defined on R.Source: §II · p. 1
- The system state is x ∈ R^n and the input is u ∈ U ⊂ R^m, with U assumed to be a polytope.The vector fields f and g are locally Lipschitz continuous.Source: §II · pp. 1–2
A. Control Barrier Functions
The CBF preliminaries connect a safe set to a barrier condition and a control law. A qualifying CBF condition supports forward invariance, and the paper describes computing a minimally invasive safe input relative to a desired controller.
A. Control Barrier Functions
- The safe region is C = {x ∈ R^n : h(x) ≥ 0}, and safety means that C is forward invariant.The passage identifies CBFs as one way to enforce this state constraint.Source: A. Control Barrier Functions · p. 2
- A continuously differentiable h is a CBF when the stated existence condition holds for an open set containing C and an extended class K function.The definition is attributed to.Source: A. Control Barrier Functions · p. 2
- The CBF dynamics include the derivative L_f h(x) + L_g h(x)u, and a locally Lipschitz control law satisfying the stated condition renders C forward invariant.Given a desired, potentially unsafe controller, the passage points to a minimally invasive safe control law.Source: A. Control Barrier Functions · p. 2
B. A Dynamic Uncertainty Perspective
A state estimate can produce a dynamic disturbance when used instead of the true state in feedback. The ISSf and R-CBF perspective gives robustness guarantees for disturbed dynamics, but may yield inflated-set guarantees or conservative conditions.
B. A Dynamic Uncertainty Perspective
- Using a state estimate instead of the true state in feedback introduces a dynamic disturbance d = k(ˆx) − k(x).When the estimation error is bounded and k is locally Lipschitz, d is bounded for bounded x.Source: B. A Dynamic Uncertainty Perspective · p. 2
- An ISSf-CBF constraint ensures forward invariance of an inflated safe set under the perturbed dynamics.The neighborhood of the original safe set scales with the disturbance magnitude.Source: B. A Dynamic Uncertainty Perspective · p. 2
- R-CBF parameters γ1 and γ2 set the disturbance threshold for guarantees on the original or an inflated safe set, but systematic tuning for known full-state uncertainty remains unclear.Online parameter adaptations are cited in [12].Source: B. A Dynamic Uncertainty Perspective · p. 2
- In the scalar example, MR-CBF is infeasible because L_g h(ˆx) = 0 reduces its condition to ∥u∥ < 0, while R-CBF remains feasible.The R-CBF guarantee may concern an inflated safe set even when an input could preserve the original set; the cited method in is inapplicable when L_g h changes sign on the uncertainty interval.Source: B. A Dynamic Uncertainty Perspective · p. 2
C. Problem Formulation
The controller uses the estimate and a bounded set of possible estimation errors to enforce the CBF condition for every compatible state. Under regularity conditions, this robust constraint guarantees forward invariance, though continuous uncertainty sets yield infinitely many constraints.
C. Problem Formulation
- The robust controller enforces the CBF inequality for every state consistent with the estimate and error set B.The possible states are {x̂} ⊕ B.Source: C. Problem Formulation · pp. 2–3
- If the controller is well-defined and locally Lipschitz, its robust CBF constraint makes the safe set C forward invariant.The guarantee applies to the closed-loop system using u = k_ro(x̂, B).Source: C. Problem Formulation · p. 3
- For continuous error sets B, the robust problem has infinitely many linear constraints on u and is intractable to solve directly.The paper seeks an efficient computation with little to no conservativeness.Source: C. Problem Formulation · p. 3
III. A DUALITY-BASED OPTIMIZATION REFORMULATION
The reformulation represents state uncertainty through the joint image of the CBF coefficients, rather than treating those coefficients as independent. This matters because independent uncertainty bounds can rule out inputs that satisfy the CBF constraint for every possible state.
III. A DUALITY-BASED OPTIMIZATION REFORMULATION
- The robust feasible input set consists of inputs satisfying the affine CBF constraint for every possible state, and is convex.The coefficients are a(ξ) = L_gh(ξ)^⊤ and b(ξ) = L_fh(ξ) + α(h(ξ)).Source: §III · p. 3
- Independent uncertainty sets for a and b can be conservative because they discard the coefficients’ shared dependence on the same uncertain state ξ.The paper notes that established polytopic or ellipsoidal reformulations applied this way may be conservative.Source: §III · p. 3
- For x ∈ [0.95, 1.05], independent coefficient bounds admit no feasible u, although u = 2 satisfies the CBF inequality for every possible state.The example gives separate ranges for a(x) and b(x).Source: §III · p. 3
A. Exactness of the Convex Hull Relaxation
Replacing the uncertainty image with its convex hull preserves the robust feasible inputs and motivates tractable reformulations for convex-shaped uncertainty sets. A feasibility condition also characterizes when an unconstrained-input robust problem can be solved.
A. Exactness of the Convex Hull Relaxation
- Replacing uncertainty image P by its convex hull P̃ preserves the feasible inputs and therefore the optimal safe input without added conservatism.The paper then focuses on exact polytopic or ellipsoidal hulls, with close over-approximations proposed when needed.Source: A. Exactness of the Convex Hull… · p. 3
- When U = R^m, disjointness of P̃ from N = {0}^m × (−∞, 0] is sufficient for feasibility of the robust optimization problem (14).Because N is convex and closed, while P̃ is convex and compact, strict hyperplane separation gives a nonzero vector (µ, t) and γ [18].Source: A. Exactness of the Convex Hull… · p. 3
- If the control gain is sign-indefinite across P̃, feasibility requires the natural dynamics to satisfy the CBF constraint throughout P̃.The stated condition is ζ_b ≥ 0 for all (ζ_a, ζ_b) ∈ P̃.Source: A. Exactness of the Convex Hull… · p. 4
B. Polytopic Uncertainty
For compact polytopic uncertainty, duality converts the inner robust constraint into a finite set of linear constraints. The resulting quadratic program yields the same safe input as the original robust controller when its feasible set is nonempty.
B. Polytopic Uncertainty
- Under the compact-polytope assumption, the inner robust optimization problem becomes a linear program whose dual can express the robust constraint.The polytope is specified by known C and d.Source: B. Polytopic Uncertainty · p. 4
- Strong duality makes the robust constraint feasible exactly when a dual multiplier λ satisfies the dual constraints and −d^⊤λ ≥ 0.This yields a quadratic program that can be solved online.Source: B. Polytopic Uncertainty · p. 4
- If the robust feasible set is nonempty, the duality-based controller exists and equals the original robust controller.This equivalence holds under Assumption 1.Source: B. Polytopic Uncertainty · p. 4
C. Ellipsoidal Uncertainty
For ellipsoidal uncertainty, duality yields an equivalent SDP reformulation of the robust safety filter. When the coefficient-image hull is not polytopic or ellipsoidal, an outer approximation is needed, and its tightness determines conservatism.
C. Ellipsoidal Uncertainty
- Strong duality holds for the inner problem because its linear-cost optimization has a nonempty ellipsoidal feasible set.This gives equality between the primal and dual optimal values for any input.Source: C. Ellipsoidal Uncertainty · p. 4
- Under the ellipsoid assumption, the reformulated controller exists and equals the robust optimizer whenever the robust feasible set is nonempty.The reformulation is expressed as a semidefinite program.Source: C. Ellipsoidal Uncertainty · pp. 4–5
- When the convex coefficient-image hull is neither polytopic nor ellipsoidal, a containing polytope or ellipsoid is needed before applying the reformulations.The resulting safety condition is sufficient, and conservatism depends on how tight the outer approximation is.Source: C. Ellipsoidal Uncertainty · p. 5
IV. SIMULATIONS
The simulations compare polytopic and ellipsoidal over-approximations in two examples. In Example 2, the proposed method maintains safety with minimal conservatism; in the Segway example, tested trajectories remain safe across uncertainty levels.
Example 2
- A supporting-hyperplane procedure over sampled directions constructs a polytopic over-approximation; increasing the number of directions approaches the exact convex hull.With p = 16 directions, additional conservatism comes from over-approximating the convex hull, not from convexifying the image set.Source: §IV · p. 5
- The proposed method guarantees safety while minimizing conservatism, whereas large-γ R-CBFs demand large inputs and regular or small-γ CBFs violate safety.The simulations use OSQP over 20 seconds with 0.02-second steps.Source: §IV · p. 5, Figure 2 · p. 5
- The proposed method maintains h(x) ≥ 0 across tested δ values with minimal conservatism, unlike regular CBFs, R-CBFs, and MR-CBFs.Regular CBFs fail for any δ > 0; MR-CBFs become infeasible for δ > 0.1, while R-CBFs remain highly conservative.Source: §IV · p. 5, Figure 2 · p. 5
Example 3
- In the Segway example, trajectories remain in the safe region across tested uncertainty levels using an ellipsoid fit to 1,000 state samples.The study compares against a state-estimate regular CBF and a tuned R-CBF; both comparison approaches also guarantee invariance in this setup.Source: §IV · p. 6, Figure 3 · p. 6
V. CONCLUSION
The paper concludes that convexifying the image of state uncertainty under the CBF coefficient maps preserves the robust optimization problem, and that duality gives equivalent tractable reformulations for polytopic or ellipsoidal hulls. Over-approximations can yield less conservative solutions than prior methods, but recursive feasibility remains open.
V. CONCLUSION
- Replacing the image of state uncertainty under the CBF coefficient maps with its convex hull does not add conservatism to the robust optimization problem.When the hull is polytopic or ellipsoidal, duality yields equivalent tractable reformulations.Source: §V · p. 6
- Polytopic or ellipsoidal over-approximations can eliminate Lipschitz-constant estimates and provide less conservative solutions than prior methods.The conclusion supports this with two case studies.Source: §V · p. 6
- Guaranteeing recursive feasibility of the closed-loop system remains an open problem.The paper identifies it as future research.Source: §V · p. 6