inoffizielles Skript
Angewandte Differentialgeometrie
Gehalten von Dr. S. Grensing im Sommersemester 2013
getippt von Aleksandar Sandic∗
22. Juli 2016
∗
[email protected]
Inhaltsverzeichnis
Vorwort
5
1 Räuber und Gendarm
1
Metrische Räume mit oberen Krümmungsschranken . . . . . . .
2
Konvexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Räuber und Gendarm . . . . . . . . . . . . . . . . . . . . . . . .
4
Geometrische Charakterisierung von Flucht- und Verfolgerkurven
5
Positive Krümmungsschranken . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
7
7
10
12
22
26
2 Bewegungsplanung & Konfigurationsräume
1
Geometrie des Kubenkomplexes Kn G . . . . . . . . . . . . . . . . .
2
Nichtpositive Krümmung von Kubenkomplexen . . . . . . . . . . . .
3
Verallgemeinerung: Lokal rekonfigurierbare Räume . . . . . . . . . .
29
36
38
40
3 „Gestänge“ (Linkages)
1
Abstandsfunktion von Roboterarmen . . . . . . . . . . . . . . . . . .
2
Polygonräume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Walkers Vermutung . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
43
43
50
4 Kinematik
1
Vorwärtstransformation . . . . . . .
2
Linarisierung (d.h. Tangentialräume)
3
Adjungierte Darstellung . . . . . . .
4
Exponentialabbildung . . . . . . . .
5
Clifford Algebren . . . . . . . . . . .
53
55
56
57
59
61
Stichwortverzeichnis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
66
3
Vorwort
Über dieses Skript
Dies ist eine Mitschrieb der Vorlesung „Angewandte Differentialgeometrie“ von Dr.
S. Grensing, gehalten im Sommersemester 2013 am Karlsruher Institut für Technologie. Dr. Grensing ist nicht für den Inhalt verantwortlich und es besteht weder eine
Garantie für Vollständigkeit, noch Korrektheit der enthaltenen Aussagen.
Wer
Das Skript wurde in von Aleksandar Sandic getippt. Bei Anmerkungen bzw. beim
Auffinden von Fehlern korrigierte bitte die entsprechende Stelle in Wiki oder schickt
eine E-Mail an
[email protected]
Wo
Link zur Vorlesung: http://www.math.kit.edu/iag5/lehre/angdifgeo2013s/de
Link zum Skript: http://mitschriebwiki.nomeata.de/AngDiffGeo2013.pdf
Link zum Mitschiebwiki: http://mitschriebwiki.nomeata.de/
To Do
Fertig, die Vorlesung ist beendet und der Inhalt ist vollständig. Eventuell könnte
man noch die Übung in’s Skript aufnehmen, aber ich bin nicht sicher ob das den
Aufwand wert wäre. Ansonsten. . .
• Glossareinträge anlegen
• Ein richtiges Literaturverzeichnis
5
Kapitel 1
Räuber und Gendarm
1 Metrische Räume mit oberen Krümmungsschranken
Es sei (X, d) ein metrischer Raum. Ein Weg c : I → X heißt (minimierende)
Geodätische, wenn d(c(t), c(t0 )) = (t − t0 ) für alle t, t0 ∈ I gilt. Der Raum X
heißt geodätischer Raum, wenn für alle x, y ∈ X eine Geodätische von x nach
y existiert, beziehungsweise R-geodätisch, wenn dies für d(x, y) ≤ R gilt. Ist c :
[a, b] → X ein Weg so heißt er rektifizierbar, falls seine Länge
dn
c(ti+1 )
L(c) = sup
nX
d(c(ti ), c(ti+1 )) | t1 < . . . tn , ti ∈ I
c
o
c(ti )
endlich ist. Es gilt d(c(a), c(b)) ≤ L(c). Die Kurvenlänge ist invariant unter monotonen Reparametrisierungen. Die Längenfunktion t 7→ L(c|[a,t] ) ist monoton wachsend; insbesondere besitzt jede Kurve eine Bogenlängenparametrisierung. Der Raum
(X, d) heißt Längenraum (oder d innere Metrik), falls die Metrik
d(x, y) = inf{L(c) | c : I → X rektif’barer Weg, c(0) = x, c(1) = y}
mit d übereinstimmt.
Beispiele
1) Rn mit der euklidischen Metrik ist ein geodätischer Raum und ein Längenraum.
2) Jede Riemannsche Mannigfaltigkeit ist ein Längenraum (Beweis zur Übung).
3) Ist (X, d) ein metrischer Raum, so folgt dass (X, d) eine Längenmetrik ist, das
heißt d = d (das iterieren der Konstruktion liefert keine neue Metrik).
4) Jeder geodätische Raum ist ein Längenraum. Es gilt stets d ≤ d. Sind x, y ∈ X
und ist γ : [a, b] → X eine Geodätische von x nach y, so gilt:
L(γ) = sup
nX
d(γ(ti ), γ(ti+1 ))
o
= sup
nX
(ti+1 − ti )
o
= t − a = d(x, y).
Also
d(x, y) = inf L(c) ≤ L(γ) = d(x, y)
c
5) R2 \{0} ist ein Längenraum (bezüglich der euklidischen Metrik), aber kein geodätischer Raum.
7
di
Kapitel 1: Räuber und Gendarm
−1
1
Es gibt keine kürzeste Verbindung
Satz (von Hopf-Rinow; Chom-Vossen 1935)
Es sei X ein lokalkompakter Längenraum. Dann sind die folgenden Aussagen äquivalent:
(i) X ist vollständig
(ii) X ist geodätisch vollständig, das heißt jede Geodätische c : [0, 1) → X
kann in 1 fortgesetzt werden.
(iii) Beschränkte abgeschlossene Mengen sind kompakt.
Jede der obigen Aussagen impliziert, dass X ein geodätischer Raum ist.
y
x
Kanten en der Länge 1 +
1
n
; Es gibt keine Kurve der Länge 1
Es bezeichne Mκ2 die (eindeutigen) 2-dimensionalen, einfachzusammenhängenden
Riemannschen Mannigfaltigkeiten mit der Schnittkrümmung sec ≡ κ, und Dκ ihren
Durchmesser:
Mκ2 =

2


S √1κ


,κ > 0
R2
,κ = 0




H2√1
,κ < 0
κ

 √π
,κ > 0
κ
Dκ =
∞ , κ ≤ 0
wobei
2
3
H √1 = x ∈ R |
κ
x21
+
x22
−
x23
1
=−
.
κ
Es sei X ein metrischer Raum. Ein geodätisches Dreieck ∆(x, y, z) besteht aus
Geodätischen cxy = xy, cyz = yz und czx = zx zwischen den Punkten x, y und z. Ein
Vergleichsdreieck in Mκ2 ist ein geodätisches Dreieck ∆(x, y, z) mit gleichen Kantenlängen wie das ursprüngliche Dreieck. Ein solches Vergleichsdrieck existiert eindeutig, falls der Umfang d(x, y) + d(y, z) + d(z, x) ≤ 2Dκ ist. Ein Punkt p ∈ ∆(x, y, z)
heißt Vergleichspunkt zu p ∈ ∆(x, y, z), p ∈ xy, falls d(x, p) = d(x, p). Das Dreieck ∆(x, y, z) erfüllt die CAT (κ)-Ungleichung, wenn für alle p, q ∈ ∆(x, y, z) mit
vergleichpunkten p, q gilt:
d(p, q) ≤ d(p, q)
8
1 Metrische Räume mit oberen Krümmungsschranken
z
z
⊆X
⊆ R2
q
q
y
p
y
x
p
x
Der Raum X besitzt die obere Krümmungsschranke κ, wenn für alle x ∈ X eine
geodätische Umgebung existiert, in der alle Dreiecke die CAT(κ)-Ungleichung erfüllen. Für κ = 0 heißt X nicht-positiv gekrümmt. Erfüllt X global die CAT(κ)Ungleichung, so heißt X CAT (κ)-Raum.
Beispiele
2
1) R2 ist CAT(0), M 2 = R Z2 ist nichtpositiv gekrümmt.
2) S1 ist CAT(1).
3) R2 \Q1 , Q1 = {x1 > 0, x2 > 0}, mit der induzierten Längenmetrik ist CAT(0).
z
Q1
y
x
4) Sei (M, g) Riemannsche Manngifaltigkeit mit der Schnittkrümmung secg ≤ κ
und vollständig. Nach dem Satz von Topogonov hat M die obere Krümmungsschranke κ.
Eigenschaften von CAT(κ)-Räumen
• Geodätische der Länge < Dκ sind eindeutig.
• Bälle vom Radius < 12 Dκ sind konvex und zusammenziehbar.
• CAT(0)-Räume sind zusammenziehbar.
Charakterisierung von CAT(κ)-Räumen
Für jedes geodätische Dreieck ∆(x, y, z) vom Umfang < 2Dκ und Punkte p ∈ xy
und q ∈ xz gilt für Vergleichsdreiecke ∆(x, y, z) und ∆(x, p, q):
(in Mκ2 )
x (p, q) ≤ x (y, z)
z
z
∆(x, y, z)
q
q
∆(x, p, q, )
p
y
p
x
y
x
Ist X ein CAT(κ)-Raum und sind c1 und c2 Geodätische mit gleichem Startpunkt
c1 (0) = c2 (0) = x so ist der Winkel x (c1 (s), c2 (t)) monoton wachsend in s und t.
Damit ist der Winkel
(c1 , c2 ) = lim x (c1 (s), c2 (t)) = lim x (c1 (t), c2 (t))
s,t→0
t→0
9
Kapitel 1: Räuber und Gendarm
wohldefiniert.
Satz (von Hadamart-Cartan; Alexander-Bishop 1990)
Es sei X ein vollständiger metrischer Raum mit der oberen Krümmungsschranke
κ ≤ 0. Dann ist seine universelle Überlagerung X̃ (bezüglich der induzierten Metrik)
(global) CAT(κ).
2 Konvexität
Eine Teilmenge C eines CAT(0)-Raumes (geodätischer Raum) heißt konvex, falls
für alle x, y ∈ C das geodätische Segment von x nach y existiert und in ganz C
verläuft. Eine Abbildung f : X → R auf einem CAT(0)-Raum heißt konvex, falls
für jede Geodätische c : [0, 1] → X die Funktion f ◦ c : [0, 1] → R konvex im
gewöhnlichen Sinne ist.
Ist X ein CAT(0)-Raum, so ist die Metrik konvex, das heißt für Geodätische c1 , c2 :
[0, 1] → X ist die Funktion
t 7→ d(c1 (t), c2 (t))
konvex, wie man in der folgenden Beweisskizze erkennt:
Beweisskizze
Wir betrachten ohne Einschränkung den Fall dass beide Geodätischen den gleichen
Startpunkt x = c1 (0) = c2 (0) haben:
c2 (1) = z
z
⊆X
c1 (t)
⊆ R2
c2 (t)
c2 (t)
y
c1 (1) = y
c1 (t)
x
x = c1 (0) = c2 (0)
Bei Betrachtung des Vergleichsdreiecks zu ∆(c1 (0), c1 (1), c2 (1)) erhalten wir aus der
CAT(0)-Ungleichung:
d(c1 (t), c2 (t)) ≤ dR2 (c1 (t), c2 (t)) = t · dR2 (y, z) = t · dR2 (c1 (1), c2 (1))
Betrachte nun c von c2 (0) nach c1 (1).
c2 (1)
c2 (t)
c2 (0)
c(t)
c
c1 (0)
c1 (t)
c1 (1)
10
2 Konvexität
Nach der Dreiecksungleichung gilt:
d(c1 (t), c2 (t)) ≤ d(c1 (t), c(t)) + d(c2 (t), c(t))
≤ (1 − t) · d(c1 (0), c2 (0)) + t · d(c1 (1), c2 (1))
(2)
Geodätische Segmente in X sind immer eindeutig, wie man mit der folgenden Skizze
erkennen kann:
c1
x
y
c2
Die Abstandsfunktion d(c1 (·), c2 (·)) ist konvex mit Nullstellen in 0 und 1, also konstant Null und damit c1 = c2 . Nun fixiere x0 ∈ X, und sei cx das geodätische
Segment von x0 nach x.
x
cx
x0
cx (t)
cy
y
Damit wird H(x, t) = cx (t) eine Retraktion von X auf {x0 }.
Ist C eine vollständige konvexe Teilmenge von X, so existiert eine „orthogonale
Projektion“ π : X → C mit folgenden Eigenschaften:
(i) Für jedes x ∈ X ist π(x) ∈ X der eindeutig bestimmte Punkt mit
d(x, π(x)) = d(x, C) = inf{d(x, c) | c ∈ C}
(ii) Für Punkte y ∈ C und x ∈
/ C, mit π(x) 6= y, gilt π(x) (x, y) ≥ π2 .
(iii) Es gilt π(xπ(x)) = {π(x)}.
(iv) π ist eine Retraktion von X auf C, welche Abstände nicht vergrößert.
C
π(x0 ) = π(x)
y
π(x)
π(z)
≥
π
2
≥
π
2
x
x0
z
Konstruktion
Es seien X1 und X2 zwei CAT(0)-Räume. Dann ist X1 × X2 ebenfalls ein CAT(0)Raum bezüglich der Produktmetrik. Die Geodätischen von X1 × X2 sind genau die
Produkt c1 × c2 von Geodätischen ci in Xi .
X1
x1
X2
y
x2
11
Kapitel 1: Räuber und Gendarm
Weitere CAT(0)-Räume erhält man durch „Verkleben“ entlang konvexer Teilmengen. Es sei A ein vollständiger metrischer Raum und seien ιi : A ,→ Ai ⊆ Xi Isometrien auf konvexen Teilmengen in X1 beziehungsweise X2 . Dann ist X1 ∪A X2 =
˙ 2
X1 ∪X
{ι1 (a) = ι2 (a) ∈ A} mit der Metrik
d(x, y) =

