Über was für einen Wettbewerb es ist und wie wir es geschafft haben, ihn zu gewinnen (und mehr als 2000 Lösungen aus 51 Ländern wurden zum Wettbewerb geschickt) - lesen Sie unter dem Schnitt.
unser Team
Das JBR_HSE-Team bestand aus fünf Mitgliedern: Konstantin Makhnev (Studium im 4. Jahr des Bachelor-Studiengangs " Angewandte Mathematik und Informatik ") Oleg Svidchenko und Vladimir Egorov (beide studieren im Masterstudiengang " Programmierung und Datenanalyse "), Doktorand Dmitry Ivanov und Leiter des Zentrums für Analyse Daten und maschinelles Lernen NRU HSE - St. Petersburg Alexey Shpilman. Alle außer Konstantin arbeiten auch im Labor für Agentensysteme und Reinforcement Learning bei JetBrains Research - daher der Name des Teams. Während der Teilnahme am Wettbewerb trainierte Kostya im selben Labor.
NeurIPS 2020: Flatland - was ist das?
Flatland ist ein Wettbewerb, der vom 10. Juli bis 15. November auf der AIcrowd- Plattform stattfand und von der renommierten internationalen Konferenz NeurIPS unterstützt wurde . Ziel des Wettbewerbs ist es, einen Algorithmus zu entwickeln, mit dem der Schienenverkehr so gut wie möglich gesteuert werden kann. Eine wichtige Einschränkung bestand darin, dass Entscheidungen in einer begrenzten Zeit (5 Sekunden pro Schritt des Simulators) getroffen werden mussten, was es unmöglich machte, einfach die optimalen Aktionen auszuwählen.
NeurIPS 2020: Flatland hatte zwei Richtungen: Allgemeines und Reinforcement Learning (RL). Der erste Bereich war offen für Entscheidungen und der zweite nur für diejenigen, die verstärktes Lernen nutzen.
Die Organisatoren stellten den Teilnehmern einen Flatland-Simulator zur Verfügung, bei dem es sich um ein zweidimensionales Raster handelt, bei dem jede Zelle ihren eigenen Typ hat: Straße, Kurve, Gabelung oder unpassierbares Gelände. Jeder Zug belegt genau eine Zelle im Netz und hat eine Richtung, in die er sich gerade bewegt. Die Simulation erfolgt Schritt für Schritt. Bei jedem Schritt für jeden Zug müssen Sie festlegen, welche Aktion ausgeführt werden soll: Halten Sie an, fahren Sie auf der linken Spur oder auf der rechten Spur. Da die aktuelle Implementierung keinen vollständigen Schnittpunkt liefert, d.h. Es kommt nicht vor, dass Sie gleichzeitig nach rechts und links vorwärts gehen können, dann wird auch die Aktion „vorwärts gehen“ nicht benötigt. In dem Fall, dass es keine Abbiegungen gibt, sind die zweite und dritte Aktion gleichwertig. Züge können miteinander kollidieren - es stellt sich heraus, dass sie festgefahren sind.Ziel des Wettbewerbs ist es, dass alle Züge so schnell wie möglich ihr Ziel erreichen. Entscheidungen werden anhand der Zeit beurteilt, die die Züge benötigt haben, um das Ziel zu erreichen. Falls der Zug nicht erreicht hat, entspricht seine Zeit der maximalen Simulationszeit.
Lösung: Wie der Agent mit dem Simulator interagiert
Es gab bereits einige Beiträge zu Habré zum Thema Bestärkungslernen, daher werden wir uns nicht im Detail mit den Grundkonzepten befassen. Sagen wir einfach, dass im Fall von Flatland die Simulation der Eisenbahn als Umgebung und der Zug als Agenten fungiert. Es ist wichtig zu beachten, dass diese Umgebung Multi-Agent ist, da viele Züge an der Simulation beteiligt sind.
Bei der Lösung des Problems haben wir den Interaktionsprozess zwischen dem Agenten und dem Simulator erheblich geändert, wodurch wir die Effizienz unseres Algorithmus erheblich steigern konnten. Im Allgemeinen wirken sich solche Änderungen häufig stark auf das Ergebnis aus, erfordern jedoch aufgabenspezifisches Wissen.
Eine der wichtigsten Änderungen war, dass wir beschlossen haben, dem Agenten keine Handlungsfreiheit zu geben, wenn er sich nicht in der Nähe der Kreuzung befindet. Somit kann ein Agent Entscheidungen nur treffen, wenn er sich vor einer Gabelung oder an einer Gabelung befindet, und in anderen Fällen bewegt er sich immer auf dem einzig möglichen Weg vorwärts. Dies verkürzt die Dauer der Episode erheblich und erleichtert daher die Aufgabe erheblich. Wir haben auch beschlossen, dass der Agent seine Episode entweder beendet, wenn er das Ziel erreicht oder wenn er in eine Sackgasse gerät und sich nicht bewegen kann (im Simulator wird die Episode in solchen Fällen fortgesetzt). Später haben wir beschlossen, dass die Folgen nicht für alle sofort beginnen sollen. Wir werden Ihnen weiter unten mehr darüber erzählen.
Die Beobachtung für einen Agenten besteht aus zwei Teilen: Features, die einem bestimmten Teil des Pfads zugeordnet sind, und Features, die nicht an einen bestimmten Teil des Pfads gebunden sind. Ein Teil des Weges bedeutet hier einen Abschnitt der Straße, der zwei Gabeln verbindet.
Der erste Teil der Beobachtung kann als Baum dargestellt werden, an dessen Spitze sich Gabeln befinden und an dessen Rändern die Straßen zwischen ihnen liegen. Wir ordnen jeder Kante und jedem Scheitelpunkt, zu dem sie führt, einen Vektor von Merkmalen zu, die für einen bestimmten Abschnitt des Pfads berechnet wurden (z. B. die Länge des Pfads, den Abstand vom Ende der Kante zum Ziel usw.). Wir haben die Baumtiefe festgelegt und damit die Anzahl der Merkmalsvektoren begrenzt, die aus dem ersten Teil der Beobachtung erhalten wurden. Unten sehen Sie ein Beispiel dafür, wie dieser Teil der Beobachtung aufgebaut ist. Farbige Linien repräsentieren Straßenabschnitte, die Kanten im Baum sind.
Der zweite Teil der Beobachtung enthält Zeichen wie die Mindestentfernung zum Ziel, ob sich der Agent an der Kreuzung oder davor befindet, der Agent in den Deadlock geraten ist usw. Es ist auch erwähnenswert, dass jedem Agenten zu Beginn der Episode eine Kennung zugewiesen wird (eine Zufallszahl von 0 bis 1), was für den Rest der Episode bei ihm bleibt und es ihm ermöglicht, besser mit dem Rest der Agenten zu verhandeln. In beiden Teilen der Beobachtung gibt es Anzeichen, die von den Agentenkennungen abhängen.
Es bleibt nur die Belohnungsfunktion des Agenten zu definieren. Nach einiger Auswahl haben wir uns für eine ziemlich einfache entschieden: $ 0.01 \ cdot \ Delta d - 5 \ cdot \ text {is \ _deadlocked} + 10 \ cdot \ text {is \ _succeed} $, d.h. Die Belohnung gibt an, um wie viel sich die Entfernung $ d $ zum Ziel seit der Entscheidung geändert hat. Eine zusätzliche Belohnung, wenn die Episode erfolgreich abgeschlossen wurde, und eine Strafe, wenn sie einen Deadlock erreicht.
PPO-Algorithmus
Es gibt viele Verstärkungslernalgorithmen, die zur Lösung von Multi-Agent-Problemen entwickelt wurden. Wir haben uns jedoch für den PPO - Proximal Policy Optimization- Algorithmus als Basisalgorithmus entschieden, da sein Code zur Implementierung von Multiagent-RL-Algorithmen (z. B. COMA) wiederverwendet werden kann. Später stellte sich jedoch heraus, dass PPO (mit einigen Modifikationen) das Problem selbst gut löst, aber Multi-Agent-Methoden viel schlechter trainiert werden, sodass PPO der Hauptteil unserer endgültigen Lösung blieb.
Der klassische PPO-Algorithmus besteht aus zwei Teilen: dem Schauspieler und dem Kritiker. Der Kritiker nähert sich der Wertfunktion an, und der Akteur lehrt eine randomisierte Richtlinie $ \ pi_ \ theta (a | s) $, die den erwarteten Wert der Gesamtbelohnung maximiert.
Eine der wichtigsten Änderungen, die wir vorgenommen haben, ist das Hinzufügen eines Moduls zur Akteursarchitektur, mit dem der Agent mit Agenten in der Nähe kommunizieren kann. Der Kommunikationsprozess ist ganz einfach aufgebaut: Agenten generieren gleichzeitig Nachrichten und senden sie an alle Züge, neben denen sie sich befinden. Nachdem sie Nachrichten von Nachbarn erhalten haben, kombinieren sie diese durch gewichtete Mittelwertbildung zu einer Nachricht. Ein einfacher Selbstaufmerksamkeitsmechanismus wurde verwendet, um die Gewichte zu bestimmen, mit denen die Nachrichten gemittelt werden. Bei einer solchen Konstruktion des Kommunikationsprozesses besteht keine Notwendigkeit, den Lernprozess irgendwie zu modifizieren, weil Es reicht aus, die Gradienten während der Rückausbreitung des Fehlers einfach durch die Nachrichten laufen zu lassen.
Wir haben uns entschlossen, PPO mit einer kleinen Karte und einer kleinen Anzahl von Agenten zu trainieren, vorausgesetzt, dass der Agent nach dem Training in größeren Umgebungen gut arbeiten kann, da er nur das beobachtet, was sich in seiner Nähe befindet.
Wie entscheiden Sie, welche Züge wann starten sollen?
Nachdem wir versucht hatten, den PPO-Algorithmus einfach anzuwenden, kamen wir schnell zu dem Schluss, dass die meisten Deadlocks genau deshalb auftreten, weil Züge gleichzeitig in Bewegung geraten und sich gegenseitig stören. Wir haben dieses Problem folgendermaßen gelöst: Wir haben damit begonnen, nur wenige Agenten gleichzeitig auszuführen. Als einer der Agenten seine Episode beendet hatte, durfte der andere Agent anfangen, sich zu bewegen. Bei diesem Ansatz ist es wichtig zu verstehen, in welcher Reihenfolge die Züge gestartet werden sollen.
Der erste Ansatz, den wir versuchten, bestand darin, die Agenten zu starten, die ihrem Ziel am nächsten kommen. In einer kleinen Umgebung - auf kurzen Straßen und mit wenigen Agenten - lief es gut genug, in großen Umgebungen jedoch viel schlechter. Daher haben wir beschlossen, diesen Ansatz nur während des Agententrainings zu verwenden, und für die Anwendung (d. H. Das Einreichen beim Testsystem) haben wir einen anderen Algorithmus verwendet. Die Idee dieses Algorithmus ist es, einen Klassifikator zu trainieren, der für jeden Agenten, der sich nicht bewegt hat, bestimmt, ob er das Ende erreicht oder nicht. Wenn dann die Wahrscheinlichkeit, das Ziel erfolgreich zu erreichen, groß genug ist, beginnt der Agent sich zu bewegen, wenn nicht, wartet er, bis die Wahrscheinlichkeit ausreichend wird.
Wettbewerbsergebnisse
Infolgedessen belegte unsere Lösung den ersten Platz in der RL-Strecke und den achten Platz in der Gesamtwertung. Dies bedeutet, dass der Nicht-RL-Ansatz zu diesem Zeitpunkt noch besser ist, aber es zeigt, dass verstärktes Lernen Potenzial hat. Unser Ansatz weist einige Schwachstellen und ungelöste Probleme auf (z. B. schwerwiegende Probleme bei der Skalierbarkeit auf große Umgebungen), sodass wir noch an etwas arbeiten müssen. Jetzt bereiten wir zusammen mit den Organisatoren des Wettbewerbs einen Artikel vor, um ihn an das Wettbewerbsbuch NeurIPS 2020 zu senden.