Highly accurate lidar-based mapping and localization for mobile robots

Abstract: This thesis contributes novel concepts, methods, and algorithms to the topic of mapping and localization for mobile robots. Mapping is the process of building a model of the robot's environment based on a collection of sensor measurements, while localization refers to the process of using the resulting map and incoming sensor measurements to estimate the current location of the robot. Together, mapping and localization enable the robot to navigate the world -- a prerequisite for any meaningful application of a mobile robot.

All of our contributions assume that the mobile robot is equipped with a lidar sensor.
Lidar is an acronym of "light detection and ranging", hinting at the operating principle of a lidar sensor: Typically, it continuously emits light pulses, waits for each pulse to be reflected by a nearby object, measures the time of flight, and uses this measurement to compute the distance to the object.

Our first contribution is a novel mathematical model for lidar sensors. By describing the interaction between the sensor and its environment mathematically, it constitutes the theoretical centerpiece of any mapping and localization algorithm. In contrast to related approaches, the proposed model formulates the reflection probability of a light ray emitted by the lidar as an exponential decay process, hence the name decay-rate model. This formulation yields several advantages compared to existing approaches, the most important being that the model makes use of the full ray-path information contained in the measurements. In this way, it achieves higher localization accuracy than comparable methods, which process only part of this information. To the best of our knowledge, it is also the first beam-based lidar sensor model that is not bound to the notion of voxels. Consequently, the decay-rate model is the first model to truly enable continuous mapping, a fact we make use of in our third contribution.

The second contribution advances the way in which grid maps produced by the reflection model or the decay-rate model represent the world. Conventionally, these models are used to create maximum-likelihood grid maps of the robot's environment.
Maximum-likelihood maps encode for each cell the mode of the underlying probability distribution over all possible map values. In this thesis, we show that it is possible to represent the full posterior probability distribution of each cell using only two variables -- without increasing the computational complexity required to create the map.
Our mathematical proof is carried out in closed form and without any simplifications. We also demonstrate that keeping track of the full posterior significantly improves localization performance compared to working with the mode of the distribution only.

The third contribution introduces another innovation to the way the map represents the environment. Instead of tessellating the space and assigning a value to each cell, it proposes a novel continuous representation that is based on the discrete cosine transform. The resulting maps are hence called DCT maps. Built upon the decay-rate model, the major advantage of DCT maps over related continuous lidar-based mapping approaches lies in their consistent nature, which allows to use them not only for mapping, but also for localization: While other continuous maps require re-tessellation to compute the probability of a given lidar measurement, DCT maps naturally support this operation. Furthermore, our experiments show that DCT maps outperform other map types in terms of memory efficiency.

The remainder of this thesis addresses another highly relevant aspect of mapping and localization: feature extraction. In contrast to dense map representations like grid maps or continuous maps, feature-based maps model the environment as a collection of objects in empty space, yielding memory-efficient maps that abstract from the modality of the sensors in use, that improve system robustness, and that can encode semantics.

First, we focus on polylines extracted from 2-D lidar scans. The polyline detection method proposed within the scope of our fourth contribution follows a maximum-likelihood approach that considers the full ray-path information contained in the lidar measurements. Extensive real-world and simulated experiments show that this probabilistic approach outperforms the rich collection of state-of-the-art methods in terms of accuracy.

Building upon this method, our fifth contribution suggests an analogous approach to extract finite planes from 3-D lidar scans. Due to the deficiencies of the most popular benchmarking dataset for plane extraction algorithms based on lidar data, we also present a novel synthetic dataset in the scope of this work.

