Page 211 - Introduction to Autonomous Mobile Robots

Chapter 5
196
expressed as a single unique point on the map. In figure 5.10, three examples of a single-
hypothesis belief are shown using three different map representations of the same actual
environment (figure 5.10a). In figure 5.10b, a single point is geometrically annotated as the
robot’s position in a continuous 2D geometric map. In figure 5.10c, the map is a discrete,
tessellated map, and the position is noted at the same level of fidelity as the map cell size.
In figure 5.10d, the map is not geometric at all but abstract and topological. In this case, the
single hypothesis of position involves identifying a single node i in the topological graph
as the robot’s position.
The principal advantage of the single-hypothesis representation of position stems from
the fact that, given a unique belief, there is no position ambiguity. The unambiguous nature
of this representation facilitates decision-making at the robot’s cognitive level (e.g., path
planning). The robot can simply assume that its belief is correct, and can then select its
future actions based on its unique position.
Just as decision-making is facilitated by a single-position hypothesis, so updating the
robot’s belief regarding position is also facilitated, since the single position must be
updated by definition to a new, single position. The challenge with this position update
approach, which ultimately is the principal disadvantage of single-hypothesis representa-
tion, is that robot motion often induces uncertainty due to effector and sensor noise. There-
fore, forcing the position update process to always generate a single hypothesis of position
is challenging and, often, impossible.

5.4.2 Multiple-hypothesis belief
In the case of multiple-hypothesis beliefs regarding position, the robot tracks not just a
single possible position but a possibly infinite set of positions.
In one simple example originating in the work of Jean-Claude Latombe [21, 99], the
robot’s position is described in terms of a convex polygon positioned in a 2D map of the
environment. This multiple-hypothesis representation communicates the set of possible
robot positions geometrically, with no preference ordering over the positions. Each point
in the map is simply either contained by the polygon and, therefore, in the robot’s belief set,
or outside the polygon and thereby excluded. Mathematically, the position polygon serves
to partition the space of possible robot positions. Such a polygonal representation of the
multiple-hypothesis belief can apply to a continuous, geometric map of the environment
[35] or, alternatively, to a tessellated, discrete approximation to the continuous environ-
ment.
It may be useful, however, to incorporate some ordering on the possible robot positions,
capturing the fact that some robot positions are likelier than others. A strategy for repre-
senting a continuous multiple-hypothesis belief state along with a preference ordering over
possible positions is to model the belief as a mathematical distribution. For example, [50,
142] notate the robot’s position belief using an X Y,{ } point in the 2D environment as the