💻 computer science

Composable Verification Pipelines for Multi-Agent Systems

Cet article introduit un cadre de programmation fonctionnelle modulaire, implémenté en Soda, qui permet des pipelines de vérification composables pour les systèmes multi-agents, permettant aux utilisateurs de définir des descriptions de domaine en YAML et d'exécuter des flux de raisonnement transparents et à terminaison garantie pour des systèmes dynamiques impliquant des scénarios complexes tels que la désinformation et le raisonnement émotionnel.

Auteurs originaux : Julian Alfredo Mendez, Andreas Brännström

Publié 2026-07-21

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Julian Alfredo Mendez, Andreas Brännström

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 un monde où les programmes informatiques ne sont pas seulement des lignes de code, mais des personnages dans une histoire vivante. Dans le domaine de l'informatique, il existe un champ dédié à la compréhension de la manière dont ces personnages se déplacent, changent et interagissent au fil du temps. C'est l'étude de « l'action et du changement ». Voyez cela comme un jeu de société où les pièces bougent, les règles dictent ce qui est autorisé, et l'objectif est de prédire si le jeu se terminera par une victoire équitable ou un chaos total. Pendant des années, les scientifiques ont utilisé des outils lourds, basés sur la logique, pour écrire ces règles, tentant de prouver qu'un système se comporte correctement. Mais ces outils peuvent être maladroits, comme essayer de construire un château de LEGO complexe en utilisant uniquement une seule brique géante. Ils fonctionnent, mais ils ne sont pas très flexibles ou faciles à partager avec d'autres types de bâtisseurs.

Maintenant, imaginez que vous puissiez construire ce château à l'aide de pièces modulaires et emboîtables que n'importe qui pourrait comprendre et réorganiser. C'est le problème que Julian Alfredo Mendez et Andreas Brännström tentent de résoudre. Ils veulent créer un moyen de vérifier si une histoire numérique (une séquence d'actions et d'états) respecte les règles, mais ils veulent le faire en utilisant une approche moderne et flexible qui ressemble davantage à la construction avec des LEGO de haute technologie qu'à la résolution d'un casse-tête mathématique. Ils se demandent : pouvons-nous rendre la vérification de systèmes multi-agents complexes (comme une équipe de robots ou un réseau social de bots) aussi facile et transparente que le raccordement de tuyaux dans une usine ?

Les auteurs introduisent un nouveau cadre appelé « Composable Verification Pipelines » (Pipelines de Vérification Composables). Au lieu d'utiliser les anciennes briques logiques lourdes, ils ont construit un système basé sur des « Tiles » (Tuiles) et un langage appelé « Soda ». Considérez les « Tiles » comme un ensemble de tuyaux magiques et transparents. Chaque tuyau effectue une tâche simple : il reçoit une portion de données (comme l'état du monde ou une action entreprise par un agent), la traite, et la transmet au suivant. En emboîtant ces tuyaux, vous créez un « pipeline » capable de surveiller le déroulement d'une histoire entière et de vérifier chaque étape par rapport aux règles.

Le document propose que vous puissiez décrire un système complexe — comme un groupe d'agents partageant des informations ou prenant des décisions — en utilisant un format simple et lisible appelé YAML (qui est comme une liste de tâches structurée). Une fois que vous avez écrit vos règles et votre histoire dans ce format, le cadre les transforme automatiquement en une chaîne de ces tuyaux fonctionnels. À mesure que l'histoire se déroule, les données circulent à travers le pipeline. Un tuyau peut vérifier si une action était autorisée ; un autre peut voir si une règle a été enfreinte ; un troisième peut combiner le tout pour donner un « Oui » ou un « Non » final sur la validité de l'histoire.

Les chercheurs démontrent que cette approche n'est pas seulement une théorie ; ils l'ont construite et testée. Ils ont démontré qu'en décomposant le processus de vérification en ces petits composants réutilisables, ils peuvent gérer des scénarios complexes, comme la propagation de la désinformation sur un réseau social ou la façon dont les émotions affectent les décisions d'un agent. Par exemple, dans un cas où l'histoire d'un agent partageant un mensonge ressemblait à une violation de règle au premier abord, l'ajout de « fluents émotionnels » (des règles sur la façon dont l'agent se sent) dans le pipeline a soudainement rendu l'histoire cohérente et valide. Cela prouve que leur système peut être facilement ajusté pour inclure de nouveaux détails plus riches sans avoir à reconstruire toute la machine.

