% -----------------------------*- LaTeX -*------------------------------
\documentclass[12pt,A4]{report}
\usepackage{PSC_class}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage[italian]{babel}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{color}
\usepackage{float}
\usepackage{epsf,indentfirst}
\usepackage{amsmath}
\usepackage{amssymb}

\begin{document}

% \course{CS 497}           % optional
% \coursetitle{Geometric Data Structures} % optional
% \semester{Fall 1998}          % optional
% \lecturer{Jeff Erickson}      % optional
\scribe{Guido Albertin, Elena Toffoli, Giancarlo Baldan}        % required
\lecturenumber{16}           % required, must be a number
\lecturedate{Maggio 22}       % required, omit year

\maketitle

\section{Consenso}
Con il termine consenso si intende la convergenza ad un parametro comune di più agenti tramite scambio di informazioni o interazione locale. I problemi di consenso si possono suddividere in:
\begin{enumerate}
	\item rendez-vous (robotica combinata);
	\item stima distribuita;
	\item sincronizzazione;
	\item calibrazione.
\end{enumerate}

\subsection{Rendez-vous}
Si hanno $N$ veicoli la cui dinamica è data da
$$x_{i}^+ = x_{i}\,+\,u_{i}$$
o equivalentemente $x_{i}^{k+1} = x_{i}^k\,+\,u_{i}^k$ in cui $x_i$ e $u_i$ sono scalari. Lo scopo è quello di far convergere tutti i veicoli in un unico punto
$$x_{i}(t) \longrightarrow \bar{x} .$$
Una soluzione banale a questo tipo di problema si ottiene ponendo $u_i=-x_i$ in modo da far convergere tutti gli agenti in un solo passo nell'origine. In termini energetici il punto ideale verso cui convergere è però il centro di massa o comunque un punto interno alla configurazione. In forma vettoriale il problema può essere formalizzato come segue
$$\textbf{x}= \left[
\begin{array}{l}
	x_1 \\ \,\vdots \\x_N
\end{array}
  \right]  \in \mathbb{R}^N
 \qquad \qquad
  \textbf{x}= \left[
						\begin{array}{l}
						x_1 \\ \,\vdots \\x_N
				   \end{array}
  \right] \in \mathbb{R}^N \qquad \qquad \textbf{x}^+=\textbf{x}+\textbf{u}.$$

  \begin{figure}[!h]
		\begin{center}
			\includegraphics[width=6cm]{banale} \qquad \qquad
            \includegraphics[width=6cm]{combConvessa}
		\end{center}
	  \caption{A sinistra convergenza in un passo all'origine; a destra l'agente $i$ riceve le posizioni di $j$ e $l$ e si muove di conseguenza.}
		\label{combinazione}
\end{figure}
L'obiettivo è quello di progettare un controllo che porti tutti i veicoli nello stesso punto all'interno della configurazione. L'idea è che ciascun veicolo riceva la posizione di altri agenti presenti nella configurazione e si sposti verso una combinazione convessa delle posizioni stesse
\begin{eqnarray*}
  x_i^+ &=& \rho_1 \,x_i + \rho_2 \,x_j + \rho_3 \, x_l= \\
    &=& (1-\rho_2-\rho_3)\,x_i +\rho_2\,x_j+\rho_3\,x_l= \\
    &=& x_i + \underbrace{\rho_2 (x_j-x_i) + \rho_3 (x_l-x_i)}_{\mbox{$u_i = k_i \,x $}} = p_i\,x
