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

After my last post on multiple observers, I will discuss another topic related to multiple observers. The question is “What should be the optimal choice of 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:

1. Find the optimal layout for 1 observer and compute coverage ratio (best coverage for one observer)
2. Add another random observer ((uniform(-8,8),uniform(-8,8))) and compute the coverage for those two observers (random one and the best observer from Step 1).
1. If the new coverage is better than the coverage in Step 1, use this as the input of optimization solver
2. Otherwise repeat Step 2 to find a better coverage.
3. 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