Crucialement, l'article prouve que ces pipelines termineront toujours leur tâche. Parce que le système est construit à partir d'étapes simples et finies, il garantit que le processus de vérification ne restera pas bloqué dans une boucle infinie. Ils ont également mesuré leur vitesse d'exécution, montrant que le temps nécessaire croît de manière prévisible et linéaire à mesure que l'on ajoute des règles ou des histoires plus longues. Les auteurs suggèrent que cette méthode comble le fossé entre la mathématique lourde des langages d'action et le monde flexible et modulaire de l'ingénierie logicielle moderne, facilitant ainsi la construction et la vérification de systèmes complexes basés sur des règles à l'avenir.

Résumé technique : Pipelines de vérification composables pour les systèmes multi-agents

Énoncé du problème

La complexité croissante des systèmes dynamiques et multi-agents a intensifié le besoin de mécanismes de vérification exécutables capables d'analyser des exécutions évolutives sous des contraintes fondées sur des règles. Bien que les travaux fondateurs sur les langages d'action (ex. : CMT, GOLOG, STRIPS) fournissent des sémantiques expressives pour raisonner sur l'action et le changement, les implémentations existantes sont principalement basées sur des systèmes de programmation logique. Cela crée une barrière à l'intégration des solutions de vérification avec les pratiques courantes du génie logiciel, particulièrement au sein des communautés de programmation fonctionnelle et orientée objet. Les auteurs identifient un manque dans la fourniture de flux de travail de vérification modulaires, composables et transparents qui puissent être opérationnalisés au sein d'écosystèmes logiciels standards (tels que la JVM) tout en maintenant des sémantiques formelles rigoureuses.

Méthodologie

Le papier propose un cadre modulaire pour la vérification de transitions et de trajectoires qui opérationnalise la sémantique des langages d'action via des pipelines fonctionnels exécutables. La méthodologie repose sur trois piliers fondamentaux :

Modèle Formel (basé sur CMT) : Le cadre utilise le langage d'action CMT, qui définit un langage de description de domaine ( $D_{MT}$ ) composé de lois causales statiques et dynamiques. Ces lois régissent l'évolution de l'état à travers des trajectoires définies comme des séquences d'états et d'ensembles d'actions ( $\langle s_0, A_1, s_1, \dots, A_n, s_n \rangle$ ).
- Représentation des fluents : Contrairement aux représentations traditionnelles par tuples, le modèle partitionne les valeurs des fluents pour assurer une unicité globale (par exemple, distinguer 'objectif-haut' de 'objectif-bas' comme des identifiants distincts).
- Fonction de vérification ( $\phi_{verify}$ ) : Une fonction de vérification formelle évalue si une transition (état d'entrée, ensemble d'actions, état de sortie) satisfait une règle spécifique. La fonction gère divers types de règles incluant causes-if (cause-si), triggers (déclenche), inhibits (inhibe), no-concurrency (pas de concomitance) et contravenes (contrevient).
- Construction de transition : Un mécanisme de fenêtre glissante est défini pour construire de manière incrémentale des transitions à partir d'une séquence de trajectoire brute, assurant une base formelle à la procédure de vérification.
Architecture Compositionnelle (Tiles & Soda) :
- Tiles : Un cadre pour composer des fonctions typées en spécifications graphiques et modulaires. Les procédures de vérification sont représentées comme des pipelines où des « tuiles » (fonctions) sont connectées pour traiter les états, les actions et les règles.
- Soda : Un langage descriptif à typage statique utilisé pour implémenter les spécifications. Les spécifications Soda sont traduites en Scala pour exécution sur la machine virtuelle Java (JVM) et peuvent être partiellement traduites en Lean pour la vérification formelle.
- Structure du Pipeline : Le processus de vérification est structuré comme une séquence de transformations typées :
  - Traitement de la trajectoire : Une opération de repli (fold) construit une séquence de transitions à partir de la trajectoire d'entrée.
  - Application des règles : Une opération de produit cartésien combine les transitions avec l'ensemble des règles.
  - Vérification : Une opération de mappage (map) applique $\phi_{verify}$ (et $\phi_{inhibit-set}$ pour la gestion des actions inhibées) à chaque paire transition-règle.
  - Agrégation : Une opération de repli (fold) finale agrège les résultats pour déterminer la validité globale.
