\documentclass[hyperref={pdfpagemode=FullScreen},10pt]{beamer}
\mode<presentation>
{
  \usetheme{CambridgeUS}
  % or ...CambridgeUS
  %\usecolortheme{beaver}

  %\setbeamercovered{transparent}

  % or whatever (possibly just delete it)
}

\definecolor{green}{rgb}{0,1,0}
\definecolor{red}{rgb}{1,0,0}
\definecolor{darkgreen}{rgb}{0, .65, 0}

\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{multimedia}
%\usepackage{subfig}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage[lined,algonl,boxed]{algorithm2e}
\usepackage[english,italian]{babel}
% or whatever
\usepackage[latin1]{inputenc}
% or whatever
\usepackage{times}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
%\usepackage[T1]{fontenc}

% Or whatever. Note that the encoding and the font should match. If T1
% does not look nice, try deleting the line with the fontenc.

\title[]% (optional, use only with long paper titles)
{Task Assignment Problem in Camera Networks}
%\subtitle
%{} % (optional)

\author[]{\large{Federico Cerruti \qquad  Mirko Fabbro \qquad  Chiara Masiero}}
% - Use the \inst{?} command only if the authors have different
%   affiliation.

\institute[Task Assignment Problem in Camera Networks]
{
  %\inst{1}%
\normalsize{Corso di laurea in Ingegneria dell'Automazione\\
Università degli Studi di Padova} \\
\vspace{.5cm}
\large{Progettazione di sistemi di controllo\\ \small{Prof. Schenato Luca}}
 }

% - Use the \inst command only if there are several affiliations.
% - Keep it simple, no one is interested in your street address.

\date % (optional)
{18 Febbraio 2010}

\subject{}
% This is only inserted into the PDF information catalog. Can be left
% out.
\pgfdeclareimage[height=1.5cm]{university-logo}{fig/logoUnipd}
\pgfdeclareimage[height=1.5cm]{dei-logo}{fig/dei}
%\logo{}
%\pgfuseimage{university-logo}

% Delete this, if you do not want the table of contents to pop up at
% the beginning of each subsection:
%\AtBeginSubsection[]
%{
% \begin{frame}<beamer>
%   \frametitle{Sommario}
%    \tableofcontents[currentsection,currentsubsection]
% \end{frame}
%}

% If you wish to uncover everything in a step-wise fashion, uncomment
% the following command:

%Trasparenze and co.

%\beamerdefaultoverlayspecification{<+->}

\begin{document}
%  \hypersetup{
%    pdftitle={Task Assignment Problem in Camera Networks},
%    pdfauthor={Cerruti Federico, Fabbro Mirko, Masiero Chiara},
%    pdfpagemode={FullScreen},
%    pdfborder={0 0 0}
%  }
% \hypersetup{pdfpagemode=FullScreen}
\begin{frame}
  \titlepage
  \begin{center}
  \pgfuseimage{university-logo}
  \pgfuseimage{dei-logo}
  \end{center}
\end{frame}
% Define block styles
\tikzstyle{decision} = [diamond, draw, fill=red!20,
    text width=5em, text badly centered, inner sep=0pt]
\tikzstyle{block} = [rectangle, draw, fill=blue!20,
    text width=10em, text centered, rounded corners]
\tikzstyle{line} = [draw, -latex']
\tikzstyle{cloud} = [draw, ellipse,fill=blue!20,
    minimum height=2em]
\begin{frame}
  \frametitle{Summary}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}
% \section{The context}
% \begin{frame}
% \frametitle{The Video-Surveillance Case Study}
% \begin{itemize}
% \item \textbf{Configuration phase:}  graph selection problem; distributed calibration problem; ... \vspace{1cm}
% \item \textbf{Running phase:} coordination between area coverage for monitoring and event detection and tracking
% \end{itemize}
% \end{frame}
\section{Problem and Objectives}
\begin{frame}
  \frametitle{Task Assignment Problem: Definition}
  %\framesubtitle{Subtitles are optional.}
  % - A title should summarize the slide in an understandable fashion
  %   for anyone how does not follow everything on the slide itself.
 We are given: \\
\centering
\includegraphics[scale = 0.5]{fig/sets}
%\section{Task assignment Problem}
 \begin{itemize}
 \item a set $\mathcal{A}$ of agents $a_i$ distributed over a certain area to monitor, such that
 \begin{itemize}

    \item They have to obey to \alert{network constraints};

    \item They have \alert{limited resources}.

\end{itemize}
 %\vspace{.6cm}
 \item a \alert{time-variant} set $\mathcal{T}$ of tasks to be executed
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Objectives}
\begin{itemize}
\item We aim to attain a good \alert{trade-off between optimality and continuity} of task execution.
%\item an \alert{optimal match} between tasks that must be executed and agents that can execute them; %\vspace{.6cm}

