Dissertations / Theses on the topic 'Graph SLAM'

This thesis starts with an introduction to Simulataneous Localization and Mapping (SLAM) and more background on Visual SLAM (VSLAM). The goal of VSLAM is to map the world with a camera, and at the same time localize the camera in that world. One important step is to optimize the acquired map, which can be done in several different ways. In this thesis, two state-of-the-art optimization algorithms are identified and compared, namely the g2o package and the SBA package. The results show that SBA is better on smaller datasets, and g2o on larger. It is also discovered that there is an error in the implementation of the pinhole camera model in the SBA package.

"This work presents a novel method to efficiently factorize the combination of multiple factor graphs having common variables of estimation. The fast-paced innovation in the algebraic graph theory has enabled new tools of state estimation like factor graphs. Recent factor graph formulation for Simultaneous Localization and Mapping (SLAM) like Incremental Smoothing and Mapping using the Bayes tree (ISAM2) has been very successful and garnered much attention. Variable ordering, a well-known technique in linear algebra is employed for solving the factor graph. Our primary contribution in this work is to reuse the variable ordering of the graphs being combined to find the ordering of the fused graph. In the case of mapping, multiple robots provide a great advantage over single robot by providing a faster map coverage and better estimation quality. This coupled with an inevitable increase in the number of robots around us produce a demand for faster algorithms. For example, a city full of self-driving cars could pool their observation measurements rapidly to plan a traffic free navigation. By reusing the variable ordering of the parent graphs we were able to produce an order-of-magnitude difference in the time required for solving the fused graph. We also provide a formal verification to show that the proposed strategy does not violate any of the relevant standards. A common problem in multi-robot SLAM is relative pose graph initialization to produce a globally consistent map. The other contribution addresses this by minimizing a specially formulated error function as a part of solving the factor graph. The performance is illustrated on a publicly available SuiteSparse dataset and the multi-robot AP Hill dataset."

SLAM (do inglês Simultaneous Localization and Mapping) Monocular baseado em Keyframes é uma das principais abordagens de SLAM Visuais, usado para estimar o movimento da câmera juntamente com a reconstrução do mapa sobre frames selecionados. Estas técnicas representam o ambiente por pontos no mapa localizados em um espaço tri-dimensional, que podem ser reconhecidos e localizados no frame. Contudo, estas técnicas não podem decidir quando um ponto do mapa se torna um outlier ou uma informação obsoleta e que pode ser descartada, ou combinar pontos do mapa que correspondem ao mesmo ponto tri-dimensional. Neste trabalho, apresentamos um método robusto para manter um mapa refinado. Esta abordagem usa o grafo de covisibilidade e um algoritmo baseado na fusão de informações para construir um mapa probabilístico, que explicitamente modela medidas de outlier. Além disso, incorporamos um mecanismo de poda para reduzir informações redundantes e remover outliers. Desta forma, nossa abordagem gerencia a redução do tamanho do mapa, mantendo informações essenciais do ambiente. Finalmente, a fim de avaliar a performance do nosso método, ele foi incorporado ao sistema do ORB-SLAM e foi medido a acurácia alcançada em datasets publicamente disponíveis que contêm sequências de imagens de ambientes internos gravados com uma câmera monocular de mão.
Keyframe-based monocular SLAM (Simultaneous Localization and Mapping) is one of the main visual SLAM approaches, used to estimate the camera motion together with the map reconstruction over selected frames. These techniques based on keyframes represent the environment by map points located in the three-dimensional space that can be recognized and located in the frames. However, many of these techniques cannot combine map points corresponding to the same three-dimensional point or detect when a map point becomes outlier and an obsolete information. In this work, we present a robust method to maintain a refined map that uses the covisibility graph and an algorithm based on information fusion to build a probabilistic map, which explicitly models outlier measurements. In addition, we incorporate a pruning mechanism to reduce redundant information and remove outliers. In this way our approach manages the map size maintaining essential information of the environment. Finally, in order to evaluate the performance of our method, we incorporate it into an ORB-SLAM system and measure the accuracy achieved on publicly available benchmark datasets which contain indoor images sequences recorded with a hand-held monocular camera.

