RT Dissertation/Thesis
T1 Global Localization based on Evolutionary Optimization Algorithms for Indoor and Underground Environments
A1 Carballeira López, Juan
AB A fully autonomous robot is defined by its capability to sense, understand and movewithin the environment to perform a specific task. These qualities are included withinthe concept of navigation. However, among them, a basic transcendent one is localization,the capacity of the system to know its position regarding its surroundings.Therefore, the localization issue could be defined as searching the robot’s coordinatesand rotation angles within a known environment. In this thesis, the particular caseof Global Localization is addressed, when no information about the initial positionis known, and the robot relies only on its sensors. This work aims to develop severaltools that allow the system to locate in the two most usual geometric map representations:occupancy maps and Point Clouds. The former divides the dimensionalspace into equally-sized cells coded with a binary value distinguishing between freeand occupied space. Point Clouds define obstacles and environment features as asparse set of points in the space, commonly measured through a laser sensor.In this work, various algorithms are presented to search for that position throughlaser measurements only, in contrast with more usual methods that combine externalinformation with motion information of the robot, odometry. Therefore, the systemis capable of finding its own position in indoor environments, with no necessity ofexternal positioning and without the influence of the uncertainty that motion sensorstypically induce. Our solution is addressed by implementing various stochastic optimizationalgorithms or Meta-heuristics, specifically those bio-inspired or commonlyknown as Evolutionary Algorithms. Inspired by natural phenomena, these algorithmsare based on the evolution of a series of particles or population members towards asolution through the optimization of a cost or fitness function that defines the problem.The implemented algorithms are Differential Evolution, Particle Swarm Optimization,and Invasive Weed Optimization, which try to mimic the behavior of evolutionthrough mutation, the movement of swarms or flocks of animals, and the colonizingbehavior of invasive species of plants respectively. The different implementationsaddress the necessity to parameterize these algorithms for a wide search space asa complete three-dimensional map, with exploratory behavior and the convergenceconditions that terminate the search. The process is a recursive optimum estimation search, so the solution is unknown. These implementations address the optimumlocalization search procedure by comparing the laser measurements from the real positionwith the one obtained from each candidate particle in the known map. Thecost function evaluates this similarity between real and estimated measurements and,therefore, is the function that defines the problem to optimize.The common approach in localization or mapping using laser sensors is to establishthe mean square error or the absolute error between laser measurements as anoptimization function. In this work, a different perspective is introduced by benefitingfrom statistical distance or divergences, utilized to describe the similarity betweenprobability distributions. By modeling the laser sensor as a probability distributionover the measured distance, the algorithm can benefit from the asymmetries providedby these divergences to favor or penalize different situations. Hence, how the laserscans differ and not only how much can be evaluated. The results obtained in differentmaps, simulated and real, prove that the Global Localization issue is successfullysolved through these methods, both in position and orientation. The implementationof divergence-based weighted cost functions provides great robustness and accuracyto the localization filters and optimal response before different sources and noise levelsfrom sensor measurements, the environment, or the presence of obstacles that are notregistered in the map.
AB Lo que define a un robot completamente autónomo es su capacidad para percibir el entorno,comprenderlo y poder desplazarse en ´el para realizar las tareas encomendadas.Estas cualidades se engloban dentro del concepto de la navegación, pero entre todasellas la más básica y de la que dependen en buena parte el resto es la localización,la capacidad del sistema de conocer su posición respecto al entorno que lo rodea. Deesta forma el problema de la localización se podría definir como la búsqueda de lascoordenadas de posición y los ángulos de orientación de un robot móvil dentro de unentorno conocido. En esta tesis se aborda el caso particular de la localización global,cuando no existe información inicial alguna y el sistema depende únicamente de sussensores. El objetivo de este trabajo es el desarrollo de varias herramientas que permitanque el sistema encuentre la localización en la que se encuentra respecto a losdos tipos de mapa más comúnmente utilizados para representar el entorno: los mapasde ocupación y las nubes de puntos. Los primeros subdividen el espacio en celdasde igual tamaño cuyo valor se define de forma binaria entre espacio libre y ocupado.Las nubes de puntos definen los obstáculos como una serie dispersa de puntos en elespacio comúnmente medidos a través de un láser.En este trabajo se presentan varios algoritmos para la búsqueda de esa posición utilizando únicamente las medidas de este sensor láser, en contraste con los métodos máshabituales que combinan información externa con información propia del movimientodel robot, la odometría. De esta forma el sistema es capaz de encontrar su posiciónen entornos interiores sin depender de posicionamiento externo y sin verse influenciadopor la deriva típica que inducen los sensores de movimiento. La solución seafronta mediante la implementación de varios tipos de algoritmos estocásticos de optimización o Meta-heurísticas, en concreto entre los denominados bio-inspirados ocomúnmente conocidos como Algoritmos Evolutivos. Estos algoritmos, inspirados envarios fenómenos de la naturaleza, se basan en la evolución de una serie de partículaso población hacia una solución en base a la optimización de una función de coste quedefine el problema.Los algoritmos implementados en este trabajo son Differential Evolution, ParticleSwarm Optimization e Invasive Weed Optimization, que tratan de imitar el comportamientode la evolución por mutación, el movimiento de enjambres o bandas de animales y la colonización por parte de especies invasivas de plantas respectivamente.Las distintas implementaciones abordan la necesidad de parametrizar estos algoritmospara un espacio de búsqueda muy amplio como es un mapa completo, con lanecesidad de que su comportamiento sea muy exploratorio, así como las condicionesde convergencia que definen el fin de la búsqueda ya que al ser un proceso recursivode estimación la solución no es conocida. Estos algoritmos plantean la forma debuscar la localización ´optima del robot mediante la comparación de las medidas delláser en la posición real con lo esperado en la posición de cada una de esas partículasteniendo en cuenta el mapa conocido. La función de coste evalúa esa semejanza entrelas medidas reales y estimadas y por tanto, es la función que define el problema.Las funciones típicamente utilizadas tanto en mapeado como localización medianteel uso de sensores láser de distancia son el error cuadrático medio o el errorabsoluto entre distancia estimada y real. En este trabajo se presenta una perspectivadiferente, aprovechando las distancias estadísticas o divergencias, utilizadas paraestablecer la semejanza entre distribuciones probabilísticas. Modelando el sensorcomo una distribución de probabilidad entorno a la medida aportada por el láser, sepuede aprovechar la asimetría de esas divergencias para favorecer o penalizar distintassituaciones. De esta forma se evalúa como difieren las medias y no solo cuanto. Losresultados obtenidos en distintos mapas tanto simulados como reales demuestran queel problema de la localización se resuelve con éxito mediante estos métodos tanto respectoal error de estimación de la posición como de la orientación del robot. El uso delas divergencias y su implementación en una función de coste ponderada proporcionagran robustez y precisión al filtro de localización y gran respuesta ante diferentesfuentes y niveles de ruido, tanto de la propia medida del sensor, del ambiente y deobstáculos no modelados en el mapa del entorno.
YR 2022
FD 2022-06
LK https://hdl.handle.net/10016/36518
UL https://hdl.handle.net/10016/36518
LA eng
NO Mención Internacional en el título de doctor
DS e-Archivo
RD 1 sept. 2024