21
21.1. Trilateration by distance measurements
 |
|
|
In many applications such as GPS it is of interest to infer the location of an emitter (for example, a cell phone) from the measurement of distances to known points. These distances are obtained by estimating the differences in time of arrival of a wave front originating from the emitter. In trilateration, only three points are used. We then have to find the intersection of three spheres. The problem can then be reduced to solving a linear equation followed by a quadratic equation in one variable. The multilateration problem, which allows for more than three points, provides more accurate measurements. (Source.) |
|
Denote by [latex]x^i[/latex], [latex]i=1,2,3[/latex] the three known points and by [latex]R_i[/latex] the measured distances to the emitter. Mathematically the problem is to solve, for a point [latex]x[/latex] in [latex]\mathbb{R}^3[/latex], the equations
[latex]\begin{align*} ||x-x^i||_2^2 &= R_i^2, \quad i=1,2,3. \end{align*}[/latex]
We write them out:
[latex]\begin{align*} x^Tx - 2x^Tx^i + ||x^i||_2^2 &= R_i^2, \quad i = 1,2,3. \end{align*}[/latex]
Let [latex]t := (1/2)x^Tx[/latex]. The equations above imply that
[latex]\begin{align*} t - x^Tx^i = \gamma_i := (1/2)(R_i^2-||x^i||_2^2), \quad i = 1,2,3. \end{align*}[/latex]
Using matrix notation, with [latex]X = [x_1,x_2,x_3][/latex] the matrix of points, and [latex]\mathbf{1}[/latex] the vector of ones:
[latex]\begin{align*} X^Tx = t \mathbf{1} - \gamma. \end{align*}[/latex]
Let us assume that the square matrix [latex]X[/latex] is full-rank, that is, invertible. The equation above implies that
[latex]\begin{align*} x = x(t) := X^{-T}( t \mathbf{1} - \gamma). \end{align*}[/latex]
In words: the point lies in a line passing through [latex]x^0 := -X^{-T}\gamma[/latex] and with direction [latex]v:=X^{-T}\mathbf{1}[/latex].
We can then solve the equation in
[latex]\begin{align*} x(t)^Tx(t) &= 2t. \end{align*}[/latex]
This equation is quadratic in [latex]t[/latex] :
[latex]\begin{align*} (v^Tv) t^2 + 2 ((v^Tx^0) -1) t + ||x^0||_2^2 = 0 \end{align*}[/latex]
and can be solved in closed-form. The spheres intersect if and only if there is a real, non-negative solution [latex]t[/latex]. Generically, if the spheres have a non-empty intersection, there are two positive solutions, hence two points in the intersection. This is understandable geometrically: the intersection of two spheres is a circle, and intersecting a circle with a third sphere produces two points. The line joining the two points is the line [latex]\{ x(t): t \in \mathbb{R} \}[/latex], as identified above.
21.2. Estimation of traffic flow
 |
|
|
The basic traffic flow estimation problem involves inferring the amount of cars going through links based on information on the amount of cars passing through neighboring links. |
|
For the simple problem above, we simply use the fact that at each intersection, the incoming traffic has to match the outgoing traffic. This leads to the linear equations:
[latex]\begin{align*} \text{Intersection A:} && x_4 + 610 &= x_1 + 450, \\ \text{Intersection B:} && x_1 + 400 &= x_2 + 640, \\ \text{Intersection C:} && x_2 + 600 &= x_3, \\ \text{Intersection D:} && x_3 &= x_4 + 520. \end{align*}[/latex]
We can write this in matrix format: [latex]Ax = y,[/latex] with
[latex]\begin{align*} A &= \left( \begin{array}{cccc} -1 & 0 & 0 & 1 \\ 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & -1 \\ \end{array} \right),\hspace{-1.5cm} & y &= \left( \begin{array}{c} -160 \\ 240 \\ -600 \\ 520 \\ \end{array} \right). \end{align*}[/latex]
The matrix [latex]A[/latex] is nothing else than the incidence matrix associated with the graph that has the intersections as nodes and links as edges.