\end{itemize}
\begin{block}{Standing assumption}
    We will focus mainly on the \alert{assignment problem} $\Rightarrow$ simplification
       %(disregarding communication issues, whenever possible)
       %\item every area is covered by two or more cameras.
\end{block}

\end{frame}

\subsection*{State-of-the-art Approaches }
\begin{frame}
 \frametitle{State-of-the-art Approaches }
  From the view-point of theory, many solutions are available. They are mainly based on:
  \begin{itemize}
    \item Dynamic systems identification
    \item Auctions
    \item Game theory
  \end{itemize}

\begin{block}{Real camera networks}
Assignment is performed by \alert{nearly Brute-force} algorithms
\end{block}
\end{frame}

\subsection*{Description of Cameras and Tasks }
\begin{frame}
\frametitle{Description of Cameras}
 Cameras $a_i$ are agents with limited resources:

  %\pgfdeclareimage[]{fig:abstract}{figura1}
  %\pgfuseimage{fig:abstract}
  \begin{center}
  \includegraphics[scale=.3]{fig/abstract}
  \end{center}
\begin{itemize}
%\item $a_i$ can communicate at least with its (topological) neighbours.
\item The monitored area can be divided into \alert{subzones}, intersecting the visual ranges of the cameras.\\  \vspace{0.5cm} \centering  $a_i$ covers one or more subzones $$\Downarrow$$ \alert{$a_i$ can execute only a subset of all possible tasks}
\end{itemize}
\end{frame}

% \begin{frame}%7
% \frametitle{Covering zones}
% \begin{itemize}
% \item The monitored area can be divided into \alert{subzones}, intersecting the visual ranges of the cameras \vspace{.6cm}
% %\item Each camera covers one ore more subzones \vspace{.6cm}
% \item It is possible to build a \alert{covering matrix} \textbf{V}:
% \begin{equation*}
% V_{ij} =
% \begin{cases}
% 1 & \text{if agent $a_i$ covers subzone $j$} \\
% 0 & \text{otherwise}
% \end{cases}
% \end{equation*}
% \end{itemize}
% \end{frame}

\begin{frame}
\frametitle{Description of Tasks}
Tasks can be:
\begin{itemize}
\item Synchronous: \emph{snapshots} and \emph{heartbeat}
\item Asynchronous:
 \begin{enumerate}
  \item Manual tracking ``Op''
  \item Automatic tracking ``Trk''
  \item Streaming ``Str''
  \item Patroling ``Pat''
 \end{enumerate}

\begin{block}{Our aim}
We want to solve the assignment problem for \alert{asynchronous tasks}, that can be considered the out-and-out ones.
\end{block}
% \begin{block}{Standing assumption 2}
%     Every area is covered by two or more cameras.
% \end{block}

\end{itemize}

\end{frame}
\section{Mathematical Model}
\begin{frame}
 \frametitle{The Pool}
 \begin{itemize}
 \item In order to assure homogeneousness we model patroling activity as a task
 \item When a task occurs, it is added to the \alert{pool}
 \begin{center}
 \includegraphics[scale = 0.6]{fig/pool}
 \end{center}
 \item A task is removed when it is completed or gets obsolete $\Rightarrow$ \alert{dropping}
 \item The pool is a \alert{global structure}
\end{itemize}
\end{frame}

\subsection*{CLP Approach}
\begin{frame}
 \frametitle{A CLP Model for Task Assignment 1}
 \begin{itemize}
  \item Given an \alert{istantaneous} pool configuration, with $H$ tasks and $N$ agents, it is easy to lay out a CLP model:
\begin{block}{CLP Model}
  \begin{equation*}\label{eq:var}
  x_{ij} =
  \begin{cases}
  1 & \text{if agent $a_i$ executes task $t_j$} \\
  0 & \text{otherwise}
  \end{cases}
  \end{equation*}
  \begin{equation*} \label{eq:ag}
  \sum _{j=1} ^H x_{ij} \leq 1 \quad \forall i \quad\text{each agent $a_i$ can execute at most one task}
  \end{equation*}
  \begin{equation*}\label{eq:ta}
  \sum _{i=1} ^N x_{ij} \leq 1 \quad \forall j \quad\text{each task $t_j$ is assigned at most to one agent}
  \end{equation*}
  \begin{equation*}\label{eq:int}
 x_{ij} \in \left\lbrace 0, 1\right\rbrace \forall i,j
 \end{equation*}
\end{block}
 \item We still haven't got it over, however...
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{A CLP Model for Task Assignment 2}
\begin{itemize}
 \item Covering constraints should be considered, but...
% They are imposed by the \alert{covering matrix} $\mathbf{V}$
%  $$
%   V_{ij} =
%     \begin{cases}
%      1 & \text{if agent $a_i$ covers subzone $j$} \\
%      0 & \text{otherwise}
%     \end{cases}
%  $$
\medskip
\begin{alertblock}{Covering constraints}
 ...modeling them as constraints lead to a \alert{non-TUM} formulation, in general!
