This thesis examines the use of multiple robots in cooperative simultaneous localization and mapping (SLAM), where each robot must estimate the poses of all robots in the team, along with the positions of all known landmarks. The robot team must operate under the condition that the communication network between robots is never guaranteed to be fully connected. Under this condition, a novel algorithm is derived that allows each robot to obtain the centralized-equivalent estimate in a decentralized manner, whenever possible. The algorithm is then extended to a decentralized and distributed approach where robots share the computational burden in considering different data association hypotheses in generating the centralized-equivalent consensus estimate.

This thesis examines the use of multiple robots in cooperative simultaneous localization and mapping (SLAM), where each robot must estimate the poses of all robots in the team, along with the positions of all known landmarks. The robot team must operate under the condition that the communication network between robots is never guaranteed to be fully connected. Under this condition, a novel algorithm is derived that allows each robot to obtain the centralized-equivalent estimate in a decentralized manner, whenever possible. The algorithm is then extended to a decentralized and distributed approach where robots share the computational burden in considering different data association hypotheses in generating the centralized-equivalent consensus estimate.

For robots to operate in human environments they must be able to make their own maps because it is unrealistic to expect a user to enter a map into the robot’s memory; existing floorplans are often incorrect; and human environments tend to change. Traditionally robots have used sonar, infra-red or laser range finders to perform the mapping task. Digital cameras have become very cheap in recent years and they have opened up new possibilities as a sensor for robot perception. Any robot that must interact with humans can reasonably be expected to have a camera for tasks such as face recognition, so it makes sense to also use the camera for navigation. Cameras have advantages over other sensors such as colour information (not available with any other sensor), better immunity to noise (compared to sonar), and not being restricted to operating in a plane (like laser range finders). However, there are disadvantages too, with the principal one being the effect of perspective. This research investigated ways to use a single colour camera as a range sensor to guide an autonomous robot and allow it to build a map of its environment, a process referred to as Simultaneous Localization and Mapping (SLAM). An experimental system was built using a robot controlled via a wireless network connection. Using the on-board camera as the only sensor, the robot successfully explored and mapped indoor office environments. The quality of the resulting maps is comparable to those that have been reported in the literature for sonar or infra-red sensors. Although the maps are not as accurate as ones created with a laser range finder, the solution using a camera is significantly cheaper and is more appropriate for toys and early domestic robots.

O problema da localização e mapeamento simultâneos, conhecido como problema do SLAM, é um dos maiores desafios que a robótica móvel autônoma enfrenta atualmente. Esse problema surge devido à dificuldade que um robô apresenta ao navegar por um ambiente desconhecido, construindo um mapa das regiões por onde já passou ao mesmo tempo em que se localiza dentro dele. O acúmulo de erros gerados pela imprecisão dos sensores utilizados para estimar os estados de localização e mapeamento impede que sejam obtidos resultados confiáveis após períodos de navegação suficientemente longos. Algoritmos de SLAM procuram eliminar esses erros resolvendo ambos os problemas simultaneamente, utilizando as informações de uma etapa para aumentar a precisão dos resultados alcançados na outra e viceversa. Uma das maneiras de se alcançar isso se baseia no estabelecimento de marcos no ambiente que o robô pode utilizar como pontos de referência para se localizar conforme navega. Esse trabalho apresenta uma solução para o problema do SLAM que faz uso de um sensor de visão omnidirecional para estabelecer esses marcos. O uso de sistemas de visão permite a extração de marcos naturais ao ambiente que podem ser correspondidos de maneira robusta sob diferentes pontos de vista. A visão omnidirecional amplia o campo de visão do robô e com isso aumenta a quantidade de marcos observados a cada instante. Ao ser detectado o marco é adicionado ao mapa que robô possui do ambiente e, ao ser reconhecido, o robô pode utilizar essa informação para refinar suas estimativas de localização e mapeamento, eliminando os erros acumulados e conseguindo mantê-las precisas mesmo após longos períodos de navegação. Essa solução foi testada em situações reais de navegação, e os resultados mostram uma melhora significativa nos resultados alcançados em relação àqueles obtidos com a utilização direta das informações coletadas. / The problem of simultaneous localization and mapping, known as the problem of SLAM, is one of the greatest obstacles that the field of autonomous robotics faces nowadays. This problem is related to a robots ability to navigate through an unknown environment, constructing a map of the regions it has already visited at the same time as localizing itself on this map. The imprecision inherent to the sensors used to collect information generates errors that accumulate over time, not allowing for a precise estimation of localization and mapping when used directly. SLAM algorithms try to eliminate these errors by taking advantage of their mutual dependence and solving both problems simultaneously, using the results of one step to refine the estimatives of the other. One possible way to achieve this is the establishment of landmarks in the environment that the robot can use as points of reference to localize itself while it navigates. This work presents a solution to the problem of SLAM using an omnidirectional vision system to detect these landmarks. The choice of visual sensors allows for the extraction of natural landmarks and robust matching under different points of view, as the robot moves through the environment. The omnidirectional vision amplifies the field of vision of the robot, increasing the number of landmarks observed at each instant. The detected landmarks are added to the map, and when they are later recognized they generate information that the robot can use to refine its estimatives of localization and mapping, eliminating accumulated errors and keeping them precise even after long periods of navigation. This solution has been tested in real navigational situations and the results show a substantial improvement in the results compared to those obtained through the direct use of the information collected.

