Resumo Técnico: Aprendizado de Modelos de Ação Levantados a partir de Rastros com Informação Mínima

Declaração do Problema

Trabalhos recentes demonstraram que modelos STRIPS levantados podem ser aprendidos eficientemente a partir de rastros de ação apenas (algoritmo SIFT), e que modelos STRIPS+ (que permitem argumentos de ação implícitos) podem ser aprendidos a partir de rastros de estado-ação totalmente observáveis (algoritmo SYNTH). No entanto, essas abordagens enfrentam limitações práticas:

1. SIFT requer rastros de ação STRIPS completos onde os argumentos são explícitos, o que frequentemente inclui parâmetros desnecessários não necessários para a seleção de ações (por exemplo, em quebra-cabeças de deslizamento de peças, a posição atual de uma peça deve ser passada explicitamente, mesmo que a ação seja "mover para a esquerda").
2. SYNTH assume a observabilidade total de todos os predicados de estado, o que é irrealista para agentes operando em ambientes parcialmente observáveis.

Este artigo aborda o problema de aprender domínios de ação STRIPS+ a partir de rastros onde tanto os argumentos de ação quanto as informações de estado são parcialmente observáveis. Especificamente, os autores investigam as condições sob as quais um domínio equivalente pode ser aprendido quando os rastros carregam informação mínima: alguns argumentos de ação são omitidos, e os predicados de estado são totalmente não observáveis, totalmente observáveis ou apenas localmente observáveis (observáveis apenas para objetos relevantes ao estado atual).

Metodologia

A solução proposta, SYNTH+, é um algoritmo unificado que estende e combina as capacidades do SIFT e do SYNTH. Opera sobre rastros estendidos (sequências de ações e observações parciais de estado) e depende de dois mecanismos centrais:

1. Recursos de Mutex (Extensão do SIFT)

Para lidar com argumentos de ação ausentes sem observabilidade de estado, os autores introduzem recursos de mutex.