This research focuses on the development of a persistent navigation algorithm for a hovering vehicle with a single, downward-facing visible spectrum camera. A successful persistent navigation algorithm allows a vehicle to: * Continuously estimate its location and pose within a local, if not global, coordinate frame. * Continuously align incoming data to both temporally proximal and temporally distant data. For aerial images, this alignment is equivalent to image mosaicking, as is commonly used in aerial photogrammetry to produce broad-scale photomaps from a sequence of discrete images. * Operate relative to, and be commanded relative to the sensor data, rather than relative to an abstract coordinate system. The core application space considered here is moderate-to-high altitude aerial mapping, and a number of sets of high-resolution, high-overlap aerial photographs are used as the core test data set. These images are captured from a sufficient altitude that the apparent perspective shift of objects on the ground is minimized -- the scene is effectively planar. As such, this research focuses heavily on the properties and advantages available when processing such planar images. This research is split into two threads which track the two main challenges in visual persistent navigation: the association and alignment of visual data given significant image change, and the development of an estimation algorithm and data storage structure with bounded computational and storage costs for a fixed map size. Persistent navigation requires the robot to accurately align incoming images against historical data. By its nature, however, visual data contains a high degree of variability despite minimal changes in the scene itself. As a simple example, as the sun moves and weather conditions change, the apparent illumination and shading of objects in the scene can vary significantly. More critically, image alignment must be robust to change in the scene itself, as that change is often a critical output from the robot's re-exploration. This problem is considered in two contexts. First, a set of state-of-the-art feature detection algorithms are evaluated against sample data sets which include both temporally proximal and disparate images of the same location. The capacity of each algorithm to identify repeated point features is measured for a spectrum of algorithm-specific parameter values. Next, the potential of using a prior estimate on the inter-image geometry to improve the robustness of precise image alignment is considered for two phases of the image alignment process: feature matching and robust outlier rejection. A number of geometry-aware algorithms are proposed for both phases, and tested against similar sets of similar and disparate aerial images. While many of the proposed algorithms do improve on the performance of the unguided algorithms, none are vastly superior. The second thread starts by considering the problem of navigation fromdownward-looking aerial images from the perspective of Simultaneous Localization and Mapping (SLAM). This leads to the development of Simultaneous Mosaicking and Resectioning Through Planar Image Graphs (SMARTPIG), an online, iterative mosaicking and SLAM algorithm built on the assumption of a planar scene. A number of samples of SMARTPIG outputs are shown, including mosaics of a 600-meter square airport with approximately 3-meter reprojection errors relative to ground control points. SMARTPIG, like most SLAM algorithms, does not fulfill the criteria for persistent navigation because the computational and storage costs are proportional to the total mission length, not the total area explored. SMARTPIG is evolved towards persistent navigation by the introduction of the featurescape, a storage structure for long-term point-feature data, to produce Planar Image Graphs for PErsistent Navigation (PIGPEN). PIGPEN is demonstrated perfoming robot re-localization onto an existing SMARTPIG mosaic with an accuracy comparable to the original mosaic.

The graph-based formulation of the navigation problem is establishing itself as one of the standard ways to formulate the navigation problem within the sensor fusion community. It enables a convenient way to access information from previous positions which can be used to enhance the estimate of the current position.To restrict working memory usage, map partitioning can be used to store older parts of the map on a hard drive, in the form of submaps. This limits the number of previous positions within the active map. This thesis examines the effect that map partitioning information loss has on the state of the art positioning algorithm iSAM2, both in open routes and when loop closure is achieved. It finds that larger submaps appear to cause a smaller positional error than smaller submaps for open routes. The smaller submaps seem to give smaller positional error than larger submaps when loop closure is achieved. The thesis also examines how the density of landmarks at the partition point affects the positional error, but the obtained result is mixed and no clear conclusions can be made. Finally it reviews some loop closure detection algorithms that can be convenient to pair with the iSAM2 algorithm.

SLAM (Simultaneous Localization And Mapping) has been a very active and almost ubiquitous problem in the field of mobile and autonomous robotics for over two decades. For many years, filter-based methods have dominated the SLAM literature, but a change of paradigms could be observed recently. Current state of the art solutions of the SLAM problem are based on efficient sparse least squares optimization techniques. However, it is commonly known that least squares methods are by default not robust against outliers. In SLAM, such outliers arise mostly from data association errors like false positive loop closures. Since the optimizers in current SLAM systems are not robust against outliers, they have to rely heavily on certain preprocessing steps to prevent or reject all data association errors. Especially false positive loop closures will lead to catastrophically wrong solutions with current solvers. The problem is commonly accepted in the literature, but no concise solution has been proposed so far. The main focus of this work is to develop a novel formulation of the optimization-based SLAM problem that is robust against such outliers. The developed approach allows the back-end part of the SLAM system to change parts of the topological structure of the problem\'s factor graph representation during the optimization process. The back-end can thereby discard individual constraints and converge towards correct solutions even in the presence of many false positive loop closures. This largely increases the overall robustness of the SLAM system and closes a gap between the sensor-driven front-end and the back-end optimizers. The approach is evaluated on both large scale synthetic and real-world datasets. This work furthermore shows that the developed approach is versatile and can be applied beyond SLAM, in other domains where least squares optimization problems are solved and outliers have to be expected. This is successfully demonstrated in the domain of GPS-based vehicle localization in urban areas where multipath satellite observations often impede high-precision position estimates.

