Kollisionsfreie Bahnplanung mit Rapidly exploring Random Trees (RRTs) bei mehreren Robotern
©2005
Bachelorarbeit
94 Seiten
Zusammenfassung
Inhaltsangabe:Einleitung:
Überall werden in zunehmendem Maße Roboter zur Automatisierung verschiedenster Prozesse eingesetzt. Grundsätzlich führt ein Roboter Bewegungen aus, die ihm in einem Programm vorgegeben wurden, das entweder im Voraus entwickelt wurde, oder erst zur Laufzeit durch entsprechende Algorithmen aus Sensordaten generiert wird.
Ein essentielles Merkmal solcher Bewegungsabläufe ist, daß diese kollisionsfrei sein müssen. Der Roboter muß Hindernissen in seiner Umgebung ausweichen, um weder sich, noch die Umgebung zu beschädigen.
Der abgeschlossene Arbeitsbereich den man einem Roboter, z.B. in der automatisierten Produktion zuweist, wird möglichst klein gehalten, da diese Fläche Geld kostet. Somit ergibt sich, daß die Umgebung, in der sich der Roboter frei bewegen darf, so stark eingeschränkt ist, daß hier häufig die Gefahr der Kollision besteht.
Heute findet zudem selten nur ein einzelner Roboter Anwendung, sondern es werden vielmehr mehrere Roboter eingesetzt, die gemeinsam an einem Werkstück arbeiten bzw. Aufgaben erledigen müssen.
Somit verschärft sich das Problem der Kollisionsvermeidung zusätzlich, da nun jeder Roboter zusätzlich beweglichen Hindernissen ausweichen muß. Da dies für jeden der beteiligten Roboter gilt, ist die Bewegung dieser Hindernisse außerdem nicht vorhersagbar.
Heutzutage werden meist noch Experten eingesetzt, die effiziente Methoden kennen, um solche kollisionsfreien Bewegungsabläufe von Hand zu implementieren. Mit zunehmender Komplexität der Umgebung, der Roboter und des Einsatzfeldes, sowie vor allen Dingen bei autonomen Robotern, wie z.B. Transportfahrzeugen in einem automatisierten Teilelager, ist es aber nicht mehr möglich, solche Bewegungsabläufe in akzeptabler Zeit und Qualität von Hand zu erzeugen. Folglich besteht ein großes Interesse an Algorithmen, die diese Aufgabe automatisiert lösen.
Ziel ist es, kollisionsfreie Bewegungsabläufe für mehrere Roboter zu berechnen.
Am konkreten Beispiel soll dies für eine Arbeitsumgebung mit 6-Achs-Robotern, sowie einige ausgewählte Problemsituationen, wie sie in einem Hochregallager mit mehreren Transportrobotern auftreten, untersucht werden.
Es soll eine Anwendung entwickelt werden, die es ermöglicht kollisionsfreie Bewegungsabläufe für mehrere Roboter automatisch zu entwerfen. Diese Anwendung wird als Plugin für die Roboter-Simulationssoftware Easy-RobTM in C++ entwickelt. Easy-RobTM wird zur Visualisierung der Roboter, ihrer Umgebung sowie der […]
Überall werden in zunehmendem Maße Roboter zur Automatisierung verschiedenster Prozesse eingesetzt. Grundsätzlich führt ein Roboter Bewegungen aus, die ihm in einem Programm vorgegeben wurden, das entweder im Voraus entwickelt wurde, oder erst zur Laufzeit durch entsprechende Algorithmen aus Sensordaten generiert wird.
Ein essentielles Merkmal solcher Bewegungsabläufe ist, daß diese kollisionsfrei sein müssen. Der Roboter muß Hindernissen in seiner Umgebung ausweichen, um weder sich, noch die Umgebung zu beschädigen.
Der abgeschlossene Arbeitsbereich den man einem Roboter, z.B. in der automatisierten Produktion zuweist, wird möglichst klein gehalten, da diese Fläche Geld kostet. Somit ergibt sich, daß die Umgebung, in der sich der Roboter frei bewegen darf, so stark eingeschränkt ist, daß hier häufig die Gefahr der Kollision besteht.
Heute findet zudem selten nur ein einzelner Roboter Anwendung, sondern es werden vielmehr mehrere Roboter eingesetzt, die gemeinsam an einem Werkstück arbeiten bzw. Aufgaben erledigen müssen.
Somit verschärft sich das Problem der Kollisionsvermeidung zusätzlich, da nun jeder Roboter zusätzlich beweglichen Hindernissen ausweichen muß. Da dies für jeden der beteiligten Roboter gilt, ist die Bewegung dieser Hindernisse außerdem nicht vorhersagbar.
Heutzutage werden meist noch Experten eingesetzt, die effiziente Methoden kennen, um solche kollisionsfreien Bewegungsabläufe von Hand zu implementieren. Mit zunehmender Komplexität der Umgebung, der Roboter und des Einsatzfeldes, sowie vor allen Dingen bei autonomen Robotern, wie z.B. Transportfahrzeugen in einem automatisierten Teilelager, ist es aber nicht mehr möglich, solche Bewegungsabläufe in akzeptabler Zeit und Qualität von Hand zu erzeugen. Folglich besteht ein großes Interesse an Algorithmen, die diese Aufgabe automatisiert lösen.
Ziel ist es, kollisionsfreie Bewegungsabläufe für mehrere Roboter zu berechnen.
Am konkreten Beispiel soll dies für eine Arbeitsumgebung mit 6-Achs-Robotern, sowie einige ausgewählte Problemsituationen, wie sie in einem Hochregallager mit mehreren Transportrobotern auftreten, untersucht werden.
Es soll eine Anwendung entwickelt werden, die es ermöglicht kollisionsfreie Bewegungsabläufe für mehrere Roboter automatisch zu entwerfen. Diese Anwendung wird als Plugin für die Roboter-Simulationssoftware Easy-RobTM in C++ entwickelt. Easy-RobTM wird zur Visualisierung der Roboter, ihrer Umgebung sowie der […]
Leseprobe
Inhaltsverzeichnis
ID 9489
Morawski, Thomas: Das Verhältnis zwischen den deutschen Revisionisten und dem
westeuropäischen Sozialismus 1895 1918
Druck Diplomica GmbH, Hamburg, 2006
Zugl.: Ludwig-Maximilian-Universität München, Magisterarbeit, 1980
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2006
Printed in Germany
I
Inhaltsverzeichnis
1 Einleitung
1.1
Motivation
1
1.2 Zielsetzung
1
1.3 Aufgabenstellung
1
2
Kollisionsfreie Bahnplanung für einen einzelnen Roboter
2.1 Der
Konfigurationsraum
2
2.1.1
Vergleich der Bahnplanung bei 2 und mehr Freiheitsgraden
2
2.1.2
Der Konfigurationsraum als universelle Darstellung
3
2.2 Berechnen von Pfaden mit Graph-Suchalgorithmen
5
2.2.1
Aufbauen von Graphen im C
free
5
2.2.2
Grenzen des Verfahrens
6
2.3 Der
RRT-Algorithmus
8
2.3.1 Funktionsprinzip
8
2.3.2
Performance und Einschränkungen
11
2.3.3 Optimierungen
12
2.3.3.1 Variable
Schrittweite
12
2.3.3.2
Fixierung von Achsen
12
2.3.3.3 Bidirektionale
RRTs
13
2.3.3.4 Gierige
Heuristik
13
2.4 RRT Plug-In für Easy-Rob
TM
16
2.4.1
Aufbau der Anwendung
16
2.4.2
Integration in Easy-Rob
TM
mittels API
17
3
Kollisionsfreie Bahnplanung für mehrere Roboter
3.1 Anwendungen
18
3.2
Gekoppeltes Planen im gemeinsamen Konfigurationsraum
19
3.2.1
Erweitern der Anwendung
20
3.2.1.1 Kollisionslisten
20
3.2.1.2
Anpassen der Datenstrukturen
22
3.2.1.3
Anpassen der Kollisionsprüfung
23
3.2.2
Vor- und Nachteile dieses Verfahrens
24
3.2.3
Optimierung des Verfahrens
25
3.3
Entkoppeltes Planen
25
3.3.1
Erweiterungen für das Planen mit mehreren Robotern
25
3.3.2 Priorisiertes
Planen
30
3.3.3 Velocity
Tuning
34
3.3.4
Probleme im Zusammenhang mit der Zeitachse
36
II
3.3.5
Vor- und Nachteile der vorgestellten Verfahren
38
4 Abschließende
Betrachtung
4.1 Leistungsuntersuchung
40
4.1.1
Einfluß der Achsenfixierung und der gierigen Heuristik
40
4.1.2
Unterschied gekoppeltes- / entkoppeltes Planen
42
4.1.3
Verhalten in Tunneln / Fluren
44
4.1.4
Verhalten bei hoher Anzahl Roboter
46
4.2
Zusammenfassung und Ausblick
52
Anhang A Codeauszüge,
Datenformate
A.1 Function-pointer auf Member-functions
1
A.2 Ausführung von Member-functions als Thread
2
A.3 Aufbau der Roboter-Definitionsdatei
3
A.4 Aufbau der Kollisionslistendatei
5
Anhang B Verzeichnisse,
Glossar
B.1 Literaturverzeichnis
1
B.2 Abbildungsverzeichnis
1
B.3 Verwendete
Software
4
B.4 Glossar
4
B.5 Links zu weiterführenden Informationen
5
Anhang C Bedienungsanleitung zum RRT-Modul
Kapitel 1
Einleitung
1 Einleitung
1
1.1 Motivation
Überall werden in zunehmendem Maße Roboter zur Automatisierung verschiedenster
Prozesse eingesetzt. Grundsätzlich führt ein Roboter Bewegungen aus, die ihm in einem
Programm vorgegeben wurden, das entweder im Voraus entwickelt wurde, oder erst zur
Laufzeit durch entsprechende Algorithmen aus Sensordaten generiert wird.
Ein essentielles Merkmal solcher Bewegungsabläufe ist, daß diese kollisionsfrei sein
müssen. Der Roboter muß Hindernissen in seiner Umgebung ausweichen, um weder sich,
noch die Umgebung zu beschädigen.
Der abgeschlossene Arbeitsbereich den man einem Roboter, z.B. in der automatisierten
Produktion zuweist, wird möglichst klein gehalten, da diese Fläche Geld kostet. Somit ergibt
sich, daß die Umgebung, in der sich der Roboter frei bewegen darf, so stark eingeschränkt
ist, daß hier häufig die Gefahr der Kollision besteht.
Heute findet zudem selten nur ein einzelner Roboter Anwendung, sondern es werden
vielmehr mehrere Roboter eingesetzt, die gemeinsam an einem Werkstück arbeiten bzw.
Aufgaben erledigen müssen.
Somit verschärft sich das Problem der Kollisionsvermeidung zusätzlich, da nun jeder
Roboter zusätzlich beweglichen Hindernissen ausweichen muß. Da dies für jeden der
beteiligten Roboter gilt, ist die Bewegung dieser Hindernisse außerdem nicht vorhersagbar.
Heutzutage werden meist noch Experten eingesetzt, die effiziente Methoden kennen, um
solche kollisionsfreien Bewegungsabläufe von Hand zu implementieren. Mit zunehmender
Komplexität der Umgebung, der Roboter und des Einsatzfeldes, sowie vor allen Dingen bei
autonomen Robotern, wie z.B. Transportfahrzeugen in einem automatisierten Teilelager, ist
es aber nicht mehr möglich, solche Bewegungsabläufe in akzeptabler Zeit und Qualität von
Hand zu erzeugen. Folglich besteht ein großes Interesse an Algorithmen, die diese Aufgabe
automatisiert lösen.
1.2 Zielsetzung
Ziel ist es, kollisionsfreie Bewegungsabläufe für mehrere Roboter zu berechnen.
Am konkreten Beispiel soll dies für eine Arbeitsumgebung mit 6-Achs-Robotern, sowie einige
ausgewählte Problemsituationen, wie sie in einem Hochregallager mit mehreren
Transportrobotern auftreten, untersucht werden.
1.3 Aufgabenstellung
Es soll eine Anwendung entwickelt werden, die es ermöglicht kollisionsfreie
Bewegungsabläufe für mehrere Roboter automatisch zu entwerfen. Diese Anwendung wird
als Plugin für die Roboter-Simulationssoftware Easy-Rob
TM
in C++ entwickelt.
Easy-Rob
TM
wird zur Visualisierung der Roboter, ihrer Umgebung sowie der errechneten
Bewegungsabläufe genutzt.
Zur Berechnung der Bewegungsabläufe sollen Rapidly exploring Random Trees - die ich im
Folgenden mit RRT abkürzen werde - zum Einsatz kommen, sowie deren Vor- und Nachteile
aufgezeigt werden.
Neben der Einführung in das grundlegende Verfahren der Berechnung kollisionsfreier
Bewegungsabläufe und einer Beschreibung des RRT-Algorithmus, soll die Übertragbarkeit
auf Problemstellungen mit mehreren Robotern, die resultierenden Verfahren sowie mögliche
Optimierungen derselben dokumentiert werden.
Kapitel 2
Kollisionsfreie Bahnplanung für einen
einzelnen Roboter
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
2
In diesem Kapitel werden die grundlegenden Probleme und Verfahren zur Planung
kollisionsfreier Bewegungsabläufe für einzelne Roboter, mit statischer Umgebung erklärt. Im
Rahmen dieser Einführung wird der RRT-Algorithmus vorgestellt, mit dem sich diese Arbeit
im weiteren befaßt.
2.1 Konfigurationsraum
Im weiteren wird die Bedeutung des so genannten Konfigurationsraumes beschrieben, der
ein grundlegendes Hilfsmittel zur Lösung der in dieser Arbeit behandelten Problemstellungen
darstellt.
2.1.1 Vergleich der Bahnplanung bei 2 und mehr Freiheitsgraden
Stellt man sich einen punktförmigen Roboter vor, der sich in einer Ebene von einem Punkt,
zu einem anderen bewegen soll, so ist einleuchtend, daß dem Roboter an einem Hindernis
zwei Möglichkeiten zum fortsetzen seiner Bewegung bleiben.
X
Abb. 2.1 Hindernisse im 2D
Wie in Abb. 2.1. zu sehen, kann der Roboter (grüner Kreis)
das rote Hindernis nur auf zwei möglichen Wegen umfahren,
nämlich 'links herum' und 'rechts herum'.
Somit kann ein Verfahren zur Berechnung eines Weges zum
Ziel letztlich recht einfach implementiert werden, da die zu
untersuchenden möglichen Wege sehr begrenzt sind.
Ein Binärbaum, der für jede aufgetretene Abzweigung einen
Knoten enthält, wäre eine geeignete Datenstruktur, mit der
es recht einfach möglich ist, alle Alternativen zu
untersuchen.
Die selbe Aufgabenstellung im dreidimensionalen Raum ergibt allerdings ein
schwerwiegendes Problem.
Z
Y
X
3
X
Abb. 2.2 Hindernisse im 3D
Trifft der Roboter auf ein Hindernis, so bieten sich
ihm unendlich viele Möglichkeiten, das Hindernis
zu umfahren.
Für keinen der Wege kann im Voraus bestimmt
werden, ob dieser in einer Sackgasse endet oder
nicht, so daß prinzipiell alle Wege untersucht
werden müßten. Theoretisch würde der
Rechenaufwand damit ins Unendliche steigen. Eine
Lösung wäre, eine Art Raster einzuführen und so
nur noch eine begrenzte Anzahl Wege zu
untersuchen. Damit besteht aber die Gefahr, exakt
die Wege nicht zu untersuchen, die die einzige,
oder eine optimale Lösung ergeben würden.
Zudem ist es schwierig, gerade bei komplexen
Robotern, deren äußere Form in die Planung mit
ein zu beziehen.
Es wird also eine andere Darstellung für das
Problem benötigt, in der solche Schwierigkeiten
nicht auftreten.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
3
2.1.2 Der Konfigurationsraum als universelle Darstellung
Eine solche Darstellung bietet der so genannte Konfigurationsraum.
Der kreisförmige Roboter aus Abb. 2.1 kann sich in X- und Y-Richtung bewegen.
X
Y
2
-2
-2
2
0
0
(0,0)
Abb. 2.3 Konfigurationsraum
Nun führt man Wertebereiche für diese Achsen ein,
beispielsweise -2 bis +2 Meter in beiden
Richtungen. Somit kann sich der Roboter, von
seiner Nullstellung (0,0) ausgehend, in einer Ebene
2 Meter in X- und Y-Richtung bewegen.
Jeder Punkt in diesem Diagramm entspricht einer
bestimmten Stellung des Roboters.
Man nennt diese Darstellung Konfigurationsraum.
Nun kann man Stellungen des Roboters, in denen Kollision mit einem Hindernis auftritt, im
Konfigurationsraum markieren.
Am Beispiel eines dreieckigen Roboters und eines rechteckigen Hindernisses läßt sich gut
zeigen, wie sich Hindernisse im Konfigurationsraum darstellen.
X
Y
realer 2D
Abb. 2.4 Die Position des
Roboters wird im
Konfigurationsraum als
Koordinate der linken, unteren
Ecke angegeben.
Abb. 2.5 Hier sind die
Randbereiche des
Kollisionsbereichs im 2D
dargestellt.
X
Y
Konfigurationsraum
Abb. 2.6 Das rote Hindernis aus
dem 2D hat im
Konfigurationsraum eine andere
Form.
Die eigentliche Besonderheit ergibt sich nun daraus, daß der Roboter unabhängig von
seinen Umrissen im Konfigurationsraum durch einen Punkt dargestellt werden kann.
Ein Weg um das Hindernis herum kann also im Konfigurationsraum ohne Berücksichtigung
der Umrisse stattfinden und stellt sich hier nur noch als Pfad dar.
X
Y
Abb. 2.7 Stellungen im 2D
Die Stellungen des Roboters
im realen Raum stellen sich
im Konfigurationsraum als
Punkte dar. Zwischen ihnen
verfährt der Roboter linear
und erreicht ohne Kollision
seinen Zielzustand.
X
Y
Abb. 2.8 Weg im Konfigurations-
raum
Der große Vorteil des Konfigurationsraumes ist, daß die Darstellung einer Achsstellung des
Roboters im Konfigurationsraum unabhängig von den äußeren Umrissen und der Kinematik
immer gleich ist.
Der Konfigurationsraum hat so viele Dimensionen, wie der Roboter Freiheitsgrade.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
4
Abb. 2.11 zeigt die Stellung des Roboters aus Abb. 2.9 mit den in 2.10 bezeichneten
Achswinkeln im zugehörigen Konfigurationsraum.
Unabhängig davon, daß sich der Roboter nur in der Ebene bewegt, ist der
Konfigurationsraum aufgrund der 3 Achsen des Roboters, dreidimensional.
X
Y
Abb. 2.9 Roboter mit 3 Freiheitsgraden
X
Y
30°
-30°
-45°
Abb. 2.10 Bezeichnung der Achswinkel
Abb. 2.11 Achsstellung des Roboters als Punkt im
Konfigurationsraum
Der in Abb. 2.9 und 2.10 gezeigte
Achsstellung des Roboters entspricht
im Konfigurationsraum ein Punkt.
Bereiche, in denen Kollision stattfindet,
stellen sich hier als dreidimensionale
Objekte im Raum dar.
Ein kollisionsfreier Bewegungsablauf
des Roboters von einer
Startkonfiguration in eine
Zielkonfiguration läßt sich nun als Pfad
im 3D darstellen.
Jedem Punkt entlang des Pfades sind
Koordinaten zugeordnet, die wiederum
den Achswinkeln des Roboters
entsprechen.
Der Konfigurationsraum wird im weiteren mit
C
(configuration space) abgekürzt, wobei die
kollisionsfreien Bereiche mit
C
free
und die Bereiche, in denen Kollision stattfindet, mit
C
obs
(von obstacle) bezeichnet werden. Eine Konfiguration liegt dann in
C
free
, wenn der Roboter in
dieser keine Kollision mit anderen Objekten verursacht.
Die Berechnung eines kollisionsfreien Bewegungsablaufs wandelt sich also im
C
zu einem
Labyrinthproblem, welches mit verschiedenen Verfahrensweisen gelöst werden kann.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
5
2.2 Berechnen von Pfaden mit Graph-Suchalgorithmen
Nachdem mit dem Konfigurationsraum nun ein universeller Zustandsraum zur Verfügung
steht, benötigt man Methoden, um in diesem Raum effizient nach Pfaden zwischen einem
Startzustand
q
init
und einem Zielzustand
q
goal
zu suchen.
Eine Möglichkeit besteht darin, Algorithmen für die Suche von Pfaden in Graphen
einzusetzen, wie z.B. Dijkstra und A*.
Hierfür muß jedoch erst ein Graph vorhanden sein, in dem überhaupt gesucht werden kann.
2.2.1 Aufbauen von Graphen im
C
free
Eine einfache Möglichkeit einen solchen Graphen aufzubauen ist es, eine Anzahl zufälliger
Punkte in den
C
free
zu 'streuen' und anschließend den vollständigen Graphen über diese
Knoten aufzuspannen. Hierbei werden nur Kanten erzeugt, die vollständig im
C
free
liegen.
Hierfür ist lediglich ein Algorithmus nötig, der entlang der zu erzeugenden Kanten auf
Kollision prüft.
C
q
init
q
goal
Abb. 2.12 Konfigurationsraum mit Start- und
Zielkonfiguration
C
Abb. 2.13 Zehn zufällige Punkte im
C
free
C
Abb. 2.14 Der vollständige Graph über diese
Punkte
C
Abb. 2.15 Der kürzeste Weg, gefunden mit einem
Graphsuchalgorithmus wie Dijkstra, oder A*
Eine andere Methode, einen Graphen zu erhalten der mögliche Wege durch den
C
free
enthält, läßt sich bei polygonalen Hindernissen in einem Konfigurationsraum für 2
Freiheitsgrade anwenden. Bei der vertical cell decomposition werden vertikale Linien,
ausgehend von den Eckpunkten der Hindernispolygone, jeweils bis zum nächsten Hindernis,
bzw. zum Rand des Konfigurationsraumes gezogen.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
6
C
Abb. 2.16 Knotenpunkte
q
goal
q
init
C
Abb. 2.17 Der aufgebaute Graph
Jeweils in der Mitte einer solchen Linie, sowie in der Mitte der daraus entstehender Flächen
im
C
free
, werden Knoten gesetzt - wie in Abb. 2.16 zu sehen. Anschließend wird die Mitte
einer jeden Fläche, mit allen Mittelknoten der senkrechten Begrenzungen, des selben
Polygons durch Kanten verbunden. Hierdurch erhält man einen Graphen, der alle Bereiche
des
C
free
durch kollisionsfreie Strecken miteinander verbindet. Nachdem man
q
init
und
q
goal
durch Kanten zum nächstgelegenen Knoten an den Graphen angebunden hat, kann man in
diesem nun mit Dijkstra oder A* einen optimalen Pfad suchen. Bei mehr als 2
Freiheitsgraden, ist die Umsetzbarkeit dieses Verfahrens allerdings fraglich.
2.2.2 Grenzen des Verfahrens
Die Methode zufällige Punkte im
C
free
zu verteilen und den vollständigen Graphen über diese
aufzuspannen, birgt den Nachteil, daß für
n
Knoten maximal
( )
2
1
-
n
n
Kanten benötigt
werden. In der Industrie sind Roboter mit 6 Freiheitsgraden Normalität und durch die
komplexe Form der Werkstücke, wie beispielsweise in der Automobilindustrie, hat der
Konfigurationsraum eine entsprechend komplexe Struktur. Um in dieser Situation einen
Graphen zu erzeugen, der den
C
free
ausreichend detailliert ausfüllt, um gute
Bewegungsabläufe zu planen, können durchaus 20.000 Knoten und mehr nötig sein.
Dies ergäbe einen Graphen mit maximal 199.990.000 Kanten. Um bei der Kollisionsprüfung
entlang der Kanten ausreichend präzise zu bleiben, dürfen zudem nicht zu wenige
Kollisionstests pro Kante durchgeführt werden.
Um zu ermitteln, welche Kanten durch Kollision mit Hindernissen wegfallen, muß entlang
aller Kanten auf Kollision geprüft werden. Geht man davon aus, daß zwei Drittel der Kanten
aufgrund von Kollision wegfallen und dies bei 10 Kollisionstests pro Kante durchschnittlich
beim 5. Kollisionstest festgestellt wird, so sind für die wegfallenden Kanten 666.633.333
Kollisionstests durchzuführen.
Für alle Kanten die kollisionsfrei sind, müssen die vollen 10 Kollisionstests durchgeführt
werden, wodurch noch einmal 666.633.333 Kollisionstests hinzukommen.
In der Summe ergeben sich somit 1.333.266.666 Kollisionstests.
Die Zeit für eine Kollisionsprüfung läßt sich optimieren, indem zuerst Bounding-Boxes auf
Kollision getestet werden. Bounding-Boxes sind Quader, die die äußere Form eines Körpers
einschließen. Nur wenn die Bounding-Boxes kollidieren, werden die exakten 3D-Modelle der
Körper auf Kollision getestet. Aufgrund der nötigen Präzision müssen diese Modelle
allerdings ausreichend genau modelliert sein.
Selbst wenn ein sehr schneller Rechner 1.000.000 Kollisionstests pro Sekunde durchführen
könnte - was in aller Regel nicht der Fall ist - so würde es immer noch ca. 22 Minuten
dauern, den Graphen aufzubauen. Außerdem kommt noch die Zeit für die Berechnung des
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
7
optimalen Weges in diesem Graphen hinzu. Diese Rechenzeit ist für die noch relativ geringe
Anzahl Knoten eindeutig zu lang.
In allgemeiner Form ergibt sich mit den Parametern
n
: Anzahl der Knoten
2
)
1
(
-
= n
n
k
: Anzahl der Kanten im vollständigen Graph
p
:
Anteil der Kanten mit Kollision an der Gesamtmenge
s
:
Anzahl durchschnittlich durchzuführender Kollisionstests bis Kollision der Kante
erkannt
wird
t
:
Maximale Anzahl Kollisionstests bei Kante ohne Kollision
q
:
Anzahl pro Sekunde durchführbarer Kollisionstests auf dem genutzten System
die benötigte Rechenzeit, um den Graphen aufzustellen in Sekunden aus
( )
q
t
p
k
s
p
k
-
+
1
Abb. 2.18 Benötigte Zeit in Abhängigkeit von der Anzahl Knoten, wenn 70% der Kanten durch
Kollision wegfallen, dies durchschnittlich beim 5. Kollisionstest erkannt wird, maximal 10
Kollisionstest durchgeführt werden und das System 1.000.000 Kollisionstests pro Sekunde
bewältigt.
Wie in Abb. 2.18 zu sehen, nimmt die benötigte Zeit exponentiell zu und bereits bei ca.
34.000 Knoten wird eine Stunde benötigt.
Das zweitgenannte Verfahren ist nur bei polygonalen Hindernissen durchführbar, wobei hier
sicher eine Erweiterung auf beliebige Formen möglich wäre. Allerdings kommt hinzu, daß die
Kanten des entstehenden Graphen immer mittig im
C
free
liegen, wodurch die resultierenden
Pfade keineswegs optimale Länge haben. Im Endeffekt wird der Roboter den Hindernissen
sehr weiträumig ausweichen, was aber nicht gewünscht ist.
Minuten
Knoten
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
8
2.3 Der RRT-Algorithmus
Generell besteht das Problem darin, daß der bei der Bahnplanung zu durchsuchende
Zustandsraum hochdimensional und sehr groß ist. Außerdem bewegen sich Roboter nicht
mit gerasterten Achsen, sondern mit Hilfe von Linearmotoren stetig.
Der Rechenaufwand läuft also über alle Grenzen, wenn man versucht, alle möglichen
Zustände in die Berechnung eines kollisionsfreien Bewegungsablaufs mit einzubeziehen.
Es wäre also wünschenswert, nicht alle Zustände überprüfen zu müssen, aber dennoch den
C
free
ausreichend abzudecken.
Dies leisten so genannte Rapidly exploring Random Trees, die in diesem Abschnitt
beschrieben werden.
2.3.1 Funktionsprinzip
Der RRT-Algorithmus prüft zufällig erzeugte Kanten auf Kollision und baut nach und nach
einen Baum im
C
free
auf. Das besondere an diesem Verfahren ist allerdings, daß sich der
Baum schnell in die noch nicht besuchten Bereiche des
C
free
ausbreitet und diese dann
genauer erforscht bzw. ausfüllt. Daher rührt auch die Bezeichnung 'rapidly exploring'.
Der Grundalgorithmus ist einfach notiert:
1. Füge die Startkonfiguration des Roboters
q
init
dem Baum hinzu
2. Ermittle eine zufällige Konfiguration
q
rand
im C
3. Ermittle den zu
q
rand
nächsten Knoten
q
near
aus dem bestehenden Baum
4. Prüfe, ob die Strecke der Länge
s
ausgehend von
q
near
in Richtung
q
rand
ohne
Kollision zurückgelegt werden kann. Ist dies der Fall, so setze am Ende dieser
Strecke einen neuen Knoten
q
new
und füge diesen mit einer Kante zu
q
near
dem
Baum
hinzu.
Ist die Strecke nicht kollisionsfrei, dann setze bei 2. fort.
5. Wenn der neue Knoten
q
new
ausreichend nahe an
q
goal
für einen Verbindungsversuch
ist, so prüfe ob die Strecke zwischen diesen beiden kollisionsfrei ist.
Wenn
nein,
setze
bei
2. fort.
Wenn
ja,
so
füge
q
goal
dem Baum hinzu. Der berechnete Path kann nun von
q
goal
ausgehend rückwärts ermittelt werden, da jeder Knoten nur einen Vorgänger hat.
Die folgenden Abbildungen verdeutlichen den Algorithmus.
C-Space
q
init
q
1
Abb. 2.19 Der Baum besteht aus 2 Knoten
C-Space
q
init
q
1
q
rand
Abb. 2.20 Zufällige Konfiguration ermittelt
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
9
C-Space
q
init
q
1
q
rand
q
new
S
c
h
ri
tt
w
e
it
e
s
Abb. 2.21 Überprüfen der Strecke zwischen
q
near
und
q
new
auf Kollision
C-Space
q
init
q
1
q
2
Abb. 2.22 Hinzufügen von
q
new
zum Baum, da
Verbindung Kollisionsfrei
C-Space
q
init
q
1
q
2
q
3
q
rand
q
new
Sch
rittw
eite
s
Abb. 2.23 Zuerst wird
q
new
auf Kollision geprüft.
Liegt
q
new
nicht in
C
free
, so wird der Zustand gleich
verworfen.
C-Space
q
init
q
1
q
2
q
3
q
rand
q
new
Sch
rittw
eite
s
q
new
liegt noch in C
free
Hier tritt Kollision auf
Abb. 2.24 Bei Kollision zwischen
q
near
und
q
new
wird ebenfalls abgebrochen.
C-Space
q
init
q
goal
Abb. 2.25 Ist der Abstand zwischen
q
new
und
q
goal
zu groß, wird kein Verbindungsversuch
unternommen.
C-Space
q
init
q
goal
Abb. 2.26 Bei Kollision zwischen
q
new
und
q
goal
wird der Algorithmus fortgesetzt.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
10
C-Space
q
init
q
goal
Abb. 2.27 Ist der Abstand zwischen
q
new
und
q
goal
klein genug, wird ein Verbindungsversuch
unternommen.
C-Space
q
init
q
goal
Abb. 2.28 Ist diese Verbindung kollisionsfrei, wird
q
goal
dem Baum hinzugefügt und der Path
ermittelt.
Nun liegt ein kollisionsfreier Path im
C
free
, bestehend aus den erzeugten Knoten vor, der
jedoch sehr unregelmäßig verläuft. Dies äußert sich direkt in einer ruckelnden Bewegung
des Roboters, bei der viele unnötige Bewegungen auftreten.
Im nächsten Schritt wird dieser Path geglättet, um einen gleichmäßigen Verlauf zu erhalten.
C-Space
q
init
q
goal
Abb. 2.29 Knoten die durch Direktverbindungen
übersprungen werden können
C-Space
q
init
q
goal
Abb. 2.30 Der geglättete Path nach dem
entfernen der überflüssigen Knoten.
In jedem Durchlauf versucht der Optimierungsalgorithmus einen Knoten zu überspringen.
War dies erfolgreich, versucht er dies mit dem nächsten Knoten, bis er am Ende des Paths
angelangt ist.
Diese Optimierung kann mehrfach auf den Path angewendet werden, bis keine weiteren
Knoten mehr ausgelassen werden konnten. Zusätzlich können weitere Optimierungen mit
mehr als 1 auszulassendem Knoten durchgeführt werden.
So kann ein äußerst flüssiger Bewegungsablauf erreicht werden, der durch seine geringe
Anzahl Knoten zudem wenige Verzögerungs- und Beschleunigungsvorgänge für den
Roboter bedeutet, was sich direkt in der Geschwindigkeit niederschlägt.
Abb. 2.31 zeigt das Ergebnis des RRT-Algorithmus am Beispiel eines 2-Achs-Roboters. Die
Kanten sind entsprechend des zeitlichen Verlaufs der Entstehung des Baumes farblich
kodiert. Blaue Kanten sind zu Beginn der Berechnung generiert worden, grüne Kanten zum
Ende hin. Dazwischen ist die Farbe interpoliert worden.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
11
Abb. 2.31 RRT mit gefundener Lösung im
Konfigurationsraum eines Roboters mit 2 Freiheitsgraden.
Der Startzustand
q
init
befindet
sich in diesem Beispiel in der
Mitte des Konfigurationsraumes,
q
goal
ist mittig, rechts zu finden.
Es ist deutlich zu erkennen, daß
der RRT-Algorithmus zu Beginn
lange Äste in alle Bereiche des
C
free
ausstreckt und dann, von
diesen ausgehend, den Raum
weiter ausfüllt.
Nachdem der Baum dem
Zielzustand nahe genug
gekommen war, ist dieser
erfolgreich hinzugefügt worden
und der Path konnte ermittelt
werden.
Dieser ist hier rot eingezeichnet.
Letztlich breitet sich der Baum
vollständig, gleichmäßig und vor
allem 'dicht' im
C
aus, weshalb er
auch 'dense tree' genannt wird.
2.3.2 Performance und Einschränkungen
Die Geschwindigkeit des RRT-Algorithmus hängt hauptsächlich von der gewählten
Schrittweite ab. Wählt man diese eher groß, so breitet sich der Baum schnell im gesamten
C
aus, allerdings mit der Gefahr, Engstellen nicht mehr passieren zu können. Wählt man die
Schrittweite klein, so breitet sich der Baum nur langsam aus, allerdings wird der
Ergebnispath näher an den Hindernissen vorbei führen und Engstellen können passiert
werden.
Die Berechnung eines kollisionsfreien Bewegungsablaufs für einen 6-Achs-Roboter kann bei
geeigneter Wahl der Parameter schon nach 2000 Iterationen abgeschlossen sein. Der
Algorithmus bewegt sich damit in Bereichen von wenigen Sekunden Rechenzeit auf einem
herkömmlichen PC.
Abb. 2.32
Große Kollisionsbereiche können den
Algorithmus viel Zeit kosten.
In Abb. 2.32 ist eine Situation gezeigt, in
der eine zufällige Position
q
rand
innerhalb
des rot markierten Bereichs einen neuen
Knoten
q
new
innerhalb des
Kollisionsbereichs zur Folge hätte.
Große Kollisionsbereiche können somit
dafür sorgen, daß nur noch wenige
Zufallspositionen für ein Wachsen des
Baumes sorgen, wodurch der Algorithmus
viel Zeit verliert.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
12
Abb. 2.33
In der in Abb. 2.33 dargestellten Situation,
wird der Algorithmus große
Schwierigkeiten haben, die Engstelle zu
finden, oder er wird sie unter Umständen
gar nicht finden.
Außerdem wird er viel Zeit beim Ausfüllen
der Bögen verschwenden, bevor er an
deren Rand einen Ausgang findet.
Alle zufälligen Positionen aus den roten
Bereichen ziehen den Baum in die Bögen
hinein und kosten somit nur Rechenzeit.
2.3.3 Optimierungen
Die Geschwindigkeit des Verfahrens läßt sich durch einige einfache Erweiterungen
entscheidend erhöhen. Außerdem können die in 2.3.2 beschriebenen Probleme entschärft,
bzw. beseitigt werden.
2.3.3.1 Variable Schrittweite
Eine sehr einfache Verbesserung bringt die Einführung einer variablen Schrittweite. Zu
Beginn sollte der Algorithmus mit einer großen Schrittweite starten, um sich so den
C
schnell
zu erschließen. Die Schrittweite sollte dann zunehmend bis zu einem eingestellten Minimum
verkleinert werden, wodurch es dem Algorithmus möglich ist, auch enge Durchgänge im
C
free
zu passieren. Ein Nebeneffekt wäre, daß der Baum die Umrisse der Kollisionsbereiche
zunehmend besser approximiert. Das Ergebnis wären Bewegungsabläufe, die sehr nah an
den Hindernissen vorbei führen und den verfügbaren Raum somit sehr effizient ausnutzen.
Wie in der Einleitung bereits erwähnt stellt dies einen direkten Kostenfaktor einer
Produktionsstraße dar.
2.3.3.2 Fixierung von Achsen
Eine weitere einfache Verbesserung bringt einiges an Geschwindigkeitszuwachs. Auch bei
einem 6-Achs-Roboter werden für viele Bewegungsabläufe nicht alle Achsen benötigt. Soll
ein Roboterarm ein Werkstück greifen und es auf gleicher Höhe, an anderer Stelle wieder
absetzen, so reichen unter Umständen 3 Achsen für diese Bewegung aus. Die anderen
Achsen können über die gesamte Bewegung hinweg die selben Werte wie in der
Startkonfiguration
q
init
beibehalten.
Durch Fixierung einzelner Achsen auf bestimmte Werte, innerhalb der Routine zur
Erzeugung der Zufallspositionen, kann die Dimension des
C
auf die Anzahl der noch frei
beweglichen Achsen reduziert werden. Beim eingangs beschriebenen 6-Achs-Roboter muß
der RRT somit nur noch einen dreidimensionalen Konfigurationsraum durchsuchen, was
einen erheblichen Geschwindigkeitszuwachs nach sich zieht.
2 Kollisionsfreie Bahnplanung für einen einzelnen Roboter
13
2.3.3.3 Bidirektionale RRTs
Dem Problem der Insektenfalle kann man mit einer einfachen Erweiterung begegnen,
nämlich den bidirektionalen RRTs.
q
init
q
goal
C
Abb. 2.34 Insektenfalle
Anstatt den RRT nur von
q
init
ausgehend
aufzubauen, erzeugt man parallel einen
zweiten Baum von
q
goal
ausgehend. Der
bestehende Algorithmus muß nur noch
um einen Arbeitsschritt erweitert werden,
in dem bei ausreichend kurzer Distanz ein
Verbindungsversuch zwischen den beiden
Bäumen vorgenommen wird. Sobald
dieser erfolgreich war, ist der Path
gefunden.
q
init
q
goal
C
Abb. 2.35 Mehrere Insektenfallen
Durch Hinzufügen stabiler
Zwischenzustände - hier blau markiert -
und aufspannen mehrerer Bäume, können
selbst Problemstellungen mit mehreren
Insektenfallen gelöst werden.
Für den Anwender bedeutet das, daß er
für den Roboter kollisionsfreie
Zwischenkonfigurationen zwischen dem
Startzustand und dem Endzustand
angeben muß. So hat der Anwender
gleichzeitig mehr Kontrolle über das
Ergebnis des Algorithmus.
2.3.3.4 Gierige Heuristik
Eine kleine Erweiterung des RRT-Algorithmus aus 2.3.1 ergibt ein völlig neues Verhalten,
daß in bestimmten Situationen zu enormen Geschwindigkeitsvorteilen führen kann.
Der Grundalgorithmus wird folgendermaßen erweitert:
1.
Füge die Startkonfiguration des Roboters
q
init
dem Baum hinzu
2.
Ermittle eine zufällige Konfiguration
q
rand
im C
3.
Ermittle den zu
q
rand
nächsten Knoten
q
near
aus dem bestehenden Baum
4.
Prüfe, ob die Strecke der Länge
s
ausgehend von
q
near
in Richtung
q
rand
ohne
Kollisions zurückgelegt werden kann. Ist dies der Fall, so setze am Ende dieser
Strecke einen neuen Knoten
q
new
und füge diesen mit einer Kante zu
q
near
dem
Baum
hinzu.
Ist die Strecke nicht kollisionsfrei, dann setze bei 2. fort.
5. Wandere vom soeben erstellten, neuen Knoten
q
new
direkt auf
q
goal
zu und setze im
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2005
- ISBN (eBook)
- 9783832494919
- ISBN (Paperback)
- 9783838694917
- Dateigröße
- 2.9 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Evangelische Hochschule Darmstadt, ehem. Evangelische Fachhochschule Darmstadt – Informatik
- Note
- 1,0
- Schlagworte
- pathplanning robotik propabilistisch montage
