---
title: "SU-CS238V FEB112025"
source: https://www.jemoka.com/posts/kbhsu_cs238v_feb112025/
date: 2025-02-11
---

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.
&hellip;for Linear Dynamical Systems Let&rsquo;s consider writing \(s&rsquo;\) as a function of \(s, x\). For a linear system, we have:
\begin{equation} s&rsquo; = \qty(T_{s}+T_{a}\Pi_{o}O_{s})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}&rsquo; = \qty(T_{s} + T_{a}\Pi_{o}O_{s}) \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} = \qty(T_{s} + T_{a}\Pi_{o}O_{s}) \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 + \qty(1-\alpha) 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&mdash;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}\qty(\mathcal{V})\) &mdash; 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}\qty(A v \midv \in\mathcal{V}) \end{equation}
\begin{equation} \mathcal{P} \oplus \mathcal{Q} = \text{conv}\qty(\qty{v_1 + v_2 \mid v_1 \in \mathcal{V}_{p}, v_2 \in \mathcal{V}_{q}}) \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: &ldquo;bound it with a box&rdquo;&mdash;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&rsquo;t make any conclusions. see overapproximation zonotope A zonotope is a symmetric polytope. A zonotope is a subset of polytope that&rsquo;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 \(\qty {c}\) in the beginning and concatenate one of the remaining $gj$s into each vertex and also in the negative direction. And then, get a convex hull.
that is:
\begin{equation} \mathcal{Z} = \qty {c + \sum_{i=1}^{m} \alpha_{i} g_{i} \mid \alpha_{i} \in \qty {-1, 1}} \end{equation}
set operations for zonotope
\begin{equation} A \mathcal{L} = \qty (Ac, \langle Ag_{i_1:m} \rangle) \end{equation}
\begin{equation} \mathcal{L} \oplus \mathcal{L} = \qty(c+c&rsquo;, \langle g_{1:m}, g&rsquo;_{1:m} \rangle) \end{equation}
