CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Resumo Técnico: CayleyPy RL: Roteamento e Aprendizado por Reforço em Grafos de Cayley

Enunciado do Problema
O artigo aborda o problema de roteamento em grafos de Cayley finitos extremamente grandes, focando especificamente no grupo simétrico $S_n$ gerado por deslocamentos cíclicos à esquerda ($L$), deslocamentos cíclicos à direita ($R$) e uma transposição dos dois primeiros elementos ($X$). Esta configuração, conhecida como grafo de Cayley LRX, corresponde à sequência OEIS A186783. O desafio matemático central é decompor um elemento do grupo no produto mais curto possível de geradores (encontrar o caminho mais curto no grafo). Este problema é NP-difícil para grafos de Cayley finitos genéricos. Sistemas de álgebra computacional clássicos, como o GAP, dependem do algoritmo de Schreier-Sims, que frequentemente produz caminhos exponencialmente longos e falha ao lidar com grupos com tamanhos superiores a $10^{30}$ (aproximadamente $n \approx 20$ para $S_n$). Os autores visam desenvolver abordagens eficientes baseadas em inteligência artificial capazes de lidar com grafos com tamanhos até $10^{70}$ (por exemplo, $n \approx 40$ a $100$), produzindo caminhos próximos ao ótimo ou ótimos.

Metodologia
Os autores propõem uma metodologia híbrida que combina Aprendizado por Reforço (RL), especificamente Deep Q-Learning (DQN), com uma estratégia de pré-treinamento baseada em distâncias de difusão.

1. Estrutura de Aprendizado por Reforço: O problema de roteamento é enquadrado como encontrar o caminho mais curto de um estado $s$ até o elemento identidade $e$. Isso é modelado usando a equação de Bellman, onde a função de distância $d(s)$ satisfaz $d(s) = 1 + \min_{t \in N(s)} d(t)$. O DQN padrão é adaptado para aproximar esta função de valor usando redes neurais.
2. Pré-treinamento por Distância de Difusão: Para abordar o problema de "recompensa esparsa" e o ruído inerente à inicialização padrão do DQN, os autores introduzem uma fase de "aquecimento". Eles geram dados de treinamento através de caminhadas aleatórias (difusão) começando a partir do alvo. Uma rede neural é primeiro treinada para prever o número de passos nessas caminhadas aleatórias (distância de difusão).
3. DQN Modificado: A rede pré-treinada é então ajustada (fine-tuned) usando um algoritmo DQN modificado. Crucialmente, os alvos de atualização de Bellman são limitados (clipped) com base no passo de tempo $k$ em que um estado foi visitado pela primeira vez durante a geração da caminhada aleatória. Isso impede que a rede superestime as distâncias e estabiliza o treinamento.
4. Busca em Feixe Guiada: Uma vez que a rede neural é treinada para estimar distâncias, ela serve como uma função heurística para um algoritmo de busca em feixe. A busca em feixe mantém um número fixo ($W$) dos estados mais promissores em cada passo, expandindo seus vizinhos e selecionando os top $W$ com base nas previsões da rede. Isso evita ficar preso em mínimos locais, uma falha comum em buscas gananciosas.
5. O "Truque X": Uma modificação heurística específica para os geradores LRX é introduzida. Se os dois primeiros elementos de uma permutação já estiverem ordenados, o gerador $X$ (que os troca) é excluído do conjunto de vizinhos. Esta modificação de uma única linha reduz drasticamente o espaço de busca e melhora os tempos de mistura.
6. Não-retrocesso: Os autores incorporam restrições de não-retrocesso tanto na geração de caminhadas aleatórias quanto na busca em feixe para reduzir a variância nas estimativas de distância e prevenir estagnação em mínimos locais.

Principais Contribuições