d
x, y ∈ Xi
Xi (x, y)
inf
a∈A {d(x, ιi (a))
+ d(ιj (a), y)}
x ∈ Xi , y ∈ Xj , i 6= j
ein CAT(0)-Raum.
X2
X1
A2
A1
z
z0
x0
y
x
Betrachte die Vergleichsdreiecke ∆(x, x0 , z 0 ) und ∆(z 0 , y, x0 )
3 Räuber und Gendarm
Regeln
Das Spielfeld D sei eine zusammenhängende Teilmenge des Rn . Eine Startkonfiguration sei gegeben durch eine endliche Anzahl von Verfolgern P1 , . . . , PN ∈ D und
einen Flüchtigen E ∈ D. Wir betrachten zunächst (zeitlich) diskrete Modelle. Es
bezeichnen Pkt beziehungsweise E t die Positionen der Verfolger beziehungsweise des
Flüchtigen zum Zeitpunkt t ∈ N.
Spielverlauf
Zum Zeitpunkt t wählt zunächst E t eine neue Position E t+1 mit dem Abstand
d(E t , E t+1 ) ≤ 1, also höchstens eine Einheit entfernt von der vorherigen Position,
danach (simultan) die Verfolger Pkt , entsprechend mit d(Pkt , Pkt+1 ) ≤ 1. Die Verfolger
gewinnen, wenn für jedes C > 1 ein t ∈ N existiert, so dass d(E t , Pkt ) < C für ein
k ∈ N gilt.
Satz
Auf jedem Kompaktum D ⊆ Rn ist „Greedy“ stets erfolgreich (mit mindestens
einem Verfolger).
Greedy
Der Verfolger bewegt sich um die Distanz 1 auf der Strecke P t E t :
12
3 Räuber und Gendarm
Et
P t+1
Pt
Beweisskizze (allgemein später)
Skizze zum Greedy Algorithmus:
Et
1
dt
αt
P t+1
E t+1
dt+1 > 1 + ε
1
Pt
dt+1 ≤ 1 + (dt − 1) = dt ⇒ limt→∞ dt =: d∞
Angenommen der Flüchtige würde entkommen. Dann wäre d∞ > 1 und damit der
t→∞
Winkel αt −−−→ 0, das bedeutet D würde beliebig lange Geradensegmente enthalten,
wäre also nicht kompakt. Das ist ein Widerspruch zur Voraussetzung.
(2)
Mehrere Verfolger in Rn
Wann ist ein Entkommen bei mehreren Verfolgern überhaupt möglich? Wir schauen
uns die folgende Zeichnung an:
Hyperebenen
P5
P1
P6
P3
P4
E
P2
Sei C t = conv(P1t , . . . , PNt ) die konvexe Hülle zum Zeitpunkt t. Ein Entkommen ist
◦
möglich, wenn es eine trennende Hyperebene gibt, also wenn E ∈
/ conv(P1t , . . . , PNt ),
◦
wobei conv das Innere der konvexen Hülle bezeichnet. Es stellt sich die Frage, ob
die Umkehrung auch zutrifft, also ob nie ein Entkommen möglich ist, wenn E ∈
◦
conv(P1 , . . . , PN ). Bei Greedy ist das nicht der Fall, der Beweis ist dem Leser zur
Übung überlassen. Wir weden uns nun also einen neuen Algorithmus anschauen.
Planes
Die idee hinter dem Planes Algorithmus ist den Bereich um die Verfolger durch
Hyperebenen einzugrenzen und systematisch zu verkleinern.
13
Kapitel 1: Räuber und Gendarm
P2
P3
E0
P4
P1
P5
• Pkt+1 = Pkt+1 (Pkt , E t , E t+1 )
• Gerade Lt+1
parallel zu E t Pkt durch E t+1
k
Et
r
Pkt
1
Pkt+1
Lt+1
k
t+1 ) minimal
• Pkt+1 ∈ Lt+1
mit d(Pkt , Pkt+1 ) = 1 und d(t+1
k
k ,E
Satz (Kopperty-Ravishankar ’05)
◦
Es sei D = Rn . Falls E ∈ conv(P1 , . . . , PN ) gilt, so ist Planes erfolgreich.
Beweis
Zunächst stellen wir mit der folgenden Zeichnung einige Vorüberlegungen an:
Pt
dt
Et
ϑ
ϑ
r
1
a = r sin ϑ
r
−r cos ϑ dt − dt+1
dt+1
E t+1
b
Falls ϑ ≤ π2√gilt r cos ϑ ≥ 0 und damit folgt dt − dt+1 ≥ 0. Im Fall ϑ >
r cos ϑ = −r 1 − sin2 ϑ und damit folgt dann
dt − dt+1 =
vk
E
Pk
Es bezeichne vk :=
p
p
r≤1
π
2
gilt
p
1 − r sin2 ϑ − r 1 − sin2 ϑ ≥ (1 − r) 1 − sin2 ϑ ≥ 0.
0 −E 0
PK
0 −E 0 k
kPK
◦
den Einheitsvektor in Richtung E 0 Pk0 . Da E ∈ conv(P1 , . . . , PN )
◦
gilt, existiert ein ε > 0 mit der Sphäre Bε ⊆ conv(v1 , . . . , vN ). Ohne Einschränkung kann man annehmen, dass die v1 , . . . , vn+1 in allgemeiner Lage sind und
◦
dass Bε (0) ⊆ conv(v1 , . . . , vn+1 ), sowie E = 0 ist. Für ein v ∈ Sn−1 existieren
P
λ1 , . . . , λn+1 ∈ (0, 1) mit εv = n+1
k=1 λk vk und es folgt
ε = εkvk2 = hv, εvi =
X
λk hv, vk i.
ε
man findet also ein k, so dass hv, vk i ≥ n+1
= dmin > 0 gilt. Es seien v =
t
und k = k(v) wie oben. Dann gilt cos ϑk = hv, vk i ≥ dmin .
14
E t+1 −E t
kE t+1 −E t k
3 Räuber und Gendarm
E t+1
r
v
Et
vk
Pt
Es gilt:
dt − dt+1 =
q
1 − r2 sin2 ϑtk + r cos ϑtk
≥
p
1 − r2 + r cos ϑtk
p
1 − r2 − cos ϑtk (1 − r) + cos ϑtk
√
√
√
≥ 1 − r( 1 + r − 1 − r) + cos ϑtk
=
≥ hv, vk i ≥ dmin > 0
und
dt+1 =
X
dt+1
≤
k
X
dtk − dmin ≤ . . . ≤
k
X
d0k − tdmin
k
2
Modifikation: Spheres
Wir betrachten das Lion and Man Problem: ein Mensch versucht einem Löwen zu
entkommen.
Lt+1
Lion
Man
Der Löwe wählt einen Punkt, so dass er zwischen den Menschen und dem Punkt
steht. Als Abgrenzung dient im Gegensatz zu Planes keine Hyperebene, sondern
eine Sphäre durch den Punkt und die Position des Löwen.
Spheres
• Initialisierung: Wähle Punkte pk auf Geraden durch E und Pk so, dass Pk ∈
pk E gilt und die Komponente von Rn \ Bd(pk ,Pk ) (pk ), welche E enthält, beschrieben ist.
p3
P4
P3
P5
E
P2
P1
• Pkt+1 = Pkt+1 (pk , Pkt , E t+1 )
• Pkt+1 ∈ pk E t+1 mit d(Pkt , Pkt+1 ) = 1 und d(Pkt+1 , E t+1 ) minimal.
15
Kapitel 1: Räuber und Gendarm
E t+1
Pkt+1
r
1
Et
Pkt
Satz
◦
Es sei D = Rn . Falls E ∈ conv(P1 , . . . , PN ) gilt, so ist Spheres erfolgreich.
Beweisskizze
Wir betrachten in dem folgenden Bild den Unterschied zwischen Planes und Spheres
E t+1
Et
Pkt
r
Pkt
E t+1
Pkt+1
α
pk
Pkt
Q (Wahl nach Planes)
β = P t (Q,E) Q
k
⇒ d(Dt+1 , E t+1 ) < d(Q, E t+1 )
Sei Rt = conv(p1 , . . . , pN ) \
eingeschlossene Bereich.
SN
k=1 Bd(pk ,Pkt ) (pk )
der zum Zeitpunkt t von den Sphären
P4t
P3t
P5t
Rt
P2t
P1t
Wie für Planes zeigt man: Es existiert ein ε > 0, so dass für alle Punkte x ∈ Rt
und Vektoren v ∈ Sn−1 ein k ≤ N und ein vk = kPPkk −x
−xk mit hvk (x), vi ≥ dmin > 0
existieren. Es sei v =
E t+1 −E t
kE t+1 −E t k
und vk = vk (E t ). Dann folgt wie für Planes:
d(P t , Ekt ) −d(Q, E t+1 ) ≥ hvk , vi ≥ dmin > 0
|
{z
=dt
}
Daraus folgt dann dtk − dt+1
≥ dmin .
k
(2)
Unser Ziel ist es nun eine Verallgemeinerung auf beliebige konvexe Gebiete zu finden.
Kopparty & Ravishankar diskutieren den folgenden Fall: Das Spielfeld D besteht aus
dem Schnitt von endlich vielen Halbräumen Hl .
D
H3
E
H3
F3
F2
16
H3
F1
3 Räuber und Gendarm
Die orthogonale Projektion Fl von E auf den Rand von Hl stell zusätzliche (virtuelle)
Verfolger dar, deren Bewegungen auf den Rand ∂Hl von Hl beschränkt sind. Für
Spheres lässt sich zeigen, dass die den Bewegungsspielraum von E einschränkenden
Bälle „monoton wachsen“. Genauer:
Pkt+1
pk
E t+1
Et
Pkt
Falls also d(pk , Ekt+1 ) ≤ konst. für alle t ∈ N gilt, so ist Spheres erfolgreich. Dies ist
äquivalent dazu, dass E im Inneren der konvexen Hülle von P1 , . . . , Pk , F1 , . . . , Fk
liegt.
Kopparty & Ravishankar behaupten, dies sei notwendig und hinreichend für den
Erfolg von Spheres. Bei unserer bisherigen Betrachtung unseres Algorithmus fallen
zwei Probleme ins Auge:
• Fl liegt unter Umständen nicht in D
E
H1
H2
F1
• Der Algorithmus ist unter Umständen nicht wohldefiniert
Et
Pt
E t+1
Hl
P t+1
Es werden möglicherweise Verfolgerpositionen außerhalb von D errechnet. Das
Verwerfen aller Verfolger Pk mit pk ∈
/ D führt unter Umständen dazu, dass
alle Pk verworfen werden
p1
P1
E
P2
p2
Die folgende Bedingung ist äquivalent zum ersten Problem:
Definition (Alexander-Bishop-Ghrist ’09)
Es sei D ⊆ Rn abgeschlossen und konvex. Für k ≤ N bezeichne Hk die abgeschlossene Halbebene, welche E enthält und deren Rand durch Pk und orthogonal zu EPk
verläuft.
17
Kapitel 1: Räuber und Gendarm
H2
P2
E
P1
H1
Die Konfiguration erfüllt die Bedingung (BC), falls D ∩
T
k≤N
Hk beschränkt ist.
Die Lösung des zweiten Problems bedarf einer Modifikation von Spheres. Im zweidimensionalen Fall ändern Randkollisionen der Verfolger (heuristisch) nichts.
E
P2
E0
π
2
π
2
P2
Im dreidimensionalen Fall sollte es möglich sein eine Konstellation in einem „breiten
und flachen“ Gebiet die Verfolger in jedem Schritt zu Kollisionen zu zwingen, so
dass eine Fluchtstrategie existiert. Zunächst lässt sich zeigen, dass (BC) notwendig
T
ist: Falls D ∩ k≤N Hk beschränkt ist, so existiert ein Strahl c mit dem Startpunkt
E und c ∩ Hk = ∅ für alle k ∈ N.
Hk
>
π
2
c
E
Dann gilt E (c, EPk ) > π2 für alle k ≤ N . Somit enthält der Halbraum H = {x |
hx, ċi ≤ hE, ci} alle Verfolger Pk und c ist eine Fluchtstrategie.
Zur Lösung des „Kollisionsproblems“
Modifikation von Spheres nach (A-B-G ’09) zu Rotating Spheres . Die Idee
besteht darin die Mittelpunkte pk in jedem Schritt so zu bewegen, dass
• Pkt+1 ∈ D
• (BC) erhalten bleibt
• Die Bälle um Pk hinreichend wachsen, so dass der Bewegungsspielraum von E
eingeschränkt wird.
Rotating Spheres
• Initialisierung: Wähle Punkte p0k auf dem Strahl von E durch Pk so, dass
S
Pk ∈ Epk gilt und die Komponente von D \ k≤N Bd(pk ,Pk ) (pk ) welche E
enthält, beschränkt ist. (folgt aus (BC))
• Pkt+1 = Pkt+1 (D, ptk , Pkt , E t+1 )
• Pk 00 ∈ ptk E t+1 mit d(Pkt , P 00 ) = 1 und d(P 00 , E t+1 ) minimal
18
3 Räuber und Gendarm
Pt
E t+1
P 00
pk
Falls P 00 ∈ D: Pkt+1 = P 00 , pt+1
= ptk
k
Falls P 00 ∈
/ D: Betrachte die folgende Zeichnung
E t+1
Pt
P0 P∗
pt+1
P 00
pt
E bezeichne P ∗ die orthogonale Projektion von P 00 auf D und pt+1
den
k
Punkt auf dem Strahl von E t+1 durch P ∗ mit d(E t+1 , ptk ) = d(E t+1 , pt+1
k ).
t+1 t+1
t+1
t+1
t
0
mit d(Pk , Pk ) = 1 und
Dann sei Pk = P der Punkt auf pk E
t+1
t+1
d(Pk , E ) minimal.
Satz (A-B-G ’09)
Für jedes konvexe Gebiet D ist Rotating Spheres erfolgreich, wenn die Konfiguration D, P1 , . . . , PN die Bedingung (BC) erfüllt.
Beweisskizze
t+1 2
t+1
t
t 2
t
0
t
0
1) Es gilt d(pt+1
k , Pk ) > d(pk , Pk ) + 1. Setze p = pk , p = pk , P = Pk , P =
t+1
Pk . Wir unterscheiden nun zwei Fälle.
Falls P 00 ∈ D: Es gilt
<1
P
α
1
p
P 00
2
d(p, P 00 )2 = d(p, P )2 + d(P, P 00 )2 − 2d(p, P )d(P, P 00 ) · cos
| {zα} > d(p, P ) + 1
<0
Falls P 00 ∈
/ D: Es gilt
E0
P0
P∗ ∈ D 0
p
β
P 00
p
P ∗ = projD (P 00 ) ∈ D, P 00 ∈
/ D, E ∈ D. Damit folgt für den Winkel β =
π
0
00
P ∗ (E , P ) ≥ 2 und d(p, P 00 ) ≤ d(p0 , P ∗ ) ≤ d(p0 , P 0 ), der Rest geht weiter
wie oben.
S
2) Setze C t = D \ k≤N Btk , Btk = Bd(pt ,P t ) (ptk ). Behauptung: C t+1 ⊆ C t .
k
k
19
Kapitel 1: Räuber und Gendarm
B00
D
P
P0P∗
Bt
H∗
∂H 0 ∩ ∂H ∗
p0
P 00
p
H0
Bt+1 B00
Falls pt+1 = p0 = p = pt : Aus 1) folgt Bt+1 ⊃ Bt .
Falls pt+1 = p0 6= p = pt : i) Bt ⊆ B00 und B ⊆ Bt+1
ii) B und B00 haben den gleichen Radius und ∂ B ∩∂ B00 ⊆ ∂H 0 . Daraus folgt
B00 ∩H 0 ⊆ B ∩H 0 = {x | d(x, p0 ) ≤ d(x, p)}
iii) ∂H ∗ ∩ ∂H 0 und ∂ B00 ∩∂H 0 werden durch P 00 P ∗ ∩ ∂H 0 „getrennt“, damit
folgt B00 ∩H ∗ ⊂ H 0 .
Insgesamt folgt aus diesen drei Punkten:
(iii)
(i)
(ii)
Bt ∩D ⊂ B00 ∩D ⊆ B00 ∩H ∗ ∩ D ⊆ B00 ∩H 0 ∩ D ⊂ B ∩H 0 ∩ D
(i)
⊆ Bt+1 ∩H 0 ∩ D ⊆ Bt+1 ∩D
Daraus folgt C t+1 ⊂ C t .
3) Es existiert C1 so, dass für alle xk ∈ B0k ∩D gilt d(xk , ptk ) ⊆ C1 . Wie oben gilt
xk ∈ B0k ∩D ⊆ . . . ⊆ Btk ∩D. Mit den Bezeichnungen wie oben sei Hkt+1 = H 0 der
mit H 0 ⊥ ptk pt+1
Halbraum durch den Mittelpunkt von ptk , pt+1
k
k . Es gilt
xk ∈ Btk ∩D ⊆ Bk 00 ∩ Hk∗
⊆ H 0 = {x | d(x, pt+1 ) ≤ d(x, p)}.
t
t
Also gilt d(xk , pt+1
k ) ≤ d(xk , pk ) und damit ist d(xk , pk ) uniform beschränkt.
H 0 = Hkt+1
x
pt+1
pt
(2)
4) E t ∈ C t ⊂ C 0 ist beschränkt. Damit folgt dass d(xk , E t ) uniform beschränkt ist
durch C2 .
(3)
(C1 + C2 )2 ≥ (d(xk , ptk ) + d(xk , E t ))2
(4)
≥ d(pk , E t )2
≥ d(pk , Pkt )2
(1)
≥ d(p0k , Pk0 ) + t
20
(2)
3 Räuber und Gendarm
Anwendung/Verallgemeinerung
Betrachte Gebiete D ⊆ Rn , welche sich als endliche Vereinigung konvexer abgeschlossener Dα schreiben lassen.
D2
D3
E = E2 = E3
E1
P
D1
E4
D4
S
Es seien D = α Dα eine endliche Vereinigung abgeschlossener konvexer Gebiete
Dα . Für E ∈ D bezeichne Eα = projDα (E). Eine Konfiguration D, E, {Pk } erfüllt
(EBC), falls eine Partition von {Pk } in Mengen {Pαi | i ≤ Nα } ⊂ Dα existiert, so
dass für Dα , Eα , {Pα,i } (BC) gilt. In diesem Fall existiert eine erfolgreiche VerfolgerS
strategie. Die Schrittweite ≤ 1 für E (bezüglich der Längenmetrik von D = Dα )
impliziert d(E t , E t+1 ) ≤ 1 in der Metrik (jedes) Rnα .
Da jedes projDα Abstände nicht vergrößert, gilt auch für alle Eα Schrittweite ≤ 1.
t = E = proj
In jedem Gebiet Dα gilt nach endlicher Zeit Pα,i
α
Dα (E). Falls Eα 6= E,
T
T
t
setze Pα,i = Eα für alle T ≥ t. Nach endlicher Zeit gilt dann Pα,i
= Eαt für alle α
α
t
= Et.
und damit ist E t = Eαt für ein α, das heißt Pα,i
α
Bhadanin-Ister ’12: In jedem einfachen kompakten Polygon mit Hinternissen existiert eine erfolgreiche Verfolgerstrategie.
E
Bei Polygonen kann man für Hindernisse eine Triangulierung wählen. Der Nachteil
dabei ist dass man einen Verfolger pro Gebiet braucht. Dies funktioniert auch, wenn
das Gebiet in eine Richtung unbeschränkt ist.
A) (Aigner-Fromme ’84) Jedes P kann ein geodätisches Segment c „bewachen“,
das heißt E wird gefangen, falls es c überquert.
B) (Ister et al. ’05) in jedem einfach zusammenhängenden Polygon existiert eine
erfolgreiche Strategie mit einem Verfolger.
c3
c1
E
c2
c01
21
Kapitel 1: Räuber und Gendarm
Wähle Kanten(züge) c1 3 P1 und c2 3 P2 . Setzt c3 so, dass D in Komponenten
zerfällt. Dann ist entweder P1 oder P2 frei. Nach endlicher Zeit liegt E in einem
einfach zusammenhängenden Polygon.
4 Geometrische Charakterisierung von Flucht- und
Verfolgerkurven
Im Folgenden sei das Soielfeld D ein CAT(0)- (beziehungsweise CAT(1)-) Raum.
Alle Resultate beziehen sich auf Greedy mit der Schrittweise d > 0, das heißt
P t+1 ∈ P t E t mit d(P t , P t+1 ) = d.
E t+1
Et
d
P t+1
Pt
Wie spiegelt sich der Ausgang eines Spiels in der Geometrie der Kurven P t , beziehungsweise E t , wider? Dabei verstehen wir die Wege P t , beziehungsweise E t , als
S
stückweise geodätische Kurven P = P t P t+1 . Für d = 1 ist P beziehungsweise E
nach der Bogenlänge parametrisiert.
Satz (Alexander-Bishop-Ghrist 2010)
Ist D ein CAT(0)-Raum, so ist D genau dann kompakt, wenn P stets gewinnt (mit
einem Verfolger).
Beweis
Ist D nicht kompakt, so existiert ein geodätischer Strahl als Fluchtstrategie.
Angenommen es existiert eine Fluchtstrategie. Für den Verfolgerabstand dt = d(P t , E t )
gilt dt+1 ≤ (dt − d) + d = dt .
E t+1
dt+1
αt+1
d
Et
d
Pt
P t+1
dt − d
Also konvergiert dt monoton fallend gegen ein d∞ > d. Betrachtet man den euklidischen Vergleichswinkel αt zu αt = P t (E t+1 , E t ), so folgt
(dt+1 )2 + (dt − d)2 − d2
2dt+1 (dt − d)
t+1
(d )2 + (dt )2 − 2dt
=
2dt+1 (dt − d)
2d∞ (d∞ − d)
→ ∞ ∞
= 1.
2d (d − d)
cos αt+1 =
t→∞
Also konvergiert αt gegen 0. Da für Vergleichswinkel stets αt ≤ αt gilt, folgt αt −−−→
0.
2
22
4 Geometrische Charakterisierung von Flucht- und Verfolgerkurven
Erinnerung
Es sei c eine reguläre ebene Kurve c : [0, l] → R2 und κ die Krümmung von c.
R
Dann ist τc = 0l κ die Totalkrümmung von c. Ist c nach Bogenlänge parametrisiert, so gilt κ = kc̈k. Bezeichnet ϑ die Drehwinkelfunktion von ċ, das heißt
ċ(t) = (cos ϑ(t), sin ϑ(t)), so gilt kc̈k = k(−ϑ0 sin ϑ, ϑ0 cos ϑ)k = |ϑ0 |. Damit ist die
Totalkrümmung die akkumulierte Winkeländerung von c.
c
c2
α2
α1
c1
c0
c(0)
ist c1 , . . . , cn eine Polynomapproximation von c, so ist die Summe der Komplementärwinkel αi = π − βi = π − (ci−1 , ci ) eine Approximation der Totalkrümmung von
c.
Definition (Totalkümmung)
Es sei c eine stückweise geodätische Kurve in einem CAT(κ)-Raum. Sind 0 = t0 <
t1 < . . . < tn = l so, dass ci = c|[ti−1 ,ti ] geodätisch Segmente sind, so bezeichne
P
βi = c(ti ) (ci−1 , ci ) die Innenwinkel. Die Totalkrümmung von c sei τc = i π − βi .
Für eine beliebige Kurve sei
τγ = lim sup{τc | c Polygonapproximation von γ}
τγ (t) = τγ |[0,t]
Im Fall von CAT(0) gilt Monotonität.
Ist c eine Verfeinerung einer Polygonapproximation c0 von γ, so gilt τc0 ≤ τc , wie
man an der Zeichnung erkennen kann:
β2
β20
β
c
α1
β10
α2
c
τc0 = π − β10 + π − β20
τ c = π − β1 + π − β2
β1
23
Kapitel 1: Räuber und Gendarm
Es gilt
τc = π − β1 + π − β + π − β2
≥ π − (β10 + α1 ) + π − β + π − (β20 + α2 )
= π − β10 + π − β20 +π − (β + α1 + α2 )
{z
|
τc 0
}
|
{z
}
≤β+α1 +α2 =π
≥ τc0
Definition (Umfang einer Kurve)
Es sei c eine Kurve. Der Umfang Rc von c ist der Radius des kleinsten Balles, der
das Bild von c enthält:
Rc (t) = inf{R | Bild c|[0,t] ⊂ BR (c(0))} = sup{d(c(0), c(t))}
t
Satz (Alexander-Bishop-Ghrist 2010)
Es sei c eine nach Bogenlänge parametrisierte Kurve in einem CAT(0)-Raum. Dann
gilt
(i) Gilt lim inf t→∞ τct(t) = 0, so folgt dass c unbeschränkt ist.
(ii) Falls τc (t) ≤ const · tλ für ein λ ∈ (0, 1) gilt (das heißt τc ∈ O(tλ )), so folgt
Rc (t) ≥ const · t1−λ für hinreichend große t (das heißt Rc ∈ Ω(t1−λ )).
Man kann c|[0,t] durch eine hinreichend feine Polynomapproximation ersetzen:
c(t2 )
c(t1 )
%
c1
σ1
c(0)
Wähle eine Partitionierung 0 = t0 < t1 < . . . < tn = t so, dass ci = c|[ti−1 ,ti ] eine
Totalkrümmung ≤ π2 hat mit n ≤ τcπ(t) + 1. Es bezeichne σi die Sekante c(ti−1 )c(ti )
2
und %i das durch ci und σi definierte Polygon. Jede Kurve (und insbesondere jedes
Polygon) in einem CAT(κ)-Raum lässt sich „ausfüllen“.
Satz (Rechetnyak 1968)
2π
Es sei c eine geschlossene Kurve in einem CAT(κ)-Raum X mit l(c) < √
. Dann
κ
2
existiert ein konvexes Gebiet C ⊆ Mκ und eine Bogenlängenparametrisierung c von
∂C, sowie eine nicht-expandierende Abbildung ϕ : C → X mit ϕ ◦ c = c.
Beweisskizze
Man sieht leicht ein, dass falls c|[a,b] geodätisch ist, so auch c|[a,b] und dass für Winkel
β, beziehungsweise β solcher aufeinanderfolgender Segmente β ≤ β gilt.
(2)
Beweis (zu Alexander-Bishop-Ghrist 2010)
(i) Es existiert zu %i ein konvexes Polygon %i mit den gleichen Seitenlängen wie %i .
Wie auch %i besteht %i aus einem konvexen Polygon ci mit der Totalkrümmung
P
P
τci = π − β i ≤ π − βi ≤ π2 und eine Sekante σi .
24
4 Geometrische Charakterisierung von Flucht- und Verfolgerkurven
ci
β2
⊆ R2
β1
σi
Es gilt
l(ci )
l(σ i )
≤
√
2, also
√
2≥
l(ci )
l(σ i )
=
l(ci )
l(σi )
=
ti −ti−1
l(σi ) .
Damit folgt
n
√ X
√ τc (t)
≤ 2
l(σi ) ≤ 2
+ 1 sup(σi )
π
!
t=
X
ti − ti−1
i
2
i=0
also
τc (t)
π
≥
t
2
!
1
1
√
−
.
t
2 sup l(σi )
Ist c beschränkt, so folgt τct(t) ≥ const > 0. Sei nun ohne Einschränkung c eine
Polynomapproximation. Zerlege c in n ≤ τcπ(t) + 1 Teilkurven ci mit τci ≤ π2 .
2
Bezeichnet σi die Sekante der Teilkurve ci , so gilt
√
ti − ti−1
l(ci )
=
≤ 2
l(σi )
l(σi )
und es folgt
!
t=
X
ti − ti−1
√ τc (t)
√ X
+ 1 sup l(σi )
l(σi ) ≤ 2
≤ 2
π
(*)
2
und
τc (t)
π
≥
t
2
1
1
√
−
t
2 sup l(σi )
!
Wenn c unbeschränkt ist, so ist l(σi ) beschränkt. Daraus folgt
für t 0 und damit folgt die Aussage von (i).
(ii) Gilt τc (t) ≤ const · tλ , so folgt aus (*)
t≤
τc (t)
t
≥ const > 0
√ τc (t)
2
+1
sup l(σi ) ≤ const · tλ · Rc (t)
π
2
| {z
}
|
{z
≤2Rc (t)
}
≤const·tλ
2
Daraus folgt die Behauptung von (ii)
Beweis (zum Beweis des ersten Satzes)
Es wurde bereits gezeigt, dass eine eine erfolgreiche Flucht gilt:
Et
dt
βt
Pt−1
Pt
αt
d
Et−1
dt−1 − d
Der Winkel αt = P t (E t−1 , E t ) konvergiert für t → ∞ gegen 0. Das liefert
1
t
1
t
t→∞
τ (t)
t
=
π − βi =
αi −−−→ 0. Damit folgt aus Satz (i), dass die Verfolgerkurve P ,
und damit D unbeschränkt ist.
2
P
P
25
Kapitel 1: Räuber und Gendarm
Satz (Alexander-Bishop-Ghrist 2010)
Es sei D ein CAT(0)-Raum. Dann gilt τP ≤ τE + π.
Beweis
Betrachte die folgende Zeichnung:
Ei+1
Ei
ϑi
δi
Pi+1
βt
αi
γi
Ei−1
αi + γi + δi ≤ π
ϑi ≤ γi+1 + δi
Pi
Pi−1
Es gilt
τP (nd) =
τE (nd) =
τP − τE (nd) =
=
n−1
X
i=1
n−1
X
π − βi ≤
π − ϑi ≥
i=1
n−1
X
n−1
X
i=1
n−1
X
αi ≤
n−1
X
π − γi − δ i
i=1
π − γi+1 − δi
i=1
(π − γi − δi ) − (π − γi+1 − δi )
i=1
n−1
X
γi+1 − γi = γn − γ1 ≤ π
i=1
2
5 Positive Krümmungsschranken
Im Folgenden Sei D stets ein CAT(1)-Raum. Beispiele für solche Räume sind die
Einheitssphäre Sn , die euklidische Ebene mit ausgeschnittenem offenen Ball R2 \ Bo1
S
oder verallgemeinert Rn \ ˙ Bo1 (pi )
Satz (Alexander-Bishop-Ghrist 2010)
Es sei D ein CAT(1)-Raum und Et eine erfolgreiche Fluchtstrategie mit d0 =
d(E0 , P0 ) < π. Dann gilt
√
τp (t) ≤ const · t.
Beweisskizze
Betrachte die Zeichnung
Ei
di
d
βi
αi
di−1 − d
Pi−1
26
Ei−1
5 Positive Krümmungsschranken
Aus der Dreiecksungleichung folgt di ≤ (di−1 − d) + d = di−1 , also ist di monoton
fallend. Es gilt
di ≤ d0 < π
Damit hat jedes Dreieck ∆Pi Ei−1 Ei den Umfang < 2π und besitzt damit ein eindeutiges Vergleichsdreieck in S2 . Damit gilt für den Vergleichswinkel αi dass αi ≤ αi
und es gilt
τp (t) =
X
π − βi ≤
X
αi ≤
X
αi .
Falls Ei eine erfolgreiche Fluchtstrategie ist, gilt d∞ = limi→∞ di > d. Es sei δi =
di − di−1 ≥ 0. Wendet man den sphärischen Kosinussatz auf das Vergleichsdreieck
an, so folgt
cos d ≤ cos d + δi sin d − const ·α2i
und daraus folgt α2i ≤ const ·δi · d. Aus der Cauchy-Schwarz-Ungleichung folgt
τp (nd) ≤
X
αi ≤
q
(n − 1)
X
α2i
q
(n − 1) · const ·d · (d0 − d∞ )
√
≤ const nd
≤
(2)
Bemerkung (zu d0 < π)
Betrachte das folgende Szenario in R2 \ B 3 (0)
2
E0 = E2 = . . .
. . . = E3 = E1
P1 = P3 = . . .
P0 = P2 = . . .
E und P starten an gegenüberliegenden Polen. Im ersten Schritt läuft E den Kreis
entlang nach links, während P nach rechts läuft. Da P jedes mal eine Geodätische
wählt und es nun zwei kürzeste Wege gibt kann P diese ungeschickte Wahl treffen.
In zweiten Schritt läuft E wieder zurück, während P erneut die unglückliche Wahl
trifft und ebenfalls zurückläuft. E und P wiederholen diese Prozedur immer wieder
und treffen sich niemals, weshalb τP (t) in diesem Szenario linear wächst.
Korollar
√
Ist D ein CAT(0)-Raum und Et erfolgreich, so gilt τP (t) ≤ const t.
Beweis
Winkel sind invariant unter Skalierungen. Damit sind die CAT(0) Bedingung und
˜ ·) = π d(·, ·) die skalierte Metrik, dann ist
die Totalkrümmung invariant. Sei d(·,
2d0
d˜0 = π2 < π. Der Rest folgt aus dem Satz.
2
27
Kapitel 1: Räuber und Gendarm
Korollar
Unter denselben Voraussetzungen wie in obigem Korollar gilt RE (t) ≥ const.
Beweis
√
Es gilt RP (t) ≥ const t nach dem obigen Korollar und Satz (ii). Ferner gilt
d(E0 , Et ) ≥ d(P0 , Pt ) − d(Pt , Et ) − d(E0 , P0 ) ≥ d(P0 , Pt ) − const
Daraus folgt
RE (t) = sup{d(E0 , Et )} ≥ . . . ≥ const ·RP (t) ≥ const
28
√
t
2
Kapitel 2
Bewegungsplanung &
Konfigurationsräume
Als Motivation für das folgende Kapitel können wir uns beispielsweise die Bewegungssteuerung gleichartiger Automaten, beziehungsweise Fahrzeuge, in einer UmS
gebung, etwa in der euklidischen Ebene R2 oder der Ebene R2 \ i≤k Ii mit Hindernissen, anschauen.
Unser Ziel ist es, bestimmte Positionen oder Zyklen von Bewegungen, zum Beispiel
zur Steuerung von Fahrzeugen in einer Lagerhalle, zu finden. Als Einschränkung
wählen wir dabei das Umfahren von Hindernissen.
Wir modellieren das Problem, so dass xi die Position des i-ten Automaten mit
xi ∈
/ Oi beschreibt, und Kollisionsfreiheit, das heißt xi 6= xj für i 6= j. Wir setzen
X = ×ni=1 (R2 \
[
∆ = {(x1 , . . . , xn ) ∈ R2n | xi = xj , i 6= j}
Ok ) \ ∆
k
Wir werden uns auf Graphen beschränken, das ist zum Einen motiviert durch Anwendung (Schienensysteme), und zum Anderen durch Methodik (lokale Kollisionsvermeidung).
Es sei X ein topologischer Raum. Die verallgemeinerte Diagonale von X n ist
∆ = ∆n (X) = {(x1 , . . . , xn ) ∈ X n | ∃i 6= j : xi = xj }. Der Raum
FN X = X n \ ∆n (X)
heißt der Konfigurationsraum von X.
Beispiel
F2 R2 = R3 ×S1 (Beweis zur Übung)
Die symmetrische Fruppe Sn wirkt frei auf Fn X. Dann heißt der Quotient Cn X =
Fn X der (ungeordnete) Konfigurationsraum von X. Die FundamentalgrupSn
pe π1 (Cn X) heißt die n-te Zopfgruppe von X. Die klassischen Zopfgruppen sind
Bn = π1 (Cn R2 ):
x1
x2
x3
x2
x1
x3
xn
29
lokale
Kollisionsvermeidung
Kapitel 2: Bewegungsplanung & Konfigurationsräume
[x1 , x2 , . . . , xn ] = [x2 , x1 , . . . , xn ]
Darstellung von B1 :
x1
xi xi+1
···
···
x1
Erzeuger: gi , i ≤ n − 1, Relationen:
• gi gj = gj gi , |i − j| ≥ 2
j
i
j
i
···
···
=
• gi gi+1 gi = gi+1 gi gi+1
i+1
i
i+1
=
w=
e
v=
∂+e
Ein Graph G besteht aus einer nichtleeren Eckenmenge V = V G, einer Kantenmenge E = G E und (surjektiven) Randabbildungen ∂ ± : E → V. Zur Notation
der Kantenorientierung sei Ẽ = E ×{+1, −1} mit den Randabbildungen
e+ = (e, 1) 7→ ∂ ± e
∂−e
e− = (e, −1) 7→ ∂ ∓ e.
und
Dann gilt für die Kanteninversion e± → e∓ , ∂ + e = ∂ − e und ∂ − e = ∂ + e. Es bezeichne
|e| stets die unorientierte Kante e.
Beispiel
w3
Y =
w2
w2
e3
e2
en
,
w
v
e1
e2
v
,Q=
e3
e3
e2
,
e2
v
v
e1
w1
e1
w1
Der Grad deg v einer Ecke ist die Zahl, wie oft v als Ecke einer Kante vorkommt.
Eine Ecke mit Grad ≥ 3 heißt essentiell, mit Grad 1 heißt sie frei.
Die geometrische Realisierung | G | eines Graphen G erhält man durch das Verkleben
von (Einheits-) Intervallen zu jeder Kante entsprechender Randabbildungen. Man
kann sich, aus topologischer Sicht, auf Graphen beschränken, deren Ecke entweder
frei oder essentiell ist. Jede essentielle Ecke v besitzt eine Umgebung U , so dass
U \ {v} in G in mindestens drei Zusammenhangskomponenten zerfällt.
Beispiel
Wir betrachten nun speziell F2 Y . Die Position zweier Punkte x und y auf benachbarten Kanten ist durch ein Einheitsquadrat parametrisiert. Die Achsen sind für
30
ihre jeweiligen Punkte zugelassene Positionen, solange nicht beide Punkte null sind,
da es dann zu einer Kollision käme.
1
y
x
v
v=x
y
y
x≡0=v
x
0
1
y≡0=v
Sechs dieser Parameterbereiche werden entlang der Kanten x ≡ 0 = v beziehungsweise y ≡ 0 = v miteinander verklebt
Liegen zwei Punkte x und y auf einer Kante, so sind ihre Koordinaten durch ein
„halbes“ Quadrat parametrisiert.
x
v
x
y
y
0
x1
Für C2 Y ergibt sich dann
Satz (Swiatowski 2001)
Es sei G ein endlicher Graph. Dann existiert ein nichtpositiv gekrümmter-Kuben
komplex Kn G ,→ Cn G = Fn G Sn , sodass Kn G ein Deformationsretrakt von Cn G
ist. Es gilt dim Kn G = min{n, b}, wobei b die Anzahl der essentiellen Ecken von G
ist.
Die Fundamentalgruppe π1 (Cn G) enthält eine frei abelsche Untergruppe vom Rang
min{b, b n2 c}. Die Konstruktion basiert darauf, die Verteilung von Punkten auf Ecken,
beziehungsweise Kanten, beziehungsweise die Übergänge zwischen solchen Zuständen zu beschreiben.
31
Kapitel 2: Bewegungsplanung & Konfigurationsräume
Ansatz (Abrams 2000)
Wie erhält man die Zellenstruktur beziehungsweise die Kombinatorik von | G |n =
{σ = σ1 × . . . × σn | σ Zelle von G} in Cn G? Man erhält Fn G durch das „Löschen“
der verallgemeinerten Diagonale.
| G |2
Analogon
| G |n ist ein Zellkomplex mit Zellen σ = σ1 ×. . .×σn . Die kombinatorische Diagonale
von | G |n besteht aus Zellen der Form σ = σ1 ×. . .×σn mit ∂σi ∩∂σj 6= ∅ für ein i 6= j.
Betrachten den kombinatorischen Konfigurationsraum mit Zellen σ = σ1 × . . . × σn
mit ∂σi ∩ ∂σj = ∅ für alle i 6= j. Dies sind genau die n-Tupel von Punkten, welche
paarweise durch eine (offene) Kante getrennt sind.
v3
v2
e3
v
Beispiel
G = Y : 1-Zellen der Form v × e, wobei e eine der Ecke v gegenüberliegende Kante
ist.
× e2
v1 × v
e1
v1 × e2
v1
v1 × v2
Anschließend lässt sich der kombinatorische Konfigurationsraum auf Cn G retraktieren. Leider erhält man im Allgemeinen nicht die Topologie von Cn G: Beispiel
e2
v
v
e1
; v × w. Es gilt zumindest
Satz (Abtrams 2000)
Ist G ein einfacher Graph, das heißt enthält keine Schleifen der Länge ≤ 2, so ist sein
kombinatorischer Konfigurationsraum auf zwei Punkten ein Deformationsretrakt von
C2 G.
Beispiel
π1 (C2 , Y )
C2 Y
Erzeuger von π1 (C2 Y ) = Z
32
Definition (Swiatowski)
Es sei G ein endlicher Graph, dessen nichtessentialle Ecken frei sind, mit Kanten E
(k)
und Ecken V. Es bezeichne B die Menge der essentiellen Ecken. Es sei Pn G die
Menge der Paare (f, S) mit
(i) f : E ∪ B → N0 eine Abbildung
(ii) S = {e1 , . . . , ek } paarweise verschiedene orientierte Kanten
(iii) vei = ∂ + ei ∈ B und vei 6= vej für i 6= j
(iv) f (v) ∈ {0, 1} für alle v ∈ B und f (vei ) = 0 für alle i ≤ k
P
(v) |a|∈E ∪ B f (|a|) = n − k.
˙
Es gelte dabe (f, S) ≺ (g, S ∪{e})
mit e ∈
/ S, falls entweder
(a) f (ve ) = g(ve ) + 1(= 1) und sonst f (a) = g(a)
oder
(b) f (|e|) = g(|e|) + 1 und sonst f (a) = g(a)
˙ n(k) G und
gilt. Es bezeichne ≺ die davon erzeugte partielle Ordnung auf Pn G = ∪P
Kn G seine geometrische Realisierung.
0-Skelett: Paare (f, ∅) mit f : E ∪ B → N0 , |a|∈E ∪ B f (|a|) = n, f „zählt“ wieviele
Punkte auf einer Kante beziehungsweise essentiellen Ecke sitzen.
P
v
×
e
∼ (f, ∅) mit f (e) = 2, f (v) = f (w) = 0
τ0 = (f, ∅)
×
w
Zwei solche 0-Zellen sind durch eine Kante (1-Zelle) verbunden, wenn einer der
Punkte das Innere einer Kante durch eine essentielle Ecke betritt oder verlässt.
v
v
×
×
e
!
e
×
w
(b)
τ1 = (g, ∅)
g([e|) = 1
g(w) = 1
τ0
τ1
σ = (h, {e})
×w
(a)
h(|e|) = 1 =⇒ τ0 ≺ σ, h(w) = 0 =⇒ τ1 ≺ σ (h(v) = 0)
Die höherdimensionalen Zellen bestehen aus k-Tupeln von unabhängigen Zügen wie
oben. Ist σ = (g, {e1 , . . . , ek }) eine k-Zelle in Kn G, so besitzt σ genau 2k Facetten
der Kodimension 1:
∂e±i σ = (gi± , {e1 , . . . , eˆi , . . . , ek })
mit gi+ (vei ) = 1, beziehungsweise gi− (|ei |) = g(|ei |) + 1. Damit ist Kn G ein Kubenkomplex: Jede Menge {τ | τ ≺ σ} ist ein Würfel.
Wir definieren die Dimension als dim Kn G = min{| B |, n}. Es gilt dann dim Kn G =
(k)
max{k | Pn G 6= ∅}. Wir beweisen die Aussage:
Aus (ii) und (iii) folgt dim Kn G ≤ | B |. Ist k = min{| B |, n}, so existieren paarweise
verschiedene essentielle Ecken v1 , . . . , vn . Da vi essentiell ist, existieren paarweise
33
Kapitel 2: Bewegungsplanung & Konfigurationsräume
verschiedene Kanten e1 , . . . , ek mit vi = vei . Es sei S = {e1 , . . . , ek } und
f : E ∪ B → N0
|a| 7→

n − k
|a| = e1
0
sonst
.
(k)
Dann gilt (f, S) ∈ Pn G.
Beispiel
Betrachte wieder den Graphen G = Y , wir suchen K2 Y mit B = {v}, E = {e1 , e2 , e3 }
und dim K2 Y = min{| B |, n} = min{2, 1} = 1.
e3
G=
e2
v
e1
Für die 1-Zellen setze σ = (g, S) mit |S| = 1, also S = {ei } für ein i ∈ {1, 2, 3}.
Dann folgt g(vei ) = g(v) = 0 nach (iv). Daraus ergibt sich für die Summe
X
g(|a|) = g(|e1 |) + g(|e2 |) + g(|e3 |) + 0 = n − k = 2 − 1 = 1
=g(v)
|a|∈E ∪ B
Da alle Summanden positiv sind muss es genau ein j mit g(|ej |) = 1 geben, und
damit existieren insgesamt genau neun 1-Zellen σij = (|ej | →
7 1, {ei }) als Ränder.
Für die 0-Zellen ergibt sich dann:
7→ 1
(a) ∂ + σij = ( |evj | 7→
1 , ∅) = τj (deg τj = 3)
|e | 7→ 1
(b) i 6= j: ∂ − σij = ( |eji | 7→ 1 , ∅) = τij = τji (deg τij = 2)
i = j: ∂ − σii = (|ei | 7→ 2, ∅) = τii (deg τii = 1)
Anschaulich ergibt sich schließlich folgendes Bild:
τ33
σ33
σ13
τ13 = τ31
τ3
σ23
σ31
τ23 = τ32
τ1
σ32
σ11
τ11
σ21
τ2
σ12
τ21 = τ12
σ22
τ22
Einbettung ι : Kn G ,→ Cn G
Sei die Verteilung von k Punkten auf einer Kante e durch De (k, (s, t)) ⊂ Cn G ∩e,
mit (s, t) ∈ [0, 1], gegeben mit
xk
x3
x1 x2
ve
34
x4
e
ve
•x1 < . . . < xk
•|xi − xi+1 | = d
•|ve − x1 | = s · d und |ve − vk | = t · d
(k)
als koordinaten auf einem Würfel σ = (f, S) ∈ Pn . Definiere t : σ → [0, 1]s durch
lineare Fortsetzung der Abbildung auf seinen 0-Zellen p = (f, ∅):
t(p) : S → [0, 1]
e 7→ 1 − f (e).
Für jedes x ∈ σ = (g, S) ⊂ Kn G ist t(x) eine Abbildung von S in [0, 1]. Setze fort
t(x) : E → [0, 1]
e 7→

t(x)(e)
e∈S
1
sonst
.
Daraus erhält man eine Einbettung ισ : σ = (g, S) → Cn G, x 7→ {v ∈ B | g(v) =
S
1} e∈E De (g̃(|e|), (t(x)(e), t(x)(e))), wobei g̃(|e|) = g(|e|) + #{s ∈ S | |s| = e}.
˙
Es sei x ∈ τ = (f, S) ≺ σ = (g, S ∪{e}).
Wir beschränken und im Folgenden zunächst
nur auf den Fall (a), der Fall (b) folgt dann analog. Sei f (ve ) = g(ve ) + 1 = 1, also
tσ (x)(e) = 0 und ve ∈ vτ (x) für e ∈
/ S. Dann folgt tτ (x)(e) = 1. Aus f (|e|) = g(|e|)
˜
folgt g̃(|e|) = f (|e|) + 1.
Es folgt
v
t·d=0
De ( g̃(|e|) , (tσ (x)(e), tσ (x)(e)))
| {z }
| {z }
=0
=f˜(|e|)+1
= De (f˜(|e|) + 1, (s, 0))
= {ve } ∪ De (f˜(|e|), (s, 1))
Damit definiert ι =
S
σ ισ
⇒ ισ (x) = ιτ (x)
eine Einbettung Kn G ,→ Cn G.
Retraktion r : Cn G → Kn G
Sei C ∈ Cn G und bezeichne nC
e = #(C ∩ e) \ B die Anzahl der Punkt auf e. Setze
d0e =

1
nC
e =0
min{|v − x| | x ∈ C ∩ e \ B}
e
sonst
und die mittlere Segmentlänge
tC
e =
1
.
nC
e +1
min{1,
C
δeC = dC
e (ne + 1)
Setzte weiterhin

1
falls ve frei oder ve ∈ C
δeC
min{δeC |e0 6=e∧ve0 =ve }
} sonst
Definiere
r : Cn G → ι(Kn G)
C 7→ (C ∩ B) ∪
ve
×
= dC
e
[
C C
De (nC
e , (te , te ))
e
Homotopie id ∼
=r
Für beliebiges C ∈ Cn G gilt
• C ∩ B = r(C) ∩ B
• #(C ∩ e) \ B = #(r(C) ∩ e) \ B für alle e ∈ E
Definiere die Homotopie kantenweise, so dass Punkte in die vorgegebene Standardposition bewegt werden.
35
Kapitel 2: Bewegungsplanung & Konfigurationsräume
1 Geometrie des Kubenkomplexes Kn G
τ̊ offenes Inneres von τ
Definition (Mκ -Komplex)
Es sei σi , für i ∈ I, eine disjunkte Familie konvexer Polyeder, das heißt σi ist eine
konvexe Hülle endlich vieler Punkte in Mκni . Es sei ∼ eine Äquivalenzrelation auf
ti∈I σi , X = ti σi ∼ und π : ti σi → X die kanonische Projektion. X heißt Mκ Polyederkomplex, falls gilt:
(i) Ist τ ≤ σi eine Seite, so ist π|τ̊ injektiv.
(ii) Sind x1 ∈ σ1 und x2 ∈ σ2 mit π|σ1 (x1 ) = π|σ2 (x2 ), so existiert eine Isometrie
ϕ : supp(x1 ) → supp(x2 ) mit π|σ1 (y) = π|σ2 (ϕ(y)) für alle y ∈ supp(x1 ); wobei
supp(xi ) die eindeutige Seite τ < σi mit τ̊ 3 xi ist.
x
supp(x) =
σi
Ein Mκ -Polyederkomplex ist im Allgemeinen kein simplizialer Komplex. Betrachte
die folgenden beiden Beispiele:
(1) 2-Torus:
π
∼
σ = [0, 1]2 einziger Polyeder, ∼ Kantenidentifikation (wie üblich)
Kein simplizialer Komplex, denn π|σ ist nicht injektiv
(2) Digon: zwei (maximale) Polyeder e1 ∼
= e2 ∼
= [0, 1], ∼= Identifikation der Randpunkte
e1
v
w
e2
(i) π|ei ist injektiv.
(ii) π(e1 ) ∩ π(e2 ) = {v, w} ist nicht gemeinsame Seite des Polyeders.
Der Kubenkomplex Kn G ist ein M -Polyederkomplex im obigen Sinne. Kn G enhält
keine Schleifen. Ist σ ⊂ Kn G ein 1-Würfel, das heiß σ = (f, {e}), so gilt ∂ + (f, {e}) =
ve 7→
0
ve 7→ 1
−
( |e|
7→ f (|e|)+1 , ∅) 6= ∂ (f, {e}) = ( |e| 7→ f (|e|) , ∅).
Es gibt Digone in Kn G: Es gelte n ≥ 1 und G enthalte eine Schleife. betrachte die
folgenden Konfigurationen:
×
×
e
×
und
×
bzw.
×
v
×
Es gelte ve = v = ve , damit existieren zwei Intervalle in Kn G, welche das Verlassen
der orientierten Kante e parametrisieren:
(f, {e})
h(v) = h(ve ) = h(ve ) = 1
h(|e|) = h(|e|) = 1
36
(h, ∅)
(g, ∅)
(f, {e})
g(v) = g(ve ) = g(ve ) = 1
g(|e|) = g(|e|) = 1
f (|e|) = 1 = h(|e|) (def. Digon in Kn G)
f (ve ) = 0
1 Geometrie des Kubenkomplexes Kn G
Jeder höherdimensionale Würfel in Kn G ist eindeutig durch seine Kodimension-1Seiten bestimmt: Es seien (g, S) und (h, T ) Würfel der Dimension ≥ 2 in Kn G mit
{∂i± (g, S)} = {∂i± (h, T )}. Es gilt
2|S| = #{∂i± (g, S)} = #{∂i± (h, T )} = 2|T |.
Daraus folgt |S| = |T | ≥ 2, also S = T . Man sieht leicht ein, dass dann auch g = h
gilt, also (g, S) = (h, T ).
Metrik auf Kn G (bzw. Mκ -Polyederkomplexen)
Es seien x, y ∈ X. Ein s ∈ {x0 , . . . , xk } mit x0 = x, xk = y und xi , xi+1 ∈ σi für
P
einen Würfel (bzw. Polyeder) heißt k-Kette. Mit l(s) = i dσi (xi , xi+1 ) sei ihre
Länge bezeichnet, wobei dσi die Metrik auf σi ist. Es sei
x
y
d(x, y) = inf{l(s) | s Kette von x nach y}.
Dies definiert im Allgemeinen keine Metrik. Es sei X der Polyederkomplex aus abzählbar vielen Kanten ek der Länge k1 . Dann gilt
1
= 0.
k k
Auf dem Kubenkomplex Kn G definiert d eine Metrik: Kn G ist zusammenhängend,
da G zusammenhängend ist. Es genügt zu zeigen, dass d(x, y) 6= 0 für x 6= y gilt:
Liegen x und y in einem Würfel σ, so ist dies offensichtlich (d|σ ist eine euklidische
Metrik auf diesem Würfel). Andernfalls betrachte für x ∈ σ
d(v, w) ≤ inf{l(ek ) | k ∈ N} = inf
εσ (x) = inf{dσ (x, τ ) | τ < σ, τ 63 x}
Dies ist in Kn G stets positiv. Man kann zeigen, dass l(s) ≥ εσ (x) für jede Kette s
von x nach y gilt, also d(x, y) > 0. Man sieht leicht ein, dass d eine Längenmetrik
ist.
Geodäzität und Vollständigkeit
Satz (Bridson 1991)
Es sei X ein zusammenhängender Mκ -Polyederkomplex. Falls in X nur endlich viele Isometrietypen von Polyedern existieren, so ist X ein geodätisch vollständiger
metrischer Raum.
Ohne Einschränkung kann man annehmen, dass X simplizial ist. Betrachte straffe
Ketten s = {x0 , . . . , xk }.
(i) Kein Tripel Xi−1 , xi , xi+1 liege in einem gemeinsamen Simplex.
(ii) Gilt xi−1 xi ∈ σi−1 und xi xi+1 ∈ σi , so sei xi−1 xi ∪xi xi+1 geodätisches Segment
in σi−1 ∪∼ σi .
Beachte: Das heißt nicht, dass xi−1 xi ∪ xi xi+1 geodätisch in X ist, wie man an
dieser Zeichnung erkennt:
σ1
x1
x2 σ2
x3
σ1
x2 σ2
x1
x3
σ3
37
w
v
ek
e1
Kapitel 2: Bewegungsplanung & Konfigurationsräume
Es gilt d(x, y) = inf{l(s) | s straffe Kette von x nach y}. Für jede Länge l existiert
eine Schranke N , abhängig von l und den Isometrietypen von Simplices, so dass jede
straffe Kette der Länge l höchstens N Simplices durchläuft.
Für x, y ∈ X durchlaufen straffe Ketten hinreichend kleiner Länge nur endlich viele
„Modellräume“, welche durch die endlichen Kombinationen der endlich vielen Isometrietypen gegeben sind. Jeder solche „Modellraum“ enhält eine kürzeste Geodätische
(Moussong 1988).
2 Nichtpositive Krümmung von Kubenkomplexen
Das Innere der Kuben ist CAT(0), da jeder Kubus die euklidische Metrik trägt. Die
Kümmung des Komplexes „konzentriert“ sich in den Ecken, das heißt 0-dimensionalen
Würfeln.
Zur Erinnerung: Das Komplement eines Quadranten in R2 ist CAT(0) und gegeben
durch R2 \Q = {(x1 , x2 ) ∈ R2 | x1 ≤ 0, x2 ≤ 0}.
z
Q
y
x
Das Komplement eines Oktanten in R3 ist nicht CAT(0).
z
y
x
Die folgenden Würfelkomplexe sind euklidisch und CAT(0):
z
z
x
σ1
x
y
„B = cone(lk(v))“
B
; acht Quadrate:
v
lk(v)
σ3
y
σ2
v
x
σ1
σ2
y
σ3
Allerdings ist dies hier nicht mehr CAT(0), vergleichbar mit dem Oktanten:
x
z
x
Man kann den Knoten v als Spitze eines Kegels betrachten und den Link lk(v) als
den Grundkreis. Je größer der Link, umso flacher der Kegel.
38
2 Nichtpositive Krümmung von Kubenkomplexen
Es sei v eine Ecke. Der Link lk(v) ist ein abstrakter simplizialer Komplex mit einem
k-Simplex für jeden (k + 1)-Würfel, der v enthält. Für K sieht der Link lkK (v)
folendermaßen aus:
σ1
σ2
Satz (Gromovs Link-Bedingung)
Es sei K ein endlichdimensionaler Kubenkomplex. K ist genau dann nichtpositiv
gekrümmt, wenn der Link jeder Ecke ein Fahnenkomplex ist.
Ein Fahnenkomplex ist ein simplizialer Komplex, in welchem jede Menge von
Ecken, die paarweise durch Kanten verbunden sind, einen Simplex aufspannen. Ein
Komplex, welcher maximal unter allen Komplexen mit dem gleichen 1-Skelett ist,
ist ein Fahnenkomplex.
v
lk(v)
Linkbedingung
verletzt
Link-Bedingung in Kn G
Es sei x ∈ Kn G eine Ecke, das heißt x = (f, ∅) mit f : E ∪ B → N0 , a∈E ∪ B f (|a|) =
n und f (v) ∈ {0, 1} für alle v ∈ B. Es gilt lk(x) = {σ ∈ Kn | (f, ∅) ≺ σ}. Ein
σ = (g, S) enthält genau dann (f, ∅), wenn gilt
P
g(a) =



f (a)



a ∈ B ∧a 6= ve , e ∈ S
a = ve , e ∈ S
0

P



s∈S (f (vs ) − 1)
f (a) +
a∈E
|s|=a
Solche σ = (g, S) sind eindeutig bestimmt duch Teilmengen S ⊂ E, welche die
folgenden Bedingungen erfüllen:
(i) ve ∈ B für alle e ∈ S
(ii) ve 6= ve0 für e, e0 ∈ S
(iii) f (|e|) + f (ve ) ≥ 1 für alle e ∈ S
(iv) f (|e|) + f (ve ) + f (ve ) ≥ 2
Der Link von x besteht aus den Teilmengen S, die (i) bis (iv) erfüllen. Jede solche
Teilmenge S definiert einen (|S| − 1)-Simplex von lk(x). Die Bedingungen (i) bis (iv)
gelten genau dann für eine Teilmenge S, wenn wie für alle ein- und zweielementigen
Teilmengen gelte.
Ist dann (gi , {ei })i≤k eine Menge von Ecken in lk(x), das heißt Kanten in Kn G, die x
enthalten, und sind diese alle durch Kanten (hij , {ei , ej }) verbunden, so sind (i) - (iv)
für {ei } und {ei , ej } erfüllt. Damit gelten die Bedingungen auch für S = {e1 , . . . , ek }
und es existiert ein g mit (g, S) x = (f, ∅); Die Kanten (hij , {ei , ej }) in lk(x)
spannen also einen Simplex auf. Damit ist lk(x) ein Fahnenkomplex.
Somit ist nach Gromovs Link-Bedingung Kn G nichtpositiv gekrümmt. Das liefert
uns
39
Kapitel 2: Bewegungsplanung & Konfigurationsräume
]
• K
n G ist (global) CAT(0)
• πk (Kn G) = 0 für alle k ≥ 2
• Kn G ,→ Cn G Deformationsretrakt ⇒ π∗ (Kn G) = π∗ (Cn G)
• π1 (Cn G) = π1 (Kn G), πk (Cn G) = 0, k ≥ 2
Sei k = min{| B |, b n2 c}, dann gilt π1 (Cn G) ≥ Zk = π1 (T ), ein Torus durch die
Wirkung π1 (Cn G) y Kn G. Finde T k in Kn G, das heißt „finde S1 en in Kn G“.
×
×
×
×
×
!
×
×
×
Jede essentielle Ecke v ∈ B in G hat deg(v) ≥ 3. Für jeden Erzeuger einer S1 in Kn G
benötigt man zwei Teilchen und eine essentielle Ecke von G.
3 Verallgemeinerung: Lokal rekonfigurierbare Räume
Wir betrachten das folgende motivierende Beispiel von Chirikjiam aus den 1990er
Jahren. In einem zweidimensionalen Modell liegen sechseckige Bausteine, angeheftet
an Kanten und drehbar an Ecken.
Es sei G ein Graph und A eine Menge. Ein Zustand ist eine „Färbung“ von G durch
A, das heißt u : V G → A.
In dem obigen Beispiel ist G ein hexagonaler Graph und A = {0, 1}. Ist eine Position
v ∈ G durch ein Sechseck besetzt, so sei u(v) = 1, sonst 0. Ein Erzeuger ϕ besteht
aus
• einem Träger supp ϕ ⊆ G, einem Teilgraph von G
• seiner Spur tr ϕ ⊆ supp ϕ, einem Teilgraph von supp ϕ
ϕ
ϕ
• einem Paar lokaler Zustände uϕ
i : supp ϕ → A, u0 |supp ϕ\tr ϕ = u1 |supp ϕ\tr ϕ
Der Erzeuger gibt uns also Aufschluss über die Drehung
ϕ
!
Bei einer Drehung passiert ein Punkt mehrere Sechsecke, daher zählen diese Sechsecke auch zum Träger
40
3 Verallgemeinerung: Lokal rekonfigurierbare Räume
tr ϕ
supp ϕ
Ein Erzeuger heißt zulässig auf einem Zustand u, falls u|supp ϕ = uϕ
0 gilt. Dann sei
ϕ.u : V G ,→ A
v 7→

u(v)
v∈
/ supp ϕ
uϕ (v)
1
v ∈ supp ϕ
die Wirkung von ϕ auf u. Ein lokal rekonfigurierbares System (LRS) sei eine
Menge von Zuständen und Erzeugern, welches abgeschlossen unter dieser Wirkung
ist. Ein geeignetes geometrisches Modell von Cn G erhielt man aus den unabhängigen
Bewegungen von Punkten durch essentielle Ecken.
Eine Familie von Erzeugern {ϕi } heißt kommutativ, wenn tr ϕi ∩ supp ϕj = ∅ für
alle i 6= j. Analog zu Cn G beziehungsweise Kn G erhält man so einen Kubenkomplex,
ein geometrisches Modell für den Zustandsraum des LRS.
Es seien u und w Zustände und ϕ1 , . . . , ϕk zulässige kommutativ Erzeuger. Die Paare
(u, {ϕi }) und (w, {ϕi }) heißen äquivalent, wenn u|V G \ S supp ϕi = w|V G \ S supp ϕi
i
i
gilt.
Der Zusatandskomplex eines LRS besteht aus den Äquivalenzklassen von Zuständen u und Erzeugern ϕ1 , . . . , ϕk , seinen k-Kuben [u, {ϕi }], mit den Randabbildungen ∂j− [u, {ϕi }] = [u, {ϕi }i6=j ] beziehungsweise ∂j+ [u, {ϕi }] = [ϕ.u, {ϕi }i6=j ]. (im
Allgemeinen nicht lokal endlich)
Satz (Ghrist ’07?)
Ein lokal endlicher Zustandskomplex eines LRS ist nicht-positiv gekrümmt.
Als Konsequenz ergibt sich daraus, dass C ein Eilenberg-McLane-Raum ist, das heißt
πk (C) = 0 für k ≥ 2.
• Jede Homotopieklasse von Wegen besitzt genau einen geodätischen Repräsentanten.
• Die Fundamentalgruppe ist torsionsfrei.
• π(C) ,→ G C =< ϕi | ϕ2i = id, [ϕi , ϕj ] >, rechtwinklige Artin-Gruppe
Ein weiteres Beispiel für ein LRS ist ein diskretes Modell für Cn G, homöomorph
zu Kn G (nach eventueller Unterteilung von G). Wir schauen uns nun ein konkretes
Beispiel an.
„Diskreter“ Roboterarm
Um die Bewegungen der Gelenke diskret zu machen legen wir ein Gitter und lassen
Bewegungen von entweder 90◦ oder 180◦ zu.
41
Kapitel 2: Bewegungsplanung & Konfigurationsräume
G = Z2 ∩ R2≥0
A = {0, 1}
nicht diskret
diskret
Für die Erzeuger gilt
1
1
0
1
ϕ
!
1
0
1
0
1
0
1
1
!
und
1
0
ψ
1
0
Entsprechend gilt für die Träger und Spuren
supp ϕ = supp ψ =
42
mit tr ϕ =
und tr ψ =
Kapitel 3
„Gestänge“ (Linkages)
Betrachte einen (stilisierten) Roboterarm mit zwei Gelenken, eines in 0 ∈ R2 fixiert,
und zwei Stangen fixer Länge l1 > l2 , die über das weitere Gelenk miteinander
verbunden sind.
Der Konfigurationsraum C, das heißt der Raum aller möglichen Positionen beider Stangen , wird durch ihre Winkel zur x-Achse parametrisiert, das heißt C =
T 2 = S1 × S1 . Sein Arbeitsbereich W , das heißt die Menge der Positionen des
Endpunktes, ist ein Annulus mit äußerem Radius l1 + l2 und innerem Radius l1 − l2 .
Das liefert die Parametrisierung
α : C = T2 → W
l2
ϑ2
l1
ϑ1
(ϑ1 , ϑ2 ) 7→ l1 · ϑ1 + l2 · ϑ2
Lemma
Es bezeichne ∆ die Diagonale in T 2 und ∆∗ = {(ϑ, −ϑ) | ϑ ∈ S1 }. Das Komplement T 2 \ ∆ ∪ ∆∗ besitzt zwei Komponenten, deren jede von α diffeomorph auf W
abgebildet wird.
1 Abstandsfunktion von Roboterarmen
Zur Untersuchung der Abstandsfunktion k i≤n li ϑi k genügt die Betrachtung des
Raumes aller möglichen „Gestalten“ des Armes, seines Modellraumes: Seine „Gestalt“
hängt nicht vom ersten Winkel, beziehungsweise seiner Länge im R2 ab. Der Modellraum sei definiert als
P
l3 l
4
l2
k
l1
P
l i ϑi k
i≤n
1
1
W = (ϑ1 , . . . , ϑn ) ∈ S × . . . × S SO(2).
−1
Durch die Abbildung [ϑ1 , . . . , ϑn ] 7→ (1, ϑ2 ϑ−1
1 , . . . , ϑn ϑ1 ) erhält man einen DiffeoP
morphismus M ∼
= T n−1 . Für jeden festen Abstand k i≤n li ϑi k ist das Urbild der
Abstandsfunktion der Raum der geschlossenen polygone mit Kantenlängen l1 , . . . , ln .
2 Polygonräume
l4
Jedes geschlossene Polygon ist, bis auf euklidische Bewegungen, durch l1 , . . . , ln und
die orientierten Winkel zwischen den Kanten charakterisiert. Normalisiert man die
letzte Kante auf die x-Achse mit ϑn = −e1 , so erhält man als Modulraum Ml =
P
{(ϑ1 , . . . , ϑn ) ∈ S1 × . . . × S1 |
li ϑi = 0, ϑn = −e1 }. Jede solche Normalisierung
entspricht einer Drehung, also
1
1
Ml = {(ϑ1 , . . . , ϑn ) ∈ S × . . . × S |
P
li ϑi = 0}
SO(2)
l1
l5
l3
l1
ln
43
l2
Kapitel 3: „Gestänge“ (Linkages)
l2
l3
l1
l3
l2
wobei auch hier SO(2) diagonal auf dem n-Torus wirkt.
Jede Permutation σ ∈ Sn induziert einen Diffeomorphismus ϕσ : T n → T n durch
ϕσ (ϑ1 , . . . , ϑn ) = (ϑσ(1) , . . . , ϑσ(n) ). Da die Summation und SO(2)-Wirkung invariant unter der Permutation sind, erhält man so einen Diffeomorphismus Ml → Mlσ ,
mit ˜l = (lσ(1) , . . . , lσ(n) ). Das Diffeomorphismus hängt nicht von der Reihenfolge der
Kantenlängen ab.
Im Fall n = 3 nehmen wir l1 ≥ l2 ≥ l3 an. Falls l1 = l2 + l3 gilt, so ist das
Dreieck entartet, es gilt Ml = {∗}. Ist die Dreickesungleichung strikt erfüllt, das
heißt l1 < l2 + l3 , so existieren zwei Dreiecke mit genau diesen Kantenlängen, welche
sich durch eine Spiegelung unterscheiden. Gilt l1 > l2 + l3 , so existiert kein Dreieck
mit diesen Kantenlängen und Ml = ∅.
l1
Lemma
Für n ≥ 3 gilt genau dann Ml = ∅, wenn li > l1 + l2 + . . . + ˆli + . . . + ln für ein i ≤ n
gilt.
Beweis
P
Offensichtlich ist die Bedingung hinreichend. Es gelte li = i6=j lj für alle i ≤ n. Für
n = 3 ist die Aussage klar. Für n ≥ 4 existiert ein i ≤ n, so dass
li + li+1 ≤ l1 + . . . + li−1 + li+2 + . . . + ln
gilt, denn wäre dem nicht so, so gälte
2(li + li+1 ) >
X
li = L
für alle i und es folgte
4·L=
X
2(li + li+1 ) > n · L .
i≤n
Nach Induktion existiert ein geschlossenes Polygon mit Kantenlängen l1 , l2 , . . . , li +
li+1 + . . . + ln , das heißt ein n-gon mit kollinearen Kanten der Längen li und li+1 .
Damit gilt Ml 6= ∅.
2
Wann ist Ml eine Mannigfaltigkeit? Ein Längenvektor l = (l1 , . . . , ln ) heißt geneP
risch, wenn es keine εi ∈ {+1, −1} gibt mit i≤n εi li = 0.
Satz
Ist l ∈ Rn>0 generisch, so ist Ml eine kompakte orientierbare (n − 3)-Mannigfaltigkeit
ohne Rand.
n
Es sei W = T SO(2) der Modulraum eines Roboterarmes mit n Stangen und
fl : W → R
[ϑ1 , . . . , ϑn ] 7→ k
X
li ϑi k2
i≤n
die Höhenfunktion zum Längenvektor l = (l1 , . . . , ln ). Ist fl (p) = 0, so ist der Arm
geschlossen, das heißt p bestimmt ein geschlossenes ebenes n-gon mit Kantenlängen
l1 , . . . , ln , d. h. p ∈ Ml . Der Modulraum liegt als Nullstellenmenge von fl in dem
(n − 1)-Torus W ; M besteht genau aus den Maximalstellen von fl .
44
2 Polygonräume
Ml
0∈R
fl
Kollineare Konfigurationen sind (topologisch) interessante Punkte in W .
P
Eine Teilmenge J ⊆ {1, . . . , n} heißt kurz (beziehungsweise lang), falls j∈J lj <
P
i6=j lj (beziehungsweise . . . > . . .) gilt, andernfalls heiße sie ausgewogen. J ist
genau dann ausgewogen, wenn sein Komplement J c ausgewogen ist. Es existiert
genau dann ein ausgewogenes J , wenn l nicht generisch ist.
Ist J lang oder ausgewogen, so sei pJ = [ϑ1 , . . . , ϑn ] ∈ W mit ϑi = 1 für i ∈ J und
ϑi = −1 sonst. Insbesondere gilt pJ = pJ c für ausgewogenes J .
Lemma
Die kritischen Punkte von fl : W \ Ml → R sind genau die Konfigurationen pJ für
lange Teilmengen J . Jeder solche Punkt ist nicht-entartet und hat den Morse-Index
n − | J |.
Bevor wir mit dem eigentliche Beweis beginnen erinnern wir uns noch zunächst an
die Vorlesung vom letzten Semester. Die Hessesche ist gegeben durch Hf = ∇2 f
für ein f ∈ C ∞ (M ) und es gilt (ACHTUNG, stimmt nicht mit Kapitel 9.1 der alten
VL überein!)
Hf (X, Y ) = X(df (Y )) − df (∇X f ) = X(Y (f )) − (∇X f )(f )
= [X, Y ](f ) + Y (Xf ) − (∇X Y − ∇Y X) f − ∇Y Xf
|
{z
=[X,Y ]f
}
= Y (Xf ) − ∇Y Xf = Hf (Y, X)
Hf ist im Allgemeinen nicht C ∞ -linear, aber in kritischen Punkten von f : Sei Xp ∈
Tp M , setze fort zu Vektorfeldern X und X̃ auf M . Dann gilt
Hf (X̃, Y )|p = X̃p (Y f ) − (∇X̃p Y )f = Xp (Y f ) − df |p (∇X̃p Y ) = Xp (Y f ).
| {z }
=0
C ∞ -linear
In kritischen Punkten ist Hf
und hängt nicht von der Wahl des ZusamP
P
d
i d
menhangs ab. In lokalen Koordinaten sei dann Xp = i≤n ζ i dx
i , Yp =
i≤n η dxi ,
und ζ i , η i konstant. Dann folgt
Hf (Xp , Yp ) = Xp (Y f ) = Xp
X
i≤n
=
X
j≤n
ζi
ηi
∂ ∂xi
∂η i
2
2
X
∂f
i ∂ f i j ∂ f
+
η
=
η
ζ
∂xi ∂xi
∂xi ∂xj
∂xi ∂xj
|{z}
i,j≤n
=0
Für den beweis des Lemmas setzen wir l = (l1 , . . . , ln ) und fl : W \ Ml → R mit
P
[u1 , . . . , un ] 7→ k− li ui k2 . Die kritischen Punkte von fl sind genau die (kollinearen)
P
P
Konfigurationen pJ für lange Teilmengen J ⊆ {1, . . . , n} ( i∈J li > j ∈J
/ lj und
pJ = (u1 , . . . , un ) mit ui = 1 für i ∈ J und ui = −1 sonst). Jeder solche kritische
Punkt pJ ist nicht ausgeartet und hat den Morse-Index n − | J |.
45
l2
l1
l3 l
4
Kapitel 3: „Gestänge“ (Linkages)
Beweis (vom Lemma)
Wir betrachten die Abbildung
f
l
fl : T n W −
→
R
(u1 , . . . , un ) 7→ −k
X
li ui k2
und setzen ui = eiϑi = (cos ϑi , sin ϑi ). Dann gilt
X
li cos ϑi )2 − (
X
X
li2 cos2 ϑi + 2
X
fl (u) = − (
= −(
X
li2 sin2 ϑi + 2
X
X
li lj sin ϑi sin ϑj )
i<j
i≤n
= −(
li lj cos ϑi cos ϑj )
i <j
i≤n
−(
li sin ϑi )2
li2 (cos2 ϑi + sin2 ϑi )) − 2
X
li lj (cos ϑi cos ϑj + sin ϑi sin ϑj )
i<j
|
{z
=cos(ϑi −ϑj )
}
Wie steht es nun um die kritischen Punkte? Es gilt
X
X
∂fl
= −2lk
li sin(ϑi − ϑk ) = −2lk
li (sin ϑi cos ϑk − cos ϑi sin ϑk ) = 0
∂ϑk
i≤n
i≤n
genau dann, wenn
cos ϑk
X
li sin ϑi = sin ϑk
li cos ϑi
i≤n
i≤n
|
X
{z
=:y(u)
}
|
{z
=:x(u)
}
1. Fall: x(u) = y(u) = 0 ⇔ −x2 (u) − y 2 (u) = fl (u) = 0 ⇔ u ∈ Ml
y(u)
∀k ≤ n ⇔ ϑi ∈ {ϑ1 , ϑ1 + π, ϑ1 − π} ⇔ ui = ±uj ∀i, j ⇔ u ist
2. Fall: tan ϑk ≡ x(u)
kollineare Konfiguration
Es sei J ⊆ {1, . . . , n} eine lange Teilmenge, pJ = (u1 , . . . , un ) mit ui = 1 für i ∈ J
P
und ui = −1 für i ∈
/ J . Dann ist LJ = i≤n li ui > 0 und es gilt fl (pJ ) = − L2J .
Die Hessesche von fl im Punkt pJ ist

−2l l cos(ϑ − ϑ )
i j
j
i
=
2l P
∂ϑi ∂ϑj
i
k6=i lk cos(ϑi − ϑk )
|
{z
}
∂ 2 fl
li
.
falls i = k
=ui uk
Es gilt
X
falls i 6= j
lk ui uk = li ui
k6=i
X
lk uk = li ui (LJ −li ui ) =
li2
k6=i
li Li
−1
li
und di =
ui LJ
,
li
also folgt

−l l u u = (l u )(l u )(−1)
1
i j i j
i i
j j
=
l2 (d − 1) = (l u )(l u )(d − 1)
2 ∂ϑi ∂ϑj
i
i i
i i
i
∂ 2 fl
.
Wir setzen nun für drei Matrizen


d1 . . . 0
. .

.
. . ... 
D=
.

0 . . . dn
46


1 ... 1
. .

. . . ... 
A=
.

1 ... 1


l1 u1 . . .
0
 .
.. 
.
.
..
B=
. 
 .

0
. . . ln un
2 Polygonräume
und schreiben dann
1
Hf (pJ ) = B T (D − A)B.
2
Es genügt zu zeigen, dass D − A auf T[pJ ] W nicht ausgeartet mit Signatur n − | J |
ist:
det(D − A) =
Y
di (1 −
i≤n
X 1
j≤n
dj
)
Ohne Einschränkung sei J = {k, k + 1, . . . , n}. Dann gilt ui = 1 und di < 0 für
i < k, dann gilt für die Hauptminoren von Ordnung l < k
det(D − A)ll =
Y
di 1 −
i≤n
X 1 j≤l
|
|
{z
>0
{z
<0
dj
.
}
}
Für l ≥ k gilt
1−
X 1
j≤l
dj
=1−
X
j≤l
= L−1
J
X
X
X
lJ
−1
l
u
= L−1
L
−
=
L
l
u
−
l
u
j
j
i
i
j
j
J
J
J
uj LJ
i≤n
j≤l
j≤l

> 0
li ui
= 0
i>l
| {z }
X
für k ≤ l < n
für l = n
≥0
Es gilt
sign(det(D − A)ll ) =

(−1)l
für l < k
(−1)k−1
für k ≤ l < k
und D − A hat n − | J | negative Eigenwert, n − k = | J | − 1 positive Eigenwerte
und genau einen Eigenwert 0. Da fl invariant unter der SO(2)-Wirkung ist, gilt in
d2
pJ in Richtung der Faser Hfl (pJ , pJ ) = dλ
2 fl (λpJ ) = 0. Damit ist Hfl auf W in
[pJ ] nicht ausgeartet und hat Signatur n − | J |.
2
Satz
P
Ist l = (l1 , . . . , ln ) generisch, das heißt gilt i≤n li ui 6= 0 für alle ui ∈ {1, −1}, so
ist Ml eine kompakte orientierbare (n − 3)-Mannigfaltigkeit ohne Rand.
Beweis
= (−ln2 ) = Ml . Betrachte den „Roboterarm“ mit
Seien l0 = (l1 , . . . , ln−1 ) und fl−1
0
(n − 1) Segmenten und fl0 : W = T n−2 → R. Nach dem obigen Lemma hat fl0 genau
einen kritischen Wert −a2 6= 0, wenn eine kollineare Konfiguration (u1 , . . . , un−1 )
P
P
existiert mit ui ∈ {1, −1}, so dass −a2 = k i≤n li ui k2 = fl0 (u) ⇔ ±a + li ui =
0 ⇔ (l1 , . . . , ln−1 , a) ist nicht generisch.
2
Das heißt −ln2 ist ein regulärer Wert von fl0 und damit ist fl−1
0 (−ln ) = Ml eine
n−2
kompakte orientierbare Mannigfaltigkeit in W ∼
der Kodimension 1.
2
=T
Was ist mit nicht-generischen Längenvektoren? Betrachte die Urbilder von kritischen
Punkten.
47
l2
l1
ln
Kapitel 3: „Gestänge“ (Linkages)
Lemma (Morse-Lemma)
Es sei p ein nicht-entarteter kritischer Punkt von Index k einer glatten Funktion f
auf einer Mannigfaltigkeit M . Dann existieren lokale Koordinaten x = (x1 , . . . , xn )
von M um p mit
f = f (p) − (x1 )2 − . . . − (xk )2 + (xk+1 )2 + . . . + (xn )2
Beweisskizze
Für f (p) = 0 schreibe
f (x) =
Z 1
d(f (tx1 , . . . , txn ))
dt
0
dt =
X
xi
i≤n
Z 1
∂f
0
|
∂xi
(tx)dt
{z
=:gi (x)
}
∂f
(0) = 0
∂xi
wobei analog zu f für ensprechends g̃ij
gi (0) =
gi (x) =
X
xj g̃ij (x)
j≤n
f (x) =
X
xi xj
i,j
g̃ij + g̃ji
2
=
X
xi xj hij
und dementsprechend
Hf (0) = (hij )ij .
„Verbiege“ nun die Koordinaten so, dass gilt






(hij ) = 






−1
..
.











σ
−1
+1
..
σ
.
+1
Lokal hat f um p entlang k Kurven in linear unabhängige Richtungen Maxima und
entsprechend n − k Minima.
f ≡ε
f ≡0
f ≡ −ε
n−k
Rn−k
f ≡ f (p)
p
Rk
und
xi , i ≤ k
k
Allgemein gilt f (q) = c−(x1 )2 −. . .+(xk+1 )2 +. . .+(xn )2 = c− i≤k (xi )2 + i>k (xi )2 ,
und mit x = (x1 , . . . , xk ) und y = (y 1 , . . . , y n−k ) = (xk+1 , . . . , xn ) schreibe f (q) =
c − kxk2 + kyk2 . Es gilt genau dann f (q) = c, wenn kxk = kyk.
P
48
P
2 Polygonräume
Dies ist genau dann der Fall, wenn entweder x(q) = y(q) = 0 gilt, oder ζ ∈ Sk−1 ,
η ∈ Sn−k−1 und r ∈ R>0 existieren, mit x(q) = rζ und y(q) = rη. Es existiert also
eine Umgebung U von p, so dass
k−1 × Sn−k−1 × [0, 1]
f − (c) ∩ U ∼
= C(Sk−1 × Sn−k−1 ) = S
Sk−1 × Sn−k−1 × {0}
und
x(tζ 1 , . . . , tζ k , tη 1 , . . . , tη n−k ) ←[ [ζ, η, t]
(2)
Eine weitere Folgerung des Morse-Lemmas ist, dass nicht-entartete kritische Punkte stets isoliert sind. Eine Teilmenge J ⊂ {1, . . . , n} ist genau dann ausgewogen
P
P
bezüglich eines Längenvektors (l1 , . . . , ln ), das heißt i∈J li = i∈J
/ li , wenn entc
weder I = J oder sein Komplement J = J eine lange Teilmenge in {1, . . . , n − 1}
bezüglich l0 = (l1 , . . . , ln−1 ) ist und fl0 = (pJ ) = −ln2 .
In einer Umgebung eines kritischen Punktes ist fl−0 (−ln2 ) homöomorph zu einem
Kegel über dem Produkt der Spären der Dimensionen
ind(pI ) − 1 = (n − 1) − | J | − 1 = n − | J | − 2
und
(n − 1) − ind(pJ ) − 1 = | J | − 2.
Damit gilt der folgende Satz:
Satz
Ist l = (l1 , . . . , ln ) ein nicht-generischer Längenvektor, so ist Ml kompakt und bis
auf endlich viele Punkte eine (n − 3)-Mannigfaltigkeit. Eine Umgebung jeder dieser
unendlich vielen Singularitäten ist homöomorph zu
C(Sn−| J |−2 × S| J |−2 ),
wobei J eine bezüglich l ausgeartete Teilmenge ist.
Der Diffeomorphietyp von Ml hängt nicht von der Reihenfolge der Längen l1 , . . . , ln
ab, das heißt σ ∈ Sn definiert einen Diffeomorphismus von Ml auf Mσ(l) .
[Ml ,→ Rn ]
Satz (Ferber-Schütz)
Es sei l = (l1 , . . . , ln ) ein geordneter Längenvektor, das heißt l1 ≥ l2 ≥ . . . ≥ ln > 0,
und es bezeichne σk (beziehungsweise µk ) die Anzahl der kurzen (beziehungsweise
ausgewogenen) Teilmengen J ⊆ {1, . . . , n} mit | J | = k + 1 und 1 ∈ J . Dann ist
Hk (Ml ; Z) frei abelsch vom Rang σk + µk + σ(n−3) − k, wobei n − 3 = dim Ml .
Beispiel
Sei l = (3, 2, 2, 1, 1), n = 5 und dim Ml = 2. Es existieren keine ausgewogenen
Teilmengen, das heißt µk = 0.
σ0 = #
σ1 = #
σ2 = #
kurze
J = #{{1}} = 1
kurze
J = #{{1, 4}, {1, 5}} = 2
kurze
J =0
1∈J ,| J |=1
1∈J ,| J |=2
1∈J ,| J |=3
49
Kapitel 3: „Gestänge“ (Linkages)
Damit:
χ(Ml ) =
X
(−1)k βk = (1 + 0 + 0) − (2 + 0 + 2) + (0 + 0 + 1) = 1 − 4 + 1 = −2
| {z }
=2−2g
Also:
Ml =
3 Walkers Vermutung
Welche Invarianten von Ml bestimmen den Längenvektor von l (bis auf geeignete Äquivalenz)? Für l ∈ Rn>0 und t ∈ R>0 gilt Ml ∼
= Mtl . Zur Definition der
geforderten Äquivalenz betrachtet man zunächst Längenvektoren im Inneren A ⊂
P
∆n−1 − {(l1 , . . . , ln ) ∈ Rn≥0 | li = 1} des Standardsimplex.
Weiter zerlegt man A wie folgt in Teilmengen niedrigerer Dimension. Für jedes
J ⊆ {1, . . . , n} definiert
X
li =
i∈J
X
li
i∈J
/
eine Hyperebene HJ . Es bezeichnen A(k) ⊂ A die Menge der Längenvektoren l,
welche in mindestens (n − 1) − k solcher Hyperebenen HJ enthalten sind, das heißt
A(0) ⊂ A(1) ⊂ A(2) ⊂ . . . ⊂ A(n−1) ⊂= A.
Ein k-Stratum ist eine Zusammenhangskomponente von A(k) \ A(k−1) . Zwei Längenvektoren liegen in demselben Stratum, falls sie die gleichen kurzen Teilmengen
besitzen.
x3
H{3} ∩ {x2 = 0}
H{3} ∩ {x1 = 0}
A
x2
A
x1
H{3} =
{x3
=
x1
+
x2 }
Maximale Strata, Zusammenhangskomponenten von A(n−1) \ A(n−2) , heißen Kammern. Betrachte die Involution (Spiegelung an der x-Achse)
τ : Ml → Ml
[u1 , . . . , un ] 7→ [u1 , . . . , un ]
Ist n ein Fixpunkt von τ , so gilt ui ∈ R, ui = ±1 für alle i ≤ n, und somit ist jeder
Fixpunkt eine kollineare Konfiguration. Insbesondere besitzt τ für generische l keine
Fixpunkte.
Satz (Hausmann, Rodriguez ’04)
Falls l und l0 in denselben Straten liegen, so sind Ml und Ml0 τ -äquivariant diffeomorph.
50
3 Walkers Vermutung
Walkers Vermutung
Es seien l, l0 ∈ A generische Längenvektoren. Falls die ganzzahligen Kohomologieringe von Ml und Ml0 graduiert isomorph sind, so existiert ein σ ∈ Sn so, dass l und
σ(l0 ) in derselben Kammer liegen.
Satz (Faber, Hausmann, Schütz ’07)
Es seien l, l0 ∈ A geoordnete Längenvektoren. Falls dann ein Isomorphismus geraduierter Ringe von H ∗ (Ml ; Z) nach H ∗ (Ml0 ; Z) existiert, welcher mit τ ∗ kommutiert,
so liegen l und l0 in demselben Stratum. Insbesondere sind dann Ml und Ml0 τ äquivalent diffeomorph.
Betrachte den Modulraum Nl der geschlossenen Polygone in R3 mit Kantenlängen
l1 , . . . , ln , das heißt
2
2
Nl = {(u1 , . . . , un ) ∈ S × . . . × S |
P
li ui = 0}
SO(3)
Hier lässt sich zeigen, dass für generische l Nl eine Mannigfaltigkeit der Dimension
2(n − 3) ist.
Satz (Faber, Hausmann, Schütz ’07)
Es sei n 6= 4 und es seien l, l0 ∈ A generische geordnete Längenvektoren. Falls
H ∗ (Ml ; Z) und H ∗ (Ml0 ; Z) isomorph (siehe oben) sind, so liegen l und l0 in derselben
Kammer.
Für n = 4 ist die Aussage falsch: Die Längenvektoren l = (2, 1, 1, 1) und l0 =
(2, 2, 2, 1) liegen in unterschiedlichen Kammern. Es gilt
∼ S0
Ml =
˙ 1
Ml 0 ∼
= S1 ∪S
Nl ∼
= S2 ∼
= Nl0
Ein Längenvektor heißt normal, falls gilt
\
J =
6 ∅.
| J |=3
lang und ausgew.
Eine Kammer heißt normal, wenn sie einen normalen Längenvektor enthält; damit
sind alle darin normal.
Satz (Faber, Hausmann, Schütz ’07)
Es seien l und l0 geordnete Längenvektoren und es gäbe einen Isomorphismus H ∗ (Ml ; Z) →
H ∗ (Ml0 ; Z). Falls l normal ist, so ist l0 normal und l und l0 liegen in denselben Straten.
Dieser Satz liefert uns
1) Die Anzahl der Sn -Bahnen von normalen Kammern ist höchstens so groß wie
die Anzahl der Diffeomorphie Typen von Ml für generische l. Diese Anzahl
wiederum ist höchstens so groß wie die Anzahl der Sn -Bahnen von Kammern.
Diffeom.-Typen
Sn -Bahnen
Sn -Bahnen
# norm.
≤ # von
Ml ,l generisch ≤ # v. Kammern
Kammern
2) Die Anzahl der Sn -Bahnen von normalen Strata ist höchstens so groß wie die
Anzahl der Diffeomorphie Typen von Ml . Diese Anzahl wiederum ist höchstens
so groß wie die Anzahl der Sn -Bahnen von Strata.
Sn -Bahnen
n -Bahnen
# norm.
≤ # Diffeom.-Typen
≤ # Sv.
von Ml
Strata
Strata
51
Kapitel 3: „Gestänge“ (Linkages)
Für große n existieren wenige nicht-normale Strata: Es sei N n ⊆ A(n−1) die Vereinigung aller normalen Strata. Dann gilt
vol(A(n−1) \ N n )
n6
.
≤
2n
vol(A(n−1) )
52
Kapitel 4
Kinematik
z0
y0
z
b
y
x0
x
Bewegungen und Zustände eines (idealisierten) Roboterarmes werden durch abstandserhaltende Transformationen, das heißt Isometrien des R3 , beschrieben. Jede
solche Transformation ist von der Gestalt
R3 3 x 7→ Ax + b
mit A ∈ O(3) und b ∈ R3 , wobei O(3) = {A ∈ R3×3 | AT A = idR3 } die Menge der skalarprodukterhaltenden linearen Abbildungen bezeichnet, die orthogonale
Gruppe. Die Hintereinanderausführung
A0 (Ax + b) + b0 = A0 Ax + A0 b + b0
ist wieder eine Isometrie des R3 . Die Gruppe E(3) der euklidischen Bewegungen ist
das semidirekte Produkt E(3) = O(3) × R3 mit der Multiplikation
(A0 , b0 )(A, b) = (AA0 , A0 b + b0 ).
Die orthogonale Gruppe O(3) besitzt zwei Zusammenhangskomponenten, die orientierungserhaltenden Drehungen mit Determinante 1, also die Spezielle Orthogonale
Gruppe oder Drehgruppe SO(3), und die (Dreh-)Spiegelungen. Da mechanisch keine
Spiegelung realisierbar ist, betrachtet man nur die orientierungserhaltenden euklidischen Bewegungen SE(3) = SO(3) × R.
Zur Vereinfachung der Notation betrachtet man die 4-dimensional Darstellung
(A, b) 7→
SE(3) ,→ GL4 (R)
A b
0 1
!
.
Tatsächlich gilt
A0 b0
0 1
!
A b
0 1
!
=
AA0 A0 b + b0
0
1
!
53
Kapitel 4: Kinematik
mit Inversem
A b
0 1
!−1
AT
0
=
!
−AT b
1
.
Nach einem Satz von Chasles (1832):
z
y
v
u
s
x
Jede euklidische Bewegung kann als „Schraubbewegung“ aufgefasst werden: Für alle
A b ∈ SE(3) existieren eine Richtung v ∈ S2 ⊂ R3 , ein Drehwinkel ϑ, eine Steigung
0 1
s ∈ R und ein Translationsvektor u ∈ R3 .
A b
0 1
!
=
id u
0 1
!
R(ϑ, v)
0
|
ϑ
2π sv
!
1
{z
id −u
0
1
!
=
R
0
ϑ
2π sv
+ (id −R)u
1
!
}
„Schraube“ mit Achse R·v und Steigung s
Bestimmte Roboterarme, beziehungsweise Teile davon, können im Allgemeinen nur
bestimmte Bewebungen ausführen, zum Beispiel lässt ein Drehgelenk keine translationen aus SE(3) zu. Der Konfigurationsraum dieses Drehgelenkes ist anschaulich
S1 = SO(2) < SE(3). Es stellt sich also die Frag nach den Untergruppen von SE(3):
Ist G eine Untergruppe von SE(3) = SO(3)×R3 , so ist auch G∩R3 = ({1}×R3 ) eine
Untergruppe von R3 , also 0, R, R2 , R3 , r Z, r Z × R, r Z × R2 , r Z ×s Z, r Z ×s Z × R
und r Z ×s Z ×t Z. Wegen
A b
0 1
!
id t
0 1
!
AT
0
−AT t
1
!
=
id A(−AT b + t) + b
0
1
!
=
id At
0 1
!
„∈“ R3
ist R3 ein Normalteiler in SE(3), das heißt die Projektion SE(3) SE(3) R3 ∼
= SO(3)
ist eine Gruppenhomomorphismus und jede Untergruppe G < SE(3) projeziert auf
eine Untergruppe in SO(3), also SO(3), SO(2) oder {1}. Welche „Bausteine“ ergeben
Untergruppen von SE(3)? Genau jene, für welche der „Faktor“ in R3 normal in der
Untergruppe liegt.
G 3 =
∼ SO(3):
• G ∩ R3 = {0}
R
• G ∩ R3 = R3 , denn SO(3) ist transitiv auf S 2 .
G 3∼
• G ∩ R3 = {0} ⇒ G ∼
= SO(2)
R = SO(2):
3
3
3
∼
• G ∩ R = R , G = SO(2) × R = SE(2) × R
• G ∩ R2 = R3 , G ∼
= SO(2) × R2 = SE(2)
• G ∩ R = R3 , G ∼
= SO(2) × R
3
• G ∩ R = sZ


1
0




 0 cos ϑ
G= 
 0 sin ϑ






0
54
0
0
− sin ϑ
cos ϑ
0
ϑ
2π s
0
0
1






 = Hs ∼
=R





1 Vorwärtstransformation
„Schraube“ durch die x-Achse mit Steigung s ∈ R. Alle diese Hs sind
nicht zu R ,→ SE(3) konjugiert.
• G ∩ R3 = s Z × R2 ⇒ G = Hs × R2
Reuleux-Paare (1875)
Bewegungen, welche durch das gegeneinander Verschieben oder Verdrehen zweier
gleicher Flächen(-stücke) im R3 entstehen. Diese entsprechen den Orbiten von einund zweidimensionalen Untergruppen von SE(3).
SO(3)
SE(2)
Ebene
Sphäre
Rotationsfäche (Drehgelenk)
Zylinder
SO(2)
Translationsfläche


1
0




 0 cos ϑ
Hs = 
 0 sin ϑ






Helicoid
0
SO(2) × R
0
0
− sin ϑ
cos ϑ
0
ϑ
2π s
0
0
1
R












1 Vorwärtstransformation
Wie berechnet man zu gegebenen Winkeln, beziehungsweise Translationen, die Endpositionen eines Roboters? Man kann sich diese Frage etwa am Puma (Programmable Universal Machine for Assembly) veranschaulichen:
ϑ3
ϑ6
ϑ5
ϑ2
ϑ4
’72 Scheinmann, @Standford
ϑ1
Jedes Gelenk bestimmt eine Ein-Paramter-Untergruppe in SE(3), ϑ 7→ Ai (ϑ), wobei
Ai (ϑ) eine Schraube in obigem Sinne ist, zum Beispiel

Ai (ϑ) =
id u
0 1
!





1
0
0

0 cos ϑ − sin ϑ 0 


0 sin ϑ cos ϑ

0
1
id −u
0
1
!
55
Kapitel 4: Kinematik
oder
Ai (ϑ) =
ϑs
2π
·v
1
id
0
!
für eine Translation in Richtung v. Nach Wahl einer Ausgangsposition des Roboters,
welche den Winkeln ϑ1 = ϑ2 = . . . = ϑk = 0 enstpricht, erhält man die Endposition,
beziehungsweise die Gestalt, durch Anwenden der Transformation ϑ = (ϑ1 , . . . , ϑk ).
Tk → SE(3)
K(ϑ) = A1 (ϑ1 )A2 (ϑ2 ) . . . Ak (ϑk )
Es bleiben immer noch einige Fragen offen:
• Geschwindigkeiten, Beschleunigungen, etc.
• Effizienz
• Umkehrbarkeit der Abbildung
• Geometrie, insbesondere in singulären Punkten
2 Linarisierung (d.h. Tangentialräume)
Die Geschwindigkeit eines Werkzeugs ist gegeben durch die erste Ableitung (nach
der Zeit) des Positionvektors p(t) des Roboterarmes. Es gilt p(t) = K(ϑt )p0 . Da jede
Gestalt durch eine Transformation g = K(ϑ) beschrieben ist, genügt es, die durch
Wege t 7→ gt (gp0 ), mit g0 = id, zu beschreiben. Dann gilt
ṗ(t) = ġt (gp0 ).
Die Gruppe SE(3) = so(3) × R3 ist eine Lie-Gruppe, das heißt eine Glatte Mannigfaltigkeit und die Gruppenoperationen sind glatt bezüglich dieser differenzierbaren
Struktur.
Als Untermannigfaltigkeit von GL(3) ist SO(3) durch die Gleichung AT A = id bestimmt. Ist gt = A(t) ein glatter Weg durch id ∈ SO(3), so gilt
0=
d d T
id
=
A(t)
A(t)
= A0 (0)T A(0) + A(0)T A0 (0) = A0 (0)T + A0 (0).
| {z } | {z }
dt t=0
dt t=0
=id
=id
Also gilt A0 (0) = −A0 (0)T , das heißt der Tangentialraum in 1 von SO(3), T1 SO(3) =
SO(3), besteht aus schiefsymmetrischen Matrizen. Ist gt = A0t b1t ein glatter Weg
in SE(3) mit g0 = idR4 , das heißt A0 = id, b0 = 0, dann gilt
g00
A00 b00
0 0
=
!
=
Ω v
0 0
!
,
wobei


0
−ωz ωy


Ω =  ωz
0
−ωx 
−ωy ωx
0
eine schiefe Matrix ist und v ∈ R3 . Für einen durch xt = gt · x0 parametrisierten
Weg in R3 gilt dann
ẋ0 = Ωx0 + v = ω × x0 + v,
56
3 Adjungierte Darstellung
wobei ω = (ωx , ωy , ωz )T . Ist gt eine Schraubbewegung, das heißt existieren u, v ∈ R3
und s ∈ R mit
gt =
R(ϑt , v)
0
ϑt s
2π v
+ (id −R(ϑt , v))
1
!
,
so gilt


0
−ωz ωy


(R(ϑt , v)) =  ωz
0
−ωx 
t=0
−ωy ωx
0
ϑt s
d s
v=
v + (id ·Rt )u = ϑ00 ·
v − Ωu
dt t=0 2π
2π
s
s
ẋ0 = Ωx0 + ϑ00 v − Ωu = ωx(x0 − u) + ϑ00 v
|
{z
} | {z
2π
2π }
d Ω=
dt Rotationsgeschwindigkeit „Vortrieb“
der Schraube
wobei ω die Winkelgeschwindigkeit ist.
xt
v
ẋ0
x0
ω × (x0 − u)
u
v
s
ϑ0 2π
v
(x0 − u)
3 Adjungierte Darstellung
Im Allgemeinen ist
Ad : G → Aut(g)
∼ g → Te G = g.
Ad(g) : (h 7→ ghg −1 )∗e : Te G =
Für die Gruppe SO(3), beziehungsweise die Lie-Algebra so(3), ist die Konjugation
von Metriken gegeben durch
Ω0 = Ad(R)Ω = RΩRT .
Für SO(3) existiert eine Orthonormalbasis r1 , r2 , r3 von R3 mit RT = (r1 |r2 |r3 ). Ist
dann


0
−ωz ωy


Ω =  ωz
0
−ωx  = ω × (·),
−ωy ωx
0
so gilt
Ω0 = RΩRT = R(ω × r1 |ω × r2 |ω × r3 )




0
hr1 , ω × r2 i hr1 , ω × r3 i
0
−hr3 , ωi hr2 , ωi




= hr2 , ω × r1 i
0
hr2 , ω × r3 i = . . . =  hr3 , ωi
0
−hr1 , ωi = Rω × (·)
hr3 , ω × r1 i hr3 , ω × r2 i
0
−hr2 , ωi hr1 , ωi
0
57
Kapitel 4: Kinematik
In SE(3) gilt damit
Ω0 v 0
0 0
!
!
R v
0 1
= Ad
!
=
R v
0 1
=
RΩRT
0
Ω v
0 0
Ω v
0 0
!
!
!
=
R v
0 1
RT
0
−RT v
1
!
Rv − RΩRT v
0
Ω v
0 0
!
R v
0 1
!−1
!
Da RΩRT v = (Rω) × v gilt, folgt für


0
−vz vy


V =  vz
0
−vx 
−vy vx
0
mit v = (vx , vy , vz )T für alle x ∈ R3 :
V x = −x × v = v × x,
das heißt
−RΩRT v = −(Rω) × v = V Rω.
Stellt man ein Lie-Algebra-Element
ω0
v
!
= Ad
ΩV
0 0
R v
0 1
!
durch ( ωv ) ∈ R6 dar, so gilt
ω
v
!
R 0
VR R
=
!
ω
v
!
Adjungierte Darstellung der Lie-Algebren so (3) und se (3)
Es gilt
Ad : G → Aut(g)
(g −1 (·)g)∗ = Ad(g)
Ad∗e = ad : g → Der(g)
ad(X)Y = [X, Y ]
Die Lie-Algebra so(3) von SO(3) besteht aus den schiefsymmetrischen Matrizen Ω
wie sie im letzten Abschnitt definiert wurden. Die Matrizen


0 0 0


X = 0 0 −1
0 1 0



bilden eine Basis von SO(3). Nun gilt




0 0 0
0 1 0

 

ad(X)Y = XY − Y X = 1 0 0 − 0 0 0 = Z
0 0 0
0 0 0




0 0 0
0 0 0

 

ad(Y )Z = Y Z − ZY = 0 0 0 − 0 0 1 = X
0 0 0
0 1 0




0 0 1
0 0 0

 

ad(Z)X = ZX − XZ = 0 0 0 − 0 0 0 = Y,
0 0 0
1 0 0
58

0 −1 0


Z = 1 0 0
0 0 0
0 0 1


Y =  0 0 0
−1 0 0
4 Exponentialabbildung
wobei man leicht sieht, dass ad(X)Y = [X, Y ] = −[Y, X] = − ad(Y )X, und entsprechend für die übrigen Matrizen. In der Basis gilt dann


0 0 0


ad(X) = 0 0 −1 = X
0 1 0
ad(Y ) = Y
ad(Z) = Z.
Zu se(3) betrachte die Basis
ωi =



vi = 


X 0
0 0
!
0
0
0
0
0
0
0
0
0
0
0
0
Y
0
ωj =
1
0
0
0









vj = 


0
0
0
0
0
0
0
0
0
0
!
ωk =
0
0
0
0
0
1
0
0









vk = 


Z 0
0 0
!
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0






Wie oben berechnet man mit den Kommutatoren der Basiselementen
ad(ωi ) =
X 0
0 X
ad(vi ) =
0 0
X 0
!
ad(ωj ) =
Y
0
0
Y
ad(vj ) =
0
Y
0
0
!
!
ad(ωk ) =
Z 0
0 Z
ad(vk ) =
0 0
Z 0
!
!
!
in der obigen Basis.
4 Exponentialabbildung
Die gewöhnliche Exponentialabbildung für Matrizen
exp(X) =
∞
X
1
n!
n=0
Xn
stimmt für Matrixgruppen wie SO(3) und SE(3), beziehungsweise ihre Lie-Algebren
so(3) und se(3), mit der Exponentialabbildung des Zusammenhanges welcher durch
Paralleltransport durch die Linksmultiplikation defniert ist, überein.
Bezüglich dieses Zusammenhanges sind die Integralkurven von linksinvarianten Vektorfeldern Geodätische, das heißt gt = exp(tX) löst ġt = gt X. Es sei Ω ∈ so(3) wie
im letzten Abschnitt und ω = (ωx , ωy , ωz )T . Wie berechnet man exp(Ω)? Zerlege Ω
(und id) in orthogonale Idempotente:
Ω3 x = ω × (ω × (ω × x))
= hω, ω × xiω − hω, ωiω × x
= 0 − kωk2 ω × x
= −kωk2 Ωx
Also gilt Ω3 + kωk2 Ω = 0. Setzt man
1
P0 =
(Ω + ikωk id) (Ω − ikωk id)
kωk2
−1
P+ =
(Ω − ikωk id)
2kωk2
−1
P− =
(Ω + ikωk id)
2kωk2
59
Kapitel 4: Kinematik
so gilt
P0 P+ = P0 P− = P+ P− = 0
P0 + P+ + P− = id
P02 = P0 , P+2 = P+ , P−2 = P−
Ω = ikωk(P− − P+ ).
Damit folgt
Ωn = (ikωk)n P− + (−ikωk)n P+
und
exp(Ω) = id +
∞
X
1
n!
n=1
Ωn
= P0 + P− + P+ +
∞
X
1
n!
n=1
((ikωk)n P− + (−ikωk)n P+ )
= P0 + eikωk P− + e−ikωk P+
= ...
1 ikωk
1 −ikωk
e
− eikωk Ω −
e
− e−ikωk − 2 Ω2
2kωk
2kωk
1
1
= id +
sin kωkΩ +
(1 − cos kωk)Ω2 .
kωk
kωk2
= id +
ω
Mit ϑ = kωk und v = kωk
erhält man die sogenannte Rodrigues-Formel für die
Drehung um die Achse R ·v mit dem Winkel ϑ:
R(ϑ, v)x = eϑv x = x + sin ϑ(v × x) + (1 − cos ϑ)v × (v × x)
Analog erhält man in der Darstellung von se(3)
S=
Ω v
0 0
!
eine Gleichung vierten Grades
S 4 + kωk2 S = 0.
Wie oben zerlegt man S und id in Idempotente und ein Nilpotent und erhält
exp(S) = id +
1
1
sin kωkS +
(1 − cos kωk)S 2 .
kωk
kωk2
In bestimmten Fällen lässt sich damit die Kinematik eines Roboters lösen. Zum
Beispiel findet man damit für Roboter mit drei Gelenken (generisch) für einen Ausgangspunkt p0 ∈ R3 und einen Zielpunkt p ∈ R3 Elemente S1 , S2 und S3 in se(3),
so dass
eϑ1 S1 eϑ2 S2 eϑ3 S3
60
p0
1
!
=
p
1
!
5 Clifford Algebren
5 Clifford Algebren
Eine (reelle) Clifford-Algebra ist bestimmt durch die Wahl einer Basis e1 , . . . , en ∈
V ∼
= Rn und die Relationen
• ei ej + ej ei = 0 für i 6= j
• e2i ∈ {0, +1, −1}
Eine Clifford Algebra ist eindeutig bestimmt durch die Anzahlen der Basiselemente,
deren Quadrate 1, −1 oder 0 ergeben. Man schreibt sie dann als Cl(p, q, r)
Beispiel
Die Clifford-Algebra Cl(0, 1, 0) wird erzeugt von e1 und R mit
e21 = −1
(x + ye1 )(z + we1 ) = xz + ywe21 + yze1 + xwe1
= (xz − yw) + (yz + xw)e1
Mit einem Isomorphismus, der die Abbildungen e1 7→ i und 1 7→ 1 enthält ist die
Algebra isomorph zu den komplexen Zahlen, also Cl(0, 1, 0) ∼
=C
Jedes Monom von Erzeugern ei1 , . . . , eik kann als Produkt von Erzeugern ej1 , . . . , ejl
mit j1 < j2 < . . . < jl (für l ≤ k) geschrieben werden. Diese Elemente bilden eine
Vektorraum-Basis von Cl(p, q, r), man erhält eine direkte Zerlegung
Cl(p, q, r) =
n
M
Vk .
k=0
Insbesondere gilt dim Cl(p, q, r) = 2(p+q+r) . Diese Vektorraum-Graduierung hängt
im Allgemeinen von der Wahl der Basis ab, allerdings ist die Zerlegung
Cl(p, q, r) = Cl(p, q, r)− ⊕ Cl(p, q, r)+
in Produkte mit einer ungeraden beziehungsweise geraden Anzahl abhängig von der
Wahl der Basis. Das ist eine Involution von Cl mit ei 7→ e∗i = −ei und (ab)∗ = b∗ a∗ .
Wo ist SO(3) (euklidische Bewegungen)
Betrachte die Clifford-Algebra Cl(0, n, 0). Dann liegt Rn in Cl(0, n, 0) durch

δij =
:i=j
0 : i 6= j
Kronecker-Delta

x1
 . 
 .  7→ x1 e1 + . . . + xn en
 . 
1
hx, yi = −
X
xi y j (−δij )
i,j≤n
xn
=−
1 X i j
x y (ei ej + ej ei )
2 i,j≤n
1
= (xy ∗ + yx∗ )
2
Betrachte die Gruppe
Pin(n) = {g ∈ Cl(0, n, 0) | gg ∗ = 1, (−1)|g| g × g ∈ Rn für alle x ∈ Rn ⊆ Cl}
61
Kapitel 4: Kinematik
Die oben bschriebene Wirkung Pin(n) y R erhält das Skalarprodukt:
1
((−1)|g| gxg ∗ )((−1)|g| gyg)∗ + ((−1)|g| gyg ∗ )((−1)|g| gxg ∗ )∗
2

=
1
(−1)|g| gx(g ∗ g )y ∗ (−1)|g| g ∗ + . . .
|{z}
2
=1
1
=g
(xy ∗ + yx∗ ) g ∗
2
= gg ∗ hx, yi = hx, yi
Damit existiert ein Homomorphismus von Pin(n) nach O(n). Man kann zeigen, dass
dieser surjektiv ist und Z2 := Z 2 Z als Kern hat. Es gilt Pin(n) ∩ Rn = Sn−1 , denn
1
1 = vv ∗ = (vv ∗ + vv ∗ ) = hv, vi = kvk2
2
und man rechnet schnell nach, dass −vwv ∗ ∈ Rn für alle w ∈ Rn . Jedes solche v
wirkt als Spiegelung an der Hyperebene v ⊥ :
(−1)|v| v(λv)v ∗ = −λvvv ∗ = −λv
Ist w ∈ v ⊥ , so gilt
1
0 = hw, vi = (wv ∗ + vw∗ ),
2
also
wv ∗ = −vw∗ = vw
und es folgt
(−1)|v| vwv ∗ = −vvw = v ∗ vw = w.
Fasst man Drehungen in Rn als Verkettung von Spiegelungen auf, so ist klar, dass
die von geraden Elemente erzeugte Untergruppe
Spin(n) = {g ∈ Cl+ (0, n, 0) | gg ∗ = 1 und (−1)|g| gxg ∗ ∈ Rn für alle x ∈ Rn }
gerade die zweifache Überlagerung von SO(n) ist. Wir werden uns nun im Folgenden
auf den Fall n = 3 beschränken. Sei g ∈ Cl+ (0, 3, 0) mit
g = a0 + a1 e2 e3 + a2 e3 e1 + a3 e1 e2
und
g ∗ = a0 + a1 (e2 e3 )∗ + a2 (e3 e1 )∗ + a3 (e1 e2 )∗
= a0 + a1 e∗3 e∗2 + a2 e∗1 e∗3 + a3 e∗2 e∗1
= a0 + a1 (−e3 )(−e2 ) + a1 (−e1 )(−e3 ) + a1 (−e2 )(−e1 )
= a0 − a1 e2 e3 − a2 e3 e1 − a3 e1 e2
und damit
gg ∗ = . . . = a20 + a21 + a22 + a23
und man rechnet leicht nach, dass für alle x ∈ Rn schon (−1)|g| gxg ∗ ∈ Rn gilt,
Danmit gilt
i
j
k
Spin(3) ⊆ S3 ⊆ Cl+ (0, 3, 0) = [e2 e3 , e3 e1 , e1 e2 ] = H
62
5 Clifford Algebren
Beispiel
Die Drehung um den Winkel ϑ um die Achse ek wird definiert durch
g = cos
ϑ
ϑ
+ sin ei ej ,
2
2
wobei k ∈
/ {i, j} für i 6= j gelte. Damit erhält man
ϑ
ϑ
ϑ
ϑ
gek g = cos + sin ei ej ek cos − sin ei ej
2
2
2
2
ϑ
ϑ
ϑ
ϑ
ϑ
ϑ
= cos2 ek + cos sin ei ej ek − cos sin ek ei ej + sin2 ei ej ek ei ej
2
2 2
2
2
2
ϑ
2 ϑ
= cos + sin
ek = ek
2
2
ϑ
ϑ
ϑ
ϑ
gej g ∗ = cos + sin ei ej ek cos − sin ei ej
2
2
2
2
ϑ
ϑ
ϑ
ϑ
ej − 2 cos sin ei
= . . . = cos2 − sin2
2
2
2
2
= cos ϑej − sin ϑei
∗
Betracht Spin(n)×Rn = {„g + t“}. Betrachte Cl(0, n, 1) mit den Erzeugern e1 , . . . , en
mit e2i = −1, sowie e mit e2 = 0. Cl(0, n, 1) enthält mit (x1 , . . . , xn )T 7→ 1 + (x1 e1 +
. . . + xn en )e einen Rn , und die Gruppe
1
Spin(n) × Rn = {(g + tge) ∈ Cl(0, n, 1) | g ∈ Spin(n), t = t1 e1 + . . . + tn en }
2
wirkt durch
1
1
(g + tge)(1 + xe)(g − tge)∗ = . . . = 1 + (gxg ∗ + t)e.
2
2
Das sind unsere gesuchten euklidischen Bewegungen.
Beispiel
Ist h = (g + 21 tge) eine reine Drehung, also t = 0, so gilt
h(1 + xe)h∗ = g(1 + xe)g ∗ = gg ∗ + gxeg ∗ = 1 + (gxg ∗ )e
Die letzte Gleichheit kommt daher, dass g gerade ist. Ist h = (1 + 21 te) reine reine
Translation, so gilt
1
1
1
1
1
(1 + te)(1 + xe)(1 − te)∗ = (1 + te + xe + texe) · (1 − te)∗
2
2
2
2
2
1
1
= (1 + te + xe)(1 − et)
2
2
1
1
1
1
= 1 + te + xe − et − te2 t − xe2 t
2
2
4
2
= 1 + te + xe = 1 + (x + t)e
63
Kapitel 4: Kinematik
Wo ist die „Geometrie“?
Ebenen im R3 sind mit einer Einheitsnormalen n ∈ S2 ⊆ R3 und einem „Abstand“
d gegeben durch
Hn,d = {x ∈ R3 | hn, xi = d}.
Ist (R, v) eine euklidische Bewegung, so gilt
(R, v)Hn,d = {x | d = hn, RT x − RT vi = hRn, xi − hRn, vi} = HRn,d+hRn,vi .
Betrachte Elemente vom Grad 1 in Cl(0, 3, 1), also π = nx e1 + ny e2 + nz e3 + de.
Für n = (nx , xy , xz )T gilt genau dann knk = 1, falls ππ ∗ = 1. Ist h = g + 12 tge eine
euklidische Bewegung, so gilt
∗
1
1
hπh = g + tge (n + de) g − tge = . . .
2
2
1
∗
∗
∗
= gng + d − (gng t + tgng ) e„=“ − hRn, vi.
2
∗
Im Gegensatz zu den vorangegeangen Betrachtungen werden jetzt „geometrische“
Punkte nicht als Grad 1 Elemente in Cl(0, 3, 1) modelliert, sondern wie folgt: Ein
Punkt ist von der Form
p = e1 e2 e3 + xe2 e3 e + ye3 e1 e + ze1 e2 e.
Die ist äquivalent (bis auf Vorzeichen) zu pp∗ = 1. Die Wirkung von Spin(3) × R3
(beziehungsweise SE(3)) ist wieder gegeben durch
1
1
(g + tge)p(g − tge).
2
2
Im R3 ist eine Gerade L durch einen Punkt p ∈ L und eine Richtung v ∈ R3
gegeben. In Cl(0, 3, 1) ist dann die entsprechende Gerade gegeben durch
L
v
v×p
v
L = (vx e2 e3 + vy e3 e1 + vz e1 e2 ) + (ux e1 e + uy e2 e + uz e3 e)
p
mit u = (ux , uy , uz )T = p × v. Dies ist äquvalent zu ll∗ = 1. Die Wirkung ist durch
Konjugation gegeben.
V
Durch die Relation x ∧ y = −y ∧ x für x, y ∈ Rn erhält man die äußere Algebra Rn
über Rn . Diese findet sich wie folgt in der Clifford Algebra wieder: Sind x ∈ Rn und
c ∈ Cl, so sind
1
x ∧ c = (xc + (−1)|c| cx)
2
1
c ∧ x = (cx + (−1)|c| xc).
2
Die R-lineare und assoziative Einbettung ergibt ein (weites) Produkt in Cl. Für
Basiselemente ei , ej ∈ Rn gilt:

0
1
ei ∧ ej = (ei ej − ej ei ) =
−e ∧ e
2
j
i
64
i=j
i 6= i
.
5 Clifford Algebren
Damit erhält Cl die äußere Algebra. Für i 6= j gilt ferner
1
1
ei ∧ ej = (ei ej − ej ei ) = (ei ej + ei ej ) = ei ej .
2
2
Betrachte das äußere Produkt eines Punktes p = e1 e2 e3 + xe2 e3 e + ye3 e1 e + ze1 e2 e
und einer Ebene π = nx e1 + ny e2 + nz e3 + de. Dann gilt
1
π ∧ p = (πp − pπ) = (xnx + yny + znz − d)e1 e2 e3 e.
2
Damit liegt genau dann der Punkt p in der Ebene π, wenn π ∧ p = 0 gilt. Analog
zeigt man, dass eine Gerade l genau dann in einer Ebene π liegt, wenn π ∧ l = 0
gilt. Der Ausdruck l ∧ p verschwindet (formal), da Grad l ∧ p > 4. Ein Punkt p liegt
jedoch genau dann auf einer Geraden l, wenn pl∗ + lp∗ = 0 gilt.
Allgemeiner lässt sich der Schnitt zweier geometrischer Objekte mit Hilfe des äußeren
Produktes charakterisieren: Es seien π1 und π2 zwei Ebenen. Dann ist jedenfalls
π1 ∧ π2 ein Grad 2 Element. Es bleibt zu zigen, dass das eine Gerade definiert, also
die Bedingung ll∗ = 1 erfüllt ist. Es gilt
1
1
(π1 ∧ π2 ) = (π1 π2 + (−1)|π2 | π2 π1 ) = (π1 π2 − π2 π1 ),
2
2
also
1
(π1 ∧ π2 )(π1 ∧ π2 )∗ = (π1 π2 − π2 π1 )(π1 π2 − π2 π1 )∗
4
1
= (π1 π2 − π2 π1 )(π2 π1 − π1 π2 )
4
1
= (π1 π2 π2 π1 + π2 π1 π1 π2 − π2 π1 π2 π1 − π1 π2 π1 π2 )
4
1
= (2 − π2 π1 π2 π1 − π1 π2 π1 π2 )
4
Man rechnet nach, dass sich alle Grad 4 Terme aufheben, und dass keine Grad 1
oder Grad 2 Terme auftreten, da (π1 ∧ π2 )(π1 ∧ π2 )∗ selbstandjungiert ist. Damit ist
l= p
π1 ∧ π2
±(π1 ∧ π2 )(π1 ∧ π2 )∗
eine Gerade. Wegen π1 ∧ (π1 ∧ π2 ) = 0 = π2 ∧ (π1 ∧ π2 ) ist l in π1 und π2 enthalten.
Analog zeigt man, dass sowohl das äußere Produkt p einer Geraden l und einer
Ebene π mit
l∧π
p= p
,
±(l ∧ π)(l ∧ π)∗
als auch das äußere Produkt dreier Ebenen p =
1
(...) π1 ∧ π2 ∧ π3
einen Punkt ergeben.
Anwendung
Die inverse Kinematik eine Roboters mit sechse Gelenken ist lösbar, falls drei aufeinanderfolgende Drehachsen entweder einen gemeinsamen Schnittpunkt haben (Piper
1968) oder parallel sind (Duffy 1980). Die inverse Kinematik ist gegeben durch
k(ϑ) = a1 (ϑ1 )a2 (ϑ2 ) . . . a6 (ϑ6 ),
65
Kapitel 4: Kinematik
wobei jedes Drehgelenk durch den Drehwinkel ϑi eines Elementes
ai (ϑi ) = cos
ϑi
ϑi
+ sin li
2
2
parametrisiert wird.
Beweisskizze
Angenommen die Achsen l2 , l3 und l4 seien parallel. Dann ist eine Ebene π orthogonal
zu den Richtungsvektoren aller drei Geraden l2 , l3 und l4 und invariant unter a2 ,
a3 und a4 , das heißt π = a2 a3 a4 πa∗4 a∗3 a∗2 . Stellt man die direkte Kinematik um, so
folgt a∗1 ka∗6 a∗5 = a2 a3 a4 , und mit der obigen Gleichung π = a∗1 ka∗6 a∗5 πa5 a6 k ∗ a1 . Es
gilt also die folgenden Gleichungen zu lösen:
k ∗ a1 πa∗1 k = a∗6 a∗5 πa5 a6
(1)
| {z }
a2 a3 a4 =
=π 0
∗
∗ ∗
a1 ka6 a5 =
k0
(2)
Lösungen zu (2) lassen sich auf die klassische Art finden. Zu (1), der Schnittpunkt
l6 ∧ (a∗5 πa5 ) ist invariant unter der Drehung um l6 . Damit gilt
l6 ∧ (k ∗ a1 πa∗1 k) = l6 ∧ (a∗6 a∗5 πa5 a6 ) = l6 ∧ (a∗5 πa5 ).
Dies liefert Lösungen für sin ϑ1 , cos ϑ1 , sin ϑ5 , cos ϑ5 , beziehungsweise für ϑ1 und ϑ5 .
Damit erhält man direkt eine Lösung für ϑ6 durch (1).
(2)
66
Stichwortverzeichnis
Arbeitsbereich, 43
ausgewogen, 45
ausgewogene Teilmenge, 49
(BC), 18
CAT(κ)-Ungleichung, 8
Clifford-Algebra, 61
Diagonale
verallgemeinerte, 29
Dreieck
geodatisches, 8
(EBC), 21
Ecke, 30
essentielle, 30
freie, 30
Erzeuger, 40
kommumtativer, 41
zulässiger, 41
Fahnenkomplex, 39
generisch, 47
Geodätische
minimierende, 7
gerümmt
nicht-positiv, 9
Gerade, 64
Gestalt, 56
Grad
einer Ecke, 30
Graph, 30
Greedy, 12
Kante, 30
Orientierung, 30
Konfigurationsraum, 29, 43
ungeordneter, 29
konvex, 10
kurz, 45
Längenvektor, 44
generischer, 44
normaler, 51
lang, 45
Link, 39
Lion and Man, 15
lokal rekonfigurierbares System, 41
äquivalentes, 41
Metrik
innere, 7
Mκ -Polyederkomplex, 36
Planes, 13
Puma
Puma, 55
Punkt, 64
Vergleichs-, 8
Randabbildung, 30
Raum
R-geodätischer, 7
CAT(κ)-, 9
geodätischer, 7
Längen-, 7
Rodrigues-Formel, 60
Rotating Spheres, 18
Höhenfunktion, 44
Hessesche, 45
Spheres, 15
Stratum, 50
k-Kette, 37
Kammer, 50
normale, 51
Totalkrümmung, 23
Umfang, 24
67
STICHWORTVERZEICHNIS
vollständig
geodätisch, 8
Weg
rektifizierbarer, 7
Wirkung, 41
Zopfgruppe, 29
Zusatandskomplex, 41
Zustand, 40
68

Einstieg: (Umkehrfunktion) Anna behauptet: „Wie am Einheitskreis

¨Ubungen zu Mathematik II für Montag, 2. Mai 2016

Blatt V5 - Fachbereich Mathematik

¨Ubungen – Blatt 6∗

10 Ableitungen von Nichtpolynomen

¨Ubungen zu Mathematik II für Dienstag, 3. Mai 2016

Übung 10 - Institut für Mathematik

Wichtige Werte von Sinus und Kosinus

Kurve in Parameterform x(t)

6.1 Für ˜f(z) = f(−z) gilt ˜f ′(z) = −f(−z) und daher für 0