Localization & SLAM · Theory · M2

M2-T7 — Data Association

Before a measurement can correct anything, the robot must decide what it measured. A wrong answer is worse than no answer.

Lesson 7 of 7
Module 2: Mathematical Foundations
Algorithm
About 8 minutes to read

A range-bearing detection arrives. Which landmark is it? If the robot knows, the Kalman update is a few lines of linear algebra. If it guesses wrongly, the update pulls the map and the pose toward a lie, and the filter reports high confidence while it does so. This lesson states the problem, builds the standard gating test, and explains why the ambiguity is the real difficulty of SLAM.

Learning objectives

After this lesson, you should be able to:

State the data-association problem: its inputs, its output, and the assumptions it makes.
Compute a Mahalanobis distance and apply a chi-square gate.
Compare nearest-neighbour, gated nearest-neighbour and joint-compatibility association.
Explain failure modes: false matches, missed matches, new landmarks and symmetric environments.

The problem and the intuition

You see a red door. The building has three red doors. Which one is it? You look at where you think you are, work out which door should be about here, and pick the one that is consistent with your own uncertainty. If two doors are consistent you are in trouble: either choice may be wrong, and a wrong choice moves your idea of the door and of yourself.

Association is a decision made under uncertainty, and its mistakes are not random noise: they are consistent lies that the filter happily believes.

A gate around the measurement in range-bearing space, shaped by the innovation covariance. Candidates inside the gate are possible matches; the others are rejected.

The algorithm: gated association

Problem. At time t the sensor returns detections z₁ … z_n. The map holds landmarks m₁ … m_k with estimated positions and covariances. Find, for each detection, the landmark it came from, or decide that it is a new landmark or clutter.

Assumptions. The pose estimate is roughly right (a good prior), the measurement and motion models are calibrated, landmarks are distinguishable by position (not appearance), and clutter is rarer than true detections.

Pipeline

Predict. For each landmark j, compute the predicted measurement ẑ_j = h(x̂, m̂_j) and the Jacobians H_x, H_m.
Innovation covariance. S_j = H_x P_xx H_xᵀ + H_x P_xm H_mᵀ + H_m P_mx H_xᵀ + H_m P_mm H_mᵀ + R. In the simplest case, with a known map, S_j = H_x P H_xᵀ + R.
Mahalanobis distance. For detection i and landmark j: ν = z_i − ẑ_j (with the bearing wrapped) and d²_ij = νᵀ S_j⁻¹ ν.
Gate. Keep candidates with d² below the chi-square threshold for 2 degrees of freedom: 5.99 (95%), 9.21 (99%).
Choose. Nearest neighbour takes the candidate with smallest d². If no candidate passes the gate, the detection is clutter or a new landmark. If several are close, the match is ambiguous.
Update the filter with the chosen pairs. Joint compatibility (JCBB) instead tests the set of pairings together, using the joint innovation covariance, and keeps the largest jointly consistent set.

Mahalanobis gate

d^{2}_{ij}=\nu _{ij}^{\top}\,S_{j}^{-1}\,\nu _{ij}

gate

d^{2}_{ij}<\chi ^{2}_{2,\,0.99}=9.21

ν: the innovation: measured minus predicted measurement.
S: the innovation covariance: how much ν varies if the match is right. It includes pose uncertainty, landmark uncertainty and sensor noise.
d²: squared Mahalanobis distance: distance measured in units of standard deviation, accounting for units and correlation.
χ²_k,p: the chi-square quantile for k degrees of freedom and probability p.

Strengths and limitations

Data-association methods compared
Method	Strength	Weakness / failure mode
Nearest neighbour (Euclidean)	Trivial to implement	Mixes metres and radians; ignores uncertainty; fails when landmarks are dense
Gated nearest neighbour (Mahalanobis)	Uses the filter’s own uncertainty; rejects clutter	Still decides each pair independently; fails when two candidates are both inside the gate
Joint compatibility (JCBB)	Exploits that all pairs share one pose error; robust to correlated errors	Costly (tree search); needs good covariances
Appearance or descriptor matching (Modules 5 and 6)	Independent of the pose estimate	Fails with repetitive scenes; needs verification with geometry
RANSAC over pairings	Robust to many outliers without a prior	Needs enough correct pairs and a minimal model

