Markov localization estimates the posterior distribution over conditioned on all available data, that is
Before deriving incremental update equations for this posterior, let us briefly make explicit the key assumption underlying our derivation, called the Markov assumption. The Markov assumption, sometimes referred to as static world assumption, specifies that if one knows the robot's location , future measurements are independent of past ones (and vice versa):
In other words, we assume that the robot's location is the only state in the environment, and knowing it is all one needs to know about the past to predict future data. This assumption is clearly inaccurate if the environment contains moving (and measurable) objects other than the robot itself. Further below, in Section 3.3, we will extend the basic paradigm to non-Markovian environments, effectively devising a localization algorithm that works well in a broad range of dynamic environments. For now, however, we will adhere to the Markov assumption, to facilitate the derivation of the basic algorithm.
When computing , we distinguish two cases, depending on whether the most recent data item is a sensor measurement or an odometry reading.
Case 1: The most recent data item is a sensor measurement .
Bayes rule suggests that this term can be transformed to
which, because of our Markov assumption, can be simplified to:
We also observe that the denominator can be replaced by a constant , since it does not depend on . Thus, we have
The reader may notice the incremental nature of Equation (7): If we write
to denote the robot's belief Equation (7) becomes
In this equation we replaced the term by based on the assumption that it is independent of the time.
Case 2: The most recent data item is an odometry reading: .
Here we compute using the Theorem of Total Probability:
Consider the first term on the right-hand side. Our Markov assumption suggests that
The second term on the right-hand side of Equation (10) can also be simplified by observing that does not carry any information about the position :
Substituting 12 and 14 back into Equation (10) gives us the desired result
Notice that Equation (15) is, too, of an incremental form. With our definition of belief above, we have
Please note that we used instead of since we assume that it does not change over time.