💻 computer science

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

COAgents introduit un cadre multi-agents coopératif qui modélise l'espace de recherche du problème de routage de véhicules comme un graphe construit dynamiquement afin de séparer le contrôle de la recherche agnostique du problème du codage spécifique au domaine, atteignant ainsi des performances de pointe parmi les méthodes basées sur l'apprentissage sur les benchmarks VRPTW en réduisant considérablement l'écart avec les meilleures solutions connues.

Auteurs originaux : Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

Publié 2026-05-21

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas, Xiaorui Li, Zirui Zhou, Mao Kun

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

Imaginez que vous êtes responsable logistique cherchant à déterminer le moyen le plus efficace pour une flotte de camions de livraison de visiter 100 maisons différentes. Il s'agit d'un « problème de routage de véhicules » classique. Le hic ? Il existe tellement de routes possibles que même les supercalculateurs les plus rapides ne peuvent pas toutes les vérifier. C'est comme essayer de trouver le seul meilleur chemin à travers un labyrinthe immense et brumeux où chaque virage que vous prenez pourrait mener à une impasse.

Pendant des décennies, les humains ont résolu ce problème en rédigeant des manuels de règles stricts : « Si vous voyez une maison à gauche, tournez à droite. » Mais ces manuels sont fragiles. Si la disposition de la ville change légèrement, les règles s'effondrent, et les experts doivent passer des semaines à les réécrire.

Voici COAgents, un nouveau système créé par des chercheurs chez Huawei. Au lieu d'un manuel de règles rigide, COAgents utilise une équipe de trois « détectives IA » qui travaillent ensemble pour explorer le labyrinthe, apprendre de leurs erreurs et trouver de meilleurs chemins que jamais auparavant.

Voici comment cela fonctionne, en utilisant des analogies simples :

1. La carte du labyrinthe : le « graphe de recherche partiel »

Imaginez que l'IA ne regarde pas seulement la route actuelle ; elle dessine une carte de chaque chemin qu'elle a déjà essayé.

Nœuds (Les points) : Chaque point sur la carte représente un itinéraire de livraison spécifique que l'IA a testé.
Arêtes (Les lignes) : Les lignes reliant les points montrent comment l'IA est passée d'un itinéraire à l'autre (par exemple : « Nous avons échangé deux maisons sur l'itinéraire »).
La partie « partielle » : L'IA ne peut pas dessiner le labyrinthe entier infini, elle ne conserve donc qu'une carte « partielle » des parties intéressantes qu'elle a visitées jusqu'ici. Cette carte constitue la mémoire partagée de l'équipe.

2. Les trois agents IA

La magie opère parce que trois agents IA différents examinent cette carte et prennent des décisions différentes, tout comme une équipe sportive avec des rôles spécifiques :

L'éclaireur (Agent de sélection de nœud) :
- Rôle : « Quel itinéraire devrions-nous examiner ensuite ? »
- Analogie : Imaginez que vous êtes dans une bibliothèque avec des milliers de livres. L'éclaireur ne choisit pas un livre au hasard. Il examine votre « historique de lecture » (la carte) et dit : « Hé, cet itinéraire là-bas semble prometteur ; il est proche d'une bonne solution. Concentrons-nous sur celui-là. » Il empêche l'équipe de perdre du temps sur des impasses.
Le mécanicien (Agent de sélection de mouvement) :
- Rôle : « Comment améliorer cet itinéraire spécifique ? »
- Analogie : Une fois que l'éclaireur a choisi un itinéraire, le mécanicien intervient. Il dispose d'une boîte à outils de astuces (comme échanger deux arrêts ou réorganiser une rue). Il examine l'itinéraire actuel et dit : « Si nous échangeons ces deux maisons, le camion économise 5 minutes. Faisons cela ! » C'est l'expert des améliorations locales et mineures.
L'explorateur (Agent de saut) :
- Rôle : « Nous sommes coincés ! Essayons quelque chose de totalement nouveau. »
- Analogie : Parfois, l'éclaireur et le mécanicien restent bloqués dans une boucle, apportant de minuscules améliorations qui n'aident pas vraiment. Ils sont coincés dans une « vallée locale ». L'explorateur est l'agent qui dit : « Oubliez ce chemin. Sautons vers une partie complètement différente de la carte. » Il génère un tout nouvel itinéraire à partir de zéro en se basant sur ce qu'il a appris du passé, aidant l'équipe à échapper au piège et à trouver une meilleure vallée.

