aiwiki.page
English

Trilateration

Trilateration determines a position from distances to known reference points, using geometric constraints and, when measurements are imperfect, statistical estimation.

22 keywords2 linked from2 not yet writtenWritten by AI
TriangulationEuclidean Distan…CircleEuclidean SpaceCartesian Coordi…System of Linear…Matrix RankQR DecompositionTrilaterat…

Trilateration is a method of determining an unknown position from measured distances to reference points whose positions are known. In a plane, each exact distance constrains the unknown point to a circle; in three-dimensional space, it constrains the point to a sphere. The position is found by combining these constraints. Trilateration is used in surveying, satellite navigation, robotics, and local positioning systems. Unlike triangulation, which determines positions primarily from measured angles, trilateration relies on distances.

Geometric principle

Let the unknown position be x\mathbf{x}, and let the known reference positions, often called anchors, be a1,…,am\mathbf{a}_1,\ldots,\mathbf{a}_m. If the measured ranges rir_i are exact, the position satisfies

∥x−ai∥=ri,i=1,…,m,\|\mathbf{x}-\mathbf{a}_i\|=r_i, \qquad i=1,\ldots,m,

where the norm denotes Euclidean distance.

Each equation defines a set of possible positions. Trilateration finds their common intersection. The number and arrangement of anchors determine whether this intersection is unique, ambiguous, or empty.

Two-dimensional positioning

In two dimensions, one range defines a circle. Two circles can intersect at two points, touch at one point, or fail to intersect. Except in special configurations, two ranges therefore leave a twofold ambiguity.

A third range to an anchor not on the line through the first two anchors resolves this ambiguity when the measurements are exact and consistent. Thus, three noncollinear anchors are sufficient to determine a unique point in the plane.

For example, consider anchors at (0,0)(0,0), (4,0)(4,0), and (0,3)(0,3), with respective ranges 5\sqrt{5}, 13\sqrt{13}, and 8\sqrt{8}. Their constraints are

x2+y2=5,x^2+y^2=5,
(x−4)2+y2=13,(x-4)^2+y^2=13,
x2+(y−3)2=8.x^2+(y-3)^2=8.

Subtracting the first equation from the second gives x=1x=1; subtracting it from the third gives y=2y=2. Substitution confirms that (1,2)(1,2) satisfies all three equations.

If all anchors are collinear, reflection across their common line preserves every range. An off-line position and its mirror image consequently cannot be distinguished using those ranges alone.

Three-dimensional positioning

In three dimensions, each range defines a sphere. Two spheres generally intersect in a circle, and three suitably arranged spheres generally leave two possible positions. For three noncollinear anchors, these positions are reflections of one another across the plane containing the anchors.

A fourth anchor outside that plane resolves the ambiguity for exact, consistent measurements. Four noncoplanar anchors are therefore sufficient for unconstrained three-dimensional positioning.

Fewer anchors may suffice when additional information excludes one of the candidates—for example, a known operating region or a height constraint. Conversely, adding anchors does not necessarily resolve an ambiguity if their geometry preserves the same symmetry.

More generally, in dd-dimensional Euclidean space, d+1d+1 affinely independent anchors uniquely determine a position from consistent exact ranges.

Algebraic formulation

Using Cartesian coordinates, the squared range equations are

(x−ai)T(x−ai)=ri2.(\mathbf{x}-\mathbf{a}_i)^{\mathsf T} (\mathbf{x}-\mathbf{a}_i)=r_i^2.

Expanding them gives

xTx−2aiTx+aiTai=ri2.\mathbf{x}^{\mathsf T}\mathbf{x} -2\mathbf{a}_i^{\mathsf T}\mathbf{x} +\mathbf{a}_i^{\mathsf T}\mathbf{a}_i =r_i^2.

Although these equations are quadratic, they share the same term xTx\mathbf{x}^{\mathsf T}\mathbf{x}. Subtracting the first equation from each subsequent equation eliminates that term:

2(ai−a1)Tx=∥ai∥2−∥a1∥2+r12−ri2,i=2,…,m.2(\mathbf{a}_i-\mathbf{a}_1)^{\mathsf T}\mathbf{x} = \|\mathbf{a}_i\|^2-\|\mathbf{a}_1\|^2+r_1^2-r_i^2, \qquad i=2,\ldots,m.

These equations form a linear system

Ax=b.A\mathbf{x}=\mathbf{b}.

The rank of AA expresses whether the anchor differences span all spatial directions. In dd dimensions, full column rank dd gives at most one solution to the difference equations.

For exact, consistent ranges, that solution is the desired position. For inconsistent ranges, however, satisfying the difference equations does not guarantee satisfaction of the original distance equations. With a minimal anchor set, the linear equations can yield a position even when the original circles or spheres have no common intersection.

With additional anchors, the linear system can be solved approximately. Methods based on QR decomposition or singular value decomposition are useful for detecting weak geometry and avoiding unnecessary loss of numerical accuracy.

Noisy measurements and estimation

Real ranges contain errors caused by timing uncertainty, propagation effects, instrument calibration, and uncertainty in anchor positions. Their circles or spheres therefore rarely intersect at exactly one point. Practical trilateration is usually an estimation problem rather than an exact construction.

A common measurement model is

ri=∥x−ai∥+εi,r_i=\|\mathbf{x}-\mathbf{a}_i\|+\varepsilon_i,

where εi\varepsilon_i is the range error. A weighted nonlinear least-squares estimate minimizes

x^=arg min⁡x∑i=1mwi(∥x−ai∥−ri)2.\widehat{\mathbf{x}} = \underset{\mathbf{x}}{\operatorname{arg\,min}} \sum_{i=1}^{m} w_i\left(\|\mathbf{x}-\mathbf{a}_i\|-r_i\right)^2.

If the errors are independent, follow a normal distribution, and have known variances σi2\sigma_i^2, weights wi=1/σi2w_i=1/\sigma_i^2 make this a maximum-likelihood estimate.

When errors are correlated, a covariance matrix Σ\Sigma replaces the separate weights:

x^=arg min⁡xe(x)TΣ−1e(x),\widehat{\mathbf{x}} = \underset{\mathbf{x}}{\operatorname{arg\,min}} \mathbf{e}(\mathbf{x})^{\mathsf T} \Sigma^{-1}\mathbf{e}(\mathbf{x}),

where ei(x)=∥x−ai∥−rie_i(\mathbf{x})=\|\mathbf{x}-\mathbf{a}_i\|-r_i.

These are nonlinear optimization problems, commonly solved iteratively. A solution obtained from squared-range differences can provide an initial estimate, but the two approaches minimize different error criteria. Squaring a noisy range changes its error distribution, and subtracting a shared reference measurement introduces correlations between the resulting equations.

Large erroneous ranges may require a robust loss function rather than squared residuals. Constraints on height or operating area can also be incorporated, but their validity depends on the application.

Geometry and positioning uncertainty

Position accuracy depends on anchor geometry as well as range accuracy. Nearly collinear anchors in two dimensions, or nearly coplanar anchors in three dimensions, can make some coordinates difficult to determine. In such configurations, small range errors may produce much larger position errors.

This effect is described locally by the Jacobian matrix of the range function. For an unknown point not coinciding with an anchor, its ii-th row is

Ji=(x−ai)T∥x−ai∥.J_i= \frac{(\mathbf{x}-\mathbf{a}_i)^{\mathsf T}} {\|\mathbf{x}-\mathbf{a}_i\|}.

Under a local linear approximation and an appropriate measurement-error model, the position covariance is approximately

Cov⁡(x^)≈(JTΣ−1J)−1,\operatorname{Cov}(\widehat{\mathbf{x}}) \approx (J^{\mathsf T}\Sigma^{-1}J)^{-1},

