Map Validation and Self-location in a Graph-like World.

Abstract

We present algorithms for the discovery and use of topological maps of an environmentby an ac-tive agent (such as a person or a mobile robot). We discuss several issues dealing with the use of pre-existing topological maps of graph-like worlds by an autonomous robot and present al-gorithms, worst cases complexity, and experi-mental results (for representative real-world ex-amples) for twokey problems. The rst of these problems is to verify that a given input map is a correct description of the world (the valida-tion problem). The second is to determine the robot's physical position on an input map (the self-location problem). We present algorithms which require O(N 2) and O(N 3) steps to validate and locate the robot in a map (where N is the number of places in the map).