• Conceito: Um recurso de mutex $f = \langle k, A, D \rangle$ representa um predicado de aridade $k$ onde o $k$-ésimo argumento é implicitamente determinado pelos primeiros $k-1$ argumentos.
• Mecanismo: Diferentemente dos recursos padrão onde os padrões de adição e exclusão possuem a mesma aridade, os recursos de mutex permitem que os padrões de exclusão tenham aridade $k-1$. Isso captura a restrição de que uma ação (por exemplo, drop()) exclui um predicado (por exemplo, holding(o)) com base no objeto atualmente segurado, sem nomear explicitamente esse objeto no rastro de ação.
• Consistência: Um recurso de mutex é consistente se, através do grafo de rastros, cada átomo ground $f(o)$ receber um único valor de verdade, e para quaisquer dois átomos verdadeiros $f(o)$ e $f(o')$ no mesmo estado, se os últimos argumentos diferirem ($o_k \neq o'_k$), então pelo menos um argumento precedente também deve diferir ($o_i \neq o'_i$ para algum $i < k$).

2. Síntese de Consultas e Integração (Extensão do SYNTH)

O SYNTH+ integra a "invenção" de predicados (via SIFT) com a inferência de argumentos implícitos (via SYNTH) em um loop iterativo:

1. Entrada: Um grafo rotulado de rastros estendidos e um conjunto de predicados totalmente observáveis $P_\omega$.
2. Iteração:
   • Etapa SIFT+: Usa padrões de ação sobre argumentos explícitos e argumentos implícitos atualmente conhecidos para inventar novos recursos de mutex e recursos simples. Esses recursos representam novos predicados e seus efeitos.
   • Etapa SYNTH: Usa os predicados recém-inventados (e quaisquer predicados observáveis) para definir consultas (subconsultas $Q_i$) que vinculam variáveis implícitas ($z_i$) a objetos únicos no estado.
   • Atualização: O grafo é atualizado com os novos argumentos implícitos e suas consultas definidoras.
3. Terminação: O processo continua até que um ponto fixo seja alcançado ou um limite máximo de profundidade ($d_{max}$) seja excedido.

3. Observabilidade Local

O framework é estendido para LOCAL SYNTH+, que lida com observabilidade local. Neste cenário, um predicado é observável apenas para objetos "locais" (aqueles que aparecem como argumentos na ação atual). O algoritmo modifica o procedimento de teste de consistência (TEST*) para assumir que átomos não locais são falsos ao testar pré-condições, garantindo que partes não observadas do estado não invalidem o aprendizado de argumentos implícitos.

Principais Contribuições

1. Algoritmo SYNTH+: Um algoritmo geral para aprender domínios STRIPS+ a partir de rastros com observabilidade parcial de ações e estados. Unifica a invenção de predicados do SIFT com a resolução de argumentos implícitos do SYNTH.
2. Recursos de Mutex: Um formalismo inovador que permite o aprendizado de predicados onde o último argumento é funcionalmente dependente dos outros, permitindo a recuperação de argumentos de ação omitidos sem observação total do estado.
3. Resultados de Completude: Condições teóricas são estabelecidas para quando os algoritmos são completos:
   • SIFT+ (Sem observabilidade de estado): Requer que o domínio STRIPS+ oculto seja bem-formado, fortemente conectado e acíclico em seu grafo de dependência (onde os nós são predicados e variáveis implícitas).
   • SYNTH+ (Observabilidade parcial de estado): Requer que o grafo de dependência restrito a predicados não observáveis seja acíclico.
   • LOCAL SYNTH+: Provado completo sob observabilidade local para predicados-chave (predicados em pré-condições envolvendo apenas argumentos implícitos) se forem totalmente observáveis, e outros predicados forem localmente observáveis.
4. Generalização: O trabalho demonstra que SIFT e SYNTH são casos especiais de SYNTH+ (onde $P_\omega = \emptyset$ e $P_\omega = P$, respectivamente).

Resultados Experimentais

Os autores avaliaram SIFT+ e SYNTH+ em uma suíte de domínios de planejamento padrão (por exemplo, Blocos, Entrega, Grade, Sokoban, Logística) usando rastros estendidos gerados a partir de modelos STRIPS+ ocultos.

• Desempenho do SIFT+: Aprendeu com sucesso domínios corretos (taxa de verificação de 100%) a partir de rastros de ação apenas em todos os domínios testados, recuperando uma média de 55% dos argumentos de ação que foram omitidos dos rastros.
• Desempenho do SYNTH+: Aprendeu domínios corretos usando significativamente menos predicados observáveis do que o SYNTH.
  • Em Entrega, o SYNTH+ aprendeu o domínio observando apenas a posição do agente (at(x)) e adjacência estática, enquanto o SYNTH exigia todos os predicados fluídos.
  • Em Sokoban e Logística*, o SYNTH+ aprendeu domínios com apenas predicados estáticos observados, um cenário onde nem o SYNTH nem o SIFT+ poderiam ter sucesso.
• Eficiência: Os algoritmos executaram eficientemente (segundos a minutos) em hardware padrão, escalando para domínios com milhares de etapas de rastro.

Significado e Alegações

O artigo afirma que o SYNTH+ fornece uma alternativa levantada prática ao aprendizado de reforço baseado em modelo, permitindo o aprendizado de modelos dinâmicos a partir de rastros "naturais". Esses rastros requerem informação mínima:

• Não precisam listar cada argumento exigido por uma codificação STRIPS formal (por exemplo, a posição atual de um bloco sendo desmontado).
• Não exigem observabilidade total de estado; observabilidade parcial ou local de predicados específicos é suficiente.

Os autores enfatizam que sua abordagem preenche a lacuna entre o aprendizado de modelo teórico (que frequentemente assume observabilidade total) e a aplicação prática (onde os agentes têm percepção limitada). Ao caracterizar as condições exatas (acilicidade dos grafos de dependência) sob as quais o aprendizado é possível, o trabalho estabelece um escopo rigoroso para o aprendizado de modelos de ação levantados em cenários parcialmente observáveis. Os resultados sugerem que domínios complexos podem ser reconstruídos a partir de rastros que transmitem apenas a informação necessária para selecionar ações, em vez da descrição completa do estado.