Our last contribution does not only present a novel approach to detect pole features in 3-D lidar scans, but a complete mapping and localization framework based on poles. The comparative experiments conducted in the scope of this work already demonstrate the proposed method's superior localization accuracy. In addition, while related methods are often tested on proprietary datasets with durations of only a few minutes, we showcase the performance and robustness of our approach by evaluating it on a public long-term dataset that contains 35 hours of data recorded over the course of 15 months
Abstract: Die vorliegende Dissertation stellt neuartige Konzepte, Methoden und Algorithmen vor, um eine Karte der Umgebung eines mobilen Roboters zu erstellen und seine Position anhand dieser Karte zu bestimmen. Sie beschäftigt sich also mit den grundlegenden Fähigkeiten eines jeden mobilen Roboters. Ohne Kartierung und Positionsschätzung kann er sich nicht in der Welt zurechtfinden. Dabei spielen die Daten, die die Sensoren des Roboters liefern, eine wichtige Rolle. Im Folgenden gehen wir immer davon aus, dass der Roboter mit einem Lidarsensor ausgestattet ist. Lidar steht für "light detection and ranging", was bereits auf die Funktionsweise dieser Art von Sensoren hindeutet: Typischerweise sendet ein Lidarsensor kontinuierlich Lichtpulse aus. Nach jedem Puls wartet er eine gewisse Zeit darauf, dass das Licht von einem Objekt in der Umgebung reflektiert wird. Wird der Puls reflektiert, misst der Sensor die Zeit, die zwischen Aussenden des Pulses und Detektion der Reflexion vergangen ist, und berechnet daraus den Abstand zum reflektierenden Objekt.

Im ersten Teil dieser Arbeit stellen wir ein neuartiges mathematisches Sensormodell für Lidarsensoren vor. Es beschreibt die Interaktion zwischen Sensor und Umgebung formal und ist deshalb Herzstück eines jeden Kartierungs- oder Positionsbestimmungsalgorithmus. Im Gegensatz zu bisherigen Arbeiten auf diesem Gebiet modelliert es die Wahrscheinlichkeit, dass ein vom Sensor emittierter Lichtstrahl reflektiert wird, als exponentiellen Zerfallsprozess. Daraus ergeben sich einige Vorteile. Beispielsweise verarbeitet unsere Methode nicht nur einen Teil, sondern die vollständige Information über den Strahlengang der Lichtpulse, was zu einer höheren Genauigkeit bei der Positionsschätzung führt. Weiterhin ist unser Sensormodell das erste, das zwar den Strahlengang berücksichtigt, dabei aber nicht darauf angewiesen ist, dass der Raum zuvor gerastert, sprich in Zellen eingeteilt wird. Das macht es zum ersten Sensormodell, das sowohl Kartierung als auch Positionsschätzung mit kontinuierlichen Karten ermöglicht -- eine Tatsache, auf die wir im dritten Teil dieser Arbeit genauer eingehen.

Im zweiten Teil der vorliegenden Dissertation präsentieren wir eine Methode, um den Informationsgehalt von Rasterkarten aus Lidardaten wesentlich zu erhöhen. Während jede Zelle einer herkömmlichen Rasterkarte meist den wahrscheinlichsten Kartenwert enthält, zeigen wir, wie man dort die komplette Wahrscheinlichkeitsverteilung über alle möglichen Kartenwerte in kompakter Form speichert, ohne die Berechnungskomplexität zu erhöhen. Die mathematische Herleitung erfolgt in geschlossener Form und kommt ohne Näherungen aus. Unsere Experimente zeigen, dass die resultierenden Karten die Güte der Positionsschätzung gegenüber herkömmlichen Karten signifikant verbessern.

Im dritten Teil geht es nicht mehr um Rasterkarten, sondern um eine neuartige kontinuierliche Kartenrepräsentation, die auf der diskreten Kosinustransformation beruht. Der wesentliche Vorteil dieser Methode gegenüber bestehenden kontinuierlichen Lidarkarten liegt darin, dass sie sowohl zur Kartierung als auch zur Positionsbestimmung eingesetzt werden kann. Bestehende Ansätze erlauben es zwar, kontinuierliche Karten zu erstellen. Um bei der Positionsschätzung die Wahrscheinlichkeit einer gegebenen Lidarmessung auf Basis einer solchen Karte zu bestimmen, musste die Karte aber bisher wieder gerastert werden. Ein weiterer Vorteil des neu vorgestellten Kartentyps gegenüber vergleichbaren Arbeiten ist seine hohe Speichereffizienz.

