🤖 AI

Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics

Cet article propose un cadre de planification épistémique multi-agents évolutif qui intègre des heuristiques dérivées de réseaux de neurones sur graphes pour guider efficacement la recherche à travers des structures de Kripke complexes, améliorant de manière significative les performances du solveur par rapport aux bases de référence existantes.

Auteurs originaux : Giovanni Briglia, Francesco Fabiano, Stefano Mariani

Publié 2026-02-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Giovanni Briglia, Francesco Fabiano, Stefano Mariani

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 essayez de résoudre un puzzle massif et multicouche. Mais voici le rebondissement : vous ne vous contentez pas de déplacer des pièces sur un plateau ; vous essayez aussi de comprendre ce que d'autres personnes dans la pièce pensent des pièces, ce qu'elles pensent que vous pensez, et ce qu'elles pensent que vous pensez qu'elles pensent.

C'est le monde de la Planification Épistémique Multi-Agents (MEP). Il s'agit d'un type de planification informatique utilisé lorsque des groupes d'agents intelligents (comme des robots ou des bots logiciels) doivent se coordonner, mais qu'ils doivent le faire tout en gérant leurs propres croyances et ce qu'ils savent des esprits les uns des autres.

Le problème ? Ce jonglage mental crée un « espace de recherche » si vaste et complexe que les ordinateurs sont submergés. C'est comme essayer de trouver un grain de sable spécifique sur chaque plage de la Terre, un par un, sans aucune carte.

La Solution : Un « GPS Intelligent » pour les Croyances

Les auteurs de cet article, Giovanni Briglia, Francesco Fabiano et Stefano Mariani, proposent une nouvelle façon d'aider les ordinateurs à naviguer dans ce chaos. Ils ont construit un système qui utilise des Réseaux de Neurones sur Graphes (GNN) pour agir comme un « GPS Intelligent » pour ces puzzles complexes de croyances.

Voici comment ils ont procédé, décomposé en étapes simples :

1. La Carte est une Toile, pas une Liste

Dans la planification traditionnelle, l'ordinateur voit le monde comme une liste de faits. Mais dans ce monde « épistémique », l'état du système est mieux décrit comme une toile de connexions (appelée structure de Kripke). Imaginez une toile d'araignée où chaque nœud est une réalité possible, et les fils qui les relient représentent ce que les différents agents croient les uns des autres.

Le Défi : Les outils informatiques standards sont mauvais pour lire ces toiles. Ils essaient de compter chaque nœud, ce qui prend un temps infini.
La Correction : Les auteurs ont utilisé des GNN. Considérez un GNN comme un type spécial de caméra qui regarde l'ensemble de la toile d'un coup. Au lieu de compter les nœuds, il « ressent » la forme et la structure de la toile pour comprendre à quel point elle est proche de la solution.

2. Apprendre par l'Expérience (La Phase d'Entraînement)

Avant que l'ordinateur puisse résoudre de nouveaux puzzles, il doit apprendre à quoi ressemble un « bon » chemin.

La Méthode : Les chercheurs ont créé une « salle de sport d'entraînement ». Ils ont laissé leur logiciel de planification parcourir des milliers de puzzles d'entraînement.
La Leçon : À mesure que le logiciel explorait, il enregistrait chaque étape franchie et la distance qui séparait cette étape de la ligne d'arrivée.
Le Résultat : Ils ont injecté ces données dans le GNN. Le GNN a appris à regarder une toile de croyances complexe et à deviner instantanément : « Cela ressemble à une situation où nous sommes à 5 étapes du but », ou « Cela ressemble à une impasse ».

3. L'Heuristique (L'Intuition)

En informatique, une « heuristique » est une règle empirique ou un pressentiment qui aide à prendre des décisions plus rapidement.