3. Comment ils travaillent ensemble

Le processus est une boucle continue :

L'éclaireur choisit un itinéraire sur la carte d'historique.
Le mécanicien tente de l'ajuster pour l'améliorer.
S'ils continuent d'ajuster sans beaucoup progresser, l'explorateur intervient, crée un itinéraire frais et l'ajoute à la carte.
L'équipe répète cela jusqu'à épuisement du temps disponible.

Pourquoi c'est une grande nouvelle

L'article affirme que cette approche basée sur une équipe est un changement de paradigme, en particulier pour des problèmes difficiles comme le VRPTW (où les camions ont des fenêtres de temps strictes, comme « doit arriver entre 14 h 00 et 14 h 30 »).

Battre le meilleur : Sur ces tests difficiles, COAgents a surpassé les meilleurs solveurs IA précédents avec une marge significative. Par exemple, avec 100 arrêts, il a réduit l'écart par rapport à la solution parfaite de 14 % par rapport au meilleur IA précédent, et de 44 % par rapport à une autre méthode de premier plan.
Apprentissage contre règles : Contrairement aux anciennes méthodes qui reposent sur des règles écrites par des humains, COAgents apprend comment chercher. Il n'a pas besoin qu'un humain lui dise comment résoudre un problème spécifique ; il détermine la meilleure stratégie en examinant son propre historique.
Adaptabilité : Parce que le « cerveau » (les agents) est séparé des « règles du jeu » (la disposition spécifique de la ville), vous pouvez facilement changer les règles du jeu (par exemple, passer des camions de livraison à la livraison par drone) sans reconstruire toute l'IA.

Le compromis

L'article est honnête sur un inconvénient : la vitesse.
Puisque COAgents dessine constamment sa carte, vérifie l'historique et exécute trois agents différents, il prend plus de temps à exécuter que certaines méthodes plus simples et plus rapides qui construisent un itinéraire une seule fois et s'arrêtent. Cependant, les auteurs soutiennent que pour les problèmes les plus difficiles où trouver la meilleure solution compte plus que la vitesse, ce temps supplémentaire en vaut la peine.

En résumé : COAgents est comme une équipe intelligente et collaborative d'explorateurs qui tient un journal détaillé de leur voyage. Au lieu de deviner aveuglément ou de suivre un manuel de règles statique, ils utilisent leur histoire partagée pour savoir quand creuser plus profondément, quand ajuster leur chemin et quand faire un bond géant vers un nouveau territoire, trouvant ainsi de meilleures solutions que quiconque auparavant.

Résumé Technique : COAgents – Cadre Multi-Agent pour les Problèmes de Routage

Énoncé du Problème

Les problèmes de routage de véhicules (VRP), y compris le problème de routage de véhicules à capacité limitée (CVRP) et le problème de routage de véhicules avec fenêtres de temps (VRPTW), sont centraux pour la logistique et la fabrication, mais restent intraitables computationnellement à grande échelle en raison de leur complexité combinatoire. Les méthodes heuristiques traditionnelles reposent sur des règles conçues à la main pour les améliorations locales et la diversification (sauts) afin d'échapper aux minima locaux. Cependant, ces ensembles de règles statiques manquent souvent de généralisation à travers des instances diverses, nécessitent une expertise de domaine étendue pour le réglage et ne peuvent pas s'adapter aux distributions de problèmes évolutives. Bien que des approches « Apprendre à Rechercher » (L2S) aient émergé, beaucoup se concentrent uniquement sur la sélection d'opérateurs ou les décisions basées sur l'état actuel, sans modéliser efficacement l'historique de recherche ou la structure plus large de l'espace de recherche.