Failure modes

False match: the wrong landmark is inside the gate and nearest. The update is confident and wrong; the covariance shrinks.
Missed match: the gate is too tight (overconfident covariance) so the correct landmark is rejected, a duplicate landmark is created, and the map doubles.
Symmetry: two landmarks are equally consistent. Without extra information there is no right answer; the robot should delay or keep both hypotheses.
Pose error larger than the landmark spacing: the gate then always contains several landmarks. This happens after a long drift without correction.

A worked example: gating two candidates

A robot predicts what it should see from two landmarks. Its innovation covariance is S = diag(0.01, 0.0004) (σ_r = 10 cm, σ_b = 0.02 rad). It measures z = (5.08 m, 0.43 rad).

Landmark A. Predicted ẑ_A = (5.00, 0.40). Innovation ν = (0.08, 0.03). d² = 0.08² / 0.01 + 0.03² / 0.0004 = 0.64 + 2.25 = 2.89. This is below 9.21: A is a candidate.
Landmark B. Predicted ẑ_B = (5.30, 0.38). Innovation ν = (−0.22, 0.05). d² = 0.22² / 0.01 + 0.05² / 0.0004 = 4.84 + 6.25 = 11.09. Above 9.21: B is rejected.
Compare with Euclidean distance. In raw numbers |ν_A| = sqrt(0.08² + 0.03²) = 0.085 and |ν_B| = sqrt(0.22² + 0.05²) = 0.226. Here both methods choose A, but only the Mahalanobis test knows that 0.05 rad is 2.5σ while 0.22 m is 2.2σ, so B is a closer call than the raw numbers suggest.
Make it ambiguous. Suppose a third landmark C is predicted at (5.05, 0.41) with the same S. Its innovation is (0.03, 0.02), so d² = 0.09 + 1.00 = 1.09, which also passes and is smaller than A’s 2.89. Now A and C are both candidates whose predictions differ by only 5 cm and 0.01 rad. Nearest neighbour picks C, but a one-sigma change in the pose error flips the choice. This is the case where joint compatibility or waiting for a second measurement is safer.
The cost of being wrong. If C is picked while the truth is A, the update pushes the robot pose by up to the difference of the two landmark positions: here a few centimetres, but with landmarks 5 m apart it is metres, and the filter shrinks its covariance as if it had learned something true.

Engineering implications and limitations

Engineering implications

Gate with the filter’s own S and a conservative inflation (for example 1.5×) when the filter may be overconfident. A gate that is too tight creates duplicate landmarks; one that is too loose accepts false matches.
Delay uncertain decisions. Keep tentative landmarks until they have been matched repeatedly (a landmark “birth” policy), and refuse updates when two candidates are within a small margin.
Use a second kind of evidence. Descriptors, colour, intensity or the scan shape can veto a geometric match. Geometry-only association fails in identical corridors.
Log association statistics: gate hits, ambiguous pairs, creation and deletion rates. A rising rate of new landmarks at a known place means the gate is too tight or the covariance is wrong.
Robust back ends (Module 4) tolerate a few wrong associations by down-weighting them; filters cannot undo an accepted update.

Limits of this treatment

The gate assumes the innovation is Gaussian with the covariance S. When the pose estimate is far off, S is wrong, and so is the gate. Moving and partly observed landmarks break the static-landmark assumption. Dense scans have no discrete landmarks at all, and scan matching (Module 3) replaces association with an alignment problem.

Common misconceptions

“Nearest neighbour in range and bearing is good enough.”

It compares metres to radians, ignores the sensor’s noise, and does not know the filter’s uncertainty. A Mahalanobis distance corrects all three.

“A chi-square gate guarantees correct matches.”

It only rejects matches that are statistically implausible. Two plausible candidates both pass, and a wrong one inside the gate is accepted.