Die Sensordatenfusion ist eine allgegenwärtige Aufgabe im Bereich der mobilen Robotik und darüber hinaus. In der vorliegenden Arbeit wird das typischerweise verwendete Verfahren zur Sensordatenfusion in der Robotik in Frage gestellt und anhand von neuartigen Algorithmen, basierend auf einem Faktorgraphen, gelöst sowie mit einer korrespondierenden Extended-Kalman-Filter-Implementierung verglichen. Im Mittelpunkt steht dabei das technische sowie algorithmische Sensorkonzept für die Navigation eines Flugroboters im Innenbereich. Ausführliche Experimente zeigen die Qualitätssteigerung unter Verwendung der neuen Variante der Sensordatenfusion, aber auch Einschränkungen und Beispiele mit nahezu identischen Ergebnissen beider Varianten der Sensordatenfusion. Neben Experimenten anhand einer hardwarenahen Simulation wird die Funktionsweise auch anhand von realen Hardwaredaten evaluiert.

SLAM (Simultaneous Localization And Mapping) has been a very active and almost ubiquitous problem in the field of mobile and autonomous robotics for over two decades. For many years, filter-based methods have dominated the SLAM literature, but a change of paradigms could be observed recently. Current state of the art solutions of the SLAM problem are based on efficient sparse least squares optimization techniques. However, it is commonly known that least squares methods are by default not robust against outliers . In SLAM, such outliers arise mostly from data association errors like false positive loop closures. Since the optimizers in current SLAM systems are not robust against outliers, they have to rely heavily on certain preprocessing steps to prevent or reject all data association errors. Especially false positive loop closures will lead to catastrophically wrong solutions with current solvers. The problem is commonly accepted in the literature, but no concise solution has been proposed so far. The main focus of this work is to develop a novel formulation of the optimization-based SLAM problem that is robust against such outliers. The developed approach allows the back-end part of the SLAM system to change parts of the topological structure of the problem’s factor graph representation during the optimization process. The back-end can thereby discard individual constraints and converge towards correct solutions even in the presence of many false positive loop closures. This largely increases the overall robustness of the SLAM system and closes a gap between the sensor-driven front-end and the back-end optimizers. The approach is evaluated on both large scale synthetic and real-world datasets. This work furthermore shows that the developed approach is versatile and can be applied beyond SLAM, in other domains where least squares optimization problems are solved and outliers have to be expected. This is successfully demonstrated in the domain of GPS-based vehicle localization in urban areas where multipath satellite observations often impede high-precision position estimates.

La localisation et cartographie simultanées connue, communément, sous le nom de SLAM (Simultaneous Localization And Mapping) est un processus qui permet à un robot explorant un environnement inconnu de reconstruire une carte de celui-ci tout en se localisant, en même temps, sur cette carte. Dans ce travail de thèse, nous nous intéressons au SLAM par optimisation de graphe. Celui-ci utilise un graphe pour représenter et résoudre le problème de SLAM. Une optimisation de graphe consiste à trouver une configuration de graphe (trajectoire et carte) qui correspond le mieux aux contraintes introduites par les mesures capteurs. L'optimisation de graphe présente une forte complexité algorithmique et requiert des ressources de calcul et de mémoire importantes, particulièrement si l'on veut explorer de larges zones. Cela limite l'utilisation de cette méthode dans des systèmes embarqués temps-réel. Les travaux de cette thèse contribuent à l'atténuation de la complexité de calcul du SLAM par optimisation de graphe. Notre approche s’appuie sur deux axes complémentaires : la représentation mémoire des données et l’implantation sur architectures hétérogènes embarquées. Dans le premier axe, nous proposons une structure de données incrémentale pour représenter puis optimiser efficacement le graphe. Dans le second axe, nous explorons l'utilisation des architectures hétérogènes récentes pour accélérer le SLAM par optimisation de graphe. Nous proposons, donc, un modèle d’implantation adéquat aux applications embarquées en mettant en évidence les avantages et les inconvénients des architectures évaluées, à savoir SoCs basés GPU et FPGA
Simultaneous Localization And Mapping is the process that allows a robot to build a map of an unknown environment while at the same time it determines the robot position on this map.In this work, we are interested in graph-based SLAM method. This method uses a graph to represent and solve the SLAM problem. A graph optimization consists in finding a graph configuration (trajectory and map) that better matches the constraints introduced by the sensors measurements. Graph optimization is characterized by a high computational complexity that requires high computational and memory resources, particularly to explore large areas. This limits the use of graph-based SLAM in real-time embedded systems. This thesis contributes to the reduction of the graph-based computational complexity. Our approach is based on two complementary axes: data representation in memory and implementation on embedded heterogeneous architectures. In the first axis, we propose an incremental data structure to efficiently represent and then optimize the graph. In the second axis, we explore the use of the recent heterogeneous architectures to speed up graph-based SLAM. We propose an efficient implementation model for embedded applications. We highlight the advantages and disadvantages of the evaluated architectures, namely GPU-based and FPGA-based System-On-Chips

