Pathfinding

Thema:

Mathematische Modellierung und Optimierung zur Bestimmung kollisionsfreier Wege für Roboter

Die Diplomarbeit beschäftigt sich mit einer zentralen Fragestellung der Robotik: Der Bestimmung kollisionsfreier Wege für Roboter. Eine besondere Aufgabe besteht darin, den kürzesten Weg zwischen einem gegebenen Paar von Start- und Zielpunkt zu finden. Hierzu ist eine Beschreibung der Geometrie des Roboters und seiner Umgebung erforderlich. Ohne vorzunehmende Einschränkungen hinsichtlich der Freiheitsgrade des Roboters und der Form der Hindernisse ist dieses Problem praktisch nicht lösbar. Daher soll hier der Roboter als Punkt idealisiert werden, welcher sich nur auf einer Ebene (2 dimensionales Problem) bewegen kann. Die Hindernisse werden durch Polygone repräsentiert.

Die Realisierung der Aufgabe kann grob in vier Schritten erfolgen. Zunächst sollen die Polygone sowie deren Platzierung in der Ebene modelliert werden. Danach wird aus diesen Hindernissen unter Beachtung des Start und Zielpunktes ein Graph erstellt, dessen Kanten mögliche Teilwege des Roboters darstellen. Um die Probleme während dieser zwei Schritte, wie z.B. das Finden möglicher Schnitte zwischen Kanten und Polygonen, effizient zu lösen, wird auf Methoden aus der "Algorithmischen Geometrie" zurückgegriffen. Nachdem alle möglichen Kanten bestimmt sind, ist es nötig deren Gewichte zu bestimmen. Diese sind proportional zu deren Längen. Danach kann nun im letzten Schritt mit Algorithmen der Graphentheorie (wie dem von Dijkstra) der Weg durch den Graph vom Start- zum Zielpunkt mit dem geringsten Gewicht gefunden werden, was in diesem Fall gleichbedeutend mit dem kürzesten Weg ist.

Ergebnis: