Evaluation of a Quality Diversity Algorithm Applied to Autonomous Rover Navigation

Die Bibliothek Parameter Space Illumination (PSI) hat das Ziel, die autonome Navigation von Weltraum Rovern zu verbessern. Insbesondere auf schwer zugänglichem Gelände soll die Wegfindung effizienter und sicherer gemacht werden. Um dieses Ziel zu erreichen verwendet PSI eine Unterart der evolutionären Algorithmen, sogenannte Quality-Diversity Algorithmen. Diese haben das besondere Ziel, nicht nur die Qualität einer Lösung zu optimieren, sondern auch verschiedene, hoch qualitative Lösungen zu finden, die später eine Auswahl ermöglichen.
Ein Anwendungsfall eines solchen Algorithmus, der die Inspiraton für PSI geliefert hat, ist das Paper "Robots that can adapt like animals" von Cullie et.al. aus dem Jahr 2015.
Dort haben die Autoren einen Quality-Diversity Algorithmus verwendet um dem Roboter verschiedene mögliche Verhaltensalternativen zur Verfügung zu stellen. Der Roboter konnten aus diesen dann schnell ALternativen testen und auswählen und sich so erfolgreicher an verschiedene Beschädigungen anpassen als mit anderen Methoden.

Die verschiedenen Verhalten werden dabei in einer sogenannten Behavior-Performance Map (BPM) repräsentiert, einer Tabelle, in die alle möglichen Verhalten des Roboters gemeinsam mit ihrer Performance eingetragen werden. Dieser Ansatz wurde auch bei PSI übernommen. Im Ansatz von Cullie et.al. stellen diese Verhalten die Dauer dar, für die verschiedene Beine des Roboters den Boden berühren. In PSI dagegen sind es verschiedene Belegungen für die Parameter des Navigations-Algorithmus (PBs).
PSI ist bereits implementiert und ich habe im Rahmen meiner Bachelorarbeit eine Evaluation dieser Bibliothek durchgeführt und die Performance eines simulierten Roboters mit Verwendung von PSI mit der eines Roboters ohne verglichen.
Um die Bibliothek zu evaluieren habe ich mich dazu entschieden, die im ersten Vortrag bereits vorgestellte Test-Mission noch um einen weiteren Modus zu erweitern, sodass es jetzt einen langen, durch fünf Wegpunkte in Abschnitte aufgeteilten Pfad und drei verschiedene Möglichkeiten für den Roboter gab, diesen zu durchqueren.
Bei allen Möglichkeiten wurde jedes Mal wenn ein neuer Abschnitt erreicht wurde, ein Wert für die Performance des Roboters bestimmt.

Die erste Möglichkeit ist, dass der simulerte Roboter die Daten aus der BPM nicht verwendet und den Pfad mit einer von einem Experten bestimmten PB absolviert. Diese Belegung ändert sich an den Wegpunkten nicht und die Performance jedes Abschnittes wird am folgenden Wegpunkt gespeichert.
Die zweite Möglichkeit ist, dass der simulierte Roboter immer die PB verwendet, die den höchsten Performance-Wert in der BPM hat. Dabei wird an jedem Wegpunkt die Performance der aktuellen PB in der BPM mit der neuen Performance im letzten Abschnitt verrechnet, und der Wert in der BPM aktualisiert. Dann wird wieder die PB mit dem höchsten Performance-Wert verwendet.
Die dritte Möglichkeit ist, dass zusätzlich Informationen über den Kontext der verschiedenen Abschnitte bei den Wegpunkten gespeichert werden. Diese Informationen werden dann verwendet um die BPM zu filtern. Anstelle der besten PB aus der gesamten BPM wird die beste PB genommen, die der Kontext-Information des Wegpunktes entspricht. Abgesehen davon sind Option 2 und 3 identisch.

Alle dieser Optionen wurden während meiner Evaluierung insgesamt je 50 Mal durchgeführt und die Performance Daten gesammelt und visualisiert. Möglichkeit 3 mit den Kontext Informationen schnitt  besser ab, als die anderen beiden.
In diesem Vortrag werde ich die Mission genauer erklären und Beispiele aus der Simulationsumgebung zeigen, ich werde die Ergebnisse präsentieren und näher beschreiben und auf mögliche Fragen eingehen.