%\documentclass[a4paper,11pt,twocolumn]{article}

\documentclass[12pt,journal,compsoc,a4paper,onesided]{IEEEtran}
\renewcommand{\rmdefault}{ptm}\selectfont

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}

\usepackage[pdftex]{graphicx}
\usepackage{subfig}
\usepackage{placeins}

\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{fixltx2e}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[a4paper, top=3cm, bottom=3cm, left=1.75cm, right=1.75cm, bindingoffset=5mm]{geometry}
%tikz
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}

%fancyhdr
\usepackage{fancyhdr}
\pagestyle{fancy}
\lhead{}
\chead{Progettazione di sistemi di controllo A.A. 2009/2010}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

%\pagestyle{plain}
%lasciamo un po' di margine

% \setlength{\paperheight}{297mm}
% \setlength{\paperwidth}{210mm}
% %\setlength{\textwidth}{165mm}
% \setlength{\textheight}{240mm}
% \setlength{\topmargin}{-10mm}
% %\setlength{\rightmargin}{10mm}
% %\setlength{\leftmargin}{10mm}
% %  \evensidemargin=1cm
% %  \oddsidemargin=1cm

%title page
\title{
%Università degli studi di Padova\\ % \includegraphics[scale = 0.3]{fig/logoUnipd}
% Corso di laurea magistrale in Ingegneria dell'Automazione\\
%\textbf{Progettazione di Sistemi di Controllo}\\Prof. Schenato Luca\\
% \vspace{0.5cm}
\textbf{Task Assignment Problem in Camera Networks}}
\author{Cerruti Federico 607374, Fabbro Mirko 586668, Masiero Chiara 600608}
\date{}

\markboth{Progettazione di sistemi di controllo A.A. 2009/2010}%
{Task Assignment Problem in Camera Networks}


\newcommand{\tr}{\mathrm {tr}}
%ora si creano nuovi contatori per teoremi etc....
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{condition}{Condition}
\newtheorem{example}{Example}
\newtheorem{pr}{Proof}

\begin{document}

\maketitle

\thispagestyle{plain}
%\IEEEcompsoctitleabstractindextext{%
\begin{abstract}
%\boldmath
This paper takes the move from a real case study and deals with the problem of task assignment in camera networks. A mathematical model is proposed and different approaches are compared. The attention is mainly focused on algorithms that derive from Constraint Linear Programming and Stable Marriage Problem (SMP).
An optimality criterion over static scenarios is defined. Subsequently it is given prominence to problem dynamics, that is a crucial issue. As a matter of fact, we would like to attain a good trade-off between continuity and optimality in matching tasks and agents. The former means that it is advisable to restrain discontinuities in task execution. The latter aims to give preference to high priority tasks.
The proposed generalization of the SMP algorithm highlights good performances. It assures a sufficient degree of continuity, it prevents deadlocks and it is tunable. Moreover, it can be recast quite easily as a  distributed algorithm.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the journal you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals frown on math
% in the abstract anyway. In particular, the Computer Society does
% not want either math or citations to appear in the abstract.

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Camera networks, task assignment.
\end{IEEEkeywords}

%}

%\tableofcontents

