Além do A*: melhor planejamento com transformadores

Além do A*: melhor planejamento com transformadores

• Os modelos de transformador alcançaram grandes avanços em diversas áreas de aplicação, mas ainda ficam atrás dos métodos tradicionais de planejamento simbólico para resolver tarefas complexas de tomada de decisão.
• Os pesquisadores apresentam uma forma de treinar transformadores para resolver tarefas complexas de planejamento e desenvolveram o modelo Searchformer, que resolve de forma ótima quebra-cabeças Sokoban nunca vistos antes em 93,7% das vezes, usando até 26,8% menos etapas de busca do que a busca A* convencional.
• O Searchformer é um modelo transformador encoder-decoder treinado para prever o comportamento da busca A*, e ajustado por meio de expert iteration para gerar planos ótimos com menos etapas de busca do que a busca A*.

Método de treinamento e desempenho

• No método de treinamento, o comportamento de busca do A* é representado como uma sequência de tokens que indica os momentos em que estados são adicionados e removidos da árvore de busca durante o planejamento simbólico.
• Em um estudo de ablação sobre navegação em labirintos, o Searchformer supera com folga um modelo de referência que prevê diretamente planos ótimos, mesmo sendo de 5 a 10 vezes menor e treinado com um conjunto de dados 10 vezes menor.
• Os pesquisadores mostram que o Searchformer é eficaz em tarefas de tomada de decisão maiores e mais complexas, como Sokoban, tanto na taxa de problemas resolvidos quanto na redução do comportamento de busca.

Opinião do GN⁺

• Este estudo mostra novas possibilidades de uso para modelos de transformador na área de inteligência artificial. Ao propor uma abordagem mais eficiente do que os métodos simbólicos tradicionais para resolver tarefas complexas de tomada de decisão, representa um avanço importante na ampliação do campo de aplicação da IA.
• O modelo Searchformer demonstra capacidade de resolver problemas de forma mais rápida e eficiente usando menos recursos. Isso pode ser uma grande vantagem, especialmente na implementação de IA em ambientes com recursos limitados.
• O estudo também sugere que o avanço da tecnologia de IA não depende apenas de mais dados e modelos maiores, mas pode acontecer por meio de metodologias mais inteligentes e melhorias algorítmicas. Trata-se de uma abordagem bastante interessante e útil do ponto de vista da sustentabilidade e da eficiência da pesquisa em IA.

[GN⁺]

Comentários do Hacker News

• Há uma pesquisa interessante sobre o uso de transformers para planejamento de movimento robótico. Fazer um braço robótico se mover de um ponto a outro sem bater em objetos é um problema muito difícil, pois é de alta dimensionalidade e contínuo. Métodos anteriores de planejamento exigiam muito cálculo e não eram muito bons. Essa é uma das razões pelas quais os movimentos dos robôs parecem “antinaturais” e por que eles não conseguem executar bem muitas das tarefas que queremos. Essa abordagem parece competitiva em relação a outros métodos de planejamento e propõe um planejamento de trajetórias ótimas mais rápido.
• Fico curioso se tentaram uma versão modificada do algoritmo J*, uma versão otimizada do algoritmo A* para grafos de jogos/busca de caminhos, antes de iniciar essa linha de pesquisa. Para quem tiver interesse, há informações sobre "Game AI Pro 2".
• Planejamento já é algo bem resolvido por técnicas existentes, como busca em grafos, SAT-solvers, OR, Prolog etc. O problema normalmente é a otimização entre várias alternativas executáveis, e fico em dúvida se transformers são adequados para fazer isso. O papel da tecnologia de LLM parece mais próximo de converter descrições em linguagem natural em programas executáveis, e o Prolog, no fim das contas, foi projetado para NLP clássico, então é algo bem próximo.
• Tradução automática envolvia decodificação e busca gramatical complexas, mas agora usamos transformers em MT e uma decodificação muito mais simples, com quase nenhuma necessidade de busca. Talvez possamos chegar a um “começo completo” em que aprendamos heurísticas para busca de arquitetura de redes neurais (NAS) usando os melhores modelos preditivos atuais e procurar novos blocos neurais melhores do que transformers e Mamba.
• A frase “26,8% menos etapas de busca do que a busca A* padrão” mostra um desempenho um pouco melhor que o A*, mas ainda fica abaixo do estado da arte (SOTA) em Sokoban. O que exatamente há de impressionante neste artigo, e por que ele foi parar no Hacker News?
• Se transformers conseguem fazer planejamento, talvez AGI (inteligência artificial geral) precise apenas de um treinamento melhor.
• Para quem aprende melhor ouvindo, há um formato de audiolivro que resume este artigo.
• Este artigo me lembrou o paper sobre Neural Network Diffusion que estava ontem na página inicial do HN. No artigo anterior, treinaram um modelo para contornar as etapas de SGD; neste, contornam as etapas de busca do A*. Por outro lado, a escolha da heurística do A* para Sokoban não é boa. Joguei Sokoban por 20 minutos enquanto lia o artigo e senti que a heurística de busca é muito fraca, porque muitas vezes é preciso afastar as caixas do estado objetivo para conseguir avançar.
• Gostaria de saber se alguém mantém uma lista de algoritmos clássicos ou problemas NP-completos que agora são resolvidos melhor com deep learning.
• Sou bastante otimista quanto ao uso de heurísticas aprendidas em algoritmos discretos como A* ou busca Focal. Na maioria das bibliotecas modernas de otimização discreta, como o CPLEX, o que explica o desempenho são heurísticas e ajustes finos. Entendo menos o uso de abordagens de aprendizado ponta a ponta para substituir rotinas de busca ótima bem compreendidas, mas isso pode ser uma preocupação exagerada. Acho que os autores perderam essa oportunidade.