Probabilistic mapping with mobile robots in structured environments

La mayor parte de los entornos diseñados por el hombre presentan características geométricas específicas. En ellos es frecuente encontrar formas poligonales, rectangulares, circulares . . . con una serie de relaciones típicas entre distintos elementos del entorno. Introducir este tipo de conocimiento en el proceso de construcción de mapas de un robot móvil puede mejorar notablemente la calidad y la precisión de los mapas resultantes. También puede hacerlos más útiles de cara a un razonamiento de más alto nivel. Cuando la construcción de mapas se formula en un marco probabilístico Bayesiano, una especificación completa del problema requiere considerar cierta información a priori sobre el tipo de entorno. El conocimiento previo puede aplicarse de varias maneras, en esta tesis se presentan dos marcos diferentes: uno basado en el uso de primitivas geométricas y otro que emplea un método de representación cercano al espacio de las medidas brutas. Un enfoque basado en características geométricas supone implícitamente imponer un cierto modelo a priori para el entorno. En este sentido, el desarrollo de una solución al problema SLAM mediante la optimización de un grafo de características geométricas constituye un primer paso hacia nuevos métodos de construcción de mapas en entornos estructurados. En el primero de los dos marcos propuestos, el sistema deduce la información a priori a aplicar en cada caso en base a una extensa colección de posibles modelos geométricos genéricos, siguiendo un método de Maximización de la Esperanza para hallar la estructura y el mapa más probables. La representación de la estructura del entorno se basa en un enfoque jerárquico, con diferentes niveles de abstracción para los distintos elementos geométricos que puedan describirlo. Se llevaron a cabo diversos experimentos para mostrar la versatilidad y el buen funcionamiento del método propuesto. En el segundo marco, el usuario puede definir diferentes modelos de estructura para el entorno mediante grupos de restricciones y energías locales entre puntos vecinos de un conjunto de datos del mismo. El grupo de restricciones que se aplica a cada grupo de puntos depende de la topología, que es inferida por el propio sistema. De este modo, se pueden incorporar nuevos modelos genéricos de estructura para el entorno con gran flexibilidad y facilidad. Se realizaron distintos experimentos para demostrar la flexibilidad y los buenos resultados del enfoque propuesto. Abstract Most human designed environments present specific geometrical characteristics. In them, it is easy to find polygonal, rectangular and circular shapes, with a series of typical relations between different elements of the environment. Introducing this kind of knowledge in the mapping process of mobile robots can notably improve the quality and accuracy of the resulting maps. It can also make them more suitable for higher level reasoning applications. When mapping is formulated in a Bayesian probabilistic framework, a complete specification of the problem requires considering a prior for the environment. The prior over the structure of the environment can be applied in several ways; this dissertation presents two different frameworks, one using a feature based approach and another one employing a dense representation close to the measurements space. A feature based approach implicitly imposes a prior for the environment. In this sense, feature based graph SLAM was a first step towards a new mapping solution for structured scenarios. In the first framework, the prior is inferred by the system from a wide collection of feature based priors, following an Expectation-Maximization approach to obtain the most probable structure and the most probable map. The representation of the structure of the environment is based on a hierarchical model with different levels of abstraction for the geometrical elements describing it. Various experiments were conducted to show the versatility and the good performance of the proposed method. In the second framework, different priors can be defined by the user as sets of local constraints and energies for consecutive points in a range scan from a given environment. The set of constraints applied to each group of points depends on the topology, which is inferred by the system. This way, flexible and generic priors can be incorporated very easily. Several tests were carried out to demonstrate the flexibility and the good results of the proposed approach.

A guided heuristic approach to the MEG inverse problem.

There is general agreement within the scientific community in considering Biology as the science with more potential to develop in the XXI century. This is due to several reasons, but probably the most important one is the state of development of the rest of experimental and technological sciences. In this context, there are a very rich variety of mathematical tools, physical techniques and computer resources that permit to do biological experiments that were unbelievable only a few years ago. Biology is nowadays taking advantage of all these newly developed technologies, which are been applied to life sciences opening new research fields and helping to give new insights in many biological problems. Consequently, biologists have improved a lot their knowledge in many key areas as human function and human diseases. However there is one human organ that is still barely understood compared with the rest: The human brain. The understanding of the human brain is one of the main challenges of the XXI century. In this regard, it is considered a strategic research field for the European Union and the USA. Thus, there is a big interest in applying new experimental techniques for the study of brain function. Magnetoencephalography (MEG) is one of these novel techniques that are currently applied for mapping the brain activity1. This technique has important advantages compared to the metabolic-based brain imagining techniques like Functional Magneto Resonance Imaging2 (fMRI). The main advantage is that MEG has a higher time resolution than fMRI. Another benefit of MEG is that it is a patient friendly clinical technique. The measure is performed with a wireless set up and the patient is not exposed to any radiation. Although MEG is widely applied in clinical studies, there are still open issues regarding data analysis. The present work deals with the solution of the inverse problem in MEG, which is the most controversial and uncertain part of the analysis process3. This question is addressed using several variations of a new solving algorithm based in a heuristic method. The performance of those methods is analyzed by applying them to several test cases with known solutions and comparing those solutions with the ones provided by our methods.

Mapping energy efficiency barriers

In the E2KW Conference we present the research we are following in collaboration with ANESE (Asociación de Empresas de Servicios Energéticos) to check the interaction among barriers that previous studies have identified. We focus our research question in the information problems that include a number of specific problems such as lack of information, asymmetric information and the well-documented principle-agent problem. Asymmetric information problems occur when one party involved in a transaction has more information that the other, which may lead to suboptimal energy decisions. The fact that energy efficiency cannot be observed (ie. it is ?invisible?) further intensifies this asymmetric information barrier.

Aerial Coverage Path Planning applied to Mapping

In the last decade we have seen how small and light weight aerial platforms - aka, Mini Unmanned Aerial Vehicles (MUAV) - shipped with heterogeneous sensors have become a 'most wanted' Remote Sensing (RS) tool. Most of the off-the-shelf aerial systems found in the market provide way-point navigation. However, they do not rely on a tool that compute the aerial trajectories considering all the aspects that allow optimizing the aerial missions. One of the most demanded RS applications of MUAV is image surveying. The images acquired are typically used to build a high-resolution image, i.e., a mosaic of the workspace surface. Although, it may be applied to any other application where a sensor-based map must be computed. This thesis provides a study of this application and a set of solutions and methods to address this kind of aerial mission by using a fleet of MUAVs. In particular, a set of algorithms are proposed for map-based sampling, and aerial coverage path planning (ACPP). Regarding to map-based sampling, the approaches proposed consider workspaces with different shapes and surface characteristics. The workspace is sampled considering the sensor characteristics and a set of mission requirements. The algorithm applies different computational geometry approaches, providing a unique way to deal with workspaces with different shape and surface characteristics in order to be surveyed by one or more MUAVs. This feature introduces a previous optimization step before path planning. After that, the ACPP problem is theorized and a set of ACPP algorithms to compute the MUAVs trajectories are proposed. The problem addressed herein is the problem to coverage a wide area by using MUAVs with limited autonomy. Therefore, the mission must be accomplished in the shortest amount of time. The aerial survey is usually subject to a set of workspace restrictions, such as the take-off and landing positions as well as a safety distance between elements of the fleet. Moreover, it has to avoid forbidden zones to y. Three different algorithms have been studied to address this problem. The approaches studied are based on graph searching, heuristic and meta-heuristic approaches, e.g., mimic, evolutionary. Finally, an extended survey of field experiments applying the previous methods, as well as the materials and methods adopted in outdoor missions is presented. The reported outcomes demonstrate that the findings attained from this thesis improve ACPP mission for mapping purpose in an efficient and safe manner.

Aerial Coverage Path Planning applied to Mapping

In the last decade we have seen how small and light weight aerial platforms - aka, Mini Unmanned Aerial Vehicles (MUAV) - shipped with heterogeneous sensors have become a 'most wanted' Remote Sensing (RS) tool. Most of the off-the-shelf aerial systems found in the market provide way-point navigation. However, they do not rely on a tool that compute the aerial trajectories considering all the aspects that allow optimizing the aerial missions. One of the most demanded RS applications of MUAV is image surveying. The images acquired are typically used to build a high-resolution image, i.e., a mosaic of the workspace surface. Although, it may be applied to any other application where a sensor-based map must be computed. This thesis provides a study of this application and a set of solutions and methods to address this kind of aerial mission by using a fleet of MUAVs. In particular, a set of algorithms are proposed for map-based sampling, and aerial coverage path planning (ACPP). Regarding to map-based sampling, the approaches proposed consider workspaces with different shapes and surface characteristics. The workspace is sampled considering the sensor characteristics and a set of mission requirements. The algorithm applies different computational geometry approaches, providing a unique way to deal with workspaces with different shape and surface characteristics in order to be surveyed by one or more MUAVs. This feature introduces a previous optimization step before path planning. After that, the ACPP problem is theorized and a set of ACPP algorithms to compute the MUAVs trajectories are proposed. The problem addressed herein is the problem to coverage a wide area by using MUAVs with limited autonomy. Therefore, the mission must be accomplished in the shortest amount of time. The aerial survey is usually subject to a set of workspace restrictions, such as the take-off and landing positions as well as a safety distance between elements of the fleet. Moreover, it has to avoid forbidden zones to y. Three different algorithms have been studied to address this problem. The approaches studied are based on graph searching, heuristic and meta-heuristic approaches, e.g., mimic, evolutionary. Finally, an extended survey of field experiments applying the previous methods, as well as the materials and methods adopted in outdoor missions is presented. The reported outcomes demonstrate that the findings attained from this thesis improve ACPP mission for mapping purpose in an efficient and safe manner.

Mapping the Functional Roles of Cap Cells in the Response of Arabidopsis Primary Roots to Gravity1

The cap is widely accepted to be the site of gravity sensing in roots because removal of the cap abolishes root curvature. Circumstantial evidence favors the columella cells as the gravisensory cells because amyloplasts (and often other cellular components) are polarized with respect to the gravity vector. However, there has been no functional confirmation of their role. To address this problem, we used laser ablation to remove defined cells in the cap of Arabidopsis primary roots and quantified the response of the roots to gravity using three parameters: time course of curvature, presentation time, and deviation from vertical growth. Ablation of the peripheral cap cells and tip cells did not alter root curvature. Ablation of the innermost columella cells caused the strongest inhibitory effect on root curvature without affecting growth rates. Many of these roots deviated significantly from vertical growth and had a presentation time 6-fold longer than the controls. Among the two inner columella stories, the central cells of story 2 contributed the most to root gravitropism. These cells also exhibited the largest amyloplast sedimentation velocities. Therefore, these results are consistent with the starch-statolith sedimentation hypothesis for gravity sensing.

Integrated architecture for vision-based indoor localization and mapping of a quadrotor micro-air vehicle

Atualmente os sistemas de pilotagem autónoma de quadricópteros estão a ser desenvolvidos de forma a efetuarem navegação em espaços exteriores, onde o sinal de GPS pode ser utilizado para definir waypoints de navegação, modos de position e altitude hold, returning home, entre outros. Contudo, o problema de navegação autónoma em espaços fechados sem que se utilize um sistema de posicionamento global dentro de uma sala, subsiste como um problema desafiante e sem solução fechada. Grande parte das soluções são baseadas em sensores dispendiosos, como o LIDAR ou como sistemas de posicionamento externos (p.ex. Vicon, Optitrack). Algumas destas soluções reservam a capacidade de processamento de dados dos sensores e dos algoritmos mais exigentes para sistemas de computação exteriores ao veículo, o que também retira a componente de autonomia total que se pretende num veículo com estas características. O objetivo desta tese pretende, assim, a preparação de um sistema aéreo não-tripulado de pequeno porte, nomeadamente um quadricóptero, que integre diferentes módulos que lhe permitam simultânea localização e mapeamento em espaços interiores onde o sinal GPS ´e negado, utilizando, para tal, uma câmara RGB-D, em conjunto com outros sensores internos e externos do quadricóptero, integrados num sistema que processa o posicionamento baseado em visão e com o qual se pretende que efectue, num futuro próximo, planeamento de movimento para navegação. O resultado deste trabalho foi uma arquitetura integrada para análise de módulos de localização, mapeamento e navegação, baseada em hardware aberto e barato e frameworks state-of-the-art disponíveis em código aberto. Foi também possível testar parcialmente alguns módulos de localização, sob certas condições de ensaio e certos parâmetros dos algoritmos. A capacidade de mapeamento da framework também foi testada e aprovada. A framework obtida encontra-se pronta para navegação, necessitando apenas de alguns ajustes e testes.

RatSLAM: A hippocampal model for simultaneous localisation and mapping

The work presents a new approach to the problem of simultaneous localization and mapping - SLAM - inspired by computational models of the hippocampus of rodents. The rodent hippocampus has been extensively studied with respect to navigation tasks, and displays many of the properties of a desirable SLAM solution. RatSLAM is an implementation of a hippocampal model that can perform SLAM in real time on a real robot. It uses a competitive attractor network to integrate odometric information with landmark sensing to form a consistent representation of the environment. Experimental results show that RatSLAM can operate with ambiguous landmark information and recover from both minor and major path integration errors.

Hippocampal models for simultaneous localisation and mapping on an autonomous robot

To navigate successfully in a novel environment a robot needs to be able to Simultaneously Localize And Map (SLAM) its surroundings. The most successful solutions to this problem so far have involved probabilistic algorithms, but there has been much promising work involving systems based on the workings of part of the rodent brain known as the hippocampus. In this paper we present a biologically plausible system called RatSLAM that uses competitive attractor networks to carry out SLAM in a probabilistic manner. The system can effectively perform parameter self-calibration and SLAM in onedimension. Tests in two dimensional environments revealed the inability of the RatSLAM system to maintain multiple pose hypotheses in the face of ambiguous visual input. These results support recent rat experimentation that suggest current competitive attractor models are not a complete solution to the hippocampal modelling problem.

Probabilistic visual recognition of artificial landmarks for simultaneous localization and mapping

Probabilistic robotics most often applied to the problem of simultaneous localisation and mapping (SLAM), requires measures of uncertainty to accompany observations of the environment. This paper describes how uncertainty can be characterised for a vision system that locates coloured landmarks in a typical laboratory environment. The paper describes a model of the uncertainty in segmentation, the internal cameral model and the mounting of the camera on the robot. It explains the implementation of the system on a laboratory robot, and provides experimental results that show the coherence of the uncertainty model.

GTM: the generative topographic mapping

Latent variable models represent the probability density of data in a space of several dimensions in terms of a smaller number of latent, or hidden, variables. A familiar example is factor analysis which is based on a linear transformations between the latent space and the data space. In this paper we introduce a form of non-linear latent variable model called the Generative Topographic Mapping, for which the parameters of the model can be determined using the EM algorithm. GTM provides a principled alternative to the widely used Self-Organizing Map (SOM) of Kohonen (1982), and overcomes most of the significant limitations of the SOM. We demonstrate the performance of the GTM algorithm on a toy problem and on simulated data from flow diagnostics for a multi-phase oil pipeline.

GTM: the generative topographic mapping

Latent variable models represent the probability density of data in a space of several dimensions in terms of a smaller number of latent, or hidden, variables. A familiar example is factor analysis which is based on a linear transformations between the latent space and the data space. In this paper we introduce a form of non-linear latent variable model called the Generative Topographic Mapping, for which the parameters of the model can be determined using the EM algorithm. GTM provides a principled alternative to the widely used Self-Organizing Map (SOM) of Kohonen (1982), and overcomes most of the significant limitations of the SOM. We demonstrate the performance of the GTM algorithm on a toy problem and on simulated data from flow diagnostics for a multi-phase oil pipeline.

GTM: the generative topographic mapping

This thesis describes the Generative Topographic Mapping (GTM) --- a non-linear latent variable model, intended for modelling continuous, intrinsically low-dimensional probability distributions, embedded in high-dimensional spaces. It can be seen as a non-linear form of principal component analysis or factor analysis. It also provides a principled alternative to the self-organizing map --- a widely established neural network model for unsupervised learning --- resolving many of its associated theoretical problems. An important, potential application of the GTM is visualization of high-dimensional data. Since the GTM is non-linear, the relationship between data and its visual representation may be far from trivial, but a better understanding of this relationship can be gained by computing the so-called magnification factor. In essence, the magnification factor relates the distances between data points, as they appear when visualized, to the actual distances between those data points. There are two principal limitations of the basic GTM model. The computational effort required will grow exponentially with the intrinsic dimensionality of the density model. However, if the intended application is visualization, this will typically not be a problem. The other limitation is the inherent structure of the GTM, which makes it most suitable for modelling moderately curved probability distributions of approximately rectangular shape. When the target distribution is very different to that, theaim of maintaining an `interpretable' structure, suitable for visualizing data, may come in conflict with the aim of providing a good density model. The fact that the GTM is a probabilistic model means that results from probability theory and statistics can be used to address problems such as model complexity. Furthermore, this framework provides solid ground for extending the GTM to wider contexts than that of this thesis.

Outlier detection with partial information:Application to emergency mapping

This paper, addresses the problem of novelty detection in the case that the observed data is a mixture of a known 'background' process contaminated with an unknown other process, which generates the outliers, or novel observations. The framework we describe here is quite general, employing univariate classification with incomplete information, based on knowledge of the distribution (the 'probability density function', 'pdf') of the data generated by the 'background' process. The relative proportion of this 'background' component (the 'prior' 'background' 'probability), the 'pdf' and the 'prior' probabilities of all other components are all assumed unknown. The main contribution is a new classification scheme that identifies the maximum proportion of observed data following the known 'background' distribution. The method exploits the Kolmogorov-Smirnov test to estimate the proportions, and afterwards data are Bayes optimally separated. Results, demonstrated with synthetic data, show that this approach can produce more reliable results than a standard novelty detection scheme. The classification algorithm is then applied to the problem of identifying outliers in the SIC2004 data set, in order to detect the radioactive release simulated in the 'oker' data set. We propose this method as a reliable means of novelty detection in the emergency situation which can also be used to identify outliers prior to the application of a more general automatic mapping algorithm. © Springer-Verlag 2007.

Automated mapping of environmental variables from a SEIS or SISE perspective

The INTAMAP FP6 project has developed an interoperable framework for real-time automatic mapping of critical environmental variables by extending spatial statistical methods and employing open, web-based, data exchange protocols and visualisation tools. This paper will give an overview of the underlying problem, of the project, and discuss which problems it has solved and which open problems seem to be most relevant to deal with next. The interpolation problem that INTAMAP solves is the generic problem of spatial interpolation of environmental variables without user interaction, based on measurements of e.g. PM10, rainfall or gamma dose rate, at arbitrary locations or over a regular grid covering the area of interest. It deals with problems of varying spatial resolution of measurements, the interpolation of averages over larger areas, and with providing information on the interpolation error to the end-user. In addition, monitoring network optimisation is addressed in a non-automatic context.