Vision-based topological mapping and localisation

Competent navigation in an environment is a major requirement for an autonomous mobile robot to accomplish its mission. Nowadays, many successful systems for navigating a mobile robot use an internal map which represents the environment in a detailed geometric manner. However, building, maintaining and using such environment maps for navigation is difficult because of perceptual aliasing and measurement noise. Moreover, geometric maps require the processing of huge amounts of data which is computationally expensive. This thesis addresses the problem of vision-based topological mapping and localisation for mobile robot navigation. Topological maps are concise and 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. In order to make vision-based topological navigation suitable for inexpensive mobile robots for the mass market we propose to characterise key places of the environment based on their visual appearance through colour histograms. The approach for representing places using visual appearance is based on the fact that colour histograms change slowly as the field of vision sweeps the scene when a robot moves through an environment. Hence, a place represents a region of the environment rather than a single position. We demonstrate in experiments using an indoor data set, that a topological map in which places are characterised using visual appearance augmented with metric clues provides sufficient information to perform continuous metric localisation which is robust to the kidnapped robot problem. Many topological mapping methods build a topological map by clustering visual observations to places. However, due to perceptual aliasing observations from different places may be mapped to the same place representative in the topological map. A main contribution of this thesis is a novel approach for dealing with the perceptual aliasing problem in topological mapping. We propose to incorporate neighbourhood relations for disambiguating places which otherwise are indistinguishable. We present a constraint based stochastic local search method which integrates the approach for place disambiguation in order to induce a topological map. Experiments show that the proposed method is capable of mapping environments with a high degree of perceptual aliasing, and that a small map is found quickly. Moreover, the method of using neighbourhood information for place disambiguation is integrated into a framework for topological off-line simultaneous localisation and mapping which does not require an initial categorisation of visual observations. Experiments on an indoor data set demonstrate the suitability of our method to reliably localise the robot while building a topological map.

Visual Navigation: Constructing and Utilizing Simple Maps of an Indoor Environment

The goal of this work is to navigate through an office environmentsusing only visual information gathered from four cameras placed onboard a mobile robot. The method is insensitive to physical changes within the room it is inspecting, such as moving objects. Forward and rotational motion vision are used to find doors and rooms, and these can be used to build topological maps. The map is built without the use of odometry or trajectory integration. The long term goal of the project described here is for the robot to build simple maps of its environment and to localize itself within this framework.

Topological SLAM using a graph-matching based method on omnidirectional images

Comunicación presentada en el XI Workshop of Physical Agents, Valencia, 9-10 septiembre 2010.

Outdoor simultaneous localisation and mapping using RatSLAM

In this paper an existing method for indoor Simultaneous Localisation and Mapping (SLAM) is extended to operate in large outdoor environments using an omnidirectional camera as its principal external sensor. The method, RatSLAM, is based upon computational models of the area in the rat brain that maintains the rodent’s idea of its position in the world. The system uses the visual appearance of different locations to build hybrid spatial-topological maps of places it has experienced that facilitate relocalisation and path planning. A large dataset was acquired from a dynamic campus environment and used to verify the system’s ability to construct representations of the world and simultaneously use these representations to maintain localisation.

Environment mapping for mobile robots navigation using hierarchical neural network and omnivision

Autonomous robots must be able to learn and maintain models of their environments. In this context, the present work considers techniques for the classification and extraction of features from images in joined with artificial neural networks in order to use them in the system of mapping and localization of the mobile robot of Laboratory of Automation and Evolutive Computer (LACE). To do this, the robot uses a sensorial system composed for ultrasound sensors and a catadioptric vision system formed by a camera and a conical mirror. The mapping system is composed by three modules. Two of them will be presented in this paper: the classifier and the characterizer module. The first module uses a hierarchical neural network to do the classification; the second uses techiniques of extraction of attributes of images and recognition of invariant patterns extracted from the places images set. The neural network of the classifier module is structured in two layers, reason and intuition, and is trained to classify each place explored for the robot amongst four predefine classes. The final result of the exploration is the construction of a topological map of the explored environment. Results gotten through the simulation of the both modules of the mapping system will be presented in this paper. © 2008 IEEE.

Multi-agent Systems in the Harvest Prognosis

The paper presents a case study of geo-monitoring a region consisting in the capturing and encoding of human expertise into a knowledge-based system. As soon as the maps have been processed, the data patterns are detected using knowledge-based agents for the harvest prognosis.

Using incomplete online metric maps for topological exploration with the Gap Navigation Tree

This paper presents a general, global approach to the problem of robot exploration, utilizing a topological data structure to guide an underlying Simultaneous Localization and Mapping (SLAM) process. A Gap Navigation Tree (GNT) is used to motivate global target selection and occluded regions of the environment (called “gaps”) are tracked probabilistically. The process of map construction and the motion of the vehicle alters both the shape and location of these regions. The use of online mapping is shown to reduce the difficulties in implementing the GNT.

A Note on the periodic orbits and topological entropy of graph maps

This paper deals with the relationship between the periodic orbits of continuous maps on graphs and the topological entropy of the map. We show that the topological entropy of a graph map can be approximated by the entropy of its periodic orbits

Topological signatures in CMB temperature anisotropy maps

We propose an alternative formalism to simulate cosmic microwave background (CMB) temperature maps in Lambda CDM universes with nontrivial spatial topologies. This formalism avoids the need to explicitly compute the eigenmodes of the Laplacian operator in the spatial sections. Instead, the covariance matrix of the coefficients of the spherical harmonic decomposition of the temperature anisotropies is expressed in terms of the elements of the covering group of the space. We obtain a decomposition of the correlation matrix that isolates the topological contribution to the CMB temperature anisotropies out of the simply connected contribution. A further decomposition of the topological signature of the correlation matrix for an arbitrary topology allows us to compute it in terms of correlation matrices corresponding to simpler topologies, for which closed quadrature formulas might be derived. We also use this decomposition to show that CMB temperature maps of (not too large) multiply connected universes must show patterns of alignment, and propose a method to look for these patterns, thus opening the door to the development of new methods for detecting the topology of our Universe even when the injectivity radius of space is slightly larger than the radius of the last scattering surface. We illustrate all these features with the simplest examples, those of flat homogeneous manifolds, i.e., tori, with special attention given to the cylinder, i.e., T-1 topology.

Topological map induction using neighbourhood information of places

In topological mapping, perceptual aliasing can cause different places to appear indistinguishable to the robot. In case of severely corrupted or non-available odometry information, topological mapping is difficult as the robot is challenged with the loop-closing problem; that is to determine whether it has visited a particular place before. In this article we propose to use neighbourhood information to disambiguate otherwise indistinguishable places. Using neighbourhood information for place disambiguation is an approach that neither depends on a specific choice of sensors nor requires geometric information such as odometry. Local neighbourhood information is extracted from a sequence of observations of visited places. In experiments using either sonar or visual observations from an indoor environment the benefits of using neighbourhood clues for the disambiguation of otherwise identical vertices are demonstrated. Over 90% of the maps we obtain are isomorphic with the ground truth. The choice of the robot’s sensors does not impact the results of the experiments much.

Genetics of path lengths in brain connectivity networks: HARDI-based maps in 457 adults

Brain connectivity analyses are increasingly popular for investigating organization. Many connectivity measures including path lengths are generally defined as the number of nodes traversed to connect a node in a graph to the others. Despite its name, path length is purely topological, and does not take into account the physical length of the connections. The distance of the trajectory may also be highly relevant, but is typically overlooked in connectivity analyses. Here we combined genotyping, anatomical MRI and HARDI to understand how our genes influence the cortical connections, using whole-brain tractography. We defined a new measure, based on Dijkstra's algorithm, to compute path lengths for tracts connecting pairs of cortical regions. We compiled these measures into matrices where elements represent the physical distance traveled along tracts. We then analyzed a large cohort of healthy twins and show that our path length measure is reliable, heritable, and influenced even in young adults by the Alzheimer's risk gene, CLU.

Topological stability through tame retractions

A smooth map is said to be stable if small perturbations of the map only differ from the original one by a smooth change of coordinates. Smoothly stable maps are generic among the proper maps between given source and target manifolds when the source and target dimensions belong to the so-called nice dimensions, but outside this range of dimensions, smooth maps cannot generally be approximated by stable maps. This leads to the definition of topologically stable maps, where the smooth coordinate changes are replaced with homeomorphisms. The topologically stable maps are generic among proper maps for any dimensions of source and target. The purpose of this thesis is to investigate methods for proving topological stability by constructing extremely tame (E-tame) retractions onto the map in question from one of its smoothly stable unfoldings. In particular, we investigate how to use E-tame retractions from stable unfoldings to find topologically ministable unfoldings for certain weighted homogeneous maps or germs. Our first results are concerned with the construction of E-tame retractions and their relation to topological stability. We study how to construct the E-tame retractions from partial or local information, and these results form our toolbox for the main constructions. In the next chapter we study the group of right-left equivalences leaving a given multigerm f invariant, and show that when the multigerm is finitely determined, the group has a maximal compact subgroup and that the corresponding quotient is contractible. This means, essentially, that the group can be replaced with a compact Lie group of symmetries without much loss of information. We also show how to split the group into a product whose components only depend on the monogerm components of f. In the final chapter we investigate representatives of the E- and Z-series of singularities, discuss their instability and use our tools to construct E-tame retractions for some of them. The construction is based on describing the geometry of the set of points where the map is not smoothly stable, discovering that by using induction and our constructional tools, we already know how to construct local E-tame retractions along the set. The local solutions can then be glued together using our knowledge about the symmetry group of the local germs. We also discuss how to generalize our method to the whole E- and Z- series.

Topological analysis off charge density distribution in concomitant polymorphs of 3-acetylcoumarin, a case off packing polymorphism

Detailed investigation of the charge density distribution in concomitant polymorphs of 3-acetylcoumarin in terms of experimental and theoretical densities shows significant differences in the intermolecular features when analyzed based on the topological properties via the quantum theory of atoms in molecules. The two forms, triclinic and monoclinic (Form A and Form B), pack in the crystal lattice via weak C-H---O and C-H---pi interactions. Form A results in a head-to-head molecular stack, while Form B generates a head-to-tail stack. Form A crystallizes in PI (Z' = 2) and Form B crystallizes in P2(1)/n (Z = 1). The electron density maps of the polymorphs demonstrate the differences in the nature of the charge density distribution in general. The charges derived from experimental and theoretical analysis show significant differences with respect to the polymorphic forms. The molecular dipole moments differ significantly for the two forms. The lattice energies evaluated at the HF and DFT (B3LYP) methods with 6-31G** basis set for the two forms clearly suggest that Form A is the thermodynamically stable form as compared to Form B. Mapping of electrostatic potential over the molecular surface shows dominant variations in the electronegative region, which bring out the differences between the two forms.

Topological blocking in quantum quench dynamics

We study the nonequilibrium dynamics of quenching through a quantum critical point in topological systems, focusing on one of their defining features: ground-state degeneracies and associated topological sectors. We present the notion of ``topological blocking,'' experienced by the dynamics due to a mismatch in degeneracies between two phases, and we argue that the dynamic evolution of the quench depends strongly on the topological sector being probed. We demonstrate this interplay between quench and topology in models stemming from two extensively studied systems, the transverse Ising chain and the Kitaev honeycomb model. Through nonlocal maps of each of these systems, we effectively study spinless fermionic p-wave paired topological superconductors. Confining the systems to ring and toroidal geometries, respectively, enables us to cleanly address degeneracies, subtle issues of fermion occupation and parity, and mismatches between topological sectors. We show that various features of the quench, which are related to Kibble-Zurek physics, are sensitive to the topological sector being probed, in particular, the overlap between the time-evolved initial ground state and an appropriate low-energy state of the final Hamiltonian. While most of our study is confined to translationally invariant systems, where momentum is a convenient quantum number, we briefly consider the effect of disorder and illustrate how this can influence the quench in a qualitatively different way depending on the topological sector considered.

Fast training of self organizing maps for the visual exploration of molecular compounds

Visual exploration of scientific data in life science area is a growing research field due to the large amount of available data. The Kohonen’s Self Organizing Map (SOM) is a widely used tool for visualization of multidimensional data. In this paper we present a fast learning algorithm for SOMs that uses a simulated annealing method to adapt the learning parameters. The algorithm has been adopted in a data analysis framework for the generation of similarity maps. Such maps provide an effective tool for the visual exploration of large and multi-dimensional input spaces. The approach has been applied to data generated during the High Throughput Screening of molecular compounds; the generated maps allow a visual exploration of molecules with similar topological properties. The experimental analysis on real world data from the National Cancer Institute shows the speed up of the proposed SOM training process in comparison to a traditional approach. The resulting visual landscape groups molecules with similar chemical properties in densely connected regions.