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.

Robôs verdadeiramente autônomos devem conhecer o ambiente para executar tarefas complexas. Em ambientes desconhecidos o robô deve concorrentemente construir o mapa do ambiente e se localizar usando sensores proprioceptivos e exteroceptivos imprecisos. Isto é problemático, uma vez que o mapa parcial e possivelmente incorreto do ambiente será usado para corrigir erros de localização. Este problema importante da robótica móvel é conhecido como Localização e Mapeamento Simultâneos (SLAM). Quando um robô autonomamente executa o algoritmo de SLAM concorrentemente com uma estratégia de exploração, o problema passa a se chamar SLAM Ativo ou Exploração Integrada. Um dos principais desafios por trás destes problemas é o tratamento de fechamento de ciclos. Ao atravessar regiões desconhecidas ou ambientes esparsos, a pose do robô e o mapa podem não ser propriamente corrigidos por falta de informação. Quando isto acontece, as incertezas da posição do robô e do mapa aumentam, podendo levar a erros irrecuperáveis. Por outro lado, quando o ciclo é fechado corretamente, estas incertezas diminuem consideravelmente. Portanto, a escolha do caminho para explorar o ambiente pode drasticamente melhorar ou degradar a qualidade do mapeamento e da localização. Uma técnica bem conhecida de exploração de ambientes é a adaptação do problema de valor de contorno (BVP) para a equação de Laplace e condições de contorno de Dirichlet. Apesar de ser fácil de implementar, resultando em trajetórias de exploração suaves, esta técnica não endereça cuidadosamente erros de SLAM, uma vez que ela segue a descida do gradiente, o que pode não possibilitar revisitas, uma limitação crucial para o SLAM Ativo. Mesmo sendo uma técnica de exploração gulosa e direcionada a fronteiras, consideramos que a flexibilidade do BVP e condições de contorno de Dirichlet ainda são pouco exploradas. Nossa proposta é modificar o algoritmo de Exploração por BVP para executar comportamentos complexos, tais como revisitas e, em particular, fechamentos de ciclo. Apresentamos duas novas abordagens: a primeira faz uso de uma condição de contorno direcionada pelo tempo combinada a distorções de potencial para gerar comportamentos de fechamento de ciclo, além de um potencial que nunca cessa de existir, mesmo após o ambiente ter sido completamente explorado; a segunda, propicia o fechamento de ciclos aproveitando a propagação do potencial em regiões desconhecidas, através de um par dinâmico de condições de contorno que funcionam como obstáculos e objetivos virtuais. Ambas abordagens aproveitam o Esqueleto de Voronoi do ambiente para reduzir o custo computacional do algoritmo. Testes em ambientes reais e simulados usando o robô Pioneer 3DX mostram que as técnicas apresentadas apresetam melhores resultados quando comparadas a técnicas concorrentes. / Truly autonomous robots must know the environment in order to execute complex tasks. In unknown environments, the robot must construct a map and localize itself using noisy proprioceptive and exteroceptive sensors. This is problematic, since the partial and possibly inaccurate map of the environment will be used to correct localization errors. This important problem of mobile robotics is known as Simultaneous Localization and Mapping (SLAM). When a robot autonomously execute a SLAM algorithm concurrently with an exploration strategy, this problem is called Active SLAM or Integrated Exploration. One of the main challenges behind both these problems is the treatment of loop closures. While the robot traverses unknown regions or sparse environments, the robot pose and the map may not be properly corrected due to lack of information. When this happens, the uncertainties about the map and the robot pose increase, which may lead to unrecoverable SLAM errors. On the other hand, when a loop is closed successfully, these uncertainties drastically decrease. Therefore, path chosen to explore the environment can considerably improve or degrade the quality of both localization and mapping. One well known way to explore the environment is the adaptation of the Boundary Value Problem (BVP) for the Laplace Equation and Dirichlet boundary conditions. Even though it is easy to implement, resulting in smooth exploration trajectories, it does not carefully address SLAM errors, since it follows a gradient decent which not always allows revisits, a crucial limitation for Active SLAM. Despite being a greedy frontier driven exploration strategy, we consider the flexibility of the BVP and Dirichlet boundary conditions still under-explored for Active SLAM. Our proposal is to modify the BVP Exploration algorithm to execute complex exploration behaviors, such as revisits and, in particular, loop-closures. We present two new approaches: the first makes use of a time driven boundary value condition together with potential distortions to generate loop closing behaviors and a potential field that never ceases to exist, even after the exploration ends; the second enables loop closure behaviors with BVP by taking advantage of potential propagation in unknown space generated by a pair of dynamic boundary conditions functioning as virtual walls and goals. Both approaches take advantage of a local optimization that uses the Voronoi Skeleton to reduce the computational cost of the algorithm. Tests in real and simulated environments using a Pioneer 3DX show that the proposed approaches present better results when compared with competing approaches.