Resumo Técnico: Escalando o Planejamento Epistêmico Multiagente através de Heurísticas Derivadas de GNN

Declaração do Problema

O Planejamento Epistêmico Multiagente (MEP - Multi-Agent Epistemic Planning) é um framework para raciocinar sobre ações físicas e as crenças de múltiplos agentes. Diferente do planejamento clássico, o MEP exige que os estados sejam representados como estruturas de Kripke (grafos direcionados, pontuados e rotulados) para capturar relações de crença complexas e conhecimento de ordem superior. Esta representação introduz dois desafios primários que dificultam a escalabilidade:

1. Complexidade Intrínseca: Aplicar transições e avaliar fórmulas dentro de estados epistêmicos (e-states) é computacionalmente mais exigente do que no planejamento clássico.
2. Falta de Heurísticas Eficazes: Solvers de MEP existentes frequentemente dependem de busca não informada (ex: Busca em Largura - BFS) porque heurísticas eficazes são escassas. À medida que a extensão do plano aumenta, o espaço de busca cresce exponencialmente, levando à intratabilidade. Embora trabalhos recentes (ex: H-EFP) tenham tentado integrar heurísticas usando constructos de planejamento tradicionais, como grafos de planejamento, poucos abordagens tratam da escalabilidade do MEP através de métodos baseados em dados.

Metodologia

Os autores propõem uma abordagem baseada em dados para gerar heurísticas para MEP usando Redes Neurais de Grafos (GNNs). A ideia central é treinar um regressor baseado em GNN para aproximar a "heurística perfeita" — estimando a distância de qualquer dado estado epistêmico até o estado objetivo mais próximo.

1. Representação de Estado e Embedding

Como os e-states são naturalmente estruturados em grafos (modelos de Kripke), as GNNs foram selecionadas por sua capacidade de capturar estruturas relacionais. O artigo investiga três estratégias para codificar os "mundos" (nós) dentro de uma estrutura de Kripke em vetores numéricos adequados para entrada de GNN:

• Mapeamento de ID Simbólico: Atribui inteiros sequenciais aos mundos com base na ordem de geração. É computacionalmente barato, mas perde a similaridade semântica entre mundos e é não-invariante entre execuções.
• Codificação Baseada em Hash: Aplica uma função de hash às interpretações dos mundos e índices de repetição. Isso garante identificadores consistentes entre execuções e oferece um equilíbrio entre preservação de informação e eficiência computacional.
• Codificação de Máscara de Bits (Bitmask): Representa os mundos como vetores binários codificando fluentes e índices de repetição. Preserva informações lógicas, mas incorre em custos computacionais mais altos e requer modelos maiores para convergir.

Para garantir que as heurísticas generalizem para diferentes condições de objetivo, os autores estendem o embedding do estado para incluir uma codificação compacta do objetivo. Isso cria um grafo unificado onde "nós de estado" e "nos de objetivo" estão conectados, permitindo que o modelo aprenda dependências entre o estado atual e condições de objetivo específicas.

2. Pipeline de Geração de Dados

Os dados de treinamento são gerados offline usando uma Busca em Profundidade (DFS) modificada dentro do planejador deep (uma reimplementação do planejador de EFP de última geração).

• O planejador explora o espaço de estados até um limite de profundidade.
• Ao atingir um objetivo, o algoritmo faz o backtracking, atribuindo a cada e-estado visitado um rótulo correspondente à sua distância até o objetivo mais próximo.
• Para gerenciar a explosão combinatória do espaço de busca, o processo de geração emprega poda probabilística de ramos, ordenação de ações aleatória e verificações de estados duplicados.
• Estados inalcançáveis são descartados para evitar rótulos espúrios, e a distribuição das classes de distância é equilibrada para evitar viés em direção a planos curtos.

3. Arquitetura do Modelo

O regressor neural é implementado em PyTorch usando PyTorch Geometric. A arquitetura consiste em:

• Embedding de Bits: Identificadores de nós (vetores de bits) e atributos de aresta são projetados em embeddings densos via Perceptrons de Camada Múltipla (MLPs).
• Passagem de Mensagem Relacional: Duas camadas de GINEConv (Graph Isomorphism Network com Edge Convolution) agregam informações de vizinhos, incorporando explicitamente atributos de aresta para lidar com dependências modais heterogêneas.
• Sumarização de Nível de Grafo: O pooling de média agrega os embeddings dos nós em uma representação de grafo de tamanho fixo.
• Cabeça de Regressão Residual Profunda: Uma sequência de blocos residuais processa o embedding do grafo, produzindo uma estimativa de distância normalizada via uma função sigmoide.

