PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Safety Filtering via Spectral Selection for Nonconvex Safe Sets

Juan Augusto Paredes Salazar, James Usevitch, Ankit Goel

arXiv:2610.12324v1eess.SYcs.SYmath.OC

TL;DR

Discrete-time barrier constraints can be nonconvex in the input for safe sets that are unions of convex sets. The paper uses current-state eigenvectors to construct a convex constraint on the membership-determining eigenvalues; in simulation, the selected filter preserves safety and runs more than an order of magnitude faster than the full-matrix filter.

  • Problem

    For safe sets that are unions of convex sets, the discrete-time barrier condition is nonconvex in the input, complicating safety filtering.

    Source: §I · p. 1

  • Method

    The method selects eigenvectors of the matrix function at the current state to form a convex input constraint on eigenvalues determining set membership.

    Source: §I · p. 2

  • Results

    The selected filter's QP is more than an order of magnitude faster than the full-matrix SDP, while both filters preserve forward invariance and their trajectories nearly coincide.

    Source: C. Results · p. 6

  • Takeaways & Limitations

    The proposed constraint is implied by the full-matrix condition, admits at least as many inputs at each state, and gives membership-determining eigenvalues a geometric lower bound along closed-loop trajectories.

    Source: §I · p. 2, §VI · p. 6

    Joint feasibility for multiple obstacles, simulations with several required nonnegative eigenvalues, and noisy or uncertain UAV and legged-robot applications remain future work.

    Source: §VI · p. 6

Abstract

from arXiv · show

The discrete-time control barrier function condition for a safe set that is a union of convex sets is nonconvex in the control input. For safe sets defined by a matrix concave function through the number of its nonnegative eigenvalues, this paper shows that the set is a union of convex sets, and that the nonconvexity arises because at least one member of the union must hold, not every member. Selecting eigenvectors of the matrix function at the current state yields a convex input constraint that acts only on the eigenvalues determining membership in the set. This constraint is implied by the matrix-wide condition of prior work, and it guarantees a geometric lower bound on each of those eigenvalues along closed-loop trajectories. A double-integrator simulation with a polytope obstacle and a spectrahedron obstacle compares the proposed filter with the matrix-wide condition.

I. INTRODUCTION

Discrete-time safety filtering becomes nonconvex when the next-state barrier condition is nonconcave in the input, a challenge for safe sets that are unions of convex sets. The paper develops a convex constraint by selecting eigenvectors of the matrix function at the current state.

I. INTRODUCTION

  • A nonconvex safe set does not itself force a nonconvex filter, but evaluating a discrete-time barrier at the next state is generally nonlinear in the input.For unions of convex sets, the constraint can be nonconvex because at least one member of the union must hold.Source: §I · pp. 1–2
  • Prior matrix-wide filtering constrains eigenvalues that do not determine set membership, while its alternative requires projection onto unsafe-set components.Other convex constructions rely on specific dynamics or obstacle geometry and can restrict admissible states or inputs.Source: §I · pp. 1–2
  • Selecting current-state eigenvectors yields a convex input constraint for any number of required nonnegative eigenvalues, without unsafe-set projection.The full-matrix condition of [21] implies the proposed constraint, which therefore admits at least as many inputs at each state.Source: §I · p. 2

B. Matrix Concavity

Matrix concavity makes scalar quadratic forms of the matrix function concave and is preserved under affine composition and orthonormal compression. In the discrete-time matrix barrier framework, this structure makes the input condition convex and supports forward invariance.

B. Matrix Concavity

  • A matrix-valued function is matrix concave when its matrix concavity condition holds; equivalently, every scalar function v^T H(x) v is concave.The passage also states that affine composition and orthonormal compression preserve matrix concavity.Source: B. Matrix Concavity · p. 2

C. Discrete-Time Matrix Control Barrier Functions

  • For the discrete-time system, forward invariance means that every trajectory starting in the set remains there at all subsequent steps.The system state is x_k and its control input is u_k.Source: C. Discrete-Time Matrix Control… · p. 2
  • The prior discrete-time matrix barrier condition renders the safe set forward invariant when the control input satisfies its constraint at every step.When H is matrix concave, that condition is a linear matrix inequality in the input and defines a convex constraint.Source: C. Discrete-Time Matrix Control… · p. 2

D. Safe Subset Functions

Prior safe-subset filtering represents a convex subset through a two-argument function and uses a discrete-time matrix barrier condition to guarantee forward invariance. Its projection-based construction targets safe sets formed as intersections of complements, whereas this paper addresses safe sets that are unions of convex sets.

