<  Back to the Polytechnique Montréal portal

Détermination d'une métrique pour le problème de localisation et cartographie simultanées

Alexandre Aubert

Masters thesis (2013)

[img]
Preview
Download (8MB)
Cite this document: Aubert, A. (2013). Détermination d'une métrique pour le problème de localisation et cartographie simultanées (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/1227/
Show abstract Hide abstract

Abstract

Résumé Les robots mobiles ont une autonomie limitée lorsqu'ils se retrouvent en environnement inconnu. Ils doivent alors construire une carte de leur environnement tout en s'y situant en même temps. Cette carte servira par la suite à la planification de trajectoire pour que le robot puisse effectuer sa tâche. Cette carte globale se doit donc d'être la plus précise possible, sinon le robot pourrait rencontrer des obstacles nuisibles et ne jamais atteindre la destination désirée. Le processus pour obtenir cette carte est composé d'une première phase d'acquisition où le robot utilise un LIDAR lui permettant de modéliser son environnement immédiat par un nuage de points. Ensuite, il faut relier les acquisitions entre elles le plus fidèlement possible pour obtenir un nuage de points couvrant une plus grande partie de l'environnement. Les balayages sont d'abord regroupés deux par deux par un algorithme de recalage appelé ICP. Cette technique est très efficace lorsque l'estimé initial de la position est près du résultat recherché. Par contre, lorsque ces conditions initiales sont plus erronées, il est fortement possible de converger vers un minimum local. Cette erreur de recalage se propage ensuite lorsque le robot continue sa trajectoire. Il est donc important de trouver une technique permettant de qualifier le résultat d'un recalage et ainsi de rejeter les mauvaises informations. La métrique proposée dans ce travail est un algorithme de discrimination où plusieurs paramètres sont comparés entre eux. Une base de données composée de plusieurs bons et mauvais résultats séparés en deux groupes respectifs a été créée. Elle permet ensuite de comparer un nouveau recalage par rapport à ces deux groupes et d'attribuer une probabilité d'appartenance à chacun des groupes. Ces valeurs donnent alors une indication de la fiabilité du recalage. Les résultats obtenus donnent un taux d'erreur de classification de 2.12%. Cette métrique est par la suite utilisée pour corriger l'accumulation d'erreurs au cours d'une longue trajectoire. En effet, lorsque le robot revisite un endroit déjà modélisé, il obtient de nouvelles informations permettant d'effectuer une correction sur sa position estimée et ainsi de réduire l'erreur accumulée. Ceci est fait à l'aide d'un algorithme de distribution d'erreur où le lien entre chaque paire de balayages est modélisé par des ressorts. L'ensemble des ressorts et des balayages constitue alors un système dynamique qui aura tendance à converger vers une position stable qui correspond au minimum d'énergie. Les positions estimées des balayages seront alors modifiées et l'erreur accumulée sera corrigée pour obtenir une carte globale de l'environnement qui est plus uniforme. La métrique de recalage permet de déterminer les constantes de raideurs des ressorts. Ainsi, les recalages moins fiables seront représentés par des ressorts plus flexibles qui pourront s'étirer pour mieux respecter les contraintes des ressorts plus rigides correspondant aux bons recalages.----------Abstract Mobile robots have a limited autonomy when they are placed in an unknown environment. They must simultaneously create a map and position themself on that map. Then the robot will be able to plan his trajectory to avoid obstacles and accomplish its task. The global map must be precise, otherwise the robot could hit an obstacle or get lost and not reach his destination. The first step to obtain this global map is to use a LIDAR to scan the immediate environment and modelize it by a scatter plot. Then, scans are registered together to create a bigger scatter plot and so on. The scans are first registered two by two with a registration algorithm called ICP. This algorithm leads to a very good estimate of the position if the initial conditions are good enough. Otherwise, it may converge towards a local minima and introduce an error in the global map. This error is then propagated along the robot path. Thus, it is very important to qualify the registration result to be able to reject false informations. This work introduces a discrimination algorithm which compares specific parameters to obtain a registration metric. A database composed of multiple registration results has been created. It is composed of two distinct groups which are the good and the bad results. Then, a new registration result can be compared against these groups to see which ones it relates the most to. The probability of appartenance of this new data to each group gives the probability that the registration converged toward the solution. The parameters used in the discrimination algorithm give an apparent error rate of 2.12%.This metric is then used to minimize the error accumulation during long trajectories. When the robot reaches a previously visited location, it can acquire new data and this new information can be used to correct its estimated position and reduce the errors accumulated during its journey. An error distribution error is used to make this correction. Virtual springs are connected between each pair of scans. Then, the springs and scans constitute a dynamic system which naturally tends towards a stable position consisting of an energy minimum. The new scans position consist of a more consistent map where the error is equally distributed. The registration metric can be used to assign the stiffness of the springs. A less reliable registration result leads to a less stiff spring which can stretch to meet the constraints of the other springs representing better registration results.

Open Access document in PolyPublie
Department: Département de génie électrique
Dissertation/thesis director: Richard Gourdeau
Date Deposited: 03 Feb 2014 13:20
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/1227/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only