\documentclass[10pt,xcolor=pdftex,dvipsnames]{beamer}

\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage[italian]{babel}
\usepackage{palatino}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{marvosym}
\usepackage{booktabs}
\graphicspath{graphs/}

\usepackage{pgf,pgfsys,pgffor}
\usepackage{tikz}
\usetikzlibrary{arrows,decorations.pathmorphing,backgrounds,fit,mindmap,calc,through,scopes,fadings,positioning,automata,calendar,shapes,er,matrix,folding,patterns,petri,plothandlers,plotmarks,shadows,topaths,through,trees}

\usepackage{ccaption}

\renewcommand{\figurename}{Figure:}

\usepackage{multirow}

\newcommand{\numberset}{\mathbb}
\newcommand{\R}{\numberset{R}}
\newcommand{\U}{\numberset{U}}

\usetheme{Darmstadt}
\setbeamertemplate{navigation symbols}{}

\title{Simulation and Multitarget Tracking}
\subtitle{Corso di Progettazione di Sitemi di Controllo --- A.A. 2009/2010}
\author{
  Edoardo D'Elia \and
  Carlo Tavian \and
  Alberto Zugno
}
\institute[PaduaUniversity]
{
  Department of Information Engineering

  University of Padova
}
\logo{\includegraphics[width=1.25cm]{involucro/DEIlogoFULL}}
\date{February 17, 2010}

\AtBeginSection[]
{
  \begin{frame}<beamer>{Outline}
    \small \tableofcontents[currentsection]
  \end{frame}
}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Outline}
  \small \tableofcontents
\end{frame}

\section[Intro]{Introduction}

\begin{frame}{Applications}

  \begin{block}{Civilian Area}
    \begin{itemize}
      \item \alert{Surveillance}-related  systems
      \item Computer Vision (\textcolor{green!50!black}{motion capture})
      \item Network and computer security (process query systems)
      \item Sensor networks (coordination of multiple agents)
    \end{itemize}
  \end{block}

  \begin{block}{Military Area}
    \begin{itemize}
      \item Ballistic missile defense (reentry vehicles)
      \item Air defense (enemy aircraft)
      \item Ocean surveillance (surface ships and submarines)
      \item Battlefield surveillance (ground vehicles and military units)
    \end{itemize}
  \end{block}
  
\end{frame}

\subsection{Goals and Beyond}

\begin{frame}{Multi-Target Tracking}
  
  \begin{block}{Purpose}
    \begin{itemize}
      \item \textcolor{green!50!black}{Accurate} data association
      \item \textcolor{green!50!black}{Real-time} computation
      \item \textcolor{green!50!black}{Robust} to false alarms and corrupted or missing reports
    \end{itemize}
  \end{block}

  \begin{block}{Possible Improvements}
    \alert{Recognize and take into account shape constraints}
  \end{block}
  
\end{frame}

\begin{frame}{Simulator}

  \begin{block}{Purpose}
    \begin{itemize}
      \item Generate \textcolor{green!50!black}{synthetic data}
      \item Introduce various types of \textcolor{green!50!black}{distortion}
    \end{itemize}
  \end{block}

  \begin{block}{Possible Improvements}
    \alert{Implement an hidden point feature}
  \end{block}

\end{frame}

\subsection{Results}

\begin{frame}{Implementations}

  \begin{block}{Simulator}
    A routine based on pin-hole model camera
  \end{block}

  \begin{block}{Multiple-Target Tracking}
    \begin{itemize}
      \item MCMCDA algorithm
      \item SMP algorithm
    \end{itemize}
  \end{block}
  
\end{frame}

\section[State of the Art]{Literature and State of the Art}

\subsection{Bayesian Approach}

