# Line of Sight (LoS) Analysis: Optimizing the Observers for Best Coverage (Part 4)

*N*observers on terrain such that visible region (as many

*green*points as possible by our convention) is maximized ?”.

We first define a pseudo code in order to find the optimal (Not guaranteed. Keep in mind that optimization problems are usually NP-complete by their nature) layout of *N* observers. For simplicity we will assume that all observers have the same height (7 units) which can be relaxed later.

We will implement a constructive way of finding optimal layout for N observers. Here is the pseudo code:

- Find the optimal layout for 1 observer and compute coverage ratio (best coverage for one observer)
- Add another random observer ((
*uniform(-8,8),*) and compute the coverage for those two observers (random one and the best observer from Step 1).*uniform(-8,8))* - If the new coverage is better than the coverage in Step 1, use this as the input of optimization solver
- Otherwise repeat Step 2 to find a better coverage.
- For number of observers greater than 2 apply the idea in Step 2 recursively.

There are some blur points in this pseudo code. We will define those before moving further with the implementation.

### Coverage

The very first thing to be defined is the coverage idea. As you will remember from second post, we have defined our 3D terrain by evaluating our *height* function over outer product of *x & y* values varying over *[-8,8]* with a step size of *0.1* units. We have *1681* different* (x,y)* tuples. Here is the definition of coverage based on our conventions:

**Coverage Ratio**is the ratio of points within LoS of a given observer/group of observers (at least one of the observers mark those set of points as*green*) to the total number of points (1681)

### How to Find Optimal Coordinates of Observers ?

Optimality is a very common word used in place of many different concepts in real life or engineering. Let me define it once more for our purpose:

**Optimization**is the process of searching for an*N-dimensional vector*using a*technique*to maximize/minimize*a function of that N-dimensional vector*.

Now let’s substitute three italic words of definition for our problem:

**N-dimensional vector**in our problem is the vector of first to components of observer dimensions. Such as,*(x1,y1,x2,y2,…,xn,yn).***Technique**to be used is the Nelder and Mead Technique (A version of it implemented in R).**Function**to be maximized is the coverage function which we have defined for a given set of observers.

### Implementation

Let’s start by defining the function to be optimized that is *coverage* of terrain for a given set of observers.

