# Challenge 3

## Overleaf Report Document

Link to the Overleaf report document (of which everyone should be able to edit):
https://www.overleaf.com/6548219626kpwchkqgysqg

## Optimisation of Sensor Location
Participants:
Bill Lionheart (Manchester): inverse problems
Bo Chen (Warwick): combinatorial optimisation; game theory
Ayalvadi Ganesh (Bristol): Applied probability, random graphs, distributed algorithms.
Will Handley (University of Cambridge),
Michael Wilsher (Bristol) ...
David Humphreys (NPL), 5GFuture Networks Science area Leader Optical and RF communication metrology, Waveform metrology, Uncertainties some inverse problems. THz comms. Metrology
Justin Ward (Queen Mary): Combinatorial optimisation
Carl Dettmann (Bristol) Applied probability and dynamics
John Beasley (Brunel) combinatorial optimisation - formulation and solution algorithms
Daniel Lesnic (Leeds) Inverse problems
Varun Chhabra (Dstl) [e-mail]
Emma Bowley (Dstl)
Naeem Desai (Dstl)

## Approaches:

### Combinatorial/ graph theoretic

Discretise the problem by dividing up the area of interest into small "cells". Sensors can be placed in any of the cells (or some may be forbidden), while the rogue transmitter can be in any cell. A sensor placed in a given cell $i$ can detect (and locate?) the rogue transmitter if it is anywhere within a set of cells $S_i$. We can now formulate the problem as follows:

Find the minimum number of sensors such that a rogue transmitter in any cell can be detected. A variant is to associate a cost with each cell for placing a sensor there - some locations may be easier to access than others for sensor placement.

This is known as the set cover problem. Here, we are given a collection of subsets of some universe $U$ and seek to find a subcollection $\mathcal{S}$ so that every element of $U$ appears in at least one set in $\mathcal{S}$. Here, we can imagine potential locations of the rogue station being $U$ and each potential sensor placement corresponding to a set of these locations that it can detect. The goal is then to choose as small or cheap a subcollection of sets (corresponding to a set of sensors) as possible to detect all locations. Set Cover is known to be NP-hard even to approximate within any constant factor (see Feige reference below), but can be solved to within a constant factor for instances with some "nice" underlying geometry (i.e. the sets are not arbitrary collections of elements, but correspond to some "simple" connected subsets of $\mathbb{R}^2$).

It might be possible to reformulate the problem as a special case of Set Cover known as Dominating Set. To do this, we use a graph (network) to represent the problem: the cells are the vertices, and an edge from $i$ to $j$ denotes that a sensor placed at $i$ can denote a transmitter at $j$. If this relation is symmetric, then the edges of this graph are undirected. The Dominating Set problem is that of finding the smallest subset $D$ of vertices such that every vertex is adjacent to some element of $D$. This problem is also NP-complete, but has known constant factor approximation algorithms.

The problem has also been stated for directed graphs, but much less seems to be known in this case.

A variant of this problem which may be of interest is as that of finding the smallest $k$-tuple dominating set or $k$-dominating set. A set $D$ is a $k$-tuple dominating set if every vertex has at least $k$ neighbours in $D$; it is a $k$-dominating set if every vertex in $D^c$ has at least $k$ neighbours in $D$. These variants can be efficiently approximated to a factor which is logarithmic in the maximum degree.

Yet another formulation is in terms of the facility location problem. The sensors are facilities, and cells are potential locatons for facilities. Each location has a cost for placing a facility there, and there is also a cost for a facility at $i$ to "serve" a demand at $j$, which might take account of how well a sensor at $i$ can detect a transmitter at $j$. In this formulation, the demand at a node can be bigger than 1. This generality allows us to incorporate the need for robustness. A demand of $k$ would mean that a cell should be covered by at least $k$ different sensors. This corresponds to the $k$-tuple dominating set, but note that the facility location problem can be formulated on directed graphs as well.

The facility location problem is also NP-complete. There are known approximation algorithms, e.g., using LP relaxation.

Finally, while all these problems are hard in theory, they are often easy in practice!

Stochastic version of facility location problem? Probabilities associated with whether facility at i can serve demand at (sense signal at) j. These are not going to be independent, though, so model could be very complicated!

