Next: The Markov Localization Algorithm Up: Markov Localization Previous: Basic Notation

## Recursive Localization

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 .

Here

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.

Next: The Markov Localization Algorithm Up: Markov Localization Previous: Basic Notation

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