Projects

Viability Kernels for Linear Systems

A sampling-based algorithm to under-approximate the viability kernel of high-dimensional linear sampled-data systems, using zonotope reachability instead of a per-point linear-feasibility program.

Setting

We are given a sampled-data linear system xk+1=Aρxk+Bρukx_{k+1} = A_\rho x_k + B_\rho u_k, with state constraint xk∈Kx_k \in \mathcal{K} and piecewise-constant input uk∈Uu_k \in \mathcal{U}, both compact and convex. The finite-horizon viability kernel is the set of initial states from which at least one input sequence keeps the trajectory inside K\mathcal{K} for NρN_\rho steps,

ViabTsd(K)={x0∈K∣∃{uk}k=0Nρ−1⊂U:xk∈K, ∀k≤Nρ}.\text{Viab}_T^{sd}(\mathcal{K}) = \{x_0 \in \mathcal{K} \mid \exists \{u_k\}_{k=0}^{N_\rho-1} \subset \mathcal{U}: x_k \in \mathcal{K},\ \forall k \le N_\rho\}.

Computed once offline, this set acts as a hard safety filter on top of any controller.

Approach

The algorithm builds on Gillula et al.'s sampling idea: from an interior seed v0∈ViabTsd(K)v_0 \in \text{Viab}_T^{sd}(\mathcal{K}), shoot NrN_r rays to the boundary of K\mathcal{K} and bisect each ray to find the outermost point that is still feasible. The convex hull of those points under-approximates the kernel.

The contribution is what runs inside the bisection. The original work solved a per-point linear feasibility program of dimension diNρd_i N_\rho. We replace it with a reachability + overlap check: at each step propagate the reachable zonotope Ωk\Omega_k forward, then test Ωk∩Kk♭≠∅\Omega_k \cap \mathcal{K}^\flat_k \ne \emptyset — where Kk♭\mathcal{K}^\flat_k is K\mathcal{K} eroded by the inter-sample drift bound — via a small LP in the zonotope coefficients αi∈[−1,1]\alpha_i \in [-1, 1]. Zonotopes are closed under affine maps and Minkowski sums in linear time, sidestepping the exponential blow-up that polytopic Minkowski sums hit in high dimension.

Why it works

Theorem — Soundness

Ωk∩Kk♭≠∅  for all  k=1,…,Nρ   ⟹   x0∈ViabTsd(K)\Omega_k \cap \mathcal{K}^\flat_k \ne \emptyset \ \text{ for all }\ k = 1, \dots, N_\rho \ \implies\ x_0 \in \text{Viab}_T^{sd}(\mathcal{K})

Proof sketch. A non-empty intersection at step kk is exactly the existence of an input uk−1∈Uu_{k-1} \in \mathcal{U} steering the system into Kk♭\mathcal{K}^\flat_k at that sampling instant. The erosion K↦K♭\mathcal{K} \mapsto \mathcal{K}^\flat is calibrated against the inter-sample drift bound on x˙\dot{x}, so a sample landing in K♭\mathcal{K}^\flat guarantees the continuous trajectory does not leave K\mathcal{K} between samples. Reordering the existential quantifiers across all NρN_\rho steps yields a single input sequence valid for the whole horizon, which is the definition of viability. ■\blacksquare

Result

On a chain of nn integrators with n=5,…,100n = 5, \dots, 100, the zonotope-based version is consistently faster than the LP-feasibility baseline. Asymptotic complexity stays in the same band — between O(n2)\mathcal{O}(n^2) and O(n3)\mathcal{O}(n^3) per direction — but the constant is meaningfully smaller. The output is a guaranteed under-approximation of ViabTsd(K)\text{Viab}_T^{sd}(\mathcal{K}), so it is safe to use as a safety filter.

Context

From my MSc thesis — published at ECE 2019 — and the foundation for Viability Kernels for Non-Linear Systems.

Visit project →
Meta
TopicsMathematics
RelatedViability Kernels for Non-Linear Systems
Referenced byViability Kernels for Non-Linear Systems