Méthodologie : Le Cadre COAgents

Les auteurs proposent COAgents, un cadre multi-agent coopératif qui modélise le processus de recherche VRP comme une traversal de graphe. L'innovation centrale est le Graphe de Recherche Partiel (PSG), un sous-graphe construit dynamiquement où les nœuds représentent les solutions explorées et les arêtes représentent soit des mouvements locaux, soit des perturbations importantes (sauts).

1. Le Graphe de Recherche Partiel (PSG)

Le PSG sert de codage d'état conscient de l'historique. C'est un graphe dirigé et disjoint où :

Nœuds : Représentent les solutions individuelles rencontrées au cours de la recherche.
Arêtes : Représentent les mouvements de voisinage (affinements locaux) ou les sauts (grandes perturbations).
Structure : Le graphe se décompose en composantes connexes (échantillons), chacune explorant le voisinage d'un optimum local. Cette structure permet au système de suivre la trajectoire de la recherche et d'identifier des motifs dans l'exploration.

2. Architecture Multi-Agent

COAgents emploie trois agents appris opérant sur le PSG, partageant tous une colonne vertébrale neuronale commune composée de Réseaux de Convolution Graphique à Portes (GGCN) et de Transformers :

Agent de Sélection de Nœud (NSA) : Sélectionne une solution candidate (nœud) dans le PSG pour servir de solution courante pour la prochaine étape de recherche locale. Il priorise les régions prometteuses de l'espace de recherche basées sur les données historiques.
Agent de Sélection de Mouvement (MSA) : Prédit l'opérateur de voisinage (mouvement) le plus prometteur à appliquer à la solution sélectionnée, pilotant l'intensification locale.
Agent de Saut (JA) : Déclenché lorsque la recherche stagne (indiqué par des tentatives échouées répétées), cet agent génère une solution complètement nouvelle à partir de zéro basée sur l'historique de recherche. Contrairement aux opérateurs standards, l'Agent de Saut effectue un redémarrage appris pour échapper aux minima locaux et orienter la recherche vers des régions inexplorées.

3. Architecture du Modèle et Entraînement