\begin{frame}{Joint Probabilistic Data Association}
  
  PDA extension to a \alert{known} number of targets in clutter.

  The derivation of joints events is done using Bayes' rule

  \begin{equation*}
    P[\boldsymbol{\theta}(k)|Y^k] = P[\boldsymbol{\theta}(k)|Y(k),Y^{k-1}] = \alert{\frac{1}{c}}P[Y(k)|\boldsymbol{\theta}(k),Y^{k-1}]P[\boldsymbol{\theta}(k)]
  \end{equation*}

  \begin{block}{Advantages and Drawbacks}
    \begin{description}
      \item[\textcolor{green!50!black}{\textsc{pros}}] single-scan, optimal solution
      \item[\alert{\textsc{cons}}] known number of targets, marginal association by summing over all the joint events
    \end{description}
  \end{block}
  
\end{frame}

\begin{frame}{Track-Splitting Filter}

  \begin{block}{Algorithm Procedure}
    \begin{enumerate}
      \item Measurement Validation
      \item Track Splitting
      \item Kalman Filtering
      \item Hypothesis Testing
    \end{enumerate}
  \end{block}

  \begin{block}{The Hypothesis Testing}
    The modified log-likelihood can be computed recursively
    \begin{equation*}
      \lambda(k) = \lambda(k-1) + e^T(k)S^{-1}(k)e(k),
    \end{equation*}
    and is a \alert{chi-square} with $kn_y$ degree of freedom.

    Thus the statistical hypothesis test is
    \begin{equation*}
      P[\chi_{kn_y}^2 > \delta] = \alpha \quad \text{(true track rejection probability)}
    \end{equation*}
  \end{block}

\end{frame}

\begin{frame}{Multi Hypothesis Tracker}

  \begin{block}{Features}
    \begin{itemize}
      \item Multiple-scan correlation
      \item Clustering
      \item Recursiveness
    \end{itemize}
  \end{block}

  \begin{block}{Algorithm Subroutines}
    \begin{description}
      \item[\textsc{cluster}] Form new clusters, identify which targets and measurements are associated with each cluster
      \item[\textsc{hypgen}] Form new set of hypothesis, calculate their probability and perform a target measurement update for each hypothesis of each cluster
      \item[\textsc{reduce}] Reduce number of hypothesis by elimination or combination
    \end{description}
  \end{block}

\end{frame}

\subsection{non-Bayesian Approach}

\begin{frame}{Linear Assignment Problem}

  \begin{columns}[t]

    \column{.45\textwidth}
    Assignment problems deal with the question how to assign $n$ items (e.g. jobs) to $n$ machines (or workers) in the best possible way.
    
    The problem may then be reformulated as an \alert{integer programming} problem or, more precisely, as a multidimensional assignment problem.
    
    \textsc{the goal} is to make an \alert{hard measurement-to-track} \textsc{association}.
    
    \column{.45\textwidth}
    \begin{exampleblock}{Representation}
      \begin{figure}
        \centering
        \input{graphs/bipartite.tex}
      \end{figure}
    \end{exampleblock}

  \end{columns}

\end{frame}

\begin{frame}{Monte Carlo Markov Chain Data Association}

  \begin{figure}
    \centering
    \input{graphs/chain.tex}
  \end{figure}

  \begin{columns}[t]
    
    \column{.45\textwidth}
    \begin{block}{Single Scan}
      \begin{itemize}
        \item JPDA \textcolor{green!50!black}{$\epsilon$-good} approximation
        \item polynomial time execution
      \end{itemize}
    \end{block}
    
    \column{.45\textwidth}
    \begin{block}{Multi Scan}
      \begin{itemize}
        \item Handle \alert{unknown} and \alert{changing} over the time \#\,targets
        \item On-line version for ``real-time'' processing
      \end{itemize}
    \end{block}
  \end{columns}

\end{frame}

