💻 computer science

EvoPlan: Evolutionary Neuro-Symbolic Robot Planning with Spatio-Temporal Guarantees

Ce document introduit EvoPlan, un cadre neuro-symbolique qui intègre la recherche évolutionnaire pour extraire des contraintes spatio-temporelles à partir de démonstrations et les combine avec un planificateur PDDL évolutionnaire et une boucle d'exécution contrainte afin de permettre aux robots basés sur les LLM de générer des plans sûrs et exécutables avec des garanties formelles dans des environnements ouverts.

Auteurs originaux : Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

Publié 2026-07-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bhavya Sai Nukapotula, Samin Moosavi, Haoze Wang, Luke Duncan, Diya Shakkottai, Varun Murali, Srinivas Shakkottai

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 essayiez d'apprendre à un robot à naviguer dans un monde agité, comme un robot de livraison dans une usine ou une voiture autonome dans une ville. Vous disposez de deux outils principaux pour l'aider, mais les deux présentent un défaut majeur :

Le « Écrivain Créatif » (IA/LLM) : C'est une IA intelligente capable de lire vos instructions (« Allez à la cafétéria ») et de concevoir un plan ingénieux. Elle est excellente pour comprendre le contexte et corriger les erreurs. Le problème : Elle est un peu imprudente. Elle peut concevoir un plan qui semble bon, mais qui est physiquement impossible, ou elle pourrait accidentellement brûler un feu rouge parce qu'elle n'a pas « réfléchi » aux règles.
Le « Comptable Rigide » (Planificateurs Classiques) : C'est un système rigide, basé sur des règles. Il ne fonctionne que si vous lui donnez une description mathématique parfaite du monde. Le problème : Il est incapable de comprendre le langage naturel ou de corriger ses propres erreurs. Si le monde change légèrement, il se fige.

EvoPlan est un nouveau cadre qui combine le meilleur des deux mondes. Il utilise l'« Écrivain Créatif » pour imaginer des plans et le « Comptable Rigide » pour s'assurer qu'ils sont sûrs et exécutables. Voici comment cela fonctionne, décomposé en trois étapes simples :

1. Le « Coach de l'Ombre » (Apprendre les règles)

Avant même que le robot ne bouge, le système doit apprendre les « règles non écrites » de la route ou de l'usine.

Le Problème : Les chercheurs ne possèdent que des vidéos de bons comportements (des conducteurs conduisant en toute sécurité ou des gens marchant poliment). Ils n'ont pas de vidéos de mauvais comportements pour montrer au robot ce qu'il ne faut pas faire.
La Solution : Le système agit comme un coach d'écriture créative. Il prend une vidéo d'une conduite exemplaire et demande à l'IA : « Et si le conducteur accélérait ? Et s'il brûlait un feu rouge ? » Il invente ces scénarios « mauvais » (contrefactuels) pour créer un contraste.
Le Résultat : En comparant les « bonnes » vidéos à celles des scénarios inventés « mauvais », le système apprend un manuel de règles unique et universel (appelé une contrainte STL). Considérez cela comme un « Coach de l'Ombre » qui murmure à l'oreille du robot : « Ne dépasse jamais la vitesse X », ou « Reste toujours à une distance de Y mètres des gens ». Ce manuel de règles s'applique à chaque mouvement du robot.

2. L'« Éditeur Évolutif » (Construire le plan)

Maintenant, le robot doit établir un plan pour aller du point A au point B.

Le Processus : L'« Écrivain Créatif » (l'IA) propose un plan. Mais au lieu de l'accepter tel quel, le système le soumet à un processus d'édition rigoureux.
La Boucle :
1. L'IA écrit un projet de plan.
2. Un « Validateur » (le comptable) le vérifie. Si le plan est défectueux (ex : « Vous ne pouvez pas ouvrir une porte qui n'existe pas »), le validateur signale l'erreur spécifique.
3. L'IA lit l'erreur, corrige cette partie spécifique, et réessaie.
4. Cela se répète de nombreuses fois, comme un écrivain qui peaufine une histoire jusqu'à ce qu'elle soit parfaite.
La Magie : Le système conserve les « bonnes parties » du plan qui ont déjà été vérifiées et ne réécrit que les parties défectueuses. Au fil du temps, le plan devient plus long et plus fiable jusqu'à ce qu'il soit entièrement valide.

3. Le « Gardien de la Sécurité » (Exécution en temps réel)

Enfin, le robot commence à se déplacer. C'est là que le « Coach de l'Ombre » et le « Gardien de la Sécurité » prennent le relais.

La Vérification : Le robot n'exécute pas son plan aveuglément. Avant de faire un seul pas (ou de tourner une roue), le système vérifie ce mouvement spécifique par rapport au manuel de règles appris à l'étape 1.
Le Filet de Sécurité :
- Scénario A : Le robot prévoit de tourner à gauche. Le Gardien vérifie : « Y a-t-il un piéton là ? La vitesse est-elle sûre ? » Oui. Le robot avance.
- Scénario B : Le robot prévoit de tourner à gauche. Le Gardien vérifie : « Attendez, un piéton est trop proche ! » Non. Le robot s'arrête immédiatement.
La Reprogrammation : Si le Gardien dit « Non », le robot ne s'écrase pas. Il verrouille toutes les étapes sûres qu'il a déjà accomplies, met à jour sa position actuelle, et demande à l'« Éditeur Évolutif » d'écrire un nouveau plan pour le reste du voyage.

Pourquoi cela importe

L'article démontre que ce système fonctionne mieux qu'en utilisant uniquement l'IA ou uniquement les règles.

En Conduite : Lors de tests sur des données de conduite, le système a considérablement réduit les collisions et les infractions aux feux rouges sans nécess avoir besoin de réentraîner l'IA du conducteur. Il a simplement ajouté un « garde-fou » qui empêche les mauvaises actions.
En Navigation : Lors de tests dans des puzzles complexes en monde ouvert (comme trouver des objets dans une maison), le système a résolu plus de tâches que les autres planificateurs d'IA, même lorsque les mots utilisés dans les instructions ne correspondaient pas parfaitement au vocabulaire du robot.

En bref : EvoPlan est un système de planification robotique qui utilise l'IA pour être créatif et flexible, mais qui force celle-ci à porter un « casque de sécurité » (appris à partir de données) et un « manuel de règles » (vérifié par du code) pour garantir qu'elle ne fasse jamais rien de dangereux ou d'impossible. C'est comme avoir un conducteur brillant mais impulsif qui est constamment guidé par un copilote très strict et très intelligent.

Résumé Technique : EvoPlan

Définition du Problème

Le papier traite du défi de l'exécution de tâches robotiques en langage naturel dans des environnements dynamiques et partiellement connus, tout en respectant des normes implicites (par exemple, les règles de sécurité, les préférences sociales) qui ne sont pas explicitement énoncées dans l'instruction de la tâche. Les auteurs identifient trois difficultés fondamentales qui rendent les solutions standards inefficaces :

Observabilité Partielle et Dynamique : Le modèle du monde est incomplet et les trajectoires de l'agent doivent être suivies en ligne, ce qui fait échouer les planificateurs reposant sur des environnements entièrement spécifiés.
Sous-spécification des Prompts : Les tâches en langage naturel omettent souvent les exigences normatives. Un planificateur optimisant uniquement pour le but explicite peut satisfaire l'instruction tout en violant des normes implicites (par exemple, atteindre une destination en brûlant un feu rouge).
Données à Classe Unique : Les seules données préalables disponibles consistent en des journaux d'opérations non annotés où chaque trace enregistrée est « acceptable ». Il n'y a pas de violations étiquetées, de paires de préférences ou de spécifications symboliques des normes, rendant inapplicable le façonnage de récompense standard, l'apprentissage par imitation (behavior cloning) ou l'apprentissage par renforcement basé sur les préférences.

Méthodologie : Le Cadre EvoPlan

EvoPlan est un cadre neuro-symbolique qui intègre les Grands Modèles de Langage (LLM) avec la vérification formelle et la recherche évolutionnaire. Il opère en trois étapes distinctes :

1. Extraction de Contraintes Hors Ligne (Ajustement STL Évolutionnaire)

Le système apprend une contrainte unique de Logique Temporelle de Signal (STL), $\Phi_{mob}$ , à partir de données de démonstration non annotées.

Synthèse Contrefactuelle : Puisque les données sont à classe unique (toutes acceptables), le système génère une classe négative ( $D^-$ ) en utilisant des perturbations procédurales (ex: vitesse excessive, encombrement) et un générateur de violations basé sur un LLM. Cela transforme le problème en une tâche de classification supervisée.
Recherche Évolutionnaire : Une recherche évolutionnaire pilotée par LLM (inspirée d'AlphaEvolve) fait évoluer des formules STL sur une grammaire d'atomes de signaux (vitesse, dégagement, temps avant collision, etc.). La fonction de fitness maximise la robustesse sur l'ensemble positif ( $D^+$ ) tout en minimisant la satisfaction sur l'ensemble négatif ( $D^-$ ), en pénalisant la complexité.
Polyvalence : Cette procédure unique permet de récupérer à la fois des règles codifiées (ex: « s'arrêter aux feux rouges » à partir de logs nuPlan) et des préférences de population (ex: espacement social à partir de données de téléopération SCAND).

2. Synthèse de Plan PDDL Évolutionnaire

Le système utilise un Planificateur PDDL Évolutionnaire pour générer des séquences d'actions discrètes.

Le LLM comme Mécanisme de Proposition : Au lieu d'un planificateur autonome, le LLM propose et répare des plans PDDL par rapport à un domaine et un problème fixes.
Cascade de Validateurs : Une cascade programmatique (vérification de la syntaxe PDDT, simulation VAL, accessibilité de l'objectif et vérification de la robustesse STL) évalue les candidats.
Réparation Itérative : Le LLètre conditionne sa prochaine mutation sur le feedback spécifique du validateur (ex: « l'action X a échoué à la précondition Y »). Cela permet au « préfixe vérifié » du plan de croître de manière monotone au fil des itérations.
Robustesse au Désalignement : Le système gère les scénarios en monde ouvert et le désalignement de vocabulaire (ex: but « chauffé » vs action « toaster ») en utilisant un LLM pour dériver une carte de correspondance prédicat-symbole avant la validation.

3. Boucle d'Exécution Contrainte

Au moment de l'exécution, le système fait le pont entre le plan PDDL discret et l'exécution robotique continue.

Expansion de Waypoints : Chaque action PDDL est envoyée à une couche de navigation (ex: Nav2) qui génère une séquence de waypoints.
Blindage (Shielding) : La séquence de waypoints est vérifiée par rapport à la contrainte STL globale extraite $\Phi_{mob}$ .
Replanification sur Violation : Si la séquence viole $\Phi_{mob}$ , l'action est rejetée. Le système valide le préfixe vérifié du plan, met à jour l'état initial basé sur l'état actuel du monde, et ré-invoque le planificateur pour générer un nouveau suffixe. Cela crée un système en boucle fermée où le planificateur n'est réactivé que lorsque la sécurité ou la faisabilité est compromise.

Contributions Clés

Extraction de STL basée sur les Données : Une méthode pour extraire une contrainte de mobilité globale unique à partir de données de démonstration à classe unique en synthétisant des contre-exemples négatifs, applicable tant aux domaines basés sur des règles qu'aux préférences.
Solveur PDDL Évolutionnaire : Un planificateur qui utilise des LLM pour la proposition et la réparation au sein d'une boucle formellement vérifiée, démontrant une robustesse au désalignement de vocabulaire et à la croissance de la croyance en monde ouvert.
Architecture d'Exécution Contrainte : Une boucle d'exécution qui compile les plans PDDL en waypoints, les valide par rapport aux contraintes STL apprises, et déclenche une replanification lors d'une violation, garantissant la sécurité sans réentraîner la politique sous-jacente.
Déploiement Local : L'ensemble du pipeline, y compris tous les appels LLM, s'exécute sur un modèle à poids ouverts hébergé localement (Qwen3-32B), permettant un déploiement sur robot sans dépendance au cloud.

Résultats Expérimentaux

Les auteurs évaluent le cadre à travers trois benchmarks :

Transfert de Contrainte STL (Blindage) :
- Conduite (nuPlan $\to$ Bench2Drive) : La contrainte de règle extraite a réduit les infractions aux feux rouges de 77 % et les collisions de 71 % sur une politique de conduite Qwen2.5-VL, améliorant le score de conduite global.
- Navigation Sociale (SCAND $\to$ HA-VLN-CE) : La contrainte de préférence extraite a réduit les contacts évitables de 82 % (PointNav) et 93 % (MLP) sur des tâches de navigation intérieure, compressant efficacement la « queue dangereuse » des distributions de sécurité.
Performance de Planification (ALFWorld Text) :
- Sur le benchmark en monde ouvert ALFText, EvoPlan a atteint un taux de réussite de 98,5 % sur des tâches inédites, surpassant les bases solides (ex: NL-PDDL à 94 %, LLM directs à ~20 %).
- Crucialement, il a maintenu cette performance (98,5 %) même lorsque le vocabulaire de l'objectif ne correspondait pas au vocabulaire du modèle d'action, là où les autres méthodes chutaient significativement.
- Il a résolu des tâches avec des plans optimaux dépassant une profondeur de 10, là où les planificateurs à horizon fixe échouaient.
Exécution de Bout en Bout (Gazebo) :
- Dans un environnement d'usine simulé avec 9 à 15 piétons, le système a complété des missions de ramassage et de dépôt avec une dégradation progressive. Bien qu'une mission ait échoué en raison d'une densité extrême, le système a maintenu une faible exposition à l'espace personnel et a évité les collisions dans quatre cas sur cinq en replanifiant lorsque les seuils de dégagement étaient violés.

Signification et Revendications

Le papier affirme qu'EvoPlan offre une approche « le meilleur des deux mondes » : il exploite la fluidité et la conscience contextuelle des LLM pour la génération et la réparation de plans, tout en s'appuyant sur la validation symbolique et la logique temporelle dérivée de données pour garantir l'exécutabilité et la sécurité.

Les auteurs soulignent que le système traite les modèles neuronaux comme des générateurs de candidats plutôt que comme des sources d'autorité non vérifiées. En apprenant les contraintes directement des journaux opérationnels non annotés, le cadre évite le besoin de spécifications de sécurité écrites manuellement ou de données de violation étiquetées. Les résultats suggèrent que cette boucle neuro-symbolique est robuste à la dynamique du monde ouvert et au désalignement de vocabulaire, offrant une voie pour déployer des planificateurs robotiques sûrs et adaptatifs qui ne nécessitent pas d'infrastructure cloud.