Parti-Game Algorithmus

Datum: 02.08.95
42

Autoren:

• Jörg Kollmann joergk
• Axel Lankenau alone

Stichworte:

• Navigation
• Wegplanung
• Adative Grid-World

Die Folien des Vortrags vom 2. August.

Folien:

Folie: Hintergrund

• Navigation zwischen zwei beliebigen Positionen
• Wegplanung im Konfigurationsraum
• Abbildung realer Hindernisse auf Hindernisse im Konfigurationsraum
• Lernt durch adaptive Grid-World und Erfahrungsschatz
• Greedy-Controller
• Konzept der Loser-Zellen

Folie: Ablauf und Verbesserungen

• Bestimmung eines Zielbereichs
• Greedy peilt Ziel an
• Fährt bis Ziel erreicht oder Hindernis
• Evtl. Aufteilung von Zellen und neue Planung
• Anpeilung einer Epsilon-Umgebung des Ziels
• Zellenübergangskosten je nach Wegstrecke

Folie: Klassenhierarchie

(Abbildung: klassen )

Folie: Details

• Lesbarer Code: for(;;) { berechneAlleJwc(*this,part); Zelle& i=lieferZelleAusZustand(*this,s); if(zielErreicht(i)) return true; if(i.entfernung==UNENDLICH) return false; ...
• Listenverwaltung mit Template-Klasse
• Berechnung der JWCs mittels dynamischer Programmierung (Abbildung: dynprog )
• Aufwand quadratisch in der Zellenzahl
• Zur Zeit omnidirektionale Tonne
• Wissensbasis global gespeichert

Folie: Ausblick

• Umstellung auf Rollstuhlobjekt
• Experimentieren mit
  • verschiedenen Controllerstrategien
  • realistischen Räumen
• Vorausschauendes Verhalten
• Optimierungen:
  • Zellteilungsstrategien
  • JWC-Berechnung
  • Lokale Speicherung des Wissens