On Sample-Efficient Generalized Planning via Learned Transition Models

Each language version is independently generated for its own context, not a direct translation.

Imagine que você está ensinando um robô a resolver quebra-cabeças. O desafio é que o robô precisa aprender a resolver não apenas um quebra-cabeça específico, mas qualquer quebra-cabeça desse tipo, mesmo que ele tenha peças muito maiores ou mais numerosas do que as que o robô já viu antes. Isso é o que chamamos de "Planejamento Generalizado".

O artigo que você enviou propõe uma nova maneira de ensinar esse robô, comparando duas abordagens principais: a antiga (que eles chamam de "focada em ações") e a nova deles (focada em "estados").

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: Adivinhar o Próximo Passo vs. Entender a Física do Mundo

A Abordagem Antiga (Focada em Ações):
Imagine que você está ensinando um aluno a dirigir apenas mostrando vídeos de carros dirigindo. O aluno memoriza: "Quando vejo uma curva à esquerda, giro o volante para a esquerda".

O que acontece: Se o aluno vir uma curva um pouco diferente, ou se a estrada for mais longa do que ele já viu, ele começa a errar. Ele tenta adivinhar o próximo movimento baseado apenas no anterior, sem realmente entender como o carro se move. Isso é chamado de "deriva de estado" (state drift). Ele perde o controle porque não sabe onde o carro está de verdade, apenas chuta o próximo movimento.
No papel: Modelos como o PlanGPT ou Plansformer funcionam assim. Eles tentam adivinhar a próxima ação diretamente. Eles precisam de muitos dados e são gigantes (milhões de parâmetros) para funcionar bem, e ainda assim falham em situações novas.

A Abordagem Nova (Focada em Estados - a proposta dos autores):
Agora, imagine que, em vez de ensinar o aluno a girar o volante, você ensina a física do carro. Você diz: "Se eu acelerar, o carro vai para frente. Se eu virar, ele muda de direção".

O que acontece: O aluno aprende a prever onde o carro vai estar no próximo segundo. Se ele sabe onde o carro está e como ele se move, ele pode planejar a rota inteira. Se a estrada for maior, ele só aplica as mesmas regras de física.
No papel: Os autores ensinam o modelo a prever o próximo estado do mundo (o que vai acontecer), não a próxima ação. Eles criam um "modelo de transição" (uma espécie de simulador interno).

2. A Mágica: O "Espelho" e o "Mapa"

Para que isso funcione com quebra-cabeças de tamanhos diferentes, eles usam uma técnica inteligente chamada Representação Relacional (WL Embeddings).

A Analogia do Mapa:
- Se você desenha um mapa de uma cidade pequena e depois tenta desenhar um mapa de uma cidade gigante no mesmo pedaço de papel, você precisa de um sistema que não dependa do tamanho.
- Os modelos antigos tentavam desenhar cada rua e cada prédio (o que é impossível se a cidade crescer).
- O modelo novo usa um código de cores (como o algoritmo de Weisfeiler-Leman). Em vez de contar "100 blocos", ele olha para a estrutura: "Há um bloco em cima de outro". Essa estrutura é a mesma, seja com 4 blocos ou 100. É como se o robô aprendesse a lógica do jogo, não a quantidade de peças.

3. O Processo: Como o Robô Planeja

O sistema funciona em três etapas, como um diretor de cinema:

O Roteiro (Codificação): O robô olha para a situação atual e o objetivo, e transforma isso em um "código" compacto (como um resumo do filme).
O Simulador (Modelo de Transição): O robô usa um modelo simples (como um LSTM ou XGBoost, que são pequenos e rápidos) para prever: "Se eu fizer algo, como vai ficar o resumo da situação no próximo segundo?". Ele prevê o futuro, não a ação.
O Verificador (Decodificação Neuro-Simbólica): Aqui está o segredo. O robô olha para a sua previsão do futuro e diz: "Ok, eu previsei que o mundo vai ficar assim. Agora, qual ação real eu posso fazer para chegar lá?". Ele consulta uma lista de regras válidas (o "simbólico") e escolhe a ação correta.
- Analogia: É como se o robô sonhasse com o próximo passo, e depois consultasse um manual de instruções para ver qual botão apertar para realizar aquele sonho. Isso garante que ele nunca cometa um erro lógico.

4. Os Resultados: Pequeno e Eficiente vs. Gigante e Caro

O estudo comparou sua abordagem com os modelos gigantes de Inteligência Artificial atuais:

Os Gigantes (Transformers): São como supercomputadores que precisam ler milhões de livros (dados) para aprender. Eles são caros, lentos e, quando o problema fica muito grande (extrapolação), eles se perdem.
O Modelo Novo: É como um bom senso.
- É muito menor: Usa milhares de vezes menos "cérebro" (parâmetros).
- É muito mais eficiente: Aprende com poucos exemplos (como 9 blocos em vez de milhares).
- Funciona melhor em novos tamanhos: Quando testado em problemas muito maiores do que os de treino, o modelo novo conseguiu resolver muitos mais que os modelos gigantes.

5. Onde ele falha? (A Limitação)

O modelo é ótimo em jogos onde as regras são locais e simples (como mover blocos ou visitar salas). Mas, em problemas muito complexos onde uma ação hoje afeta algo muito distante no futuro (como logística complexa com caminhões e aviões), ele ainda tem dificuldade. É como tentar prever o trânsito de uma metrópole inteira apenas olhando para o cruzamento da sua casa; às vezes, o sistema é muito complexo para uma previsão de um passo só.

Resumo Final

Os autores dizem: "Pare de tentar adivinhar o próximo movimento. Em vez disso, aprenda como o mundo funciona."

Ao ensinar a IA a prever o futuro (o estado do mundo) em vez de apenas adivinhar a próxima ação, e usando uma linguagem matemática que entende o tamanho do problema, eles conseguiram criar um planejador que é pequeno, barato, rápido e muito mais inteligente em situações novas do que os modelos gigantes atuais. É a diferença entre decorar um roteiro e entender a física do universo.

Each language version is independently generated for its own context, not a direct translation.

1. O Problema

O Planejamento Generalizado (GP) visa construir estratégias de solução que se generalizem através de famílias de problemas de planejamento que compartilham um mesmo modelo de domínio (definido por uma função de transição $\gamma: S \times A \to S$ ).

A abordagem recente baseada em aprendizado de máquina, utilizando arquiteturas Transformer (como PlanGPT e Plansformer), trata o GP como uma tarefa de previsão direta de sequências de ações (aprendizado centrado na ação). Embora eficazes em distribuições de dados similares às de treinamento, essas abordagens apresentam limitações críticas:

Ineficiência de Amostra: Requerem conjuntos de dados massivos e modelos grandes (centenas de milhões de parâmetros).
Deriva de Estado (State Drift): Em cenários de longo horizonte ou fora da distribuição (OOD), a falta de modelagem explícita do estado do mundo leva a erros cumulativos, onde o modelo "alucina" estados que não são válidos segundo a dinâmica real do domínio.
Falta de Generalização de Tamanho: Muitos modelos falham ao tentar resolver instâncias com um número de objetos significativamente maior do que aquelas vistas durante o treinamento.

2. Metodologia

Os autores propõem reformular o planejamento generalizado como um problema de aprendizado de modelos de transição (aprendizado centrado no estado), onde o modelo aprende explicitamente a função de sucessor de estado.

A. Abordagem Centrada no Estado (State-Centric)

Em vez de prever o próximo token de ação, o modelo aprende uma função de transição neural $T_\theta$ que, dado o estado atual $s_t$ e o objetivo $g$ , prevê o próximo estado $s_{t+1}$ .

Formulação: O modelo aprende a mapear $(s_t, g) \to \hat{s}_{t+1}$ .
Decodificação Neuro-Simbólica: Para garantir validade simbólica, o sistema não executa a previsão neural diretamente. Em vez disso:
1. O modelo neural prevê um vetor de embedding do próximo estado ( $\hat{\phi}(s_{t+1})$ ).
2. Um buscador simbólico enumera todos os sucessores válidos possíveis $Succ(s_t)$ baseados nos operadores do domínio.
3. Seleciona-se o sucessor simbólico cujo embedding é mais próximo da previsão neural (via busca de vizinho mais próximo).
4. A ação correspondente a essa transição válida é executada.
  Isso corrige erros de previsão neural em tempo real e garante que o plano seja sempre executável.

B. Representações de Estado Invariantes a Tamanho

