next up previous
Next: The Markov Localization Algorithm Up: Markov Localization Previous: Basic Notation

Recursive Localization


Markov localization estimates the posterior distribution over tex2html_wrap_inline2887 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 tex2html_wrap_inline2845 , 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 tex2html_wrap_inline2891 , we distinguish two cases, depending on whether the most recent data item tex2html_wrap_inline2893 is a sensor measurement or an odometry reading.

Case 1: The most recent data item is a sensor measurement tex2html_wrap_inline2886 .



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 tex2html_wrap_inline2897 , since it does not depend on tex2html_wrap_inline2887 . 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 tex2html_wrap_inline2901 by tex2html_wrap_inline2903 based on the assumption that it is independent of the time.

Case 2: The most recent data item is an odometry reading: tex2html_wrap_inline2825 .

Here we compute tex2html_wrap_inline2891 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 tex2html_wrap_inline2909 does not carry any information about the position tex2html_wrap_inline2911 :


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 tex2html_wrap_inline2913 instead of tex2html_wrap_inline2915 since we assume that it does not change over time.

next up previous
Next: The Markov Localization Algorithm Up: Markov Localization Previous: Basic Notation

Dieter Fox
Fri Nov 19 14:29:33 MET 1999