Department of Computer Science Technische Universitaet Muenchen
Home People Teaching Research Publications Info Sitemap
About | Teaching

Zu vergebende SEP- / Bachelorarbeit

Thema:

Berechnung eines generalisierten Voronoi-Diagramms zur 2d-Navigationsplanung für einen B21 Roboter

Betreuung: Andreas Fedrizzi
Themensteller: Prof. Michael Beetz, PhD

Beschreibung

Einleitung

Die Aufgabe eines mobilen Roboters, kollisionsfrei von A nach B zu fahren wird oft unterschätzt, denn das allgemeine Problem der Bewegungsplanung ist PSPACE-hart. Zwar ist der in diesem Projekt zu implementierenden Algorithmus einfacher, da er sich auf die 2d-Navigation beschränkt und auch die geometrische Form von Roboter und Umgebung relativ einfach sind. Trotzdem bleibt die Entwicklung eines Bewegungsplaners anspruchsvoll, wenn zusätzliche Constraints formuliert werden, wie zum Beispiel den kürzesten Pfad zu bestimmen (shortest path), oder einen Weg zu finden, der die Distanz zum nächstgelegenen Hindernis maximiert (maximum clearing distance oder auch MCD). Gerade die zweite Anforderung spielt in der mobilen Robotik eine wichtige Rolle, da es bei mobilen Robotern immer passieren kann, dass sie einige Zentimeter von ihrem Pfad abweichen, oder die Karte die zur Pfadplanung benutzt wurde ungenau ist. Daher ist es immer vorteilhaft einen gewissen Manövrierspielraum zu haben.

Kombinatorische vs. Sampling-basierte Bewegungsplaner

In dem hier ausgeschriebenen Projekt wird es um Offline-Bewegungsplanung gehen, bei der die Planung eines kollisionsfreien Pfades komplett vor dem Abfahren des Pfades erfolgt. Offline-Bewegungsplaner müssen daher eine möglichst vollständige und exakte Karte der Umgebung besitzen. Zur Lösung von Offline-Planungsproblemen werden in letzter Zeit vor allem sampling-basierte und kombinatorische Planer eingesetzt. Obwohl die sampling-basierten Metoden in hochdimensionalen Räumen deutliche Geschwindigkeitsvorteile haben, so besitzen kombinatorische Planer doch einige Vorteile, die sie für niedrigdimensionale Planungsprobleme wie die 2d-Navigation attraktiv machen. Beispielsweise finden kombinatorische Planer immer einen Pfad, wenn einer existiert und erkennen ansonsten, dass es keinen kollisionsfreien Pfad von der aktuellen Position zum Ziel gibt. Man sagt auch, dass kombinatorische Planer vollständig sind. Ausserdem kann man Parameter wie die Pfaddistanz oder die MCD und sogar komplexere Zielfunktionen optimieren.

B21 im existierenden Fabrik-Szenario Generalisiertes Voronoi-Diagramm der Fabrik
Aufgabenbeschreibung

Im Rahmen der Arbeit wird es darum gehen aus einer Welt, die in einer xml-Datei definiert ist, ein polygonales Modell zu extrahieren. Anhand dieses polygonalen Umgebungsmodells ist dann unter Einbeziehung der Roboterform der Konfigurationsraum des B21-Roboters zu berechnen. Anschliessend soll ein generalisiertes Voronoi-Diagramm erstellt werden. Ein Voronoi-Diagramm berechnet Linien, die zu vorher definierten Objekten (den Konfigurationsraum-Hindernissen) gleich weit entfernt sind und ist daher die ideale Grundlage für eine MCD-Roadmap. Die letzte Aufgabe besteht darin, mit Hilfe der MCD-Roadmap einige Pfadplanungs-Anfragen zu beantworten. Und zwar so, dass der Roboter vom Start in Richtung des nächsten Punktes auf der MCD-Roadmap fährt, dieser dann bis in die Nähe des Zieles folgt und dort die MCD-Roadmap in Richtung Zielpunkt verlässt (siehe Grafik). In allen Phasen dürfte die mächtige Geometrie-Bibliothek CGAL wertvolle Dienste leisten und vieles an Implementierungsaufwand ersparen.

Studenten, die sich mit diesem spannenden Thema im Rahmen eines SEP oder einer Bachelorarbeit auseinandersetzen wollen, können mir mailen oder direkt im Büro 02.09.039 vorbeikommen. Sollte Bedarf an weiteren Informationen zum Thema bestehen, so gebe ich gerne Auskunft, oder man kann sich die Kapitel 6.1 - 6.2.4 aus dem Buch Planning Algorithms von Steve LaValle durchlesen.


Aufgabenstellung

  1. Implementierung eines Algorithmus zur Berechnung der Maximum Clearing Distance-Roadmap (MCD-Roadmap).
  2. Benutzung der MCD-Roadmap um Pfadplanung für einen B21-Roboter zu betreiben.

Software

  • Benutzung des Robotersimulations-Framework Player/Gazebo
  • CGAL - Computational Geometry Algorithms Library

Erforderliche Fähigkeiten

  • Grundlegende Kenntnisse in C++ hilfreich
  • Interesse an geometrischen Algorithmen

Computer Science IX | Technische Universität München