Projects

Viability Kernels for Non-Linear Systems

This extends Viability Kernels for Linear Systems to non-linear systems x˙(t)=f(x(t),u(t))\dot x(t) = f(x(t), u(t)). Same boundary-sampling scaffolding; what changes is how we compute the per-step reachable set when ff is not linear.

Setting

Reformulate the dynamics as a differential inclusion x˙∈F(x):={f(x,u):u∈U}\dot x \in F(x) := \{f(x, u) : u \in \mathcal{U}\}. Assuming ff is C1C^1 and convex in uu for each xx, with U\mathcal{U} non-empty, compact, and convex, the set-valued map FF has non-empty, compact, convex images and is Lipschitz. That is enough to guarantee a solution to the Cauchy problem x˙∈F(x),x(0)=x0\dot x \in F(x), x(0) = x_0, so the per-step reachable set always exists.

Approach

At each propagation step:

  1. Linearize around a point z∗=(x∗,u∗)z^* = (x^*, u^*) near the centre of the predicted reachable set, getting x˙≈Ax+Bu+L\dot x \approx Ax + Bu + \mathcal{L}, where L\mathcal{L} is the Lagrangian remainder.
  2. Bound the remainder componentwise via the Hessian over the convex hull Zˉ\bar{\mathcal{Z}} of the current and predicted reachable sets, ∣Li∣≤12 γ⊤max⁡z∈Zˉ∣Ji(z)∣ γ,|\mathcal{L}_i| \le \tfrac{1}{2}\,\gamma^\top \max_{z \in \bar{\mathcal{Z}}}|J_i(z)|\,\gamma, where γ\gamma depends on the zonotope generators and the choice of z∗z^*.
  3. Split the initial zonotope along its longest generator and recurse if the remainder exceeds a user-set tolerance Lˉ\bar{\mathcal{L}}. Otherwise propagate as in the linear case.

The constraint set is eroded by the remainder bound, so the linear-system overlap test still produces a sound under-approximation.

Why it works

The boundary-sampling scheme only yields a valid under-approximation if the kernel itself is convex — otherwise the convex hull of NrN_r feasible boundary points might leak outside it. This holds under the assumptions above:

Theorem — Convexity of the Kernel

f∈C1, f(x,⋅) convex in u, X,K,U compact convex   ⟹   ViabTsd(K) is convexf \in C^1,\ f(x,\cdot)\ \text{convex in}\ u,\ \mathcal{X},\mathcal{K},\mathcal{U}\ \text{compact convex} \ \implies\ \text{Viab}_T^{sd}(\mathcal{K})\ \text{is convex}

Proof sketch. The associated set-valued map FF inherits non-empty, compact, convex images and Lipschitz continuity from the assumptions on ff and U\mathcal{U}. The kernel can be built recursively as Kn+1=Kn∩Backρ(Kn)K_{n+1} = K_n \cap \text{Back}_\rho(K_n), where the backward reachable set is the forward reachable set of the dynamics −F-F. By Wolenski's exponential formula, that reachable set is the Kuratowski limit of (I+TN(−F))N\big(I + \tfrac{T}{N}(-F)\big)^N — a sequence of set-valued maps with convex images, since affine maps and compositions preserve convexity here. The Kuratowski limit of a nested sequence of convex sets is convex, so each KnK_n is convex, and so is ViabTsd(K)=KNρ\text{Viab}_T^{sd}(\mathcal{K}) = K_{N_\rho}. ■\blacksquare

Result

Sanity-checked on the inverted-pendulum-on-cart, where the algorithm's output sits strictly inside Saint-Pierre's grid-based kernel — as expected from the piecewise-constant input restriction. For loose tolerances on Lˉ\bar{\mathcal{L}} the per-direction cost stays sub-cubic, beating griding methods in moderate dimension; tight tolerances make splitting dominate.

Context

From my MSc thesis — published at ICINCO 2018. Builds directly on Viability Kernels for Linear Systems.

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