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

Nel mondo dell'intelligenza artificiale, prendere decisioni è spesso trattato come un gioco di fortuna giocato su una scacchiera dove le regole sono perfettamente note. Immaginate un robot che naviga in un labirinto; se gli ingegneri conoscono esattamente quanto sia scivoloso il pavimento e come ruoteranno le ruote del robot, possono calcolare il percorso perfetto per l'uscita. Questo è il modello standard per molti sistemi decisionali. Tuttavia, il mondo reale è raramente così preciso. I sensori si guastano, i materiali si usurano e i dati sono rumorosi, il che significa che le probabilità esatte che un robot scivoli o che un'auto sbandi non sono mai veramente note, ma solo stimate entro un intervallo di possibilità. Quando queste incertezze si aggiungono al mix, il problema diventa molto più difficile: come si pianifica un percorso sicuro quando non si può essere certi del comportamento del terreno? Inoltre, in settori critici per la sicurezza come la guida autonoma o la robotica medica, l'obiettivo non è solo raggiungere una destinazione rapidamente, ma garantire che il sistema non entri mai in uno stato pericoloso o non segua una specifica sequenza logica di eventi all'infinito.

Ricercatori dell'Indian Institute of Technology Bombay e della Nanyang Technological University hanno affrontato questa difficile intersezione tra incertezza e rigida sicurezza logica. Si sono concentrati su una classe di problemi in cui un agente deve prendere decisioni mentre vede solo parzialmente il mondo, e dove le regole di movimento non sono numeri fissi ma appartengono a un insieme di valori possibili. Il team ha dimostrato che risolvere questi complessi problemi decisionali incerti è matematicamente identico a risolvere un tipo diverso e ben studiato di gioco che coinvolge due giocatori con informazioni nascoste. Stabilendo questa connessione bidirezionale, sono stati in grado di prendere in prestito decenni di conoscenze esistenti sulla teoria dei giochi per determinare istantaneamente la difficoltà computazionale di risolvere questi problemi robotici incerti. Il loro lavoro rivela esattamente quanto sia difficile garantire la sicurezza in questi scenari, mostrando che per alcuni tipi di obiettivi logici, il problema è risolvibile con metodi noti, mentre per altri è così complesso che nessun algoritmo potrebbe mai risolverlo in un tempo ragionevole.

Il cuore della loro scoperta risiede nel collegare due mondi matematici differenti. Da un lato c'è il processo decisionale di Markov parzialmente osservabile e robusto, un modello usato per descrivere una situazione in cui un agente, come un'auto a guida autonoma, deve scegliere azioni senza conoscere la propria posizione esatta e senza conoscere la probzione esatta di spostarsi in un nuovo stato. Invece di una singola probabilità, il sistema opera all'interno di una "nuvola" di probabilità possibili. Dall'altro lato c'è il gioco stocastico parzialmente osservabile, un modello in cui due giocatori, uno che cerca di avere successo e l'altro che cerca di impedirlo, si alternano nel compiere mosse mentre vedono solo informazioni parziali della scacchiera. Per anni, i ricercatori sapevano che se l'obiettivo era semplicemente massimizzare un premio, questi due modelli potevano essere tradotti l'uno nell'altro. Tuttavia, quando l'obiettivo si sposta verso rigide regole logiche — come "non colpire mai un pedone" o "raggiungere eventualmente l'ospedale e restarci per sempre" — la connessione si interrompeva. Il nuovo studio dimostra che anche con queste complesse regole logiche, i due modelli sono ancora perfettamente equivalenti.

Per dimostrare ciò, i ricercatori hanno costruito un preciso meccanismo di traduzione che funziona in entrambe le direzioni. Per prima cosa, hanno mostrato come prendere un problema decisionale robusto con probabilità incerte e convertirlo in un gioco a due giocatori. In questo nuovo gioco, l'agente diventa un giocatore, e l'incertezza del mondo diventa un secondo giocatore avversario. Questo secondo giocatore non agisce casualmente; invece, sceglie attivamente lo scenario peggiore tra le opzioni disponibili per cercare di sconfiggere l'agente. I ricercatori hanno dimostrato che se l'agente può vincere questo gioco contro un avversario astuto, può anche avere successo nel mondo incerto originale. Più sorprendentemente, hanno ottenuto la traduzione inversa. Hanno dimostrato che qualsiasi gioco a due giocatori con informazioni nascoste poteva essere convertito in un problema decisionale robusto. Questo passaggio inverso era tecnicamente difficile perché, nel gioco, l'avversario vede la mossa dell'agente prima di agire, mentre nel problema decisionale, l'ambiente si impegna nel proprio comportamento immediatamente. Il team ha risolto questo problema inserendo una breve pausa invisibile nella struttura del gioco, dando efficacemento all'ambiente la stessa informazione che aveva nel problema originale. Questo ponte bidirezionale significa che qualsiasi risultato di informatica sulla difficoltà di risolvere un tipo di problema si applica automaticamente all'altro.

Le implicazioni di questa equivalenza sono immediate e profonde per la comprensione dei limiti del ragionamento automatizzato. Utilizzando questo ponte, i ricercatori sono stati in grado di mappare l'esatta complessità computazionale della risoluzione di questi problemi per vari tipi di obiettivi logici. Hanno scoperto che per obiettivi semplici, come raggiungere un obiettivo o evitare una zona di pericolo, i problemi sono risolvibili, sebbene richiedano una potenza di calcolo significativa che cresce esponenzialmente con la dimensione del sistema. Tuttavia, lo studio ha anche identificato un limite invalicabile. Per certi obiettivi logici complessi, specificamente quelli che coinvolgono un mix di condizioni di "sempre" e "eventualmente" in un ambiente a incertezza bilaterale, il problema diventa indecidibile. Ciò significa che nessun programma informatico, indipendentemente da quanto potente, potrà mai garantire una risposta per ogni possibile scenario. I ricercatori hanno inoltre chiarito la difficoltà per l'incertezza unidirezionale, dove solo l'agente è cieco mentre l'ambiente vede tutto, mostrando che questi casi sono generalmente più facili da risolvere rispetto agli scenari di cecità totale.

Questo lavoro fornisce un panorama completo di ciò che è computazionalmente possibile quando si progettano sistemi autonomi sicuri sotto incertezza. Conferma che, sebbene possiamo costruire algoritmi per gestire molti compiti critici per la sicurezza, esistono confini fondamentali dove la combinazione di informazioni nascoste, incertezza avversaria e regole logiche complesse rende impossibile trovare una soluzione. Lo studio non offre un nuovo algoritmo per risolvere ogni caso, ma piuttosto una mappa definitiva del terreno, dicendo agli ingegneri esattamente quali problemi possono risolvere e quali richiedono un approccio completamente diverso. Dimostrando che questi due framework matematici sono la stessa cosa, i ricercatori hanno sbloccato una vasta libreria di strumenti e teorie esistenti, permettendo al campo di procedere con una chiara comprensione delle sfide che attendono.