Triangulation

Triangulation#

Reference of the math used to localise signals, objects, and emitters from multiple measurements. The discipline shows up in GNSS, RF direction-finding, sonar, multilateration of aircraft / ships, astronomical observation, and (more recently) acoustic event localisation and 5G positioning.

The umbrella term positioning covers several distinct problems, each with its own algorithms and error models:

Problem types#

Problem

Inputs

Triangulation

Two or more angle / bearing measurements from known stations to an unknown emitter (AoA, DF).

Trilateration

Two or more distance measurements from known stations to an unknown emitter (TOA / RSSI / GNSS).

Multilateration

Two or more time-difference-of-arrival (TDOA) measurements from known stations; classical aircraft surveillance.

Time-of-Arrival

Single station knows when the emission happened; range = c · ΔT.

Time-Difference

Pairs of stations measure relative arrival times; doesn’t require synchronized emission clock.

Doppler / FDOA

Frequency shift from a moving emitter / receiver localises along Doppler hyperboloids.

Hybrid

Combine angles + ranges + time differences; standard in modern GNSS / 5G positioning.

Core algorithms#

Algorithm

Notes

Linear least-square s

Classical solution for over-determined trilateration; linearise around an initial guess, solve normal equations.

Non-linear least-sq

uares Levenberg-Marquardt / Gauss-Newton; handles the non-linear range-from-position equations directly.

Weighted least-squa res

Per-measurement weights from variance estimates; the standard for heterogeneous measurements.

Kalman filter

Track a moving emitter by combining a state-transition model with sequential measurements. Linear systems / Gaussian noise.

Extended Kalman (EK F)

Linearise non-linear models around the current state; standard in GPS receivers.

Unscented Kalman (U KF)

Sigma-point linearisation; better than EKF on highly non-linear models.

Particle filter

Monte-Carlo state estimation; handles arbitrary noise / multimodal distributions; expensive.

Maximum likelihood

Maximize the joint log-likelihood across measurements; baseline for any noise model.

Closed-form solvers

Foy (1976) for TDOA; Bancroft (1985) for GPS; Smith-Abel for hyperbolic.

TDOA / Chan algorit hm

Closed-form 2-D TDOA solver; standard cellular E-911.

TDOA / Friedlander

  1. Pseudo-linear TDOA; iterative.

RSSI fingerprinting

Match a measured signal-strength vector to a database of known locations; common indoor positioning.

Pseudo-range solver

GNSS L1 C/A; iterative trilateration with clock-offset as a fourth unknown.

Differential GNSS / RTK

Carrier-phase ambiguity resolution (LAMBDA method); centimetre accuracy.

PPP (Precise Point

Pos.) Single-receiver, no base station; uses precise orbits / clocks.

SLAM

Simultaneous Localisation and Mapping; the robotics hybrid of mapping + positioning.

Cooperative localis

ation Stations measure each other; solves the joint system. Multi-robot, sensor networks.

Direction finding ( DF)

Watson-Watt (amplitude); Doppler DF; correlative interferometry; MUSIC / ESPRIT for high-resolution.

Music / ESPRIT

Subspace-based DOA estimation; super-resolution.

Beamforming

Phased-array sums; Bartlett (conventional), Capon (MVDR), MUSIC (subspace).

Apollonius / Pappus

Classical geometric circle intersections; underlies analytic trilateration.

Error models#

Concept

Notes

GDOP / HDOP / VDOP

Geometric Dilution of Precision; how station geometry amplifies measurement error.

CRLB

Cramér-Rao Lower Bound; theoretical floor on unbiased estimator variance for given measurement noise.

Multipath

Reflections create false ranges; mitigated by narrow correlator, antenna design, time-tagging.

NLOS

Non-line-of-sight bias; longer measured range than true.

Clock bias

Receiver clock offset from system time; one extra unknown in pseudorange solutions.

Atmospheric (GNSS)

Ionospheric + tropospheric delay; modeled or differenced away.

Practical stacks#

Domain

Tools

GNSS / GPS

RTKLIB, GLAB, NRCan PPP, GPSTK.

SDR / RF DF

KrakenRF / kerberosSDR, GNU Radio, dragOS, OpenWebRX, gr-doa.

Multilateration

OpenSky, dump1090 + multilat, LibreATCS.

Indoor RF

Kismet WiFi, BLE beacons, DecaWave UWB.

SLAM

ROS / ROS2, Cartographer, ORB-SLAM3, RTAB-Map, hdl-graph-slam.

Underwater / sonar

AUV positioning; LBL / USBL / SBL acoustic systems.

Astronomy

AstroPy, Skyfield, IAU SOFA library.

Filtering libraries

FilterPy (Python), Kalmanif (C++), ROS robot_localization.

Optimization

Ceres, GTSAM, g2o for non-linear LS / SLAM back-end.

Tracking and prediction#

Static positioning answers “where is the emitter now?”. Tracking answers “where will it be next, given a sequence of noisy measurements?”. The state-space toolkit underneath:

Concept

Notes

State vector

Position + velocity (CV model), + acceleration (CA), + turn-rate (CT). Augmented with sensor biases as needed.

Motion models

CV (constant velocity), CA (constant acceleration), CT (constant turn), Singer (correlated random acceleration), IMM (interacting multiple models).

Measurement model

How the true state maps to what the sensor reports (range, bearing, range-rate, image pixel, …).