\begin{frame}{Stable Marriage Problem}

  \begin{columns}[t]
    
    \column{.45\textwidth}
    \begin{block}{The Problem}
      \begin{itemize}
        \item 1 matchmaker
        \item 100 female clients
        \item 100 male clients
        \item 200 preference lists
        \item<alert@1-> Arrange 100 happy marriages
      \end{itemize}
    \end{block}

    \column{.45\textwidth}
    \begin{exampleblock}{Pair Satisfaction}
      When given two married pairs, (\Male,~\FEMALE) and (\MaleMale,~\Female), if man \Male\ prefers another woman \Female\ more than his current wife \FEMALE\ and woman \Female\ prefers \Male\ more than her current husband \MaleMale, then (\Male,~\FEMALE) is called a dissatisfied pair
    \end{exampleblock}
    
  \end{columns}

  \bigskip

  The marriage is \alert{stable} if there are \alert{no dissatisfied} pairs

  \textsc{the goal} is to ``marry'' targets with measurement in a \textsc{stable way}
  
\end{frame}

\section[Simulator]{Camera Simulator}

\subsection{Camera Model}

\begin{frame}{Pin-hole model}

  \begin{figure}
    \centering
    \includegraphics[width=0.75\textwidth]{graphs/pinhole2d.pdf}
  \end{figure}

  \medskip

  Projection equations:

  \medskip

  $$x=\frac{fX_c}{Zc};\:y=\frac{fY_c}{Zc}$$

\end{frame}

\begin{frame}{Pin-hole model}
  \begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{graphs/camera2.pdf}
  \end{figure}

  \begin{multline*}
    \begin{bmatrix}
        su_{1} & su_{2} & \cdots & su_{n}\\
        sv_{1} & sv_{2} & \cdots & sv_{n}\\
        s & s & \cdots & s
    \end{bmatrix}
    = K \cdot F \cdot RT \cdot P_{3dpts} =
    \begin{bmatrix}
        k_{u} & 0 & u_{0}\\
        0 & k_{v} & v_{0}\\
        0 & 0 & 1
    \end{bmatrix} \cdot \\
    \cdot
    \begin{bmatrix}
        f & 0 & 0 & 0\\
        0 & f & 0 & 0\\
        0 & 0 & 1 & 0
    \end{bmatrix}
    \begin{bmatrix}
        r_{11} & r_{12} & r_{13} & T_{x}\\
        r_{21} & r_{22} & r_{23} & T_{y}\\
        r_{31} & r_{32} & r_{33} & T_{z}\\
        0 & 0 & 0 & 1
    \end{bmatrix}
    \begin{bmatrix}
        x_{1} & x_{2} & \cdots & x_{n}\\
        y_{1} & y_{2} & \cdots & y_{n}\\
        z_{1} & z_{2} & \cdots & z_{n}\\
        1 & 1 & \cdots & 1
    \end{bmatrix}
  \end{multline*}
\end{frame}

\begin{frame}{Distortions}
  \begin{columns}[t]
    
    \column{.45\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=0.75\textwidth]{graphs/skew.pdf}
    \end{figure}
    \begin{block}{Skew}
      $$K'=\left[\begin{array}{ccc}
          k_{u} & s_w & u_{0}\\
          0 & k_{v} & v_{0}\\
          0 & 0 & 1\end{array}\right]$$
    \end{block}
    
    \column{.45\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=0.75\textwidth]{graphs/radial.pdf}
    \end{figure}
    \begin{block}{Radial distortion}
      $$\begin{array}{c}
        x=x_{d}(1+a_{1}r^{2}+a_{2}r^{4})\\
        y=y_{d}(1+a_{1}r^{2}+a_{2}r^{4})\end{array}$$
    \end{block}
  \end{columns}
\end{frame}

\subsection{Possible Improvements}

\begin{frame}{Hidden Points}
  \begin{figure}[tbp]
    \centering
    \includegraphics[width=0.75\textwidth]{graphs/schema_zbuf.pdf}
  \end{figure}
\end{frame}

\section{Markov Chain Monte Carlo Data Association}

\subsection{Model Formulation}