“A wrong association adds noise that averages out.”

It adds a consistent, systematic error that the filter treats as information and cannot remove later.

“More landmarks make association easier.”

Denser landmarks make gates overlap and ambiguity more likely.

Engineering takeaways

Data association decides which map element each measurement belongs to, or whether it is new or clutter.
Gate with the Mahalanobis distance d² = νᵀS⁻¹ν against a chi-square threshold (9.21 for 2 dof at 99%).
Joint compatibility checks all pairs together because they share the same pose error.
Wrong matches are confident, systematic and irreversible in a filter; ambiguity should delay the decision.
Use appearance as well as geometry, and monitor association statistics in operation.

References and further reading

Established fundamentals. Learned association (Module 8) is an active research area and is covered there.

Bar-Shalom, Y. and Fortmann, T. E. (1988). Tracking and Data Association. Academic Press: gating and nearest-neighbour methods.
Neira, J. and Tardós, J. D. (2001). Data association in stochastic mapping using the joint compatibility test. IEEE Transactions on Robotics and Automation 17(6).
Thrun, S., Burgard, W. and Fox, D. (2005). Probabilistic Robotics. MIT Press, section 10.3 on data association in EKF-SLAM.
Cadena, C. et al. (2016). Past, Present, and Future of SLAM. IEEE Transactions on Robotics 32(6): data association and robustness as open problems.

Knowledge check

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

Question 1

A detection falls inside the 99% gate of two landmarks with d² = 3.0 and d² = 3.4. What should a careful system do?

Explanation

Treat the match as ambiguous. The two candidates are nearly equally consistent, so choosing one is close to a coin flip, and a wrong choice is applied as confident information. Defer the update, collect another measurement, use an appearance cue, or test the pairs jointly.

Question 2

The filter’s covariance shrinks after every update, and gradually the robot starts creating duplicate landmarks at places it has already visited. What is the most likely cause?

Explanation

Overconfidence: the covariance is too small, so the gate around the predicted measurement becomes too tight and rejects the true landmark. The detection is then treated as new and a duplicate is born. The root cause is often a motion-noise model that is too optimistic.

Question 3

Why does Mahalanobis distance work better than Euclidean distance in (range, bearing) space?

Explanation

It divides each component by its uncertainty and accounts for correlation, so metres and radians are comparable and the test reflects how much deviation is actually plausible. Euclidean distance mixes incompatible units and treats all directions as equally uncertain.

What’s next

Module 2 closes with a lab on matching noisy detections to landmarks. Module 3 then uses these tools to build maps and run the first complete SLAM filter.

Practice this lesson

Match Observations to Landmarks

Associate noisy range-bearing detections with known landmarks and survive clutter and ambiguity.

Next lesson

M3-T1 — Occupancy Grid Mapping

Build a grid map from range scans with a log-odds inverse sensor model.

Nothing below is required to finish this lesson. The last entry is a lesson of other courses on this site that teach the background or go further.

Before
M2-T6: Motion and Observation Models
Write the process and measurement models for a 2D robot with range-bearing sensing, with their Jacobians.
Lab
M2-L4: Match Observations to Landmarks
Associate noisy range-bearing detections with known landmarks and survive clutter and ambiguity.
Linear Algebra
Mahalanobis Distance
The distance used to gate an association, and its chi-square threshold.

Learning objectives

The problem and the intuition

The algorithm: gated association

Pipeline

Strengths and limitations

Failure modes

A worked example: gating two candidates

Engineering implications and limitations

Engineering implications

Limits of this treatment

Common misconceptions

“Nearest neighbour in range and bearing is good enough.”

“A chi-square gate guarantees correct matches.”

“A wrong association adds noise that averages out.”

“More landmarks make association easier.”

Engineering takeaways

References and further reading

Knowledge check

Question 1

Question 2

Question 3

What’s next

Match Observations to Landmarks

M3-T1 — Occupancy Grid Mapping

Related content

Get notified when the next lesson and new labs are released.