Page 229 - Introduction to Autonomous Mobile Robots

Chapter 5
214
µ
σ
Gaussian probability density function, and thus retains just a and parameterization of
the robot’s belief about position with respect to the map. Updating the parameters of the
Gaussian distribution is all that is required. This fundamental difference in the representa-
tion of belief state leads to the following advantages and disadvantages of the two methods,
as presented in [73]:
• Markov localization allows for localization starting from any unknown position and can
thus recover from ambiguous situations because the robot can track multiple, completely
disparate possible positions. However, to update the probability of all positions within
the whole state space at any time requires a discrete representation of the space, such as
a geometric grid or a topological graph (see section 5.5.2). The required memory and
computational power can thus limit precision and map size.

• Kalman filter localization tracks the robot from an initially known position and is inher-
ently both precise and efficient. In particular, Kalman filter localization can be used in
continuous world representations. However, if the uncertainty of the robot becomes too
large (e.g., due to a robot collision with an object) and thus not truly unimodal, the
Kalman filter can fail to capture the multitude of possible robot positions and can
become irrevocably lost.
In recent research projects improvements are achieved or proposed by either only updat-
ing the state space of interest within the Markov approach [49] or by tracking multiple
hypotheses with Kalman filters [35], or by combining both methods to create a hybrid
localization system [73, 147]. In the next two sections we will each approach in detail.

5.6.2 Markov localization
Markov localization tracks the robot’s belief state using an arbitrary probability density
function to represent the robot’s position (see also [50, 88, 116, 119]). In practice, all
known Markov localization systems implement this generic belief representation by first
tessellating the robot configuration space into a finite, discrete number of possible robot
poses in the map. In actual applications, the number of possible poses can range from sev-
eral hundred to millions of positions.
Given such a generic conception of robot position, a powerful update mechanism is
required that can compute the belief state that results when new information (e.g., encoder
values and sensor values) is incorporated into a prior belief state with arbitrary probability
density. The solution is born out of probability theory, and so the next section describes the
foundations of probability theory that apply to this problem, notably the Bayes formula.
Then, two subsequent sections provide case studies, one robot implementing a simple fea-
ture-driven topological representation of the environment [88, 116, 119] and the other
using a geometric grid-based map [49, 50].