L'estimation en robotique est un sujet important affecté par les compromis entre certains critères majeurs parmi lesquels nous pouvons citer le temps de calcul et la précision. L'importance de ces deux critères dépend de l'application. Si le temps de calcul n'est pas important pour les méthodes hors ligne, il devient critique lorsque l'application doit s'exécuter en temps réel. De même, les exigences de précision dépendent des applications. Les estimateurs EKF sont largement utilisés pour satisfaire les contraintes en temps réel tout en obtenant une estimation avec des précisions acceptables. Les centrales inertielles (Inertial Measurement Unit - IMU) demeurent des capteurs répandus dnas les problèmes d'estimation de trajectoire. Ces capteurs ont par ailleurs la particularité de fournir des données à une fréquence élevée. La principale contribution de cette thèses est une présentation claire de la méthode de préintégration donnant lieu à une meilleure utilisation des centrales inertielles. Nous appliquons cette méthode aux problèmes d'estimation dans les cas de la navigation piétonne et celle des robots humanoïdes. Nous souhaitons par ailleurs montrer que l'estimation en temps réel à l'aide d'une centrale inertielle à faible coût est possible avec des méthodes d'optimisation tout en formulant les problèmes à l'aide d'un modèle graphique bien que ces méthodes soient réputées pour leurs coûts élevés en terme de calculs. Nous étudions également la calibration des centrales inertielles, une étape qui demeure critique pour leurs utilisations. Les travaux réalisés au cours de cette thèse ont été pensés en gardant comme perspective à moyen terme le SLAM visuel-inertiel. De plus, ce travail aborde une autre question concernant les robots à jambes. Contrairement à leur architecture habituelle, pourrions-nous utiliser plusieurs centrales inertielles à faible coût sur le robot pour obtenir des informations précieuses sur le mouvement en cours d'exécution ?
Estimation in robotics is an important subject affected by trade-offs between some major critera from which we can cite the computation time and the accuracy. The importance of these two criteria are application-dependent. If the computation time is not important for off-line methods, it becomes critical when the application has to run on real-time. Similarly, accuracy requirements are dependant on the applications. EKF estimators are widely used to satisfy real-time constraints while achieving acceptable accuracies. One sensor widely used in trajectory estimation problems remains the inertial measurement units (IMUs) providing data at a high rate. The main contribution of this thesis is a clear presentation of the preintegration theory yielding in a better use IMUs. We apply this method for estimation problems in both pedestrian and humanoid robots navigation to show that real-time estimation using a low- cost IMU is possible with smoothing methods while formulating the problems with a factor graph. We also investigate the calibration of the IMUs as it is a critical part of those sensors. All the development made during this thesis was thought with a visual-inertial SLAM background as a mid-term perspective. Firthermore, this work tries to rise another question when it comes to legged robots. In opposition to their usual architecture, could we use multiple low- cost IMUs on the robot to get valuable information about the motion being executed?

In this thesis the novel concept of Sycophant Wireless Sensors (SWS) is introduced. A SWS network is a static ectoparasitic clandestine sensor network mounted incognito on a mobile agent using only the agent&rsquo
s mobility without intervention. SWS networks not only communicate with each other through mobileWireless Sensor Networks (WSN) but also cooperate with them to form a global hybrid Wireless Sensor Network. Such a hybrid network has its own problems and opportunities, some of which have been studied in this thesis work. Assuming that direct position measurements are not always feasible tracking performance of the sycophant using range only measurements for various communication intervals is studied. Then this framework was used to create a hybrid 2D map of the environment utilizing the capabilities of the mobile network the sycophant. In order to show possible applications of a sycophant deployment, the sycophant sensor node was equipped with a laser ranger as its sensor, and it was let to create a 2D map of its environment. This 2D map, which corresponds to a height dierent than the follower network, was merged with the 2D map of the mobile network forming a novel rough 3D map. Then by giving up from the need to properly localize the sycophant even when it is disconnected to the rest of the network, a full 3D map of the environment is obtained by fusing 2D map and tracking capabilities of the mobile network with the 2D vertical scans of the environment by the sycophant. And finally connectivity problems that arise from the hybrid sensor/actuator network were solved. For this 2 new connectivity maintenance algorithms, one based on the helix structures of the proteins, and the other based on the acute triangulation of the space forming a Gabriel Graph, were introduced. In this new algorithms emphasis has been given to sparseness in order to increase fault tolerance to regional problems. To better asses sparseness a new measure, called Resistance was introduced, as well as another called updistance.