L'Ancienne Méthode : L'ordinateur explorait aveuglément tous les chemins possibles jusqu'à ce qu'il ait de la chance (comme une personne les yeux bandés touchant tous les murs dans un labyrinthe).
La Nouvelle Méthode : Le GNN agit comme un guide. Avant que l'ordinateur ne fasse un pas, il demande au GNN : « Cette direction est-elle prometteuse ? ». Le GNN donne un score. Si le score est élevé, l'ordinateur s'y plonge. Si le score est bas, il ignore ce chemin. Cela évite à l'ordinateur de perdre du temps sur des impasses.

Ce Qu'Ils Ont Trouvé (Les Résultats)

L'équipe a testé leur nouveau « GPS Intelligent » (qu'ils ont nommé deep) contre les anciennes méthodes aveugles sur plusieurs domaines de puzzles standards :

Chaîne d'Assemblage : Des robots construisant des choses ensemble.
Collaboration : Des agents déplaçant des boîtes et communiquant entre eux.
Grapevine (Le Potin) : Des agents partageant des secrets dans différentes pièces.

Le Résultat :

Moins d'Étapes : Le planificateur guidé par le GNN a dû examiner beaucoup moins de possibilités pour trouver la solution. Dans certains cas, il a exploré 10 à 20 fois moins de « pièces » dans le labyrinthe que la méthode aveugle.
Meilleur sur les Sujets Difficiles : Bien qu'il n'ait pas été parfait pour chaque puzzle (certains étaient simplement trop complexes), il a systématiquement surpassé les anciennes méthodes en trouvant des solutions plus rapidement et plus efficacement.
Généralisation : Même lorsqu'ils ont entraîné le GNN sur un type de puzzle et testé sur un type complètement différent, il fonctionnait toujours bien, montrant qu'il avait appris la logique de la toile, et non seulement les réponses spécifiques.

Le Bémol (Limites)

Les auteurs sont honnêtes quant aux limites actuelles :

Vitesse : Bien que le GNN aide l'ordinateur à penser plus intelligemment, le GNN lui-même prend un peu de temps pour s'exécuter. Actuellement, la partie « réflexion » est plus lente que la partie « recherche ». C'est comme avoir un navigateur brillant qui donne d'excellentes directions, mais qui met du temps à parler.
Ingénierie : Les auteurs notent que si le GCNN pouvait s'exécuter plus rapidement (en utilisant de meilleures astuces de matériel informatique), l'ensemble du système serait encore plus puissant.

L'Essentiel

Cet article ne prétend pas avoir résolu tous les problèmes d'IA. Il prouve plutôt que enseigner aux ordinateurs à « voir » la structure des croyances en utilisant des Réseaux de Neurones sur Graphes est un moyen puissant de rendre la planification multi-agents complexe évolutive. Cela transforme une recherche aveugle et épuisante en un voyage guidé et intelligent.

Résumé Technique : Mise à l'échelle de la Planification Épistémique Multi-Agent via des Heuristiques Dérivées de GNN

Énoncé du Problème

La Planification Épistémique Multi-Agent (MEP - Multi-Agent Epistemic Planning) est un cadre pour raisonner sur les actions physiques et les croyances de plusieurs agents. Contrairement à la planification classique, la MEP nécessite que les états soient représentés sous forme de structures de Kripke (graphes orientés, dirigés et étiquetés) pour capturer les relations complexes de croyance et de connaissance d'ordre supérieur. Cette représentation introduit deux défis primaires qui entravent la scalabilité :

Complexité Intrinsèque : Appliquer des transitions et évaluer des formules au sein des états épistémiques (e-states) est plus exigeant en termes de calcul que dans la planification classique.
Manque d'Heuristiques Efficaces : Les solveurs MEP existants reposent souvent sur une recherche non informée (par exemple, la recherche en largeur - BFS) car les heuristiques efficaces sont rares. À mesure que la longueur du plan augmente, l'espace de recherche croît exponentiellement, menant à l'intractabilité. Bien que des travaux récents (par exemple, H-EFP) aient tenté d'intégrer des heuristiques en utilisant des constructions de planification traditionnelles comme les graphes de planification, peu d'approches traitent la scalabilité de la MEP par des méthodes fondées sur les données.

Méthodologie