Note that the dual problem, in which we have in advance a budget on the number of sets we may choose and now seek to cover as many elements as possible, is easy to approximate to within a constant factor with a simple greedy algorithm (even for arbitrary sets).

References:

U. Feige, A threshold of ln n for approximating set cover, https://dl.acm.org/doi/10.1145/285055.285059

Collection of references on facility location problem: https://en.wikipedia.org/wiki/Facility_location_problem

Collection of references on set cover problem: https://en.wikipedia.org/wiki/Set_cover_problem

Collection of references on dominating set problem:
https://en.wikipedia.org/wiki/Dominating_set

Banks et al. (2007) Sensitivity functions and their use in inverse problems, Journal of Inverse and Ill-Posed Problems Vol.15, No.7
https://apps.dtic.mil/dtic/tr/fulltext/u2/a471254.pdf

-----------------

### Inverse problem

This is my attempt to capture what Daniel said and may not be fully accurate. Also, I am discretising the problem but believe he had a continuous version in mind.

We are given the transmission matrix $A$, so the received signal is
$$
\mathbf{y}=A \mathbf{x}+ \epsilon,
$$
where $\mathbf{x}$ is the transmitted signal and $\epsilon$ is noise, which we might assume is Gaussian.

If there is a single transmitter, then $\mathbf{x}=\beta e_i$, where $e_i$ is the unit vector corresponding to a transmitter at location $i$, and $\beta$ is the unknown transmit power.

We can only observe some coordinates of $\mathbf{y}$ and want to decide which coordinates to observe in order to best estimate $\mathbf{x}$.

One challenge I see is that "best" is not the usual error metrics like $\ell^2$ distance between estimated and true $\mathbf{x}$. The error metric should capture Euclidean distance between the estimated and true locations instead. So, we might want some "earth-mover" metric like Wasserstein distance.

suggest inverse problem arising from actual and planned location - how far from optimal was the positioning? This might be useable with the boolean sensor map approach.

-----------------

### (Non-convex) $2N$-dimensional optimisation problem with nonlinear constraints.


- Number of sensors $N$ may also be a parameter to be optimised.
- Each sensor location has $2$ parameters $(x_i, y_i)$, and is constrained to be in certain locations in the landscape (e.g. to be on top of buildings, not in rivers). Full parameter space is $\{x_1, y_1, x_2, y_2, \ldots, x_N, y_N\}$
- constraints may be hard (forbidden), or soft (discouraged due to expense/difficulty of placement)
- Possible algorithms:
- Genetic algorithm
- MCMC
- gradient descent
- nested sampling
- particle filter
- hybrid combinations of the above, e.g. use the heuristic minimization to providea good initial guess for the gradient descent
- Could possibly be multi-objective (optimising coverage vs cost of sensor placement). Consider risk as a cost or a separate objective or constraint?
- If you have an ensemble-based approach, typical multi-objective strategy is to optimise over the main objective (e.g. coverage) and then to re-optimise over the ensemble of solutions (or particles, or random samples) over the second objective (e.g. cost).
- As problem is non-convex, and constraints are (very) nonlinear, there will be no guarantees of finding the optimum, but there are lots of heuristic approaches which will get a good answer. In the case of multi-objective optimisation, finding the 'optimum', is not even necessarily desirable.
- Another advantage of ensemble-based approaches is that they tend to find more 'stable' solutions (i.e. less fine-tuned regions of parameter space) which is useful if you want your approach to be robust to, say, knocking out a sensor. This is effectively a 'sensitivity analysis'
- In general this approach is an 'offline' approach -- maximising in a non-convex space will require significant computing power (although this can be reduced in walltime in general with HPC), so would likely not be so suitable for a rapidly dynamically updating landscape

Toy example


Given that the computation of coverage is effectively a black box it is unlikely you can do any optimality calculation for sensor positions. Algorithmically to decide (fixed) sensor locations you can do some sort of simple algorithm: move one (or more) sensors a small bit, recompute coverage, if better keep these positions, if not then move some different sensors. Repeat until no improvement can be found.

In terms of sensitivity (e.g. loss of a sensor) you can incorporate this into the cost function. Small changes in actually positioning the sensor away from the position given by the model I would regard as lesser importance. Realistically can you actually model the buildings etc to a high degree of accuracy.

import matplotlib.pyplot as plt
import numpy as np

