Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games

In der Welt der künstlichen Intelligenz wird das Treffen von Entscheidungen oft wie ein Glücksspiel behandelt, das auf einem Brett mit perfekt bekannten Regeln gespielt wird. Stellen Sie sich einen Roboter vor, der durch ein Labyrinth navigiert; wenn die Ingenieure genau wissen, wie rutschig der Boden ist und wie sich die Räder des Roboters drehen werden, können sie den perfekten Pfad zum Ausgang berechnen. Dies ist das Standardmodell für viele Entscheidungssysteme. Die reale Welt ist jedoch selten so präzise. Sensoren fallen aus, Materialien verschleißen und Daten sind verrauscht, was bedeutet, dass die genauen Wahrscheinlichkeiten dafür, dass ein Roboter ausrutscht oder ein Auto driftet, niemals wirklich bekannt sind, sondern nur innerhalb eines Bereichs von Möglichkeiten geschätzt werden können. Wenn diese Unsicherheiten hinzukommen, wird das Problem viel schwieriger: Wie plant man einen sicheren Pfad, wenn man sich über das Verhalten des Terrains nicht sicher sein kann? Darüber hinaus geht es in sicherheitskritischen Bereichen wie dem autonomen Fahren oder der medizinischen Robotik nicht nur darum, ein Ziel schnell zu erreichen, sondern darum, zu garantieren, dass das System niemals in einen gefährlichen Zustand gerät oder eine bestimmte logische Sequenz von Ereignissen auf ewig verfolgt.

Forscher am Indian Institute of Technology Bombay und der Nanyang Technological University haben sich dieser schwierigen Schnittstelle von Unsicherheit und strikter logischer Sicherheit gewidmet. Sie konzentrierten sich auf eine Klasse von Problemen, bei denen ein Agent Entscheidungen treffen muss, während er die Welt nur teilweise sieht und wobei die Bewegungsregeln keine festen Zahlen sind, sondern zu einer Menge möglicher Werte gehören. Das Team bewies, dass das Lösen dieser komplexen, unsicheren Entscheidungsprobleme mathematisch identisch mit dem Lösen eines anderen, gut untersuchten Typs von Spielen ist, das zwei gegnerische Spieler mit verborgener Information beinhaltet. Durch die Herstellung dieser wechselseitigen Verbindung konnten sie Jahrzehnte bestehenden Wissens über die Spieltheorie nutzen, um sofort die rechnerische Komplexität beim Lösen dieser unsicheren Robotikprobleme zu bestimmen. Ihre Arbeit zeigt exakt auf, wie schwer es ist, Sicherheit in diesen Szenarien zu garantieren, und zeigt, dass das Problem für einige Arten von logischen Zielen mit bekannten Methoden lösbar ist, während es für andere so komplex ist, dass kein Algorithmus es jemals in einer angemessenen Zeitspanne lösen könnte.

Der Kern ihrer Entdeckung liegt in der Überbrückung zweier unterschiedlicher mathematischer Welten. Auf der einen Seite steht der robuste, teilweise beobachtbare Markov-Entscheidungsprozess (Robust Partially Observable Markov Decision Process), ein Modell, das verwendet wird, um eine Situation zu beschreiben, in der ein Agent, wie etwa ein selbstfahrendes Auto, Handlungen wählen muss, ohne seinen genauen Standort zu kennen und ohne die genaue Wahrscheinlichkeit zu kennen, in einen neuen Zustand überzuge-gehen. Anstelle einer einzelnen Wahrscheinlichkeit operiert das System innerhalb einer „Wolke“ möglicher Wahrscheinlichkeiten. Auf der anderen Seite steht das teilweise beobachtbare stochastische Spiel (Partially Observable Stochastic Game), ein Modell, bei dem zwei Spieler, von denen einer versucht zu gewinnen und der andere versucht, dies zu verhindern, abwechselnd Züge machen, während sie nur begrenzte Informationen über das Spielfeld sehen. Jahrelang wussten Forscher, dass es möglich war, diese beiden Modelle ineinander zu übersetzen, wenn das Ziel lediglich darin bestand, eine Belohnung zu maximieren. Doch wenn sich das Ziel hin zu strikten logischen Regeln verschiebt – wie etwa „niemals einen Fußgänger treffen“ oder „schließlich das Krankenhaus erreichen und dort für immer bleiben“ – wurde die Verbindung unterbrochen. Die neue Studie beweist, dass diese beiden Modelle selbst mit diesen komplexen logischen Regeln immer noch perfekt äquivalent sind.

