M8-T5 — GPS-Denied Localization

Learning objectives

After this lesson, you should be able to:

• Quantify how quickly inertial and wheel dead reckoning drift and why.
• Describe the main aids when GNSS is lost: map matching, odometry, absolute place recognition and radio or magnetic beacons.
• Explain how an error-state filter fuses aids and what is and is not observable.
• Identify what is established practice and what is active research, with the primary references.

The problem and the intuition

Walk across a dark room with your eyes shut. Counting steps (dead reckoning) works for a while and then you drift; the longer you walk, the more you are off. If you can touch a wall now and then (an aid), you know where you are again. Navigation without GNSS is this: a drifting internal estimate and occasional corrections from whatever the environment offers.

The drift of the internal estimate depends brutally on the sensor. An accelerometer bias b integrates twice: position error grows as ½ b t². A bias of 0.05 m/s² (a consumer MEMS part) gives 90 m after one minute. A gyroscope bias tilts the gravity compensation and makes it worse. Wheel odometry grows linearly with distance rather than quadratically with time, but slips. Everything that follows is about bounding that drift with something that does not drift: a map, a landmark, a beacon.

Dead reckoning drifts without bound; an aid must supply an absolute or drift-free reference. The design question is which aids exist in your environment, and how they fail.

The toolbox: dead reckoning, aids, fusion

Problem. Maintain a pose estimate with bounded error in the world frame for a robot that has no GNSS, using onboard sensors, prior maps and the environment.

Assumptions. The robot has an IMU and wheel or visual/lidar odometry; some prior information about the environment exists (a map, beacons, terrain data) or can be built on the way (SLAM); the aiding sources have independent errors.

Established: dead reckoning and its drift

Better inertial sensors (tactical and navigation grade) reduce b by orders of magnitude at cost and size. See Groves (2013) for the full error model.

Established: aids

Established: fusion with an error-state filter

The standard architecture is an (extended or error-state) Kalman filter whose prediction step integrates the IMU and whose update steps take each aid as a measurement with its own covariance (M3-T1, M6-T6; Groves, 2013). The covariance grows between aids and shrinks at each one. The filter is only as good as the honesty of the covariances (M8-T8: check NEES).

Observability

An aid that gives only relative information (odometry) leaves the global position and yaw unobservable and the error grows without bound; an aid that gives an absolute position bounds it; one that gives only range or bearing to a known point bounds it in the geometry that the measurements span. Choose aids so that the unobservable directions are covered by at least one absolute source (M6-T6).

Active research

• Cross-view and map-based localisation against satellite imagery, aerial maps or HD maps with learned descriptors (for example Levinson and Thrun, 2010, for probabilistic LiDAR intensity maps; more recent learned approaches for aerial-to-ground matching).
• Robust fusion under jamming and spoofing: detecting that GNSS is corrupted, and falling back to other aids without a jump.
• Magnetic and terrain navigation for aerial and underwater vehicles, with data-driven models.
• Certifiable and consistent fusion of many heterogeneous, intermittent aids; the field relies largely on tuning.

b_a, b_g

accelerometer and gyroscope bias.

aid

a measurement that corrects dead reckoning using an external reference.

NLOS

non-line-of-sight: a radio path blocked so that the measured range is biased long.

error-state filter

a Kalman filter on the small error of a nominal state; standard for INS.

A worked example: how long can the robot go without help?