4. Integração de Busca

A GNN treinada é integrada ao pipeline de planejamento para guiar uma Busca de Heurística Primeiro (HFS - Heuristics-First Search). Os autores também avaliam uma variante, HFS*, que aumenta a heurística prevista $h(s)$ com a profundidade de busca $d(s)$ para formar um score total $f(s) = h(s) + d(s)$, inspirado pelo algoritmo A*.

Principais Contribuições

O artigo delineia quatro contribuições primárias:

1. Comparação de Embeddings: Uma definição formal e comparação empírica de três embeddings de estrutura de Kripke (ID Simbólico, Hash, Bitmask) para entrada de GNN, identificando a codificação baseada em hash como o equilíbrio mais eficaz.
2. Pipeline Automatizado: Um sistema totalmente automatizado para gerar dados de treinamento (pares estado-distância) e treinar o regressor GNN especificamente para o cenário de MEP.
3. Integração: A integração do regressor GNN ao planejador deep para avaliar e-states e guiar o processo de busca.
4. Avaliação Abrangente: Um benchmarking rigoroso da abordagem contra busca não informada (BFS) e planejadores baseados em heurísticas existentes (H-EFP) em múltiplos domínios padrão.

Resultados Experimentais

A avaliação foi conduzida em benchmarks padrão de MEP (ex: Colaboração e Comunicação, Comunicação Seletiva, Grapevine) usando um tempo limite de 600 segundos.

• Escalabilidade vs. Busca Não Informada: A busca guiada por GNN reduziu significativamente o número de nós expandidos em comparação com a Busca em Largura (BFS) na maioria dos domínios. Por exemplo, no domínio de Colaboração e Comunicação (CC), a abordagem GNN expandiu aproximadamente 65 nós em média comparado a 610 para BFS, resolvendo o mesmo número de instâncias.
• Estratégia de Busca: A variante HFS* (combinando heurística e profundidade) superou a HFS padrão, resolvendo aproximadamente 32% mais instâncias e reduzindo o número de nós expandidos.
• Generalização: Modelos treinados com dados agrupados de múltiplos domínios (CC e GR) demonstraram capacidade de generalizar para domínios não vistos, superando a linha de base BFS em termos de expansão de nós.
• Comparação com H-EFP: A abordagem GNN teve desempenho equivalente às melhores heurísticas individuais do planejador H-EFP (especificamente a heurística $S\_PG$), resolvendo 85,33% das instâncias de teste comparado ao intervalo de 49–82% do H-EFP dependendo da heurística específica utilizada.
• Limitações de Tempo de Execução: O artigo observa que, embora a GNN reduza o espaço de busca (nós expandidos), a implementação atual carece de otimizações de inferência em lote (ex: batching CUDA). Consequentemente, os tempos de resolução brutos ainda não são competitivos com heurísticas tradicionais, embora os autores argumentem que a informatividade da heurística é a métrica primária para escalabilidade neste contexto.

Significância e Alegações

Os autores posicionam este trabalho como um passo fundamental na integração de Aprendizado de Máquina com Planejamento Epistêmico Multiagente. Eles alegam que:

• Escassez de Heurísticas: O MEP sofre com a falta de heurísticas eficazes em comparação ao planejamento clássico. Este trabalho demonstra que GNNs podem aprender com sucesso aproximar heurísticas perfeitas neste cenário complexo baseado em grafos.
• Eficiência Baseada em Dados: Ao tratar cada e-estado como um sinal de treinamento independente em vez de depender de trajetórias completas, a abordagem gera grandes conjuntos de dados de forma eficiente, permitindo o aprendizado de padrões significativos da estrutura relacional dos modelos de Kripke.
• Complementaridade: Os autores não alegam que as GNNs substituirão imediatamente as heurísticas existentes. Em vez disso, argumentam que as heurísticas baseadas em GNN servem como uma poderosa ferramenta complementar para aumentar a cobertura do solver, particularmente quando integradas em abordagens de portfólio onde diferentes heurísticas podem compensar as fraquezas umas das outras.

O artigo conclui que, embora otimizações de engenharia (como processamento em lote) sejam necessárias para tornar o desempenho de tempo de execução competitivo, a redução na complexidade do espaço de busca prova a viabilidade de heurísticas aprendidas para escalar o MEP.