\end{alertblock}
\medskip
 \item We skip them out by choosing a clever \alert{utility function} $f(\mathbf{x})=\mathbf{c}^T\mathbf{x}$:
  \begin{equation*}\label{eq:f}
    c_{ij} =
  \begin{cases}
    score(j) & \text{if $a_i$ can monitor $t_j.loc$} \\
    -\infty & \text{otherwise}
  \end{cases}
\end{equation*}
 \item We now obtain a TUM constraint matrix $\Rightarrow$ \alert{Integer constraints are redundant!}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A CLP Model for Task Assignment 3}
\begin{itemize}
 \item We can now obtain optimum \alert{instantaneous} solution, but what about \alert{problem dynamics}?
%  \item Modifications in the pool imply variations in the polyhedron of decision variables $x_{ij}$
      \begin{center}
       \includegraphics[scale = .5]{fig/poliedro}
      \end{center}
 \item Modifications in the pool imply variations in the polyhedron of decision variables $x_{ij}$
%  \item Let $\mathcal{Z}$ be the set of all possible strings $x_{11}\dots x_{1H}x_{21}\dots x_{2H} \dots  x_{NH}$.
%  \item Let $\mathcal{X}\subset \mathcal{Z}$ be the set of all the feasible strings.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{A CLP Model for Task Assignment 4}
\begin{itemize}
\item The number of feasible solutions is
    \begin{equation*}\label{eq:comb}
      |\mathcal{X}| = \sum _{k=0}^N \binom{N}{k}\frac{H!}{(H-k)!}
    \end{equation*}
%  \item If patroling tasks are enough, in optimum solutions all agents are busy
%  %We have two cases of modification:
%  \begin{enumerate}
%   \smallskip
%   \item \alert{a new task occurs}: the number of potentially optimum solutions is multiplied by $\frac{H+1}{H+1-N}$
% \smallskip
%   \item \alert{a task is dropped or completed}: the polyhedron loses $N$ dimensions
% \smallskip
%  \end{enumerate}
 \item \alert{New} or \alert{completed} tasks: it is extremely difficult to understand how the optimum solution changes!
\end{itemize}

\begin{center}
\includegraphics[scale=0.5]{fig/esempio1}
\end{center}

\end{frame}


\subsection*{Performance Metrics, Parameters and Constraints}
\begin{frame}
\frametitle{Performance Metrics 1}
\begin{itemize}
  \item
    A measure of \alert{optimality} (in the sense of task's type priority) is given by
    \begin{equation*}
      P(t)=\frac{1}{t}\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{p_n(\tau)}}
    \end{equation*}
%   \item
%     Let be the \alert{IDLE occurrence rate}
%     \begin{equation*} \label{IdleCounter}
%       I(t) = \frac{1}{t}\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{\textup{Idle}_n(\tau)}}
%     \end{equation*}
  \item
    \alert{Average discontinuity rate}: cases of agents that leave tasks before completing them.
    \begin{equation*}
      D(t)=\frac{1}{t}\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{d_n(\tau)}}
    \end{equation*}
\item
    Let be the \alert{IDLE occurrence rate}
    \begin{equation*} \label{IdleCounter}
      I(t) = \frac{1}{t}\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{\textup{Idle}_n(\tau)}}
    \end{equation*}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Performance Metrics 2}
\begin{itemize}
  \item
    The \alert{Average waiting time} is:
    \begin{equation*}
      W = \frac{1}{|\mathcal{H}_C|}\sum_{h\in\mathcal{H}_C}
          {T_{\textup{end}}(h)-T_{\textup{occ}}(h)-T_{\textup{serv}}(h)}
    \end{equation*}
  \item
    \alert{Complexity}: expressed in term of $O(\cdot)$.\smallskip
  \item
    \alert{Dropping rate}:
    \begin{equation*}
      F=\frac{|\mathcal{H}_\textup{drop}|}{|\mathcal{H}|}
    \end{equation*}
    with $\mathcal{H}_\textup{drop}$ set of dropped tasks and $\mathcal{H}$ set of generated tasks.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Instance Parameters and Constraints}
\begin{itemize}
  \item
    In case of uniform topology, a general \alert{load factor} can be estimated.
    \begin{equation*}
      C = \frac{1}{N}
          \left(
            \frac{\overline{T}_\textup{serv}^\textup{OP}}
                 {\overline{T}_\textup{occ}^\textup{OP}}
           +\frac{\overline{T}_\textup{serv}^\textup{TRK}}
                 {\overline{T}_\textup{occ}^\textup{TRK}}
           +\frac{\overline{T}_\textup{serv}^\textup{STR}}
                 {\overline{T}_\textup{occ}^\textup{STR}}
          \right)
    \end{equation*}
  \bigskip
  \item If there is no redundancy in covering areas, i.e.:
    \begin{equation*}
         \textit{rank}(\mathbf{V}) = N
    \end{equation*}
   $\Rightarrow$  in optimal solution all agents are busy
  \end{itemize}
