SU-CS238V FEB112025 — Jemoka Knowledge Base

Key Sequence Notation Linear Dynamical System set operations New Concepts reachability analysis Set Propagation Techniques Important Results / Claims Questions Set Propagation Techniques Now, how exactly do we compute the reachable set. …for Linear Dynamical Systems Let’s consider writing s’ as a function of s, x. For a linear system, we have:

\begin{equation} s’ = \left(T_{s}+T_{a}\Pi_{o}O_{s}\right)s + T_{a}\Pi_{o}x_{o} + T_{a}x_{a} + x_{s} \end{equation}

our goal is to then write this for sets of initial s. Write this in terms of Set Propagation Techniques:

\begin{equation} \mathcal{S}’ = \left(T_{s} + T_{a}\Pi_{o}O_{s}\right) \mathcal{S} \oplus T_{a}\Pi_{o}\mathcal{X}_{o} \oplus T_{a}\mathcal{X}_{a} \oplus \mathcal{X}_{s} \end{equation}

We can then build out the reachable set over time by continuously applying this expression, namely:

\begin{equation} \mathcal{R}_{d} = \left(T_{s} + T_{a}\Pi_{o}O_{s}\right) \mathcal{S}_{d-1} \oplus T_{a}\Pi_{o}\mathcal{X}_{o} \oplus T_{a}\mathcal{X}_{a} \oplus \mathcal{X}_{s} \end{equation}

Now, to bound our reachable set for horizon up to t, we can write:

\begin{equation} \mathcal{R}_{1:t} = \bigcup_{d=1}^{t} \mathcal{R}_{d} \end{equation}

Now, if you want to bound your reachable set up to infinite horizon, we have to show for SOME d we have:

\begin{equation} \mathcal{R}_{d} \subseteq \mathcal{R}_{d-1} \end{equation}

(why some but not all? because once this happens once, you are forever trapped into the set \mathcal{R}_{d-1} at least (since the next one is smaller) and so will be bounded forever.) set representations finite representations: specify all points in the set without enumerating all systems convex tend to be nice: a set \mathcal{P} is convex if \alpha p + \left(1-\alpha\right) p \in \mathcal{P}, for all p,q \in \mathcal{P} and \alpha \in [0,1] polytope We are most interested in polytope: a bounded intersection of half-spaces—a series of inequality a^{T}x \leq b. Two types of polytopes: H polytopes a set of half-spaces: Ax \leq b for matrices A, b, which are a series of things that are specified. V polytope the convex hull of a set of vertices: \text{conv}\left(\mathcal{V}\right) — i.e. give a set of vertices at the edges of the hull. set operations for \mathcal{V} polytopes:

\begin{equation} A\mathcal{P} = \text{conv}\left(A v \midv \in\mathcal{V}\right) \end{equation}

\begin{equation} \mathcal{P} \oplus \mathcal{Q} = \text{conv}\left(\left\{v_1 + v_2 \mid v_1 \in \mathcal{V}_{p}, v_2 \in \mathcal{V}_{q}\right\}\right) \end{equation}

^ computing this convex hull is wayyyy to expensive as verticies scale; we can solve this with one of two ways. use a zonotope instead overapproximate: “bound it with a box”—which do not loose our safety guarantees if it does not intersect with the avoid set; if it does intersect with the avoid set, we can’t make any conclusions. see overapproximation zonotope A zonotope is a symmetric polytope. A zonotope is a subset of polytope that’s easy to parametrize. a set of vector generators g a center point c for any ordering of g, g_{j}, we maintain a set of active verticies \left\{c\right\} in the beginning and concatenate one of the remaining gjs into each vertex and also in the negative direction. And then, get a convex hull. that is:

\begin{equation} \mathcal{Z} = \left\{c + \sum_{i=1}^{m} \alpha_{i} g_{i} \mid \alpha_{i} \in \left\{-1, 1\right\}\right\} \end{equation}

set operations for zonotope

\begin{equation} A \mathcal{L} = \left(Ac, \langle Ag_{i_1:m} \rangle\right) \end{equation}

\begin{equation} \mathcal{L} \oplus \mathcal{L} = \left(c+c’, \langle g_{1:m}, g’_{1:m} \rangle\right) \end{equation}