Neste trabalho foi desenvolvido um estudo comparativo entre duas estratégias básicas para a combinação de mapas parciais baseados em marcos para sistemas multirobô: a estratégia por associação de marcos e a estratégia por distância relativa entre os robôs (também conhecida por rendez-vous). O ambiente simulado corresponde a um entorno plano povoado de árvores que são mapeadas por uma equipe de dois robôs móveis equipados com sensores laser para medir a largura e localização de cada _arvore (marco). Os mapas parciais são estimados usando o algoritmo FastSLAM. Além do estudo comparativo propõe-se também um algoritmo alternativo de localização e mapeamento simultâneos para multirrobôs cooperativos, utilizando as observações entre os robôs não só para o cálculo da transformação de coordenadas, mas também no desenvolvimento de um processo seqüencial para atualizar o alinhamento entre os mapas, explorando de forma mais eficiente as observações entre robôs. Os experimentos realizados demonstraram que o algoritmo proposto pode conduzir a resultados significativamente melhores em termos de precisão quando comparado com a abordagem de combinação de mapas tradicional (usando distância relativa entre os robôs). / In this text a comparative survey between the two basic strategies used to combine partial landmark based maps in multi-robot systems, data association and inter-robot observations (known as rendezvous), is presented. The simulated environment is a at place populated by trees, which are going to be mapped by a two-mobile robot team equipped with laser range finders in order to measure every tree (landmark) location and width. Partial maps are estimated using the algorithm FastSLAM. Besides the comparative study it is also proposed an alternative algorithm for Simultaneous Localization and Mapping (SLAM) in multi-robot cooperative systems. It uses observations between robots (detections) not only for calculating the coordinate transformation but also in the development of a sequential process for updating the alignment between maps, exploiting in a more efficient way the inter-robot observations. The experiments showed that the algorithm can lead to significantly better results in terms of accuracy when compared with the traditional approach of combining maps (using the relative distance between robots).

Master of Science / Department of Mechanical and Nuclear Engineering / Dale E. Schinstock / The core objective of this research is to develop an estimator capable of tracking the states of ground targets with observation measurements obtained from a single monocular camera mounted on a small unmanned aerial vehicle (UAV). Typical sensors on a small UAV include an inertial measurement unit (IMU) with three axes accelerometer and rate gyro sensors and a global positioning system (GPS) receiver which gives position and velocity estimates of the UAV. Camera images are combined with these measurements in state estimate filters to track ground features of opportunity and a target. The images are processed by a keypoint detection and matching algorithm that returns pixel coordinates for the features. Kinematic state equations are derived that reflect the relationships between the available input and output measurements and the states of the UAV, features, and target. These equations are used in the development of coupled state estimators for the dynamic state of the UAV, for estimation of feature positions, and for estimation of target position and velocity. The estimator developed is tested in MATLAB/SIMULINK, where GPS and IMU data are generated from the simulated states of a nonlinear model of a Navion aircraft. Images are also simulated based upon a fabricated environment consisting of features and a moving ground target. Target observability limitations are overcome by constraining the target vehicle to follow ground terrain, defined by local features, and subsequent modification of the target's observation model. An unscented Kalman filter (UKF) provides the simultaneous localization and mapping solution for the estimation of aircraft states and feature locations. Another filter, a loosely coupled Kalman filter for the target states, receives 3D measurements of target position with estimated covariance obtained by an unscented transformation (UT). The UT uses the mean and covariance from the camera measurements and from the UKF estimated aircraft states and feature locations to determine the estimated target mean and covariance. Simulation results confirm that the new loosely coupled filters are capable of estimating target states. Experimental data, collected from a research UAV, explores the effectiveness of the terrain estimation techniques required for target tracking.