This thesis addresses the problem of localizing a vehicle in unstructured environments through on-board instrumentation that does not require infrastructure modifications. Two widely used opto-electronic systems which allow for non-contact measurements have been chosen: camera and laser range finder. Particular attention is paid to the definition of a set of procedures for processing the environment information acquired with the instruments in order to provide both accuracy and robustness to measurement noise. An important contribute of this work is the development of a robust and reliable algorithm for associating data that has been integrated in a graph based SLAM framework also taking into account uncertainty thus leading to an optimal vehicle motion estimation. Moreover, the localization of the vehicle can be achieved in a generic environment since the developed global localization solution does not necessarily require the identification of landmarks in the environment, neither natural nor artificial. Part of the work is dedicated to a thorough comparative analysis of the state-of-the-art scan matching methods in order to choose the best one to be employed in the solution pipeline. In particular this investigation has highlighted that a dense scan matching approach can ensure good performances in many typical environments. Several experiments in different environments, also with large scales, denote the effectiveness of the global localization system developed. While the laser range data have been exploited for the global localization, a robust visual odometry has been investigated. The results suggest that the use of camera can overcome the situations in which the solution achieved by the laser scanner has a low accuracy. In particular the global localization framework can be applied also to the camera sensor, in order to perform a sensor fusion between two complementary instrumentations and so obtain a more reliable localization system. The algorithms have been tested for 2D indoor environments, nevertheless it is expected that they are well suited also for 3D and outdoors.
La tesi affronta il problema della localizzazione di veicoli in ambienti non strutturati mediante sistemi di misura che, montati a bordo del veicolo, non richiedono modifiche dell'ambiente di navigazione. La scelta è ricaduta su due strumenti opto-elettronici largamente utilizzati, camera e Laser Range Finder (LRF), i quali consentono di effettuare misure senza contatto e quindi non intervenire sull'ambiente. Particolare attenzione è stata posta alla definizione di una serie di procedure per l'elaborazione dei dati acquisiti da questa strumentazione al fine di ottenere delle informazioni affidabili e robuste alle sorgenti di rumore ambientali. Un importante contributo di questo lavoro è lo sviluppo di un procedura di associazione robusta ed affidabile che consente di tener conto di tutti gli aspetti probabilistici in maniera tale da poter essere utilizzata in un algoritmo di localizzazione globale SLAM basato sulla teoria dei grafi e fornire una stima ottimale del moto del veicolo. Inoltre, la localizzazione del veicolo può essere eseguita in un ambiente generico dato che questo metodo di localizzazione globale non richiede l'identificazione di caratteristiche particolari nell'ambiente. Parte del lavoro è stata dedicata ad un'analisi esaustiva dei metodi di stima del moto fra scansioni laser, allo scopo di identificare il metodo con prestazioni migliori da impiegare nel metodo di localizzazione. Questo ha consentito di evidenziare come un metodo di comparazione denso permetta di ottenere buone prestazioni in diverse tipologie di ambiente. L'efficacia del metodo di localizzazione globale implementato è supportata da una serie di valutazioni sperimentali in diversi ambienti, anche di elevati dimensioni. Riguardo alla camera, è stato sviluppato un metodo robusto di visual odometry, il quale ha evidenziato come tale strumento permetta di affrontare delle situazioni nelle quali le informazioni del laser non sono sufficienti per stimare la posa del veicolo. In particolare, data la generalità del metodo di localizzazione globale, questo può essere facilmente applicato anche alla camera, al fine di ottenere la fusione di informazioni fra due strumentazioni complementari e quindi ottenere un sistema di localizzazione più affidabile. Gli algoritmi sono stati testati in un ambiente indoor bidimensionale, ma si prevede che possano essere utilizzati anche in ambienti tridimensionali e outdoor.

Micro aerial vehicles and other autonomous systems have the potential to truly transform life as we know it, however much of the potential of autonomous systems remains unrealized because reliable navigation is still an unsolved problem with significant challenges. This dissertation presents solutions to many aspects of autonomous navigation. First, it presents ROSflight, a software and hardware architure that allows for rapid prototyping and experimentation of autonomy algorithms on MAVs with lightweight, efficient flight control. Next, this dissertation presents improvments to the state-of-the-art in optimal control of quadrotors by utilizing the error-state formulation frequently utilized in state estimation. It is shown that performing optimal control directly over the error-state results in a vastly more computationally efficient system than competing methods while also dealing with the non-vector rotation components of the state in a principled way. In addition, real-time robust flight planning is considered with a method to navigate cluttered, potentially unknown scenarios with real-time obstacle avoidance. Robust state estimation is a critical component to reliable operation, and this dissertation focuses on improving the robustness of visual-inertial state estimation in a filtering framework by extending the state-of-the-art to include better modeling and sensor fusion. Further, this dissertation takes concepts from the visual-inertial estimation community and applies it to tightly-coupled GNSS, visual-inertial state estimation. This method is shown to demonstrate significantly more reliable state estimation than visual-inertial or GNSS-inertial state estimation alone in a hardware experiment through a GNSS-GNSS denied transition flying under a building and back out into open sky. Finally, this dissertation explores a novel method to combine measurements from multiple agents into a coherent map. Traditional approaches to this problem attempt to solve for the position of multiple agents at specific times in their trajectories. This dissertation instead attempts to solve this problem in a relative context, resulting in a much more robust approach that is able to handle much greater intial error than traditional approaches.