targetfunc<-function(observer){ m <- matrix(data=observer,ncol=2,byrow=TRUE) # Compute merged status of all observers mergedstatus <- rep("red",length(terrain$height)) for(oidx in seq(1:dim(m)[1])){ terrain$dist2observer <- distance(terrain, c(m[oidx,],7)) status <- LoS(terrain,c(m[oidx,],7),maxVisibleDistance) mergedstatus <- updatestatus(mergedstatus,status) } sum(mergedstatus=="green")/1681 }

*matrix* routine allows us to create a table of two columns(first two dimensions of observers) and *length(observer)/2 *rows*. *We have used the technique discussed in part 3 to compute merged status of observers. *sum(mergedstatus==”green”)* call is used to count number of *green* points on terrain with respect to observers.

Next is the computation of first input to be given to optimization solver. That’s because for any optimization technique starting point is critical. Without any formal definition we will use our pseudo code to choose a *“good starting point/vector”.*

n <- 2 baselineValue <- 0.541344 previousObserver <- c(1.15861411217711, 1.1499851362913) observers <- c(previousObserver,runif(2,-8,8)) while(targetfunc(observers) <= baselineValue){ observers <- c(previousObserver,runif(2,-8,8)) } print(observers)

Above code is an example to initialize *observers* vector for searching best 2 observer layout. It uses the best coverage ratio for 1 observer case (*54.1344%*) and adds a new random observer next to best observer found for single observer case.

Final point is the optimization solver which is very simple and totally handled by R

optim <- optim(observers, targetfunc, control=list(fnscale=-1,trace=5,REPORT=1))

First parameter is the initial value for input vector (prepared by previous code piece). Second parameter is the name of the function to be maximized. *optim* function is implemented to solve minimization problems by default. Setting *fnscale* attribute of *control* parameter turns it to a maximization problem solver.

Now we can combine all to have our final script

library(rgl) ################## # Functions ################## # 3D Terrain Function height <- function (point) { sin(point$x)+0.125*point$y*sin(2*point$x)+sin(point$y)+0.125*point$x*sin(2*point$y)+3 } # Linear Function linear <- function (px, observer, target) { v <- observer - target y <- ((px - observer[1])/v[1])*v[2]+observer[2] z <- ((px - observer[1])/v[1])*v[3]+observer[3] data.frame(x=px,y=y, z=z) } # Linear Function distance <- function (terrain, observer) { sqrt((terrain$x-observer[1])^2+(terrain$y-observer[2])^2+(terrain$height-observer[3])^2) } LoS <- function(terrain, observer, maxVisibleDistance){ status = c() for (i in seq(1:nrow(terrain))) { if (observer[1] == terrain$x[i] && observer[2] == terrain$y[i]){ if(observer[3] >= terrain$height[i]){ if (terrain$dist2observer[i] > maxVisibleDistance){ status <- c(status,"yellow") }else{ status <- c(status,"green") } }else{ status <- c(status,"red") } }else{ # All points on line line <- linear(seq(from=min(observer[1],terrain$x[i]), to=max(observer[1],terrain$x[i]), by=0.1), observer, c(terrain$x[i],terrain$y[i],terrain$height[i])) # Terrain Height h <- height(line) # LoS Analysis aboveTerrain <- round((line$z-h),2) >= 0.00 visible <- !is.element(FALSE,aboveTerrain) if (visible){ # Second Rule if(terrain$dist2observer[i] <= maxVisibleDistance){ status <- c(status,"green") }else{ status <- c(status,"yellow") } }else{ status <- c(status,"red") } } } status } updatestatus <- function(status1,status2){ mergedstatus<-c() for(i in seq(length(status1))){ if (status1[i] == "green" || status2[i] == "green"){ mergedstatus <- c(mergedstatus,"green") }else if (status1[i] == "yellow" || status2[i] == "yellow"){ mergedstatus <- c(mergedstatus,"yellow") } else{ mergedstatus <- c(mergedstatus,"red") } } mergedstatus } ################## # Input ################## # Max visible distance maxVisibleDistance = 8 # Generate points with a step size of 0.1 x <- seq(from=-8,to=8,by=0.4) xygrid <- expand.grid(x=x, y=x) terrain <- data.frame(xygrid, height=height(xygrid) ) targetfunc<-function(observer){ #print(observer) m <- matrix(data=observer,ncol=2,byrow=TRUE) # Compute merged status of all observers mergedstatus <- rep("red",length(terrain$height)) for(oidx in seq(1:dim(m)[1])){ terrain$dist2observer <- distance(terrain, c(m[oidx,],7)) status <- LoS(terrain,c(m[oidx,],7),maxVisibleDistance) mergedstatus <- updatestatus(mergedstatus,status) } sum(mergedstatus=="green")/1681 } n <- 3 baselineValue <- 0.541344 previousObserver <- c(-1.32661956044593, 2.18870625357827) # List of observers (x1,y1,z1,x2,y2,z2) observers <- c(previousObserver,runif(2,-8,8)) while(targetfunc(observers) <= baselineValue){ observers <- c(previousObserver,runif(2,-8,8)) } print(observers) optim <- optim(observers, targetfunc, control=list(fnscale=-1,trace=5,REPORT=1))

### Results

Here is the coverage ratio for different number of observers after optimization

You can test covering more than 98% of whole terrain is not trivial by using only 6 random observers but requires “careful” choice of their layout.

Finally let’s check step by step improvement in coverage as we add more optimal observers.

## Single Observer

## Two Observers

## Three Observers

## Four Observers

## Five Observers

## Six Observers

Posted on September 24, 2011, in Uncategorized and tagged R, Spatial. Bookmark the permalink. 1 Comment.

Amazing work man, I saw the three more posts and they are very interesting, thank’s a lot

Precisely I have been searching about LOS in free software.