Markov localization, EKF localization with feature-based maps, data association, and multi-hypothesis tracking.
A robot has a map. It has sensors. It moves around. But where is it? This is the mobile robot localization problem: determining the robot's pose (x, y, θ) relative to a known map, using sensor data accumulated over time.
Localization is fundamentally a problem of coordinate transformation. The map lives in a global frame. The robot's sensors live in a local frame. Knowing the robot's pose connects the two, enabling navigation, obstacle avoidance, and task execution.
No robot has a perfect pose sensor. GPS is noisy and unavailable indoors. Wheel odometry drifts. The pose must be inferred from indirect evidence, and that inference is inherently probabilistic.
Not all localization problems are equally hard. We classify them along four dimensions:
| Dimension | Easy | Hard |
|---|---|---|
| Initial knowledge | Position tracking (pose roughly known) | Global localization (pose unknown) |
| Environment | Static (only robot moves) | Dynamic (people, furniture move) |
| Control | Active (controls motion for localization) | Passive (observes only) |
| Robots | Single robot | Multi-robot (can share beliefs) |
Position tracking assumes the initial pose is approximately known. Uncertainty stays small and local — a single Gaussian suffices. This is the easiest case.
Global localization starts from complete ignorance. The robot could be anywhere. The belief must be multi-modal — a single Gaussian cannot represent "maybe I'm here or maybe I'm there." This is much harder.
The kidnapped robot problem is the hardest: the robot thinks it knows where it is, but it has been secretly moved. It must detect its own failure and re-localize from scratch. This tests an algorithm's ability to recover from catastrophic errors.
Markov localization is simply the Bayes filter applied to the localization problem. It is the most general probabilistic localization algorithm — every other method in this chapter is a special case.
The algorithm takes a belief bel(xt-1), a control ut, a measurement zt, and a map m, then outputs the updated belief bel(xt):
The initial belief determines the type of problem being solved:
| Problem | Initial bel(x0) |
|---|---|
| Position tracking | Narrow Gaussian around known pose |
| Global localization | Uniform over all poses in the map |
| Kidnapped robot | Must inject random particles / uniform mass during operation |
Consider a 1D hallway with three identical doors. The robot starts with no idea where it is (uniform belief). Watch the Bayes filter in action:
Step 1 — Sense a door: The robot detects it is next to a door. It multiplies its uniform belief by p(z|x,m), which peaks at the three door locations. The resulting belief has three peaks — the robot knows it's near some door, but not which one.
Step 2 — Move right: The prediction step convolves the belief with the motion model. Each peak shifts right and spreads out (motion adds uncertainty).
Step 3 — Sense a door again: The second measurement multiplies in another likelihood. Now the posterior strongly favors the correct position, because only one hypothesis is consistent with seeing a door at this new location after moving that distance.
This example works beautifully with histograms and particle filters, which can represent multi-modal beliefs. With an EKF (single Gaussian), we need to know which door we're at — we can't represent three hypotheses simultaneously.
EKF localization represents the belief as a single Gaussian: mean μt and covariance Σt. It uses feature-based maps — a list of point landmarks with known positions.
At each time step, the robot observes a set of features zt = {zt1, zt2, ...}, where each feature measurement is a vector:
containing the range r (distance), bearing φ (angle), and signature s (identity) of the landmark.
The EKF localization algorithm has two phases:
Motion update (lines 2-4): Predict the new pose using the velocity motion model. The mean shifts by the expected motion; the covariance grows by the motion noise Rt.
Measurement update (lines 5-15): For each observed feature, compute the expected measurement, the Jacobian Hti, and the Kalman gain Kti. Each feature tightens the uncertainty.
The key limitation: EKF localization can only handle position tracking. The Gaussian cannot represent multi-modal beliefs, so global localization is impossible.
Here is the concrete algorithm, step by step. We use the velocity motion model and the feature-based measurement model.
Motion update: Given control ut = (vt, ωt), compute the predicted pose and covariance:
where Gt is the Jacobian of the motion model at μt-1.
Measurement update: For each observed feature zti with known correspondence cti = j:
The final pose estimate integrates all features:
In practice, the robot doesn't know which landmark it's seeing. The feature signature helps, but isn't always unique. This is the data association problem.
The simplest solution: maximum likelihood correspondence. For each detected feature zti, find the landmark k that makes the measurement most probable:
where Ψk = Htk Σ̄t HtkT + Qt is the innovation covariance — the combined uncertainty of the pose and the measurement projected into measurement space.
This is a Mahalanobis distance: it measures how surprising the measurement is, normalized by the expected uncertainty. The landmark with the smallest Mahalanobis distance wins.
Two defenses: (1) Design landmarks to be unique and well-separated. (2) Keep the pose uncertainty small — a narrow Gaussian makes it unlikely that a far-away landmark is mistaken for a nearby one. Also, apply an outlier threshold: reject any correspondence whose Mahalanobis distance exceeds a cutoff.
Maximum likelihood correspondence is brittle — it bets everything on one hypothesis. The Multi-Hypothesis Tracking (MHT) algorithm hedges its bets by maintaining multiple Gaussians simultaneously:
Each mixture component (or track) carries its own mean μt,l, covariance Σt,l, and weight ψt,l. Each track is conditioned on a unique history of data association decisions.
How it works: At each time step, every existing track spawns new tracks for each possible correspondence assignment. Each new track's weight is set to:
Tracks with weight below a threshold ψmin are pruned. This keeps the number of tracks manageable — at most 1/ψmin tracks at any time.
Watch EKF localization in action. A robot moves along a corridor and observes landmarks with known positions. The blue ellipse shows the pose uncertainty (covariance). When a landmark is observed, the ellipse shrinks.
The robot moves right. Uncertainty grows during motion (ellipse expands). Observing a landmark (teal diamond) shrinks the uncertainty. Click "Step" to advance.
This chapter introduced mobile robot localization and the EKF approach. Key takeaways:
| Concept | Key Point |
|---|---|
| Markov localization | Bayes filter for pose estimation; representation-agnostic |
| Position tracking | Easy — small, local uncertainty; Gaussian works well |
| Global localization | Hard — multi-modal; Gaussians insufficient |
| EKF localization | Gaussian belief + feature-based maps; position tracking only |
| ML correspondence | Pick the most likely landmark; fast but brittle |
| MHT | Gaussian mixture; robust to association errors; still local |