On assiste aujourd'hui à l'importation des NTIC (Nouvelles Technologies de l'Information et de la Télécommunication) dans la robotique. L'union de ces technologies donnera naissance, dans les années à venir, à la robotique de service grand-public.Cet avenir, s'il se réalise, sera le fruit d'un travail de recherche, amont, dans de nombreux domaines : la mécatronique, les télécommunications, l'automatique, le traitement du signal et des images, l'intelligence artificielle ... Un des aspects particulièrement intéressant en robotique mobile est alors le problème de la localisation et de la cartographie simultanée. En effet, dans de nombreux cas, un robot mobile, pour accéder à une intelligence, doit nécessairement se localiser dans son environnement. La question est alors : quelle précision pouvons-nous espérer en terme de localisation? Et à quel coût?Dans ce contexte, un des objectifs de tous les laboratoires de recherche en robotique, objectif dont les résultats sont particulièrement attendus dans les milieux industriels, est un positionnement et une cartographie de l'environnement, qui soient à la fois précis, tous-lieux, intègre, bas-coût et temps-réel. Les capteurs de prédilection sont les capteurs peu onéreux tels qu'un GPS standard (de précision métrique), et un ensemble de capteurs embarquables en charge utile (comme les caméras-vidéo). Ce type de capteurs constituera donc notre support privilégié, dans notre travail de recherche. Dans cette thèse, nous aborderons le problème de la localisation d'un robot mobile, et nous choisirons de traiter notre problème par l'approche probabiliste. La démarche est la suivante, nous définissons nos 'variables d'intérêt' : un ensemble de variables aléatoires. Nous décrivons ensuite leurs lois de distribution, et leur modèles d'évolution, enfin nous déterminons une fonction de coût, de manière à construire un observateur (une classe d'algorithme dont l'objectif est de déterminer le minimum de notre fonction de coût). Notre contribution consistera en l'utilisation de mesures GPS brutes GPS (les mesures brutes - ou raw-datas - sont les mesures issues des boucles de corrélation de code et de phase, respectivement appelées mesures de pseudo-distances de code et de phase) pour une navigation bas-coût précise en milieu extérieur suburbain. En utilisant la propriété dite 'entière' des ambiguïtés de phase GPS, nous étendrons notre navigation pour réaliser un système GPS-RTK (Real Time Kinematic) en mode différentiel local précise et bas-coût. Nos propositions sont validées par des expérimentations réalisées sur notre démonstrateur robotique
We are witnessing nowadays the importation of ICT (Information and Communications Technology) in robotics. These technologies will give birth, in upcoming years, to the general public service robotics. This future, if realised, shall be the result of many research conducted in several domains: mechatronics, telecommunications, automatics, signal and image processing, artificial intelligence ... One particularly interesting aspect in mobile robotics is hence the simultaneous localisation and mapping problem. Consequently, to access certain informations, a mobile robot has, in many cases, to map/localise itself inside its environment. The following question is then posed: What precision can we aim for in terms of localisation? And at what cost?In this context, one of the objectives of many laboratories indulged in robotics research, and where results impact directly the industry, is the positioning and mapping of the environment. These latter tasks should be precise, adapted everywhere, integrated, low-cost and real-time. The prediction sensors are inexpensive ones, such as a standard GPS (of metric precision), and a set of embeddable payload sensors (e.g. video cameras). These type of sensors constitute the main support in our work.In this thesis, we shed light on the localisation problem of a mobile robot, which we choose to handle with a probabilistic approach. The procedure is as follows: we first define our "variables of interest" which are a set of random variables, and then we describe their distribution laws and their evolution models. Afterwards, we determine a cost function in such a manner to build up an observer (an algorithmic class where the objective is to minimize the cost function).Our contribution consists of using brute GPS measures (brute measures or raw datas are measures issued from code and phase correlation loops, called pseudo-distance measures of code and phase, respectively) for a low-cost navigation, which is precise in an external suburban environment. By implementing the so-called "whole" property of GPS phase ambiguities, we expand the navigation to achieve a GPS-RTK (Real-Time Kinematic) system in a precise and low-cost local differential mode.Our propositions has been validated through experimentations realized on our robotic demonstrator

Ce travail traite la Modélisation 3D d'un environnement intérieur par un robot mobile. La principale contribution concerne la construction d'un modèle géométrique hétérogène combinant des amers plans texturés, des lignes 3D et des points d'intérêt. Pour cela, nous devons fusionner des données géométriques et photométriques. Ainsi, nous avons d'abord amélioré la stéréovision, en proposant une approche de la mise en correspondance stéréoscopique par coupure de graphe. Notre contribution réside dans la construction d'un graphe réduit qui a permis d'accélérer la méthode globale et d'obtenir de meilleurs résultats que les méthodes locales. Aussi, pour percevoir l'environnement, le robot est équipé d'un télémètre laser 3D et d'une caméra. Nous proposons une chaîne algorithmique permettant de construire une carte hétérogène, par l'algorithme de Cartographie et Localisation Simultanées (EKF-SLAM). Le placage de la texture sur les facettes planes a permis de solidifier l'association de données
This thesis examines the problem of 3D Modelling of indoor environment by a mobile robot. Our main contribution consists in constructing a heterogeneous geometrical model containing textured planar landmarks, 3D lines and interest points. For that, we must fuse geometrical and photometrical data. Hence, we began by improving the stereo vision algorithm, and proposed a new approach of stereo matching by graph cuts. The most significant contribution is the construction of a reduced graph that allows to accelerate the global method and to provide better results than the local methods. Also, to perceive the environment, the robot is equipped by a 3D laser scanner and by a camera. We proposed an algorithmic chain allowing to incrementally constructing a heterogeneous map, using the algorithm of Simultaneous Localization and Mapping based (EKF-SLAM). Mapping the texture on the planar landmarks makes more robust the phase of data association

Made available in DSpace on 2014-12-17T14:54:48Z (GMT). No. of bitstreams: 1 DiogoPFP_Tese.pdf: 4402228 bytes, checksum: 17eacb6b5f1731f405518c976d32f701 (MD5) Previous issue date: 2006-05-19
Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior
The objective of this thesis is proposes a method for a mobile robot to build a hybrid map of an indoor, semi-structured environment. The topological part of this map deals with spatial relationships among rooms and corridors. It is a topology-based map, where the edges of the graph are rooms or corridors, and each link between two distinct edges represents a door. The metric part of the map consists in a set of parameters. These parameters describe a geometric figure which adapts to the free space of the local environment. This figure is calculated by a set of points which sample the boundaries of the local free space. These points are obtained with range sensors and with knowledge about the robot s pose. A method based on generalized Hough transform is applied to this set of points in order to obtain the geomtric figure. The building of the hybrid map is an incremental procedure. It is accomplished while the robot explores the environment. Each room is associated with a metric local map and, consequently, with an edge of the topo-logical map. During the mapping procedure, the robot may use recent metric information of the environment to improve its global or relative pose
Esta tese tem o objetivo de propor uma metodologia para constru??o de um mapa h?brido de um ambiente interno. A parte topol?gica da representa??o trata das rela??es de conectividade existentes entre as salas e corredores, sendo assim um grafo que representa a topologia do ambiente global. A parte m?trica consiste em armazenar um conjunto de par?metros que descreve uma figura geom?trica plana que melhor se ajusta ao espa?o livre local. Esta figura ? calculada atrav?s do conhecimento de pontos, ou amostras, dos limites do espa?o livre. Estes pontos s?o obtidos com sensores de dist?ncia e a informa??o ? complementada com a estimativa da pose do rob?. Uma vez que estes pontos est?o determinados, o rob? ent?o aplica uma ferramenta baseada na transformada generalizada de Hough para obter a figura em quest?o. O processo de constru??o do mapa ? incremental e totalmente realizado enquanto o rob? explora o ambiente. Cada sala ? representada por este mapa local e cada n? do grafo que representa a topologia do ambiente est? associado a este mapa. Durante o mapeamento o rob? pode utilizar as informa??es rec?m-adquiridas do ambiente para obter uma melhor estimativa de sua pose global ou relativa a uma sala ou corredor

To date, technology is in constant development, and researchers all over the world are pushing its boundaries every day further. In particular, Robotics is one of the fields that is currently in great expansion, entering into our daily lives in many ways - e.g. autonomous driving cars, service robots, video-games. Intelligent systems have several basic requirements to safely accomplish tasks in the real world. Among them we include i) having a digital map of the environment in which these agents are placed and ii) the ability to localize themselves in such a map. The problem of building a map while estimating the agent’s pose is known in Robotic research as Simultaneous Localization and Mapping (SLAM). As an example, an autonomous car that is asked to reach a location and, thus, has to traverse the city, needs to know the configuration of its surroundings in real-time, including the position of pedestrians, cars, bikes, and every other dynamic (or static) obstacle. Global positioning infrastructures - e.g. GPS - do not provide information on the surroundings and their signal is not always available. For this reason, other sensing modalities are generally used to accomplish such tasks efficiently. This thesis focuses on SLAM, investigating ways to increase the robustness and scalability of the solutions to this problem. More in detail, we will aim the attention to graph- based SLAM systems, which represent the most common choice in state-of-the-art pipelines. In such formalization, Least-Squares optimization represents the foundation of the entire estimation process, allowing it to achieve good accuracy without violating the real-time constraint of Robotic applications. In particular, we will investigate how non-minimal over-parametrizations of the optimization entities contribute to the accuracy, robustness, and scalability of the system. Traditionally, minimal parametrizations are used in the Least-Squares estimation process at different levels: i) to apply small increments to state variables, ii) to represent measurements, and iii) to express local distances between prediction and measurement. Still, such minimal parametrizations might be hard to compute, leading to complex mathematical derivations in the minimization algorithm. Conversely, extended parametrizations introduce additional parameters in the estimation process, possibly leading to a relaxed version of the original problem which can be solved more easily. Leveraging on this concept, we introduced a non-minimal error function in the context of global optimization, aiming to enlarge the converge basin and the overall robustness to noise. Then, we addressed how the map is represented, exploiting a novel extended landmark formalization that allows representing multiple geometric primitives as a unique object. Finally, we present a novel Least-Square optimization framework, which is specifically designed for SLAM pipelines and that can be easily extended to accommodate new solutions - such as the ones previously proposed. All of our contributions are open-source and publicly available to the research community. We believe that this is an important aspect of research, allowing to easily reproduce the results obtained in the proposed experiments while fostering the collaboration with other members of the community.

