Key Sequence
Notation
New Concepts
Important Results / Claims
Questions
Interesting Factoids
reachability for non-linear systems
Standard reachability analysis for Linear Dynamical System is not great, because polytopes don’t stay polytopes when we apply non-linear operations.
The general vibe, then, is to take a non-linear thing and bound them using a polytope.
interval arithmetic
We can’t propagate polytopes though non linear systems; but we can propagate intervals.
Suppose we have an interval:
\begin{equation} [x] = \qty {x \mid x_1 \leq x \leq x_2} \end{equation}
Let’s define some operations
interval counterpart of addition
\begin{equation} [x] + [y] = \qty {x+y \mid x \in [x], y \in [y]} \end{equation}
We could actually compute the interval explicitly:
\begin{equation} [x] + [y] = [x_1 + y_1, x_2 + y_2] \end{equation}
we can just add the intervals together
interval counter part of binary operators
\begin{equation} [x] \cdot [y] = \qty {x \cdot y \mid x \in [x], y \in [y]} \end{equation}
specifically…
\begin{equation} [x] + [y] = [x_1 - y_2, x_2 - y_1] \end{equation}
\begin{equation} [x] \times [y] = [\min \qty(x_1y_1, x_1y_2, x_2y_1, x_2y_2), \max \qty(x_1y_1, x_1y_2, x_2y_1, x_2y_2)] \end{equation}
notably! this last thing is not defined if any of the intervals contains \(0\).
for monotone function f:
\begin{equation} f\qty([x]) = [f\qty(x_1), f\qty(x_2)] \end{equation}
inclusion functions
we said above the with monotone functions we can directly compute the interval \(f\qty([x])\). But, we can bound the behavior of \(f\qty([x])\) with some “inclusion function”:
\begin{equation} f\qty([x]) \subseteq [f]\qty([x]) \end{equation}
natural inclusion function
Consider:
\begin{equation} f\qty(x) = x - \sin \qty(x) \end{equation}
we can just “naively” plug in the interval:
\begin{equation} [f]\qty([x]) = [x] - \sin \qty([x]) \end{equation}
but! this yields a huge overapproximation error. This is due to the dependency effect, since \(x\) and \(\sin \qty(x)\) values are not independent!
mean value inclusion function
applying this interval \([x]\), but weirdly:
given the centerpoint \(c\) of the interval \([x]\) and any \(x \in [x]\), there exists a point \(x’ \in [x]\) such that:
\begin{equation} \frac{f\qty(x) - f\qty( c)}{x - c} = f’\qty(x’) \end{equation}
Now, algebra! We now obtain a reparameterized version of the function
\begin{equation} f\qty(x) = f\qty( c) + f’\qty(x’) \qty(x-c) \end{equation}
applying the natural inclusion function (remember \(x’ \in [x]\), so)
\begin{equation} [f]\qty([x]) = f\qty( c) + [f’] \qty([x]) \qty( [x] - c) \end{equation}
with \(c = \frac{x_{\max } + x_{\min }}{2}\).
where we take the natural inclusion function for \(f’\qty(x)\).
mean value theorem
For \(f\qty(x)\) that is continuous and differentiable on the interval \([x]\), there exists a point \(x’ \in [x]\) such that:
\begin{equation} \frac{f\qty(x_{\max}) - f\qty(x_{\min})}{x_{\max } - x_{\min }} = f’\qty(x’) \end{equation}
Taylor inclusion function
Notice the above mean value theorem gives us a first-order Taylor approximation. We can just add more terms where we explicitly compute \(f’\) up to \(pn\).
