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).


Movebox

Detour

Swap boxes

Swap + Rotate

Snake

Gripper

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

~awbs/Daten/Pfadplanung/

eine C-Bibliothek zur Verfügung. Die Erläuterung der bereitgestellten Typen, Variablen und Routinen entnehmen Sie bitte dem Headerfile include/pathlib.h. Ihr Algorithmus kann dabei auf das gegebene Umgebungswissen u.a. über ein abstraktes Prädikat IsConnectable() zugreifen, das für eine Strecke (im C-Space!) angibt, ob sie vollständig im erlaubten Bereich liegt, d.h. keines der Hindernisse durchquert.

Hinweis: Anstatt direkt auf die Funktionen der Bibliothek zuzugreifen, sollten die neueren Klassen Config (Vektor von double-Zahlen) und CSpace2D verwendet werden.

Informationen zur Planung in der neuen 3D-Umgebung sind unter www9.in.tum.de/praktika/awbs_info_general/plan3d.html.

Stefan Burkhardt Last modified: Mon Dec 10 11:03:18 CET 2001