碩士
國立臺灣大學
電機工程學研究所
102
The objective of this thesis is to develop simultaneous localization and mapping (SLAM) with capability of tracking moving object in indoor environments. SLAM can help build environment map, while detection and tracking of moving object separate the environment into static and dynamic parts. The map can help detect the moving object, on the other hand, the moving object tracking can help separate the stationary and moving objects, thus we can separate them in the map. By augmenting the moving objects state and related constraints into the robot and objects graph, the general graph-based framework for SLAM issues can be extended to jointly optimize the SLAM and moving object tracking result. By incorporating the moving object prediction and moving object Retro-BestGuess, the later measurement of moving object can help the estimation of the previous state and vice versa. Consequently, the trajectory of robot together with the trajectories of moving objects is optimized. Furthermore, the SLAM with moving object tracking issues in the cluttered indoor environment are analyzed, the moving object may have different size and characteristics difficult to modelling, and the data association is difficult. The multi-frame moving object detection is applied to detect the moving object without the need of prior knowledge, by which even the slightly movement can be detected. The multi-sensor fusion methodologies can help increase the data association accuracy. The experimental results shown that our algorithm is feasible in cluttered indoor environment, graph-based SLAM incorporating moving objects can decrease the pose estimation uncertainty compare to the one not incorporating them.

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.