Point set registration is a well-researched yet still not a very exploited area in computer vision. As the field of machine learning grows, the possibilities of application expand. This thesis investigates the possibility to expand an already implemented probabilistic machine learning approach to point set registration to more complex, larger datasets gathered in a forest environment. The system used as a starting point was created by Järemo Lawin et. al. [10]. The aim of the thesis was to investigate the possibility to register the forest data with the existing system, without ground-truth poses, with different optimizers, and to implement a SLAM pipeline. Also, older methods were used as a benchmark for evaluation, more specifically iterative closest point(ICP) and fast global registration(FGR).To enable the gathered data to be processed by the registration algorithms, preprocessing was required. Transforming the data points from the coordinate system of the sensor to world relative coordinates via LiDAR base coordinates. Subsequently, the registration was performed with different approaches. Both the KITTI odometry dataset, which RLLReg originally was evaluated with[10], and the gathered forest data were used. Data augmentation was utilized to enable ground-truth-independent training and to increase diversity in the data. In addition, the registration results were used to create a SLAM-pipeline, enabling mapping and localization in the scanned areas. The results showed great potential for using RLLReg to register forest scenes compared to other, older, approaches. Especially, the lack of ground-truth was manageable using data augmentation to create training data. Moreover, there was no evidence that AdaBound improves the system when replacing the Adam-optimizer. Finally, forest models with sensor paths plotted were generated with decent results. However, a potential for post-processing with further refinement is possible. Nevertheless, the possibility of point set registration and LiDAR-SLAM using machine learning has been confirmed.