class City(list):
    def in_building(self, X):
        in_building = np.zeros(X.shape[1:],dtype=bool)
        for building in self:
            xmin, ymin = building.get_xy()
            xmax, ymax = xmin + building.get_width(), ymin + building.get_height()
            in_building = in_building | ((X[0] >= xmin)  &  (X[0] <= xmax) & (X[1] >= ymin)  &  (X[1] <= ymax) )
        return in_building

    def has_line_of_sight(self, y, X, N_line=None, lblock=0.05):
        y = np.array(y)
        X = np.array(X)
        if N_line is None:
            N_line = X.shape[-1] - 1
        d = y[:,None,None]-X
        u = np.linspace(0,1,N)
        line = X + d*u[:,None,None,None] 
        l = np.sqrt((d*d).sum(axis=0))
        crossings = np.zeros((N_line,*X.shape[1:]),dtype=bool)
        for building in self:
            xmin, ymin = building.get_xy()
            xmax, ymax = xmin + building.get_width(), ymin + building.get_height()
            crossings = crossings | ((line[:,0] >= xmin)  &  (line[:,0] <= xmax) & (line[:,1] >= ymin)  &  (line[:,1] <= ymax) )

        covered = (crossings.sum(axis=0)/N_line*l < lblock) & ~self.in_building(X)

        return covered

    def seen(self, sensors, X):
        seen = np.zeros(X.shape[1:],dtype=bool)
        for i, sensor in enumerate(sensors):
            covered = city.has_line_of_sight(sensor, X)
            seen = seen | covered
        return seen

    def coverage(self, sensors, X):
        return (self.seen(sensors, X)/X.size).sum()

    def plot(self, ax=None):
        if ax == None:
            ax = plt.gca()

        for building in self:
            ax.add_artist(building)

        ax.set_xlim(0,1)
        ax.set_ylim(0,1)
        ax.set_xticks([])
        ax.set_yticks([])
        return ax.figure, ax

city = City()

city.append(plt.Rectangle((0.,0.),0.15,0.7, fill=False))
city.append(plt.Rectangle((0.25,0.),0.5,0.15, fill=False))
city.append(plt.Rectangle((0.85,0.),0.15,0.6, fill=False))
city.append(plt.Rectangle((0.25,0.25),0.3,0.15, fill=False))
city.append(plt.Rectangle((0.6,0.25),0.15,0.25, fill=False))
city.append(plt.Rectangle((0.0,0.85),1.,0.15, fill=True))
city.append(plt.Rectangle((0.4,0.6),0.1,0.1, fill=False))

sensors = np.array([(0.5, 0.13), (0.35,0.38), (0.73,0.47)])
m = 150
X = np.array(np.meshgrid(np.linspace(0,1,m+1), np.linspace(0,1,m+1)))

%lprun -f city.has_line_of_sight city.coverage(sensors, X)

fig, ax = city.plot()
fig.set_size_inches(7,7)
fig.tight_layout()
fig.savefig('city_0.png')

seen = np.zeros(X.shape[1:],dtype=bool)
for i, sensor in enumerate(sensors):
    covered = city.has_line_of_sight(sensor, X)
    seen = seen | covered

    points, = ax.plot(X[0][covered], X[1][covered], '.')
    ax.plot(*sensor, 'o', color=points.get_color(), markeredgecolor='k')
    fig.savefig('city_%i.png' % (i+1))

plt.plot(X[0][~city.in_building(X) & ~seen], X[1][~city.in_building(X) & ~seen], 'k.')
fig.savefig('city_%i.png' % (i+2))

city.coverage(sensors, X)