Um dies zu demonstrieren, bauten die Forscher einen präzisen Translationsmechanismus, der in beide Richtungen funktioniert. Zuer erst zeigten sie, wie man ein robustes Entscheidungsproblem mit unsicheren Wahrscheinlichkeiten in ein Zwei-Spieler-Spiel umwandelt. In diesem neuen Spiel wird der Agent zu einem Spieler, und die Unsicherheit der Welt wird zu einem zweiten, adversen Spieler. Dieser zweite Spieler handelt nicht zufällig; stattdessen wählt er aktiv das Worst-Case-Szenario aus den verfügbaren Optionen aus, um den Agenten zu besiegen. Die Forscher bewiesen, dass wenn der Agent dieses Spiel gegen einen klugen Gegner gewinnen kann, er auch in der ursprünglichen unsicheren Welt erfolgreich sein kann. Überraschenderweise gelang ihnen auch die umgekehrte Translation. Sie zeigten, dass jedes Zwei-Spieler-Spiel mit verborgener Information wieder in ein robustes Entscheidungsproblem umgewandelt werden konnte. Dieser Rückwärtsschritt war technisch schwierig, da der Gegner im Spiel den Zug des Agenten sieht, bevor er handelt, während in dem Entscheidungsproblem die Umgebung ihr Verhalten sofort festlegt. Das Team löste dies durch das Einfügen einer kurzen, unsichtbaren Pause in die Spielstruktur, wodurch der Umgebung effektiv die gleiche Information gegeben wurde, die sie im ursprünglichen Problem hatte. Diese Brücke in beide Richtungen bedeutet, dass jedes computerwissenschaftliche Ergebnis über die Schwierigkeit der Lösung eines Problemtyps automatisch auch für den anderen gilt.

Die Auswirkungen dieser Äquivalenz sind unmittelbar und tiefgreifend für das Verständnis der Grenzen des automatisierten Schließens. Durch die Nutzung dieser Brücke konnten die Forscher die exakte rechnerische Komplexität beim Lösen dieser Probleme für verschiedene Arten von logischen Zielen kartieren. Sie fanden heraus, dass die Probleme für einfache Ziele, wie das Erreichen eines Ziels oder das Vermeiden einer Gefahrenzone, lösbar sind, wenngleich sie eine erhebliche Rechenleistung erfordern, die exponentiell mit der Größe des Systems wächst. Die Studie identifizierte jedoch auch eine harte Grenze. Für bestimmte komplexe logische Zielsetzungen, insbesondere solche, die eine Mischung aus „immer“ und „schließlich“-Bedingungen in einer zweiseitig unsicheren Umgebung beinhalten, wird das Problem unentscheidbar. Das bedeutet, dass kein Computerprogramm, egal wie leistungsstark, jemals eine Antwort für jedes mögliche Szenario garantieren kann. Die Forscher klärten auch die Schwierigkeit für einseitige Unsicherheit auf, bei der nur der Agent blind ist, die Umgebung aber alles sieht, und zeigten, dass diese Fälle im Allgemeinen leichter zu lösen sind als die vollkommen blinden Szenarien.

Diese Arbeit liefert eine vollständige Landschaft dessen, was unter Unsicherheit beim Design sicherer, autonomer Systeme rechnerisch möglich ist. Sie bestätigt, dass wir zwar Algorithmen bauen können, um viele sicherheitskritische Aufgaben zu bewältigen, es aber fundamentale Grenzen gibt, an denen die Kombination aus verborgener Information, adverser Unsicherheit und komplexen logischen Regeln eine Lösung unmöglich macht. Die Studie bietet keinen neuen Algorithmus, um jeden Fall zu lösen, sondern vielmehr eine definitive Karte des Geländes, die Ingenieuren genau sagt, welche Probleme sie lösen können und welche einen völlig anderen Ansatz erfordern. Indem sie bewiesen, dass diese beiden mathematischen Rahmenwerke dasselbe sind, haben die Forscher eine riesige Bibliothek bestehender Werkzeuge und Theorien erschlossen, die es dem Feld ermöglichen, mit einem klaren Verständnis der kommenden Herausforderungen voranzuschreiten.