Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-87741
URL: http://www.freidok.uni-freiburg.de/volltexte/8774/


Wurm, Kai M.

Techniques for multi-robot coordination and navigation

Roboterteams: Techniken zur Koordinierung und Navigation

Dokument1.pdf (16.382 KB) (md5sum: fbd67a277a94a3f94aa79a317d203b77)

Kurzfassung in Englisch

A team of mobile robots that work in parallel has the potential to finish a given task faster than a single robot. When a task can be decomposed into several independent sub-tasks, the problem can be approached using a divide-and-conquer strategy: Each robot in the team solves one sub-task and the partial solutions are then combined to complete the overall mission. One of the tasks that can be distributed well among a team of robots is mapping an environment. In this thesis, we focus on creating maps with teams of autonomous robots. There are two fundamental challenges that need to be addressed: The first challenge is the coordination of the team, in other words, assigning actions to robots so that the efficiency of the team is maximized. The second challenge is model estimation, the task of generating a map of the environment with a team of robots.

The contributions of this thesis are innovative techniques that address both of these challenges to enable teams of robots to explore environments more efficiently. In the first part of this thesis, we present approaches to coordinate teams of robots. We introduce an approach that makes use of the typical structure of buildings. It partitions the environment into regions such as rooms and corridors and then assigns robots to regions. In this way, our approach achieves a balanced distribution of the robots in the building.

Moreover, we present a method to coordinate teams of exploring robots that are able to perform actions that go beyond navigation. Such actions include opening doors or deploying other robots. Our coordination technique integrates a symbolic planning system and a robotic path planner. By explicitly considering actions other than navigating to goal positions, our approach is more flexible and more efficient than previous approaches.

In the second part of the thesis, we address challenges that arise during model estimation with multiple robots. We first present a technique to combine mapping results of individual robots into a joint map of the environment. To compute relative transformations between maps, we identify locations that occur in several of the local maps. As a result, our approach is able to estimate a consistent joint model from overlapping partial maps without relying on global estimates of robot poses.

We furthermore provide techniques for efficient 3D mapping. Our proposed mapping framework generates maps that are probabilistic, compact, and that can be created by teams of autonomous robots. Furthermore, we address the question of how semantic information can be incorporated into 3D maps. We present a hierarchical 3D mapping method that is based on knowledge about spatial dependencies in the environment.

In addition, we present an approach that robustly detects flat vegetation from laser measurements. Our method makes use of laser remission measurements and it can be used with data of most laser range finders. It reliably detects flat vegetation and enables vehicles that have not been designed to drive on vegetation to safely navigate in structured outdoor environments such as parks or campus sites.


Kurzfassung in Deutsch

Robotergruppen können eine gegebene Aufgabe häufig schneller bewältigen als einzelne Roboter. Besonders effizient können Roboterteams eingesetzt werden, falls sich die Aufgabe in unabhängige Teilaufgaben zerlegen lässt. Die Kartierung einer Umgebung ist eine solche Aufgabe. Die vorliegende Arbeit behandelt das Erstellen von Umgebungskarten mit Gruppen autonomer Roboter.

Die Kartierung einer Umgebung lässt sich grob in zwei Bereiche unterteilen: die Koordinierung des Teams und das Erstellen des Umgebungsmodells. Der Beitrag dieser Arbeit sind innovative Techniken, die Lösungen für diese beiden Aufgaben bereitstellen. Der erste Teil der Arbeit stellt Ansätze vor, um Roboterteams so zu koordinieren, dass sie eine unbekannte Umgebung möglichst effizient erkunden. Zunächst wird eine Methode vorgestellt, die die typische Struktur von Gebäuden nutzt. Das Verfahren teilt die Umgebung in Regionen wie beispielsweise Räume und Gänge auf. Die einzelnen Roboter des Teams werden dann so auf die Umgebung verteilt, dass jeder Roboter eine andere Regionen erkundet und kartiert. Auf diese Weise folgt die Verteilung der Roboter der Struktur der Umgebung und ist deutlich effizienter als Verfahren, die dieses Zusatzwissen nicht nutzen.

Einige Roboter sind in der Lage, Aktionen auszuführen, die über das Navigieren in der Umgebung hinausgehen. Beispiel für solche Aktionen sind das Öffnen von Türen oder das Absetzen anderer Roboter. Leider gibt es keine effiziente Methode, um solche Aktionen auf Kosten und Nutzenmaße abzubilden, wie sie üblicherweise in bisherigen Koordinierungsverfahren verwendet werden. In dieser Arbeit wird eine Methode vorgestellt, die in der Lage ist, Gruppen solcher Roboter zu koordinieren. Der vorgestellte Ansatz integriert ein symbolisches Planungssystem und einen Pfadplaner für mobile Roboter. Der symbolische Planer ermöglicht es dem Verfahren, symbolische Aktionen zu berücksichtigen. Da die Gesamtkosten der Kartierung in der Regel jedoch entscheidend von den Kosten abhängen, die durch das Bewegen der Roboter in der Umgebung entstehen, werden diese Kosten durch den effizienten Pfadplaner geschätzt. Auf diese Weise werden symbolischen Aktionen explizit berücksichtigt, während gleichzeitig die Ausführungszeit minimiert wird.

Der zweite Teil dieser Arbeit behandelt Fragestellungen, die sich bei der Erstellung von Umgebungsmodellen mit mehreren Robotern ergeben. Zunächst wird ein Verfahren vorgestellt, das Kartierungsergebnisse einzelner Roboter zu einer Gesamtkarte kombiniert. Das Verfahren identifiziert Bereiche, die in mehreren Teilkarten vorkommen. Diese Korrespondenzen werden dann genutzt, um relative Kartentransformationen zu bestimmen. Auf diese Weise werden konsistente Gesamtkarten erzeugt, ohne das die relativen Positionen der einzelnen Roboter bekannt sein muss.

Dreidimensionale Modelle der Umgebung stellen eine volumetrische Beschreibung der Umgebung zur Verfügung. Solche Modelle sind beispielsweise wichtig für fliegende Roboter und Roboter mit Manipulatoren. Diese Arbeit stellt ein effizientes Verfahren zur dreidimensionalen Kartierung vor. Das Verfahren erzeugt kompakte Karten und erlaubt das Kartieren mit mehreren Robotern. Es setzt probabilistische Methoden ein, um Messdaten aus mehreren Quellen zu einem Gesamtmodell zu vereinen. Eine der Neuerungen des Verfahrens ist ein verlustfreies Kompressionsverfahren, das den Speicherbedarf um mehr als 40% senken kann. Des Weiteren wird die Frage behandelt, wie semantisches Wissen bei der 3D-Kartierung berücksichtigt werden kann, beispielsweise das Wissen über Ebenen in der Umgebung und darauf platzierte Objekte. Die vorliegende Arbeit stellt eine Methode vor, die solches Wissen verwendet, um eine hierarchische 3D-Karte der Umgebung zu erstellen.

Die meisten autonomen Fahrzeuge, wie Transportfahrzeuge, autonome Rollstühle oder autonome Autos, wurden für das Fahren auf Straßen und befestigten Wegen entwickelt. Um die Navigation solcher Fahrzeuge in Außenumgebungen zu verbessern, wird in dieser Arbeit ein Verfahren vorgestellt, um flache Vegetation aus den Daten von Lasermesssystemen zu erkennen. Das Verfahren nutzt die Reflektionseigenschaften von Vegetation, um eine sichere Erkennung zu erreichen. Es erreicht hohe Erkennungsraten von über 99%. Auf diese Weise ermöglicht das Verfahren autonomen Fahrzeugen die sichere Navigation in strukturierten Außenumgebungen.

Zusammenfassend werden in dieser Arbeit die folgenden Fragestellungen behandelt:

Wie kann semantisches Wissen verwendet werden, um die Koordinierung von Robotergruppen zu verbessern?

Wie können Gruppen von verschiedenartigen Robotern effizient koordiniert werden?

Wie kann eine Gruppe von Robotern gemeinsam ein konsistentes Modell der Umgebung erstellen?

Wie können mobile Roboter auf effiziente Weise dreidimensionale Modelle der Umgebung erstellen?

Wie können Roboter effizient und sicher in strukturierten Außenumgebungen navigieren?


SWD-Schlagwörter: Robotik
Freie Schlagwörter (deutsch): Roboterteam , Koordinierung , Navigation , Exploration , Kartierung
Freie Schlagwörter (englisch): Robotics , Teams , Coordination , Navigation , Mapping
CCS Klassifikation Command an
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Burgard, Wolfram (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 12.09.2012
Erstellungsjahr: 2012
Publikationsdatum: 11.10.2012
Indexliste