Les auteurs proposent une approche fondée sur les données pour générer des heuristiques pour la MEP en utilisant des Réseaux de Neurones sur Graphes (GNN). L'idée centrale est d'entraîner un régresseur basé sur un GNN pour approximer l'« heuristique parfaite » — estimant la distance entre un état épistémique donné et l'état cible le plus proche.

1. Représentation et Encastrement des États (Embedding)

Puisque les e-states sont naturellement structurés en graphes (modèles de Kripke), les GNN sont sélectionnés pour leur capacité à capturer les structures relationnelles. Le papier examine trois stratégies pour encoder les « mondes » (nœuds) au sein d'une structure de Kripke en vecteurs numériques adaptés à l'entrée d'un GNN :

Mapping d'ID Symbolique : Assigne des entiers séquentiels aux mondes basés sur l'ordre de génération. C'est peu coûteux en calcul mais cela perd la similitude sémantique entre les mondes et n'est pas invariant d'une exécution à l'autre.
Encodage par Hachage : Applique une fonction de hachage aux interprétations des mondes et aux indices de répétition. Cela garantit des identifiants cohérents entre les exécutions et offre un équilibre entre la préservation de l'information et l'efficacité computationnelle.
Encodage par Masque de Bits (Bitmask) : Représente les mondes sous forme de vecteurs binaires encodant les fluents et les indices de répétition. Cela préserve l'information logique mais entraîne des coûts de calcul plus élevés et nécessite des modèles plus larges pour converger.

Pour garantir que les heuristiques se généralisent à travers différentes conditions de but, les auteurs étendent l'encastrement de l'état pour inclure un encodage compact du but. Cela crée un graphe unifié où les « nœuds d'état » et les « nœuds de but » sont connectés, permettant au modèle d'apprendre les dépendances entre l'état actuel et les conditions de but spécifiques.

2. Pipeline de Génération de Données

Les données d'entraînement sont générées hors ligne en utilisant une Recherche en Profondeur (DFS) modifiée au sein du planificateur deep (une réimplémentation du planificateur EFP de pointe).

Le planificateur explore l'espace d'état jusqu'à une limite de profondeur.
Lorsqu'un but est atteint, l'algorithme effectue une remontée (backtracking), assignant à chaque e-état visité une étiquette correspondant à sa distance vers le but le plus proche.
Pour gérer l'explosion combinatoire de l'espace de recherche, le processus de génération emploie l'élagage probabiliste des branches, un ordonnancement aléatoire des actions et des vérifications de doublons d'états.
Les états inaccessibles sont écartés pour éviter les étiquettes fallacieuses, et la distribution des classes de distance est équilibrée pour éviter les biais vers des plans courts.

3. Architecture du Modèle

Le régresseur neuronal est implémenté dans PyTorch en utilisant PyTorch Geometric. L'architecture se compose de :

