Au-delà d’A* : une meilleure planification grâce aux transformeurs

Beyond A* : une meilleure planification grâce aux transformeurs

• Les modèles de type transformeur ont permis d’importants progrès dans de nombreux domaines d’application, mais ils restaient en retrait par rapport aux méthodes traditionnelles de planification symbolique pour résoudre des tâches complexes de prise de décision.
• Les chercheurs présentent une méthode pour entraîner des transformeurs à résoudre des tâches de planification complexes et ont développé un modèle appelé Searchformer, capable de résoudre de manière optimale des puzzles Sokoban jamais vus auparavant en 93,7 % du temps, tout en utilisant jusqu’à 26,8 % d’étapes de recherche en moins que la recherche A* classique.
• Searchformer est un modèle transformeur encodeur-décodeur entraîné à prédire le comportement de recherche d’A*, puis affiné via expert iteration afin de générer des plans optimaux tout en effectuant moins d’étapes de recherche qu’A*.

Méthode d’entraînement et performances

• Dans la méthode d’entraînement, le comportement de recherche d’A* est représenté comme une séquence de tokens indiquant les moments où des états sont ajoutés puis retirés de l’arbre de recherche dans la planification symbolique.
• Dans une étude d’ablation sur la navigation dans des labyrinthes, Searchformer surpasse largement un modèle de référence qui prédit directement le plan optimal, avec une taille de modèle 5 à 10 fois plus petite et un jeu de données d’entraînement 10 fois plus réduit.
• Les chercheurs montrent que Searchformer est efficace, pour des tâches de prise de décision plus vastes et complexes comme Sokoban, à la fois pour augmenter la proportion de problèmes résolus et pour réduire le comportement de recherche nécessaire.

L’avis de GN⁺

• Cette recherche montre de nouvelles possibilités d’usage des modèles transformeurs en intelligence artificielle. En proposant une approche plus efficace que les méthodes symboliques existantes pour résoudre des tâches complexes de prise de décision, elle constitue une avancée importante qui élargit le champ d’application de l’IA.
• Le modèle Searchformer démontre des capacités de résolution plus rapides et plus efficaces en utilisant moins de ressources. Cela peut représenter un avantage majeur, en particulier pour déployer de l’IA dans des environnements aux ressources limitées.
• Cette étude suggère que les progrès de l’IA ne dépendent pas uniquement de davantage de données et de modèles toujours plus grands, mais peuvent aussi venir de méthodologies plus intelligentes et d’améliorations algorithmiques. C’est une approche très intéressante et utile du point de vue de la durabilité et de l’efficacité de la recherche en IA.

[GN⁺]

Avis Hacker News

• Il existe des recherches intéressantes sur l’utilisation des transformeurs pour la planification des mouvements robotiques. Faire déplacer un bras robotique d’un point à un autre sans heurter d’objet est un problème très difficile, car il est de haute dimension et continu. Les méthodes de planification précédentes demandaient beaucoup de calcul et n’étaient pas très bonnes. C’est l’une des raisons pour lesquelles les mouvements des robots paraissent « peu naturels » et pourquoi ils n’arrivent pas bien à accomplir nombre des tâches que nous attendons d’eux. Cette approche semble compétitive face aux autres méthodes de planification et propose une planification de trajectoire optimale plus rapide.
• Je me demande s’ils ont essayé une variante modifiée de l’algorithme J*, une version optimisée de l’algorithme A* pour les graphes de jeu / la recherche de chemin, avant de s’engager dans cette piste de recherche. Pour les personnes intéressées, il existe des informations sur "Game AI Pro 2".
• La planification est déjà bien traitée par des techniques existantes comme la recherche sur graphe, les solveurs SAT, l’OR, Prolog, etc. Le problème relève généralement de l’optimisation parmi plusieurs alternatives réalisables, et je me demande si les transformeurs sont adaptés à cela. Le rôle de la technologie LLM semble plus proche de la conversion de descriptions en langage naturel en programmes exécutables, et Prolog en est finalement très proche puisqu’il a été conçu pour le NLP classique.
• La traduction automatique impliquait autrefois un décodage grammatical complexe et de la recherche, mais on utilise désormais des transformeurs pour le MT, avec un décodage bien plus simple qui ne nécessite presque plus de recherche. Avec les meilleurs modèles prédictifs actuels, on pourrait peut-être atteindre un « nouveau départ complet » en apprenant des heuristiques pour la recherche d’architectures neuronales (NAS), puis en cherchant de nouveaux blocs neuronaux meilleurs que les transformeurs et Mamba.
• La formule « 26,8 % de étapes de recherche en moins que la recherche A* standard » montre des performances légèrement meilleures qu’A*, mais cela n’atteint pas l’état de l’art (SOTA) sur Sokoban. Je me demande ce qui est impressionnant dans cet article et pourquoi il est arrivé sur Hacker News.
• Si les transformeurs peuvent élaborer des plans, alors l’AGI (intelligence artificielle générale) n’aura peut-être besoin que d’une meilleure formation.
• Un format livre audio résumant cet article est proposé pour les apprenants auditifs.
• Cet article me rappelle celui sur la diffusion par réseau de neurones qui était hier sur la page d’accueil de HN. Dans l’article précédent, on entraînait un modèle qui contournait les étapes de SGD, et dans celui-ci il contourne les étapes de recherche A*. D’un autre côté, le choix d’heuristique A* pour Sokoban est mauvais. En jouant 20 minutes à Sokoban pendant la lecture de l’article, j’ai eu l’impression que l’heuristique de recherche était très insuffisante, car il faut souvent éloigner les caisses de l’état cible pour progresser.
• Je me demande si quelqu’un tient une liste des algorithmes classiques ou des problèmes NP-complets sur lesquels le deep learning obtient désormais de meilleurs résultats.
• Je suis très optimiste quant à l’usage d’heuristiques apprises dans des algorithmes discrets comme A* ou la recherche Focal. Dans la plupart des bibliothèques modernes d’optimisation discrète, ce qui explique les performances — comme avec CPLEX — ce sont les heuristiques et le réglage fin. Je comprends moins l’usage d’approches d’apprentissage de bout en bout pour remplacer des routines de recherche optimale bien comprises, mais c’est peut-être une inquiétude excessive. Je pense que les auteurs ont laissé passer cette occasion.