def objective_function(coordinates):
    sensors = np.reshape(coordinates, (len(coordinates)//2,2))
    return city.coverage(sensors, X)

print(objective_function([0.6,0.2,0.3,0.4,0.5,0.6]))

Optimal examples for $N=1,2,3,4$ found using nested sampling (PolyChord)

Nested Sampling: Bayesian Anal. Volume 1, Number 4 (2006), 833-859. https://projecteuclid.org/euclid.ba/1340370944

PolyChord: Monthly Notices of the Royal Astronomical Society, Volume 453, Issue 4, p.4384-4398 https://arxiv.org/abs/1506.00171


#### $N=1$

#### $N=2$

#### $N=3$

#### $N=4$

#### Selection of optimal solutions

---

Tycho Brahe triangulation



## Considerations:

- Fast fading environments (some form of Frequency Domain Multiplexing e.g. OFDMA gives a degree of protection -assume environment is dynamicly changing Ref: M. Rumney, “LTE and the Evolution to 4G Wireless ‐ Design and Measure-ment Challenges, Second Edition: Design and Measurement Challenges, Sec-ond Edition, CH2” John Wiley & Sons, Ltd., ISBN:9781119962571, July 2013.). Worst case will be if the sensor is in a dead zone -> no data or communication - allow some redundancy in the optimisation.
- Different sensor capabilities and complexities (This can be incorporated into the cost function)
- Mobility?
- For identification of radio angular and time proposed. Both solutions have limitations: Angular (multi-elements, 6-axis frame of reference), Time (multi-path, higher communication payload, time-distribution) Existing Ref: W. Tidd, J. W. Raymond, Y. Huang and Y. Zhao, "A RF source localization and tracking system," 2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE, San Jose, CA, 2010, pp. 858-863, doi: 10.1109/MILCOM.2010.5680188. K. Bregar et al., "Evaluation of range-based indoor tracking algorithms by merging simulation and measurements," . EURASIPJournalonWirelessCommunicationsand Networking (2019) 2019:173 https://doi.org/10.1186/s13638-019-1489-y
- power/energy required?
- How well do you know the location? Could this be described as some potential as the information is often imperfect at some level of granularity?

### Coverage model

* Let $a_{ij}=1$ if a sensor placed at $i$ can detect a signal at location $j$ for $i, j=1,\ldots,N$
* Let $c_i$ be the cost of placing a sensor at location $i$
* Let the decision variable be defined using $x_i=1$ if we place a sensor at location $i$, where $i=1,\ldots,n$, and zero otherwise
* Let $y_j=1$ if location $j$ is not covered (so no sensor can detect a signal there)
* Let $K$ be the number of uncovered locations

Then the decision problem is:

$\mbox{Minimise} \sum_{i=1}^n c_i x_i$

subject to
\begin{equation}
\sum_{i=1}^n a_{ij}x_{i} \geq 1 - y_j, \quad j=1,\ldots,N, \nonumber \\
\sum_{j=1}^N y_j = K.
\end{equation}

You can trade off objective cost against $K$, or produce a combined objective involving cost and $K$.

### Questions

- How to generate the $a_{ij}$ matrix (innacurate location/coverage information etc.).
- Include costs by giving weights to placing sensors at specific locations.
- Interference between sensors: do we have independence between sensor locations?
- Is it possible to take limits and move into the continuous landscape?

### Sensitivity analysis
Sensitivity coefficients are the partial derivatives of the measurements (e.g. scattering matrix or time-of-flight data) with respect to the design variables (e.g. the nodes parameterising the unknown target). In order to obtain comparable quantities in terms of physical units, the sensitivity coefficients are multiplied by the design variable resulting in the normalised sensitivity coefficients. In general, the sensitivity coefficients are desired to be large and uncorrelated.

Banks et al. (2007) Sensitivity functions and their use in inverse problems, Journal of Inverse and Ill-Posed Problems, 15 (7).
https://apps.dtic.mil/dtic/tr/fulltext/u2/a471254.pdf

J.V. Beck and K.J. Arnold (1977) Parameter Estimation in Engineering and Science, J. Wiley.

### Comment from David Bourne

A couple of references from the optimal transport literature on optimal location problems with cost constraints, which I've worked on quite a bit. One of the references is a SIAM Numerical Analysis paper by me and Steve Roper (see Section 1.5.3) and the other is a SIAM Review article.

Challenge 3 could be cast in this framework, as an optimisation problem where you penalise the cost of building/running each sensor plus the 'distance' between the environment and the sensors (e.g., a distance between two probability distributions, a distribution representing the prior knowledge on the location of the target, and a discrete probability distribution representing the location of the sensors). This approach also chooses the optimal number of sensors for you. It uses tools from computational geometry, namely weighted Voronoi diagrams (power diagrams). This is perhaps related to the 'utility' approach you mentioned

Bourne, David P., and Steven M. Roper. "Centroidal power diagrams, Lloyd's algorithm, and applications to optimal location problems." SIAM Journal on Numerical Analysis 53.6 (2015): 2545-2569.

https://arxiv.org/pdf/1409.2786.pdf