To introduce the major concepts, we will begin with an intuitive description of Markov localization, followed by a mathematical derivation of the algorithm. The reader may notice that Markov localization is a special case of probabilistic state estimation, applied to mobile robot localization (see also [Russell & Norvig1995, Fox1998, Koenig & Simmons1998]).
For clarity of the presentation, we will initially make the restrictive assumption that the environment is static. This assumption, called Markov assumption, is commonly made in the robotics literature. It postulates that the robot's location is the only state in the environment which systematically affects sensor readings. The Markov assumption is violated if robots share the same environment with people. Further below, in Section 3.3, we will side-step this assumption and present a Markov localization algorithm that works well even in highly dynamic environments, e.g., museums full of people.