Para lidar com a variação no número de objetos entre instâncias de treinamento e teste, o paper compara duas representações:

Codificações Fatoradas de Tamanho Fixo (FSF): Vetores com slots pré-definidos para objetos. Falha em generalizar para instâncias maiores que o tamanho de treinamento.
Embutimentos de Grafos Weisfeiler-Leman (WL): Utiliza kernels de grafos para mapear estados relacionais de tamanho variável para vetores de dimensão fixa. Esta representação é invariante a permutações (a ordem dos objetos não importa) e invariante a tamanho (funciona para qualquer número de objetos), permitindo que modelos leves aprendam a dinâmica do domínio independentemente da escala.

C. Modelagem de Transição Residual

Considerando a natureza esparsa das transições em domínios STRIPS (onde a maioria dos predicados permanece inalterada), o modelo aprende a prever o delta (a diferença) entre o estado atual e o futuro, em vez de prever o estado completo.
$\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$
Isso impõe axiomas de quadro (frame axioms) implicitamente e melhora a eficiência da amostra.

D. Arquiteturas de Modelos

Os autores testam modelos compactos:

LSTM (2 camadas): Para capturar dependências temporais.
XGBoost: Um regressor não paramétrico baseado em árvores, testando se a memória temporal é necessária ou se uma aproximação local da função de transição é suficiente.

3. Contribuições Principais

Formulação Alternativa: Propõe uma formulação de GP baseada em previsão de estados sucessores condicionados ao objetivo, contrastando com a previsão direta de ações.
Avaliação Sistemática: Realiza uma análise abrangente de representações de estado (WL vs. FSF) e arquiteturas (LSTM vs. XGBoost) para generalização invariante a tamanho e eficiência de amostra.
Desempenho com Recursos Reduzidos: Demonstra empiricamente que modelos compactos (com ~1 milhão de parâmetros ou menos) podem superar ou igualar planejadores baseados em Transformers massivos (com ~25-220 milhões de parâmetros) em tarefas de generalização, utilizando ordens de magnitude menos dados de treinamento e sem aumento de dados (data augmentation).

4. Resultados Experimentais

Os experimentos foram realizados em quatro domínios do IPC (Blocksworld, Gripper, Logistics, VisitAll), avaliando a generalização para instâncias maiores (extrapolação).

Superioridade em Extrapolação: Em domínios com estrutura local fatorada (Blocksworld, VisitAll), os modelos centrados no estado com embeddings WL alcançaram taxas de sucesso significativamente maiores na extrapolação estrita do que os modelos centrados em ações (Plansformer, PlanGPT, SymT), que frequentemente falharam (0% de sucesso).
- Exemplo: Em Blocksworld, o modelo WL-XGB (delta) atingiu 45% de sucesso na extrapolação, enquanto o SymT atingiu apenas 13% e os outros 0%.
Eficiência de Dados e Modelo: Os modelos propostos foram treinados em conjuntos de dados pequenos e não aumentados, alcançando desempenho competitivo com modelos que exigem milhões de parâmetros e grandes volumes de dados sintéticos.
Importância da Representação: As codificações FSF falharam completamente na extrapolação, confirmando que a invariância relacional (WL) é crucial para generalizar para novos tamanhos de problemas.
Limitações: O modelo teve desempenho zero no domínio Logistics sob extrapolação estrita. Os autores atribuem isso a acoplamentos causais hierárquicos e de longo alcance complexos que não são capturados por previsões de transição de um único passo, mesmo com representações invariantes.

5. Significado e Conclusão

O trabalho demonstra que, para planejamento generalizado, aprender a física do domínio (dinâmica de transição) é um viés indutivo mais forte do que simplesmente escalar arquiteturas de sequência (Transformers) para prever ações.

A abordagem neuro-simbólica proposta combina o melhor dos dois mundos: a capacidade de generalização e aprendizado de padrões dos modelos neurais (via embeddings WL e previsão de transição) com a garantia de correção lógica e validade simbólica dos planejadores clássicos (via verificação de sucessores). Isso permite criar planejadores robustos, eficientes em termos de dados e capazes de lidar com problemas de escala variável, oferecendo uma alternativa viável e mais sustentável aos modelos de linguagem grandes (LLMs) para tarefas de planejamento.