Um zu verstehen, wie fahrerlose Fahrzeuge durch die Komplexität der Straße navigieren können, verwenden Forscher oft die Spieltheorie – mathematische Modelle, die darstellen, wie sich rationale Agenten strategisch verhalten, um ihre Ziele zu erreichen.
Dejan Milutinovic, Professor für Elektro- und Computertechnik an der UC Santa Cruz, arbeitet seit langem mit Kollegen an der komplexen Teilmenge der Spieltheorie, den so genannten Differenzialspielen, die mit sich bewegenden Spielern zu tun haben. Eines dieser Spiele heißt Wandverfolgungsspiel, ein relativ einfaches Modell für eine Situation, in der ein schneller Verfolger das Ziel hat, einen langsameren Ausweicher zu fangen, der darauf beschränkt ist, sich entlang einer Wand zu bewegen.
Seit dieses Spiel vor fast 60 Jahren erstmals beschrieben wurde, gab es innerhalb des Spiels ein Dilemma – eine Reihe von Stellungen, bei denen man dachte, dass es keine optimale Lösung für das Spiel gibt. Aber jetzt haben Milutinovic und seine Kollegen in einem neuen Artikel bewiesen, der in der Zeitschrift veröffentlicht wurde IEEE-Transaktionen zur automatischen Steuerung dass dieses seit langem bestehende Dilemma nicht wirklich existiert, und führte eine neue Analysemethode ein, die beweist, dass es immer eine deterministische Lösung für das Mauerverfolgungsspiel gibt. Diese Entdeckung öffnet die Tür zur Lösung anderer ähnlicher Herausforderungen, die auf dem Gebiet der Differentialspiele bestehen, und ermöglicht eine bessere Argumentation über autonome Systeme wie fahrerlose Fahrzeuge.
Die Spieltheorie wird verwendet, um über das Verhalten in einer Vielzahl von Bereichen wie Wirtschaft, Politikwissenschaft, Informatik und Ingenieurwesen nachzudenken. Innerhalb der Spieltheorie ist das Nash-Gleichgewicht eines der am häufigsten anerkannten Konzepte. Das Konzept wurde vom Mathematiker John Nash eingeführt und definiert spieloptimale Strategien für alle Spieler im Spiel, um das Spiel mit dem geringsten Bedauern zu beenden. Jeder Spieler, der sich entscheidet, seine optimale Spielstrategie nicht zu spielen, wird am Ende mehr Bedauern haben, daher sind rationale Spieler alle motiviert, ihre Gleichgewichtsstrategie zu spielen.
Dieses Konzept gilt für das Wandverfolgungsspiel – ein klassisches Nash-Gleichgewichtsstrategiepaar für die beiden Spieler, den Verfolger und den Ausweicher, das ihre beste Strategie in fast allen ihren Positionen beschreibt. Es gibt jedoch eine Reihe von Positionen zwischen dem Verfolger und dem Ausweicher, für die die klassische Analyse keine optimalen Spielstrategien liefert und mit der Existenz des Dilemmas endet. Diese Reihe von Positionen ist als singuläre Oberfläche bekannt – und seit Jahren hat die Forschungsgemeinschaft das Dilemma als Tatsache akzeptiert.
Doch das wollten Milutinovic und seine Co-Autoren nicht hinnehmen.
„Das hat uns gestört, weil wir dachten, wenn der Betrüger weiß, dass es eine singuläre Oberfläche gibt, besteht die Gefahr, dass der Betrüger auf die singuläre Oberfläche gehen und sie missbrauchen kann“, sagte Milutinovic. „Der Ausreißer kann Sie dazu zwingen, an die einzigartige Oberfläche zu gehen, wo Sie nicht wissen, wie Sie sich optimal verhalten sollen – und dann wissen wir einfach nicht, welche Auswirkungen das auf viel kompliziertere Spiele hätte.“
Also entwickelten Milutinovic und seine Co-Autoren einen neuen Weg, um das Problem anzugehen, indem sie ein mathematisches Konzept verwendeten, das noch nicht existierte, als das Mauerverfolgungsspiel ursprünglich konzipiert wurde. Durch die Verwendung der Viskositätslösung der Hamilton-Jacobi-Isaacs-Gleichung und die Einführung einer Verlustratenanalyse zur Lösung der singulären Oberfläche konnten sie feststellen, dass eine spieloptimale Lösung unter allen Umständen des Spiels bestimmt werden kann, und das Dilemma lösen.
Die Viskositätslösung partieller Differentialgleichungen ist ein mathematisches Konzept, das bis in die 1980er Jahre nicht existierte und eine einzigartige Argumentation zur Lösung der Hamilton-Jacobi-Isaacs-Gleichung bietet. Es ist mittlerweile allgemein bekannt, dass das Konzept relevant ist für Überlegungen zu optimalen Steuerungs- und Spieltheorieproblemen.
Die Verwendung von Viskositätslösungen, die Funktionen sind, um spieltheoretische Probleme zu lösen, beinhaltet die Verwendung von Kalkül, um die Ableitungen dieser Funktionen zu finden. Es ist relativ einfach, spieloptimale Lösungen zu finden, wenn die einem Spiel zugeordnete Viskositätslösung wohldefinierte Ableitungen hat. Dies ist beim Wall-Pursuit-Spiel nicht der Fall, und dieser Mangel an wohldefinierten Ableitungen schafft das Dilemma.
Wenn ein Dilemma besteht, besteht ein praktischer Ansatz normalerweise darin, dass Spieler zufällig eine der möglichen Aktionen auswählen und Verluste akzeptieren, die sich aus diesen Entscheidungen ergeben. Aber hier liegt der Haken: Wenn es einen Verlust gibt, wird jeder rationale Spieler ihn minimieren wollen.
Um also herauszufinden, wie Spieler ihre Verluste minimieren könnten, analysierten die Autoren die Viskositätslösung der Hamilton-Jacobi-Isaacs-Gleichung um die singuläre Oberfläche herum, wo die Ableitungen nicht wohldefiniert sind. Dann führten sie eine Verlustratenanalyse über diese einzelnen Oberflächenzustände der Gleichung ein. Sie fanden heraus, dass es klar definierte Spielstrategien für ihre Aktionen auf der singulären Oberfläche gibt, wenn jeder Akteur seine Verlustrate minimiert.
Die Autoren fanden heraus, dass diese Minimierung der Verlustrate nicht nur die spieloptimalen Aktionen für die singuläre Oberfläche definiert, sondern auch mit den spieloptimalen Aktionen in jedem möglichen Zustand übereinstimmt, wo die klassische Analyse diese Aktionen auch finden kann.
„Wenn wir die Verlustratenanalyse nehmen und sie an anderer Stelle anwenden, werden die optimalen Aktionen des Spiels aus der klassischen Analyse nicht beeinflusst“, sagte Milutinovic. „Wir nehmen die klassische Theorie und erweitern sie mit der Verlustratenanalyse, sodass überall eine Lösung existiert. Dies ist ein wichtiges Ergebnis, das zeigt, dass die Augmentation nicht nur ein Fix ist, um eine Lösung auf der singulären Oberfläche zu finden, sondern ein grundlegender Beitrag zur Spieltheorie.
Milutinovic und seine Co-Autoren sind daran interessiert, andere spieltheoretische Probleme mit singulären Oberflächen zu untersuchen, wo ihre neue Methode angewendet werden könnte. Das Papier ist auch ein offener Aufruf an die Forschungsgemeinschaft, andere Dilemmata auf ähnliche Weise zu untersuchen.
„Nun stellt sich die Frage, welche Art von anderen Dilemmata können wir lösen?“ sagte Milutinović.
Mehr Informationen:
Dejan Milutinovic et al, Charakterisierung der Verlustrate, die das Dilemma der Wandverfolgungsspiellösung löst, IEEE-Transaktionen zur automatischen Steuerung (2023). DOI: 10.1109/TAC.2021.3137786