Unter Bewegungsplanung versteht man das Finden von Bahnen für gegebene geometrische Objekte unter gewissen Randbedingungen. Bei den Randbedingungen handelt es sich zunächst darum, daß während der Bewegung keine Kollisionen/Überschneidungen zwischen Objekten und der (statischen) Umgebung auftreten dürfen. Es kann aber auch zu beachten sein, daß Bewegungen zusätzlichen lokalen Kriterien genügen müssen (z.B. kann ein Auto weder auf der Stelle drehen noch seine Geschwindigkeit abrupt ändern). Konkrete Beispiele sind die Pfadplanung für einen mobilen Roboter (Pathfinder), die Generierung von Steuerbefehlen für einen Roboterarm, aber auch die zentrale Planung für mehrere unabhängige Einheiten (autonome Einheiten bzw. Roboterarme).
Im Praktikum setzen wir voraus, daß vollständige Information über die Umgebung (den sog. Arbeitsraum) vorliegt. D.h. es bestehen insbesondere keine Unsicherheiten bzgl. der Form und Anzahl der Hindernisse. Außerdem werden zunächst nur stark abstrahierte Probleme betrachtet (s.u. Abb., bei den statischen Beispielen ist die Startstellung rot und die Zielstellung grün eingezeichnet).
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Für Planungsaufgaben dieser Art wurde das Konzept des Konfigurationsraumes (C-Space) (hat nichts mit der Programmiersprache C zu tun) eingeführt. Ein Punkt dieses Raumes repräsentiert dabei eine bestimmte Position und Orientierung (eine sog. Konfiguration) für alle beweglichen Objekte innerhalb des Arbeitsraumes. Die Dimension des C-Space entspricht deshalb der Anzahl der Freiheitsgrade des gegebenen Problems. Durch die Randbedingungen wird der Konfigurationsraum, vereinfacht gesagt, in 'erlaubte' und 'verbotene' Bereiche eingeteilt. Die Lösung einer Aufgabenstellung besteht nun (im Rahmen des Praktikums) darin, einen Pfad (Polygonzug) im Konfigurationsraum zu finden, der eine gegebene Anfangs- mit einer gegebenen Zielkonfiguration verbindet und der zudem vollständig im erlaubten Bereich liegt.
Es handelt sich bei diesem Suchproblem um kein Problem mit
endlichem Zustandsraum, da die Anzahl der Zwischenpunkte
beliebig groß gewählt werden kann und die Zwischenpunkte auf
reellen Koordinaten zu liegen kommen (können). Auch bei relativ
grober Diskretisierung ist die Anzahl aller Zustände meist
unbeherrschbar groß. In der Praxis ist es aufgrund der grossen
Zeitkomplexität des Problems bei höherer Dimension unmöglich,
den Konfigurationsraum exakt zu berechnen. Im Praktikum können
verschiedene praktikable Pfadplanungsansätze implementiert und
getestet werden, z.B. randomisierte Verfahren
(Probabilistischer Roadmap-Planer
bzw. RRT-Verfahren) oder der in der Vorlesung behandelte
Via-Punkt Algorithmus.
Seit dem WS 1999/2000 können die Planungsalgorithmen auch in
einer realistischeren 3D-Umgebung getestet werden. Es können
eigene Roboter und ganze Szenarien mit Hindernissen entworfen
werden. Die Schnittstelle zum Planungsalgorithmus ist wie bei
den 2D-Beispielen über eine Klasse CSpace gegeben, die folgende
Operationen bereitstellt:
Beispiel 1: Testroboter mit 6 Freiheitsgraden
(Animated GIF (591kB))
![]() |
![]() |
| Startstellung | Zielstellung |
Beispiel 2: Testroboter mit 11 Freiheitsgraden (Animated GIF (1.5MB))
![]() |
![]() |
| Startstellung | Zielstellung |
Für die Bearbeitung der 2D Planungsaufgaben steht Ihnen
unter
Informationen zur Planung in der neuen 3D-Umgebung sind unter www9.in.tum.de/praktika/awbs_info_general/plan3d.html.