Structure-Induced Information for Rerooting Levin Tree Search

Resumo Técnico: Informação Induzida por Estrutura para Busca de Árvore de Reenraizamento de Levin

Definição do Problema

Problemas de planejamento discreto complexos em ambientes determinísticos de agente único permanecem difíceis de resolver em escala. Embora métodos de busca em árvore guiados por política, como a Busca de Árvore de Levin (LTS) e a Busca Heurística Guiada por Política (PHS*), ofereçam garantias teóricas sobre o esforço de busca, eles frequentemente enfrentam dificuldades em domínios complexos sem orientação estrutural adicional.

Uma estratégia comum para abordar isso é a decomposição de problemas em submetas. No entanto, os métodos baseados em submetas existentes (ex: HIPS-$\epsilon$, SGPS) dependem da geração e reconstrução explícitas de submetas. Isso introduz uma complexidade de modelagem e um overhead computacional significativos, pois o desempenho da busca torna-se fortemente acoplado à qualidade da geração de submetas. À medida que a complexidade do domínio aumenta, o custo de reconstruir e raciocinar sobre essas submetas explícitas torna-se um gargalo, dificultando a escalabilidade.

O artigo aborda o desafio de explorar a estrutura do espaço de estados para guiar a busca de forma eficiente sem o custo computacional da geração de submetas explícitas. Especificamente, investiga como derivar pesos de "reenraizamento" (rerooting) eficazes para o algoritmo $\sqrt{\text{LTS}}$ — um método que inicia implicitamente uma busca LTS em cada nó da árvore — utilizando sinais estruturais disponíveis durante o processo de busca.

Metodologia

Os autores propõem um framework que utiliza Reenraizadores Induzidos por Estrutura para alocar o esforço de busca em $\sqrt{\text{LTS}}$. Em vez de gerar submetas explícitas, o framework deriva pesos de reenraizamento da estrutura da árvore de busca e de heurísticas aprendidas. O artigo introduz três instaciações específicas:

1. Reenraizamento de Estrutura Global ($\sqrt{\text{LTS-L}}$)

Esta abordagem captura a estrutura global grosseira no espaço de estados usando agrupamento de Leiden (Leiden clustering).

• Mecanismo: À medida que a árvore de busca é construída, um subgrafo induzido do espaço de estados é construído. O algoritmo de Leiden é invocado periodicamente (em um cronograma geométrico) para agrupar estados com base na conectividade.
• Atribuição de Peso: Os nós recebem uma "cor" correspondente ao seu cluster. O peso de reenraizamento de um nó é inversamente proporcional ao tamanho de seu cluster (aproximado pela contagem de nós com aquela cor).
• Racional: Isso incentiva a busca a concentrar o esforço em regiões subexploradas (clusters pequenos) e redireciona o esforço para longe de regiões sobreexploradas (clusters grandes), tratando efetivamente os clusters como subtarefas suaves sem reconstrução explícita.

2. Reenraizamento de Estrutura Local ($\sqrt{\text{LTS-H}}$)

Esta abordagem aproveita estimativas locais de custo-para-ir fornecidas por uma função heurística aprendida.

• Mecan_nismo: O peso de reenraizamento é definido como uma função exponencial do valor heurístico normalizado: $w_t = \exp(-\alpha \frac{h(n_t)}{h(n_1)})$.
• Racional: Isso cria uma priorização "suave" onde nós estimados estarem mais próximos do objetivo (valores heurísticos menores) recebem pesos maiores. A normalização pelo heurístico da raiz garante a invariância à escala absoluta da heurística, enquanto o mapeamento exponencial garante pesos suaves e estritamente positivos que permitem heurísticas imperfeitas.

3. Reenraizamento Híbrido de Estrutura ($\sqrt{\text{LTS-LH}}$)

Este método combina os sinais global e local de forma aditiva.

• Mecanismo: O peso final é uma combinação linear do peso baseado em clustering e do peso baseado em heurística: $w_t = u_a w_{t, \text{cluster}} + u_b w_{t, \text{heuristic}}$.
• Racional: O reenraizador global fornece estabilidade contra ruído ou má calibração da heurística ao identificar gargalos estruturais, enquanto o reenraizador local refina as prioridades dentro dessas regiões com base no progresso estimado. Esta abordagem "coarse-to-fine" (do grosseiro ao fino) visa equilibrar robustez com adaptatividade direcionada ao objetivo.

Garantias Teóricas

