Page 269 - Introduction to Autonomous Mobile Robots

254

Figure 5.40 Chapter 5
Cyclic environments: A naive, local mapping strategy with small local error leads to global maps that
have a significant error, as demonstrated by this real-world run on the left. By applying topological
correction, the grid map on the right is extracted (courtesy of S. Thrun [142]).

5.8.2.1 Cyclic environments
Possibly the single hardest challenge for automatic mapping to be conquered is to correctly
map cyclic environments. The problem is simple: given an environment that has one or
more loops or cycles (e.g., four hallways that intersect to form a rectangle), create a glo-
bally consistent map for the whole environment.
This problem is hard because of the fundamental behavior of automatic mapping sys-
tems: the maps they create are not perfect. And, given any local imperfection, accumulating
such imperfections over time can lead to arbitrarily large global errors between a map, at
the macrolevel, and the real world, as shown in figure 5.40. Such global error is usually
irrelevant to mobile robot localization and navigation. After all, a warped map will still
serve the robot perfectly well so long as the local error is bounded. However, an extremely
large loop still eventually returns to the same spot, and the robot must be able to note this
fact in its map. Therefore, global error does indeed matter in the case of cycles.
In some of the earliest work attempting to solve the cyclic environment problem,
Kuipers and Byun [94] used a purely topological representation of the environment, rea-
soning that the topological representation only captures the most abstract, most important