A framework for map construction

Abstract

In many applications in mobile robotics, it is important for a robot to explore its environment in order to construct a representation of space useful for navigation. We refer to such a representation as a map, and we have considered the process of constructing a map from data gathered while exploring an environment. We have developed a framework for describing map construction problems in which the measurements taken by the robot are subject to errors. In this framework, maps are constructed by representing the robot's environment as a finite automaton. We provide the robot with a set of actions which restrict its interaction with the world in such a way that the world behaves like a finite state automata, and the robot's task is to infer the structure of this automata by experimenting with it. It is natural to divide the problem of developing such a system into two parts. The first part is controlling exploration of the environment and constructing a map from the data gathered, this is the problem of automata inference. The second part is constructing the set of actions and sensing strategies that are used as procedures by this algorithm. In this thesis we first describe the framework, and then consider several variations on the problem of automata inference and their solutions. We then look at one solution that we have used to implement a map construction system, and describe the robotic systems used by the algorithm as procedures. Finally, we discuss the overall performance of the system.