Codage : Les solutions sont codées en caractéristiques de nœud ( $u_i$ ) capturant des attributs globaux (valeur de l'objectif, faisabilité) et des matrices de structure interne ( $V_i$ ). Des embeddings de position sont dérivés via des encodeurs de marche aléatoire pour la structure du PSG et des encodeurs spécifiques au problème pour la topologie de la solution.
Blocs Centraux : Le réseau utilise des couches GGCN entrelacées pour capturer les motifs structurels locaux au sein du PSG et des couches Transformer pour modéliser les dépendances à longue portée à travers tous les nœuds. Des modules spécifiques au problème de bout en bout (E2E) affinent la structure interne du problème combinatoire.
Entraînement :
- NSA et MSA : Entraînés conjointement comme des tâches de classification binaire pour identifier la solution la plus proche de l'optimum et le meilleur mouvement suivant, respectivement, en minimisant l'entropie croisée binaire conjointe.
- Agent de Saut : Entraîné séparément pour prédire une matrice d'adjacence stochastique représentant une nouvelle solution. Il est entraîné contre un ensemble de solutions de référence quasi-optimales pour réduire l'ambiguïté des étiquettes.
Inférence : Le cadre exécute une boucle où le NSA sélectionne un nœud, le MSA sélectionne un mouvement, et le PSG est mis à jour. Si une stagnation se produit, le JA est invoqué. Cela continue jusqu'à ce qu'un budget computationnel (temps ou limite de nœuds) soit atteint.

Contributions Clés

Agents Appris Novateurs : Introduction de l'Agent de Sélection de Nœud et de l'Agent de Saut aux côtés d'un Agent de Sélection de Mouvement. Ces agents remplacent collectivement les règles conçues à la main, permettant des politiques de décision adaptatives et pilotées par les données pour la sélection de solutions, l'application d'opérateurs et la diversification.
Architecture Unifiée et Partage de Poids : Tous les agents partagent une colonne vertébrale neuronale commune, facilitant un entraînement efficace en données, une transférabilité vers de nouvelles variantes de problèmes et une réduction du besoin de réglage par des experts.
Représentation du Graphe de Recherche Partiel : Formalisation du PSG comme un codage d'état général et conscient de l'historique qui guide les décisions des agents, distinguant cette approche des méthodes qui reposent uniquement sur l'état actuel.
Cadre Adaptatif aux Solveurs et aux Problèmes : COAgents s'enroule autour des routines de recherche locale existantes et des solveurs neuronaux, les améliorant avec des politiques adaptatives qui s'adaptent de manière transparente à différentes variantes de VRP.

Résultats Expérimentaux

Le cadre a été évalué sur des benchmarks CVRP et VRPTW utilisant 10 000 instances d'entraînement et des ensembles de tests standards (par exemple, 1 000 instances VRPTW).

Performance VRPTW : COAgents a établi un nouvel état de l'art parmi les méthodes basées sur l'apprentissage.
- Il a réduit l'écart d'optimalité par rapport aux meilleures solutions connues de 14 % (à N=100) et 44 % (à N=50) par rapport au solveur neuronal le plus puissant (POMO).
- Il a réduit l'écart de 21 % (N=100) et 40 % (N=50) par rapport à la Recherche de Voisinage à Grande Échelle Adaptative (ALNS).
- Il a surpassé tous les baselines neuronaux, OR-Tools et ALNS sur l'ensemble de tests VRPTW.
Performance CVRP : COAgents est resté compétitif avec les baselines d'apprentissage à la recherche de l'état de l'art, démontrant son efficacité même avec un module de codage spécifique au problème compact.
Étude d'Ablation : La suppression de l'Agent de Saut a presque doublé l'écart d'optimalité (de 3,7 % à 7,8 %), soulignant son rôle critique pour échapper aux minima locaux. Les agents de sélection de nœud et de mouvement ont également contribué de manière significative à la performance.
Comparaison avec ALNS : Même lorsque l'ALNS avait accès à un plus grand pool d'opérateurs conçus à la main (incluant 27 paires supplémentaires de destruction-réparation), COAgents l'a constamment surpassé, validant la supériorité des politiques apprises par rapport aux heuristiques statiques.

Importance et Revendications

L'article revendique que COAgents représente un changement significatif des heuristiques statiques et conçues à la main vers des systèmes multi-agents adaptatifs qui apprennent de l'historique de recherche. En modélisant explicitement l'espace de recherche comme un graphe et en utilisant un Graphe de Recherche Partiel, le cadre permet aux agents de prendre des décisions éclairées concernant l'intensification et la diversification que les méthodes traditionnelles ne peuvent pas atteindre.

Les auteurs positionnent COAgents comme une alternative convaincante aux heuristiques classiques et aux méthodes existantes d'apprentissage pour la construction/recherche, en particulier pour des problèmes complexes comme le VRPTW où la généralisation et l'adaptabilité sont cruciales. Tout en reconnaissant que l'implémentation Python actuelle est plus lente que les heuristiques basées sur C/C++ (comme LKH3 et HGS) et que la mise à l'échelle vers des instances très grandes reste un défi en raison des coûts d'attention quadratiques, le cadre démontre que le contrôle de recherche appris et conscient de l'historique peut réduire considérablement l'écart par rapport aux meilleures solutions connues dans les problèmes de routage.