D. Safe Subset Functions

  • Prior work replaces H with a two-argument function whose first argument tests a point's safety and whose second selects a convex subset.The present paper constructs that subset by a different mechanism for safe sets that are themselves unions of convex sets.Source: D. Safe Subset Functions · pp. 2–3
  • A control law satisfying the SDTE-MCBF input condition at every step renders the safe set forward invariant.The condition requires an admissible input for each state in the specified domain.Source: D. Safe Subset Functions · p. 3
  • The prior construction projects onto each convex unsafe-set component and forms a separating hyperplane, requiring the unsafe set to lie in a finite union of closed convex sets.That setting makes the safe set an intersection of complements; this paper instead treats a safe set that is a union of convex sets.Source: D. Safe Subset Functions · p. 3

III. NONCONVEX SAFE SETS ARISING FROM CONVEX OBSTACLES

Complements of convex obstacles can produce nonconvex safe sets whose discrete-time barrier constraints are nonconvex in the input. The section illustrates this with polytope and spectrahedron obstacles.

III. NONCONVEX SAFE SETS ARISING FROM CONVEX OBSTACLES

  • The complement of a polytope is a finite union of halfspaces, while the complement of a spectrahedron is a union indexed by unit vectors.Figure 1 also depicts a union of convex cells.Source: Figure 1 · p. 3

A. Complement of a Polytope

  • For a polytope obstacle, the barrier constraint confines the input to a union of p halfspaces.Enforcing all p inequalities simultaneously corresponds to the matrix condition, which is empty when the polytope is bounded.Source: A. Complement of a Polytope · p. 3

B. Complement of a Spectrahedron

  • For a spectrahedron obstacle, the safe set is described by a matrix-concave function, but its largest-eigenvalue barrier constraint is nonconvex in the input.The complement is a union of halfspaces indexed by unit vectors.Source: B. Complement of a Spectrahedron · p. 3, §III · p. 3

C. Union of Convex Sets

When the matrix function is matrix concave, these safe sets can be represented as unions of convex sets. Their discrete-time filter is nonconvex because at least one member, rather than every member, must hold.

C. Union of Convex Sets

  • A union of convex cells or corridors is one setting in which this safe-set construction arises.A block-diagonal matrix function does not encode the union through the largest-eigenvalue condition.Source: C. Union of Convex Sets · p. 3
  • For a union of Q safe sets, the maximum of their concave scalar functions yields a discrete-time constraint that confines the input to a union of Q convex sets.Each scalar function is the largest eigenvalue of its matrix function.Source: C. Union of Convex Sets · p. 3

D. Summary

  • Across the cases considered, nonconvexity arises because at least one of the convex-set inequalities must hold, and selecting a member at each step yields a convex constraint that preserves forward invariance.The section identifies the same union-of-convex-sets structure for all three cases.Source: D. Summary · p. 4

IV. DISJUNCTIVE SAFE SETS AND CONVEX SAFETY FILTERS

For matrix-concave safe-set functions, the paper represents disjunctive membership as a union of convex sets. Selecting eigenvectors at the current state produces a convex constraint that preserves forward invariance and bounds the relevant eigenvalues along trajectories.

A. Disjunctive Safe Sets

  • When H is matrix concave, the disjunctive safe set is a union of convex sets indexed by orthonormal matrices Y.Each member is defined by a projected matrix inequality.Source: A. Disjunctive Safe Sets · p. 4

B. Eigenvector Selection

  • At each step, selecting eigenvectors of H(xk) associated with the relevant eigenvalues fixes the subspace used in the convex constraint.The selected eigenvectors attain the maximum in the Courant–Fischer characterization at the current state.Source: B. Eigenvector Selection · p. 4
  • Satisfying the selected constraint at every step makes the set forward invariant and ensures λi(H(xk+1)) ≥ (1 − γ)λi(H(xk)) for i from j through p.The constraint is a convex matrix inequality in the control input.Source: B. Eigenvector Selection · p. 4
  • Even if λj(H(x0)) is negative, it converges exponentially to zero from below, so the state approaches S(j) in the sense of that eigenvalue.Source: B. Eigenvector Selection · p. 4
  • Changing the selected subspace does not affect pointwise forward invariance, but switching affects the conservatism of the constraint.The trajectory remains in the currently selected convex subset until the selection changes.Source: B. Eigenvector Selection · p. 4
  • The selected safe-subset function avoids projection onto the unsafe set, unlike the construction in [21].The paper applies the SDTE-MCBF framework directly to this function.Source: B. Eigenvector Selection · p. 4

C. Comparison with a Full-Matrix Condition

The full-matrix condition guarantees forward invariance and a geometric lower bound on the membership-determining eigenvalue. It is at least as restrictive as the selected-compression condition because it also constrains eigenvalues that do not determine membership.

C. Comparison with a Full-Matrix Condition

  • λ_j(H(x_k)) ≥ (1 − γ)^k λ_j(H(x_0)) for all k ≥ 0, and S(j) is forward invariant when (24) holds at every step.Every input satisfying (24) also satisfies (21).Source: C. Comparison with a Full-Matrix… · p. 5
  • Condition (24) constrains all p eigenvalues, including the j − 1 smallest eigenvalues that do not affect membership in S(j).By contrast, (21) acts only on the r-dimensional compression that determines membership.Source: C. Comparison with a Full-Matrix… · p. 5
  • Condition (24) is convex in u when H is matrix concave, the same condition required for (21).Thus, the full-matrix condition's greater restrictiveness does not reduce the convexity requirement.Source: C. Comparison with a Full-Matrix… · p. 5