In den verbleibenden Teilen der Arbeit wenden wir uns einem weiteren wichtigen Aspekt der Kartierung und Positionsschätzung zu: der Erkennung von Features. Unter Features verstehen wir abstrakte Merkmale in Sensordaten, zum Beispiel Linien in einem Kamerabild oder ebene Flächen in einer Punktwolke. Nutzt man Features statt Sensorrohdaten zur Kartierung, erhält man eine Featurekarte. Featurekarten unterscheiden sich dadurch von den oben beschriebenen dichten Kartentypen, sprich kontinuierlichen und Rasterkarten, dass sie die Welt als eine Sammlung von Objekten in ansonsten leerem Raum modellieren. Dieser Ansatz spart Speicherplatz, vereinfacht die Integration von Daten aus unterschiedlichen Sensormodalitäten, er kann die Robustheit des Gesamtsystems erhöhen und ermöglicht es, semantische Informationen in die Karten aufzunehmen.

Unsere erste Arbeit zum Thema Featureerkennung beschäftigt sich mit der Detektion von zusammenhängenden linienförmigen Konturen in planaren Lidardaten. Die Erkennung solcher Konturen ist beispielsweise nützlich, um den Grundriss eines Gebäudes in den Daten zu erkennen, die ein horizontal am Roboter angebrachter Lidar liefert. Der entwickelte Ansatz beruht auf dem Prinzip, die kombinierte Wahrscheinlichkeit aller Messungen zu maximieren. Dabei nutzt er die in den Sensordaten enthaltene Information über den Strahlengang der vom Sensor ausgesendeten Lichtpulse vollständig aus. Im Rahmen ausführlicher Experimente mit echten und simulierten Daten zeigen wir, dass die entwickelte Methode eine signifikant höhere Genauigkeit erreicht als vergleichbare Ansätze.

Aufbauend auf dieser Arbeit beschreibt der nächste Teil der Dissertation einen analogen Ansatz zur Erkennung finiter Ebenen in 3-D-Lidardaten. Da der Datensatz, der normalerweise zum Vergleich solcher Ebenenerkennungsalgorithmen herangezogen wird, in die Jahre gekommen ist und zahlreiche Nachteile aufweist, stellen wir weiterhin einen Nachfolger vor, der synthetisch generierte Lidardaten enthält.

Der letzte Teil der Dissertation dreht sich um Pfosten-Features in 3-D-Lidardaten, also Objekte, die einem stehenden Zylinder gleichen, zum Beispiel Poller, Baumstämme, Masten von Straßenschildern und Lampen. Wir stellen ein komplettes System zur Positionsbestimmung basierend auf diesen Features vor, bestehend aus einem Modul zur Featuredetektion, einem Kartierungsmodul und einem Positionsschätzer. Vergleichsexperimente mit ähnlichen Methoden zeigen, dass der vorgeschlagene Ansatz die Roboterposition genauer schätzt. Während andere Ansätze meist nur auf einem wenige Minuten langen, nichtöffentlichen Datensatz ausgewertet werden, demonstrieren wir zusätzlich die Leistungsfähigkeit und Robustheit unseres Ansatzes über lange Zeiträume hinweg. Dazu evaluieren wir ihn auf einem frei verfügbaren Langzeitdatensatz, der 35 Stunden Daten enthält, die über einen Zeitraum von 15 Monaten aufgenommen wurden

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Notes: Universität Freiburg, Dissertation, 2020

Classification and Topics

• Classification: Elektrotechnik, Elektronik
• Keyword: Robotik ; Lidar ; Automatische Kartierung ; Lokalisierung ; Wahrscheinlichkeitsrechnung ; Ray tracing ; Feature ; Diskrete Fourier-Kosinustransformation

Contributors, Places and Time

• Event: Veröffentlichung
• (where): Freiburg
• (who): Universität
• (when): 2020
• Creator: Schaefer, Alexander
• Contributor: Burgard, Wolfram ; Albert-Ludwigs-Universität Freiburg. Fakultät für Angewandte Wissenschaften

Further information

• DOI: 10.6094/UNIFR/155154
• URN: urn:nbn:de:bsz:25-freidok-1551546
• Rights: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 25.03.2025, 1:54 PM CET