Suggest edit — SU-CS238V FEB112025

Title

Name

Note

---
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}