Key Sequence
Notation
New Concepts
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’ = \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}’ = \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—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})\) — 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: “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 \(\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}
\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’, \langle g_{1:m}, g’_{1:m} \rangle) \end{equation}