Module 04: Localization — The Art of Not Getting Lost

By Gopi Krishna Tummala

The Ghost in the Machine — Building an Autonomous Stack

Module 1: Architecture Module 2: Sensors Module 3: Calibration Module 4: Localization Module 7: Prediction Module 8: Planning

📖 You are reading Module 4: Localization — The Art of Not Getting Lost

The Story: The Blue Line

You wake up in a dark room. You don’t know where you are. You take a step forward and feel a wall. You take a step right and feel a table. Suddenly, you know exactly where you are in your house.

You didn’t use a GPS. You used a Map (your memory of the room) and Observation (touching the wall).

This is exactly how a self-driving car localizes itself.

Most people think cars use GPS to drive. They do not.

GPS is accurate to about 3–5 meters.

A highway lane is 3.7 meters wide.

If a car drove using only GPS, it would spend half its time in the neighbor’s lane and the other half on the sidewalk.

To survive, a robot needs to know its location not to the meter, but to the centimeter. It needs to lock onto the world so tightly that it feels like it is on rails. We call this The Blue Line.

Act I: The Three Liars

To find the truth, the car listens to three different sensors. The problem is that all of them are lying to it.

The Promise: “You are at Lat: 37.42, Long: -122.08.”
The Lie: Clouds, trees, and tall buildings bounce the satellite signals (Multipath error).
The Result: The GPS dot jumps around like a caffeinated squirrel. It tells you you’re in the Starbucks, not on the road.

2. The IMU (Inertial Measurement Unit)

The Promise: “You just moved forward 1.2 meters and turned 2 degrees left.”
The Lie: The IMU is the car’s “inner ear” (accelerometers and gyroscopes). It is incredibly fast (1000 times per second) but it drifts.
The Result: If you close your eyes and try to walk in a straight line, you drift. An IMU does the same. After 60 seconds of driving on IMU alone, the car thinks it has drifted into the next town.

3. Wheel Odometry

The Promise: “The wheel turned 4 times, so we moved 8 meters.”
The Lie: Tires slip. Roads are slippery.
The Result: If you spin your tires on ice, the car thinks it moved 100 meters, but it hasn’t moved an inch.

Conclusion: We have three sensors, and they are all unreliable. To fix this, we need a Map.

Act II: The Map Match (Scan Matching)

This is the “aha!” moment.

Imagine you have a puzzle piece in your hand (what the LiDAR sees right now).

You have the box cover with the full picture (the HD Map).

Localization is simply sliding the puzzle piece over the box cover until it clicks.

The Algorithm: NDT (Normal Distributions Transform)

We don’t match every single dot—that’s too slow. Instead, we match probabilities.

The Map is stored as a grid of “probability clouds” (where is a pole likely to be?).
The LiDAR takes a snapshot of the world (poles, curbs, walls).
The Match: The car slides its LiDAR snapshot over the map. It wiggles it left, right, and rotates it slightly until the snapshot lines up perfectly with the probability clouds.

“Click.”

The car snaps into place. It ignores the noisy GPS and the drifting IMU. It knows it is exactly 14.2 centimeters from the curb.

Act III: The Kalman Filter (The Truth Machine)

We have a problem.

LiDAR Matching is accurate but slow (10 Hz).
IMU is fast (1000 Hz) but drifts.

How do we get a smooth, high-speed position? We fuse them using the Kalman Filter.

Think of the Kalman Filter as a strict editor.

Prediction (IMU): “Based on your speed, you should be here.”
Update (LiDAR): “Actually, I see a stop sign, so we are here.”
Correction: The filter blends them. “I trust the LiDAR more for position, but I trust the IMU more for sudden acceleration.”

This loop runs hundreds of times per second. The result is a silky smooth trajectory that feels stable even when the car goes over bumps.

Act IV: The “Blue Line”

When you look at the dashboard of a Tesla or Waymo, you see a stable, glowing path stretching out in front of the car.

That isn’t just a drawing. That is the Localized Trajectory.

It is the car saying: “I know where I am (Localization), I know where the lanes are (Map), and I know where I want to go (Planning).”
If Localization fails (e.g., inside a featureless tunnel), the Blue Line starts to jitter. The car gets nervous. It may ask you to take over.

The Blue Line is the heartbeat of the autonomous stack. As long as it is steady, the car is alive.

Summary of Module 4

We started with a car that was blind and lost.

GNSS gave us a rough zip code.
IMU gave us the feeling of motion.
HD Maps + LiDAR gave us the “Click” of certainty.
The Kalman Filter tied it all together into a smooth reality.

Now that we know where we are, we need to remember the rules of the road.

Next, in Module 5, we will discuss HD Maps—why the car needs a memory that is better than yours.

Graduate Assignment: The Sensor Fusion Problem

Task:

Design a simple 1D localization system using two sensors.

Scenario: A car is driving on a straight road. You have:
- GPS: Reports position with ±3m error (noisy, but no drift)
- IMU: Reports velocity perfectly, but position drifts at 0.1 m/s
Experiment:
- Drive for 10 seconds at 10 m/s.
- GPS says you’re at 100m ± 3m.
- IMU says you’ve moved 100m (perfect velocity), but has accumulated 1m of drift.
Fusion:
- Use a weighted average: $x_{fused} = w_1 \cdot x_{GPS} + w_2 \cdot x_{IMU}$
- Try $w_1 = 0.9, w_2 = 0.1$ (trust GPS more)
- Try $w_1 = 0.1, w_2 = 0.9$ (trust IMU more)
Analysis: Which weighting works better? Why? What happens if GPS fails completely?

Further Reading:

NDT: Normal Distributions Transform for Registration (Biber & Straßer, 2003)
Probabilistic Robotics (Thrun, Burgard, Fox)
SLAM: Simultaneous Localization and Mapping

Video Recommendation:

This video visualizes “NDT Matching” in real-time—watch how the red dots (live LiDAR) slide around until they perfectly align with the white lines (the Map), locking the car’s position.

NDT Localization Visualization