Localization is critical for self-awareness of any autonomous system and is an important part of the autonomous system stack which consists of many phases including sensing, perceiving, planning and control. In the sensing phase, data from on board sensors are collected, preprocessed and passed to the next phase. The perceiving phase is responsible for self awareness or localization and situational awareness which includes multi-objects detection and scene understanding. After the autonomous system is aware of where it is and what is around it, it can use this knowledge to plan for the path it can take and send control commands to pursue this path. In this proposal, we focus on the localization part of the autonomous stack using camera images. We deal with the localization problem from different perspectives including single images and videos. Starting with the single image pose estimation, our approach is to propose systems that not only have good localization accuracy, but also have low space and time complexity. Firstly, we propose SurfCNN, a low cost indoor localization system that uses SURF descriptors instead of the original images to reduce the complexity of training convolutional neural networks (CNN) for indoor localization application. Given a single input image, the strongest SURF features descriptors are used as input to 5 convolutional layers to find its absolute position and orientation in arbitrary reference frame. The proposed system achieves comparable performance to the state of the art using only 300 features without the need for using the full image or complex neural networks architectures. Following, we propose SURF-LSTM, an extension to the idea of using SURF descriptors instead the original images. However, instead of CNN used in SurfCNN, we use long short term memory (LSTM) network which is one type of recurrent neural networks (RNN) to extract the sequential relation between SURF descriptors. Using SURF-LSTM, We only need 50 features to reach comparable or better results compared with SurfCNN that needs 300 features and other works that use full images with large neural networks. In the following research phase, instead of using SURF descriptors as image features to reduce the training complexity, we study the effect of using features extracted from other CNN models that were pretrained on other image tasks like image classification without further training and fine tuning. To learn the pose from pretrained features, graph neural networks (GNN) are adopted to solve the single image localization problem (Pose-GNN) by using these features representations either as features of nodes in a graph (image as a node) or converted into a graph (image as a graph). The proposed models outperform the state of the art methods on indoor localization dataset and have comparable performance for outdoor scenes. In the final stage of single image pose estimation research, we study if we can achieve good localization results without the need for training complex neural network. We propose (Linear-PoseNet) by which we can achieve similar results to the other methods based on neural networks with training a single linear regression layer on image features from pretrained ResNet50 in less than one second on CPU. Moreover, for outdoor scenes, we propose (Dense-PoseNet) that have only 3 fully connected layers trained on few minutes that reach comparable performance to other complex methods. The second localization perspective is to find the relative poses between images in a video instead of absolute poses. We extend the idea used in SurfCNN and SURF-LSTM systems and use SURF descriptors as feature representation of the images in the video. Two systems are proposed to find the relative poses between images in the video using 3D-CNN and 2DCNN-RNN. We show that using 3D-CNN is better than using the combination of CNN-RNN for relative pose estimation.
Graduate