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

In de wereld van kunstmatige intelligentie wordt het nemen van beslissingen vaak behandeld als een kansspel dat gespeeld wordt op een bord waarvan de regels perfect bekend zijn. Stel je een robot voor die door een doolhof navigeert; als de ingenieurs precies weten hoe glad de vloer is en hoe de wielen van de robot zullen draaien, kunnen ze het perfecte pad naar de uitgang berekenen. Dit is het standaardmodel voor veel besluitvormingssystemen. De werkelijkheid is echter zelden zo precies. Sensoren falen, materialen slijten en data is ruizig, wat betekent dat de exacte kansen op het uitschieten van een robot of het afwijken van een auto nooit echt bekend zijn, maar slechts geschat worden binnen een reeks mogelijkheden. Wanneer deze onzekerheden aan de mix worden toegevoegd, wordt het probleem veel moeilijker: hoe plan je een veilig pad wanneer je niet zeker bent van het gedrag van het terrein? Bovendien, in veiligheidskritische velden zoals autonoom rijden of medische robotica, is het doel niet alleen om een bestemming snel te bereiken, maar om te garanderen dat het systeem nooit een gevaarlijke staat betreedt of voor eeuwig een specifieke logische sequentie van gebeurtenissen volgt.

Onderzoekers van het Indian Institute of Technology Bombay en Nanyang Technological University hebben zich aangepakt van dit moeilijke snijvlak van onzekerheid en strikte logische veiligheid. Ze richtten zich op een klasse van problemen waarbij een agent beslissingen moet nemen terwijl hij de wereld slechts gedeeltelijk ziet, en waarbij de regels van beweging geen vaste getallen zijn maar behoren tot een verzameling mogelijke waarden. Het team bewees dat het oplossen van deze complexe, onzekere besluitvormingsproblemen wiskundig identiek is aan het oplossen van een ander, goed bestudeerd type spel waarbij twee tegenovergestelde spelers met verborgen informatie betrokken zijn. Door deze tweerichtingsverbinding te vestigen, waren ze in staat om decennia aan bestaande kennis over speltheorie te lenen om direct de computationele moeilijkheid van het oplossen van deze onzekere robotproblemen te bepalen. Hun werk onthult precies hoe moeilijk het is om veiligheid te garanderen in deze scenario's, waarbij zij laten zien dat voor sommige soorten logische doelen het probleem oplosbaar is met bekende methoden, terwijl het voor andere zo complex is dat geen enkel algoritme het in een redelijke tijd zou kunnen oplossen.

De kern van hun ontdekking ligt in het overbruggen van twee verschillende wiskundige werelden. Aan de ene kant is er de robuuste gedeeltelijk observeerbare Markov-beslissingsproces (robust partially observable Markov decision process), een model dat wordt gebruikt om een situatie te beschrijven waarin een agent, zoals een zelfrijdende auto, acties moet kiezen zonder de exacte locatie te kennen en zonder de exacte waarschijnlijkheid te kennen van een beweging naar een nieuwe staat. In plaats van een enkele waarschijnlijkheid, opereert het systeem binnen een "wolk" van mogelijke waarschijnlijkheden. Aan de andere kant is er de gedeeltelijk observeerbare stochastische spel (partially observable stochastic game), een model waarbij twee spelers, één die probeert te slagen en de ander die probeert dit te voorkomen, om de beurt zetten doen terwijl ze slechts gedeelde informatie over het bord zien. Jarenlang wisten onderzoekers dat als het doel simpelweg het maximaliseren van een beloning was, deze twee modellen naar elkaar vertaald konden worden. Echter, wanneer het doel verschuift naar strikte logische regels — zoals "nooit een voetganger raken" of "uiteindelijk het ziekenhuis bereiken en daar voor altijd blijven" — werd de verbinding verbroken. De nieuwe studie bewijst dat zelfs met deze complexe logische regels, de twee modellen nog steeds perfect equivalent zijn.

Om dit te demonstreren, bouwden de onderzoekers een nauwkeurig vertaalmechanisme dat in beide richtingen werkt. Eerst lieten ze zien hoe je een robuust beslissingsprobleem met onzekere waarschijnlijkheden kunt omzetten in een tweespeler-spel. In dit nieuwe spel wordt de agent één speler, en de onzekerheid van de wereld wordt een tweede, tegenstander-speler. Deze tweede speler handelt niet willekeurig; in plaats daarvan kiest het actief het slechtst denkbare scenario uit de beschikbare opties om de agent te verslaan. De onderzoekers bewezen dat als de agent dit spel kan winnen tegen een slimme tegenstander, hij ook kan slagen in de oorspronkelijke onzekere wereld. Nog verrassender was dat zij de omgekeerde vertaling bereikten. Ze lieten zien dat elk tweespeler-spel met verborgen informatie kon worden omgezet in een robuust beslissingsprobleem. Deze omgekeerde stap was technisch moeilijk omdat, in het spel, de tegenstander de zet van de agent ziet voordat hij handelt, terwijl in het beslissingsprobleem de omgeving zich direct aan haar gedrag committeert. Het team loste dit op door een korte, onzichtbare pauze in de spelstructuur in te voegen, waardoor de omgeving effectief dezelfde informatie kreeg als in het oorspronkelijke probleem. Deze tweerichtingsbrug betekent dat elk computerwetenschappelijk resultaat over de moeilijkheid van het oplossen van het ene type probleem automatisch van toepassing is op het andere.

De implicaties van deze equivalentie zijn onmiddellijk en diepgaand voor het begrip van de grenzen van geautomatiseerd redeneren. Door deze brug te gebruiken, waren de onderzoekers in staat om de exacte computationele complexiteit van het oplossen van deze problemen voor diverse typen logische doelen in kaart te brengen. Ze vonden dat voor eenvoudige doelen, zoals het bereiken van een doel of het vermijden van een gevarenzone, de problemen oplosbaar zijn, hoewel ze aanzienlijke rekenkracht vereisen die exponentieel groeit met de omvang van het systeem. Echter, de studie identificeerde ook een harde grens. Voor bepaalde complexe logische doelstellingen, specifiek die die een mix bevatten van "altijd" en "uiteindelijk" condities in een tweezijdige onzekere omgeving, wordt het probleem onbeslisbaar (undecidable). Dit betekent dat geen enkel computerprogramma, ongeacht hoe krachtig, ooit een antwoord kan garanderen voor elk mogelijk scenario. De onderzoekers verduidelijkten ook de moeilijkheid voor eenzijdig onzekere scenario's, waarbij alleen de agent blind is maar de omgeving alles ziet, waarbij zij lieten zien dat deze gevallen over het algemeen gemakkelijker op te lossen zijn dan de volledig blinde scenario's.

Dit werk biedt een volledig landschap van wat computationeel mogelijk is bij het ontwerpen van veilige, autonome systemen onder onzekerheid. Het bevestigt dat hoewel we algoritmen kunnen bouwen om veel veiligheidskritische taken aan te pakken, er fundamentele grenzen zijn waar de combinatie van verborgen informatie, adversariële onzekerheid en complexe logische regels een oplossing onmogelijk maakt. De studie biedt geen nieuw algoritme om elk geval op te lossen, maar biedt eerder een definitieve kaart van het terrein, die ingenieurs precies vertelt welke problemen ze kunnen oplossen en welke een totaal andere aanpak vereisen. Door te bewijzen dat deze twee wiskundige kaders hetzelfde zijn, hebben de onderzoekers een enorme bibliotheek aan bestaande instrumenten en theorieën ontsloten, waardoor het vakgebied met een helder begrip van de komende uitdagingen vooruit kan gaan.