O artigo estende os limites teóricos sobre o número de expansões de nós exigidas pelo $\sqrt{\text{LTS}}$. Ele fornece uma nova garantia para reenraizadores aditivos, mostrando que a complexidade da busca é limitada pelo efeito sinérgico de múltiplos reenraizadores. Especificamente, se os pesos relativos dos componentes forem equilibrados, o limite depende do mínimo dos limites individuais, permitindo que a busca recue para o sinal mais informativo em qualquer região da árvore.

Principais Contribuições

1. Aprendizado Automatizado de Reenraizadores: O artigo apresenta métodos automatizados para derivar pesos de reenraizamento diretamente da estrutura da árvore de busca (via clustering) e de heurísticas aprendidas, eliminando a necessidade de redes separadas e computacionalmente caras de geração e reconstrução de submetas.
2. Três Designs de Reenraizadores: Introduz e avalia três designs distintos: um reenraizador global baseado em clustering, um reenraizador local baseado em heurística e um reenraizador híbrido aditivo.
3. Extensão Teórica: Fornece um novo limite teórico para $\sqrt{\text{LTS}}$ usando reenraizadores aditivos, demonstrando como múltiplos sinais estruturais podem ser combinados para melhorar a eficiência da busca.
4. Demonstração de Escalabilidade: O trabalho demonstra que o reenraizamento pode escalar para ambientes complexos onde métodos baseados em submetas explícitas falham, alcançando eficiência de treinamento online de estado da arte.

Resultados Experimentais

Os autores avaliaram seus métodos em quatro domínios: BoulderDash, CraftWorld, Sokoban e uma versão em grid do Problema do Caixeiro Viajante (TSP). Eles compararam seus métodos contra LTS, PHS*, variantes baseadas em submetas (LTS($\pi_{SG}$), PHS*($\pi_{SG}$)) e Weighted A*.

• Eficiência de Treinamento: Em todos os domínios, o reenraizador híbrido ($\sqrt{\text{LTS-LH}}$) e o reenraizador baseado em heurística ($\sqrt{\text{LTS-H}}$) melhoraram substancialmente a eficiência de amostra de treinamento online em comparação com as linhas de base sem reenraizamento e métodos anteriores baseados em submetas. Em configurações complexas (ex: BoulderDash com alta densidade de sujeira), os métodos baseados em submetas (PHS*($\pi_{SG}$)) não escalaram ou sofreram timeout, enquanto os métodos de reenraizamento completaram o treinamento com sucesso.
• Desempenho de Teste: Apesar do treinamento mais rápido, os métodos de reenraizamento alcançaram desempenho de teste comparável ou superior (medido por problemas resolvidos, expansões para solução e comprimento da solução) aos métodos anteriores.
• Robustez: A abordagem híbrida provou ser a mais robusta, particularmente em domínios com estruturas de impasse (Sokoban, CraftWorld) onde a orientação puramente heurística poderia ser instável. O componente de clustering global ajudou a estabilizar a busca quando as heurísticas eram pouco confiáveis.
• Escalabilidade de Complexidade: No experimento de escalabilidade de complexidade do BoulderDash, os reenraizadores híbrido e de heurística mantiveram o desempenho conforme o espaço de estados crescia, enquanto os métodos baseados em submetas degradaram significativamente devido à dificuldade de reconstruir submetas relevantes em ambientes visualmente densos, mas irrelevantes para a tarefa.

Significância e Alegações

O artigo afirma que o reenraizamento é uma abstração escalável e flexível para explorar a estrutura na busca de árvore de política. Sua principal significância reside em demonstrar que:

• Subtarefas Implícitas: É possível alcançar os benefícios da decomposição de subtarefas (melhor exploração e orientação de busca) sem o overhead computacional da geração e reconstrução de submetas explícitas.
• Sinais Leves: Mesmo sinais estruturais leves (como valores heurísticos locais) podem ser suficientes para guiar um reenraizamento eficaz, muitas vezes superando abordagens de clustering global mais complexas isoladamente.
• Sinergia: Combinar sinais estruturais complementares (conectividade global e custo-para-ir local) cria um mecanismo robusto que se adapta às variações de complexidade do domínio e de qualidade da heurística.

Os autores concluem que o $\sqrt{\text{LTS}}$ com transformações estruturais simples de heurísticas clássicas oferece um caminho altamente eficiente para a busca de árvore de política escalável, evitando os gargalos associados à modelagem de submetas explícitas em domínios complexos.