Opérationnalisation : Le cadre inclut une couche de spécification basée sur YAML. Les utilisateurs définissent les descriptions de domaine (fluents, actions, règles) et les trajectoires d'entrée en YAML, qui sont ensuite analysés et opérationnalisés dans le modèle de vérification sous-jacent et le pipeline exécutable.

Principales Contributions

Le papier expose quatre contributions majeures :

Cadre Modulaire : Introduction d'un cadre modulaire pour la vérification de transitions et de trajectoires basé sur les technologies Tiles et Soda.
Sémantique Opérationnalisée : Le cadre opérationnalise la sémantique des langages d'action (spécifiquement CMT) via des pipelines de vérification exécutables, traitant les états, les actions et les règles comme des composants fonctionnels composables.
Couche de Spécification YAML : Fourniture d'une couche de spécification et d'un analyseur basés sur YAML qui permettent aux utilisateurs de définir des descriptions de domaine et des entrées de trajectoire, comblant ainsi le fossé entre les modèles formels et le code exécutable.
Exécution Transparente : Démonstration que l'approche fournit une méthode transparente, exécutable et scalable pour vérifier les exécutions de systèmes fondés sur des règles, avec une terminaison garantie du pipeline.

Résultats et Évaluation

Les auteurs fournissent une implémentation open-source et illustrent le cadre à travers deux exemples spécifiques impliquant la propagation de la désinformation et le raisonnement émotionnel :

Désinformation et Raisonnement Émotionnel : Le papier démontre comment le cadre supporte le raffinement modulaire. Dans un scénario impliquant la propagation de la désinformation, une trajectoire apparaît initialement invalide lorsque seuls les états informationnels sont considérés. Cependant, en étendant le modèle avec des fluents émotionnels (par exemple, « émotionnellement conflictuel » vs « émotionnellement aligné »), la même trajectoire devient valide. Cela illustre la capacité du cadre à incorporer des informations contextuelles sans altérer la structure de vérification sous-jacente.
Performance et Complexité : L'analyse théorique (Proposition 4) établit la complexité du pipeline comme étant $O(r \times t \times d)$ , où $r$ est le nombre de règles, $t$ le nombre d'états/ensembles d'actions, et $d$ la borne pour l'évaluation de la fonction de vérification. L'évaluation empirique sur un ordinateur Linux multi-cœurs standard montre que les temps d'exécution évoluent linéairement avec le nombre de règles, conformément aux attentes théoriques, avec de légères déviations attribuées à la surcharge de gestion de la mémoire.

Signification et Revendications

Le papier affirme que sa principale signification réside dans le pont jeté entre la recherche sur le raisonnement/la planification d'action et les approches de génie logiciel compositionnel. En s'éloignant des implémentations purement basées sur la programmation logique, le cadre :

Permet l'intégration avec les écosystèmes logiciels mainstream basés sur la JVM.
Fournit une vue d'ensemble graphique des spécifications (via Tiles), améliorant la transparence et l'interprétabilité.
Assure la terminaison du processus de vérification par construction.
Supporte des composants de raisonnement réutilisables et le raffinement modulaire des modèles de trajectoire.

Les auteurs maintiennent un champ d'application modeste, notant que le travail actuel est limité à la vérification sur des trajectoires et des descriptions de domaines explicitement spécifiées. Il ne traite pas de la génération automatique de trajectoires ou de la planification, mais fournit plutôt une plongée sémantique complète du langage d'action CMT qui est extensible par conception.