\end{frame}



\section{Proposed Approach}
\subsection*{The Stable Marriage Problem}
\begin{frame}
 \frametitle{The SMP Problem}
 We are given:
 \begin{itemize}
 \item a set of $n$ men and $n$ women
 \item a preference list for each person, where all the persons of the opposite sex appear
 \end{itemize}
 \smallskip
 \begin{block}{Objective}
 Finding a set of \alert{stable marriages} between the men and the women.
 \end{block}
 \smallskip
 \begin{exampleblock}{Stable matching}
 A marriage is stable if there are \alert{no dissatisfied pairs}: $ \nexists \, (m,w)$ s.t. $m$ prefers $w$ to his current wife and $w$ prefers $m$ to her current husband
 \end{exampleblock}
\end{frame}

\begin{frame}
\frametitle{Gale-Shapley Algorithm 1}
\begin{itemize}
\item an \alert{unpaired man} \emph{X} considers the \alert{first woman on
his list} \emph{a} and removes her from it
\begin{center}
\includegraphics[scale=.5]{fig/men}
\end{center}

\item two situations are possible, depending on \emph{a} 's status
\end{itemize}


\end{frame}

\begin{frame}
\frametitle{Gale-Shapley Algorithm 2}
\begin{enumerate}
\item \emph{a} is not engaged $\Rightarrow$ \emph{a} accepts \emph{X} 's proposal
\item \emph{a} is engaged $\Rightarrow$ \emph{a} can change her husband, depending on her list
\end{enumerate}
\begin{center}
\includegraphics[scale=.4]{fig/GS}
\end{center}

\end{frame}

\begin{frame}
\frametitle{Gale-Shapley Algorithm 3}
\begin{block}{Observations}
\begin{itemize}
\item Once a woman becomes attached, she remains married, altough she can change her partner
\item The \alert{termination} of the algorithm is assured
\item This marriage is \alert{stable}
\end{itemize}
\end{block}
\smallskip
\begin{exampleblock}{Question}
Is it possible a direct application of this algorithm to our case study problem?
\end{exampleblock}

