# Trilateration with bounds?

This is a question I posted on Stack Overflow, but I figured you guys would have a better answer for me, so:

I'm in need of help solving an issue, the problem came up doing one of my small robot experiments, the basic idea, is that each little robot has the ability to approximate the distance, from themselves to an object, however the approximate I'm getting is way too rough, and I'm hoping to calculate something more accurate.

So:
Input: A list of vertex (v_1, v_2, ... v_n), a vertex v_* (robots)
Output: The coordinates for the unknown vertex v_* (object)

Each vertex v_1 to v_n's coordinates are well known (supplied by calling getX() and getY() on the vertex), and its possible to get the approximate range to v_* by calling; getApproximateDistance(v_*), function getApproximateDistance() returns two variables variables, that is; minDistance and maxDistance. - The actual distance lies in between these.

So what I've been trying to do to obtain the coordinates for v_*, is to use trilateration, however I can't seem to find a formula for doing trilateration with limits (lower and upperbound), so that's really what I'm looking for (not really good enough at math, to figure it out myself).

Note: is triangulation the way to go instead?
Note: I would possibly love to know a way to do, performance/accuracy trade-offs.

An example of data:

[Vertex . getX() . getY() . minDistance . maxDistance]
[v_1  .  2       .  2       .  0.5          .  1  ]
[v_2  .  1       .  2       .  0.3          .  1  ]
[v_3  .  1.5     .  1       .  0.3          .  0.5]


Picture to show data: http://img52.imageshack.us/img52/6414/unavngivetcb.png

It's obvious that the approximate for v_1 can be better, than [0.5; 1], as the figure that the above data creates is small cut of a annulus (limited by v_3), however how would I calculate that, and possibly find the approximate within that figure (this figure is possibly concave)?

Okay, so I hope that wasn't programmish, and you'll figure how to help me anyways :)

-
It might help if you told us what the word "trilateration" means. I've never seen it before. –  Gerry Myerson Jun 1 '11 at 13:04
en.wikipedia.org/wiki/Trilateration –  Skeen Jun 1 '11 at 14:30
Limits in title + calculus tags seems to give a different picture. Going by the wiki link on Trilateration, geometry seems more apt. –  Aryabhata Jun 1 '11 at 17:50
ah, obviously, sorry. –  Skeen Jun 1 '11 at 19:01

In general this is not easy.

What you really want to do is optimise subject to constraints. To do so, you need a function to optimise, for example some combination of how close a point's distances are to the middle of the ranges. The constraints are the maximum and minimum distances. So in your particular example, you might start at the point (1.5, 1.4) and then see which direction will improve the function you are trying to optimise.

A problem with such an approach is that the feasible region may not be continuous. For example, in the following diagram you want to be in one or other of the grey areas.

Added What you need is a function to optimise. For example, you might try minimising

$$\sum_i (\text{distance}_i - \text{mindistance}_i)(\text{distance}_i - \text{maxdistance}_i)$$

and then check whether the resulting point is within the feasible region. For example in R, the following does so using the data in your example and starting the search at $(0,0)$

centres_x <- c(2,   1,   1.5)
centres_y <- c(2,   2,   1  )
mindist   <- c(0.5, 0.3, 0.3)
maxdist   <- c(1,   1,   0.5)

dist <- function(x,y) {sqrt( (x-centres_x)^2 + (y-centres_y)^2 )}

cost <- function(p){
x <- p[1]
y <- p[2]
sum( (dist(x,y)-mindist)*(dist(x,y)-maxdist) )
}

o <- optim(c(0,0), cost)


It produces the results

> o$par [1] 1.438917 1.456083 > dist(o$par[1],o$par[2]) > mindist [1] TRUE TRUE TRUE > dist(o$par[1],o$par[2]) < maxdist [1] TRUE TRUE TRUE  i.e. close to the point$(1.439,1.456)\$, which is within the permitted area.

I would expect this sort of approach to perform reasonably well in most real-world problems (it can even give a moderately sensible result when the annuli do not in fact overlap), though as I have shown in the diagram, it cannot be guaranteed to find the global optimum in every case.

-
So.. I get what your saying, however I don't see how that brings me closer to solving my issue? –  Skeen Jun 1 '11 at 16:34
@Skeen: I have added a worked example –  Henry Jun 1 '11 at 18:37
@Henry: May I ask what that 'code' is written in? - So I can play with it –  Skeen Jun 1 '11 at 18:59
@Skeen: R –  Henry Jun 1 '11 at 19:31
@Henry got any idea, how I would achieve anything alike this in C/Java/D/Python/Lua, ect? - Never used R –  Skeen Jun 1 '11 at 21:51