\begin{frame}{Target Trajectories}

  We suppose exist an \alert{hidden Markov chain} $\mathcal{M}$ \emph{suitable for modelling track labelling}.

  \begin{columns}

    \column{.45\textwidth}
    \begin{block}{Model}
      \begin{equation*}
        \left\{ \begin{array}{l}
          x_{t+1}^{q}=F^{k}\left(x_{t}^{q}\right)+w_{t}^{q}\\
          y_{t}^{j} = \left\{ \begin{array}{l}
            H^{j}\left(x_{t}^{k}\right)+v_{t}^{j}\\
            u_{t}\\
          \end{array} \right.\\
        \end{array} \right.
      \end{equation*}
    \end{block}

    \column{.45\textwidth}
    \begin{exampleblock}{Parameters}
      \begin{itemize}
        \item $p_{d}$, target detection probability
        \item $p_{z}$, target disappearance probability
        \item $\lambda_b$ target birth rate
        \item $\lambda_f$ false alarms rate
      \end{itemize}
    \end{exampleblock}
  \end{columns}
\end{frame}

\subsection{Algorithm}

\begin{frame}{Approach} 
  \begin{itemize}
  \item \alert{sliding window} of $T$ frames, up to current time $H$
  \item $Y_{W}=\left\{Y_{t} \quad | \quad t=H-T+1,\dots,H\right\}$, \alert{3D noisy data}
  \end{itemize}
  
  \begin{center}
    {\large$\Downarrow$}
  \end{center}
  
  \begin{block}{Labelling Structure}
    \begin{itemize}
    \item $\tau_{k}=\tau_{\left[H-T,\dots,H\right]_{k}}=\textrm{Alg}(Y_{W})$, target \alert{tracks}
    \item $\omega=\left\{\tau_{0},\tau_{1},\dots,\tau_{K}\right\}$, \alert{labelling \& track history} in the sliding window
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Online Multi-Scan MCMCDA}
  \begin{center}
    \begin{tikzpicture}
      \node[scale=0.7]{ 
        \begin{tikzpicture}[auto, >=stealth', thick, draw=black!80]
          \tikzstyle{point} = [coordinate]
          \tikzstyle{decision} = [shape aspect=3,diamond, draw=black!80, top color=white, bottom color=PineGreen!40, text badly centered, inner sep=1pt]
          \tikzstyle{expr} = [rectangle, draw=black!80, top color=white, bottom color=RoyalBlue!70, text centered, rounded corners, minimum height=2em]
          \tikzstyle{expr2} = [rectangle, draw=black!80, top color=white, bottom color=Goldenrod!70, text centered, rounded corners, minimum height=2em]
          \tikzstyle{line} = [draw, thick, shorten >=2pt]
          \tikzstyle{cloud} = [rectangle,draw=black!80, top color=white,bottom color=Red!70, text centered, rounded corners, minimum height=3em]
          \tikzstyle{node1} = [thick, draw=black!80, top color=white, bottom color=black!20, circle, inner sep=0.5mm]
          \matrix[column sep=2.5em, row sep=1em]
                 {
                   % row 1
& & & \node[point](p4){}; & \node[point](pfp2){};  & \node[point](p3){}; & \\
                   % row 2
                   & \node[point](pi){}; & & \node [expr] (proposal) {$\omega' = \textrm{Proposal Distribution}(\hat{\omega},Y)$};  & & &\\
                   
                   & & & \node [expr2] (u) {$u\sim \textrm{Unif}\left[0,1\right]$};  & & &\\
                   % row 3
                   \node [cloud] (y) {$Y_{W}$}; & \node [expr2] (omeginit) {$\hat{\omega}:=\omega$};  & \node[point](pnacc1){}; & \node [decision] (acceptance) {$u<\textrm{Acceptance}(\omega,\omega')$}; & & &\\
                   % row 4
                   \node [cloud] (omega) {$\omega$};  &  & & \node [expr2] (omegaacc) {$\omega:=\omega'$}; & & \node[point](pp2){}; & \node [cloud] (omegafinal) {$\hat{\omega}$};  \\
                   % row 5
                   & & \node[point](pnacc2){}; &\node [decision] (prob) { $P[\omega | Y ] > P[\hat{\omega} | Y ]$}; &  \node[point](pfp1){}; & & \\
                   % row 6
                   & & & \node [expr2] (omegaprob) {$\hat{\omega}:=\omega$}; & & & \\
                   % row 7
                   & & & \node[point](p1){}; & & \node[point](p2){}; & \\
                 };
                 \draw[->,blue!80,dashed]  (y) |- (proposal);
                 \draw[->,blue!80,dashed]  (omega) -| (omeginit);
                 \draw[blue!80,dashed]  (omeginit) -- (pi);
                 \draw[->]  (acceptance) -- node [pos=.3,swap] {true}  (omegaacc);
                 \draw[->]  (omegaacc) --  (prob);
                 \draw[->]  (prob) -- node [pos=.3] {true}  (omegaprob);
                 \draw[->] (omegaprob) -- (p1)--(p2) -- node [pos=.7,swap] {$N_{mc}$ times} (p3)--(p4) -- (proposal);   
                 \draw[->]  (proposal)--(u);
                 \draw[->]  (u)--(acceptance);
                 \draw[->,blue!80,dashed]  (pp2)--(omegafinal);
                 \draw[->]  (acceptance) --(pnacc1) -- node [pos=.5] {false} (pnacc2)-- (prob);
                 \draw (prob) --(pfp1) -- node [pos=.5] {false} (pfp2);
      \end{tikzpicture} };
    \end{tikzpicture}
  \end{center}
\end{frame}

\subsection*{Proposal Distribution}
\begin{frame}{Move selection}
  \begin{block}{Constructing a suitable Markov chain}
    \begin{center}
      A \alert{random move $m$} is chosen,\\
      accordingly to the probability distribution \alert{$\xi_{K,H}(m)$},\\
      for $N_{mc}$ times every frame.
    \end{center}
  \end{block}
\end{frame}

\begin{frame}{1) Birth Move}
\end{frame}

\begin{frame}{2) Death Move}
\end{frame}

\begin{frame}{3) Split Move}
\end{frame}

\begin{frame}{4) Merge Move}
\end{frame}


\begin{frame}{5) Extension Move}
\end{frame}

\begin{frame}{6) Reduction Move}
\end{frame}

