Key Sequence

Notation

New Concepts

• Markov Chain Monte-Carlo

Important Results / Claims

Questions

Interesting Factoids

Key Sequence

Notation

New Concepts

• Importance Sampling
• adaptive importance sampling
• finding a good proposal distribution
  • population monte-carlo
  • sequential monte-carlo

Important Results / Claims

• adaptive cross entropy method with adaptive importance sampling

Questions

Interesting Factoids

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’ = \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:

Key Sequence

Notation

New Concepts

Important Results / Claims

• overapproximate
• inclusion functions

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}

Key Sequence

Notation

New Concepts

Important Results / Claims

• Taylor Models
• Concrete Reachability

Questions

Interesting Factoids

Partitioning

As a way to prevent wrapping effect, you can partition your initial set into smaller chunks and propagate them separately, and then union them together.

Discrete Reachability

Remember: we can represent discrete systems using directed graphs.

reachable sets for discrete systems

Breadth-first search to get the reachable sets. We can terminate the BFS by checking if one subset of points is contained within another: