Localização e Mapeamento são problemas fundamentais da robótica que vêm sendo estudados exaustivamente pela comunidade científica para a navegação de robôs móveis. A maior parte das pesquisas estão concentradas em implementações para computadores pessoais, mas pouco se tem feito na área de computação embarcada. Este trabalho mostra a análise e implementação em FPGA de um algoritmo de localização para ambientes dinâmicos composto por um filtro de partículas, e também de um algoritmo de mapeamento baseado na técnica de scan matching. Os algoritmos originais desenvolvidos em linguagem de programação C foram analisados e modificados para uma abordagem embarcada (embedded) em robôs reconfiguráveis utilizando-se o processador Nios II da Altera. Os algoritmos são comparados quanto ao desempenho, no intuito de servir como referência no futuro desenvolvimento da ferramenta de codesign autom´atico ARCHITECT+ / Localization and Mapping are fundamental robot navigation problems wich currently has been exaustily studied by scientific comunity. Most of research is concentrated on implementation for personal computers, and the robot navigation is done on static environment. But, these algorithms can not be directly applied for embedded solutions on dynamic environments. This work shows an analysis and implementation on FPGA of a localization algorithm for dynamic environments composed of a particle filter, and by an mapping algorthm known as scan matching. The original algorithm devoloped on C programming language for PCs are analised and modified for an embedded approach to mobile robots using Altera Nios II processor. Both C and embedded algorithms are compared within performance, to serve as reference on a future developement of automatic codesign tool ARCHITECT+

Cette thèse étudie le problème de la localisation et de la cartographie simultanée (SLAM), dans des environnements non structurés, c'est-à-dire, qui ne peuvent pas être décrits par des équations ou des formes géométriques. Ces types d'environnements sont souvent rencontrés dans le domaine sous-marin. Contrairement aux approches classiques, l'environnement n'est pas modélisé par une collection de descripteurs ou d'amers ponctuels, mais directement par des ensembles. Ces ensembles, appelés forme ou shape, sont associés à des caractéristiques physiques de l'environnement, comme par exemple, des textures, du relief ou, de manière plus symbolique, à l'espace libre autour du véhicule. D'un point de vue théorique, le problème du SLAM, basé sur des formes, est formalisé par un réseau de contraintes hybrides dont les variables sont des vecteurs de Rn et des sous-ensembles de Rn. De la même façon que l'incertitude sur une variable réelle est représentée par un intervalle de réels, l'incertitude sur les formes sera représentée par un intervalle de forme. La principale contribution de cette thèse est de proposer un formalisme, basé sur le calcul par intervalle, capable de calculer ces domaines. En application, les algorithmes développés ont été appliqués au problème du SLAM à partir de données bathymétriques recueillies par un véhicule sous-marin autonome (AUV). / This thesis deals with the simultaneous localization and mapping (SLAM) problem in unstructured environments, i.e. which cannot be described by geometrical features. This type of environment frequently occurs in an underwater context.Unlike classical approaches, the environment is not described by a collection of punctual features or landmarks, but directly by sets. These sets, called shapes, are associated with physical features such as the relief, some textures or, in a more symbolic way, the space free of obstacles that can be sensed around a robot. In a theoretical point of view, the SLAM problem is formalized as an hybrid constraint network where the variables are vectors and subsets of Rn. Whereas an uncertain real number is enclosed in an interval, an uncertain shape is enclosed in an interval of sets. The main contribution of this thesis is the introduction of a new formalism, based on interval analysis, able to deal with these domains. As an application, we illustrate our method on a SLAM problem based on bathymetric data acquired by an autonomous underwater vehicle (AUV).

As the capabilities of autonomous vehicles increase, their use in situations that are dangerous or dull for humans is becoming more popular. Autonomous systems are currently being used in several military and civilian domains, including search and rescue operations, disaster relief coordination, infrastructure inspection and surveillance missions. In order to perform high level mission autonomy tasks, a method is required for the vehicle to localize itself, as well as generate a map of the environment. Algorithms which allow the vehicle to concurrently localize and create a map of its surroundings are known as solutions to the Simultaneous Localization and Mapping (SLAM) problem. Certain high level tasks, such as drivability analysis and obstacle avoidance, benefit from the use of a dense map of the environment, and are typically generated with the use of point cloud data. The point cloud data is incorporated into SLAM algorithms with scan registration techniques, which determine the relative transformation between two sufficiently overlapping point clouds. The Normal Distributions Transform (NDT) algorithm is a promising method for scan registration, however many issues with the NDT approach exist, including a poor convergence basin, discontinuities in the NDT cost function, and unreliable pose estimation in sparse, outdoor environments. This thesis presents methods to overcome the shortcomings of the NDT algorithm, in both 2D and 3D scenarios. To improve the convergence basin of NDT for 2D scan registration, the Multi-Scale k-Means NDT (MSKM-NDT) algorithm is presented, which divides a 2D point cloud using k-means clustering and performs the scan registration optimization over multiple scales of clustering. The k-means clustering approach generates fewer Gaussian distributions when compared to the standard NDT algorithm, allowing for evaluation of the cost function across all Gaussian clusters. Cost evaluation across all the clusters guarantees that the optimization will converge, as it resolves the issue of discontinuities in the cost function found in the standard NDT algorithm. Experiments demonstrate that the MSKM-NDT approach can be used to register partially overlapping scans with large initial transformation error, and that the convergence basin of MSKM-NDT is superior to NDT for the same test data. As k-means clustering does not scale well to 3D, the Segmented Greedy Cluster NDT (SGC-NDT) method is proposed as an alternative approach to improve and guarantee convergence using 3D point clouds that contain points corresponding to the ground of the environment. The SGC-NDT algorithm segments the ground points using a Gaussian Process (GP) regression model and performs clustering of the non ground points using a greedy method. The greedy clustering extracts natural features in the environment and generates Gaussian clusters to be used within the NDT framework for scan registration. Segmentation of the ground plane and generation of the Gaussian distributions using natural features results in fewer Gaussian distributions when compared to the standard NDT algorithm. Similar to MSKM-NDT, the cost function can be evaluated across all the clusters in the scan, resulting in a smooth and continuous cost function that guarantees convergence of the optimization. Experiments demonstrate that the SGC-NDT algorithm results in scan registrations with higher accuracy and better convergence properties than other state-of-the-art methods for both urban and forested environments.

The Global Positioning System (GPS) is a cornerstone in Unmanned Aerial Vehicle (UAV) navigation and is by far the most common way to obtain the position of a UAV. However, since there are many scenarios in which GPS measurements might not be available, the possibility of estimating the UAV position without using the GPS would greatly improve the overall robustness of the navigation. This thesis studies the possibility of instead using Simultaneous Localisation and Mapping (SLAM) in order to estimate the position of a UAV using an Inertial Measurement Unit (IMU) and the direction towards ground based radio transmitters without prior knowledge of their position. Simulations using appropriately generated data provides a feasibility analysis which shows promising results for position errors for outdoor trajectories over large areas, however with some issues regarding overall offset. The method seems to have potential but further studies are required using the measurements from a live flight, in order to determine the true performance.

As the capabilities of autonomous vehicles increase, their use in situations that are dangerous or dull for humans is becoming more popular. Autonomous systems are currently being used in several military and civilian domains, including search and rescue operations, disaster relief coordination, infrastructure inspection and surveillance missions. In order to perform high level mission autonomy tasks, a method is required for the vehicle to localize itself, as well as generate a map of the environment. Algorithms which allow the vehicle to concurrently localize and create a map of its surroundings are known as solutions to the Simultaneous Localization and Mapping (SLAM) problem. Certain high level tasks, such as drivability analysis and obstacle avoidance, benefit from the use of a dense map of the environment, and are typically generated with the use of point cloud data. The point cloud data is incorporated into SLAM algorithms with scan registration techniques, which determine the relative transformation between two sufficiently overlapping point clouds. The Normal Distributions Transform (NDT) algorithm is a promising method for scan registration, however many issues with the NDT approach exist, including a poor convergence basin, discontinuities in the NDT cost function, and unreliable pose estimation in sparse, outdoor environments. This thesis presents methods to overcome the shortcomings of the NDT algorithm, in both 2D and 3D scenarios. To improve the convergence basin of NDT for 2D scan registration, the Multi-Scale k-Means NDT (MSKM-NDT) algorithm is presented, which divides a 2D point cloud using k-means clustering and performs the scan registration optimization over multiple scales of clustering. The k-means clustering approach generates fewer Gaussian distributions when compared to the standard NDT algorithm, allowing for evaluation of the cost function across all Gaussian clusters. Cost evaluation across all the clusters guarantees that the optimization will converge, as it resolves the issue of discontinuities in the cost function found in the standard NDT algorithm. Experiments demonstrate that the MSKM-NDT approach can be used to register partially overlapping scans with large initial transformation error, and that the convergence basin of MSKM-NDT is superior to NDT for the same test data. As k-means clustering does not scale well to 3D, the Segmented Greedy Cluster NDT (SGC-NDT) method is proposed as an alternative approach to improve and guarantee convergence using 3D point clouds that contain points corresponding to the ground of the environment. The SGC-NDT algorithm segments the ground points using a Gaussian Process (GP) regression model and performs clustering of the non ground points using a greedy method. The greedy clustering extracts natural features in the environment and generates Gaussian clusters to be used within the NDT framework for scan registration. Segmentation of the ground plane and generation of the Gaussian distributions using natural features results in fewer Gaussian distributions when compared to the standard NDT algorithm. Similar to MSKM-NDT, the cost function can be evaluated across all the clusters in the scan, resulting in a smooth and continuous cost function that guarantees convergence of the optimization. Experiments demonstrate that the SGC-NDT algorithm results in scan registrations with higher accuracy and better convergence properties than other state-of-the-art methods for both urban and forested environments.

Orientador: Suely Cunha Amaro Mantovani / Resumo: A criação de robôs que podem operar autonomamente em ambientes controlados e não controlados tem sido, um dos principais objetivos da robótica móvel. Para que um robô possa navegar em um ambiente interno desconhecido, ele deve se localizar e ao mesmo tempo construir um mapa do ambiente que o rodeia, a este problema dá-se o nome de Localização e Mapeamento Simultâneos- SLAM. Tem-se como proposta neste trabalho para solucionar o problema do SLAM, o uso de um sensor RGB-D, com 6 graus de liberdade para perceber o ambiente, o qual é embarcado em um robô. O problema do SLAM pode ser solucionado estimando a pose - posição e orientação, e a trajetória do sensor no ambiente, de forma precisa, justificando a construção de um mapa em três dimensões (3D). Esta estimação envolve a captura consecutiva de frames do ambiente fornecidos pelo sensor RGB-D, onde são determinados os pontos mais acentuados das imagens através do uso de características visuais dadas pelo algoritmo ORB. Em seguida, a comparação entre frames consecutivos e o cálculo das transformações geométricas são realizadas, mediante o algoritmo de eliminação de correspondências atípicas, bPROSAC. Por fim, uma correção de inconsistências é efetuada para a reconstrução do mapa 3D e a estimação mais precisa da trajetória do robô, utilizando técnicas de otimização não lineares. Experimentos são realizados para mostrar a construção do mapa e o desempenho da proposta. / Doutor

Localização e Mapeamento Simultâneos (SLAM) é uma das tarefas mais difíceis em robótica móvel, uma vez que existe uma dependência mútua entre a estimativa da localização do robô e a construção do mapa de ambiente. As estratégias de SLAM mais bem sucedidas focam na construção de um mapa métrico probabilístico empregando técnicas de filtragem Bayesiana. Embora tais métodos permitam a construção de soluções localmente consistentes e coerentes, o SLAM continua sendo um problema crítico em operações em ambientes grandes. Para contornar esta limitação, muitas estratégias dividem o ambiente em pequenas regiões, e formulam o problema de SLAM como uma combinação de múltiplos submapas métricos precisos associados em um mapa topológico. Este trabalho propõe um método de SLAM baseado nos algoritmos DP-SLAM (Distributed Particle SLAM) e SegSlam (Segmented SLAM). SegSLAM é um algoritmo que cria múltiplos submapas para cada região do ambiente, e posteriormente constrói o mapa global selecionando combinações de submapas. Por sua vez, DP-SLAM é um algoritmo de filtro de particulas Rao-Blackwellized que utiliza uma representação distribuída eficiente dos mapas das partículas, juntamente com a árvore de ascendência das partículas. A característica distribuída destas estruturas é favorável para a combinação de diferentes segmentos de mapa localmente precisos, o que aumenta a diversidade de soluções. O algoritmo proposto nesta dissertação, chamado SDP-SLAM, segmenta e combina diferentes hipóteses de trajetórias do robô, a fim de reconstruir o mapa do ambiente. Nossas principais contribuições são o desenvolvimento de novas estratégias para o casamento de submapas e para a estimativa de boas combinações de submapas. O SDP-SLAM foi avaliado através de experimentos realizados por um robô móvel operando em ambientes reais e simulados. / Simultaneous Localization and Mapping (SLAM) is one of the most difficult tasks in mobile robotics, since there is a mutual dependency between the estimation of the robot pose and the construction of the environment map. Most successful strategies in SLAM focus in building a probabilistic metric map employing Bayesian filtering techniques. While these methods allow the construction of consistent and coherent local solutions, the SLAM remains a critical problem in operations within large environments. To circumvent this limitation, many strategies divide the environment in small regions, and formulate the SLAM problem as a combination of multiple precise metric submaps associated in a topological map. This work proposes a SLAM method based on the Distributed Particle SLAM (DPSLAM) and the Segmented SLAM (SegSLAM) algorithms. SegSLAM is an algorithm that generates multiple submaps for every region of the environment, and then build the global map by selecting combinations of submaps. DP-SLAM is a Rao-Blackwellized particle filter algorithm that uses an efficient distributed representation of the particles maps associated with an ancestry tree of the particles. The distributed characteristic of these structures favors the combination of locally accurate map segments, that can increase the diversity of global level solutions. The algorithm proposed in this dissertation, called SDP-SLAM, segments and combines different hypotheses of robot trajectories to reconstruct the environment map. Our main contributions are the development of novel strategies for the matching of submaps and for the estimation of good submaps combinations. SDP-SLAM was evaluated through experiments performed by a mobile robot operating in real and simulated environments.

This diploma thesis deals with the implementation of selected simultaneous locali-zation and mapping (SLAM) algorithm for mobile robot and testing of this algo-rithm. In theoretical part there is a research that describes various existing SLAM algorithms. One of these algorithms is selected for the implementation based on the selected criteria at the end of the research. Practical part of the thesis deals with the implementation of selected SLAM algorithm in particular programming language and with its testing on real data. Computer simulation in which model of the robot travels through the model of Q Building of Mendel University in Brno is created for the purpose of testing.

This work presents a design of an indoor/outdoor SLAM technique combined with navigation for mobile robots. The system does not use any external beacons and relies on only one 2D range finder. This work focuses mainly on an implementation of already established algorithms which were significantly improved (which in effect helped also to overcome the set sensory limitations). To localize the robot and create a map of an unknown environment, we are using a variant of a Rao-Blackwell's particle filter. We also present techniques for navigating in the map and recognizing terrain types. The method for recognizing terrain types creates a much more unique map and also improves the outdoor localization. The outdoor environment that we focused on are city parks where the robot has to stay on designated paths.

Localização e Mapeamento Simultâneos (SLAM) é uma das tarefas mais difíceis em robótica móvel, uma vez que existe uma dependência mútua entre a estimativa da localização do robô e a construção do mapa de ambiente. As estratégias de SLAM mais bem sucedidas focam na construção de um mapa métrico probabilístico empregando técnicas de filtragem Bayesiana. Embora tais métodos permitam a construção de soluções localmente consistentes e coerentes, o SLAM continua sendo um problema crítico em operações em ambientes grandes. Para contornar esta limitação, muitas estratégias dividem o ambiente em pequenas regiões, e formulam o problema de SLAM como uma combinação de múltiplos submapas métricos precisos associados em um mapa topológico. Este trabalho propõe um método de SLAM baseado nos algoritmos DP-SLAM (Distributed Particle SLAM) e SegSlam (Segmented SLAM). SegSLAM é um algoritmo que cria múltiplos submapas para cada região do ambiente, e posteriormente constrói o mapa global selecionando combinações de submapas. Por sua vez, DP-SLAM é um algoritmo de filtro de particulas Rao-Blackwellized que utiliza uma representação distribuída eficiente dos mapas das partículas, juntamente com a árvore de ascendência das partículas. A característica distribuída destas estruturas é favorável para a combinação de diferentes segmentos de mapa localmente precisos, o que aumenta a diversidade de soluções. O algoritmo proposto nesta dissertação, chamado SDP-SLAM, segmenta e combina diferentes hipóteses de trajetórias do robô, a fim de reconstruir o mapa do ambiente. Nossas principais contribuições são o desenvolvimento de novas estratégias para o casamento de submapas e para a estimativa de boas combinações de submapas. O SDP-SLAM foi avaliado através de experimentos realizados por um robô móvel operando em ambientes reais e simulados. / Simultaneous Localization and Mapping (SLAM) is one of the most difficult tasks in mobile robotics, since there is a mutual dependency between the estimation of the robot pose and the construction of the environment map. Most successful strategies in SLAM focus in building a probabilistic metric map employing Bayesian filtering techniques. While these methods allow the construction of consistent and coherent local solutions, the SLAM remains a critical problem in operations within large environments. To circumvent this limitation, many strategies divide the environment in small regions, and formulate the SLAM problem as a combination of multiple precise metric submaps associated in a topological map. This work proposes a SLAM method based on the Distributed Particle SLAM (DPSLAM) and the Segmented SLAM (SegSLAM) algorithms. SegSLAM is an algorithm that generates multiple submaps for every region of the environment, and then build the global map by selecting combinations of submaps. DP-SLAM is a Rao-Blackwellized particle filter algorithm that uses an efficient distributed representation of the particles maps associated with an ancestry tree of the particles. The distributed characteristic of these structures favors the combination of locally accurate map segments, that can increase the diversity of global level solutions. The algorithm proposed in this dissertation, called SDP-SLAM, segments and combines different hypotheses of robot trajectories to reconstruct the environment map. Our main contributions are the development of novel strategies for the matching of submaps and for the estimation of good submaps combinations. SDP-SLAM was evaluated through experiments performed by a mobile robot operating in real and simulated environments.