Page 218 - Introduction to Autonomous Mobile Robots

203
Mobile Robot Localization
Yet, the continuous representation does not disallow representation of position in the
form of a discrete set of possible positions. For instance, in [62] the robot position belief
state is captured by sampling nine continuous-valued positions from within a region near
the robot’s best-known position. This algorithm captures, within a continuous space, a dis-
crete sampling of possible robot positions.
In summary, the key advantage of a continuous map representation is the potential for
high accuracy and expressiveness with respect to the environmental configuration as well
as the robot position within that environment. The danger of a continuous representation is
that the map may be computationally costly. But this danger can be tempered by employing
abstraction and capturing only the most relevant environmental features. Together with the
use of the closed-world assumption, these techniques can enable a continuous-valued map
to be no more costly, and sometimes even less costly, than a standard discrete representa-
tion.

5.5.2 Decomposition strategies
In the section above, we discussed one method of simplification, in which the continuous
map representation contains a set of infinite lines that approximate real-world environmen-
tal lines based on a 2D slice of the world. Basically this transformation from the real world
to the map representation is a filter that removes all nonstraight data and furthermore
extends line segment data into infinite lines that require fewer parameters.
A more dramatic form of simplification is abstraction: a general decomposition and
selection of environmental features. In this section, we explore decomposition as applied
in its more extreme forms to the question of map representation.
Why would one radically decompose the real environment during the design of a map
representation? The immediate disadvantage of decomposition and abstraction is the loss
of fidelity between the map and the real world. Both qualitatively, in terms of overall struc-
ture, and quantitatively, in terms of geometric precision, a highly abstract map does not
compare favorably to a high-fidelity map.
Despite this disadvantage, decomposition and abstraction may be useful if the abstrac-
tion can be planned carefully so as to capture the relevant, useful features of the world while
discarding all other features. The advantage of this approach is that the map representation
can potentially be minimized. Furthermore, if the decomposition is hierarchical, such as in
a pyramid of recursive abstraction, then reasoning and planning with respect to the map
representation may be computationally far superior to planning in a fully detailed world
model.
A standard, lossless form of opportunistic decomposition is termed exact cell decompo-
sition. This method, introduced by Latombe [21], achieves decomposition by selecting
boundaries between discrete cells based on geometric criticality.