1. Drift budget. A robot may be off by at most 2 m before it risks leaving its corridor. With an uncompensated accelerometer bias of 0.05 m/s² the position error is ½ × 0.05 × t² = 2 m at t = √(2 × 2 / 0.05) = 8.9 s. With a bias of 0.005 m/s² it is 28 s. At t = 60 s: 90 m and 9 m, as in the figure.
2. Wheel odometry. With a 1% scale error, the error after 100 m is 1 m, increasing linearly: much better than the pure inertial case for ground robots, until a wheel slips or the floor is soft. A fused estimate with the IMU’s heading bounds the heading error and so the sideways drift.
3. A beacon fix. A UWB anchor at a known position gives a range of 12.4 m with σ = 0.1 m. The measurement constrains the robot to a circle around the anchor; it corrects the component of the position error along the line to the anchor and leaves the tangential component unchanged. Two anchors at different bearings fix a 2D position; with three, the NLOS outlier of one can be detected by inconsistency.
4. Filter consistency. The filter predicts a position standard deviation of 0.3 m at an aid; the actual error at the aid is 1.2 m. The normalised innovation squared is (1.2/0.3)² = 16 for one degree of freedom, far above the 95% chi-squared threshold of 3.84: the filter is over-confident (or the aid is wrong), and should reject the measurement or inflate its covariance (M2-T7). Accepting it blindly can pull the estimate onto a wrong place.
5. Map matching as an aid. A lidar scan matched against a prior map yields a pose with σ = 0.05 m in structured areas, but in the corridor it only constrains the sideways direction (M8-T4), so the aid is partial: the fusion filter must use it with the information matrix, not as a full 2D measurement.

Engineering implications and limitations

Engineering implications

• Start from the drift budget. From the allowed error and the longest GNSS outage, work out which sensor grades and which aids are needed, before choosing algorithms.
• Carry at least one absolute aid that works where GNSS does not: a prior map, fiducials, anchors. Relative sensors alone drift.
• Use innovation gating on every aid and monitor consistency; most field failures are a wrong aid accepted as truth.
• Plan the transition. When GNSS returns or an aid fires, avoid a pose jump into the controller: use the map → odom structure (M7-T2) or smooth the correction.
• Test in outages. Replay logs with GNSS cut at known times and measure the error growth, not only the average.
• Report the uncertainty downstream: a robot that knows it is lost can slow down or stop.

Limits

Aids depend on infrastructure or prior maps that may not exist or may have changed, and each has environment-specific failures. The fusion filters are tuned, not proven; consistency in the presence of many intermittent, correlated aids is not settled. Claims of “GPS-free” performance often rest on benign environments and good priors; check the conditions and the length of the outage in any report (M8-T8).

Common misconceptions

Engineering takeaways

1. Accelerometer bias gives a position error ½ b t²; 0.05 m/s² is 90 m after one minute.
2. Odometry aids are relative and drift; absolute position and yaw need a map, a landmark or a beacon.
3. An error-state Kalman filter fuses aids with their covariances; gate innovations and check consistency.
4. Established: INS aiding, map matching, odometry, radio ranging. Active research: cross-view localisation, robust fusion under jamming, magnetic and terrain navigation.
5. Design from the drift budget and the longest outage, and test in outages.

References and further reading

Primary sources and standard texts. The text separates the established methods from the active research.

• Groves, P. D. (2013). Principles of GNSS, Inertial, and Multisensor Integrated Navigation Systems, 2nd ed. Artech House.
• Levinson, J. and Thrun, S. (2010). Robust vehicle localization in urban environments using probabilistic maps. IEEE ICRA.
• Wan, G. et al. (2018). Robust and precise vehicle localization based on multi-sensor fusion in diverse city scenes. IEEE ICRA.
• Forster, C., Carlone, L., Dellaert, F. and Scaramuzza, D. (2017). On-manifold preintegration for real-time visual-inertial odometry. IEEE Transactions on Robotics 33(1).
• Hesch, J. A., Kottas, D. G., Bowman, S. L. and Roumeliotis, S. I. (2014). Camera-IMU-based localization: Observability analysis and consistency improvement. International Journal of Robotics Research 33(1).
• Bar-Shalom, Y., Li, X. R. and Kirubarajan, T. (2001). Estimation with Applications to Tracking and Navigation. Wiley.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

So far the components were hand-designed. The next lesson surveys what learning has contributed: learned features, depth, place recognition and, more ambitiously, learned SLAM systems.

Related content

Nothing below is required to finish this lesson.

• Before
  M8-T4: SLAM in Feature-Poor Environments

  Recognise geometric and visual degeneracy and the remedies: more sensors, constraints and degeneracy-aware updates.

• Lab
  M8-L3: Diagnose Localization in a Feature-Poor Environment

  Localization slides along a corridor: detect the degenerate direction and constrain it.