\end{frame}
% \begin{frame}
% \frametitle{Lagesse's Algorithm}
% \begin{itemize}
%  \item Assignment of tasks to employees $\Rightarrow$ \alert{Multiple Knapsack Problem}
%  \begin{itemize}
%    \item Employee time $\Leftrightarrow$ Knapsack
%    \item Tasks $\Leftrightarrow$ Items
%    \item Task execution time $\Leftrightarrow$ Weight
%   \end{itemize}
% \end{itemize}
% \begin{block}{Algorithm}
%  Assignment based on \alert{preference lists}
% \end{block}
% % Assignment of tasks to employees, taking into consideration manager and employees preference, employee time and employee skills
% \begin{block}{Problem}
% \centering
% \alert{Dinamics} and \alert{non-homogeneousness} of tasks and agents $$\Downarrow$$ no direct application!
% % A direct application of this algorithm to our case study problem is not
% % possible, because it is more complex owing to dinamicity and the characteristics of tasks and agents
% \end{block}
% \end{frame}

\begin{frame}
 \frametitle{The SMP Problem: Variants 1}
 \begin{block}{Stable marriage problem with incomplete lists (SMI)}
 \begin{itemize}
 \item The number of men and women may be not the same
 \item Each person's preference list consists of a \alert{subset} of the members of the opposite sex in \alert{strict order}
% \item Each person’s preference list consists of a subset of the members of the opposite sex in strict order
%  There is always at least one stable matching for an instance of the SMI
\end{itemize}
\end{block}
\begin{block}{Stable marriage problem with ties (SMT)}
\begin{itemize}
\item Lists can have \alert{ties} i.e. no strict order in preferences
\end{itemize}
\end{block}
\begin{exampleblock}{Stable solution}
 \begin{itemize}
  \item There is always \alert{at least one stable matching} for an instance of both SMI and SMT
 \end{itemize}
\end{exampleblock}

\end{frame}

\begin{frame}
\frametitle{The SMP Problem: Variants 2}
 Our case:
\medskip
\begin{block}{Stable marriage problem with ties and incomplete lists (SMTI)}
\begin{itemize}
 \smallskip
 \item A stable matching can be found by \alert{breaking all the ties}...
 \smallskip
 \item... but the ways in which ties are broken affect the solution!
 \smallskip
 \item Finding a solution of \alert{maximum cardinality} is a \alert{NP-hard problem}
\end{itemize}
\end{block}
\end{frame}

\subsection*{Our algorithm: SMTI Revised}

\begin{frame}
 \frametitle{SMTI Revised Algorithm 1}
  \framesubtitle{a.k.a. The Wedding Planner Algorithm}
  \begin{block}{Building lists}
  %\alert{Building lists}
  \begin{itemize}
 %\item task $\Rightarrow$ static list containing all agents that can execute it
  \item agent $\Rightarrow$ list containing all tasks it can execute, \alert{sorted} by
  \end{itemize}
  \textcolor{darkgreen}{$$ score = \alpha \cdot pr_{tsk} + \gamma \cdot \frac{lft_{tsk}}{drop_{tsk}} $$}
   \end{block}
   \begin{columns}
   \column{.6\textwidth}
  \begin{itemize}
 \item $pr_{tsk} \Rightarrow$ intrinsic priority of the task \emph{tsk}\\
  \smallskip
  \item $lft_{tsk} \Rightarrow$ lifetime of the task \emph{tsk}\\
  \smallskip
  \item $drop_{tsk} \Rightarrow$ drop time of the task \emph{tsk}
 \smallskip
 \item $\gamma = 1 - \alpha$

  \end{itemize}
  \column{.7\textwidth}
  \includegraphics[scale=.5]{fig/AG}
  \end{columns}
 \end{frame}


\begin{frame}
\frametitle{SMTI Revised Algorithm 2}
\begin{itemize}
 \item Ties $\Rightarrow$ \alert{Temporary lists} of tasks $t_j$
 \begin{center}
\includegraphics[scale=.5]{fig/ties}
  \end{center}
\item Current agent $a_i$ proposes to tasks of the current Temporary List ($currTempList$)
\end{itemize}
\begin{block}{}
Three situations are possible, depending on status of the tasks
\end{block}
\end{frame}

\begin{frame}
\frametitle{SMTI Revised Algorithm 3}

 %\item Agent $a_i$ proposes to a $t_j$
  \begin{enumerate}
    \smallskip
    \item $a_i$ already executing its favourite task $\Rightarrow$ no change
    \smallskip
    \item $ \exists \, t_j \in currTempList$ unmatched $\Rightarrow$ ($a_i,t_j$) now matched
    \smallskip
    \item $ \nexists \, t_j \in currTempList$ unmatched $\Rightarrow$ there may be a \alert{swap}
    \medskip
 \end{enumerate}
 \begin{itemize}
 \item if $a_i$ still unmatched, a new temporary list (lower score) is built
 \item if $a_i$'s list has come to an end, another agent $a_k$ is considered
\end{itemize}
\begin{exampleblock}{Termination}
The algorithm is repeated until it attains a stable matching.
\end{exampleblock}
\end{frame}
\begin{frame}
 \frametitle{Swap Policy}
\begin{itemize}
 \item $a_i$ asks for a task $t_j$ being executing by $a_k$. There is a \alert{swap} if:
 \begin{enumerate}
  \item %in the remaining part of $a_j$ 's list there are fewer tasks than in $a_k$'s residual list
   $a_i$ has fewer left tasks it can propose to\\
   \includegraphics[scale = 0.5]{fig/ivsk1}
  \item %they have the same number of residual tasks, but $a_i$ global list is shorter
  $a_i$ and $a_k$ have the same number of residual tasks, but $a_i$ 's global list is shorter \\
  \includegraphics[scale = 0.5]{fig/ivsk2}
\end{enumerate}
\begin{block}{Motivation}
 We want to prevent the tasks from being idle, possibly
\end{block}
\end{itemize}
\end{frame}

\subsection*{Comparison}
\begin{frame}
 \frametitle{Proposed Algorithms}
 SMTI Revised algorithm will be compared with:
 \smallskip
\begin{itemize}
 \item Randomized SMTI Revised
 \item Centralized Assignment
 \item Nearly Brute-force (Purely Random) Assignment
 \item Greedy Assignment
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{SMTI Revised}
To begin with, let's analyse our approach...
\begin{itemize}
  \item Computational complexity $O(N ^ 2)$.
\begin{exampleblock}{Pros}
       \begin{enumerate}
       \item No deadlocks (Swap rule)
       \item Scalable
      \end{enumerate}
\end{exampleblock}
 \begin{alertblock}{Cons}
\begin{enumerate}
       \item Continuity is not assured
       \item Assignment is \alert{stable} but it \alert{could be not optimal}
       \item There could be IDLE agents
      \end{enumerate}
 \end{alertblock}
 \end{itemize}
\end{frame}

\begin{frame}
\frametitle{SMTI Revised: Critical Situations}
 \begin{itemize}
  \item Non-optimality from the view-point of the utility function:
 \begin{figure}
 \centering
 \includegraphics[scale=0.4]{fig/critTS2a}\quad
 \includegraphics[scale=0.4]{fig/critTS2b}
 \end{figure}
 \item The matching depends on the first considered agent!
 \end{itemize}
\end{frame}
%
% \begin{frame}
% \frametitle{SMTI Revised: Critic Situations 2}
%  \begin{itemize}
%   \item Another case of non-optimality:
% \begin{figure}
%  \includegraphics[scale=0.4]{fig/critTS2a}\qquad
%  \includegraphics[scale=0.4]{fig/critTS2b}
%  \end{figure}
%  \item The matching depends on order in which agents are considered!
%  \end{itemize}
% \end{frame}
%
\begin{frame}
 \frametitle{Randomized SMTI Revised}
   \centering
   \includegraphics[scale=0.4]{fig/critTSa}\qquad
   \includegraphics[scale=0.4]{fig/critTSb}
 \begin{itemize}
 \item Can \alert{randomized swaps} solve the problem?
 \item $P\left[equivalent\, agents \,do\, swap\right] =p $\\In this case: $a_1$ and $a_2$ should swap in the $1^{st}$ iteration, then they should not: $P = p(1-p)$ $$\Downarrow$$
 \centering \alert{There are not sufficient guarantees of improvement!}
 \end{itemize}
\end{frame}


\begin{frame}
\frametitle{Centralized Assignment}
\begin{itemize}
  \item It finds the optimum solution of the CLP problem (by means of Simplex, for instance).
\begin{exampleblock}{Pros}
       \begin{enumerate}
       \item Optimality
       \end{enumerate}
\end{exampleblock}
 \begin{alertblock}{Cons}
\begin{enumerate}
       \item Discontinuity
       \item Worst case complexity: $O({2^{H}}^N)$ %$\binom{n}{k}$ where $n =NH$ and $k = N+H$
       \item Not scalable
      \end{enumerate}
 \end{alertblock}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Nearly Brute-force}
 \begin{itemize}
  \item Each agent performs the following sequence of operations:
\end{itemize}
\begin{figure}
\begin{center}
\begin{tikzpicture}[auto]
    % Place nodes
    \node [cloud,scale = 0.6] (start) {Start};
    \node [decision, below of=start, node distance=1.4cm,scale = 0.6] (isFree) {is $a_i$ unloaded?};
    \node [decision, below of=isFree, node distance=2cm,scale = 0.6] (isPat) {is $a_i$ patroling?};
    \node [block, right of=isPat,node distance=2.7cm,scale = 0.6] (randomMatch){$a_i$ randomly picks an available unmatched task (different from patroling, if it exists)};
    \node [block, below of=isPat,node distance=1.7cm,scale = 0.6] (noChange) {$a_i$ keeps executing the same task};
    % Draw edges
    \path [line] (start) -- (isFree);
    \path [line] (isFree) -- node {no} (isPat);
    \path [line] (isFree) -| node [near start] {yes} (randomMatch);
    \path [line] (isPat) -- node {yes} (randomMatch);
    \path [line] (isPat) -- node {no} (noChange);
  \end{tikzpicture}
 \end{center}
\end{figure}
\end{frame}
\begin{frame}
\frametitle{Nearly Brute-force 2}
\begin{itemize}
  \item Its computational complexity in the worst case is $O(NH)$

\begin{exampleblock}{Pros}
       \begin{enumerate}
       \item Maximum continuity
       \item Scalable
      \end{enumerate}
\end{exampleblock}
 \begin{alertblock}{Cons}
\begin{enumerate}
       \item No optimality criterion
       \item Idle agents
 \end{enumerate}
 \end{alertblock}
 \end{itemize}
\end{frame}

% \begin{frame}
%  \frametitle{Idle agents occurence}
%  \begin{itemize}
%   \item With NB-f there may be \alert{idle agents}!
%  \end{itemize}
% \centering
% \includegraphics[scale = 0.5]{fig/idlePRApres}
% \end{frame}


\begin{frame}
 \frametitle{Greedy Assignment}
 \begin{itemize}
  \item Each agent performs the following sequence of operations:
\end{itemize}
  \begin{figure}
\begin{center}
\begin{tikzpicture}[auto]
    % Place nodes
    \node [cloud,scale = 0.6] (start) {Start};
    \node [block, below of=start, node distance=1cm,scale = 0.6] (pool) {$a_i$ looks through the pool for the best unmatched task $t_{best}$};
    \node [decision, below of=pool, node distance=1.7cm,scale = 0.6] (isBetter) {is $t_{best}$ better than $t_{curr}$?};
    \node [block, right of=isBetter,node distance=2.7cm,scale = 0.6] (newMatch){$a_i$ drops $t_{curr}$ and starts executing $t_{best}$};
    \node [block, below of=isBetter,node distance=1.7cm,scale = 0.6] (noChange) {$a_i$ keeps executing $t_{curr}$};
    % Draw edges
    \path [line] (start) -- (pool);
    \path [line] (pool) -- (isBetter);
    \path [line] (isBetter) -- node [near start] {yes} (newMatch);
    \path [line] (isBetter) -- node {no} (noChange);
  \end{tikzpicture}
  \end{center}