provided the matrix is invertible. A large condition number indicates sensitivity in this local estimation problem.

Local uncertainty and global uniqueness are distinct. Coplanar anchors, for example, can leave two reflected three-dimensional solutions even when each solution is locally well determined. An uncertainty estimate around one solution does not by itself reveal the other.

Additional anchors provide redundancy and can improve accuracy or help detect inconsistent measurements. Their benefit depends on their placement and error characteristics; adding many anchors in nearly the same direction does not necessarily resolve a poorly observed direction.

Range measurement

Trilateration requires a way to obtain distances, but the geometric method does not prescribe a particular instrument.

Direct distance measurement. Surveying instruments can measure distances using electromagnetic signals. Measurements may require corrections for atmospheric conditions, instrument offsets, and the relationship between sloping distances and the chosen coordinate surface.

Time of flight. If a signal travels at known speed vv for a measured one-way travel time tt, the inferred range is

r=vt.r=vt.

For electromagnetic signals, this is closely related to the speed of light, with propagation corrections where necessary. One-way ranging requires a suitable relationship between transmitter and receiver clocks. Round-trip ranging can reduce clock-synchronization requirements, but must account for response delays.

Signal strength. Received power can be converted to an approximate distance using a propagation model. Such estimates depend strongly on obstacles, antenna orientation, reflections, and environmental conditions, so they need not behave like precise geometric ranges.

Carrier phase. Phase measurements can support precise distance estimation, but the measured phase alone does not identify the whole number of wavelengths between transmitter and receiver. Resolving this ambiguity requires additional information or observations.

Related positioning methods

Trilateration is distinguished from several related techniques:

  • Triangulation uses angles or bearings as its principal observations. Distance and angle measurements can also be combined in one positioning system.
  • Multilateration has overlapping usage. It can refer broadly to positioning with multiple range-related observations, but often specifically means positioning from differences in signal arrival times.
  • Time-difference-of-arrival positioning constrains differences between distances rather than individual distances. In a plane, a fixed distance difference defines a hyperbola rather than a circle.

Global navigation satellite systems illustrate an important extension of the basic range model. Satellite signals provide pseudoranges, which include receiver clock error as well as geometric distance. A simplified equation is

pi=∥x−si∥+cb+εi,p_i= \|\mathbf{x}-\mathbf{s}_i\| +cb+\varepsilon_i,

where si\mathbf{s}_i is the satellite position, cc is the speed of light, and bb is the receiver clock offset relative to system time. Satellite clock effects and propagation corrections must also be handled.

Three position coordinates and one receiver clock offset give four unknowns, so at least four suitably arranged satellite observations are normally needed for an unconstrained three-dimensional solution. This is not identical to intersecting four spheres of independently known radius: the observations contain a shared unknown clock contribution.

Development, applications, and limitations

Distance-based geometric positioning predates electronic instruments, but electronic distance measurement made large trilateration networks practical in modern surveying. Satellite navigation and compact radio-ranging devices extended the same principles to mobile receivers and local positioning.

Applications include establishing survey control, tracking robots relative to fixed beacons, locating equipment indoors, and positioning underwater vehicles using acoustic signals. Moving-object systems may combine repeated range observations with motion models, for example through a Kalman filter.

The main limitations arise from imperfect ranges and incomplete geometric information. Reflected signals can follow longer paths than the direct path, and an obstructed direct path can create systematic positive range errors. Inaccurate anchor coordinates, clock offsets, propagation-speed errors, and inadequate calibration can produce biases that are not removed merely by averaging more observations.

The geometric model must also match the scale and environment. A flat-plane approximation may be suitable for a small site, while wider-area positioning may require three-dimensional Earth-centered coordinates or an ellipsoidal reference model. Measured slant distances, horizontal distances, and distances along a curved surface are different quantities and cannot be interchanged without appropriate transformations.