# Trilateration with unknown fixed points

I am able to measure my distance to a set of (about 6 or 7) fixed but unknown points from many positions.

The difference in position between measurements is also unknown.

I believe that I should be able to work out the relative position of the fixed points, and therefore where I measured from and the path I took.

I have looked at the wiki page for trilateration, but it only gives examples working from known points.

Any help?

-
Let's say the distances are 1,2,3,4,5,6. Now construct the following sets of points in $\mathbb{R}^2$: you are on position $(0,0)$, the next point is on position $(1,0)$, the next one on position $(2,0)$, etc... on the other hand, the following is also compatible with your distances: $(0,0),(0,1),(2,0),(0,3),(4,0),(0,5),(6,0)$. See? – Raskolnikov Dec 12 '10 at 12:25
I understand that, but it doesn't get me any closer to a solution. I will need to use differences in the distance sets of two or more readings. – FlightOfStairs Dec 12 '10 at 13:49

For each distance measured, you can write an equation for the distance between that point on your path and that fixed point, both of which are unknown. In two dimensions (on a flat plane), each unknown point has two unknown coordinates. If you have $n$ fixed points and you measure from $k$ points on your path, you will have $nk$ distances and equations and $2n+2k$ unknowns. As long as $nk\ge 2n+2k$, this should yield a system that can be solved (if the distances are exact), but it probably helps to have $nk$ be more than $2n+2k$ because the system when $nk=2n+2k$ might have multiple solutions (because the equations are nonlinear). (If you are working in three dimensions, then $2n+2k$ changes to $3n+3k$.)

-
Since the whole setup is invariant under isometric transformations, there are three degrees of freedom which you can't conclude from the variables. Fixing them in an arbitrary way corresponds to an arbitrary choice of coordinate system. It makes sense to think of these three degrees of freedom as origin and orientation of the coordinate system. This newer question referenced the one here, which is how I noticed your answer. – MvG Oct 14 '14 at 7:25

I'm elaborating on the answer Isaac already gave, so I'll adopt his notation. I'm posting a second answer to elaborate the point of isometric transformations, but also because the question has been asked again and the author of that newer question found the existing answer insufficient.

Suppose you have $n$ fixed points and perform $k$ distance measurements to all of these, taken from different points. Also suppose that you are working in the plane, althgough the ideas can be easily generalized to 3D space. Let's assume the fixed point with index $i$ is at position $(a_i,b_i)$ and the measurements with index $j$ were taken from position $(x_j,y_j)$, then the equations are of the form

$$(a_i-x_j)^2 + (b_i-y_j)^2 = d_{ij}^2$$

where $d_{ij}$ is the distance you measured to fixed point $i$ from position $j$ along the trajectory. So you have $2n$ variables $a_i,a_j$ and $2k$ variables $x_i,y_i$ together with $n\cdot k$ equations.

But the whole setup is invariant under isometric transformations. Which means you can't know the origin or orientation of your coordinate system, since that coordinate system is completely arbitrary. Therefore you might simply fix some coordinate system, by choosing $x_1=y_1=y_2=0$. So the origin of the coordinate system is defined as your starting point, and the $x$ axis of the coordinate system is the direction from the first to the second point of your trajectory. This adds three more equations. (If you were operating in 3D instead of 2D, then you'd end up with 6 parameters you may choose arbitrarily, three for position and three for orientation.)

A system of $n\cdot k+3$ equations with $2n+2k$ will often have a finite number of solutions if $2n+2k=n\cdot k+3$. At least if the equations are sufficiently independent. If the equations were linear, that solution would be unique, but as the equations are non-linear, there may be multiple solutions. If you have more than the required number of equations, that might help you pick one of these. I'll not discuss techniques of how to solve systems on non-linear polynomial equations, but I suggest you let some computer algebra system or some numerical tool designed for the task handle that.

Of course, if you have more equations than absolutely required, and if your measurements are subject to some error (measurement error, rounding error, …) then you may end up with no matching solution at all. So you'll want the solution which is closest to your measurements, even though it doesn't exactly reproduce the observed measurements. This would place the problem in the domain of unconstrained non-linear optimization. You'd definitely want to tackle this numerically, and would be well advised to use a tool designed for that task.

-
Ok, trying to make sure I understand this. In a situation with perfect measurements this requires at least two sets of (x,y)'s to determine the arbitrary positions of each (a,b)? and if you say x1=y1=y2=0 then you must know the x2 (the distance between the first two points) before you can calculate all of the (a,b) positions? So essentially you must use some other method to get the distance from the first location change, then can use the systems of equations to calculate future location changes? – jp36 Oct 14 '14 at 20:55
Also, there will be measurement/calculation error. So when you say I want to tackle this numerically does that mean I'd still set up the same system of equations but I'd use a numerical solver tool to determine the solution instead of some simple solving method? – jp36 Oct 14 '14 at 20:59
@jp36: If you have $n=3$ fixed points (which is the absolute minimum), then $2n+2k=nk+3$ simplifies to $k=3$, so you need to measure distances from three different positions. For larger $n$ the resulting $k$ will be not an integer, so you'd round that up and will end up in the case of “more equations than absolutely required”. The distance between the first two points, $x_2$, is just one of the variables of your system of equations; you don't neccessarily have to determine that before the others. – MvG Oct 15 '14 at 6:12
@jp36: When you have errors, “solving” is the wrong term, “approximating” and “optimizing” would fit. You'd try to minimize $$\sum_{i=1}^n\sum_{j=1}^k\left((a_i-x_j)^2+(b_i-y_j)^2-d_{ij}^2\right)^2$$ (at least in a least squares approximation) to find the solution which best matches your obervations. – MvG Oct 15 '14 at 6:14
You mention using a tool designed for this task, I assume you mean something like matlab. I am trying to program this and thus I need some library or algorithm to use. I am having trouble finding finding what to use as I only have a high level understanding of most of this. I have been searching using key words such as "least squares approximation" and "unconstrained non-linear optimization". Does (en.wikipedia.org/wiki/NEWUOA) seem like something that would be appropriate to use? Or should I be looking for libraries that handle "non-linear programming." Sorry for my ignorance. – jp36 Nov 11 '14 at 22:16