%\begin{titlepage}
%\begin{center}
%\vspace{10cm}
%{\LARGE {\bfseries UNIVERSITA' DEGLI STUDI \\[0.3cm]DI PADOVA}}\\
%\vspace{1cm}
%{\Large Facoltà di Ingegneria\\[1cm] Corso di Laurea Magistrale \\[0.2cm]in Ingegneria dell'Automazione}\\
%\vspace{2cm}
%\end{center}
%\end{titlepage}

%\newpage

%\tableofcontents

%\newpage
\section{Introduction}
%\IEEEsetlabelwidth{a}
\subsection{The video surveillance case study}
\IEEEPARstart{T}{his} work is a part of a project about video surveillance: given a set of agents distributed over a certain area and subject to network constraints and agent limitations, this project aims to solve the following problems:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
\item dividing the interesting monitored area in subzones according to the positions where the cameras are placed and establishing a connectivity graph (which cameras can communicate), a topological graph (which subzones are adjacent) and a visibility graph (which subzones can be ''seen'' by every camera);
\item using information from the calibrated cameras and the objects that are shot both by the calibrated and the non-calibrated cameras in order to determine the parameters about the non-calibrated cameras;
\item coordinating agents for attaining an optimal match between tasks that must be executed (i.e. keeping the area monitored or detecting and tracking events that occur in the environment) and agents that can execute them (according to their positions and their graphs);
\item coordinating agents so that, when an event occurs, this event is tracked and all the interested area keeps being monitored with efficiency.
\end{enumerate}

Here, we will focus on the third point.

\subsection{Objective and motivations}
As we stated above, this work aims to develop an efficient algorithm in order to coordinate a group of cameras distributed over an area to monitor. \\
We are given a set of agents and a group of requests of execution from tasks that periodically arrives at the network.
We have to find a good assignment of the tasks to the agents, according to the positions of the agents and the types of the tasks, so that the number of the executed tasks is maximized and their lifetimes are minimized. \\
At the present, a nearly brute-force method is used for matching: the first agent that is free and can execute a task starts to execute it; if a critical situation takes place, a special agent (the so called \emph{leader}) solves the problem of assignment.

\subsection{A simple description of tasks and agents}\label{sec:desc}

Cameras can be considered as agents with limited resources. Hardware structure of the cameras is shown in figure (\ref{fig:hw}).

\begin{figure} [htb]
\begin{center}
\includegraphics[scale = 0.4]{fig/abstract}
\caption{Hardware structure of cameras}
\label{fig:hw}
\end{center}
\end{figure}

Each agent can communicate at least with its (topological) neighbours and can execute a subset of all possible tasks.
In fact, the monitored area can be divided into subzones, that are obtained intersecting the visual ranges of the cameras. With this convention, each camera covers one ore more subzones and it is possible to build a covering matrix $\mathbf{V}$ that represents the visibility graph. When a task is generated, it is also given an attribute that specifies its location (or target agent, depending on the type) of interest. A camera can execute only tasks that concern one of the subzones it covers.

Two groups of tasks can be distinguished:
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item {\bfseries asynchronous tasks:} each of them periodically repeats the request of its execution, until it is assigned to an agent (\emph{pulsated broadcast});
\item {\bfseries synchronous tasks:} they represent the only redundant piece of information of the network: the (synchronous) \emph{heartbeat} contains information about the state of the network; the \emph{snapshots} are used as backup information if necessary.
\end{itemize}

%Da portare alla sezione tecnica
The assignment problem exists for asynchronous tasks, so we will focus mainly on them. In our simplified formalisation, they include:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
\item \emph{patroling:} it employs the hard-disk of the cameras; if an anomalous event takes place (i.e. an \emph{event detection} occurs), it is automatically tracked and a state packet (asynchronous heartbeat) is generated and put in the network;
\item \emph{automatic tracking:} its request is pulsated by a camera that has noticed an anomalous event during its patroling operation;
\item \emph{manual tracking:} it employs the serial port of a camera; it has the highest priority and is executable by only one agent;
\item \emph{streaming:} agents are used as repository of video information.
\end{enumerate}


 %SI POTREBBERO AGGIUNGERE ANCHE LE INFO SULL'USO DELLE RISORSE HARDWARE (DOCUMENTO GOOGLE)

\subsection{Task assignment problem: literature survey}\label{sec:litSurvey}
%\subsection{Previous works on task assignment}
Applications of task assignment problem can be found in many different disciplines. We have focused mainly on works related to information technology and informatics, but some of the most interesting hints were offered by other fields, such as business administration and project management.

We will now summarize the most important ideas that previous works on task assignment suggested to us.
Anyway, it is important to point out that we were not able to collect specific research material on camera networks. Probably, application of task assignment algorithms to video-surveillance problems is still not a well-established practice.

Depending on available resources, features and skills of the agents, it is possible to turn to a variety of solving techniques. In this section we recall the most meaningful approaches with regard to our specific aim.
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item \textbf{Brute-force approach}. Although not optimal, it is frequently used in applications because of its simplicity. A completely brute-force approach would imply the enumeration of all possible solutions to the matching problem, that is usually unfeasible. At the present, the camera networks installed by the case study company~\footnote{\textbf{Videotec S.p.a.} Via Friuli, 6 - 36015 Schio (VI) Italy}, are equipped with a nearly brute-force algorithm. It is not necessary to enumerate all possible combinations of task and agents: the underlying idea is that, when a new task occurs, the first agent that gets free starts executing it (if the task can be carried out by that specific agent: as it has already been pointed out, tasks are ``localized''). In addition, there migth be a special leader agent that can solve dangerous situations in which conflicts take place (i.e. when two or more agents ask to be assigned to the same task). In this cases, the leader decides the winner in the competition, usually by means of a random choice. Brute-force approach does not give any guarantees on the quality of assignment. However, it is quick and robust to node failure (i.e. when a camera loses the contact with the rest of the net). Moreover, the presence of a leader agent prevents deadlocks.
\item \textbf{Identification based approach}. A completely different point of view is the one offered by M. J. Feiler in his article \cite{art:feiler}. This approach was firstly proposed in the field of identification of dynamic systems. Its aim is to match the elements of an agent set $\mathcal{A}$ with elements belonging to an information set $\mathcal{S}$.
% In particular, the author demonstrates the consistency of estimates $\bar{\Theta} _i$ of the parameters $\Theta _i \in \mathcal{S}$.
The standing assumptions is that agents can communicate their positions with each other.
% \begin{itemize}
%  \item Estimates, i.e. elements of the agent set $\mathcal{A}$, can move freely in the parameters space.
%  \item They can communicate with each other their positions.
% \end{itemize}
A simple algorithm that provides the estimates is:
\begin{equation}\label{eq:feiler1}
 \tilde{\Theta _i}(t+1,t) = (1-\eta _i\left[\tilde{\Theta(t,t)})\right]) \tilde{\Theta}(t,t)
\end{equation}
where
\begin{equation}\label{eq:feiler2}
 \eta_i\left[ \tilde{\Theta}(t,t)\right] =  \frac{{||{\tilde{\Theta}_i(t,t)}||}^{-2}}{\sum _{k=1} ^N {||{\tilde{\Theta}_k(t,t)}|| }^{-2} }
\end{equation}
The left-hand term of equation (\ref{eq:feiler1}) is the distance, existing at time $t+1$, between agent $i$ and the piece of information $\Theta\in \mathcal{S}$ appeared at time $t$.
The second equation (\ref{eq:feiler1}) implies that the distance decreases as much as the esimate $\hat{\Theta}$ gets closer to the real parameter $\Theta$.
The main result of the article is the following.
If the number of agents is greater or equal to $|\mathcal{S}|$, for all $\Theta \in \mathcal{S}$ there is a $\hat{\Theta} \in \mathcal{A}$ such that
$$
\lim_{t \rightarrow \infty} \hat{\Theta}(t)=\Theta\quad a.s.
$$

It should be underlined that the contents of this work are not immediately linked to our specific setting. Nevertheless, reading this article was meaningful, in the first part of our work, in order to define some characteristic features of our project. In particular, we realized that the main problem about our agents was their lack of homogeneousness. A camera can perform only tasks regarding its specific visual zone, or the whole net. This happens because both tasks and agents are ``localized'', i.e. each of them can affect only a subset of the comprehensive area. Actually, there are some ``global'' tasks, such as the \emph{heartbeat} broadcasting. However, this kind of tasks can be modelled as default net activities, that do not interfere with the out-and-out tasks, that are involved in our matching problem.
Another discrepancy between our context and the work proposed by Feiler, is that, in the latter, it is assumed that each agent knows the position of everyone else in the net exactly and without delays. This is a strong hypothesis; moreover, it is difficult to define a distance function in the case of such non-homogeneous agents. Finally, the number of agents in our case study is usually less than the number of tasks. In conclusion, despite of some proposed and implemented ad-hoc improvements, the approach of \cite{art:feiler} does not seem to be suitable to our model of camera networks, but gave us help to undestand the particular features of our project.
\item\textbf{Market-based approach} The basic idea of this approach is that it is possible to obtain a match between agents and tasks by means of auctions. In the simplest implementation of it, agents play the role of bidders. Depending on the specific context, many different implementations are available. For instance, these methods are frequently used in coordinating mobile vehicles in Search and Rescue missions. Some interesting works in this field are \cite{art:cdAuctions}, \cite{art:distributedTA} and \cite{art:distributedMRTA}. Another article that provides an exhaustive description of marked-based methods and their applications to task assignment (paying particular attention to mobile vehicles) is \cite{art:marketBased}. In contrast with other non-cooperative methods, market-based methods require that agents can communicate with each other, or at least with their neighbours (i.e. the agents that are interested in the same task and take part in the auction). In \cite{art:marketBased} different auction heuristics are analysed. The authors deal with the problem of defining adequate cost and utility functions for bidders (agents) and targets (tasks), in order to speed up the auctions.
% It is important to take into consideration the cost associated with each obtained pair (agent,task) and the cost of the auction in terms of required time and communication among agents.
Moreover, it is suggested the idea that, once a matching is found, it can be subsequently improved by swapping tasks between agents, during execution, without reiterating the expensive (in terms of synchronization and communication costs) auction procedure.
\item \textbf{Game theory based approach}. A point of view that is frequently adopted in mathematical project management is the one that looks to game-theoretical algorithms.  A typical situation can be the assignment of tasks to employees. An interesting scheme is proposed in \cite{art:Lagesse}. The key idea is to take into consideration the preferences of both managers and employees. The issue is formulated in order to resume a weighted multiple knapsack problem, in which tasks play the role of items, whose cost is required time for execution; each employee has an allotment of available time, that can be viewed as a knapsack to fill. The proposed strategy is the following:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
% \item Idea di partenza: algoritmo di Gale-Shapley (problema dei matrimoni stabili: si dice che il match è instabile se, date le coppie (m,w) ed (m',w'), m preferisce w' a  w e w' preferisce m ad m'), che tiene conto delle preferenze degli elementi di due insiemi, che vanno combinati. Problemi da risolvere: GS non assicura che tutti i task vengano assegnati.
\item Since this assignment problem is a \emph{stable marriage problem} (in order to collect information about SMP, we have referred, for instance, to \cite{art:smp} and \cite{art:smpVariants} ), it can be handled by means of a Gale-Shapley like algorithm \cite{art:gs}.
%\item Strategia: si assegnano pesi ai task (che rappresentano il tempo richiesto) ed uno slot temporale da riempire agli agenti; si introducono callbacks per verificare l'effetto del rifiuto dei task.
\item Each task is given a weight (that corresponds to the time it requires in order to be executed), a preference list and a pointer to the next non-rejected preference.  Each agent is equipped with a similar structure, that includes available time, a preference list, a pointer to the next non-rejected preference and a callback list.
%\item Ai task viene assegnata una struttura comprensiva di lista di preferenze, tempo richiesto, puntatore alla preferenza non rifiutata successiva; la struttura assegnata agli agenti comprende anch'essa una lista di preferenza ed il puntatore alla successiva preferenza non rifiutata. Ne fanno parte, inoltre, un indice del tempo disponibili ed una lista di callback.
\item The algorithm proceeds taking a task from the set of unattached tasks and recurring to the agent indicated by its pointer to the next non-rejected preference. If the agent is not busy or prefers this task to the one that it is currently performing, it accepts the task. If the replaced task can no longer be executed in the time left to the worker, it becomes unattached and establishes a callback. If the current task is not accepted, it moves to the next non-rejected preference. When an agent has completed its task, it can recall the highest of preferred tasks it has a callback for. The algorithm is iterated, until it ends when all tasks have been executed or rejected by all agents.

%\item L'algoritmo prevede che un task si rivolga al suo agente preferito, che se lo preferisce al task che sta eseguendo, lo sostituisce ad esso. Qualora l'agente non potesse più,per limite di tempo disponibile, eseguire il task precedente, questo si ``libera'' lanciando un callback, che altri agenti potrebbero risolvere in seguito. La procedura garantisce l'assenza di deadlock (grazie alle liste di precedenza, secondo gli autori) e la terminazione (task tutti processati -al massimo rifiutati da ogni agente)
\end{enumerate}
We have developed this approach in order to fit our case study problem. This is fairly more complex, since, even though our assumptions are very simple, it can be shown that we have to face a NP-hard assignment problem. This is due to the fact that charging non-homogeneous agents with localized task implies the presence of incomplete lists with ties (this issue will be developed in section (\ref{sec:SMP}).
\end{itemize}
% At last, \cite{art:pizzoccaro} helped us defining a mathematical formalisation of our problem, from the point of view of linear constraint programming.


%\subsection{A brief review of the proposed approach and main results}

\section{Contents of the following sections}
Here we report what the following sections will deal with.\\
In Section Two we describe task assignment problem more in detail and specify our assumptions. We also draw a mathematical formalisation of the problem: we show that a possible implementation is represented by a Constraint Linear Programming approach, even though our case study is quite difficult because our problem is dynamic.
We introduce some indexes to compare the different implemented approaches and evaluate their performances.
Then we make a digression about the Stable Marriage Problem and its variants, the topics that have mainly inspired our work.
Finally we go over the approaches we propose and we briefly describe them, highlighting their \emph{pros} and \emph{cons}, besides their computational complexities.\\
Section Three contains simulations. Firstly, we desribe the task simulator we have built in order to test our algorithms. Then, simulation results are analysed.\\
In Sections Four and Five, we conclude our project with some comments on attained results, comparisons among the proposed approaches and some opportunities for future works.

\section{Matching tasks and agents}
As we hinted in the previous sections, we are given a group of cameras distributed over an area to monitor. This area is divided into subzones owing to the intersection of the visual ranges of the cameras. \\

Each of them, that can be considered as an agent with limited resources, is able to cover a subset of all the possible subzones of the monitored area. As a consequence, it is possible to define a covering matrix $\mathbf{V}$.\\
In our treatment, we suppose that every subzone is covered by at least two cameras. The reason of this assumption is that we would like to assure continuity in monitoring each zone. In fact, if a zone were covered by a single agent and this agent were forced to perform streaming, since this task is not compatible with video-recording, surveillance would fail.\\
Our problem is to assign the tasks that occur to the agents, obeying to the previously introduced costraints, in order to attain a good match. The quality of the resulting match has to be defined in some ways: we will point out this issue in section (\ref{sec:proposedApproach}). \\
Each task is different from the others by some characteristics, i.e. its type (as explained in section (\ref{sec:desc})) and its location (or target agent).
We assume that when a task occurs, it is added to a structure called \emph{pool} and is removed from it when it is completed or gets obsolete. Actually, it is meaningful to define a dropping procedure that contrasts obsolescence: when a task exceeds a fixed lifetime, it is removed although not completed, unless it is already associated to an agent. This solution prevents the pool from an excessive growth. Moreover, a task that has not been executed after a certain fixed time, can be reasonably considered unprofitable, so it should be removed. \\
The \emph{pool} is thought to be a global structure, so all the agents are aware of the existing tasks at every instant and their characteristics. The agents can access to information about all the tasks. However, as we stated above, they cannot perform all of them, but only those ones that concern one of the subzones they cover.  \\
In our treatment, we disregard the aspects related to communication problems: no delays or losses of packets of information are possible and so agents have an instantaneous knowledge of the state of the net and the \emph{pool}.
For simplicity, we have simulated a task generation method that may be far from reality in some situations. This happens because tasks are created without correlation (i.e. a task of \emph{manual tracking} on a certain subzone can take place when an identical task is already existing). However, this is not an oversimplification, since it does not affect the pith of the resolving procedure.
%Dimostrare la robustezza dell'approccio ad un pool generato secondo ``natura''.
In conclusion, thanks to this abstraction, we have been able to turn a complex problem about camera network management into a simpler matter: the issue of matching tasks to agents.
\subsection{Mathematical formalisation}\label{sec:model}
The next step to take is to draw a mathematical formalisation of the assignment problem we are interested in.
A natural implementation is offered by a constraint linear programming (CLP) approach, that aims to build a model that resembles:

$$
\max \mathbf{c}^T(\mathbf{x})
$$
$$
\mathbf{A}\mathbf{x} \leq \mathbf{b}
$$
$$
\mathbf{x} \geq 0
$$

However, we have to face a dynamic problem. The number of task is not fixed: new ones can occur, increasing the length of the pool, whereas others can be completely performed or may be dropped, shortening it. This implies consequences that are not usually taken into consideration in linear programming. More in details, task dynamicity induces variations of the polyhedron containing decision variables. We are going to analyse this matter after describing the CLP model.

To begin with, the variables of the optimization problem have to be defined.

\begin{equation}\label{eq:var}
x_{ij} =
\begin{cases}
1 & \text{if agent $i$ executes task $j$} \\
0 & \text{otherwise}
\end{cases}
\end{equation}
where $i \in \left\lbrace1,\dots,N\right\rbrace$ and $j \in \left\lbrace1,\dots,H\right\rbrace$. The network has $N$ cameras and we are considering a pool of length $H$.

Under our assumptions on the skills of agents and the type of tasks, we can impose that assignment has to obey to the inequalities:

\begin{equation} \label{eq:ag}
 \sum _{j=1} ^H x_{ij} \leq 1 \quad \forall i
\end{equation}

\begin{equation}\label{eq:ta}
 \sum _{i=1} ^N x_{ij} \leq 1 \quad \forall j
\end{equation}

The meaning of (\ref{eq:ag}) is that each agent can execute at most one task, whereas (\ref{eq:ta}) implies that each task is assigned at most to one agent.

Our first model was thought in order to describe the constraints imposed by the covering matrix $\mathbf{V}$. This is a $N\times M$ matrix, where $M$ is the number of subzones (whereas $N$ is the number of agents, as we have already stated). Its elements are defined as:
\begin{equation}\label{eq:V}
 V(i,j)=
\begin{cases}
1 & \text{if agent $i$ covers area $j$} \\
0 & \text{otherwise}
\end{cases}
\end{equation}
The covering matrix $\mathbf{V}$ is supposed to be known exactly by the agents.
Moreover, w.l.o.g. it is possible to assume that each task is equipped with a structure containing information about it. In particular, it is possible to derive the area to which the task $j$ aims, by inspecting the structure field $task(j).loc$.
In order to model covering costraints, other variables had to be introduced:
$$
\bar{v}_{ij} =
\begin{cases}
0 & \text{if $i$ can monitor $task(j).loc$} \\
1 & \text{otherwise}
\end{cases}
$$
The additional costraint on covering was imposed by the equations:

\begin{equation}\label{eq:cop}
 \sum _{j=1}^H \bar{v}_{ij} x_{ij} = 0  \quad \forall i
\end{equation}

Finally, the problem involves integer values, such that:
\begin{equation}\label{eq:int}
x_{ij} \in \left\lbrace 0, 1\right\rbrace \forall i,j
\end{equation}

It should be noticed that equations (\ref{eq:cop}) make the problem more complicated. For instance, they prevent the constraint matrix $\mathbf{A}$ from being TUM (totally unimodular), in general. By a clever choice of the utility function, however, it is possible to skip out equations (\ref{eq:cop}).
For now, we postpone the question of defining an adequate (linear) utility function $f(\mathbf{x})$. There is only one assumption we are interested in now. It is that the function strongly penalizes ``wrong'' assignments. By ``wrong'', we mean that agents are given tasks that are incident to zones they can not monitor. The resulting model is given by constraints (\ref{eq:ag}), (\ref{eq:ta}), (\ref{eq:int}), aiming to find $\max f(\mathbf{x})$.
A key observation is that now the constraints matrix $\mathbf{A}$ is totally unimodular. Let $N$ be the number af agents and $H$ the length of the pool (number of existing tasks, both waiting or being performed). The expansion of the constraints (\ref{eq:ag}) results in:
\begin{gather*}
 x_{11} + x_{12} + \dots + x_{1H} \leq 1\\
 x_{21} + x_{22} + \dots + x_{2H} \leq 1\\
 \vdots\\
x_{N1} + x_{N2} + \dots + x_{NH} \leq 1
\end{gather*}
whereas constraints (\ref{eq:ta}) bring:
\begin{gather*}
x_{11} + x_{21} + \dots + x_{N1} \leq 1\\
x_{12} + x_{22} + \dots + x_{N2} \leq 1\\
\vdots\\
x_{1H} + x_{2H} + \dots + x_{NH} \leq 1
\end{gather*}

As a consequence (and ordering variables so that they appear as $x_{11}, \dots, x_{1H}, x_{21}, \dots,x_{2H}, \dots, x_{N1}, \dots, x_{NH} $),  it follows that the constraint matrix $\mathbf{A}$ has the form:
\begin{equation*}
\mathbf{A} =
  \begin{bmatrix}
  1 & \dots & 1 & 0 & \dots & 0 & 0 & \dots & 0\\
  0 &   0   & 0 & 1 & \dots & 1 & 0 & \dots & 0\\
  \vdots & \vdots & \cdots & \cdots & \cdots & \cdots & \vdots & \vdots & \vdots \\
  0 & 0& 0& \dots & \dots & 0& 1 & 1 &1\\
  1 &\dots& 0 & 1&\dots & 0 & 1 & \dots & 0\\
  0 &1& \dots & 0&1 & \dots & 0 & 1 & \vdots\\
  \vdots & \vdots & \cdots & \cdots & \cdots & \cdots & \vdots & \vdots & \vdots\\
  0 & \dots & 1 & 0 &\dots & 1 & 0 & \dots & 1
\end{bmatrix}
\end{equation*}
Since all elements are equal to 1 or 0 and each column contains exactly two non-null elements, $\mathbf{A}$ is TUM. As a consequence, conditions (\ref{eq:int}) are now redundant and the solving procedure is strongly simplified.

It is now interesting to focus on what we meant before when talking about dinamicity of the case study assignment problem.
This idea is linked to the fact that, after a match has been found, a new task can occur (increasing the pool) whereas others may be dropped or completed (so that they disappear from the pool). This influences the dimension of the polyhedron containing variables. In order to make the following tractation more intuitive, we can observe that it is possible to represent each combination of the values of $x_{ij}$ by a string of binary digits:
$$
x_{11}x_{12}\dots x_{1H}x_{21}\dots x_{2H}\dots x_{N1}\dots x_{NH}
$$
Disregarding the constraints (\ref{eq:ag}) and (\ref{eq:ta}), it can be easily seen that there are $2^{NH}$ different strings, where $N$ is the number of agents and $H$ is the current dimension of the task pool. For simplicity, $Z$ is defined to be the set of all possible strings.
Feasible strings with respect to the former constraints can be interpreted as a subset $X$ of $Z$. The cardinality of $X$ can be obtained by combinatorial calculus. It is given by
\begin{equation}\label{eq:comb}
|X| = \sum _{k=0}^N \binom{N}{k}\frac{H!}{(H-k)!}
\end{equation}
The $k^{th}$ addend corresponds to the number of solutions in which $k$ agents are busy.

A natural representation for the set $Z$ is possible in a $NH$ - dimensional space, where each string can be seen as a vertex of the unit NH-cube (i.e. the unit hypercube in $\mathbb{R}^{NH}$).

\subsubsection*{New task occurence}
Firstly, we analyse what the occurence of a new task implies. The main result is that $Z$ becomes $(HN+N)$-dimensional. Its cardinality is multiplied by $2^{N}$: an idea of how the polyhedron is affected by the new occurrence is given in figure (\ref{fig:poliedro}).
\begin{figure} [htb]
\centering
\includegraphics[scale = 0.7]{fig/poliedro}
\caption{Initial condition: two tasks and one agent. The corresponding polyhedron containing feasible solutions is the red triangle. The new occurence implies that $Z$ becomes a cube (before, it was the square given by the red vertices). The new polyhedron is coloured in blue.}
\label{fig:poliedro}
\end{figure}

The number of feasible values can be computed by means of equation (\ref{eq:comb}), by replacing $H$ with $H+1$.
All feasible combinations corresponding to $H$ tasks in the pool, keep feasibility when a new task occurs (they correspond to new assignments in which the new task is not chosen).
However, it is quite difficult to say what happens to the optimal solution.
For simplicity, we consider now that the utility function $f(\cdot)$ rewards only assignment that are consistent with the constraints imposed by the covering matrix $\mathbf{V}$. For instance, it could assign a positive value that depends on the task type. Of course, it has to penalise wrong assignment, as we have already assumed. It should also be underlined that the optimal solution could be not unique (there could be permutations of agents and tasks in the same zone, for instance).

It is possible that the occurence of a new task does not imply modification in the optimal solution (for instance, if all agents of the interested area are already performing more convenient tasks). However, the new occurence may cause that all (or nearly all) agents decide to change their tasks with a better one, now available. In fact, when a new task occurs, very different scenarios can tak place.


Let us consider a case in which a new occurence completely mix up the optimal solution.

\begin{example}
We refer to an early, very simple definition of the utility function $f(\mathbf{x})$ that obeys to our assumptions:
\begin{equation}
 f(\mathbf{x}) = \sum _{i,j} c_{ij}x_{ij}
\end{equation}

The gain $c_{ij}$, associated to the choice of assigning task $j$ to agent $i$ (i.e. putting $x_{ij} =1$), is given by:
\begin{equation}\label{eq:f}
c_{ij} =
\begin{cases}
pr(j) & \text{if $i$ can monitor $j.loc$} \\
-\infty & \text{otherwise}
\end{cases}
\end{equation}
Where  $j.loc$ is the area to which the task aims, whereas the value of $pr$ depends only on the type of task $j$. It can be chosen as:
\begin{equation}
pr(j) =
\begin{cases}
0.25 & \text{if $j.type$ is patroling} \\
0.5 & \text{if $j.type$ is streaming} \\
0.75 & \text{if $j.type$ is automatic tracking} \\
1 & \text{if $j.type$ is manual tracking}
\end{cases}
\end{equation}

We analyse a simple network configuration, characterized by the covering matrix
$$
V=
\begin{bmatrix}
 1 & 1 & 0 & 0 & 0 \\
 1 & 1 & 1 & 0 & 0 \\
 0 & 1 & 1 & 1 & 0 \\
 0 & 0 & 1 & 1 & 1 \\
 0 & 0 & 0 & 1 & 1
\end{bmatrix}
$$
We assume that $v_{ij} = 1 $ if agent $i$ can monitor area $j$.
As it can be easily seen in figure (\ref{fig:esempio}), a new occurence can bring to a new matching that is completely different from the previous one. \begin{flushright}$\Box$\end{flushright}
\begin{figure*}[ht]
 \centering
 \includegraphics[scale=0.7]{fig/esempio1.png}
 \caption{A new occurence can mix up the previous assignment}
 \label{fig:esempio}
\end{figure*}
\end{example}



% We can assume that each optimal solution implies that all agents are busy \footnote{In our case, this can be inferred from the fact that an agent that can not perform tracking or streaming should automatically change its state to patroling.}, it is not easy to understand how the new optimal solution is linked to the previous one.
% With regard to the utility function (\ref{eq:f}), under our assumptions we can assume that each optimal solution implies that all agents are busy.
We have modeled patroling activity as a task in order to achieve a better uniformity among tasks\footnote{Our approach creates an initial pool whose elements are patroling tasks, one for each area that has to be monitored. A sufficient condition to assure that patroling tasks are enough to keep all agents busy is that the covering matrix $\mathbf{V}$ contains a permutation of the columns of the identity matrix $I_N$}. With regard to the utility function (\ref{eq:f}), it is possible to say that, if patroling tasks are enough to keep all the agents busy, each optimal solution is characterized by the fact that all agents are busy.

\begin{proposition}\label{prop:1}
 If patroling tasks are enough to keep all agents busy, in each optimal solution all agents are busy.
\end{proposition}

\begin{IEEEproof}
 By absurd. Suppose that there is an optimal solution $s$ in which at least one agent $a$ is unloaded. Since patroling tasks are enough to keep all agents busy, if $a$ is unloaded it means that other agents have been matched to all the patroling tasks that could be executed by $a$. As a consequence, there is another solution $s'$ such that:
\begin{itemize}[\IEEEsetlabelwidth{a}]
 \item all other agents are performing the same kind of task they are assigned to in $s$.
 \item there is a permutation in the assignment of patroling task, so that $a$ can perform patroling, too.
\end{itemize}
 This permutation do exist since patroling tasks never change (once they have been create in the first execution) and they are sufficient to keep all agents busy. But $s'$ is characterized by a profit that is $f_{s'}(\mathbf{x}) = f_{s}(\mathbf{x}) +1$. So $s$ is not an optimal solution.
\end{IEEEproof}

Actually, an agent that can not perform tracking or streaming should automatically change its state to patroling, that should be considered a default state.

The occurence of a new task cause a drastical growth in the number of the possible matching in which all agents are busy.As a matter of fact, it becomes:
$$
\frac{(H+1)!}{(H+1-N)!} = \frac{H+1}{H+1-N}\frac{H!}{(H-N)!}
$$
An enumerative procedure would imply to compute the utility for the new potentially optimal solutions (in which all agents are busy and the new task is assigned). The number of new cases to be considered is:
$$
( \frac{H+1}{H+1-N} -1 )\frac{H!}{(H-N)!} =
$$
$$
 \frac{N}{H+1-N}\frac{H!}{(H-N)!}
$$
\subsubsection*{Dropped or completed task}
When the length of the pool is decrease by one, the dimension of $Z$ is reduced to $(H-1)N$. So, the number of possible strings in $Z$ becomes $2^{(H-1)N}$ (it is divided by $2^N$). This can happen in two cases.
\begin{enumerate}[\IEEEsetlabelwidth{a}]
 \item \textbf{A task is dropped}. If a task is dropped, it means that, during its whole life, other tasks were more advantageous. As a consequence, the vanishing of the dropped task does not affect the optimality of the current solution.
 \item \textbf{A task is completed}. If a task is completed, it means that an agent becomes unloaded. If the agents are capable to start patroling when no other tasks are available, of course optimality is lost. This happens because, under our assumptions, only streaming and tracking - both manual and automatic - tasks are subjected to dropping \footnote{Patroling tasks are supposed to have infinite service and dropping time, since they represent the default state of the net}. So, the agent that was previously busy was executing a task that was more convenient than patroling.
\end{enumerate}

In conclusion, it is difficult to understand how the change in the length of the pool affects the optimum solution. As a consequence, this formulation of the problem suggests two straightforward choices. The first one is to completely repeat the assignment procedure. This solution assures optimallity.
The second one is to implement a greedy heuristic. For instance, if a new task occurs, the agents that can monitor its area should evaluate it, allowing swaps if it is convenient but not affecting the assignment that has already been reached in other subzones.
If a task is completed, instead, the agent that has just carried it out should evaluate all the unmatched tasks it is able to perform. Of course, this kind of heuristic can not guarantee the optimality of the final solution. An example can show it clearly.

\begin{example}
 The situation is the one illustrated in figure (\ref{fig:esempio2}). The covering matrix is:
\begin{equation*}
V =
\begin{bmatrix}
1 & 1 & 0\\
0 & 1 & 1
\end{bmatrix}
\end{equation*}
The pool comprises the following tasks:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
 \item 'OP' on agent 1;
 \item 'STR' in area A1;
 \item 'TRK' in area A2;
 \item 'TRK' in area A3;
\end{enumerate}
The optimum solution is not unique; for istance, it can be the assignment in which the following pairs have been formed:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
 \item (a1,'OP' on agent 1)
 \item (a2,'TRK' in area 2)
\end{enumerate}
The other optimum solution is (a1,'OP' on agent 1) and (a2,'TRK' in area 3). Referring to the utility function described by (\ref{eq:f}), the optimum solutions are characterized by $f(\mathbf{X})=1.75$.
We consider the first one. What happens if the first task ('OP' on agent 1) is completed? Applying the previously described greedy heuristic, the assignment that involves agent 2 is never questioned. The best that agent 1 can do is to start executing task 'STR'. The final value of $f(\mathbf{x})$ is $1.25$. However, if the optimum assignment procedure had been repeated for both the agents, the solution would have been (a1, 'TRK' in A2) and (a2,'TRK' in A3), with $f(\mathbf{X})=1.5$.
\begin{figure*}[ht]
 \centering
 \includegraphics[scale=0.8]{fig/esempio2.png}
 \caption{Greedy heuristic vs optimum matching}
 \label{fig:esempio2}
\end{figure*}

\end{example}

\subsection{Performance metrics and constraints}\label{sec:performanceMetrics}
	Before introducing the analysis of the different proposed algorithms, it is fundamental to define some measurement criterion for the reached performances.
	The intrinsic complexity of the studied application, and in particular the necessity of working with dynamic assignments, imply heterogeneous and often contrasting goals.
	On one side, in fact, we look for an optimal assignment in the sense of priorities (i.e. it is preferable to execute critical tasks, instead to run the less important ones), on the other one we pursue a certain continuity in task's execution, avoiding situations in which tasks are temporary paused even if almost completed, or continuously swapped between different agents before the end of execution.
	Nevertheless we may want to avoid unaccomplished tasks queue growing too large, or infinite waiting time for tasks (also if those are low-priority tasks).
	Those and other aspects are formally presented in the following.

\subsubsection*{Qualitative constraints}
\begin{itemize}[\IEEEsetlabelwidth{a}]
	\item \textbf{Robustness.}
		Common requirement for every algorithm is the convergence to a stable assignment. In this paper randomized methods are also considered that may lead to continuously swapping configurations. In those cases iteration-breaking mechanisms are implemented to guarantee a finite time convergence.
	\item \textbf{Queue stability.}
		Another desirable goal is keeping a length-bounded pool (according with reasonable low generation rate of new tasks). This is in general strongly dependent on the particular instance of problem. To ensure the overall stability of the task pool, task dropping after a time-out period is necessary.
		As a side effect of such a policy, the oldest tasks, that are likely obsolete and no more critical, are cleaned from the queue.
\end{itemize}

\subsubsection*{Performance metrics}
\begin{itemize}[\IEEEsetlabelwidth{a}]
	\item \textbf{Optimality.}
		A measure of optimality (in the sense of task's type priority) is given by
		\begin{equation} \label{eq:bigP}
			P(t)=\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{p_n(\tau)}}
		\end{equation}
		where $p_n$ is the intrinsic priority of task executed by agent $n$ at the (discrete) time $\tau$ and $N$ is the number of agents in the system.
	\item \textbf{IDLE avoidance.}
		In a real implementation of the surveillance system, there are not agents doing properly \emph{nothing}: if a camera has nothing better to do it is always free to patrol its covered areas. IDLE state for an agent means to us that that agent found no compatible high-priority it can run and all the areas it covers are already patrolled by others. Such a situation reveals an unbalanced assignment configuration (as stated by proposition \ref{prop:1}).
		Let be the 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}
		where $\textup{Idle}_n(\tau)$ is 1 when the agent $n$ is IDLE at time $\tau$, 0 otherwise.
	\item \textbf{Complexity.}
		Algorithm's computational complexity (expressed in term of $O(\cdot)$) gives an estimation both of computational load per agent (i.e. necessary iteration to converge to a stable assignment) and scalability of the system (depending on number of agents $N$, areas $M$ and instantaneous size of the task pool $H(t)$).
	\item \textbf{Assignment (dis-)continuity.}
		This metric concerns how much agents tend to complete by themselves tasks they already started to execute. Let define
		\begin{equation} \label{eq:DiscontinuityRate}
			D(t)=\frac{1}{t}\sum_{\tau=0}^{t}{\sum_{n=1}^{N}{d_n(\tau)}}
		\end{equation}
		with $d_n(\tau)\in \{0,1\}$.
		Here $d_n(\tau)$ is 1 if agent $n$ has changed its running task for another one before completion, 0 otherwise~\footnote{If an agent has been running a patrolling task, $d_n(\tau)=1$ only if the new task type is still patrolling (obviously in a different area).}.\\
		$D(t)$ ($\in \mathopen{[}0,1\mathclose{]}$) represents in this way a ``mean discontinuity rate'' indication, that it is preferable to minimize.
	\item \textbf{Average waiting time.}
		The time every high-priority task spends waiting in queue strongly depends on new tasks arrival rate, but is symptomatic of system inefficiency, too. Let be the average waiting time
		\begin{equation} \label{eq:AverageWaitingTime}
			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}
		where $T_{\textup{end}}(h)$, $T_{\textup{occ}}(h)$, $T_{\textup{serv}}(h)$ are respectively time of completion, time of creation and pure execution time of task $h$ in the set of completed tasks $\mathcal{H}_C$.
	\item \textbf{Dropping rate.}
		A well tuned time-out parameter allows to keep the queue size bounded. Nevertheless setting this variable on small values involves the risk of dropping large numbers of tasks, more than necessary. The dropping rate is defined as
		\begin{equation} \label{eq:DroppingRate}
			F=\frac{|\mathcal{H}_\textup{drop}|}{|\mathcal{H}|}
		\end{equation}
		with $\mathcal{H}_\textup{drop}$ the set of dropped tasks and $\mathcal{H}$ the set of all high-priority tasks.
\end{itemize}

\subsubsection*{Instance parameters}
Another interesting goal is value instance size both of the system ($N,M,\mathbf{V}$) and the task occurrence.
Since the behaviour of the assignment is strongly dependent on the particular realization, we may ask if, under certain hypothesis, it is possible to conclude on intrinsic feasibility of a good resulting assignment.
In order to keep a simple structure of the problem, let assume that task arrival process is a Poisson process, i.e. task generations are independent and memoryless. In addition, the concerning areas of tasks, their \emph{localizations}, are supposed uniformly distributed over all $M$ areas.
Let define for each kind of task
\begin{itemize}[\IEEEsetlabelwidth{a}]
	\item $\overline{T}_\textup{occ}^{(\cdot)}$ as the average interarrival time. This is the mean interval between the generation of consecutive tasks \emph{of the same type}.
	\item $\overline{T}_\textup{serv}^{(\cdot)}$ as the average service time of a task, in other words the mean time such a task need to spend in execution before being considered completed.
\end{itemize}
Considering the previously introduced typology of task, there will be, in general, different values of
$\overline{T}_\textup{occ}^\textup{OP}$,
$\overline{T}_\textup{occ}^\textup{TRK}$,
$\overline{T}_\textup{occ}^\textup{STR}$ and
$\overline{T}_\textup{serv}^\textup{OP}$,
$\overline{T}_\textup{serv}^\textup{TRK}$,
$\overline{T}_\textup{serv}^\textup{STR}$.
Patrolling tasks are particular cases as these are not properly said tasks, however. Nevertheless, to maintain a certain consistence and homogeneousness, consider patrolling job as a set of tasks (one for each area $m\in\{1 \ldots M)$) generated at the initial time ($t=0$) and never completable, hence $\overline{T}_\textup{serv}^\textup{PAT}=\infty$.
The system size is represented, quantitatively, by
\begin{itemize}[\IEEEsetlabelwidth{a}]
	\item Number of total agents $N$.
	\item Number of total areas $M$.
	\item The covering matrix $\textbf{V}$ as defined in equation (\ref{eq:V}) and more specifically, the mean covered area per agent
		\begin{equation}
			\overline{v}_\textup{agent} = \frac{1}{N}\sum_{\forall (n,m)}{v_{nm}}
		\end{equation}
		and the mean agent covering an area
		\begin{equation}
			\overline{v}_\textup{area} = \frac{1}{M}\sum_{\forall (n,m)}{v_{nm}}.
		\end{equation}
		A suppletory condition is that each agent is able to cover at least two different areas and each area is covered at least by two agents~\footnote{This to avoid  overdetermined solutions.}.
\end{itemize}
Next step is computing a load factor that takes into account all of the variable listed above. Let be
\begin{align}
	c_\textup{op}&= \overline{T}_\textup{serv}^\textup{OP}/
		\overline{T}_\textup{occ}^\textup{OP} \notag \\
	c_\textup{trk}&= \overline{T}_\textup{serv}^\textup{TRK}/
		\overline{T}_\textup{occ}^\textup{TRK}\\
	c_\textup{str}&= \overline{T}_\textup{serv}^\textup{STR}/
		\overline{T}_\textup{occ}^\textup{STR} \notag
\end{align}
the single load of different tasks.
Since each operator task is compatible with only one agent and tracking and streaming tasks are feasible by all agents covering relative area, we may conclude that:
\begin{itemize}[\IEEEsetlabelwidth{a}]
	\item OP tasks are equally distributed on the $N$ agents;
	\item TRK and STR tasks are equally distributed on the areas and executed by the agents according to the topology.
\end{itemize}
So
\begin{equation}
	C = \frac{1}{N} c_\textup{OP} +
		\frac{\overline{v}_\textup{agent}}{M\cdot \overline{v}_\textup{area}}
		\left( c_\textup{trk} + c_\textup{str} \right)
%\overline{v}_\textup{area}
\end{equation}
is taken as a global load factor.
When $C>1$ the incoming rate of new tasks is faster than the completion rate, hence, even ignoring limitation represented by the covering matrix $\mathbf{V}$, the system won't be able to satisfy all tasks.

\subsection{Proposed approach}\label{sec:proposedApproach}
\subsubsection{The stable matching problem }\label{sec:SMP}
Our work was mainly inspired by the \emph{stable marriage problem} \cite{art:gs}.\\
It considers a set of $n$ men and $n$ women.
Each person has a list (ordered by his preference), where all the persons of the opposite sex appear.\\
We have to find a set of stable marriages between the men and the women.\\
A marriage is said to be stable if there are no dissatisfied pairs, that is there is no pair of a man and a woman who both prefer another partner to their current one (according to their preference lists).\\
The algorithm proposed in \cite{art:smp} is the following: an unpaired man $X$ considers the first woman on his list and removes her from it. If the woman is not engaged, she accepts his proposal, otherwise she considers her preference list: if she prefers $X$ to  her current partner, she breaks it with her mate (who gets unpaired) and marries $X$, otherwise $X$ is still unpaired because the woman is happier with her husband.
These operations are repeated while there are men unpaired (see also alorithm \ref{alg:gs}).\\
In this way, once a woman becomes attached, she remains married, altough she can change her partner (if she receives a better marriage proposal). As a man eliminates one woman from his list during every iteration, if the rounds continue long enough, all men and women will be married and it is assured the termination of the algorithm. This marriage is shown to be stable: let us assume we have a dissatisfied pair, i.e. a man \emph{X} that prefers a woman \emph{b}, to his current wife \emph{a}. This implies that \emph{X} must have proposed to \emph{b} before \emph{a}. Woman \emph{b} either rejected him or, at first, she accepted him but then refused him for another better man. So, \emph{b} must prefer her current husband to \emph{X}, contradicting the initial assumption that \emph{b} id dissatisfied: so the marriage is stable.
\begin{algorithm}
\caption{Gale-Shapley Algorithm}
\label{alg:gs}
\begin{algorithmic}[1]
\WHILE{there is an unpaired man}
\STATE pick an unpaired man \emph{X}
\STATE remove the first woman \emph{w} from his list
\IF{\emph{w} is engaged}
\IF{\emph{w} prefers \emph{X} \\ to her current partner \emph{Y}}
\STATE set $(X,w)$ as paired
\STATE set $(Y,w)$ as unpaired
\ELSE
\STATE \emph{X} is still unpaired %(\emph{w}is happier with \emph{Y})
\ENDIF
\ELSE
\STATE set $(X,w)$ as paired
\ENDIF
\ENDWHILE
\end{algorithmic}
\end{algorithm}

This algorithm was modified by Brent Lagesse that in \cite{art:Lagesse} faces the problem of the assignment of tasks to employees, taking into consideration manager and employees preference, employee time and employee skills. A new more specific approach was proposed, which utilises two-sided matching: each task is given a weight, that is the estimated time required to complete the task; each employee has an allotment of time available to fill with tasks. The algorithm is the one described in section \ref{sec:litSurvey}.
This algorithm terminates when all tasks have been assigned or they have been rejected by all workers. Termination is assured since the preference lists mean that are no deadlock.\\
In video-surveillance case study, cameras (agents) and tasks play the role of duties and employees. \\
Nevertheless, a direct application of this algorithm to our case study problem was not possible, because it is more complex owing to dinamicity and the characteristics of tasks and agents.
So we have studied some variants of the \emph{stable marriage problem} (referring to \cite{art:smpVariants}, in particular):
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item \textbf{Stable marriage problem with incomplete lists (SMI)}. This is the case when the involved preference lists can be incomplete: the number of men and women does not have to be the same and each person's preference list consists of a subset of the members of the opposite sex in strict order. Now, a matching $M$ is a one-one correspondance between a subset of men and a subset of women, where each member of a pair is acceptable to the other one, that is each one appears in the preference list of the other one. \\
$M$ is said to be a stable marriage if there is no acceptable pair $(m,w)$, such that $m$ and $w$ are either both unmatched in $M$ or prefer the other to his/her partner in $M$. \\
As in the classical case, there is always at least one stable matching for an instance of the \emph{stable marriage problem with incomplete lists}, that can be found in a polinomial time. %EX LINEAR
\item \textbf{Stable marriage problem with ties (SMT)}. This extension of the \emph{stable matching problem} arises when lists contain \emph{ties}. In this case, a person, we say a man, prefers each woman of a tie to all the women belonging to every subsequent tie and is indifferent among the women of a single tie. \\
A matching $M$ is (weakly) stable if there is no pair of $m$ and $w$, each of whom prefers the other to his/her partner. For an instance of this problem, a weakly stable matching is bound to exist, and can be found in polinomial time by breaking all ties in an arbitrary way.
\item \textbf{Stable marriage problem with ties and incomplete lists (SMTI)}. This variant is obtained combining both extensions described above.\\
 In this context, a matching $M$ is stable if there is no pair of $m$ and $w$, each of whom is either unmatched in $M$ and finds the other acceptable or strictly prefers the other to his/her partner in $M$. A stable matching can be found by breaking all the ties, but the ways in which ties are broken affect the solution. Finding a solution of maximum cardinality is a NP-hard problem. \\
\end{itemize}


In the end we have chosen an algorithm that draws on from these concepts and tries to avoid some problems related to the NP-hard complexity of the problem. It will be described in the following section.

% In the end we have chosen the algorithm that works as follows (algorithm \ref{alg:ts}).
% Each task has a fixed preference list, that is created once and for all at the moment of the creation of the task; it contains all the agents that can execute that task (according to the covering matrix, as explained in the previous sections).\\
% Each agent draws up a preference list, that contains the tasks it can execute, ordered by a criterion that keeps into account the lifetimes of tasks and their priorities (see the algorithm \ref{alg:cs} for details); ties and incomplete lists are possible. \\
% So an agent, chosen at random, builds temporary lists, containing only tasks with the same scores as defined in its entire list.
% The temporary lists are scrolled, beginning from those containing tasks with the highest scores (in descending order). \\
% Three situations are possible:
% \begin{enumerate}[\IEEEsetlabelwidth{a}]
% \item  the current agent is executing a task of the temporary list it is considering: in this case, no change takes place and the algorithm switches to the next agent;
% \item  some tasks belonging to the current temporary list are unassigned: in this case, the current agent takes the first of these tasks (and if it was executing a task, this gets unmatched) and the algorithm switches to the next agent;
% \item all the tasks belonging to the current temporary list are assigned. A swap can occur in two situations:
% \begin{enumerate}[\IEEEsetlabelwidth{a}]
% \item the current task in the temporary list appears in a lower position in the list of the current agent $A$ than in the list of the agent $B$ that is executing it. In fact, if $A$ did not take this task, its list would risk to be empty and so $A$ to get IDLE.
% \item the current task in the temporary list appears in the same position of both agents' lists and the current agent can execute a lower number of tasks; that is because we can think that an agent that can perform few tasks will be subject to a lower number of requests from them.
% \end{enumerate}
% If a swap does not take place, the algorithm considers the following task in the temporary list, otherwise it switches to the next agent.
% \end{enumerate}
% These operations are repeated until a stable matching is attained.\\
%
%
% \begin{algorithm}
% \caption{Compute Score}
% \label{alg:cs}
% \begin{algorithmic}[1]
% \STATE \textbf{function} $score$ = computeScore($task$)
% \STATE score = $\alpha * (task\; priority) + (1-\alpha) * (task \;lifetime)/(task\; drop\; time)$;
% \end{algorithmic}
% \end{algorithm}
%
%
% \onecolumn
%
% \begin{algorithm}
%  \caption{Task Selection}
%  \label{alg:ts}
%  \begin{algorithmic}[1]
% \STATE \textbf{function} taskSelection
%   \STATE global \emph{X \, pool} \;\;
%    \emph{\small{\%} $\!$ structures containing agents and existing tasks respectively};
%
% \FOR{each agent}
%  \STATE compute scores of tasks that are compatible with the current agent (using function \emph{computeScore} in algorithm \ref{alg:cs});
%  \STATE build a list containing tasks that are compatible with the current agent, placed by a score decreasing order;
% \ENDFOR
%
%
% \WHILE{(matching is unstable)}
%  \STATE $A \leftarrow$ vector containing all the agents placed with a random order;
%  \FOR{$n \in A$}
%   \STATE build temporary lists for $X(n)$ containing only its compatible tasks with the same scores, beginning from those with the highest scores;
%   \LOOP
%    \STATE consider the current temporary list of $X(n)$ ($tempList$);
%     \IF{$X(n)$ is executing a task that appears in $tempList$}
%      \STATE break: switches to another agent;
%     \ENDIF
%     \IF{no assignment has just taken place}
%      \IF{a task in $tempList$ is unassigned}
%       \STATE $t \leftarrow$ first unassigned task in $tempList$;
%       \STATE set $(X(n),t)$ as paired;
%       \STATE break: switches to another agent;
%       \ELSE
%       \STATE consider the following temporary list;
%      \ENDIF
%     \ENDIF
%     \IF{no assignment has just taken place}
%      \IF{all tasks in $tempList$ are assigned}
%      \STATE $ft \leftarrow$ first task in $tempList$;
%      \WHILE{no swap takes place}
%       \STATE $t \leftarrow$ current task $tempList$;
%       \STATE posTn = position of $t$ in $X(n).list$;
%       \STATE posTcurr = position of $t$ in the list of the agent is                      executing it;
%       \IF{($posTn \prec posTcurr$) OR
%          ($posTn = posTcurr$ $\;$ \small{\&\&} \\ $X(n)$ can execute a               lower number of tasks)
%          }
%        \STATE set $(X(n),t)$ as paired;
%        \STATE break: switches to another agent;
%        \ELSE
%        \STATE consider the following temporary list;
%       \ENDIF
%       \ENDWHILE
%      \ENDIF
%     \ENDIF
%   \ENDLOOP
%   \ENDFOR
%  \ENDWHILE
% \end{algorithmic}
% \end{algorithm}
%
%  % \FOR{$n = 1:length(X)$}
% %   \STATE clean $X(n).list$ and $X(n).score$;
% %   \FOR{$h = 1:length(pool)$}
% %    \IF{$n\in pool(h).list$}
% %     \STATE $X(n).list(end+1) = pool(h).ID$;
% %     \STATE $X(n).score(end+1) = computeScore(pool(h))$ $\;\;$ \emph{\small{\%} $\!$ see algorithm \ref{alg:cs}};
% %    \ENDIF
% %   \ENDFOR
% %   \STATE sort $X(n).list$,$\:$$X(n).score$,$\:$$X(n).index$ according to the scores (in descending order);
% %  \ENDFOR
% %  \WHILE{(matching is unstable)}
% %   \FOR{$n \in randperm(length(X))$}
% %    \STATE assignmentDone = false;
% %    \FOR{each (not repeated) value of scores chosen in an descending order}
% %     \STATE create temporary lists ($tempList$) containing only tasks with the same scores;
% %      \IF{$n$ is executing a task in $tempList$}
% %       \STATE assignmentDone = true;
% %      \ENDIF
% %      \IF{~assignmentDone}
% %       \FOR{$h \in tempList$}
% %        \IF{$h$ is not assigned}
% %         \STATE matching $(h,n)$;
% %         \STATE assignmentDone = true; break;
% %         %\STATE break;
% %        \ENDIF
% %       \ENDFOR
% %      \ENDIF
% %      \IF{~assignmentDone}
% %       \FOR{$h \in tempList$}
% %        \STATE $T$ = $n$'s preferred task;
% %        \STATE posTn = position of $T$ in $X(n).list$;
% %        \STATE posTcurr = position of $T$ in the list of the agent is executing $h$;
% %        \IF{($posTn \prec posTcurr$) OR
% %        ($posTn == posTcurr$ $\;$ \small{\&\&} \\ $length(X(n).list)\,<\,length(list\; of\; the\; opposing\; agent))$
% %        }
% %         \STATE assignmentDone = true; break;
% %         %\STATE break;
% %        \ENDIF
% %       \ENDFOR
% %      \ENDIF
% %      \IF{assignmentDone}
% %       \STATE break;
% %      \ENDIF
% %    \ENDFOR
% %   \ENDFOR
% %  \ENDWHILE
% % \end{algorithmic}
% %\end{algorithm}
%
%
% \twocolumn

\subsection{Proposed Algorithms}
We have developed two algorithms, that are based on the Stable Marriage Problem. In order to evaluate their performances, we are going to compare them with other task assignment procedures. Some of them have been already introduced, the others will be explained subsequently. The algorithms that are going to be studied are the following.
\begin{itemize}[\IEEEsetlabelwidth{a}]
 \item Centralized assignment.
 \item Nearly Brute-force (Purely random assignment).
 \item Greedy assignment.
 \item SMTI Revised.
 \item Randomized SMTI Revised.
\end{itemize}

They have been implemented and simulated using Mathworks \textsc{Matlab}\texttrademark. Before we show the results of these simulation, it is meaningful to premise a brief description and some considerations about them.

\subsubsection*{Centralized assignment}
This algorithm follows directly from the formulation of the problem given in subsection (\ref{sec:model}). It aims at founding the best solution with regard to the maximization of a utility function similar to (\ref{eq:f}).
Actually, it has been improved in order to weigh the life span of tasks. The resulting function is:
\begin{equation*}\label{eq:fDef}
 f(\mathbf{x}) = \sum_{i,j} c_{ij}x_{ij}\\
\end{equation*}
where
\begin{equation}\label{eq:fABC}
c_{ij} =
\begin{cases}
%\frac{\beta}{ag(j)}
\alpha pr(j)+ (\gamma) \frac{T_{lftm}(j)}{T_{drop}(j)} &\textit{ if $j.loc\in i.v$}\\
-\infty & \textit{otherwise}
\end{cases}
\end{equation}
We say that $j.loc\in i.v$ if agent $i$ can monitor the area affected by task $j$.
% $ag(j)$ is the number of agents that can execute task $j$ (this is decided univocally on the basis of the covering matrix $\mathbf{V}$, once the task has occurred)
The term $pr(j)$ is the priority associated to the type of the task, $T_{lftm}(j)$ is the duration of the life of task $j$ and $T_{drop}$ is the fixed time after that task $j$ is dropped.
The choice of this kind of function has been motivated by some considerations about the features we would like to attain.
The former addend weighs the role of the intrinsic priority of the task, whereas the latter one assigns higher priority to tasks whose life span is close to drop time (they might be dropped soon, if no agent carry them out).
It should be pointed out that $\alpha$ and $\gamma$ are positive or null, such that $\alpha + \gamma =1$~\footnote{Since we are interested in comparing the role of priority and life span, $\alpha$ and $\gamma$ are chosen to provide a convex linear combination of them}.
%$\beta$ and $\gamma$ are chosen to provide a convex linear combination of the three addends (so they are positive or null and their sum is 1).
%The second one has been inserted to force the algorithm to assign earlier a task that can be executed by a smaller number of agents, since it has a bigger probabilty to remain unmatched.

Since the problem can be reduced in each time interval in a CLP issue without integer conditions, we can solve it simply by means of the simplex algorithm, for instance~\footnote{We have chosen Simplex algorithm as a solving procedure in our code implementation}.

Let us analyse the features of this algorithm.
\begin{itemize}[\IEEEsetlabelwidth{a}]
 \item \textbf{Pros:} The assignment is optimum with regard to the function (\ref{eq:fABC}).\\ It assures the absence of deadlock: it is sufficient to make it obey to the Bland law (which prevents cyclic degeneration of simplex, by fixing the order of choice of the variables to be taken as basis, when there are doubtful situations).
 \item \textbf{Cons:} The worst case is characterized by the complexity $\binom{n}{k}$ where $n$ is the number of variables and $k$ is the number of constraints (in particular, in the case study problem we have $n = NH$ and $k=N+H$. In the worst case, it means that the number of possible iterations is: $$\frac{(NH)!}{(N+H)!(NH-(N+H))!}$$
Moreover, it cannot be implemented in a distributed version.

\end{itemize}
\begin{figure}
 \begin{center}
  \includegraphics[scale=0.7]{fig/idlePRA}
  \caption{With Nearly Brute-force agents can be IDLE. An example is given by the case in which there are only patroling tasks, one per area, and agent $a_i$ can patrol areas $i$ and $(i+1)$ $mod$ $4$. A possible result of random assignment in this situation lets agent $a_3$ unloaded.}
 \label{fig:idlePRA}
 \end{center}

\end{figure}

 \subsubsection*{Nearly Brute-force (Purely random assignment)}
This is the simplest assigment procedure that can be implemented. Each agent $a_i$, with $i \in \left\lbrace 1, \dots, N\right\rbrace$, performs the sequence of operations that is described by the flow chart in figure (\ref{fig:PRA}).

% FLOW CHART DA FARE GRAFICAMENTE
% \begin{itemize}[\IEEEsetlabelwidth{a}]
%  \item $a$ is free $\Rightarrow $ 1.$a$ randomly chooses one task from the free tasks that it can perform; 2. If there are no tasks other than patroling, $a$ starts executing patroling.
% \item $a$ is busy $\Rightarrow $ 1.$a$ is executing patroling:  it looks for another kind of tasks among the free ones. 2. $a$ is performing a task that is different from patroling: it keeps on performing it.
% \end{itemize}

% Define block styles
\tikzstyle{decision} = [diamond, draw, fill=red!20,
    text width=5em, text badly centered, node distance=3cm, inner sep=0pt]
\tikzstyle{block} = [rectangle, draw, fill=blue!20,
    text width=5em, text centered, rounded corners, minimum height=4em]
\tikzstyle{line} = [draw, -latex']
\tikzstyle{cloud} = [draw, ellipse,fill=blue!20, node distance=3cm,
    minimum height=2em]

% Define block styles
\tikzstyle{decision} = [diamond, draw, fill=red!20,
    text width=5em, text badly centered, node distance=3cm, inner sep=0pt]
\tikzstyle{block} = [rectangle, draw, fill=blue!20,
    text width=5em, text centered, rounded corners, minimum height=4em]
\tikzstyle{line} = [draw, -latex']
\tikzstyle{cloud} = [draw, ellipse,fill=blue!20, node distance=3cm,
    minimum height=2em]

\begin{figure}
\begin{center}
\begin{tikzpicture}[node distance = 3cm, auto]
    % Place nodes
    \node [cloud] (start) {Start};
    \node [decision, below of=start, node distance=2.4cm] (isFree) {is $a_i$ unloaded?};
    \node [decision, below of=isFree, node distance=4cm] (isPat) {is $a_i$ patroling?};
    \node [block, right of=isPat,node distance=4cm] (randomMatch){$a_i$ randomly picks an available unmatched task (different from patroling, if it exists)};
    \node [block, below of=isPat,node distance=3cm] (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}
  \caption{Nearly Brute-force}
  \label{fig:PRA}
 \end{center}
\end{figure}

This algorithm is very similar to the procedure that is presently put in practise (it resembles the \emph{brute-force} approach we have described in section (\ref{sec:litSurvey}), under our assumptions on the pool structure).
Let us analyse the features of the Nearly Brute-force algorithm.

Its computational complexity in the worst case is $O(NH)$, where $N$ is the number of agents and $H$ is the pool length. This is due to the fact that an agent can look through the whole length of the pool before finding a task it can perform. This can be easily understood referring to our implementation. Patroling is considered a task like the others and we initialize the pool inserting a task of patroling for each subzone to be monitored. Since these tasks cannot be brought to a close (since they have infinite service time), they never leave the pool. Other tasks queue up. The structure of the resulting pool is shown in figure (\ref{fig:pool}).

\begin{figure*}
	\centering
	\includegraphics[scale = 0.7]{fig/pool}
	\caption{Example of the pool structure}
	\label{fig:pool}
\end{figure*}

The number of zones to be monitored is given by $M$ and the total number of existing tasks is given by $H$. If we suppose that an agents randomly chooses tasks that are different from patroling, if there are any, the worst case occurs when an agent does not find any suitable tasks of this type and has to glance through all the tasks before considering the patroling ones (so it takes into consideration at first $(H-M)$ tasks, then at most all $M$ patroling tasks - actually, if we suppose that an agent covers more than one zone, it has to consider less than M tasks before finding a patroling task that is suitable for it).

\begin{itemize}[\IEEEsetlabelwidth{a}]
 \item \textbf{Pros}: It assures maximum continuity in matching tasks and agents. An agent cannot drop the task that it has chosen, apart from the patroling tasks (that are to be considered as an astraction of the default state of the cameras).\\ This approach easily allows scaling, since it does not request communications among the agents (except for the synchronization of global information regarding the pool, eventually). Of course, the scaling cost depends on the dimension of the pool.\\
%ALTRO SULLO SCALING?
 Deadlocks could occur only if two or more agent asked for the same task simultaneously. However, this situation can be easily avoided. On the one hand, in the centralized implementation agents are considered sequentially; on the other one, it is sufficient to recur to a \emph{leader} agent to solve conflicts. For instance, this hierarchically higher agent can settle differences by operating a random choice.
 \item \textbf{Cons}: No optimality criterion directs the assignment, that is completely random.\\There could be IDLE agents (under the assumption that patroling is a task like the others and not the default state of each agent). An example is exhibited in figure (\ref{fig:idlePRA}).
\end{itemize}
% \begin{figure}
%  \begin{center}
%   \includegraphics[scale=0.7]{fig/idlePRA}
%   \caption{With Nearly Brute-force agents can be IDLE. An example is given by the case in which there are only patroling tasks, one per area, and agent $a_i$ can patrol areas $i$ and $(i+1)$ $mod$ $4$. A possible result of random assignment in this situation lets agent $a_3$ unloaded.}
%  \label{fig:idlePRA}
%  \end{center}
%
% \end{figure}

 \subsubsection*{ Greedy assignment}
This algorithm is quite similar to the previous one, except for the fact that assignment is not chosen randomly. Each agent evaluates all the tasks, than it chooses the best one (of course, it has to be a task that aims to a zone covered by the agent). The profit associated to a task can be established by means of the function (\ref{eq:fABC}).
The sequence of operations performed by each agent are shown in flow chart (\ref{fig:greedyA})

\begin{figure}
\begin{center}
\begin{tikzpicture}[node distance = 3cm, auto]
    % Place nodes
    \node [cloud] (start) {Start};
    \node [block, below of=start, node distance=2.4cm] (pool) {$a_i$ look through the pool for the best unmatched task $t_{best}$};
    \node [decision, below of=pool, node distance=4cm] (isBetter) {is $t_{best}$ better than $t_{curr}$?};
    \node [block, right of=isBetter,node distance=4cm] (newMatch){$a_i$ drops $t_{curr}$ and start executing $t_{best}$};
    \node [block, below of=isBetter,node distance=3cm] (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}
  \caption{Greedy Assignment. The task that is currently performed by $a_i$ is indicated by $t_{curr}$.}
  \label{fig:greedyA}
 \end{center}
\end{figure}

The computational complexity of this algorithm is always $O(NH)$, since each agents need to glance through the whole pool to evaluate the tasks.

\begin{itemize} [\IEEEsetlabelwidth{a}]
 \item \textbf{Pros}: This algorithm, as the previous one, easily allows scaling, since the cost of communication is low and each agent behaves almost regerdless of other agents' choices. Conflicts can be solved, as we have already stated, by means of a \emph{leader} agent, so deadlocks are prevented.
 \item \textbf{Cons}: Continuity is not assured. A task may be dropped by an agent before it comes to the end, since the agent may find a better task to perform.\\As in the previous case, there can be IDLE agents, even if the optimal assignment would match all the agents with a task.
\end{itemize}

%  \subsubsection*{ Task selection}
% \begin{figure*}
%  \begin{center}
%    \subfloat[][\emph{Non optimal assignament with TS}]
%  {\includegraphics[scale=.5]{fig/critTS2a}}\quad
%  \subfloat[][\emph{Optimal assignament with TS}]
%  {\includegraphics[scale = .5]{fig/critTS2b}}
%  \end{center}
%
% \end{figure*}
%
%  \subsubsection*{ Randomized Task selection}
% %ESEMPIO GRAFICO CASO IN CUI PUÒ ESSERE UTILE (IL CELEBRE ESEMPIO DEL GRANDE GROSSO TASK CONTESO)
% %NE' INFAMIA NE' LODE
% \begin{figure*}
%  \begin{center}
%    \subfloat[][\emph{Non optimal assignament with TS}]
%  {\includegraphics[scale=.5]{fig/critTSa}}\quad
%  \subfloat[][\emph{Optimal assignament with TS}]
%  {\includegraphics[scale = .5]{fig/critTSb}}
%  \end{center}
%
% \end{figure*}

\subsection*{Our algorithm: SMTI Revised (a.k.a. The Wedding Planner algorithm)}
The algorithm we have implemented to solve our task assignment problem is the following (see also algorithm \ref{alg:ts}).\\
Each task has a fixed preference list, that is created once and for all at the moment of the creation of the task; it contains all the agents that can execute that task (according to the covering matrix, as explained in the previous sections).\\
Each agent draws up a preference list, that contains the tasks it can execute, ordered by a criterion that keeps into account the lifetimes of tasks and their priorities (see the algorithm \ref{alg:cs} for details); ties and incomplete lists are possible. \\
So an agent, chosen at random, builds temporary lists, containing only tasks with the same scores as defined in its entire list.
The temporary lists are scrolled, beginning from those containing tasks with the highest scores (in descending order). \\
Three situations are possible:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
\item  the current agent is executing a task of the temporary list it is considering: in this case, no change takes place and the algorithm switches to the next agent;
\item  some tasks belonging to the current temporary list are unassigned: in this case, the current agent takes the first of these tasks (and if it was executing a task, this gets unmatched) and the algorithm switches to the next agent;
\item all the tasks belonging to the current temporary list are assigned. A swap can occur in two situations:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
\item the current task in the temporary list appears in a lower position in the list of the current agent $A$ than in the list of the agent $B$ that is executing it. In fact, if $A$ did not take this task, its list would risk to be empty and so $A$ to get IDLE.
\item the current task in the temporary list appears in the same position of both agents' lists and the current agent can execute a lower number of tasks; that is because we can think that an agent that can perform few tasks will be subject to a lower number of requests from them.
\end{enumerate}
If a swap does not take place, the agent goes on in considering the following tasks in the temporary list, then the lower placed items in its global preference list. If the end is reached without a match, the algorithm switches to the next agent
% If a swap does not take place, the algorithm considers the following task in the temporary list, otherwise it switches to the next agent.
%If a swap does not take place, the algorithm considers the following task in the temporary list, otherwise it switches to the lower score tasks, until the end of the entire preference list, if no matching is found for the agent.

\end{enumerate}
These operations are repeated until a stable matching is attained.\\


\begin{algorithm}
\caption{Compute Score}
\label{alg:cs}
\begin{algorithmic}[1]
\STATE \textbf{function} $score$ = computeScore($task$)
\STATE $score \leftarrow \alpha * (task\; priority) +$\\$ (1-\alpha) * (task \;lifetime)/(task\; drop\; time)$;
\end{algorithmic}
\end{algorithm}


\onecolumn

\begin{algorithm}
 \caption{ SMTI Revised}
 \label{alg:ts}
 \begin{algorithmic}[1]
\STATE \textbf{function} SMTI Revised
  \STATE global \emph{X \, pool} \;\;
   \emph{\small{\%} $\!$ structures containing agents and existing tasks respectively};

\FOR{each agent}
 \STATE compute scores of tasks that are compatible with the current agent (using function \emph{computeScore} in algorithm \ref{alg:cs});
 \STATE build a list containing tasks that are compatible with the current agent, placed by a score decreasing order;
\ENDFOR


\WHILE{(matching is unstable)}
 \STATE $A \leftarrow$ vector containing all the agents placed with a random order;
 \FOR{$n \in A$}
  \STATE build temporary lists for $X(n)$ containing only its compatible tasks with the same scores, beginning from those with the highest scores;
  \LOOP
   \STATE consider the current temporary list of $X(n)$ ($tempList$);
    \IF{$X(n)$ is executing a task that appears in $tempList$}
     \STATE break: switches to another agent;
    \ENDIF
    \IF{no assignment has just taken place}
     \IF{a task in $tempList$ is unassigned}
      \STATE $t \leftarrow$ first unassigned task in $tempList$;
      \STATE set $(X(n),t)$ as paired;
      \STATE break: switches to another agent;
      \ELSE
      \STATE consider the following temporary list;
     \ENDIF
    \ENDIF
    \IF{no assignment has just taken place}
     \IF{all tasks in $tempList$ are assigned}
     \STATE $ft \leftarrow$ first task in $tempList$;
     \WHILE{no swap takes place}
      \STATE $t \leftarrow$ current task $tempList$;
      \STATE posTn = position of $t$ in $X(n).list$;
      \STATE posTcurr = position of $t$ in the list of the agent is                      executing it;
      \IF{($posTn \prec posTcurr$) OR
         ($posTn = posTcurr$ $\;$ \small{\&\&} \\ $X(n)$ can execute a               lower number of tasks)
         }
       \STATE set $(X(n),t)$ as paired;
       \STATE break: switches to another agent;
       \ELSE
       \STATE consider the following temporary list;
      \ENDIF
      \ENDWHILE
     \ENDIF
    \ENDIF
  \ENDLOOP
  \ENDFOR
 \ENDWHILE
\end{algorithmic}
\end{algorithm}

 % \FOR{$n = 1:length(X)$}
%   \STATE clean $X(n).list$ and $X(n).score$;
%   \FOR{$h = 1:length(pool)$}
%    \IF{$n\in pool(h).list$}
%     \STATE $X(n).list(end+1) = pool(h).ID$;
%     \STATE $X(n).score(end+1) = computeScore(pool(h))$ $\;\;$ \emph{\small{\%} $\!$ see algorithm \ref{alg:cs}};
%    \ENDIF
%   \ENDFOR
%   \STATE sort $X(n).list$,$\:$$X(n).score$,$\:$$X(n).index$ according to the scores (in descending order);
%  \ENDFOR
%  \WHILE{(matching is unstable)}
%   \FOR{$n \in randperm(length(X))$}
%    \STATE assignmentDone = false;
%    \FOR{each (not repeated) value of scores chosen in an descending order}
%     \STATE create temporary lists ($tempList$) containing only tasks with the same scores;
%      \IF{$n$ is executing a task in $tempList$}
%       \STATE assignmentDone = true;
%      \ENDIF
%      \IF{~assignmentDone}
%       \FOR{$h \in tempList$}
%        \IF{$h$ is not assigned}
%         \STATE matching $(h,n)$;
%         \STATE assignmentDone = true; break;
%         %\STATE break;
%        \ENDIF
%       \ENDFOR
%      \ENDIF
%      \IF{~assignmentDone}
%       \FOR{$h \in tempList$}
%        \STATE $T$ = $n$'s preferred task;
%        \STATE posTn = position of $T$ in $X(n).list$;
%        \STATE posTcurr = position of $T$ in the list of the agent is executing $h$;
%        \IF{($posTn \prec posTcurr$) OR
%        ($posTn == posTcurr$ $\;$ \small{\&\&} \\ $length(X(n).list)\,<\,length(list\; of\; the\; opposing\; agent))$
%        }
%         \STATE assignmentDone = true; break;
%         %\STATE break;
%        \ENDIF
%       \ENDFOR
%      \ENDIF
%      \IF{assignmentDone}
%       \STATE break;
%      \ENDIF
%    \ENDFOR
%   \ENDFOR
%  \ENDWHILE
% \end{algorithmic}
%\end{algorithm}


\twocolumn

The computational complexity of this algorithm is $O(N^2)$, where $N$ is the number of agents that monitor the area of interest.\\
It is interesting to point out that, if we assume that each agent has complete lists with no ties, the worst case occurs when agents' lists contain tasks with exactly the opposite order than tasks'lists.\\
Every time the function is invocated, each agent builds temporary lists containing only tasks with the same scores, beginning from those with the highest scores: for our hypotheses, each of them contains only one task. Actually, agents do not build $H$ temporary lists (where $H$ is the number of task in the \emph{pool} at the current time), because, as soon as an assignment takes place, the algorithm switches to the next agent and the temporary lists with lower scores are not created. \\
However, the first agent builds one temporary list, the second one creates two temporary lists and so on. The $n^{th}$ agent builds:
$$
N + (N-1) + \cdots + 1 = $$ $$
\sum_{i=1}^N{i} = \frac{N(N+1)}{2} $$
Computational complexity in the worst case of the proposed SMTI Revised algorithm can not fall away, since lists are likely to be shorter. However, optimality is not assured any more, since the final solution may not be of maximum cardinality.
%Finally we have to take into account that the algorithm is repeated until a stable match is attained. But, for this particular configuration, it occurs twice: the first one for the assignment, the second one for the stability check.
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item \textbf{Pros} This algorithm allows scalability, since it requests communications only between an agent and its neighbours. \\
No deadlock is possible: two agents can prefer the same task, but the conflict is solved by breaking the ties in the lists, building temporary lists and defining a swap policy.\\
\item \textbf{Cons} Continuity is not assured: tasks can be swapped in order to attain a stable match.\\
Agents can be IDLE, i.e. if an agent's list gets empty.\\ Finally, the achieved solution may be non-optimum from the point of view of the maximization of function (\ref{eq:fABC}), as shown in the following examples.
\end{itemize}
\begin{example}
 The swapping policy of SMTI Revised may not be sufficient to achieve the best assignment. For instance, the situation could be the one shown in figure \ref{fig:nonOptSMTI1}. The best matching plans that task 1 is assigned to $a_1$, task 2 to $a_2$ and task3 to $a_3$. However if the algorithm starts from agent $a_1$, the final assignment is not optimal. As a matter of fact, a swap between $a_1$ and $a_2$, that would lead to the best configuration, is not possible, after $a_1$ has been matched to task 2. This is because task 2 is in the same position of $a_1$ and $a_2$' preference lists and agents are all equivalent in terms of the number of task they can be matched to.
\end{example}

\begin{figure*}
 \begin{center}
   \subfloat[][\emph{Non optimal assignment with SMTI Revised}]
 {\includegraphics[scale=.7]{fig/critTSa}}\quad
 \subfloat[][\emph{Optimal assignment with SMTI Revised}]
 {\includegraphics[scale = .7]{fig/critTSb}}
 \caption{The swapping policy may not be sufficient to achieve the best assignment in SMTI Revised}
\label{fig:nonOptSMTI1}
 \end{center}
\end{figure*}

\begin{example}
Another example is given in figure \ref{fig:nonOptSMTI2}, showing how the sequence in which agents are taken into consideration and the equivalence of the agents themselves can affect the final solution. The left figure shows the worst possible stable matching. This can be attained, for instance, if the forth agent, $a_4$ is the last that is considered, when its favourite task has already been assigned. A swap can not occur since the contested task is the first of a list whose length is two for both $a_3$ and $a_4$. Moreover, they have the same number of feasible tasks (i.e. two). The right figure shows the best possible matching.
\end{example}
\begin{figure*}
 \begin{center}
   \subfloat[][\emph{Non optimal assignment with SMTI Revised}]
 {\includegraphics[scale=.7, trim = -3cm 0cm -3cm 0cm]{fig/critTS2a}}\quad
 \subfloat[][\emph{Optimal assignment with SMTI Revised}]
 {\includegraphics[scale=.7, trim = -3cm 0cm -3cm 0cm]{fig/critTS2b}}
\caption{Another example in which SMTI Revised does not guarantee optimality}
\label{fig:nonOptSMTI2}
 \end{center}

\end{figure*}

\subsection*{Randomized SMTI Revised}
This algorithm is similar to the previous one. The only difference is when a swap can take place:
\begin{enumerate}[\IEEEsetlabelwidth{a}]
\item if the current agent can execute a lower number of tasks than its opposing agent;
\item according to the outcome of a coin toss, if the two agents can execute the same number of tasks.
\end{enumerate}

The main risk of this algorithm is that it continues to repeat the same assignment procedure for ever, generating a deadlock. This is the reason we have introduced an upper limit to the number of iterations that can be executed. \\
Our intentions were to solve the bad situations of the previous algorithm, but we have found that it does not imply big advantages.

% %ESEMPIO GRAFICO CASO IN CUI PUÒ ESSERE UTILE (IL CELEBRE ESEMPIO DEL GRANDE GROSSO TASK CONTESO)
% %NE' INFAMIA NE' LODE


% \begin{figure*}
%  \begin{center}
%    \subfloat[][\emph{Non optimal assignment with SMTI Revised}]
%  {\includegraphics[scale=.5]{fig/critTS2a}}\quad
%  \subfloat[][\emph{Optimal assignment with SMTI Revised}]
%  {\includegraphics[scale = .5]{fig/critTS2b}}
%  \end{center}
% \end{figure*}
%
% \begin{figure*}
%  \begin{center}
%    \subfloat[][\emph{Non optimal assignment with SMTI Revised}]
%  {\includegraphics[scale=.5]{fig/critTSa}}\quad
%  \subfloat[][\emph{Optimal assignment with SMTI Revised}]
%  {\includegraphics[scale = .5]{fig/critTSb}}
%  \end{center}
%
% \end{figure*}
\section{Simulations}
\subsection{Task Simulator}
We have built a task simulator in order to test the algorithms we have projected. \\
Two parameters can be chosen:
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item the number of agents that monitor the area of interest
\item the number of subzones the area is divided in, by intersecting the visual ranges of cameras, as explained in the previous sections.
\end{itemize}
It is defined a global structure called \emph{pool}: it contains all tasks generated, until they are completed or dropped. We recall the definition of covering matrix $\mathbf{V}$ given in equation (\ref{eq:V}):
\begin{equation}
V_{ij} =
\begin{cases}
1 & \text{if agent $i$ covers subzone $j$} \\
0 & \text{otherwise}
\end{cases}
\end{equation}
Tasks are generated in a simple way: we assume they are Poisson processes, that are processes whose interarrival times are i.i.d. random variables with exponential distribution.
Each task structure contains:
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item ID
\item Instant when it occurs for the first time
\item type: \emph{patroling}, \emph{automatic tracking}, \emph{manual tracking} or \emph{streaming}
\item location or target agent (depending on the type) of interest
\item service time, that is the required total time to complete its execution
\item residual service time, that is the remaining time before its execution is completed
\item (normalized) priority, according to the type
\item a list of compatible agents, according to the covering matrix $\mathbf{V}$
\item the agent that is executing it at the current time
\item drop time: after this time, the task is removed from the \emph{pool} even though it has not been completed, because it has got obsolete.
\end{itemize}

Each agent structure is defined by:

\begin{itemize}[\IEEEsetlabelwidth{a}]
\item ID
\item the task it is executing at the current time
\item the set of subzones it covers
\item the scores of compatible tasks
\item a preference list containing compatible tasks, ordered by a desecending scores
\item the position of \emph{pool} where compatible tasks are placed
\item a counter of the number of iterations when the agent is IDLE.
\end{itemize}

\subsection{Results}
In this section we analyse the simulation results, in order to compare the previously described algorithms.
The Randomized SMTI Revised algorithm will not be dealt, since it does not exhibit significant advantages with regard to the SMTI Revised.
The simulations were performed by means of Mathworks \textsc{Matlab}\texttrademark R2009a (7.8.304).
Unless differently specified, the attained results are a mean over ten random realizations of the pool, with the same instance parameters:
\begin{itemize}[\IEEEsetlabelwidth{a}]
 \item N = 8 (number of agents);
 \item M = 9 (number of monitored zones);
 \item Covering matrix:
    $$\mathbf{V} =
	\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}
    $$
 \item ${T}_\textup{occ}^\textup{OP} = {T}_\textup{occ}^\textup{TRK} ={T}_\textup{occ}^\textup{STR}$ = 2 s.
 \item ${T}_\textup{serv}^\textup{OP} = {T}_\textup{serv}^\textup{TRK} ={T}_\textup{serv}^\textup{STR}$ = 3 s.
 \item Simulation time: $T = 500 $ s.
 \item Load factor $C \approx 0.48$.
\end{itemize}

The considered environment is described in figure \ref{fig:topologia}.
\begin{figure}
	\centering
	\includegraphics[scale=0.7]{fig/topologia}
	\caption{Simulation environment}
	\label{fig:topologia}
\end{figure}


\begin{figure*}
	\centering
	\includegraphics[scale=1, trim = 3.8cm 10cm 3.8cm 10cm]{fig/drop}
	\caption{Drop rate}
	\label{fig:drop}
\end{figure*}

To begin with, we take into consideration the performances in terms of dropped tasks. The plot in figure \ref{fig:drop} shows the importance of the choice of the parameter $T_{\textup{drop}}$. As predictable, the longer it is, the smaller is the dropping rate. The maximum value it can assume is determined by the practise implementation, as it describes the maximum allowed duration of a task life. After $T_{\textup{drop}}$, a task is to be considered obsolete, so it is removed from the pool.
% Except for the Nearly Brute-force (NBf) algorithm (that does not keep into account the values of $\alpha$ and $\gamma$), the rate of dropped task is

\begin{figure*}
	\centering
	\subfloat[][] {
		\includegraphics[scale=.7,trim = 3.8cm 10cm 3.8cm 10cm]{fig/dropOP}
		\label{fig:dropOP}} \quad
	\subfloat[][] {
		\includegraphics[scale = .7,trim = 3.8cm 10cm 3.8cm 10cm]{fig/dropTRK}
		\label{fig:dropTRK} } \\
	\subfloat[fig:dropSTR][] {
		\includegraphics[scale = .7,trim = 3.8cm 10cm 3.8cm 10cm]{fig/dropSTR}
		\label{fig:dropSTR} }
	\caption{Drop rate}
	\label{fig:dropAll}
\end{figure*}

Still considering the dropping rate, it is interesting to compare the behaviour of the different types of tasks, depending on the values of parameters $\alpha$ and $\gamma$.

Figure \ref{fig:dropOP} shows how the highest priority tasks are preferred when $\alpha=1$. This occurs because $\alpha$ weighs the intrinsic priority of the tasks. On the one hand, since this is maximum for tasks of manual tracking -the so called ``OP'' tasks- PLI, SMTI Revised and Greedy (that make use of the utility function described in equation (\ref{eq:fABC}) show extremely low dropping rate for this kind of tasks. On the other hand, lower intrinsic priority tasks are penalized, as illustrated in figures \ref{fig:dropTRK} and \ref{fig:dropSTR}. Streaming tasks, that have the smallest priority degree, show the worst dropping rate for high values of $\alpha$.

\begin{figure*}
	\centering
	\subfloat[][]{
		\includegraphics[scale=.55,trim = 3.8cm 10cm 3.8cm 10cm]{fig/waitingOP}
		\label{fig:waitingOP}}\quad
	\subfloat[][]{
		\includegraphics[scale = .55,trim = 3.8cm 10cm 3.8cm 10cm]{fig/waitingTRK}
	 	\label{fig:waitingTRK}}\\
	\subfloat[][]{
		\includegraphics[scale = .8,trim = 3.8cm 10cm 3.8cm 10cm]{fig/waitingSTR}
		\label{fig:waitingSTR}}
	\caption{Average waiting time}
	\label{fig:waitingAll}
\end{figure*}

As regards the average waiting time of the executed tasks, the overall effect of choosing high values of $\alpha$ is to reduce it. This happens because $\gamma$ weighs the task life span, giving preference to tasks that are close to be dropped.
As a consequence, the time spent in queue by the executed tasks results longer, in average.
However, observing in detail the task behaviour, it can be found that streaming tasks do not follow the general trend (as shown in figure \ref{fig:waitingAll}).
In order to achieve a better comprehension of these results, it is useful to think about the role of $\alpha$ and $\gamma$.
Considering the array of active tasks (both being executed or waiting), sorted by occurence time, we can say that $T_{\textup{drop}}$ defines the length of this structure. The time interval $\mathcal{I}$ in which the probability of selecting a task is higher, is linked to $\gamma$. The smaller it is, the wider $\mathcal{I}$ is. Viceversa, for higher values of $\gamma$, $\mathcal{I}$ shrinks to its fixed extreme $t_{\textup{current}}-T_{\textup{drop}}$. Dually, $\alpha$ plays the same role with regard to priority: higher values of $\alpha$ imply bigger probability of selecting only the highest priority tasks (see figure \ref{fig:slidingPool} for a graphic representation of the role of $\alpha$ and $\gamma$).

% \begin{figure}
% 	\centering
% 	\includegraphics[scale = 0.75]{fig/SlidingPool}
% 	\caption{A graphic representation of the role played by $\alpha$ and $\gamma$ in determining the most probable task to be selected}
% 	\label{fig:slidingPool}
% \end{figure}


In spite of the fact that high values of $\alpha$ generally cause the waiting time to decrease, streaming tasks behave differently. This is because they have the lowest intrinsic priority, so with $\alpha \approx 1$ agents tend to neglect them.
Obviously, longer $T_{\textup{drop}}$ allows the queue to grow, so waiting time are increased.

\begin{figure*}
	\centering
	\includegraphics[scale=1, trim = 3.8cm 10cm 3.8cm 10cm]{fig/discontinuity}
	\caption{Discontinuity rate}
	\label{fig:disc}
\end{figure*}

We have already stated that we are interested in a good trade-off between continuity and optimality. We now consider the first one, comparing the proposed algorithms (figure \ref{fig:disc}).

By discontinuity we mean that a task is left by an agent before it comes to complete execution. As predictable, the PLI algorithm does not exhibit the desired continuity. This happens because this approach is memoryless: it does not take into account the previous matching in order to update the assignment when a new task occurs or is completed.
Greedy and NBf show the best results, since they are designed to be extremely conservative in matching tasks and agents. The best performances are exhibited by the Greedy algorithm when $\alpha \approx 0$, because in such a case agents evaluate tasks considering only their occurence time. As a consequence the oldest tasks are always at the top of the agents'lists.
SMTI Revised achieves good performances, thanks to the fact that swaps are limited by restrictive conditions.

\begin{figure*}
	\centering
	\includegraphics[scale=1, trim = 3.8cm 10cm 3.8cm 10cm]{fig/idle}
	\caption{IDLE occurrence}
	\label{fig:idle}
\end{figure*}

Another meaningful aspect that has to be inspected is the presence of undesired IDLE agents (figure \ref{fig:idle}).
Under our assumptions we can exclude an instantaneous optimal solution in which some agents are unloaded (as we have already stated in proposition \ref{prop:1}). As matter of fact, PLI never shows IDLE agents. SMTI Revised achieves good performances since it willfully tries to match each agent. In order to do it, in comparing agents to be assigned to a task, it weighs the shortness of their list of unexplored feasible tasks.
As already described in example of figure (\ref{fig:idlePRA}), Greedy and NBf do not guarantee the IDLE avoidance.

As a general trend, when working with a longer $T_{\textup{drop}}$, the pool contains more elements and makes unlikely that an agent has no tasks to do.

\begin{figure*}
	\centering
	\includegraphics[scale = .9]{fig/SlidingPool}
	\caption{A graphic representation of the role played by $\alpha$ and $\gamma$ in determining the most probable task to be selected}
	\label{fig:slidingPool}
\end{figure*}

Referring to optimality, a remarkable aspect is the average sum of the intrinsic priorities of assigned tasks (shown in figure \ref{fig:pr}).
The best results are obtained by PLI and SMTI Revised: there are not significant variations with different values of $\alpha$.

\begin{figure*}
	\centering
	\includegraphics[scale=1, trim = 3.8cm 10cm 3.8cm 10cm]{fig/priority}
	\caption{Assigned priorities}
	\label{fig:pr}
\end{figure*}
%
% Referring to optimality, a remarkable aspect is the average sum of the intrinsic priorities of assigned tasks (shown in figure \ref{fig:pr}).
% The best results are obtained by PLI and SMTI Revised: there are not significant variations with different values of $\alpha$.

 \clearpage

\section{Conclusions}
The proposed SMTI Revised algorithm shows good performances. In maximizing assigned priorities, avoiding IDLE agents and reducing both drop rate and average waiting time, it is similar to the centralized assignment (PLI). Moreover, it is better in terms of continuity. As precedently discussed, SMTI Revised can be easily turned into a distributed algorithm, even though the consequent costs in terms of both communication and code implementation should be furtherly analysed.
As regards the PLI algorithm, it performs best over almost every index, but it is hardly reliable over a real scenario like ours, due to the bad scalability and the unacceptable discontinuity in task execution.
In such a situation, it can be wiser to turn to Greedy or Nearly Brute-force algorithms. They are simpler to implement, scalable and cheaper. In particular, Greedy algorithm allows the designer to tune the value of $\alpha$, improving control on the assignment policy. In addition, it shows acceptable performances, except for IDLE agents avoidance.
%\vfill
\section{Future work}
A point that has not been taken into account is the problem of keeping the pool up to date when algorithms are implemented in distributed form.
In this paper we have assumed that not only the pool of tasks, but also all the variables which describe state of the system and instantaneous associations between tasks and agents, are always disposable and consistent for each agent.
In addition, cameras are considered sequentially (even if in a random order) and \emph{one for} iteration in task selection algorithm. Hence the generalization to a real system of independent agents rises many problem in the field of communications and consensus between actors:
\begin{itemize}[\IEEEsetlabelwidth{a}]
\item Keeping the pool consistent is the most critical point. A deep analysis of consequences derived from different versions of data stored in the cameras memory is required.
Also, it is important to find out a consensus mechanism for determining the most trustworthy version and develop merging algorithms, if necessary.
\item Another question is to ponder the effects of completely asynchronous acting cameras and to implement a management of task assignment collision.
Consensus algorithms, deterministic or randomized are likely the best manner to proceed. Alternatively it can be defined a \emph{leader} agent (hierarchical logic) that directly decides the best solution when such a collision happens.
\end{itemize}

It may be interesting to implement the assignment policy following the market based approach. This would imply to define communication costs properly. Moreover, the swapping mechanism should be furtherly explored. As a matter of fact, it could avoid reiterating unnecessary auctions, that are expensive in terms of synchronization and communication costs.

A completely different problem is an extension to PTZ cameras. It is possible to fraction areas in sub-areas corresponding to discrete camera angles of view and still apply the algorithms considered in this paper (with minimal adjustments).
Continuous angles are not defined if the present framework holds.
\newpage
%\addcontentsline{toc}{section}{\refname}

\bibliographystyle{plain}
\bibliography{bib}

\end{document}