La navigation autonome est un axe de recherche principal dans le domaine de la robotique mobile. Dans ce contexte, le robot doit disposer des algorithmes qui lui permettent d’évoluer de manière autonome dans des environnements complexes et inconnus. Les algorithmes de SLAM permettent à un robot de cartographier son environnement tout en se localisant dans l’espace. Les algorithmes SLAM sont de plus en plus performants, mais aucune implémentation matérielle ou architecturale complète n’a eu. Une telle implantation d’architecture doit prendre en considération la consommation d’énergie, l’embarquabilité et la puissance de calcul. Ce travail scientifique vise à évaluer des systèmes embarqués impliquant de la localisation ou reconstruction de scène. La méthodologie adoptera une approche A3 (Adéquation Algorithme Architecture) pour améliorer l’efficacité de l’implantation des algorithmes plus particulièrement pour des systèmes à fortes contraintes. Le système SLAM embarqué doit disposer d’une architecture électronique et logicielle permettant d’assurer la production d’information pertinentes à partir de données capteurs, tout en assurant la localisation de l’embarquant dans son environnement. L’objectif est donc de définir, pour un algorithme choisi, un modèle d’architecture répondant aux contraintes de l’embarqué. Les premiers travaux de cette thèse ont consisté à explorer les différentes approches algorithmiques permettant la résolution du problème de SLAM. Une étude plus approfondie de ces algorithmes est réalisée. Ceci nous a permet d’évaluer quatre algorithmes de différente nature : FastSLAM2.0, ORB SLAM, RatSLAM et le SLAM linéaire. Ces algorithmes ont été ensuite évalués sur plusieurs architectures pour l’embarqué afin d’étudier leur portabilité sur des systèmes de faible consommation énergétique et de ressources limitées. La comparaison prend en compte les temps d’exécutions et la consistance des résultats. Après avoir analysé profondément les évaluations temporelles de chaque algorithme, le FastSLAM2.0 est finalement choisi, pour un compromis temps d’exécution-consistance de résultat de localisation, comme candidat pour une étude plus approfondie sur une architecture hétérogène embarquée. La second partie de cette thèse est consacré à l’étude d’un système embarqué implémentant le FastSLAM2.0 monoculaire dédié aux environnements larges. Une réécriture algorithmique du FastSLAM2.0 a été nécessaire afin de l’adapter au mieux aux contraintes imposées par les environnements de grande échelle. Dans une démarche A3, le FastSLAM2.0 a été implanté sur une architecture hétérogène CPU-GPU. Grâce à un partitionnement efficace, un facteur d’accélération global de l’ordre de 22 a été obtenu sur une architecture récente dédiée pour l’embarqué. La nature du traitement de l’algorithme FastSLAM2.0 pouvait bénéficier d’une architecture fortement parallèle. Une deuxième instance matérielle basée sur une architecture programmable FPGA est proposée. L’implantation a été réalisée en utilisant des outils de synthèse de haut-niveau afin de réduire le temps de développement. Une comparaison des résultats d’implantation sur cette architecture matérielle par rapport à des architectures à base de GPU a été réalisée. Les gains obtenus sont conséquent, même par rapport aux GPU haut-de-gamme avec un grand nombre de cœurs. Le système résultant peut cartographier des environnements larges tout en garantissant le compromis entre la consistance des résultats de localisation et le temps réel. L’utilisation de plusieurs calculateurs implique d’utiliser des moyens d’échanges de données entre ces derniers. Cela passe par des couplages forts. Ces travaux de thèse ont permis de mettre en avant l’intérêt des architectures hétérogènes parallèles pour le portage des algorithmes SLAM. Les architectures hétérogènes à base de FPGA peuvent particulièrement devenir des candidats potentiels pour porter des algorithmes complexes traitant des données massives. / Autonomous navigation is a main axis of research in the field of mobile robotics. In this context, the robot must have an algorithm that allow the robot to move autonomously in a complex and unfamiliar environments. Mapping in advance by a human operator is a tedious and time consuming task. On the other hand, it is not always reliable, especially when the structure of the environment changes. SLAM algorithms allow a robot to map its environment while localizing it in the space.SLAM algorithms are becoming more efficient, but there is no full hardware or architectural implementation that has taken place . Such implantation of architecture must take into account the energy consumption, the embeddability and computing power. This scientific work aims to evaluate the embedded systems implementing locatization and scene reconstruction (SLAM). The methodology will adopt an approach AAM ( Algorithm Architecture Matching) to improve the efficiency of the implementation of algorithms especially for systems with high constaints. SLAM embedded system must have an electronic and software architecture to ensure the production of relevant data from sensor information, while ensuring the localization of the robot in its environment. Therefore, the objective is to define, for a chosen algorithm, an architecture model that meets the constraints of embedded systems. The first work of this thesis was to explore the different algorithmic approaches for solving the SLAM problem. Further study of these algorithms is performed. This allows us to evaluate four different kinds of algorithms: FastSLAM2.0, ORB SLAM, SLAM RatSLAM and linear. These algorithms were then evaluated on multiple architectures for embedded systems to study their portability on energy low consumption systems and limited resources. The comparison takes into account the time of execution and consistency of results. After having deeply analyzed the temporal evaluations for each algorithm, the FastSLAM2.0 was finally chosen for its compromise performance-consistency of localization result and execution time, as a candidate for further study on an embedded heterogeneous architecture. The second part of this thesis is devoted to the study of an embedded implementing of the monocular FastSLAM2.0 which is dedicated to large scale environments. An algorithmic modification of the FastSLAM2.0 was necessary in order to better adapt it to the constraints imposed by the largescale environments. The resulting system is designed around a parallel multi-core architecture. Using an algorithm architecture matching approach, the FastSLAM2.0 was implemeted on a heterogeneous CPU-GPU architecture. Uisng an effective algorithme partitioning, an overall acceleration factor o about 22 was obtained on a recent dedicated architecture for embedded systems. The nature of the execution of FastSLAM2.0 algorithm could benefit from a highly parallel architecture. A second instance hardware based on programmable FPGA architecture is proposed. The implantation was performed using high-level synthesis tools to reduce development time. A comparison of the results of implementation on the hardware architecture compared to GPU-based architectures was realized. The gains obtained are promising, even compared to a high-end GPU that currently have a large number of cores. The resulting system can map a large environments while maintainingthe balance between the consistency of the localization results and real time performance. Using multiple calculators involves the use of a means of data exchange between them. This requires strong coupling (communication bus and shared memory). This thesis work has put forward the interests of parallel heterogeneous architectures (multicore, GPU) for embedding the SLAM algorithms. The FPGA-based heterogeneous architectures can particularly become potential candidatesto bring complex algorithms dealing with massive data.

