View
1.669
Download
5
Category
Preview:
DESCRIPTION
Das im Jahr 2007 ins Leben gerufene Oldenburger Robot Soccer Team der Universität Oldenburg verwendet eine auf Potentialfeldern basierende Methode zur Pfadplanung für seine Roboterfußball- mannschaft. Die vorliegende Arbeit befasst sich mit der Verbesserung des bestehenden Pfadplanungs- verfahrens. Dazu wird das bestehende System zunächst evaluiert und bezüglich seiner Eignung be- wertet. Die Ergebnisse dieser Evaluation fließen in den Entwurf für eine verbesserte Pfadplanung ein. Es wird die Implementierung eines auf harmonischen Funktionen basierenden Pfadplaners für die 2D-Simulationsliga beschrieben. Dieser nutzt GPGPU-Techniken zur Konstruktion einer diskreten Repräsentation des Konfigurationsraums unter Verwendung von impliziten Flächen, löst die Laplace- Gleichung auf dem freien Konfigurationsraum mittels des Jacobi-Verfahrens und emuliert Gleitkom- mazahlen mit doppelter Genauigkeit zur Verbesserung der näherungsweisen Lösung der Laplace- Gleichung auf der GPU. Die erzielten Ergebnisse werden abschließend diskutiert.
Citation preview
C A R LV O N
O S S I E T Z K Y
Pfadplanung mitharmonischenPotentialfeldern
Johannes Diemke
Prasentation zur BachelorarbeitSommersemester 2012
Gliederung
1 Problemstellung
2 Grundlagen
3 Anforderungserhebung
4 Evaluation
5 Entwurf und Implementierung
6 Fazit
Johannes Diemke Bachelorarbeit 4. September 2012 2/17
Problemstellung
Motivation
Pfadplanung mit Potentialfeldern in TORF
Nicht vollends zufriedenstellende Ergebnisse
Sichere Navigation ist aber wichtige Kompetenz
Problemstellung
Verbesserung des bestehenden Pfadplaners
Johannes Diemke Bachelorarbeit 4. September 2012 3/17
Pfadplanung
MotivationNavigation eines Spielers zu einer Zielposition
I Positionsverbesserung vor einem Torschuss
AnforderungenI Vermeiden von KollisionenI Kurzer vs. sicherer Pfad
Johannes Diemke Bachelorarbeit 4. September 2012 4/17
Pfadplanung
KonfigurationsraumReduzieren einer Pose auf einen Punkt im KonfigurationsraumFreier Konfigurationsraum:
Cfree = C \⋃
i∈1,...,n
q ∈ C | A(q) ∩ Bi 6= ∅
Freier Pfad τ : [0, 1]→ Cfree , τ(0) = q1, τ(1) = q2
Johannes Diemke Bachelorarbeit 4. September 2012 5/17
Anforderungserhebung
Anforderungen
Vollstandigkeit
Echtzeitfahigkeit
Robustheit bzgl. Ungenauigkeiten
Berucksichtigung der dynamischen Umgebung
Glatte und sichere Pfade
Johannes Diemke Bachelorarbeit 4. September 2012 6/17
Evaluation
Istzustand der PfadplanungVerwendet Potentialfeldmethode
Potentialfeld induziert gerichtete Kraft F = −∇UPotentialfeld als Superposition U = Uatt +
∑ni=1 Urepi
Johannes Diemke Bachelorarbeit 4. September 2012 7/17
Evaluation
BewertungEinfache ImplementierungGute EffizienzBerucksichtigung der Dynamischen UmgebungLimitationen
I Lokale MinimaI OszillationenI Nicht optimale Pfade
Johannes Diemke Bachelorarbeit 4. September 2012 8/17
Entwurf
Harmonische Funktionen
Losungen der Laplace-Gleichung: ∇2φ =∑n
i=1∂2φ∂x2
i= 0
Pfadplanung mit harmonischen Funktionen
Als Dirichlet-Randwertproblem: ∇2φ = 0, φ|∂ΩCB = 1, φ|∂ΩZiel= 0
Numerische Losung mit Finite-Differenzen-Methode
Johannes Diemke Bachelorarbeit 4. September 2012 9/17
Entwurf
Entwurf des neuen Pfadplanungsverfahrens
Basiert auf harmonischen Funktionen
Abgestimmt auf Anforderungen der 2D-Simulationsliga
Implizite Repräsentation desKonfigurationsraums
durch Distanzfunktionen
Diskretisierung desKonfigurationsraums durch
ein regelmäßiges Gitter
Lösung der Laplace-Gleichungdurch ein Splitting-Verfahren
Numerische Differentiationund Navigation
Johannes Diemke Bachelorarbeit 4. September 2012 10/17
Entwurf
Reprasentation des KonfigurationsraumsImplizite Reprasentation durch SDF
CB = p ∈ R2|DCB(p) ≤ 0
Diskretisierung des KonfigurationsraumsApproximation durch regelmaßiges Gitter
PCfree (p) : DCB(p)− 1
2
√∆x2 + ∆y2 > 0
Johannes Diemke Bachelorarbeit 4. September 2012 11/17
Implementierung
ArchitekturAuslagerung performancekritischer Teilschritte auf GPU
Geschwindigkeitszuwachs durch parallele Berechnung
Verwendung von Shader-Programmen
Numerische Differentiationund Navigation
Diskretisierung desKonfigurationsraums durch
ein regelmäßiges Gitter
Lösung der Laplace-Gleichungdurch das Jacobi-Verfahren
Berechnung aufGPUImplizite Repräsentation des
Konfigurationsraumsdurch Distanzfunktionen
Berechnung inClient-Anwendung
Johannes Diemke Bachelorarbeit 4. September 2012 12/17
Implementierung
Reprasentation der Gitterknoten32-Bit-Floating-Point-Texturen
Gitterknoten φi ,j entspricht Texel in 2D-Textur
GL_RGBA32F
32 bit 32 bit 32 bit 32 bit
double-single.high double-single.low boundary-flag
Implementierung des Jacobi-VerfahrensRender-Target Ping-Pong-Technik
Textur A Textur B
Jacobi-Iteration
Jacobi-Iteration
Johannes Diemke Bachelorarbeit 4. September 2012 13/17
Implementierung
Prototyp
Verwendet Java und JOGL 2.0
Intel Core 2 Quad (2,83 GHz) mit GeForce GTX 260
Gitter: 70×40Iterationen: 2000Diskretisierung: 39, 06 · 10−4 msLaplace-Gleichung: 39, 81 ms
Bewertung
Vermeidet Probleme des alten Pfadplaners
Trotz geringer Gitterauflosung glatte Pfade
Hardware in Wettkampfen aktuell nicht verfugbar
Johannes Diemke Bachelorarbeit 4. September 2012 14/17
Implementierung
Video
(Quelle: http://youtu.be/mB6X2p3XROs)
Johannes Diemke Bachelorarbeit 4. September 2012 15/17
Fazit
ZusammenfassungPfadplanung nicht vollends zufriedenstellend
I Lokale MinimaI Oszillationen
Entwurf eines neuen Pfadplaners
Entwicklung eines Prototyps
I Echtzeitfahige Implementierung moglich
Ausblick
Zukunftige Verfugbarkeit von 3D-Beschleunigern zu erwarten
Einsatz von OpenCL
Verwendung von Multigrid Verfahren
Integration in TORF
Johannes Diemke Bachelorarbeit 4. September 2012 16/17
Fragen?
Vielen Dank fur Ihre Aufmerksamkeit
Johannes Diemke Bachelorarbeit 4. September 2012 17/17
Recommended