autonomous navigation in complex nonplanar - ETH E

DISS. ETH NO. 23155
AUTONOMOUS N AVIGATION IN
C OMPLEX N ONPLANAR E NVIRONMENTS
BASED ON L ASER R ANGING
A thesis submitted to attain the degree of
DOCTOR OF SCIENCES of ETH ZURICH
(Dr. sc. ETH Zurich)
presented by
P HILIPP A NDREAS K R ÜSI
MSc ETH in Mechanical Engineering, ETH Zurich
born on 05.02.1984
citizen of Gais AR, Switzerland
accepted on the recommendation of
Prof. Dr. Roland Y. Siegwart, Examiner
Prof. Dr. Timothy D. Barfoot, Co-examiner
2016
Abstract
This thesis addresses the problem of autonomous navigation with ground robots in
complex environments, which may be characterized as nonplanar and nonstatic.
The goal of the presented research is to enable reliable navigation over large distances in generic indoor and outdoor environments, independent of external localization sources such as a global positioning system (GPS). Focusing on these challenges, algorithms for all building blocks of autonomous navigation—localization,
mapping, terrain assessment, motion planning, and motion control—are developed,
implemented, integrated, and finally evaluated in extensive field experiments.
Sensor-based perception of the environment is a basic requirement for localization
and mapping. We propose to use a high-frequency three-dimensional (3D) laser
scanner as the main exteroceptive sensor. The advantages of this technology lie in
the high density and accuracy of the provided measurements, and their independence
of lighting and weather conditions. We develop a highly scalable system for sixdimensional (6D) localization and 3D mapping based on iterative closest point (ICP)
matching. A topological/metric map representation, where metric information is kept
in spatially constrained local submaps representing vertices in a graph, allows to build
consistent large-scale maps without requiring global optimization. Long-term application in dynamic and changing environments is enabled by integrating methods
for identifying dynamic objects in the scene and for continuously updating existing
submaps.
Planning feasible and safe motions for a robotic vehicle requires distinguishing obstacles from traversable terrain. We develop two different algorithms for terrain assessment. The first method is targeted at real-time obstacle detection in the vicinity of
the robot. Assuming locally planar terrain, a grid-based obstacle map is built by analyzing the raw laser scans. The second approach is based on dense point cloud maps
(which can be obtained from the ICP mapping system) and suitable for planar and
nonplanar environments. The algorithm computes the geometry and the traversability of the terrain “on demand” at specific query locations, avoiding any artificial disi
A BSTRACT
cretization or explicit surface reconstruction. The desired terrain characteristics are
estimated based on statistics on the local distribution of map points.
Given a specific navigation task, motion planning can be defined as the problem of
reasoning about how to act based on the knowledge about the environment. This
thesis addresses both local obstacle avoidance and global planning over large distances. Our approach to local planning consists of computing a set of candidate
trajectories, which are shaped around nearby obstacles or along a given reference
path, and enforced to satisfy the robot’s kinematic constraints. The optimal local trajectory is chosen by evaluating the motion alternatives in terms of guidance towards
the goal and traversability of the underlying terrain. For global motion planning,
we develop an algorithm embedding the proposed point-cloud-based terrain assessment method, which allows trajectories to be directly planned on 3D point cloud
maps. The approach is designed to be suitable for generic nonplanar environments,
including rough outdoor terrain, multi-level facilities, and more complex geometries.
Piecewise continuous trajectories are computed in the full 6D space of robot poses,
while strictly considering the vehicle’s kinematic and dynamic constraints. We apply sampling-based planning algorithms to generate an initial trajectory connecting
the desired start and goal poses. Subsequently, the trajectory is locally optimized
according to a generic cost function, which may include path length, path curvature,
and roughness of the traversed terrain. While enforcing the hard constraints to remain satisfied (terrain contact, traversability, kinodynamic feasibility), the trajectory
is iteratively deformed until a local minimum of the cost function is reached.
We develop two complete systems for autonomous navigation, integrating these approaches. Combining the ICP-based localization and mapping framework with local
obstacle detection and local motion planning, we implement a framework for autonomous route following, commonly referred to as teach and repeat (T&R). After
a manually controlled teach run, where a graph of local submaps is built, the robot
is able to automatically repeat the learned route, using the recorded maps for localization. Unlike classical T&R systems, our framework is suitable for application in
dynamic environments, where the integrated obstacle avoidance scheme allows to detect and circumnavigate obstacles appearing on the reference path. In addition to the
T&R approach, we present a second navigation system, integrating the point-cloudbased terrain assessment and global planning algorithms with ICP-based localization
and mapping. Given a graph of point cloud maps—typically recorded in a manually controlled survey run—the framework enables navigation within the mapped
area without being restricted to known routes. Motion control is implemented by a
trajectory tracking controller with integrated real-time collision checking. Together
ii
A BSTRACT
with continuous map updates and frequent replanning of the global trajectory, these
techniques enable autonomous navigation in nonplanar, nonstatic environments.
Finally, we describe the characteristics of the mobile robot ARTOR, which was set
up for the purpose of testing and evaluating the developed algorithms under realistic conditions. ARTOR consists of a six-wheeled, electrically powered base vehicle equipped with sensors, computers, and communication gear. The proposed
autonomous navigation algorithms were integrated on the robot and tested in extensive field experiments, demonstrating reliable, GPS-independent navigation over
large distances and under greatly varying environmental conditions, in unstructured
off-road terrain, multi-level environments, and dynamic urban areas.
iii
Zusammenfassung
Diese Dissertation behandelt das Thema der autonomen Navigation mit bodengebundenen Robotern in komplexen Umgebungen, die weder als planar noch als statisch angenommen werden können. Ziel der vorliegenden Arbeit ist es, zuverlässige
Navigation über weite Distanzen im Innen- und Aussenbereich zu ermöglichen, unabhängig von externen Lokalisierungssystemen wie beispielsweise GPS. Mit Blick
auf diese Herausforderungen werden Algorithmen für alle Bausteine der autonomen Navigation – Lokalisierung, Kartierung, Geländebeurteilung, Bewegungsplanung und Bewegungssteuerung – entwickelt, implementiert, integriert, und schliesslich in ausgedehnten Feldversuchen evaluiert.
Sensorbasierte Wahrnehmung der Umgebung ist eine Grundvoraussetzung für Lokalisierung und Kartierung. Wir verwenden einen hochfrequenten dreidimensionalen
(3D) Laserscanner als Hauptsensor. Die Vorteile dieser Technologie liegen in der hohen Dichte und Genauigkeit der Messungen und in der Unabhängigkeit der letzteren
von Lichtverhältnissen und Wetterbedingungen. Wir entwickeln ein in hohem Masse
skalierbares System für sechsdimensionale (6D) Lokalisierung und 3D Kartierung
basierend auf Iterative Closest Point Matching (ICP). Eine topologisch/metrische
Kartendarstellung – metrische Daten werden in räumlich beschränkten, lokalen Submaps gespeichert, die Knoten in einem Graphen darstellen – erlaubt es, konsistente, grossflächige Karten anzulegen, ohne dass eine globale Optimierung nötig wäre.
Durch die Integration von Algorithmen zur Erkennung von dynamischen Objekten
und zur fortlaufenden Aktualisierung der existierenden Submaps wird eine langfristige Anwendung in einem dynamischen und sich ständig ändernden Umfeld ermöglicht.
Zur Planung von umsetzbaren und sicheren Bewegungen für einen mobilen Roboter
müssen Hindernisse von befahrbarem Terrain unterschieden werden können. Wir entwickeln zwei unterschiedliche Algorithmen zur Geländebeurteilung. Die erste Methode ist für lokale Hindernisvermeidung in Echtzeit konzipiert. Unter der Annahme eines lokal planaren Untergrunds wird eine rasterbasierte Hinderniskarte direkt
aus den Rohdaten des Laserscanners errechnet. Der zweite Ansatz basiert auf hochauflösenden Punktewolken-Karten (welche von dem ICP-Kartierungssystem bereitv
Z USAMMENFASSUNG
gestellt werden) und eignet sich für planare und nicht-planare Umgebungen. Der Algorithmus berechnet die Geometrie und die Befahrbarkeit des Geländes auf Verlan”
gen“ an spezifischen Abfragestellen, wodurch sowohl künstliche Diskretisierung als
auch explizite Oberflächenrekonstruktion vermieden werden können. Die gesuchten
Geländeeigenschaften werden aus einer statistischen Betrachtung der lokalen Verteilung der Kartenpunkte berechnet.
Bewegungsplanung kann definiert werden als die Aufgabe, zu bestimmen, wie der
Roboter – basierend auf dem angeeigneten Wissen über sein Umfeld – agieren soll,
um eine bestimmte Navigationsaufgabe zu erfüllen. Diese Dissertation behandelt sowohl lokale Hindernisvermeidung als auch globale Bewegungsplanung über weite
Strecken. Unser Ansatz für lokale Planung besteht in der Berechnung einer Auswahl von möglichen Trajektorien, die so geformt werden, dass sie um nahe gelegene Hindernisse herum oder entlang eines gegebenen Referenzpfades verlaufen, und
die kinematischen Beschränkungen des Roboters berücksichtigen. Die optimale lokale Trajektorie wird ausgewählt indem alle Alternativen in Bezug auf Zielführung
und Befahrbarkeit des unterliegenden Geländes beurteilt werden. Für globale Bewegungsplanung entwickeln wir einen Algorithmus, der die punktewolkenbasierte
Geländebeurteilungsmethode einbindet und es ermöglicht, Trajektorien direkt auf 3D
Punktewolken zu planen. Der Ansatz ist so konzipiert, dass er für generische nichtplanare Umgebungen geeignet ist, was sowohl unwegsames, unebenes Gelände als
auch mehrstöckige Gebäudeanlagen einschliesst. Stückweise stetige Trajektorien im
sechsdimensionalen Raum der Roboterposen werden unter strikter Berücksichtigung
der kinematischen und dynamischen Beschränkungen des Fahrzeugs berechnet. Wir
verwenden samplingbasierte Planungsalgorithmen für die Berechnung einer initialen
Trajektorie, die den spezifizierten Startpunkt mit der Zielposition verbindet. Anschliessend wird die Trajektorie lokal optimiert gemäss einer benutzerdefinierten Kostenfunktion, die beispielsweise die Pfadlänge, die Pfadkrümmung, und die Unebenheit des durchquerten Terrains beinhaltet. Während sichergestellt wird, dass die harten Randbedingungen (Geländekontakt, Befahrbarkeit, kinematische und dynamische
Realisierbarkeit) erfüllt bleiben, wird die Trajektorie iterativ verformt, bis ein lokales
Minimum der Kostenfunktion erreicht ist.
Basierend auf diesen Algorithmen entwickeln wir zwei verschiedene Systeme für autonome Navigation. Wir kombinieren das ICP-basierte Lokalisierungs- und Kartierungssystem mit lokaler Hinderniserkennung und Bewegungsplanung zu einem System für autonomes Abfahren von bekannten Strecken, häufig als Teach and Repe”
at“ (T&R) bezeichnet. Der Roboter wird einmalig manuell entlang der gewünschten
Strecke gesteuert, während ein Graph von lokalen Submaps aufgebaut und gespeichert wird. Danach kann die Strecke beliebig oft autonom abgefahren werden, wovi
Z USAMMENFASSUNG
bei sich der Roboter anhand der aufgenommenen Karten lokalisiert. Im Gegensatz
zu klassischen T&R-Systemen eignet sich unser System auch für die Anwendung
in dynamischen Umgebungen, da es in der Lage ist, Hindernisse, die den Referenzpfad blockieren, zu erkennen und zu umfahren. Jenseits von T&R präsentieren
wir ein zweites Navigationssystem, das die punktewolkenbasierten Algorithmen für
Geländebeurteilung und globale Bewegungsplanung mit ICP-basierter Lokalisierung
und Kartierung verbindet. Auf der Grundlage eines Graphen von Punktewolkenkarten – typischerweise während einer manuell gesteuerten Erkundungsfahrt erstellt –
ermöglicht das System autonome Navigation innerhalb der gesamten kartierten Umgebung, ohne die Fahrt auf zuvor gelernte Routen zu beschränken. Die Bewegungssteuerung erfolgt durch einen Pfadfolgeregler mit integrierter Hinderniserkennung.
Zusammen mit kontinuierlich aktualisierten Karten und häufiger Neuplanung der
globalen Trajektorie ermöglichen diese Techniken autonome Navigation in nichtplanaren, nicht-statischen Umgebungen.
Schliesslich beschreiben wir den Roboter ARTOR, der im Rahmen dieses Projekts
aufgebaut wurde, um die entwickelten Algorithmen unter realistischen Bedingungen
zu evaluieren. ARTOR besteht aus einem sechsrädrigen, elektrisch angetriebenen Basisfahrzeug, das mit einer Reihe von Sensoren sowie Computern und Kommunikationsgeräten ausgestattet ist. In ausführlichen Feldversuchen konnte gezeigt werden,
dass die dargelegten Algorithmen zuverlässige, GPS-unabhängige autonome Navigation über grosse Distanzen ermöglichen, in verschiedensten Witterungs- und Lichtverhältnissen, sowohl in unebenem, rauem Gelände abseits befestigter Wege, als auch
in mehrstöckigen Gebäuden und in dynamischer, urbaner Umgebung.
vii

Download Report