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

  eqnarray439

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):

  eqnarray444

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 .

Here

  eqnarray455

Bayes rule suggests that this term can be transformed to

  eqnarray459

which, because of our Markov assumption, can be simplified to:

  eqnarray465

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

  eqnarray470

The reader may notice the incremental nature of Equation (7): If we write

  eqnarray475

to denote the robot's belief Equation (7) becomes

  eqnarray479

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:

  eqnarray484

Consider the first term on the right-hand side. Our Markov assumption suggests that

  eqnarray489

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 :

  eqnarray498

Substituting 12 and 14 back into Equation (10) gives us the desired result

  eqnarray509

Notice that Equation (15) is, too, of an incremental form. With our definition of belief above, we have

  eqnarray516

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