Francesco Savelli. 2005.
Topological Mapping of Ambiguous Space:
Combining Qualitative Biases and Metrical Information
Ph.D. Thesis, Department of Computer and Systems Science,
University of Rome "La Sapienza", 2005.


The question "Have I already been here, or is it the first time I see this place?" offers a paradigmatic example of the topological spatial uncertainty that may arise when exploring a new environment. This type of uncertainty concerns both the number of places encountered, and the order in which they are visited. Its occurrence requires taking into account different hypotheses about the size and loops of the graph-model of places (nodes) and paths (edges) that abstracts the space. Because of their limited perceptual mechanisms, modern robotic systems are often faced with topological ambiguity, which makes the autonomous acquisition of a reliable map of the environment a particularly difficult task.

A different type of spatial uncertainty regards the exact geometrical layout of the environment in a single global frame of reference. Most approaches to map-building in robotics are primarily concerned with this second kind of uncertainty, and look at topological ambiguity as an additional adversity --- the correspondence or data association problem --- for which they either assume to be given a solution a priori, or devise ad hoc methods.

The main assumption that drives our work is that metrical uncertainty and topological ambiguity factorize the spatial uncertainty arising in the problem of map-building. They can thus be handled in isolation, but their partial solutions can also take advantage of each other and offer complementary benefits.

In this direction, we provide theory for combining modern metrical mapping methods, among the best of the state of the art, along with a customizable system of qualitative biases and ontological expectations that has proved relevant to topological mapping. The latter has been previously studied in the framework of the Spatial Semantic Hierarchy (SSH), which plays a foundational role in this thesis. To this purpose, we make use of probability theory, and in particular of the Bayes Networks, which we believe to account best for the different nature of metrical and topological uncertainty. We show experimentally the advantages of the approach. In the spirit of the SSH ontology, we also study the dramatic reduction of topological ambiguity that follows from enforcing the planarity constraint, which is adequate in many real-world cases.


[QR home:]