Encastrement Bitwise : Les identifiants de nœuds (vecteurs de bits) et les attributs d'arêtes sont projetés dans des plongements denses via des MLP (Perceptrons Multicouches).
Passage de Messages Relationnels : Deux couches de GINEConv (Graph Isomorphism Network avec Convolution d'Arêtes) agrègent les informations des voisins, incorporant explicitement les attributs d'arêtes pour gérer les dépendances modales hétérogènes.
Résumé au Niveau du Graphe : Le pooling moyen (mean pooling) agrège les encastrements des nœuds en une représentation de graphe de taille fixe.
Tête de Régression Résiduelle Profonde : Une séquence de blocs résiduels traite l'encastrement du graphe, produisant une estimation de distance normalisée via une fonction sigmoïde.

4. Intégration de la Recherche

Le GNN entraîné est intégré dans le pipeline de planification pour guider une Recherche Prioritaire par Heuristique (HFS - Heuristics-First Search). Les auteurs évaluent également une variante, HFS*, qui augmente l'heuristique prédite $h(s)$ par la profondeur de recherche $d(s)$ pour former un score total $f(s) = h(s) + d(s)$ , inspiré de l'algorithme A*.

Contributions Clés

Le papier expose quatre contributions principales :

Comparaison des Encastrements : Une définition formelle et une comparaison empirique de trois encastrements de structures de Kripke (ID Symbolique, Hash, Bitmask) pour l'entrée GNN, identifiant l'encodage par hachage comme le compromis le plus efficace.
Pipeline Automatisé : Un système entièrement automatisé pour générer des données d'entraînement (paires état-distance) et entraîner le régresseur GNN spécifiquement pour le contexte MEP.
Intégration : L'intégration du régresseur GNN dans le planificateur deep pour évaluer les e-states et guider le processus de recherche.
Évaluation Complète : Un benchmarking approfondi de l'approche par rapport à la recherche non informée (BFS) et aux planificateurs basés sur des heuristiques existants (H-EFP) à travers plusieurs domaines standards.

Résultats Expérimentaux

L'évaluation a été réalisée sur des benchmarks MEP standards (ex: Collaboration et Communication, Communication Sélective, Grapevine) en utilisant un délai d'attente (timeout) de 600 secondes.

Scalabilité vs Recherche Non Informée : La recherche guidée par GNN a considérablement réduit le nombre de nœuds expansés par rapport à la recherche en largeur (BFS) dans la plupart des domaines. Par exemple, dans le domaine Collaboration et Communication (CC), l'approche GNN a expansé environ 65 nœuds en moyenne contre 610 pour BFS, tout en résolvant le même nombre d'instances.
Stratégie de Recherche : La variante HFS* (combinant l'heuristique et la profondeur) a surpassé le HFS standard, résolvant environ 32 % d'instances de plus et réduisant le nombre de nœuds expansés.
Généralisation : Les modèles entraînés sur des données regroupées de plusieurs domaines (CC et GR) ont démontré une capacité à se généraliser à des domaines non vus, surpassant la base de référence BFS en termes d'expansion de nœuds.
Comparaison avec H-EFP : L'approche GNN est au niveau des meilleures heuristiques individuelles du planificateur H-EFP (spécifiquement l'heuristique $S\_PG$ ), résolvant 85,33 % des instances de test contre la plage de 49 à 82 % de H-EFP selon l'heuristique utilisée.
Limitations de Temps d'Exécution : Le papier note que bien que le GNN réduise l'espace de recherche (nœuds expansés), l'implémentation actuelle manque d'optimisations d'inférence par lots (ex: batching CUDA). Par conséquent, les temps de résolution bruts ne sont pas encore compétitifs avec les heuristiques traditionnelles, bien que les auteurs soutiennent que l'informativité de l'heuristique est la métrique primaire de scalabilité dans ce contexte.

Signification et Revendications

Les auteurs positionnent ce travail comme une étape fondamentale dans l'intégration de l'Apprentissage Automatique avec la Planification Épistémique Multi-Agent. Ils affirment que :

Rareté des Heuristiques : La MEP souffre d'un manque d'heuristiques efficaces comparée à la planification classique. Ce travail démontre que les GNN peuvent réussir à apprendre des approximations d'heuristiques parfaites dans ce cadre complexe basé sur les graphes.
Efficacité Fondée sur les Données : En traitant chaque e-state comme un signal d'entraînement indépendant plutôt que de compter sur des trajectoires complètes, l'approche génère des ensembles de données volumineux efficacement, permettant l'apprentissage de motifs significatifs à partir de la structure relationnelle des modèles de Kripke.
Complémentarité : Les auteurs ne prétendent pas que les GNN remplaceront immédiatement les heuristiques existantes. Au contraire, ils soutiennent que les heuristiques basées sur les GNN servent d'outil complémentaire puissant pour améliorer la couverture des solveurs, particulièrement lorsqu'ils sont intégrés dans des approches de type portfolio où différentes heuristiques peuvent compenser les faiblesses les unes des autres.

Le papier conclut que bien que des optimisations d'ingénierie (telles que le traitement par lots) soient nécessaires pour rendre les performances de temps d'exécution compétitives, la réduction de la complexité de l'espace de recherche prouve la viabilité des heuristiques apprises pour passer à l'échelle en MEP.