View
1
Download
0
Category
Preview:
Citation preview
Offline Bewegungsplanung: Translation undRotation
Elmar Langetepe
University of Bonn
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 1
Jetzt: Translation und Rotation!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
• Bewegung, Translation und Rotation gleichzeitig
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
• Bewegung, Translation und Rotation gleichzeitig
• Startpunkt S, Endpunkt T
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
• Bewegung, Translation und Rotation gleichzeitig
• Startpunkt S, Endpunkt T
• Kollisionsfreie Bewegung?
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
• Bewegung, Translation und Rotation gleichzeitig
• Startpunkt S, Endpunkt T
• Kollisionsfreie Bewegung?
• Wie aufwendig ist die Berechnung? Untere Schranke!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Jetzt: Translation und Rotation!
• Konvexer Roboter, m Ecken
• Polygonale Szene, n Ecken
• Bewegung, Translation und Rotation gleichzeitig
• Startpunkt S, Endpunkt T
• Kollisionsfreie Bewegung?
• Wie aufwendig ist die Berechnung? Untere Schranke!
• Kann ich einen Weg angeben? Obere Schranke!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 2
Kapitel 2.3 Beispiel!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Kapitel 2.3 Beispiel!
Bewegung von A nach B mit Rotation und Translation
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 3
Untere Schranke! Th. 2.25
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
s
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
• Mindestens Ω(n2) Bewegungsschritte
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
• Mindestens Ω(n2) Bewegungsschritte
• Translation, Rotation im Wechsel
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
• Mindestens Ω(n2) Bewegungsschritte
• Translation, Rotation im Wechsel
• Konstruktiv!
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.25
• Liniensegment bewegen
• Von s nach t in Szene mit n Kanten
• Mindestens Ω(n2) Bewegungsschritte
• Translation, Rotation im Wechsel
• Konstruktiv!
s
t
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 4
Untere Schranke! Th. 2.24
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
LowerBound.html
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
LowerBound.html
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
2
34
56
7
75 3 6 4
L
C
B
A
2 3 4 6 71 5
12
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 5
Untere Schranke! Th. 2.24
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden,
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
• Dazu: Sukzessive Reihe von A Blocken uberwinden
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
• Dazu: Sukzessive Reihe von A Blocken uberwinden
• Dazu: Sukzessive Reihe von C Blocken uberwinden
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
• Dazu: Sukzessive Reihe von A Blocken uberwinden
• Dazu: Sukzessive Reihe von C Blocken uberwinden
• Nachster B Block: zuruck!!
6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
• Dazu: Sukzessive Reihe von A Blocken uberwinden
• Dazu: Sukzessive Reihe von C Blocken uberwinden
• Nachster B Block: zuruck!!
• O(n) fur jeden B-Block!6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Untere Schranke! Th. 2.24
• Einen B Block uberwinden, in die Kerbe
• Dazu: Sukzessive Reihe von A Blocken uberwinden
• Dazu: Sukzessive Reihe von C Blocken uberwinden
• Nachster B Block: zuruck!!
• O(n) fur jeden B-Block! n Blocke: Ω(n2)6
L
C
B
A
2 3 4 6 71 5
12
34
56
7
13 45
2
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 6
Berechne 3D Konfigurationsraum? Ein Hindernis!
θ
KonfigurationsraumArbeitsraum
CPi
R
P
x
y
y
x
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 7
Ideen!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen:
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen: θi = i · 360
k , 0 ≤ i ≤ k − 1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen: θi = i · 360
k , 0 ≤ i ≤ k − 1
– Vereinigung
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen: θi = i · 360
k , 0 ≤ i ≤ k − 1
– Vereinigung– Problem: (x, y, θi), (x, y, θi+1) in Cfrei , dazwischen nicht!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen: θi = i · 360
k , 0 ≤ i ≤ k − 1
– Vereinigung– Problem: (x, y, θi), (x, y, θi+1) in Cfrei , dazwischen nicht!– Abhilfe: Vergroßern!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Ideen!
• Konfigurationsraum berechnen:
– Problem: Kurven als Kanten
• Diskrete Orientierungen: θi = i · 360
k , 0 ≤ i ≤ k − 1
– Vereinigung– Problem: (x, y, θi), (x, y, θi+1) in Cfrei , dazwischen nicht!– Abhilfe: Vergroßern!– Keine Korrekte Bahnplanung!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 8
Kritische Platzierung: 2.3.1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Kritische Platzierung: 2.3.1
• Ansatz: Wann andert sich der Konfigurationsraum substantiell
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Kritische Platzierung: 2.3.1
• Ansatz: Wann andert sich der Konfigurationsraum substantiell
• Neue Kante, neuer Knoten
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Kritische Platzierung: 2.3.1
• Ansatz: Wann andert sich der Konfigurationsraum substantiell
• Neue Kante, neuer Knoten
• Definition: Kritische Platzierungen
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Kritische Platzierung: 2.3.1
• Ansatz: Wann andert sich der Konfigurationsraum substantiell
• Neue Kante, neuer Knoten
• Definition: Kritische Platzierungen
• Zum Beispiel bei Kontakten mit Hindernissen!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Kritische Platzierung: 2.3.1
• Ansatz: Wann andert sich der Konfigurationsraum substantiell
• Neue Kante, neuer Knoten
• Definition: Kritische Platzierungen
• Zum Beispiel bei Kontakten mit Hindernissen!
W1S1
W3S3W2
S2 R
W1S1
W3S3W2
S2 R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 9
Anderung des Konfigurationsraumes!Auch bei Wechsel parallel und nicht-parallel! Neue Knoten
θ
KonfigurationsraumArbeitsraum
CPi
R
P
x
y
y
x
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 10
Kritische Platzierungen Def.: 2.27
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S),
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S), W beruhrt S
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S), W beruhrt S
i) W ist eine Hinderniskante und S eine Roboterecke (Typ I) oder
ii) W ist eine Hindernisecke und S eine Roboterkante (Typ II) oder
iii) W ist eine Hindernisecke und S eine Roboterecke (Typ III)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S), W beruhrt S
i) W ist eine Hinderniskante und S eine Roboterecke (Typ I) oder
ii) W ist eine Hindernisecke und S eine Roboterkante (Typ II) oder
iii) W ist eine Hindernisecke und S eine Roboterecke (Typ III)
Freie Plazierung (x, y, θ):
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S), W beruhrt S
i) W ist eine Hinderniskante und S eine Roboterecke (Typ I) oder
ii) W ist eine Hindernisecke und S eine Roboterkante (Typ II) oder
iii) W ist eine Hindernisecke und S eine Roboterecke (Typ III)
Freie Plazierung (x, y, θ): Kritische Plazierung
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
R konvexer Roboter m Ecken, Pi polygonale Hindernisse
Kontaktpaar O = (W,S), W beruhrt S
i) W ist eine Hinderniskante und S eine Roboterecke (Typ I) oder
ii) W ist eine Hindernisecke und S eine Roboterkante (Typ II) oder
iii) W ist eine Hindernisecke und S eine Roboterecke (Typ III)
Freie Plazierung (x, y, θ): Kritische Plazierung
• drei paarweise verschiedene Kontaktpaare vom Typ I oder II oder
• Kontaktpaar vom Typ III und Kontaktpaar vom Typ I oder II
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 11
Kritische Platzierungen Def.: 2.27
W3
R
S1W1
W3
(i) (iii)(ii)
W2
S2
P2
S3
S3
S3
W3
R RSW
WS
P3
P1 P1P1
P3
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 12
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
1.
(iii)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
1.
(iii)
Pi
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
1.
(iii)
Pi
(iii)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
1.
(iii)
Pi
(iii)
Pj
Pi
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Zelle Cfrei: Kritische Platzierungen Lem.: 2.28
Jede Zelle von Cfrei besitzt Krit. Platzierung!
Pi
R
(i)
Pj
(ii)
(i)/(ii)
Pi
Pk
(iii)
Pk
1.
(iii)
Pi
(iii)
Pj
Pi
(iii)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 13
Kurven in Cfrei! Bem. 2.29
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Kurven in Cfrei! Bem. 2.29
• Zwei Kontakte behalten
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Kurven in Cfrei! Bem. 2.29
• Zwei Kontakte behalten
• Kurve eines Referenzpunktes (x, y)
O2KRO1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Kurven in Cfrei! Bem. 2.29
• Zwei Kontakte behalten
• Kurve eines Referenzpunktes (x, y)
O2KRO1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Kurven in Cfrei! Bem. 2.29
• Zwei Kontakte behalten
• Kurve eines Referenzpunktes (x, y)
• Parametrisierung: Grad 4
O2KRO1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Kurven in Cfrei! Bem. 2.29
• Zwei Kontakte behalten
• Kurve eines Referenzpunktes (x, y)
• Parametrisierung: Grad 4 (Ubungsaufgabe)
O2KRO1
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 14
Anzahl Kontakte: Kor. 2.30
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Kontakte: Kor. 2.30
• Drei Kontaktpaare Oi = (Wi, Si)
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Kontakte: Kor. 2.30
• Drei Kontaktpaare Oi = (Wi, Si)
• 2 Falle: Zwei festhalten oder die Hindernisse bewegen
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Kontakte: Kor. 2.30
• Drei Kontaktpaare Oi = (Wi, Si)
• 2 Falle: Zwei festhalten oder die Hindernisse bewegen
• Kurve Grad 4 (Bem. 2.29) und Grad 1 schneiden
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Kontakte: Kor. 2.30
• Drei Kontaktpaare Oi = (Wi, Si)
• 2 Falle: Zwei festhalten oder die Hindernisse bewegen
• Kurve Grad 4 (Bem. 2.29) und Grad 1 schneiden
• Hochstens vier mal kommt das vor!
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Kontakte: Kor. 2.30
• Drei Kontaktpaare Oi = (Wi, Si)
• 2 Falle: Zwei festhalten oder die Hindernisse bewegen
• Kurve Grad 4 (Bem. 2.29) und Grad 1 schneiden
• Hochstens vier mal kommt das vor!
• Typ III und Typ I/II?
S1S2
S3W3
W2 W1R
O1 O2
S3 W3
K
R
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 15
Anzahl Krit. Platzierungen: Th. 2.31
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
• 2mn Kontaktpaare Typ I/II
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
• 2mn Kontaktpaare Typ I/II
• Je drei auswahlen:(2mn3
)∈ O(m3n3)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
• 2mn Kontaktpaare Typ I/II
• Je drei auswahlen:(2mn3
)∈ O(m3n3)
• 4 mal vorkommen: O(m3n3)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
• 2mn Kontaktpaare Typ I/II
• Je drei auswahlen:(2mn3
)∈ O(m3n3)
• 4 mal vorkommen: O(m3n3)
• Typ III und Typ I/II: O((mn2
))
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
• |R| = m,∑|Pi| = n
• Ecke/Kante, Kante/Ecke, Ecke/Ecke
• 2mn Kontaktpaare Typ I/II
• Je drei auswahlen:(2mn3
)∈ O(m3n3)
• 4 mal vorkommen: O(m3n3)
• Typ III und Typ I/II: O((mn2
))
• Konvexitat nicht genutzt
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 16
Anzahl Krit. Platzierungen: Th. 2.31
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 17
Anzahl Krit. Platzierungen: Th. 2.31
Ω(m3n3) konstruktiv:
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 17
Anzahl Krit. Platzierungen: Th. 2.31
Ω(m3n3) konstruktiv:(m3
)mal
(n3
)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 17
Anzahl Krit. Platzierungen: Th. 2.31
Ω(m3n3) konstruktiv:(m3
)mal
(n3
)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 17
Anzahl Krit. Platzierungen: Th. 2.31
Ω(m3n3) konstruktiv:(m3
)mal
(n3
)
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 17
R konvex! Krit. Platzierungen: Th. 2.32
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn))
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn)) subquadratisch
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn)) subquadratisch
• Davenport-Schinzel-Sequenzen
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn)) subquadratisch
• Davenport-Schinzel-Sequenzen
• Wichtige Elemente fur Bahnplanung
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn)) subquadratisch
• Davenport-Schinzel-Sequenzen
• Wichtige Elemente fur Bahnplanung
• Beweis Komplexitat
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
R konvex! Krit. Platzierungen: Th. 2.32
• |R| = m konvex,∑|Pi| = n
• Anzahl Kritische Platzierungen: O(mnλ6(mn))
• λ6(mn) ∈ O(mn log∗(mn)) subquadratisch
• Davenport-Schinzel-Sequenzen
• Wichtige Elemente fur Bahnplanung
• Beweis Komplexitat
• Berechnen!
Offline Bewegungsplanung 9.12.13 Kollisionsfreie Wege c©Elmar Langetepe WS ’1314 18
Recommended