Pathfinding _ TNG - SoftHeldgm2

"einfach mal richtig lesen"
Elise

Pathfinding

Meine Diplomarbeit dreht sich um das Thema Pathfinding. Dabei wird die Informatik mit einem grossen Stück Mathematik verbunden. Da dies vielen ein Mysterium zu sein scheint, habe ich mich entschieden, die Diplomarbeit an dieser Stelle zu veröffentlichen. Wer also etwas über mathematische Ansätze zum Pathfinding erfahren möchte, Spass an Informatik und Mathematik oder einfach zuviel Zeit hat, ist hier genau richtig. Ausserdem könnt ihr nun endlich mit Apfel und Birne vergleichen.

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:

Am Ende meiner Diplomarbeit stand (zusätzlich zu einem 100 seitigen Schriftstück) eine Anwendung, die demonstriert welchen Weg der idealisierte Roboter durch ein Labyrinth von Polygonen nehmen würde. Das sieht dann so aus.


Download der Diplomarbeit als pdf (461 kb)$$$COMMENTS$$$
Webcritics, es wird kritisch _ DruckKapitelWeiter