Más allá de A*: una mejor planificación con transformadores

Más allá de A*: una mejor planificación con transformadores

• Los modelos de transformadores han logrado grandes avances en diversos campos de aplicación, pero se han quedado atrás frente a los métodos tradicionales de planificación simbólica a la hora de resolver tareas complejas de toma de decisiones.
• Los investigadores presentan una forma de entrenar transformadores para resolver tareas complejas de planificación y desarrollaron un modelo llamado Searchformer, que resuelve de forma óptima acertijos de Sokoban no vistos previamente en el 93.7% de los casos, usando hasta 26.8% menos pasos de búsqueda que la búsqueda A* convencional.
• Searchformer es un modelo transformador codificador-decodificador entrenado para predecir el comportamiento de búsqueda de A* y afinado mediante iteración experta, de modo que genera planes óptimos mientras realiza menos pasos de búsqueda que A*.

Método de entrenamiento y rendimiento

• En el método de entrenamiento, el comportamiento de búsqueda de A* se representa como una secuencia de tokens que indica cuándo se agregan y eliminan estados del árbol de búsqueda durante la planificación simbólica.
• En un estudio de ablación sobre navegación en laberintos, Searchformer supera ampliamente a un modelo base que predice directamente planes óptimos, con un tamaño de modelo entre 5 y 10 veces menor y un conjunto de entrenamiento 10 veces más pequeño.
• Los investigadores muestran que Searchformer también es eficaz para tareas de toma de decisiones más grandes y complejas, como Sokoban, al mejorar la proporción de problemas resueltos y acortar el comportamiento de búsqueda.

Opinión de GN⁺

• Esta investigación muestra una nueva posibilidad de uso para los modelos de transformadores en el campo de la inteligencia artificial. Al proponer un enfoque más eficiente que los métodos simbólicos tradicionales para resolver tareas complejas de toma de decisiones, representa un avance importante que amplía el alcance de aplicación de la IA.
• El modelo Searchformer demuestra una capacidad de resolución de problemas más rápida y eficiente usando menos recursos. Esto podría ser una gran ventaja, especialmente al implementar IA en entornos con recursos limitados.
• Este estudio sugiere que el avance de la tecnología de IA no depende únicamente de más datos y modelos más grandes, sino que también puede lograrse mediante metodologías inteligentes y mejoras algorítmicas. Es un enfoque muy interesante y valioso desde la perspectiva de la sostenibilidad y la eficiencia en la investigación en IA.

[GN⁺]

Opiniones en Hacker News

• Hay una investigación interesante sobre el uso de transformadores para la planificación de movimiento de robots. Mover un brazo robótico de un punto a otro sin golpear objetos es un problema muy difícil, ya que es de alta dimensión y continuo. Los métodos de planificación anteriores requerían mucho cómputo y no eran muy buenos. Esa es una de las razones por las que el movimiento de los robots se ve "poco natural" y por las que no pueden realizar bien muchas de las tareas que queremos. Este enfoque parece competitivo frente a otros métodos de planificación y propone una planificación de trayectorias óptimas más rápida.
• Me pregunto si probaron el algoritmo J* modificado, una versión optimizada del algoritmo A* para grafos de juego/búsqueda de rutas, antes de comenzar esta línea de investigación. Para quienes estén interesados, hay información sobre "Game AI Pro 2".
• La planificación ya se maneja bien con técnicas existentes como búsqueda en grafos, SAT-solvers, OR, Prolog, etc. El problema suele ser la optimización entre varias alternativas viables, y dudo que los transformadores sean adecuados para eso. El papel de la tecnología LLM parece estar más cerca de convertir descripciones en lenguaje natural en programas ejecutables, y Prolog, al final, fue diseñado para NLP clásico, así que está muy cerca.
• La traducción automática solía implicar descifrado gramatical complejo y búsqueda, pero ahora usa transformadores para MT y una decodificación mucho más simple que casi no necesita búsqueda. Tal vez podamos llegar a un "inicio completo" en el que se aprenda una heurística para la búsqueda de arquitectura de redes neuronales (NAS) usando los mejores modelos predictivos actuales, y se busquen nuevos bloques neuronales mejores que los transformadores y Mamba.
• La frase "26.8% fewer search steps than standard A* search" muestra un rendimiento apenas mejor que A*, pero en Sokoban no alcanza el estado del arte (SOTA). Me pregunto qué es lo impresionante de este artículo y por qué llegó a Hacker News.
• Si los transformadores pueden hacer planificación, entonces AGI (inteligencia artificial general) quizá solo necesite mejor entrenamiento.
• Para quienes aprenden mejor escuchando, se ofrece un formato de audiolibro que resume este artículo.
• Este artículo me recuerda al paper sobre Neural Network Diffusion que estuvo ayer en la portada de HN. En el paper anterior, entrenaban un modelo para saltarse los pasos de SGD, y en este paper se saltan los pasos de búsqueda A*. Por otro lado, la elección de la heurística de A* para Sokoban no es buena. Mientras leía el paper, jugué Sokoban durante 20 minutos y sentí que la heurística de búsqueda era muy deficiente, porque para avanzar a menudo hay que mover cajas lejos del estado objetivo.
• Me pregunto si alguien mantiene una lista de algoritmos clásicos o problemas NP-completos que ahora se resuelven mejor usando deep learning.
• Soy muy optimista sobre el uso de heurísticas aprendidas en algoritmos discretos como A* o búsqueda focal. En la mayoría de las bibliotecas modernas de optimización discreta, como CPLEX, lo que explica el rendimiento son las heurísticas y el ajuste. Entiendo menos el uso de enfoques de aprendizaje de extremo a extremo para reemplazar rutinas de búsqueda óptima bien entendidas, aunque quizá esa preocupación sea exagerada. Creo que los autores dejaron pasar esa oportunidad.