Thesis (Ph. D.)--Computing, Georgia Institute of Technology, 2008. / Committee Chair: Dellaert, Frank; Committee Member: Balch, Tucker; Committee Member: Christensen, Henrik; Committee Member: Kuipers, Benjamin; Committee Member: Rehg, Jim.

Topological maps are light-weight, graphical representations of environments that are scalable and amenable to symbolic manipulation. Thus, they are well- suited for basic robot navigation applications, and also provide a representational basis for the procedural and semantic information needed for higher-level robotic tasks. However, their widespread use has been impeded in part by the lack of reliable, general purpose algorithms for their construction. In this dissertation, I present a probabilistic framework for the construction of topological maps that addresses topological ambiguity, is failure-aware, computa- tionally efficient, and can incorporate information from various sensing modalities. The framework addresses the two major problems of topological mapping, namely topological ambiguity and landmark detection. The underlying idea behind overcoming topological ambiguity is that the com- putation of the Bayesian posterior distribution over the space of topologies is an effective means of quantifying this ambiguity, caused due to perceptual aliasing and environment variability. Since the space of topologies is combinatorial, the posterior on it cannot be computed exactly. Instead, I introduce the concept of Probabilistic Topological Maps (PTMs), a sample-based representation that ap- proximates the posterior distribution over topologies given the available sensor measurements. Sampling algorithms for the efficient computation of PTMs are described. The PTM framework can be used with a wide variety of landmark detection schemes under mild assumptions. As part of the evaluation, I describe a novel landmark detection technique that makes use of the notion of "surprise" in mea- surements that the robot obtains, the underlying assumption being that landmarks are places in the environment that generate surprising measurements. The com- putation of surprise in a Bayesian framework is described and applied to various sensing modalities for the computation of PTMs. The PTM framework is the first instance of a probabilistic technique for topo- logical mapping that is systematic and comprehensive. It is especially relevant for future robotic applications which will need a sparse representation capable of accomodating higher level semantic knowledge. Results from experiments in real environments demonstrate that the framework can accomodate diverse sensors such as camera rigs and laser scanners in addition to odometry. Finally, results are pre- sented using various landmark detection schemes besides the surprise-based one.

This thesis deals with various aspects of indoor navigationfor mobile robots. For a system that moves around in ahousehold or office environment,two major problems must betackled. First, an appropriate control scheme has to bedesigned in order to navigate the platform. Second, the form ofrepresentations of the environment must be chosen. Behaviour based approaches have become the dominantmethodologies for designing control schemes for robotnavigation. One of them is the dynamical systems approach,which is based on the mathematical theory of nonlineardynamics. It provides a sound theoretical framework for bothbehaviour design and behaviour coordination. In the workpresented in this thesis, the approach has been used for thefirst time to construct a navigation system for realistic tasksin large-scale real-world environments. In particular, thecoordination scheme was exploited in order to combinecontinuous sensory signals and discrete events for decisionmaking processes. In addition, this coordination frameworkassures a continuous control signal at all times and permitsthe robot to deal with unexpected events. In order to act in the real world, the control system makesuse of representations of the environment. On the one hand,local geometrical representations parameterise the behaviours.On the other hand, context information and a predefined worldmodel enable the coordination scheme to switchbetweensubtasks. These representations constitute symbols, on thebasis of which the system makes decisions. These symbols mustbe anchored in the real world, requiring the capability ofrelating to sensory data. A general framework for theseanchoring processes in hybrid deliberative architectures isproposed. A distinction of anchoring on two different levels ofabstraction reduces the complexity of the problemsignificantly. A topological map was chosen as a world model. Through theadvanced behaviour coordination system and a proper choice ofrepresentations,the complexity of this map can be kept at aminimum. This allows the development of simple algorithms forautomatic map acquisition. When the robot is guided through theenvironment, it creates such a map of the area online. Theresulting map is precise enough for subsequent use innavigation. In addition, initial studies on navigation in human-robotinteraction tasks are presented. These kinds of tasks posedifferent constraints on a robotic system than, for example,delivery missions. It is shown that the methods developed inthis thesis can easily be applied to interactive navigation.Results show a personal robot maintaining formations with agroup of persons during social interaction. <b>Keywords:</b>mobile robots, robot navigation, indoornavigation, behaviour based robotics, hybrid deliberativesystems, dynamical systems approach, topological maps, symbolanchoring, autonomous mapping, human-robot interaction

<p>This thesis deals with various aspects of indoor navigationfor mobile robots. For a system that moves around in ahousehold or office environment,two major problems must betackled. First, an appropriate control scheme has to bedesigned in order to navigate the platform. Second, the form ofrepresentations of the environment must be chosen.</p><p>Behaviour based approaches have become the dominantmethodologies for designing control schemes for robotnavigation. One of them is the dynamical systems approach,which is based on the mathematical theory of nonlineardynamics. It provides a sound theoretical framework for bothbehaviour design and behaviour coordination. In the workpresented in this thesis, the approach has been used for thefirst time to construct a navigation system for realistic tasksin large-scale real-world environments. In particular, thecoordination scheme was exploited in order to combinecontinuous sensory signals and discrete events for decisionmaking processes. In addition, this coordination frameworkassures a continuous control signal at all times and permitsthe robot to deal with unexpected events.</p><p>In order to act in the real world, the control system makesuse of representations of the environment. On the one hand,local geometrical representations parameterise the behaviours.On the other hand, context information and a predefined worldmodel enable the coordination scheme to switchbetweensubtasks. These representations constitute symbols, on thebasis of which the system makes decisions. These symbols mustbe anchored in the real world, requiring the capability ofrelating to sensory data. A general framework for theseanchoring processes in hybrid deliberative architectures isproposed. A distinction of anchoring on two different levels ofabstraction reduces the complexity of the problemsignificantly.</p><p>A topological map was chosen as a world model. Through theadvanced behaviour coordination system and a proper choice ofrepresentations,the complexity of this map can be kept at aminimum. This allows the development of simple algorithms forautomatic map acquisition. When the robot is guided through theenvironment, it creates such a map of the area online. Theresulting map is precise enough for subsequent use innavigation.</p><p>In addition, initial studies on navigation in human-robotinteraction tasks are presented. These kinds of tasks posedifferent constraints on a robotic system than, for example,delivery missions. It is shown that the methods developed inthis thesis can easily be applied to interactive navigation.Results show a personal robot maintaining formations with agroup of persons during social interaction.</p><p><b>Keywords:</b>mobile robots, robot navigation, indoornavigation, behaviour based robotics, hybrid deliberativesystems, dynamical systems approach, topological maps, symbolanchoring, autonomous mapping, human-robot interaction</p>