\end{figure}
 \end{frame}


\begin{frame}
\frametitle{Greedy Assignment 2}
\begin{itemize}
  \item   The computational complexity is always $O(NH)$

\begin{exampleblock}{Pros}
       \begin{enumerate}
       \item Scalable
       \end{enumerate}
\end{exampleblock}
 \begin{alertblock}{Cons}
\begin{enumerate}
       \item Continuity is not assured
       \item Idle agents
 \end{enumerate}
 \end{alertblock}
 \end{itemize}
\end{frame}

\begin{frame}
 \frametitle{Non optimality of GA and NBf}
 \begin{itemize}
  \item GA and NBf do \alert{not} assure optimality!
 \end{itemize}
 \centering
 \includegraphics[scale = .5]{fig/esempio2} \\
\medskip
$$\footnotesize f_{OP}=1 \qquad f_{TRK} = 0.75 \qquad f_{STR}=0.5 $$
\end{frame}

\begin{frame}
 \frametitle{Idle agents occurrence}
 \begin{itemize}
  \item With NB-f and GA there may be \alert{idle agents}!
 \end{itemize}
\centering
\smallskip
\includegraphics[scale = 0.5]{fig/idlePRApres}


\end{frame}


\section{Simulations}
\begin{frame}
\frametitle{Simulations}
\textbf{Our framework:}
\begin{columns}
  \column{.4\textwidth}
    \centering
     \includegraphics[scale=.5,trim= 0 0 0 0]{fig/topologia}
      %height=5cm,width=7cm,autostart,poster

  \begin{equation*}
      N=8 \qquad M=9
    \end{equation*}
  \column{.5\textwidth}
    \begin{itemize}
      \item Covering matrix:
        \begin{equation*}
           \mathbf{V}=
           \footnotesize
           \begin{bmatrix}
             1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
             1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
             0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0\\
             0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0\\
             0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0\\
             0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\
             0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1\\
             0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0
           \end{bmatrix}
        \end{equation*}\smallskip
      \item Interarrival time: ${T}_\textup{occ}=2s$ \smallskip
      \item Service time: ${T}_\textup{serv}=3s$ \smallskip
      \item Simulation time: $T = 500 s$. \smallskip
      \item Load factor: $C \approx 0.48$.
    \end{itemize}
\end{columns}
\end{frame}

\begin{frame}
 \frametitle{Simulation Environment}
 \begin{center}
 \movie[height=6cm,width=10cm,duration=10s,poster,showcontrols]{}{simulatoreCorto.avi}
  \end{center}
\end{frame}


\subsection*{Assigned priority}

\begin{frame}
\frametitle{Assigned priority}
\begin{columns}
  \column{.5\textwidth}
    \includegraphics[scale=.65,trim= 5.7cm 10cm 6.5cm 10.5cm]{fig/priorityNew}
  \column{.5\textwidth}
    \includegraphics[scale=.6,trim= 8cm 13.5cm 8cm 13.5cm]{fig/legend}
    \bigskip
    \begin{itemize}
      \item PLI performs best, as it is designed to maximize instantaneous priorities.
      \item SMTI Revised does well, and places itself immediately under the top.
      \item Greedy achieves mean results, especially with longer $T_\textup{drop}$ that provides more feasible tasks in pool.
      \item NBF does not care about priorities.
    \end{itemize}
\end{columns}
\end{frame}

\subsection*{Drop Rate}
\begin{frame}
\frametitle{Drop Rate}
\begin{columns}
  \column{.4\textwidth}
    \includegraphics[scale=.57,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/dropNew}
  \column{.6\textwidth}
     \begin{itemize}
       \item $T_\textup{drop}\uparrow \; \Longrightarrow \; \textup{Drop Rate} \downarrow$
        \begin{itemize}
          \item \textit{Upper bound defined by the practice implementation.}
        \end{itemize}
      \medskip
      \item Big $\alpha$ favours only the highest priority tasks.
     \end{itemize}
\end{columns}
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/dropOPnew}\quad
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/dropTRKnew}\quad
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/dropSTRnew}
\end{frame}

\subsection*{Average Waiting Time}
\begin{frame}
\frametitle{Average Waiting Time 1}
\begin{columns}
  \column{.4\textwidth}
    \includegraphics[scale=.57,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/waitingNew}
  \column{.6\textwidth}
    \begin{itemize}
      \item Longer $T_\textup{drop}$ allows larger queue. Waiting time increases.
      \item In general big $\alpha$ means short queue time for tasks, but\dots
    \end{itemize}
\end{columns}
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/waitingOPnew}\quad
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/waitingTRKnew}\quad
\includegraphics[scale=.41,trim= 5.9cm 11.1cm 6.2cm 11.3cm]{fig/waitingSTRnew}
\end{frame}

