🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Ce papier présente le projet CayleyPy, qui combine l'apprentissage par renforcement avec des méthodes de distance de diffusion pour résoudre efficacement le problème du plus court chemin sur d'immenses graphes de Cayley, surmontant avec succès des outils classiques comme GAP, apportant de solides preuves pour la conjecture OEIS-A186783 concernant le diamètre du groupe symétrique, et établissant de nouvelles bornes théoriques tout en invitant la communauté à participer via des défis Kaggle.

Auteurs originaux : A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

Publié 2026-05-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La Grande Image : Trouver le Plus Court Chemin vers la Maison dans un Labyrinthe de Miroirs

Imaginez que vous êtes dans un labyrinthe gigantesque et infini. Mais ce n'est pas un labyrinthe normal avec des murs ; c'est un labyrinthe fait de règles. À chaque fois que vous faites un pas, vous suivez une règle spécifique qui change votre position. En mathématiques, cela s'appelle un graphe de Cayley.

L'objectif de ce papier est de résoudre un type spécifique de labyrinthe : le labyrinthe LRX. Ce labyrinthe est construit en utilisant les règles du mélange d'un jeu de cartes (ou d'une permutation de nombres).

Règle L : Déplacez tout d'un cran vers la gauche.
Règle R : Déplacez tout d'un cran vers la droite.
Règle X : Échangez les deux premiers éléments.

Le défi est le suivant : si vous commencez avec un jeu de cartes dans un ordre désordonné, quelle est la plus courte séquence de mouvements Gauche, Droite et Échange pour les remettre dans l'ordre parfait ?

Le Problème : Le Labyrinthe est Trop Grand pour les Humains (et les Anciens Ordinateurs)

Pour un petit jeu de cartes, un humain ou un programme informatique standard (comme le célèbre logiciel mathématique GAP) peut trouver la solution. Mais à mesure que le nombre de cartes ( $n$ ) augmente, le nombre d'arrangements possibles explose.

Pour $n=20$ , le labyrinthe est immense.
Pour $n=100$ , le labyrinthe est si grand qu'il possède plus de chemins qu'il n'y a d'atomes dans l'univers.

Les anciens programmes informatiques restent bloqués. Ils tentent de cartographier chaque chemin individuel, manquent de mémoire et abandonnent. Les auteurs voulaient voir si l'Intelligence Artificielle (IA) pouvait agir comme un explorateur intelligent pour trouver son chemin à travers ces labyrinthes massifs sans cartographier chaque centimètre.

La Solution : Enseigner à une IA à « Deviner » le Chemin

Les auteurs ont construit un système appelé CayleyPy RL. Imaginez que vous entraînez un robot à naviguer dans le labyrinthe. Ils ont utilisé une méthode appelée Apprentissage par Renforcement (RL).

Voici comment ils ont entraîné le robot, en utilisant une analogie simple :

1. Le « Échauffement » (Distance de Diffusion)
Imaginez que vous laissez tomber une goutte d'encre dans un verre d'eau. L'encre se répand de manière aléatoire. Si vous voulez savoir à quelle distance un endroit spécifique se trouve du centre, vous pouvez voir combien de temps il faut à l'encre pour l'atteindre.

L'IA a d'abord appris en observant des millions de « marches aléatoires » (comme la propagation de l'encre). Elle ne connaissait pas le plus court chemin, mais elle avait développé une « sensation » de distance. Elle savait : « Si je suis ici, il faut généralement environ 50 étapes aléatoires pour rentrer à la maison. »
Cela a donné à l'IA une carte approximative, mais elle n'était pas parfaite.

2. L'« Entraînement Intelligent » (Apprentissage par Renforcement)
Ensuite, ils ont appris à l'IA à être plus intelligente. Au lieu de simplement deviner en se basant sur des marches aléatoires, ils ont utilisé une technique appelée Deep Q-Learning.

Imaginez que l'IA joue à un jeu où elle reçoit une « pénalité » pour chaque pas qu'elle fait. Elle veut atteindre la ligne d'arrivée avec le moins de pénalités possible.
L'IA a essayé différents mouvements, a vu lesquels l'ont rapprochée de l'objectif, et a ajusté son cerveau (réseau de neurones) pour faire de meilleures prédictions.
L'Innovation : Ils ont combiné l'intuition de la « propagation de l'encre » avec la logique du « jeu ». Cela a aidé l'IA à éviter de rester coincée dans des impasses (minima locaux) qui piègent habituellement les algorithmes plus simples.

3. La « Recherche en Faisceau » (L'Équipe d'Explorateurs)
C'est la partie la plus critique. Imaginez que vous envoyez un seul explorateur dans le labyrinthe. S'il prend un mauvais tournant, vous perdez.

Au lieu de cela, les auteurs ont envoyé une équipe d'explorateurs (un « faisceau »).
À chaque intersection, l'équipe se divise. Ils gardent les 10 000 chemins les plus prometteurs et jettent les mauvais.
En maintenant une équipe énorme (des millions de chemins dans certains cas), l'IA s'assure que même si la plupart des explorateurs se perdent, au moins l'un d'eux trouve le chemin le plus court parfait.

Le « Tour de Magie » (Le Astuce X)

Les auteurs ont découvert un petit raccourci amusant. Dans leur code, ils ont ajouté une seule ligne de logique :

Si les deux premières cartes sont déjà dans le bon ordre, ne les échangez pas.

Cela semble évident pour un humain, mais pour un ordinateur, cela a changé la donne. Cette petite règle, qu'ils ont appelée l'« astuce X », a permis à leur IA de résoudre des labyrinthes avec 100 cartes ( $n=100$ ).

Sans l'astuce : L'IA ne pouvait gérer qu'environ 40 cartes.
Avec l'astuce : Elle a géré plus de 100 cartes, battant l'ancien logiciel informatique (GAP) qui plantait autour de 20 cartes.

Ce qu'ils ont Démontré ? (La Partie Mathématique)

Au-delà de la simple construction d'un solveur rapide, ils ont utilisé leur IA pour faire des découvertes sur les mathématiques de ces labyrinthes :

La Conjecture du « Nombre de Dieu » : Il existe une hypothèse célèbre en mathématiques selon laquelle le mélange le plus difficile possible de $n$ cartes nécessite exactement $n(n-1)/2$ mouvements. L'IA a testé cela pour de grands nombres et n'a jamais trouvé de mélange plus difficile que cela. Cela soutient fortement l'idée que cette formule est la limite absolue.
Le Mélange « Le Plus Long » : Ils ont identifié le seul mélange le plus chaotique possible (le « plus long élément ») et ont prouvé exactement comment le décomposer en mouvements.
Nouvelles Bornes : Ils ont prouvé mathématiquement que le labyrinthe ne peut pas être plus petit qu'une certaine taille et ne peut pas être plus grand qu'une autre taille, réduisant considérablement la réponse.
La Forme du Labyrinthe : Ils ont découvert que si l'on compte combien de mélanges existent à chaque distance du départ, les nombres ne suivent pas une courbe en cloche parfaite (comme une distribution normale). Au lieu de cela, ils suivent une forme étrange et asymétrique appelée distribution de Gumbel.

Les Résultats : IA contre la Vieille Garde

Le papier compare leur nouvelle méthode d'IA au système d'algèbre informatique standard GAP :

GAP : Peut résoudre jusqu'à ~20 cartes. Cela prend des heures ou des jours. Les chemins qu'il trouve sont souvent longs et inefficaces.
CayleyPy RL (IA) : Peut résoudre jusqu'à ~100 cartes. C'est beaucoup plus rapide. Il trouve des chemins très proches du chemin théoriquement le plus court possible.

Résumé

Les auteurs ont créé un système d'IA intelligent qui traite les problèmes mathématiques complexes comme un gigantesque labyrinthe. En combinant des devinettes aléatoires avec un apprentissage intelligent et en envoyant une « équipe » massive d'explorateurs virtuels, ils peuvent naviguer dans des labyrinthes trop grands pour les ordinateurs traditionnels. Ils ont même trouvé un petit « code de triche » (l'astuce X) qui leur permet de résoudre des problèmes 5 fois plus grands qu'auparavant, tout en démontrant simultanément de nouveaux faits mathématiques sur la structure de ces labyrinthes.

Ils ont également mis leur code et leurs défis sur une plateforme appelée Kaggle, invitant d'autres personnes à essayer de battre leurs records et à aider à résoudre des versions encore plus difficiles de ces énigmes.

Résumé technique : CayleyPy RL : Recherche de chemin et apprentissage par renforcement sur les graphes de Cayley

Énoncé du problème
L'article aborde le problème de la recherche de chemin sur des graphes de Cayley finis extrêmement grands, en se concentrant spécifiquement sur le groupe symétrique $S_n$ généré par des décalages cycliques gauches ( $L$ ), des décalages cycliques droits ( $R$ ) et une transposition des deux premiers éléments ( $X$ ). Cette configuration, connue sous le nom de graphe de Cayley LRX, correspond à la séquence OEIS A186783. Le défi mathématique central consiste à décomposer un élément du groupe en le produit le plus court possible de générateurs (trouver le chemin le plus court dans le graphe). Ce problème est NP-difficile pour les graphes de Cayley finis génériques. Les systèmes classiques d'algèbre informatique, tels que GAP, reposent sur l'algorithme de Schreier-Sims, qui produit souvent des chemins exponentiellement longs et échoue à gérer des groupes dont la taille dépasse $10^{30}$ (environ $n \approx 20$ pour $S_n$ ). Les auteurs visent à développer des approches efficaces basées sur l'intelligence artificielle capables de traiter des graphes d'une taille allant jusqu'à $10^{70}$ (par exemple, $n \approx 40$ à $100$) tout en produisant des chemins quasi optimaux ou optimaux.

Méthodologie
Les auteurs proposent une méthodologie hybride combinant l'apprentissage par renforcement (RL), spécifiquement le Deep Q-Learning (DQN), avec une stratégie de pré-entraînement basée sur les distances de diffusion.

Cadre d'apprentissage par renforcement : Le problème de recherche de chemin est formulé comme la recherche du chemin le plus court depuis un état $s$ vers l'élément identité $e$ . Cela est modélisé à l'aide de l'équation de Bellman, où la fonction de distance $d(s)$ satisfait $d(s) = 1 + \min_{t \in N(s)} d(t)$ . Le DQN standard est adapté pour approximer cette fonction de valeur à l'aide de réseaux de neurones.
Pré-entraînement par distance de diffusion : Pour résoudre le problème de la « récompense sparse » et du bruit inhérent à l'initialisation standard du DQN, les auteurs introduisent une phase de « mise en route ». Ils génèrent des données d'entraînement via des marches aléatoires (diffusion) partant de la cible. Un réseau de neurones est d'abord entraîné à prédire le nombre d'étapes de ces marches aléatoires (distance de diffusion).
DQN modifié : Le réseau pré-entraîné est ensuite affiné à l'aide d'un algorithme DQN modifié. Crucialement, les cibles de mise à jour de Bellman sont tronquées en fonction de l'étape temporelle $k$ à laquelle un état a été visité pour la première fois lors de la génération de la marche aléatoire. Cela empêche le réseau de surestimer les distances et stabilise l'entraînement.
Recherche en faisceau guidée : Une fois le réseau de neurones entraîné pour estimer les distances, il sert de fonction heuristique pour un algorithme de recherche en faisceau. La recherche en faisceau maintient un nombre fixe ( $W$ ) des états les plus prometteurs à chaque étape, développe leurs voisins et sélectionne les $W$ meilleurs en fonction des prédictions du réseau. Cela évite de rester coincé dans des minima locaux, un mode de défaillance courant de la recherche gloutonne.
Le « X-trick » : Une modification heuristique spécifique aux générateurs LRX est introduite. Si les deux premiers éléments d'une permutation sont déjà triés, le générateur $X$ (qui les échange) est exclu de l'ensemble des voisins. Cette modification en une seule ligne réduit drastiquement l'espace de recherche et améliore les temps de mélange.
Non-retour en arrière : Les auteurs intègrent des contraintes de non-retour en arrière dans la génération de marches aléatoires et dans la recherche en faisceau afin de réduire la variance des estimations de distance et d'éviter la stagnation dans les minima locaux.

Contributions clés

Avancées algorithmiques : L'article présente une combinaison novatrice de pré-entraînement par distance de diffusion et de DQN modifié. Cette approche surmonte les limites du DQN standard (récompenses rares, cibles bruyantes) et surpasse les méthodes classiques.
Benchmarks de performance : Les méthodes proposées trouvent avec succès des chemins pour les graphes de Cayley LRX jusqu'à $n \approx 44$ sans connaissance préalable et jusqu'à $n \approx 100$ en utilisant le « X-trick ». Cela dépasse considérablement les capacités de GAP, limité à $n \approx 20$ . Les méthodes d'IA produisent des chemins plus courts et s'exécutent plus rapidement que GAP pour des $n$ comparables.
Résultats mathématiques et conjectures :
- Conjecture du diamètre : Les auteurs soutiennent fortement la conjecture OEIS-A186783 selon laquelle le diamètre du graphe de Cayley LRX est $n(n-1)/2$ . Ils l'ont vérifiée par force brute via BFS pour $n \le 15$ et par décomposition via IA pour $n$ allant jusqu'à 200 (via des défis Kaggle), ne trouvant aucune décomposition plus courte que la longueur conjecturée.
- Élément le plus long : Ils identifient un « élément le plus long » unique $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ et fournissent une décomposition explicite de longueur $n(n-1)/2$ .
- Bornes : L'article prouve une borne inférieure pour le diamètre de $n(n-1)/2 - n/2 - 1$ et une borne supérieure de $n(n-1)/2 + 3n$ via un algorithme constructif. Un algorithme empirique suggère une borne plus serrée de $n(n-1)/2 + n/2$ .
- Distribution de croissance : Des expériences numériques suggèrent que la fonction de croissance du graphe LRX suit une distribution de Gumbel asymétrique à gauche pour les grands $n$ , contrairement à la distribution gaussienne observée dans les graphes de transposition de voisins.
- Temps de mélange : Alors que les marches aléatoires standard ont des temps de mélange compris entre $O(n^3)$ et $O(n^3 \log n)$ , les auteurs conjecturent que les marches aléatoires modifiées avec le « X-trick » mélangent plus rapidement, avec une complexité temporelle de $O(n^2)$ .
- Spectre : Le spectre du graphe LRX semble suivre une distribution uniforme.
Open Source et crowdsourcing : Les auteurs ont publié le projet « CayleyPy » et créé des défis Kaggle pour externaliser les solutions de décomposition de l'élément le plus long et de recherche d'algorithmes optimaux, favorisant la collaboration entre les communautés d'IA et de mathématiques.

Résultats

Efficacité : Pour $n=20$ , GAP nécessite plus de 41 minutes pour trouver un chemin de longueur 217 944, tandis que la méthode par distance de diffusion trouve le chemin optimal de longueur 190 en moins de 4 minutes.
Évolutivité : Avec le « X-trick », le système a résolu des instances pour $n=100$ (taille du graphe $\approx 10^{157}$ ) en environ 8,5 heures sur un seul GPU, trouvant un chemin de longueur 16 632 (comparé au diamètre conjecturé de 4 950).
Performance du modèle : Des modèles simples comme les Perceptrons Multicouches (MLP) et le Gradient Boosting (CatBoost/XGBoost) surpassent souvent des architectures complexes comme les Transformers et les CNN pour cette tâche spécifique.
Recherche en faisceau : Le taux de réussite de la recherche d'un chemin dépend fortement de la largeur du faisceau, montrant une amélioration super-linéaire à mesure que la taille du faisceau augmente, analogue à « l'échange d'idées » au sein d'une communauté de recherche.

Signification
L'article affirme que les expériences computationnelles, en particulier celles exploitant l'IA, peuvent faire progresser considérablement la recherche mathématique sur les graphes de Cayley. Il démontre que les méthodes d'IA peuvent « surpasser » les systèmes classiques d'algèbre informatique tant en évolutivité (gestion de $n$ beaucoup plus grands) qu'en qualité de solution (trouvant des chemins plus courts, quasi optimaux). Ce travail comble le fossé entre la théorie des groupes théorique et l'IA pratique, fournissant des bornes rigoureuses, de nouvelles conjectures sur la croissance et les temps de mélange, et un cadre pour résoudre des problèmes de recherche de chemin dans des espaces d'états extrêmement vastes qui étaient auparavant intraitables. Les auteurs positionnent cela comme une étape vers l'application de l'IA à d'autres problèmes de planification complexes en science théorique.