# Agreement Technologies for Coordination in Smart Cities
## 3 Applications
### Emergency Medical Service Coordination
#### Dynamic Redeployment  
The second part of the proposed coordination approach for emergency medical services (EMS) consists of locating and redeploying ambulances in an appropriate manner. Here, the objective is to place ambulances in such a way that the expected travel time to future emergency patients is minimised. We addressed this problem by using Voronoi tessellations [48]. A Voronoi tessellation (or Voronoi diagram) is a partition of a space into a number of regions based on a set of generation points such that for each generation point there will be a corresponding region. Each region consists of the points in the space that are closer to the corresponding generation point than to any other. Formally, let \(\Omega\)\(\in\)\(R^{2}\) denote a bounded, two-dimensional space and let \(S\)\(=\)\(\{s_{1},\)\(\dots,\)\(s_{g}\}\) denote a set of generation points in \(\Omega\). For simplicity, let \(\Omega\) be a discrete space. The Voronoi region \(V_{i}\) corresponding to point \(s_{i}\) is defined by:  
\[V_{i}=\{y\in\Omega\colon\text{$y$}-s_{i}\text{$\mid$}<\text{$y$}-s_{j}\text{$ \mid$}\text{ for $j=1,\)\(\dots,\)\(k\) and \(j\
eq i\)}\]where \(|\cdot|\) denotes the Euclidean norm. The set \(V(S)=\{V_{1},\,\ldots,\,V_{k}\}\) with \(\cup_{i=1}^{k}V_{i}=\Omega\) is called a Voronoi tessellation of \(S\) in \(\Omega\). A particular type of tessellation is centroidal Voronoi tessellation (CVT). A centroidal Voronoi tessellation is one where each generation point \(s_{i}\) is located in the mass centroid of its Voronoi region with respect to some positive density function \(\rho\) on \(\Omega\). A CVT is a necessary condition for minimising the cost function and, thus, provides a local minimum for the following cost function:  
\[F(S)=\sum_{V_{i}\in V(S)}\sum_{y\in V_{i}}\rho(y)|y-s_{i}|^{2} \tag{1}\]  
A common approach to calculate CVTs and, thus, to minimise (1) is the algorithm proposed by Lloyd [49]. The algorithm is an iterative gradient descent method that finds a set of points \(S\) that minimises \(F(S)\) in each iteration and converges to a local optimum. Lloyd's algorithm can be summarised in the following steps:  
1. Select an initial set \(S\) of \(k\) sites in \(\Omega\). 2. Calculate the Voronoi regions \(V_{i}\) for all generation points \(s_{i}\in S\). 3. Compute the mass centroid of each region \(V_{i}\) with respect to the density function \(q\). These centroids compose the new set of points \(S\). 4. If some termination criteria are fulfilled, finish; otherwise return to Step 2. Lloyd's algorithm is not assured to find a global minimum, but it finds solutions of reasonable quality very fast--after a few iterations. Therefore, we applied Lloyd's algorithm to find suboptimal positions of ambulances. The application is straightforward: \(\Omega\) represents the region of interest, and the set of generation points \(S\) represents the set of all idle ambulances and their positions. Each Voronoi region \(V_{i}\) corresponds to the area that is covered by ambulance \(s_{i}\) (e.g., the area for which \(s_{i}\) is the closest ambulance in case any patient requires help). Furthermore, as the density function \(\rho\), we use an estimation of the probability distribution of the appearance of a patient in any point in the region of interest. In particular, to define \(\rho\), we divide the region of interest in a set of equally sized cells \(C=\{c_{1},\,\ldots,\,c_{u}\}\), where \(u\) is the cardinality of \(C\). That means we discretise the region \(\Omega\) into \(u\) points, each of which represents the centre of one of the cells \(c_{i}\). Then, we estimate, for each cell \(c_{i}\), the conditional probability \(p_{ci}\) that a new emergency patient will appear in this cell. With this setting, Lloyd's algorithm finds a distribution of ambulances that minimises (1). In particular, in our case, this is a reasonable approximation for minimising the expected distance and, thus, the arrival time, to future emergency patients.