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

No mundo da inteligência artificial, a tomada de decisões é frequentemente tratada como um jogo de azar jogado em um tabuleiro onde as regras são perfeitamente conhecidas. Imagine um robô navegando em um labirinto; se os engenheiros souberem exatamente o quão escorregadio é o chão e como as rodas do robô irão girar, eles podem calcular o caminho perfeito para a saída. Este é o modelo padrão para muitos sistemas de tomada de decisão. No entanto, o mundo real raramente é tão preciso. Sensores falham, materiais se desgastam e os dados são ruidosos, o que significa que as chances exatas de um robô escorregar ou de um carro derivar nunca são verdadeiramente conhecidas, apenas estimadas dentro de uma gama de possibilidades. Quando essas incertezas são adicionadas à mistura, o problema torna-se muito mais difícil: como planejar um caminho seguro quando não se pode ter certeza do comportamento do terreno? Além disso, em campos críticos para a segurança, como a condução autónoma ou a robótica médica, o objetivo não é apenas chegar a um destino rapidamente, mas garantir que o sistema nunca entre em um estado perigoso ou siga uma sequência lógica específica de eventos para sempre.

Pesquisadores do Instituto Indiano de Tecnologia de Bombaim e da Universidade Tecnológica de Nanyang enfrentaram essa intersecção difícil entre incerteza e rigor lógico de segurança. Eles se concentraram em uma classe de problemas onde um agente deve tomar decisões enquanto vê apenas parcialmente o mundo, e onde as regras de movimento não são números fixos, mas pertencem a um conjunto de valores possíveis. A equipe provou que resolver esses complexos problemas de decisão incertos é matematicamente idêntico a resolver um tipo diferente e bem estudado de jogo envolvendo dois jogadores com informação oculta. Ao estabelecer essa conexão de via dupla, eles puderam tomar emprestado décadas de conhecimento existente sobre a teoria dos jogos para determinar instantaneamente a dificuldade computacional de resolver esses problemas robóticos incertos. O trabalho deles revela exatamente o quão difícil é garantir a segurança nesses cenários, mostrando que, para alguns tipos de objetivos lógicos, o problema é solucionável com métodos conhecidos, enquanto para outros, é tão complexo que nenhum algoritmo conseguiria resolvê-lo em um tempo razoável.

O cerne de sua descoberta reside na ponte entre dois mundos matemáticos diferentes. De um lado está o processo de decisão de Markov parcialmente observável e robusto, um modelo usado para descrever uma situação onde um agente, como um carro autônomo, deve escolher ações sem saber sua localização exata e sem saber a probabilidade exata de se mover para um novo estado. Em vez de uma única probabilidade, o sistema opera dentro de uma "nuvem" de probabilidades possíveis. Do outro lado está o jogo estocástico parcialmente observável, um modelo onde dois jogadores, um tentando ter sucesso e o outro tentando impedi-lo, alternam turnos para fazer movimentos enquanto veem apenas informações parciais sobre o tabuleiro. Durante anos, os pesquisadores sabiam que, se o objetivo fosse simplesmente maximizar uma recompensa, esses dois modelos poderiam ser traduzidos um no outro. No entanto, quando o objetivo muda para regras lógicas estritas — como "nunca atingir um pedestre" ou "eventualmente chegar ao hospital e permanecer lá para sempre" — a conexão era quebrada. O novo estudo prova que, mesmo com essas regras lógicas complexas, os dois modelos ainda são perfeitamente equivalentes.

Para demonstrar isso, os pesquisadores construíram um mecanismo de tradução preciso que funciona em ambas as direções. Primeiro, eles mostraram como pegar um problema de decisão robusto com probabilidades incertas e convertê-lo em um jogo de dois jogadores. Neste novo jogo, o agente torna-se um jogador e a incerteza do mundo torna-se um segundo jogador adversário. Este segundo jogador não age aleatoriamente; em vez disso, ele escolhe ativamente o pior cenário das opções disponíveis para tentar derrotar o agente. Os pesquisadores provaram que, se o agente puder vencer este jogo contra um oponente astuto, ele também poderá ter sucesso no mundo incerto original. Mais surpreendentemente, eles alcançaram a tradução reversa. Eles mostraram que qualquer jogo de dois jogadores com informação oculta poderia ser convertido de volta em um problema de decisão robusto. Este passo reverso foi tecnicamente difícil porque, no jogo, o oponente vê o movimento do agente antes de agir, enquanto no problema de decisão, o ambiente se compromete com seu comportamento imediatamente. A equipe resolveu isso inserindo uma pausa breve e invisível na estrutura do jogo, dando efetivamente ao ambiente a mesma informação que ele tinha no problema original. Esta ponte de via dupla significa que qualquer resultado de ciência da computação sobre a dificuldade de resolver um tipo de problema aplica-se automaticamente ao outro.

As implicações desta equivalência são imediatas e profundas para a compreensão dos limites do raciocínio automatizado. Ao usar esta ponte, os pesquisadores foram capazes de mapear a exata complexidade computacional de resolver esses problemas para vários tipos de objetivos lógicos. Eles descobriram que, para objetivos simples, como alcançar um alvo ou evitar uma zona de perigo, os problemas são solucionáveis, embora exijam um poder de computação significativo que cresce exponencialmente com o tamanho do sistema. No entanto, o estudo também identificou um limite rígido. Para certos objetivos lógicos complexos, especificamente aqueles que envolvem uma mistura de condições de "sempre" e "eventualmente" em um ambiente de incerteza de dois lados, o problema torna-se indecidível. Isso significa que nenhum programa de computador, não importa o quão poderoso, pode jamais garantir uma resposta para todos os cenários possíveis. Os pesquisadores também esclareceram a dificuldade para a incerteza de um lado só, onde apenas o agente é cego, mas o ambiente vê tudo, mostrando que esses casos são geralmente mais fáceis de resolver do que os cenários de cegueira total.

Este trabalho fornece um panorama completo do que é computacionalmente possível ao projetar sistemas autônomos seguros sob incerteza. Confirma que, embora possamos construir algoritmos para lidar com muitas tarefas críticas de segurança, existem fronteiras fundamentais onde a combinação de informação oculta, incerteza adversária e regras lógicas complexas torna uma solução impossível de encontrar. O estudo não oferece um novo algoritmo para resolver todos os casos, mas sim um mapa definitivo do terreno, dizendo aos engenheiros exatamente quais problemas eles podem resolver e quais exigem uma abordagem inteiramente diferente. Ao provar que esses dois frameworks matemáticos são os mesmos, os pesquisadores desbloquearam uma vasta biblioteca de ferramentas e teorias existentes, permitindo que o campo avance com uma compreensão clara dos desafios que virão pela frente.