The mining industry has over the last few decades seen a drastic increase in the usage of laser scanning technologies as a way of creating 3D maps of the mines being exploited. Underground mapping in places such as mines has become more prevalent as the technology has progressed and made it easier to generate highly detailed point clouds faster. A newer and faster method of generating point clouds is using a simultaneous localization and mapping (SLAM) based mobile laser scanner (MLS). With the help of complex algorithms, it enables instant point cloud registration and allows for continuous mapping of the surrounding environment while tracking the device location without needing a connection to GPS. As the accuracy and speed of SLAM based MLS continues to improve, its use is becoming far more widespread within the mining industry. Although studies have been conducted previously investigating the differences in quality between SLAM based MLS and terrestrial laser scanners (TLS), there is still a need for further studies conducted in mining environments. This case study aims to investigate the quality differences between two point clouds generated using an Emesent Hovermap HF1, which is a SLAM based MLS, and a Faro Laser Scanner Focus 3D X 330 TLS. Parameters like root mean square (RMS) were investigated. Volume calculations were carried out for both point clouds and compared to each other as well the calculated volume of a theoretical model. To conduct this study data from LKAB’s Kiruna mine was collected and provided by Blå Projekt, Process & GIS AB. The result of this study concludes that the Faro TLS is superior in terms of point cloud quality, with five times better RMS values and higher point density than the Hovermap MLS. It also shows that both scanners allowed for accurate volume calculations with only roughly 1% difference in the estimated volumes. The TLS method yielded a much more readable point cloud with clearer visual details than the SLAM based MLS method. This may however be a result of SLAM drift since no loop closure was performed when collecting the MLS data which otherwise could’ve minimized the errors. It was concluded that due to the amount of data processing required and the longer work time of TLS, SLAM based MLS is a method that is worth further development as it provides unparalleled flexibility, safety improvements and work time efficiency.

Active sensors, such as radar, lidar and sonar, emit a signal into the environment and gather information from its reflection. In contrast, passive sensors such as cameras and microphones rely on the signals emitted from the environment. In the current application of active sensors in multi-agent autonomous systems, agents only rely on their own active sensing and filter out any information available passively. However, fusing passive and active sensing information may improve the accuracy of the agents. Also, there is evidence that bats who use biosonar eavesdrop on a conspecific's echolocation sound, which shows a successful example of implementing active and passive sonar sensor fusion in nature. We studied the effect of such information fusion in the framework of two problems: the collective behavior in a multi-agent system using the Vicsek model and the canonical robotics problem of Simultaneous Localization And Mapping (SLAM). Collective behavior refers to emergence of a complex behavior in a group of individuals through local interaction. The Vicsek model is a well-established flocking model based on alignment of individuals with their neighbors in the presence of noise. We studied the aligned motion in a group in which the agents employ both active and passive sensing. Our study shows that the group behavior is less sensitive to measurement accuracy compared to modeling precision. Therefore, using measurement values of the noisier passive sonar can be beneficial. In addition, the group alignment is improved when the passive measurements are not dramatically noisier than active measurements. In the SLAM problem, a robot scans an unknown environment building a map and simultaneously localizing itself within that map. We studied a landmark-based SLAM problem in which the robot uses active and passive sensing strategies. The information provided passively can improve the accuracy of the active sensing measurements and compensate for its blind spot. We developed an estimation algorithm using Extended Kalman Filter and employed Monte Carlo simulation to find a parameter region in which fusing passive and active sonar information improves the performance of the robot. Our analysis shows this region is aligned within the common range of active sonar parameters. / Doctor of Philosophy / Group behavior is a fascinating phenomenon in animal groups such as bird flocks, fish schools, bee colonies and fireflies. For instance, many species of fireflies synchronize their flashing when they bio-luminesce. This synchronization pattern is a group behavior created as a result of local interaction formed by sensing individuals in the group. The research question for this dissertation is inspired by comes from group behavior in bats. Bats use echolocation to perceive the environment. They make a sound and listen to the echo of the sound coming back from objects and by analyzing the echo, they can get information about their surroundings. It has been observed that bats may also use the echo of other bats' sound to perceive their environment. In other words they use two different sensors, one is called active sonar since they actively make the sound and listen to its echoes, and the other one is called passive sonar since they just passively listen to the sound generated by other bats. If this information is useful, can we exploit that in design of engineered systems? We investigated these questions using numerical simulation to solve two test bed problems. The first problem is based on a mathematical flocking model in which the individuals in the group align through local interaction. We found out that eavesdropping improves the alignment of the group within a range of parameters in the model which are relevant to the sensing capabilities of the sonar sensors. The other problem is a canonical robotics problem known as the simultaneous localization and mapping (SLAM). In this problem, a robot searches an unknown environment and creates a map of the environment (mapping) and reports the path it takes within the map (localization). We found out that when the robot uses both passive and active sonar, depending on the accuracy of the two sensing approaches, it can improve the accuracy of both the generated map and the robot's path.