Efficient localization and mapping for robotics : algorithms and tools

Abstract

Um dos problemas fundamentais em robótica é a capacidade de estimar a pose de um robô móvel relativamente ao seu ambiente. Este problema é conhecido como localização robótica e a sua exatidão e eficiência têm um impacto direto em todos os sistemas que dependem da localização. Nesta tese, abordamos o problema da localização propondo um algoritmo baseado em scan matching com otimização robusta de mínimos quadrados não lineares em manifold com a utilização de um campo de verosimilhança contínuo como modelo de perceção. Esta solução oferece uma melhoria percetível na eficiência computacional sem perda de exatidão. Associado à localização está o problema de criar uma representação geométrica (ou mapa) do meio ambiente recorrendo às medidas disponíveis, um problema conhecido como mapeamento. No mapeamento a representação geométrica mais popular é a grelha volumétrica que discretiza o espaço em volumes cúbicos de igual tamanho. A implementação direta de uma grelha volumétrica oferece acesso direto e rápido aos dados mas requer uma quantidade substancial de memória. Portanto, propõe-se uma estrutura de dados híbrida, com divisão esparsa do espaço combinada com uma subdivisão densa do espaço que oferece tempos de acesso eficientes com alocações de memória reduzidas. Além disso, também oferece um mecanismo integrado de compressão de dados para reduzir ainda mais o uso de memória e uma estrutura de partilha de dados implícita que duplica dados, de forma eficiente, quando necessário recorrendo a uma estratégia copy-on-write. A implementação da solução descrita é disponibilizada na forma de uma biblioteca de software que oferece um framework para a criação de modelos baseados em grelhas volumétricas, e.g. grelhas de ocupação. Como existe uma separação entre o modelo e a gestão de espaço, todas as funcionalidades da abordagem esparsa-densa estão disponíveis para qualquer modelo implementado com o framework. O processo de mapeamento é um problema complexo considerando que localização e mapeamento são resolvidos simultaneamente. Este problema, conhecido como localização e mapeamento simultâneo (SLAM), tem tendência a de consumir recursos consideráveis à medida que a exigência na qualidade do mapeamento aumenta. De modo a contribuir para o aumento da eficiência, esta tese apresenta duas solução de SLAM. Na primeira abordagem, o algoritmo de localização é adaptado ao mapeamento incremental que, em combinação com o framework esparso-denso, oferece uma solução de SLAM online computacionalmente eficiente. O resultados obtidos são comparados com outras soluções disponíveis na literatura recorrendo a um benchmark de SLAM. Os resultados obtidos demonstram que a nossa solução oferece uma boa eficiência sem comprometer a exatidão. A segunda abordagem combina o nosso SLAM online com um filtro de partículas Rao-Blackwellized para propor uma solução de full SLAM com um grau elevado de eficiência computacional. A solução inclui propostas de distribuição melhorada com refinamento de pose através de scan matching, re-amostragem adaptativa com pesos de amostragem suavizados, partilha eficiente de dados entre partículas da mesma geração e suporte para multi-threading.

One of the most basic perception problems in robotics is the ability to estimate the pose of a mobile robot relative to the environment. This problem is known as mobile robot localization and its accuracy and efficiency has a direct impact in all systems than depend on localization. In this thesis, we address the localization problem by proposing an algorithm based on scan matching with robust non-linear least squares optimization on a manifold that relies on a continuous likelihood field as measurement model. This solution offers a noticeable improvement in computational efficiency without losing accuracy. Associated with localization is the problem of creating the geometric representation (or map) of the environment using the available measurements, a problem known as mapping. In mapping, the most popular geometric representation is the volumetric grid that quantizes space into cubic volumes of equal size. The regular volumetric grid implementation offers direct and fast access to data but requires a substantial amount of allocated memory. Therefore, in this thesis, we propose a hybrid data structure with sparse division of space combined with dense subdivision of space that offers efficient access times with reduced memory allocation. Additionally, it offers an online data compression mechanism to further reduce memory usage and an implicit data sharing structure that efficiently duplicates data when needed using a thread safe copy-on-write strategy. The implementation of the solution is available as a software library that provides a framework to create models based on volumetric grids, e.g. occupancy grids. The separation between the model and space management makes all features of the sparse-dense approach available to every model implemented with the framework. The process of mapping is a complex problem, considering that localization and mapping have to be solved simultaneously. This problem, known as simultaneous localization and mapping (SLAM), has the tendency to consume considerable resources as the mapping quality requirements increase. As an effort to increase the efficiency of SLAM, this thesis presents two SLAM solutions. The first proposal adapts our localization algorithm to incremental mapping that, in combination with the sparse-dense framework, provides a computationally efficient online SLAM solution. Using a SLAM benchmark, the obtained results are compared with other solutions found in the literature. The comparison shows that our solution provides good efficiency without compromising accuracy. The second approach combines our online SLAM with a Rao-Blackwellized particle filter to propose a highly computationally efficient full SLAM solution. It includes an improved proposal distribution with scan matching pose refinement, adaptive resampling with smoothed importance weight, efficient sharing of data between sibling particles and multithreading support.