\end{eqnarray*}
dove i pesi sono $\rho_i \geq 0$ e $\Sigma \rho_i =1$. Si osserva che con questo tipo di approccio è necessaria la sola distanza relativa tra gli agenti e non la loro posizione nel piano. Si ottiene così
$$
\left\{
\begin{array}{l}
\textbf{x}^+  =  \textbf{x} +\textbf{u} \\
\textbf{u}  =  K \textbf{x}
\end{array}
\right.
$$
quindi
$$\textbf{x}^+ = \textbf{x}+K\textbf{x}= \underbrace{(I+K)}_{\mbox{P}}\textbf{x}  \qquad \qquad P = \left[
						\begin{array}{c}
						p_1 \\ \vdots \\ p_N
				   \end{array}
  \right] \in \mathbb{R}^N .  $$
La matrice $P$ è una matrice stocastica fatta cioè di elementi non negativi ($p_{ij}\geq 0$) e tale per cui la somma degli elementi di ciascuna riga è unitaria ($\Sigma_{i=1}^N p_{ij}$). Se l'agente $j$-esimo comunica la posizione a quello $i$-esimo l'elemento $p_{ij}$ sarà positivo mentre in caso contrario esso sarà nullo. \\
Si può definire a questo punto il vettore $$\textbf{1} =\left[
						\begin{array}{c}
						1 \\ \vdots \\ 1
				   \end{array}
  \right]  $$
autovettore destro relativo all'autovalore unitario e tale per cui $P\textbf{1}=\textbf{1}$. \'E proprio grazie a quest'ultima proprietà della matrice $P$ che il punto verso cui i veicoli convergono è un punto di equilibrio (questo non equivale a dire che la matrice $P$ è asintoticamente stabile). \\
Introduciamo ora 
$$\textsl{S}=\left\{z=\sum_{i=1}^N \alpha_i x_i \,|\, \alpha_i\geq 0,\sum\alpha_i=1 \right\}$$ 
ovvero il poligono convesso (vedi figura \ref{convexHull}) che include tutti i punti; si può dimostrare che ed ad ogni passo dell'algoritmo di controllo \textsl{S} si riduce o al più resta invariato.
\begin{figure}[!h]
		\begin{center}
		\includegraphics[width=6cm]{convexHull} 
		\end{center}
		\caption{Convex hull}
		\label{convexHull}
\end{figure}
Un altro caso di interesse è quello in cui $P$ è tempo variante; la relazione che lega lo stato della configuarazione alle condizioni iniziali ad un generico istante $t$ è esprimibile come 
$$x(t) = ( \prod_{k=1}^t P_k ) x(0) $$
mentre nel con $P$ costante si aveva $x(t) = P^t  x(0)$. Un ulteriore distinzione tra le matrici tempo varianti si può avere in base al metodo con cui vengono scelti i veicoli con i quali ciascun agente comunica ad ogni passo: si distingue tra matrici random (se la scelta avviene in modo casuale) oppure deterministiche. \\ Bisogna a questo punto dimostrare che $\textsl{S}$ tende a ridursi ad un punto e capire quali siano le proprietà che deve avere la matrice $P$ affichè questo avvenga ovvero sotto quali condizioni 
$$P^t \stackrel{?} {\rightarrow} P_\infty \qquad \mbox{oppure} \qquad \prod_{k=1}^t P_k \stackrel{?} {\rightarrow} P_\infty .$$
Sarà inoltre importante capire che relazioni intercorrono tra le prorietà della matrice $P$ ed il grafo di comunicazione allo scopo di progettare la matrice di modo che la configurazione converga il più velocemente possibile.



\subsection{Stima distribuita}
Il comando di controllo è in questo caso proporzionale alla stima ottima 
$$\textbf{u} = L \hat{\textbf{x}} = \left[
						\begin{array}{l}
						l_1 \\ \,\vdots \\l_N
				   \end{array} \right] \hat{\textbf{x}}.$$
A ciascun agente serve quindi, per comportarsi in modo ottimo, la stima che dipende dalle misure di tutti i sensori essendo $\textbf{u}_i = l_i \hat{\textbf{x}}$; tale stima non sarà ovviamente disponibile nel caso in cui il grafo non sia completamente connesso. \\
Un esempio può essere quello in cui ciascuno degli $N$ nodi misura la temperatura all'interno di una stanza 
$$y_i = T +\nu_i \qquad\mbox{dove}\qquad \nu_i \sim N(0,1).$$
La stima ottima di massima verosimiglianza date tutte le misure è la media 
$$\hat{T}_{glob} = \frac{1}{N} \sum_{i=1}^N y_i $$
ed il nostro obiettivo è quello di trovare un'algoritmo di controllo tale per cui 
$$\hat{T}_i(t) \longrightarrow \hat{T}_{glob}.$$
L'idea è di utilizzare come stima iniziale la misura di ciascun sensore 
$\hat{T}_i(0) = y_i$ e di iterare l'algoritmo
$$\hat{T}^+ = P \hat{T} .$$
Nel caso in cui $P^t \rightarrow P_\infty$ e imponendo che $P$ sia anche stocastica per colonna ovvero che $\mathbf{1}^T P = \textbf{1}^T$ varrà anche $\textbf{1}^T P^t = (\textbf{1}^T P) P^{t-1}= \textbf{1}^T$. Supponendo inoltre che $P_\infty$ sia tale per cui 
 $$\textbf{x}(t) = P^t \textbf{x}(0)\qquad \longrightarrow \qquad P_\infty \textbf{x}(0)\,=\, \bar{x} \textbf{1}$$
dalle seguenti relazioni
\begin{eqnarray*}
  \textbf{1}^T \textbf{x}(t)  &=& \textbf{1}^T P^t \textbf{x}(0)\qquad \longrightarrow \qquad  \textbf{1}^T P_\infty \textbf{x}(0)\,=\, \textbf{1}^T \textbf{x}(0)\textbf{} \\
 \textbf{1}^T \bar{\textbf{x}}\textbf{1}   &=& \textbf{1}^T \textbf{x}(0)
\end{eqnarray*}
segue 
$$ \bar{\textbf{x}} = \frac{1}{N} \sum_i x_i (0)$$
ovvero se si ha convergenza il valore verso cui tutti i sensori tendono è la media stessa, ma solo nel caso in cui $P$ sia doppiamente stocastica. Si avrà in oltre 
$$\hat{T}(t) \longrightarrow \frac{1}{N} \sum_i y_i \textbf{1} = \hat{T}_{glob} \textbf{1}.$$




\subsection{Sincronizzazione}
Si hanno in questo caso a disposizione N orologi ciascuno dei quali fornisce una misura locale del tempo  
$$\tau_i (t)= \alpha \,t + o_i \,.$$
Si muovono tutti alla stessa velocità $\alpha$ ma partendo da istanti diversi $o_i$. Lo scopo è quello di realizzare uno stimatore funzione del tempo locale ed in grado di compensare l'offset iniziale
$$\hat{\tau}_i (t) = f(\tau_i) + \hat{o}_i(t) = t + o_i + \hat{o}_i(t)$$
di modo che dopo un certo numero di iterazioni gli orologi restituiscano la stessa stima
$$\hat{\tau}_i (t) \longrightarrow \tau_{glob} \qquad \forall i$$
con $\tau_{glob} (t) = t + o_{glob}$. Ponendo $x_i(t) = o_i + \hat{o}_i(t)$ ci si può ricondurre ad un problema di consenso infatti 
$$t+o_i + \hat{o}_i(t) \longrightarrow t + o_{glob}$$
diventa ora
$$ x_i(t) \longrightarrow o_{glob}.$$
A questo punto si tratterà di scegliere una matrice stocastica $P$ tale per cui tutte le $ x_i(t)$ convergano ad un unico valore (non necessariamente la misura esatta del tempo). In analogia a quanto visto in precedenza si avrà quindi 
$$\textbf{x}^+ = P \textbf{x}$$
In forma vettoriale 
$$\hat{\textbf{o}}= \left[
\begin{array}{c}
	\hat{o}_1 \\ \,\vdots \\ \hat{o}_N
\end{array}
  \right]  \in \mathbb{R}^N
 \qquad \qquad
  \textbf{o}= \left[
						\begin{array}{c}
						o_1 \\ \,\vdots \\x_N
				   \end{array}
  \right] \in \mathbb{R}^N \qquad \qquad \textbf{x}^+=\textbf{o}+\hat{\textbf{o}}$$
$$(\textbf{o}+\hat{\textbf{o}})^+ = P ( \textbf{o}+\hat{\textbf{o}}) = (I+K)( \textbf{o}+\hat{\textbf{o}}).$$
Quindi    
\begin{eqnarray*}
  \hat{\textbf{o}}(t+1) &=& \hat{\textbf{o}}(t) + \textbf{o} - \textbf{o} + K ( \textbf{o}+\hat{\textbf{o}})= \\
    &=& \hat{\textbf{o}}(t) + K ( \textbf{o}+\hat{\textbf{o}})
\end{eqnarray*}
come in precedente la matrice $K$ sarà facilmente ricavabile dalla matrice $P$ (e viceversa) sulla base della relzione $P = I+K$; si osserva in oltre che essa, anche in questo caso, introduce fattori moltiplicativi le differenze tra gli offset iniziali ed il termine atto a compensarli. In altre parole per ciascuna componente si avrà $[K \textbf{x}]_i = \sum_j \rho_i (x_j-x_i)$ dove $x_j-x_i$ può essere espresso
$$\underbrace{t+o_i+\hat{o}_i(t)}_{\mbox{$\hat{\tau}_i(t)$}} \, - \, (\underbrace{t+o_j+\hat{o}_j(t)}_{\mbox{$\hat{\tau}_j(t)$}}).$$
Si può osservare come in questo caso le stime $\hat{o_i}(t)$ tendano a valori diversi essendo
$$\hat{\textbf{o}}(t+1)=\hat{\textbf{o}}(t) + K \hat{\tau}(t) $$  
mentre a convergere sono $o_j+\hat{o}_j(t)$. Il problema può essere esteso anche al caso in cui i sensori si muovano a velocità diverse.

    
\subsection{Calibrazione}
Si hanno ora $N$ sensori che raccolgono misure affette da offset 
$$y_i = \Theta + \nu_i $$
ed in questo caso vorremmo che tutti i sensori restituissero misure coerenti ovvero che 
$$\hat{y}_i \rightarrow y_{glob}$$
non si tratta quindi di calcolare $\Theta$ ed il problema è analogo a quelli visti in precedenza. Un esempio può essere rappresentato dalla calibrazione della potenza segnale radio nei \emph{motes} ovvero dispositivi posti alla stessa distanza devono restiutire la stessa misura dell'intensità del campo elettrico. Anche in questo caso ci si potrebbe trovare ad affrontare casi più complessi ad esempio con misure che dipendono da termini di ordine superiore di $\Theta$.
\end{document}