\begin{frame}
\frametitle{Average Waiting Time 2}
\begin{columns}
  \column{.4\textwidth}
    \includegraphics[scale=.5,trim= 0 1cm 0 0]{fig/SlidingPool}
  \column{.6\textwidth}
    \textbf{Most probable area of task execution:}
    \begin{itemize}
      \item \alert{Big $\alpha$} \\ Uniformely distributed over time, but shrinked around high priority tasks.
      \item \alert{Small $\alpha$} \\ Uniformely distributed over priorities, but closer to the drop limit.
    \end{itemize}
\end{columns}
\bigskip\bigskip
\dots the lowest priority tasks (streaming) do not profit by $\alpha$, because they are neglected in favour of higher priority tasks!
\end{frame}

\subsection*{Discontinuity in task execution}
\begin{frame}
\frametitle{Discontinuity in task execution}
\begin{columns}
  \column{.5\textwidth}
    \includegraphics[scale=.65,trim= 5.7cm 10cm 6.5cm 10.5cm]{fig/discontinuityNew}
  \column{.5\textwidth}
    \includegraphics[scale=.6,trim= 8cm 13.5cm 8cm 13.5cm]{fig/legend}
    \bigskip
    \begin{itemize}
      \item PLI doesn't care about continuity. \smallskip
      \item Greedy and Nearly Brute Force are extremely conservative in assignment. \smallskip
      \item SMTI Revised is a good trade off. It leaves past configurations if there are chances to improve assigned priority.
    \end{itemize}
\end{columns}
\end{frame}

\subsection*{IDLE occurrence}
\begin{frame}
\frametitle{IDLE occurrence}
\begin{columns}
  \column{.5\textwidth}
    \includegraphics[scale=.65,trim= 5.7cm 10cm 6.5cm 10.5cm]{fig/idleNew}
  \column{.5\textwidth}
    \includegraphics[scale=.6,trim= 8cm 13.5cm 8cm 13.5cm]{fig/legend}
    \bigskip
    \begin{itemize}
      \item Under previously stated conditions, \alert{PLI never shows IDLE agents}.
      \item SMTI Revised achives good performances, as it swaps agents trying to obtain a better balance.
      \item In Greedy each agent considers only the best solution for itself.
      \item Nearly Brute Force performances are random. In average it is placed between Greedy and SMTI Revised.
    \end{itemize}
\end{columns}
\end{frame}

% \subsection*{Assigned priority}
% \begin{frame}
% \frametitle{Assigned priority}
% \begin{columns}
%   \column{.5\textwidth}
%     \includegraphics[scale=.65,trim= 5.7cm 10cm 6.5cm 10.5cm]{fig/priorityNew}
%   \column{.5\textwidth}
%     \includegraphics[scale=.6,trim= 8cm 13.5cm 8cm 13.5cm]{fig/legend}
%     \bigskip
%     \begin{itemize}
%       \item PLI performs best, as it is designed to maximize instantaneous priorities.
%       \item SMTI Revised does well, and places itself immediately under the top.
%       \item Greedy achieves mean results, especially with longer $T_\textup{drop}$ that provides more feasible tasks in pool.
%       \item NBF does not care about priorities.
%     \end{itemize}
% \end{columns}
% \end{frame}

\section{Conclusions and Future Work}
\begin{frame}
 \frametitle{Conclusions}
  \begin{block}{Centralized assignment}
  \begin{itemize}
    \item Instantaneously optimum assignment
    \item Bad scalability and continuity
    \item No distributed implementation
  \end{itemize}
   \end{block}
 \begin{alertblock}{SMTI Revised}
  \begin{itemize}
  \item Good trade-off between optimality and continuity
  \item Scalable
  \item Distributed implementation available
  \end{itemize}
 \end{alertblock}
\begin{exampleblock}{Greedy and NBF}
 \begin{itemize}
  \item Strongly dependent on agents sequence (\alert{no swap})
  \item Easy to implement: scalable, potentially distributed and cheap
  \item Poor performances (especially for NBF)
 \end{itemize}

\end{exampleblock}

\end{frame}

\begin{frame}
\frametitle{Future Work}
\begin{itemize}
\item \alert{Communication} costs
\medskip
\item \alert{Distributed} version
\medskip
\begin{itemize}
      \item Consistent pool
      \smallskip
      \item Synchronization and conflicts management (\alert{consensus} or \alert{leader} agent)
      \smallskip
  \end{itemize}
\item \alert{Market-based} approach
\medskip
   \begin{itemize}
     \item Auction mechanism
      \smallskip
      \item Swap policy
      \smallskip
   \end{itemize}
\item Extension to \alert{PTZ} cams
\end{itemize}
\end{frame}
\section*{The end}
\begin{frame}
 \centering
 \Huge{The End}\\
 \medskip
 \begin{center}
 \large{Grazie per l'attenzione!}
 \end{center}
\end{frame}

\end{document}
