Part 4 · How Automated Driving Works

4.4 Localization and maps

Knowing “where am I?”

10-minute readAdvancedPrerequisites: 4.3 Sensors and fusion (weighting by the inverse of the variance), 1.2 Conditional probability and Bayes’ theorem▶ Video (about 5 min)

What you will learn

Explain the accuracy localization needs, and the strengths and weaknesses of GNSS, dead reckoning and map matching
Calculate how dead-reckoning errors build up with distance, and explain why outside references are needed to correct them
Check with simple calculations the repeating cycle of localization — spreading with prediction, shrinking with observation (Bayesian updating, the Kalman filter)

Build intuition

People judge “where am I?” naturally, from familiar scenery and signs. An automated vehicle also needs to know where in its lane it is and how many metres remain to the next stop line. This is localization. Once the vehicle knows its position on the map, it can learn in advance from the map about curves and stop lines its sensors cannot yet see, and about the edges of its ODD (4.1).

There are three broad sources of information about the vehicle’s own position:

Method	How it works	Good at	Poor at
GNSS (satellite positioning)	Finds position from the time signals take to arrive from several satellites	Absolute position anywhere on Earth; a few centimetres with RTK, which uses corrections from base stations	Usually an error of a few metres. No signal in tunnels, underground or in urban canyons; reflections from buildings enlarge the error
Dead reckoning (IMU and wheels)	Adds up how far the vehicle has moved from acceleration, rotation and wheel rotation	Smooth and fast, with no outside references	Small errors build up with the distance travelled
Map matching	Compares LiDAR point clouds, or lane markings and signs seen by cameras, with an HD map	Position relative to the lanes to within centimetres; works in tunnels too	Fails when the map differs from reality (roadworks, lanes hidden by snow); confuses similar-looking places

An HD map records lane shapes, stop lines, signs and so on to an accuracy of a few to a dozen or so centimetres. Information that changes from moment to moment, such as roadworks and congestion, may be layered on top. The three sources are combined by the fusion of 4.3 so that each covers for the others’ weaknesses.

Position error while passing through a tunnel (schematic). Even combined, only dead reckoning is left inside the tunnel and the error builds up, but it shrinks quickly once GNSS returns at the exit. If lanes or wall shapes can be matched against the map inside the tunnel too, the build-up can be held down.

Building a map while at the same time finding one’s own position within it is called SLAM (Simultaneous Localization and Mapping). It is used when making HD maps and by robots that move through places without a map.

Check with math

① How much accuracy is needed?

When a car 1.8 m wide drives in a lane 3.5 m wide, the margin on each side is (3.5 − 1.8) ÷ 2 = 0.85 m. This margin must be shared not only with localization but also with errors in lane perception and in control (steering) — the allocation of requirements in 4.2. If 0.3 m is allocated to localization, to be kept at ±3σ (about 99.7%), then

$$3\sigma \le 0.3\ \text{m} \quad\Longrightarrow\quad \sigma \le 0.1\ \text{m}$$

is required. The few-metre error of ordinary GNSS falls far short.

② Dead-reckoning errors build up

In dead reckoning, a small error in heading turns directly into a sideways offset that keeps growing. With a heading error δθ (in radians) and distance travelled L, the lateral offset is roughly

$$e_{\text{lat}} \approx L\,\delta\theta$$

(an approximation for small angles; 1° = π/180 ≈ 0.0175 radians). Driving through a 1 km tunnel with a heading error of just 0.1° (about 0.00175 radians) gives a lateral offset of 1000 × 0.00175 ≈ 1.7 m — close to half a lane width. The same happens front to back: if the speed derived from wheel rotation is off by 1%, the position drifts by 10 m over 1 km, badly misjudging where the stop line is. Dead reckoning is reliable over short stretches, but it must be corrected again and again with outside references (GNSS or map matching).

③ Spreading with prediction, shrinking with observation

Localization repeats two steps. In “prediction”, dead reckoning moves the position forward, adding error and spreading the distribution. In “observation” by map matching or GNSS, the inverses of the variances are added, just as in ③ of 4.3, and the distribution shrinks:

$$\text{predict: }\ \sigma^2 \leftarrow \sigma^2 + q, \qquad \text{observe: }\ \frac{1}{\sigma^2} \leftarrow \frac{1}{\sigma^2} + \frac{1}{\sigma_z^2}$$

Here q is the variance of the error added by one prediction step and $\sigma_z$ is the error of the observation (← is the “update” symbol used in 2.3). Suppose that on leaving the tunnel, the dead-reckoning error has reached σ = 1.2 m. When a map-matching observation ($\sigma_z = 0.2$ m) comes in,

$$\frac{1}{\sigma^2} = \frac{1}{1.2^2} + \frac{1}{0.2^2} \approx 0.69 + 25 = 25.7 \quad\Longrightarrow\quad \sigma \approx 0.20\ \text{m}$$

so a single observation brings the accuracy back to about that of the observation. Repeating this “predict → observe” cycle is the Kalman filter introduced in 4.3. It amounts to applying Bayes’ theorem from 1.2 over and over at each time step: the prediction is the prior belief, and the result updated by the observation is the posterior.

Where the scenery is repetitive, the candidate positions can split into several, such as “in the left lane” and “in the right lane”. A single normal distribution cannot represent this, so methods such as the particle filter, which represents probability with many candidate points (particles), are also used.

Summary

Localization combines GNSS (absolute position, unavailable in tunnels), dead reckoning (smooth, but its error builds up) and map matching (centimetre-level relative to the lanes, provided the map is right)
Staying in lane needs an accuracy of about 10 cm. Dead reckoning’s lateral offset builds up as “distance × heading error” — even 0.1° gives about 1.7 m over 1 km
Localization repeats spreading with prediction and shrinking with observation (the Kalman filter, Bayesian updating). Watching for maps that disagree with reality and for how sure the position is leads to safety

Quick quiz

Q1. With a lane 3.6 m wide and a car 1.8 m wide, what is the margin on each side?

(3.6 − 1.8) ÷ 2 = 0.9 m. This margin is shared among localization, lane perception and control errors.

Q2. Driving 500 m with a heading error of 0.2°, roughly how large is the lateral offset?

0.2° is about 0.0035 radians, so 500 × 0.0035 ≈ 1.7 m.

Q3. The dead-reckoning error has reached σ = 1.0 m when a map-matching observation with σ_z = 0.25 m comes in. What is the combined error?

1/σ² = 1/1.0² + 1/0.25² = 1 + 16 = 17, so σ = 1/√17 ≈ 0.24 m.

Q4. What could happen when driving, with an outdated HD map, through a section where roadworks have shifted the lanes to the right? How can it be prevented?

The vehicle may try to follow the map’s lanes and stray out of the actual lane or into the works area. Map matching may also fail to fit and mistake the position. Prevent it by giving priority to lanes seen by the sensors, watching for disagreement with the map and restricting the function, updating the map frequently, and treating roadworks sections as outside the ODD.