• Avanços Algorítmicos: O artigo apresenta uma combinação novel de pré-treinamento por distância de difusão e DQN modificado. Esta abordagem supera as limitações do DQN padrão (recompensas esparsas, alvos ruidosos) e supera os métodos clássicos.
• Benchmarks de Desempenho: Os métodos propostos encontram com sucesso caminhos para grafos de Cayley LRX até $n \approx 44$ com zero conhecimento prévio e até $n \approx 100$ ao utilizar o "truque X". Isso excede significativamente as capacidades do GAP, que é limitado a $n \approx 20$. Os métodos de IA produzem caminhos mais curtos e executam mais rápido que o GAP para $n$ comparáveis.
• Resultados Matemáticos e Conjecturas:
  • Conjectura do Diâmetro: Os autores apoiam fortemente a conjectura OEIS-A186783 de que o diâmetro do grafo de Cayley LRX é $n(n-1)/2$. Eles verificaram isso via BFS de força bruta para $n \le 15$ e via decomposição por IA para $n$ até 200 (via desafios Kaggle), não encontrando nenhuma decomposição mais curta que o comprimento conjecturado.
  • Elemento Mais Longo: Eles identificam um único "elemento mais longo" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ e fornecem uma decomposição explícita de comprimento $n(n-1)/2$.
  • Limites: O artigo prova um limite inferior para o diâmetro de $n(n-1)/2 - n/2 - 1$ e um limite superior de $n(n-1)/2 + 3n$ via um algoritmo construtivo. Um algoritmo empírico sugere um limite mais apertado de $n(n-1)/2 + n/2$.
  • Distribuição de Crescimento: Experimentos numéricos sugerem que a função de crescimento do grafo LRX segue uma distribuição Gumbel enviesada à esquerda para grandes $n$, contrastando com a distribuição Gaussiana observada em grafos de transposição de vizinhos.
  • Tempo de Mistura: Enquanto caminhadas aleatórias padrão têm tempos de mistura entre $O(n^3)$ e $O(n^3 \log n)$, os autores conjecturam que caminhadas aleatórias modificadas com o "truque X" misturam mais rápido, com uma complexidade de tempo de $O(n^2)$.
  • Espectro: O espectro do grafo LRX parece seguir uma distribuição uniforme.
• Código Aberto e Crowdsourcing: Os autores lançaram o projeto "CayleyPy" e criaram desafios Kaggle para crowdsourcing de soluções para decompor o elemento mais longo e encontrar algoritmos ótimos, fomentando a colaboração entre as comunidades de IA e matemática.

Resultados

• Eficiência: Para $n=20$, o GAP requer mais de 41 minutos para encontrar um caminho de comprimento 217.944, enquanto o método de distância de difusão encontra o caminho ótimo de comprimento 190 em menos de 4 minutos.
• Escalabilidade: Com o "truque X", o sistema resolveu instâncias para $n=100$ (tamanho do grafo $\approx 10^{157}$) em aproximadamente 8,5 horas em uma única GPU, encontrando um caminho de comprimento 16.632 (comparado ao diâmetro conjecturado de 4.950).
• Desempenho do Modelo: Modelos simples como Perceptrons Multicamada (MLP) e Gradient Boosting (CatBoost/XGBoost) frequentemente superaram arquiteturas complexas como Transformers e CNNs para esta tarefa específica.
• Busca em Feixe: A taxa de sucesso de encontrar um caminho depende altamente da largura do feixe, mostrando uma melhoria superlinear à medida que o tamanho do feixe aumenta, análogo ao "intercâmbio de ideias" em uma comunidade de pesquisa.

Significado
O artigo afirma que experimentos computacionais, particularmente aqueles que alavancam IA, podem avançar significativamente a pesquisa matemática sobre grafos de Cayley. Demonstra que os métodos de IA podem "superar" sistemas de álgebra computacional clássicos tanto em escalabilidade (lidando com $n$ muito maiores) quanto na qualidade da solução (encontrando caminhos mais curtos e próximos do ótimo). O trabalho preenche a lacuna entre a teoria dos grupos teórica e a IA prática, fornecendo limites rigorosos, novas conjecturas sobre crescimento e tempos de mistura, e um quadro para resolver problemas de roteamento em espaços de estado extremamente grandes que anteriormente eram intratáveis. Os autores posicionam isso como um passo para aplicar IA a outros problemas complexos de planejamento na ciência teórica.