Page 214 - Introduction to Autonomous Mobile Robots

199
Mobile Robot Localization
explicit reasoning about the effect that trajectories will have on the quality of localization
requires a multiple-hypothesis representation.
One of the fundamental disadvantages of multiple-hypothesis approaches involves deci-
sion-making. If the robot represents its position as a region or set of possible positions, then
how shall it decide what to do next? Figure 5.11 provides an example. At position 3, the
robot’s belief state is distributed among five hallways separately. If the goal of the robot is
to travel down one particular hallway, then given this belief state, what action should the
robot choose?
The challenge occurs because some of the robot’s possible positions imply a motion tra-
jectory that is inconsistent with some of its other possible positions. One approach that we
will see in the case studies below is to assume, for decision-making purposes, that the robot
is physically at the most probable location in its belief state, then to choose a path based on
that current position. But this approach demands that each possible position have an asso-
ciated probability.
In general, the right approach to such decision-making problems would be to decide on
trajectories that eliminate the ambiguity explicitly. But this leads us to the second major
disadvantage of multiple-hypothesis approaches. In the most general case, they can be
computationally very expensive. When one reasons in a 3D space of discrete possible posi-
tions, the number of possible belief states in the single-hypothesis case is limited to the
number of possible positions in the 3D world. Consider this number to be N . When one
moves to an arbitrary multiple-hypothesis representation, then the number of possible
N
belief states is the power set of N , which is far larger: 2 . Thus explicit reasoning about
the possible trajectory of the belief state over time quickly becomes computationally unten-
able as the size of the environment grows.
There are, however, specific forms of multiple-hypothesis representations that are some-
what more constrained, thereby avoiding the computational explosion while allowing a
limited type of multiple-hypothesis belief. For example, if one assumes a Gaussian distri-
bution of probability centered at a single position, then the problem of representation and
tracking of belief becomes equivalent to Kalman filtering, a straightforward mathematical
process described below. Alternatively, a highly tessellated map representation combined
with a limit of ten possible positions in the belief state, results in a discrete update cycle that
is, at worst, only ten times more computationally expensive than a single-hypothesis belief
update. And other ways to cope with the complexity problem, still being precise and com-
putationally cheap, are hybrid metric-topological approaches [145, 147] or multi-Gaussian
position estimation [35, 60, 81].
In conclusion, the most critical benefit of the multiple-hypothesis belief state is the abil-
ity to maintain a sense of position while explicitly annotating the robot’s uncertainty about
its own position. This powerful representation has enabled robots with limited sensory