Is Markov localization always grid based?

No. The probabilistic recursion can be implemented using different belief representations; Monte Carlo localization uses samples.

Does it build the map?

In its standard localization form, it uses a given map. Joint map and pose estimation is SLAM.

Can a new observation increase uncertainty?

Yes. A conflicting or ambiguous observation can redistribute belief in ways that reduce confidence under the chosen model.

AI Glossary / Reinforcement learning and robotics / Advanced

Markov localization

Definition

Markov localization is a probabilistic method for estimating a robot's pose by maintaining and updating a belief distribution over possible poses. It combines a motion model with a sensor model through recursive Bayesian updates. Its Markov assumptions make the current state sufficient for predicting the next state and interpreting the next observation within the specified model.

What it means

Instead of committing immediately to one location, a robot can retain several possibilities. A repeated doorway pattern may make two corridors plausible; later movement and observations can help distinguish them.
The belief summarizes the evidence accumulated so far. Markov localization therefore does not mean that the robot ignores its history. It means that the history's relevant information is carried forward through the current belief and the assumed state representation. The quality of that representation and the models determines whether the summary is adequate.

How it works

The prediction step moves probability through the motion model. In a discrete pose space, predicted belief at pose x is the sum, over previous poses x_previous, of p(x given x_previous, action) times the previous belief. Continuous formulations use an integral.
The correction step multiplies the predicted belief by p(observation given x, map), then normalizes across poses. A pose becomes more plausible when the observation is more compatible with it relative to competing hypotheses.
Implementations can represent beliefs with grids, particles, or more restricted distribution families. A fine grid can preserve several separated hypotheses but becomes costly as spatial and angular resolution increase.
The basic model usually treats the map as given. Moving objects, correlated measurements, or an incomplete state can violate its simplifying assumptions. Robust sensor models, observation handling, or a richer state may be needed rather than blindly accumulating every reading.

Three practical examples

Global initialization: a robot starts with broad uncertainty and uses observations to narrow its possible location within a known environment.
Ambiguous corridors: several pose hypotheses are retained until distinctive observations provide enough evidence to separate them.
Ongoing tracking: motion predictions and new sensor information are combined to compensate for uncertainty during navigation.

Think of it this way

Think of distributing tokens across all the places you might be on a map. Moving shifts and spreads the tokens according to the movement uncertainty. Seeing a landmark increases the relative share at places where that landmark would be expected. The tokens represent your uncertainty, not many physical robots, and a badly wrong map can misdirect all of them.

Worked example

Consider an original three-position toy world arranged in a ring: A, B, and C. The initial belief is 0.6 at A, 0.3 at B, and 0.1 at C. Heading is fixed and omitted to keep the arithmetic small.
The robot commands a clockwise move. It advances one position with probability 0.8 and stays in place with probability 0.2. Clockwise transitions are A to B, B to C, and C to A.
The predicted belief at A is 0.2 times 0.6 plus 0.8 times 0.1 = 0.20. At B it is 0.2 times 0.3 plus 0.8 times 0.6 = 0.54. At C it is 0.2 times 0.1 plus 0.8 times 0.3 = 0.26. These probabilities sum to one.
A sensor then reports a particular landmark. The likelihood of that report is 0.1 at A, 0.8 at B, and 0.2 at C. Multiplication gives unnormalized values 0.020, 0.432, and 0.052. Their sum is 0.504.
Normalizing gives posterior probabilities 5/126 at A, 6/7 at B, and 13/126 at C, approximately 0.0397, 0.8571, and 0.1032. B is now most plausible, but the evidence has not made its probability one.
The likelihood values need not sum to one across positions: each is the probability of the same report conditional on a different position. The posterior must sum to one across positions. If the report had equal likelihood everywhere, the normalized posterior would equal the predicted belief and provide no localization information.

Illustrative case study

Fictional case: Birch Guides tests a robot in a small exhibition building with repeated wall layouts. A single initial observation leaves several plausible starting poses, so the team retains multiple hypotheses while collecting additional evidence.
The engineers compare estimated beliefs with independently recorded robot positions and test routes that reveal distinctive landmarks. They also inspect how crowds affect observations, since nearby people are not permanent features in the map.
The team chooses a conservative operational response when localization remains ambiguous. This fictional case illustrates belief-based reasoning and testing; it does not claim that a particular implementation reliably handles every crowd or recovers from every localization failure.

Common misconceptions and mistakes

A Markov assumption does not make observations unconditionally independent or erase the effect of past evidence. Sensor likelihood is not the same quantity as posterior probability. A discretized grid's highest-probability cell is also not an exact continuous pose.
A distribution can become confidently wrong if its models are wrong. If an implementation removes all probability from the true pose and has no mechanism to restore it, later evidence may not recover that pose. Global initialization and recovery after an unexpected displacement are related capabilities, but one does not automatically guarantee the other.

Business use

Markov localization helps navigation systems manage uncertainty instead of hiding it behind one pose estimate. It is useful when an environment contains ambiguity or motion errors that require repeated correction. Teams should balance representation cost against required accuracy and evaluate both routine tracking and difficult initialization. Evidence about confidence calibration and recovery behavior matters alongside average position error.

Check your understanding

Why is B's posterior probability 6/7 rather than the sensor likelihood 0.8?

Answer: The posterior combines the motion-predicted probability 0.54 with the likelihood 0.8 and then normalizes against the competing weighted hypotheses. Likelihood alone is not the posterior.

Related terms

Learn next

Practice a discrete Bayes-filter prediction and correction cycle. Then add heading, noisy motion, and ambiguous observations before comparing grid-based and particle-based representations of the same localization problem.

Localization

Sources

Dieter Fox, Wolfram Burgard, and Sebastian Thrun, Markov Localization for Mobile Robots in Dynamic Environments (1999), Sections 2.3–2.5: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume11/fox99a-html/jair-localize.html Article PDF mirror: https://arxiv.org/pdf/1106.0222

Independent review checked the recursive belief and motion updates.

Previous: Markov decision process Next: Markov logic network