Offline Bewegungsplanung: AllgemeinerKonfigurationsraum
Elmar Langetepe
University of Bonn
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 1
Kap. 3.2: Allg. Konfigurationsraum
ā¢ Beispiele fur einfach beschreibare Objekte
ā¢ Kreise, Rechtecke, Ellipsen, Projektionen
ā¢ Mittel zur Beschreibung eines Konfigurationsraumes
(x1, x2)|(x1 ā a)2 + (x2 ā b)2 ā¤ r2
r
(a, b)
(x1, x2)|(x1 ā„ a ā§ x1 ā¤ b ā§ x2 ā„ c ā§ x2 ā¤ d
b
d
a
c
X2
X1
(x1, x2)|(ax1 ā b)2 + (cx2 ā d)2 ā¤ r2
x1|āx2 : (ax1 ā b)2 + (cx2 ā d)2 ā¤ r Projektion der Ellipse auf die X1āAchse:
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 2
Definition 3.3: Tarski-Ausdruck (Rekursiv!)
ā¢ Jede polynomiale Ungleichung P (X1, X2, . . . , Xn)<=>
0 mit
Polynom P (X1, X2, . . . , Xn) ā Q[X1, X2, . . . , Xn]
ā¢ Log. Verknupfung zweier TarskiāAusdrucke T1, T2:
Ā¬T1, T1 āØ T2, T1 ā§ T2, T1ā T2ā¢ TarskiāAusdruck T (X), Variable X frei, die Ausdrucke:
āX : T (X) und āX : T (X)
Beispiel: āX : 3X2 < 10 ā§ āY : Ā¬(4XY 2 < 20)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 3
Definition 3.4: Semialgebraische Menge
ā¢ Teilmenge S ā Rn
ā¢ Es ex. TarskiāAusdruck T (X1, . . . , Xn), mit genau den freien
Variablen X1, . . . , Xn
ā¢ S = (x1, . . . , xn) ā IRn|T (x1, . . . , xn) giltā¢ S heiĆt semialgebraisch
ā¢ Beispiel: S = (x, y, z)|āw : w ā 3x2 ā z < 10 āØ w + 4zy2 < 20ā¢ Abgeschlossen bezuglich endl. Vereinigung/Schnitt, Komplement,
Projektion
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 4
Beispiel Beschreibung Cfrei!
ā¢ Starrer 2-dimensionaler Roboter R und polygonale Szene P
ā¢ Hindernis Pi in Dreiecke Di,j zerlegen
ā¢ Di,j durch Ti,j(X,Y ) darstellen!
ā¢ Pi(X1, X2) :ā” Ti,1(X1, X2) āØ Ti,2(X1, X2) āØ . . . āØ Ti,k(X1, X2)
ā¢ H(X1, X2) :ā” Pi(X1, X2) āØ P2(X1, X2) āØ . . . āØ Pl(X1, X2) ,
R(0, 0, 0) durch R(X1, X2)
R
P1
P3
P4
Pi
Di,j
P2
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 5
Dreieck D als Tarski Ausdruck!
ā¢ D = (x1, x2) | āĪ» āĀµ (Ī» ā„ 0 ā§ Āµ ā„ 0 ā§ Ī»+ Āµ ā¤ 1 ā§ (x1, x2) =
Ī»(c, 0) + Āµ(a, b)) ā¢ (x1, x2)|āĪ» āĀµ (Ī» ā„ 0 ā§ Āµ ā„ 0 ā§ Ī»+ Āµ ā¤ 1 ā§ x1 =
Ī»c+ Āµa ā§ x2 = Āµb) ā¢ T1(x1, x2) = āĪ» āĀµ (Ī» ā„ 0 ā§ Āµ ā„ 0 ā§ Ī»+ Āµ ā¤ 1 ā§ x1 =
Ī»c+ Āµa ā§ x2 = Āµb)
X2 =
baācX1 ā bc
aāc
D
a
b
c
X2 =
baX1
X1
X2
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 6
Dreieck D als Tarski Ausdruck!
ā¢ Alternativ: D als Schnitt von Halbebenen
ā¢ D = (x1, x2)|x2 ā„ 0 ā§ x2 ā¤b
ax1 ā§ x2 ā¤
b
aā cx1 ā
bc
aā cļøø ļø·ļø· ļøøT2(x1,x2)
ā¢ T2 quantorenfrei!! Kein Zufall!!
X2 =
baācX1 ā bc
aāc
D
a
b
c
X2 =
baX1
X1
X2
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 7
Drehung und Translation als Tarski Ausdruck!
Hindernisse durch H(X1, X2), Roboter: R(0, 0, 0) durch R(X1, X2)
Translation: Add. Translationsvektors(a1a2
)Rotation um Īø: Anw. Rotationsmatrix:
(cos Īøsin Īø
ā sin Īøcos Īø
)Nicht explizit cos und sin: Matrix:
(S1S2
āS2S1
)mit S2
1 + S22 = 1
Ubergang:(xā²1xā²2
)=
(s1 ās2s2 s1
)(x1x2
)+(a1a2
)Tarski Ausdruck: B(X1, X2, X
ā²1, X
ā²2, A1, A2, S1, S2)
Bedeutung:(xā²1xā²2
)geht aus Startposition
(x1x2
)durch
Translation/Rotation mit(a1a2
)/(s1s2
ās2s1
)hervor
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 8
Beispiel: Konfigurationsraum als Tarski Ausdruck!
ā¢ B(X1, X2, Xā²1, X
ā²2, A1, A2, S1, S2), R(X1, X2), H(X1, X2)
ā¢ Raum der verbotenen Bewegungen: Cverb(A1, A2, S1, S2)
:ā” ā X1, X2, Xā²1, X
ā²2
(R(X1, X2) ā§H(X ā²1, X
ā²2) ā§
B(X1, X2, Xā²1, X
ā²2, A1, A2, S1, S2)
)ā¢ Von Ausgangsposition zu einer Endposition, diese gehort zu
Hindernis
ā¢ Cfrei(A1, A2, S1, S2) :ā” Ā¬Cverb(A1, A2, S1, S2)
ā¢ Raum der verbotenen Bewegungen als semialgebraische Menge
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 9
Bewegungsplanung mit dieser Beschreibung!
ā¢ Jetzt: Entscheidbarkeit spezieller Tarski Ausdrucke
ā¢ Beweistechnik fur unsere Zwecke benutzen
ā¢ Theorie der reellen Zahlen ist entscheidbar
ā¢ Beweistechnik!
ā¢ Zerlegung in Zellen
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 10
Theorie der reellen Zahlen
ā¢ Sei Ī© = T |T ist TarskiāAusdruck ohne freie Variablen ā¢ TH(IR) = T ā Ī©|T gilt uber IR ā¢ Beispiele:
āx (x2 ā¤ 0ā x = 0) ā TH(IR)
āx āy (x ā„ 0ā x = y2) ā TH(IR)
āx (x2 = ā1) /ā TH(IR)
ā¢ Theorem 3.5: TH(IR) ist entscheidbar!
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 11
Theorie der reellen Zahlen
ā¢ Theorem 3.5: TH(IR) ist entscheidbar!
ā¢ Theorem 3.6: Jede semi-algebraische Menge laĆt sich durch
quantorenfreien Tarski-Ausdruck definieren
ā¢ Deshalb Beweistechnik auch fur uns anwendbar
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 12
Quantoren Elimination: Motivation!
ā¢ Ausdruck mit freier Variablen:
Ļ(Z) = āY āX(X2 ā ZX2 ā Y < 0)
ā¢ Wahrheitswert abhangig von Z
ā¢ Ļ(Z) =
TRUE : if Z ā„ 1
FALSE : if Z < 1
ā¢ Ļ(Z) = (Z ā„ 1)
ā¢ Tarski-Ausdruck ohne Quantoren, einfacher!
ā¢ Benutzen!!
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 13
Quantoren Elimination!
Gilt allgemein:
Theorem 3.6: Jede semi-algebraische Menge laĆt sich durch
quantorenfreien Tarski-Ausdruck definieren!
Wichtiger Schritt!
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 14
Zentrales Resultat zum Beweis!
Theorem 3.5: Die Theorie der reellen Zahlen ist entscheidbar!
Hilfsmittel: Algebraische Zerlegung Kn des IRn Def. 3.7
Endl. System Kn disjunkter Teilmengen des IRn fur die gilt:
ā¢ Jede Zelle Cj ā Kn ist semialgebraisch
ā¢ Jede Zelle Cj ā Kn ist homoomorph zu einem IRk, k ā¤ n
ā¢ Kn ist eine disjunkte Zerlegung des IRn: IRn =
mā¢āj=1
Cj
ā¢ Besonderheit: Cj homoomorph zu IR0, algebraischer Punkt
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 15
Beispiel: Algebraische Zerlegung von IR!
ā¢ Endliche Menge von offenen Intervallen und Punkten
ā¢ Punkte homoomorph zu IR0 (algebraische Punkte)
ā¢ Offene Intervalle homoomorph zu IR
ā¢ Disjunkte Zerlegung
(a2, a3)(āā, a1)
X
[a1] (a1, a2) [a2] [a3] (a3,ā)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 16
Algebraische Zerlegung Kn des IRn
ā¢ Def. 3.7: Probefunktion Ļn, Fkt. Ļn : Kn āā IRn, die jeder
Zelle Cj Probepunkt Ļn(Cj) ā Cj zuordnet
ā¢ Beispiel: Zerlegung von IR: Punkt auf Punkt, Intervall auf
Mittelpunkt des Intervalls
ā¢ Def. 3.7: Projektion Ļn, Abbildung
Ļn : IRn āā IRnā1
(X1, . . . , Xn) 7āā (X1, . . . , Xnā1)
ā¢ Projektion einer Menge M ist Projektion der Elemente:
Ļn(M) := y | y = Ļn(x), x āM
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 17
Spezielle algebraische Zerlegung Kn des IRn
Def. 3.8: System (Kn, Ļn) heiĆt Zylindrische Algebraische
Zerlegung (cylindrical algebraic decomposition, CAD, hier: ZAZ) des
IRn, falls
ā¢ Kn algebraische Zerlegung mit Probefkt. Ļnā¢ Fur n > 1 laĆt sich der IRnā1 rekursiv zerlegen.
D.h., es ex. ZAZ (Knā1, Ļnā1) des IRnā1 mit:
ā Probefunktion zu Knā1 ist Projektion der Probefkt. zu Kn:
Ļnā1 : Knā1 āā IRnā1
Ļn(C) 7āā Ļn(Ļn(C))
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 18
ā Zu jeder Zelle Cj ā Kn ex. Zelle C ā²j ā Knā1 mit C ā²j = Ļn(Cj),
(die Projektion einer Zelle in Kn ist Zelle in Knā1)
ā Fur Zellen Ci, Cj ā Kn mit Ļn(Ci) = Ļn(Cj) gilt
Ļn(Ļn(Ci)) = Ļn(Ļn(Cj))
ā¢ Fur n = 1 ist K1 Zerlegung von IR in endliche Menge
algebraischer Zahlen, und (endliche und unendliche) offenen
Intervalle zwischen Zahlen
ā¢ Zylinder uber C ā², alle Zellen C ā Kn: Ļn(C) = C ā²
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 19
Beispiel: Zylindr. algebr. Zerl. K2 des IR2
ā¢ 9 Zellen, 1 Punkt, vier Intervalle, 4 Quadranten
ā¢ Homoomorph zu IR0,IR1,IR2
ā¢ Projektion auf X1-Achse ergibt K1 von IR
ā¢ Zwei Zellen bilden jeweils Zylinder
X1
X2
' R0
' R1
' R2
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 20
Invarianz bezuglich Polynomen: Def. 3.9
ā¢ Zylindrische Algebraische Zerlegung (Kn, Ļn) und Menge von
Polynomen P ā IQ[X1, . . . , Xn]
ā¢ (Kn, Ļn) heiĆt Pāinvariant, falls
āf(X1, . . . , Xn) ā P : āC ā Kn : sign(fā£ā£ā£C
)= const
ā¢ Das gleiche Vorzeichen fur alle Punkte der Zelle
ā¢ Auswertung fur Probestelle reicht
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 21
Beispiel: Invarianz bezuglich Polynomeā¢ P = X2 ā 2X,X2 ā 4X + 3, zwei Parabeln: (K1, Ļ1)
ā¢ K1: (āā, 0), [0, 0], (0, 1), [1, 1], (1, 2), [2, 2], (2, 3), [3, 3], (3,ā)
ā¢ Probefkt: Ļ1): ā1, 0, 12, 1,32, 2,
52, 3, 4
ā¢ Vorzeichen der Polynome ist konstant innerhalb der Zellen
ā¢ Auswertung fur Probestelle reicht
ā¢ Nullstellen von (X2 ā 2X)Ć (X2 ā 4X + 3)
(āā, 0)
[0]
(0, 1)
[1] [2]
Y = X2 ā 4X + 3Y = X2 ā 2X
(3,ā)
[3]
(1, 2) (2, 3)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 22
Idee: Entscheidbarkeit von Tarski-Ausdruckenā¢ Tarski-Ausdruck ohne freie Variable:
āX[(X2 ā 2X ā¤ 0) ā§ (X2 ā 4X + 3 = 0)]ā¢ Polynom-Invariante Zerlegung (K1, Ļ1) der zugeh. Polynomeā¢ Durch die Probepunkte feststellen, ob die Aussage gultig istā¢ Alle Zellen durchgehen, gilt fur Probepunkt 1ā¢ āX und andere Logik, genauso!
(āā, 0)
[0]
(0, 1)
[1] [2]
Y = X2 ā 4X + 3Y = X2 ā 2X
(3,ā)
[3]
(1, 2) (2, 3)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 23
Allgemeines Ergebnis: Theorem 3.10
Gegeben ist eine Menge P von Polynomen. Man kann eine
Pāinvariante zylindrische algebraische Zerlegung effektiv
konstruieren. Die Laufzeit ist polynomiell in Anzahl und Grad der
Polynome in P, doppelt exponentiell in der Anzahl der Dimensionen.
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 24
Anwendung von Theorem 3.10
ā¢ Pāinvariante Zerlegung berechnen, entscheiden ob
Tarski-Ausdruck gultig ist
ā¢ Anhand eines Beispiels: āX āY : T (X,Y )
ā¢ Berechne Tāinvariante ZAZ (K2, Ļ2) des IR2
ā¢ Polynome in X und Y , die in T vorkommen, haben in jeder Zelle
konstantes Vorzeichen
ā¢ (K1, Ļ1) sei die projizierte eindimensionale ZAZ
ā¢ Wollen Folgendes zeigen:
āX āY : T (X,Y ) ist gultig āā fur jede Zelle C ā² ā K1 gibt es eine
Zelle C ā K2 im Zylinder uber C ā² mit T (x, y) ist wahr fur
(x, y) = Ļ2(C)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 25
Bsp: āX āY : T (X,Y )
āX āY : T (X,Y ) ist gultig āā fur jede Zelle C ā² ā K1 gibt es eine
Zelle C ā K2 im Zylinder uber C ā² mit T (x, y) ist wahr fur
(x, y) = Ļ2(C)
Falls das stimmt: Konnen die Gultigkeit durch endlich viele Tests
bestimmen. Probestellen der Zellen verwenden. Jetzt Beweis!
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 26
Bsp: āX āY : T (X,Y )
āX āY : T (X,Y ) ist gultig āā fur jede Zelle C ā² ā K1 gibt es eine
Zelle C ā K2 im Zylinder uber C ā² mit T (x, y) ist wahr fur
(x, y) = Ļ2(C)
ā=āā
ā¢ C ā² ā K1. Betrachte x = Ļ1(Cā²) ā C ā²
ā¢ Nach Vor. ex. y mit T (x, y)
ā¢ Sei C die Zelle uber C ā² mit (x, y) ā Cā¢ Wg. TāInvarianz gilt auch T (x, y) fur (x, y) = Ļ2(C)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 27
Bsp: āX āY : T (X,Y )
āX āY : T (X,Y ) ist gultig āā fur jede Zelle C ā² ā K1 gibt es eine
Zelle C ā K2 im Zylinder uber C ā² mit T (x, y) ist wahr fur
(x, y) = Ļ2(C)
āā=ā
ā¢ Sei x beliebig, C ā² die Zelle in K1 mit x ā C ā²
ā¢ Nach Vor. ex es ein C ā K2 uber C ā² mit T (x, y) fur
(x, y) = Ļ2(C)
ā¢ Es ex ein y mit (x, y) ā Cā¢ wegen TāInvarianz gilt auch T (x, y)
Offline Bewegungsplanung 16.01.17 Allgemeine Bahnplanung cĀ©Elmar Langetepe WS ā1617 28