\begin{frame}{7) Track Update Move}
\end{frame}

\begin{frame}{8) Track Switch Move}
\end{frame}

\subsection*{$\omega'$ Validation}
\begin{frame}
  \begin{block}{Acceptance Probability}
    \begin{equation*}
      A(\omega,\omega')=min\left(1, \frac{\pi(\omega')q(\omega',\omega)}{\pi(\omega)q(\omega,\omega')}\right)
    \end{equation*}
  \end{block}
  \bigskip
  \begin{itemize}
  \item $\pi(\omega_{a}):=P(\omega_{a}|Y_{W})$
  \item $q(\omega_{a},\omega_{b}):=\xi_{K,H}(m_{\omega_{a}})$
  \end{itemize}
\end{frame}

\begin{frame}
  \begin{block}{\emph{A posteriori} Probability}
    \begin{align*}
      P(\omega|Y_{W}) &= \frac{1}{Z_0}\prod_{\tau\in\omega\setminus\{\tau_{0}\}}\prod_{i=2}^{|\tau|}\mathcal{N}(\tau(t_{i});\hat{y}_{t_{i}}(\tau),B_{t_{i}})\cdot \\
      & \cdot \prod_{t=1}^{T}p_{z}^{z_t}(1-p_z)^{m_{t-1}z_t}\cdot P_d^{d_t}(1-P_d)^{u_t}\lambda_b^{a_t}\lambda_f^{f_t}
    \end{align*}
  \end{block}

  \begin{itemize}
    \item $m_t$ target at time $t$
    \item $a_t$ new targets
    \item $z_t$ terminated  targets
    \item $d_t$ detected targets 
    \item $u_t$ undetected targets
    \item  $f_t$ false alarms
    \item $d_t$ measurements
    \item $z_t$ missing relabelled measurements
  \end{itemize}
  
\end{frame}

\subsection{Possible Improvements}

\begin{frame}{Shaping $\xi_{K,H}(m)$}
  \begin{equation*}
    \xi_{K,H}(m) =\left\{ \begin{array}{lcl}
      0.033 & m=1 & P\left[\textrm{birth}\right]=1/30\\
      0.066 & m=2 & P\left[\textrm{death}\right]=1/30\\   
      0.133 & m=3 & P\left[\textrm{split}\right]=2/30\\
      0.2 & m=4 & P\left[\textrm{merge}\right]=2/30\\
      0.5 & m=5 & \alert{P\left[\textrm{extension}\right]=9/30}\\
      0.666 & m=6 & P\left[\textrm{reduction}\right]=5/30\\
      0.833  & m=7 & P\left[\textrm{track switch}\right]=5/30\\
      1 & m=8 & P\left[\textrm{track update}\right]=5/30\\
    \end{array} \right.
  \end{equation*}
\end{frame}

\begin{frame}{Two-by-Two Track Distance Bond Pruning}
\end{frame}

\begin{frame}{Volume or Distance Clusters Splitting up}
  \begin{figure}
    \centering
    \includegraphics[width=.9\textwidth]{graphs/cluster_splitting.pdf}
  \end{figure}
\end{frame}

\subsection{Simulation Results}

\begin{frame}{Moving cube}
\end{frame}

\begin{frame}{Moving cube}
\end{frame}

\begin{frame}{Moving cube, vertices  trajectories}
\end{frame}

\begin{frame}{$\textrm{\emph{Proposal Distribution}}(\omega,Y)$ with perfect data}
\end{frame}

\begin{frame}{$\textrm{\emph{Proposal Distribution}}(\hat{\omega},Y)$  with perfect data}
\end{frame}

\begin{frame}{$N_{mc}=30$ with noisy data}
\end{frame}

\begin{frame}{$N_{mc}=80$ with noisy data}
\end{frame}

\begin{frame}{$N_{mc}=1000$ with noisy data}
\end{frame}

\begin{frame}{}
  \begin{table}
    \centering
    \begin{tabular}{ccc}
      \toprule
      \multicolumn{3}{c}{Simulation results} \\
      \midrule
      \multirow{3}{*}{$N_{mc}=30$} & wrong associations & $\sim36\%$ \\
      & generated tracks & $12$ \\
      & missing labelled markers & $\sim10\%$ \\
      & runtime & 40.70 minutes \\ \hline
      \multirow{3}{*}{$N_{mc}=80$} & wrong associations & $\sim12\%$ \\
      & generated tracks & $9$ \\
      & missing labelled markers & $\sim6\%$ \\
      & runtime & 102.30 minutes \\
      \midrule
      \multirow{3}{*}{$N_{mc}=1000$} & wrong associations & $\sim0.1\%$ \\
      & generated tracks & $8$ \\
      & missing labelled markers & $\sim0.1\%$ \\ 
      & runtime & 364.75 minutes \\
      \bottomrule
    \end{tabular}
  \end{table}
\end{frame}

\section{Stable Marriage Problem}

\subsection{Definition \& Algorithm}

\begin{frame}{Definition}
  \emph{The Stable Marriage Problem:}
  \begin{itemize}
  \item We have N single men and an equal number of single women.
  \item Each man and each woman want to get marry, so express their own list of preferences.
  \item Our goal is to arrange \alert{N stable marriages}
  \end{itemize}
  \begin{figure}[tbp]
    \centering
    \includegraphics[width=0.7\textwidth]{graphs/marriage_intro.pdf}
  \end{figure}
\end{frame}

\begin{frame}{Definition}

  \begin{columns}[t]
    
    \column{.6\textwidth}
    \begin{itemize}
      \item A marriage is a match between one element of $M$ and one of $F$ (example: $A-b$).
      \item A pair $X-y$ is a \alert{dissatisfied} one if in the solution $S$ exists two marriages, $X-z$ and $W-y$ such that $X$ prefer $y$ more than is current partner $z$ and woman $y$ prefers $X$ more than her current partner $W$.
      \item A set of marriage $M$ is called \alert{stable} if there are no dissatisfied pairs.
    \end{itemize}

    \column{.4\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=\textwidth]{graphs/marriage.pdf}
    \end{figure}
  \end{columns}
\end{frame}

\begin{frame}{Algorithm}
\end{frame}

\begin{frame}{Analysis}

  \begin{itemize}
    \item Worst case complexity: $O(n^2)$
    \item Average case complexity: $O(n\cdot log(n))$
    \item Male-optimal
  \end{itemize}

  \begin{exampleblock}{Optimality Criterion}
    A marriage between a man A and a woman B is \alert{feasible} if there exists a stable pairing in which A and B are married.
    A pairing is \alert{male-optimal} if every man is married with his highest ranked feasible partner.
  \end{exampleblock}
\end{frame}

\subsection{Application to Data Association}

\begin{frame}{Data Association}
  The SMP basically provides a way to \alert{pair the elements of two sets}.
  
  We adapted it to \alert{associate measurements to markers}.
  
  \begin{figure}[tbp]
    \centering
    \includegraphics[width=0.8\textwidth]{graphs/SMPDA.pdf}
  \end{figure}

\end{frame}

\begin{frame}{Preferences Criterion}
  To use SMP we have to define how the men and women \alert{rank} their partners:
  \begin{figure}[tbp]
    \centering
    \includegraphics[width=1\textwidth]{graphs/criteri.pdf}
  \end{figure}
  For males (markers) preferences list we evaluate the \alert{normal distribution} $\mathcal{N}(y_i;\hat{y}_{t},\Sigma_{t})$, for females (measurements)
  preferences list we evaluate the \alert{distance} from each prediction.
\end{frame}

\subsection{Simulation Results}

\begin{frame}{Simulation Results}
  Three tests:
  \begin{itemize}
    \item 8 points on a translating and rotating cube
    \item 16 points on two cubes crossing each other
    \item Random Walk
  \end{itemize}
  In the first two case the reconstruction is \alert{correct}.

  In third case, designed specifically to put in trouble our algorithm:

  \begin{table}
    \centering
    \begin{tabular}{cc}
      \toprule
      wrong associations & percentage \\
      \midrule
      0 (all correct)    & $\sim82\%$ \\
      2 		 & $\sim11\%$ \\
      3 		 & $\sim2.5\%$ \\
      4 		 & $\sim2.5\%$ \\
      5 		 & $\sim0.5\%$ \\
      6 		 & $\sim0.5\%$ \\
      7 		 & $\sim0.5\%$ \\
      8 		 & $\sim0.5\%$ \\
      \bottomrule
    \end{tabular}
  \end{table}
\end{frame}

\begin{frame}{First Simulation}
  \begin{columns}[t]
    
    \column{.7\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=0.95\textwidth]{graphs/SMP_simulazione1.pdf}
    \end{figure}
    
    \column{.3\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=1\textwidth]{graphs/MCMCDAcube.pdf}
    \end{figure}
  \end{columns}
  
\end{frame}


\begin{frame}{Second Simulation}
  \begin{columns}[t]
    
    \column{.7\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=0.95\textwidth]{graphs/SMP_simulazione2.pdf}
    \end{figure}
    
    \column{.3\textwidth}
    \begin{figure}[tbp]
      \centering
      \includegraphics[width=1\textwidth]{graphs/percorso_cubo2.pdf}
    \end{figure}

  \end{columns}

\end{frame}

\begin{frame}{Third Simulation}
  \begin{figure}[tbp]
    \centering
    \includegraphics[width=0.8\textwidth]{graphs/SMP_simulazione3_RW.pdf}
  \end{figure}
\end{frame}

\subsection{Possible Improvements}

\begin{frame}{Possible Improvements}
  \begin{block}{Variable number of targets}
    \begin{itemize}
      \item decreasing measurements: factitious women
      \item increasing measurements: start new Kalman filter
    \end{itemize}
  \end{block}
  \begin{block}{False alarms / undetect measurements}
    Hospitals Problem: more than one patient (female) associated to one hospital (male)
  \end{block}
  \begin{block}{Sliding window}
    Take into consideration the last $n$ measurements to decide the preferences list
  \end{block}
\end{frame}

\section{Summary}

\begin{frame}{Conclusions}

  \begin{columns}

    \column{.45\textwidth}
    \begin{block}{MCMCDA}
      \begin{itemize}
        \item \textcolor{green!50!black}{Highly accurate}
        \item \textcolor{green!50!black}{Robust to missing and false reports}
        \item \alert{Very slow}
      \end{itemize}
    \end{block}

    \column{.45\textwidth}
    \begin{block}{SMP}
      \begin{itemize}
        \item \textcolor{green!50!black}{Highly accurate}
        \item \textcolor{green!50!black}{Real-time}
        \item \alert{Can't handle false alarms and undetections} (at the moment...)
      \end{itemize}
    \end{block}

  \end{columns}

\end{frame}

\appendix

\section*{Appendix}

\begin{frame}{Correctness}
  \begin{itemize}
    \item If there is a single man, there is a single woman
    \item If a man proposal is refused, he proposes to the next woman on his list until the last woman
    \item In a man list there are all the women
  \end{itemize}
  Therefore, all women receive \alert{at least one proposal}
  \begin{itemize}
    \item A woman always accept her first proposal since she is unmarried
  \end{itemize}
  Therefore, \alert{all women get married}.
\end{frame}

\begin{frame}{Complexity}
  \begin{itemize}
    \item Every time a man makes a proposal to a woman, she is removed from his list;
    \item There are $N$ men and $N$ woman
  \end{itemize}
  Therefore, the number of proposals \alert{is less then $N^2$}.
\end{frame}

\begin{frame}{Stability}
  Suppose there is a dissatisfied pair $X-b$, where in solution $S$ there are the marriages $X-a$ and $Y-b$.	 
  \begin{enumerate}
    \item $X$ prefers $b$ over $a\Longrightarrow$ $X$ have proposed to $b$ before $a$
    \item Since in $S$ woman $b$ is married with $Y$:
      \begin{itemize}
        \item either $b$ \alert{rejected} $X$
        \item or accepted but \alert{dropped} him for a better man $Y$
      \end{itemize}
  \end{enumerate}
  Therefore $b$ prefers $Y$ to $X$ contradicting the hypothesis that $X-B$ is a dissatisfied pair.
\end{frame}

\begin{frame}{Optimality}
  Let $M$ be a man which is just be \alert{rejected by his optimal parter} $w$
  \begin{itemize}
    \item $w$ have rejected $M$ for $Z\Longrightarrow$ she prefers $Z$
    \item $Z$ have proposed to $w$ before $X\Longrightarrow$ her rank for $Z$ is higher or equal of $X$
    \item If $w$ is the optimal mate for $X$, there must exist a solution $S$ including the marriage $X-w$
  \end{itemize}
\end{frame}

\begin{frame}{Optimality}
  In the a solution $S$ including the marriage $X-w$:
  \begin{itemize}
    \item $w$ prefers $Z$ to $M$
    \item $Z$ prefers $w$ to his mate, since $Z$ prefers $w$ at least as much as $X$ prefers his optimal partner $w$
  \end{itemize}
  Therefore The marriage is \alert{unstable}, since $Z-w$ is a \alert{dissatisfied pair} $\Longrightarrow$ $w$ cannot be $M$'s optimal partner	 
\end{frame}

\end{document}