D. Specialization to the Sets of Section III

For the three set constructions, the selected constraint uses an eigenvector of the current matrix function, yielding a convex program whose form depends on the set. The filter requires one eigenvector computation per step in addition to that program.

D. Specialization to the Sets of Section III

  • For the polytope and spectrahedron cases, the selected vector is a unit eigenvector associated with λ_p(H(x_k)); the polytope uses an indexed coordinate vector, while the spectrahedron uses the leading eigenvector of its negated matrix.The spectrahedron constraint is linear in u because its matrix function is affine.Source: D. Specialization to the Sets of… · p. 5
  • For a union of convex sets, the filter selects the index maximizing h_i(x_k) and constrains that selected function at the next state.The resulting inequality is h_i*(f(x_k) + g(x_k)u) ≥ (1 − γ)h_i*(x_k).Source: D. Specialization to the Sets of… · p. 5
  • The polytope and spectrahedron filters are quadratic programs with one linear constraint, while the union-of-sets filter is a semidefinite program sized for one selected convex set.Each case also requires one eigenvector computation of a p × p matrix per step.Source: D. Specialization to the Sets of… · p. 5

V. NUMERICAL SIMULATIONS

The simulation uses two discretized planar double integrators tracking a constant reference, with a pentagonal polytope and a spectrahedron placed between the initial state and the reference. Each obstacle is handled separately, preserving forward invariance of their intersection.

A. Setup

  • The simulation places a regular pentagon and a spectrahedron between the initial state and the constant reference for two planar double integrators.The nominal controller is a reference-tracking LQR controller, and both obstacles depend only on position.Source: A. Setup · p. 5
  • The pentagon has circumradius 2 m and the spectrahedron has p = 3; each receives a 0.2 buffer through its stated geometric adjustment.The pentagon uses a halfspace offset, while the spectrahedron is scaled about its center.Source: A. Setup · p. 5
  • The two obstacles are imposed as separate constraints, and applying Theorem 2 independently to each preserves forward invariance of their intersection.The resulting safe set is the conjunction of two disjunctive sets.Source: A. Setup · p. 5

B. Safety Filters

The safety-filter comparison includes a selected-eigenvector filter and a full-matrix condition applied to both obstacles. The full-matrix approach can trap the system near an obstacle, so its implementation adds a boundary-motion term.

B. Safety Filters

  • The selected filter uses one linear constraint per obstacle and solves a quadratic program, while the full-matrix alternative is included to quantify its conservatism.Both obstacles use γ = 0.2 in the comparison.Source: B. Safety Filters · p. 5
  • The full-matrix condition can trap the system near an obstacle, so the comparison modifies it to permit movement along the boundary perpendicular to the closest-point normal.The example sets c_perp > 0.05.Source: B. Safety Filters · p. 6
  • The simulations run for k ∈ {0, ..., 1200} on a laptop with MATLAB R2024b Update 5.The computer uses Windows 10 Pro and an Intel Core i7-10750H processor.Source: B. Safety Filters · p. 6

C. Results

Both filters preserved the safe sets in simulation, with position trajectories differing by centimeters, while the proposed QP had a lower reported solve time. The conclusions are bounded by solver-stack differences and unestablished joint feasibility for multiple obstacles.

C. Results

  • 1.9 ms for the proposed QP versus 92 ms for the full-matrix SDP was the reported mean solve time per step.The two filters used different solver stacks, so the ratio does not isolate the effect of the constraint.Source: Table I · p. 6, §VI · p. 6
  • Both filters kept both safe sets invariant, and their position trajectories differed by centimeters.The eigenvalue traces remained nonnegative, while the position trajectories nearly coincided.Source: Figure 3 · p. 6, Figure 2 · p. 6, C. Results · p. 6

VI. CONCLUSIONS

  • For matrix-concave functions, the safe set is a union of convex sets, and selecting current-state eigenvectors yields a convex input constraint for any required number of nonnegative eigenvalues.The construction uses one eigendecomposition and one convex program per step, without projection onto the unsafe set.Source: §VI · p. 6
  • The proposed constraint guarantees a geometric lower bound on each membership-determining eigenvalue and admits at least as many inputs as the full-matrix condition.The full-matrix condition implies the proposed constraint.Source: §VI · p. 6
  • The simulations used one required nonnegative eigenvalue, and joint feasibility of constraints from multiple obstacles was assumed rather than established.The paper identifies simulations with several required eigenvalues and joint feasibility as future work.Source: §VI · p. 6
Loading 2610.12324v1…