\NeedsTeXFormat{LaTeX2e}
\documentclass[pdf,distiller,nototal,nuancegris]{prosper}
\usepackage{graphicx,amsmath,calc,psfrag}

\newtheorem{thm}{Theorem}[section]
\newtheorem{alg}[thm]{Algorithm}
\newcommand\algbox[2]{\hspace*{#1}\parbox[]{\columnwidth-#1}{#2}\vspace{0.06in}}

\newcommand\psize{\ptsize{12}}

%\ptsize{12}

\title{Stochastic Reachability and Aircraft Collision Avoidance}
%\subtitle{Prosper in action}
\author{Oliver Watkins and John Lygeros}
\email{ojw26@cam.ac.uk}
\institution{University of Cambridge, UK}

%%% Things which go on all slides:
%% the caption. The default is the \title argument.
\slideCaption{CDCO3}
%% A logo. x and y coordinates measured in inches with
%% zero point at the lower left corner.
%\Logo{\includegraphics[height=1cm]{mpa_logo}}

\begin{document}
\maketitle

\ptsize{12}

\begin{slide}{Presentation}
\psize
\begin{itemize}
\item Discrete time stochastic reachability.
\item Methods of solution.
\item Monte Carlo algorithm.
\item Application - Air Traffic Control.
\item Results.
\end{itemize}
\end{slide}

\begin{slide}{Stochastic Reachability}
\psize
Given a model of the form:
\begin{equation}
\label{eqn:mod}
x_{k+1} = f(x_k) + w_k,
\end{equation}
For $x_k \in \mathbb{R}^n$ and $\mathcal{T} \subseteq \mathbb{R}^n$,
find a measure of probability that $x_k \in \mathcal{T}$, for some $k$
over a horizon $[0,T]$.
\end{slide}

\begin{slide}{\vspace{-0.3in} Approaches}
\psize
\vspace{-0.3in}
\begin{itemize}
\item Approximate probability by a measure e.g.
\begin{itemize}
\item Maximum instantaneous probability $\max_{k \in
    [0,T]}\int_{\mathcal{T}} P(x_k)dx_k$
\item Assume constant uncertainty statistics while $x_k$ near $\mathcal{T}$ -
  analytical solution.
\end{itemize}
\item Approximate true conflict probability:
\begin{equation}
P_c = P\{x_k \in \mathcal{T} \text{ for some $k \in [0,T]$}\}
\end{equation}
\item Is $P_c$ more valuable than other measures?
\end{itemize}
\end{slide}

\begin{slide}{Gridding}
\psize
\begin{itemize}
\item Suitable $f(\cdot)$ and $w_k$ allow analytical expression of
  mixing kernel $K:\mathcal{P}(\mathbb{R}^n) \rightarrow \mathcal{P}(\mathbb{R}^n)$:
\begin{equation}
K(x_k,x_{k-1})= P(x_k|x_{k-1},\dots,x_0)
\end{equation}
\item Grid state space and perform analytical approximation over horizon.
\item Good results - but unreasonably complex for satisfactory results.
\end{itemize}
\end{slide}

\begin{slide}{\vspace{-0.2in} MC Algorithm}
\psize
\vspace{-0.1in}
\begin{itemize}
\item Simulate $N$ particles according to system dynamics.
\item Set indicator function $I^{(i)} = 0$ for $i = 1,\dots,N$. Set
  $x_0 = y_t$: most recent observation.
\item At each time step $k$:
\begin{enumerate}
\item Sample new positions from $x_k^{(i)} \sim \delta_{x_{k-1}^{(i)}}
  K(x_k,x_{k-1}^{(i)})$
\item For all $x_k^{(i)} \in \mathcal{T}$ set $I^{(i)} = 1$
\item Approximate $P_c \approx \frac{1}{N} \sum_i I^{(i)}$
\item Increment $k$ and return to 1.
\end{enumerate}
\end{itemize}
\end{slide}

\begin{slide}{Application}
\psize
\begin{itemize}
\item Conflict Probability in Air Traffic Control.
\item Evaluate criticality of airspace configurations - test aircraft pairwise.
\item Simple aircraft models fit $x^r_{k+1} = f(x^r_k) + u_k$.
\item Assess conflict detection through flight simulations.
\item Evaluate stochastic measure of `good algorithm'.
\item Assess performance vs. other criticality measures.
\end{itemize}
\end{slide}

\begin{slide}{\vspace{-0.5in} SOC curves}
\psize
\vspace{-0.3in}
\begin{itemize}
\item Performance judged by:
\begin{equation}
\min_{\bar{C}}d(\bar{C}) = \sqrt{P(FA)^2 + (1-P(SA))^2}
\end{equation}
\item Ideal performance at $P(FA) = 0$ and $P(SA) = 1$, hence
  $d(\bar{C}) = 0$.
\item Plot $P(FA)$ against $P(SA)$, for $\bar{C} \in [0,1]$.
\item Resulting plots called `System Operating Characteristic' (SOC) curves.
\end{itemize}
\end{slide}

\begin{slide}{\vspace{-0.5in} Results I}
\psize
\vspace{-0.3in}
\begin{itemize}
\item Compare with measure: $P_c= \max_{k \in
    [0,T]}\int_{\mathcal{T}} P(x_k)dx_k$
\item Already demonstrated to compare well with other algorithms.
\item Simple flight plans - intersecting straight lines. 
\begin{figure}
\begin{centering}
\psfrag{xr}{$y_1$}
\psfrag{yr}{$y_2$}
\psfrag{th}{$\theta$}
\psfrag{v1}{$v_1$}
\psfrag{v2}{$v_2$}
%\psfrag{*}{*}
\hspace{1in}
\includegraphics[width = 0.5\textwidth]{cfgeom2}
\label{fig:cfgeom2}
\end{centering}
\end{figure}
\end{itemize}
\end{slide}

\begin{slide}{\vspace{-0.5in}Results 2}
\psize
\begin{figure}[h]
\begin{centering}
\vspace{-0.5in}
\includegraphics[width = 0.7\textwidth]{G90_60_5}
\caption{SOC curve for $90^{\circ}$ crossing angle.}
\label{fig:G00_60_5}
\end{centering}
\end{figure}
\end{slide}

\begin{slide}{\vspace{-0.5in}Results 3}
\psize
\begin{figure}[h]
\begin{centering}
\vspace{-0.5in}
\includegraphics[width = 0.7\textwidth]{G00_8_5}
\caption{SOC curve for parellel flight.}
\label{fig:G90_60_5}
\end{centering}
\end{figure}
\end{slide}

\begin{slide}{Conclusions}
\psize
\begin{itemize}
\item Stochastic Reachability does not admit simple solution.
\item Other algorithms rely on analytical tractability of parts of the
  model.
\item Particle methods can offer more, and need only admit simulation.
\item Can introduce more complex underlying models when required.
\end{itemize}
\end{slide}

\end{document}