Process noise (Q)

Captures motion-model mismatch; tune to expected maneuver intensity.

Measurement noise (

  1. Sensor variance; per-sensor calibration.

Innovation

Measurement minus prediction; its statistics validate the model.

Mahalanobis dist.

Distance metric in covariance-weighted space; the gating threshold for measurement association.

Data association

Decide which measurement updates which track. NN, GNN, PDA (probabilistic), JPDA (joint), MHT (multiple hypothesis), MCMC-DA.

Track management

Initialisation, confirmation, deletion; M/N rules.

Estimators (filtering / smoothing):

Algorithm

Notes

Kalman filter

Linear systems + Gaussian noise; closed-form Bayes-optimal.

Extended Kalman

EKF; linearises non-linear models around the current state. Standard in GPS, AHRS, sonar tracking.

Unscented Kalman

UKF; sigma-point linearisation; better than EKF for strongly non-linear models, similar cost.

Cubature Kalman

CKF; cubature-rule sigma points; close cousin of UKF.

Information filter

Algebraic dual of Kalman; useful when many sensors fuse into one state.

Square-root forms

SR-KF / SR-UKF; numerically stable variants.

Particle filter

Monte-Carlo posterior; arbitrary noise / multimodal; expensive but very general.

Rao-Blackwellised PF

Hybrid PF + KF; exploit the linear-Gaussian sub-state.

Gaussian sum filt.

Mixture of Kalmans; multimodal estimate.

Forward-backward

Smoothing pass after filtering; RTS smoother for Kalman models.

Bayesian RNN

Modern: LSTM / Transformer with explicit uncertainty for trajectory prediction.

Sequence-to-seq.

Trajectory prediction from past trajectory plus context (Social-LSTM, Social-GAN, Trajectron++).

Diffusion models

Probabilistic trajectory forecasting (2024+).

Multi-target / multi-sensor:

Algorithm

Notes

GNN (Global NN)

Hungarian / Munkres assignment of measurements to tracks.

PDA / JPDA

Bayesian soft assignment in clutter.

MHT

Maintains multiple hypotheses over data-association ambiguities; pruned by score.

PHD filter

Probability-Hypothesis-Density; intensity-based; FISST.

CPHD, GLMB, LMB

Random-finite-set descendants of PHD.

Track-to-track

Fuse tracks from different sensors into a system track.

fusion

(covariance intersection, Bar-Shalom-Campo).

JIPDA

Joint integrated PDA; handles existence + association.

Sensor scheduling

Which sensor to task next to minimize expected error (information gain).

Trajectory prediction (planning / forecasting):

Algorithm

Notes

Kinematic propag.

Roll the motion model forward; the cheap baseline.

Constant turn / Sin

ger Use parametric motion model + assumed accelerations.

IMM (Interacting

Bank of motion models with mode probabilities; switching

Multiple Models)

between cruise / turn / brake.

Behavior models

Map / lane / waypoint constraints (vehicles, pedestrians).

Inverse RL / IRL

Infer the cost function the target is optimizing; predict from that.

Social-LSTM /

Pedestrian / vehicle trajectory NNs that condition on

Social-GAN / Trajectron++

neighbor positions.

Multi-modal NN

Predict a distribution over future paths (mixture density, diffusion).

Conformal pred.

Calibrated prediction intervals around any point estimate.

Performance metrics:

Metric

Notes

RMSE / MAE

Per-time-step position error.

NEES / NIS

Normalized state / innovation squared; consistency tests for filters.

OSPA / OSPA(2)

Optimal Subpattern Assignment; multi-target metric that penalises both location error and miscount.

GOSPA

Generalised OSPA; current preferred metric.

ADE / FDE

Average / Final Displacement Error; trajectory-prediction metrics.

Track purity

Fraction of measurements correctly associated to truth.

Tooling:

  • FilterPy, KF / EKF / UKF / particle filters (Python).

  • Stone Soup, DSTL’s open-source tracking framework; full multi-sensor / multi- target stack.

  • pykalman, simpler KF / EKF.

  • pomegranate, HMMs + general probabilistic models.

  • GTSAM, Ceres, g2o, non-linear optimization back-ends used in factor-graph SLAM.

  • OpenCV trackers, visual single-object trackers (KCF, MOSSE, MIL, CSRT).

  • Norfair, ByteTrack, BoT-SORT, OC-SORT, modern multi-object tracking on top of object detectors.

  • Trajectron++, pedestrian / vehicle trajectory prediction.

Operator notes#

  • Two stations are not enough in 2-D unless the geometry is benign; over-determined systems (4+ stations) give residuals to detect bad measurements (RAIM in GNSS).

  • TOA needs a synchronized clock at every station (GPS- disciplined oscillator typical); TDOA only needs the difference of clocks, much cheaper.

  • Geometry matters more than measurement quality, low GDOP rejects far more error than a small variance reduction.

  • Multi-frequency (L1+L2+L5 GNSS, dual-band SDR) breaks ionospheric delay and lifts accuracy from meters to centimetres.

  • Hybrid sensors, IMU + GNSS, IMU + camera (visual- inertial), GNSS + cellular, the modern standard in mobile / vehicular / drone applications.

  • Authorization, direction-finding hardware is regulated in many jurisdictions; receive-only is generally legal, transmit-back / spoofing is not.

References#

Contents