GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

Le papier présente GenePlan, un cadre novateur utilisant des algorithmes évolutionnaires assistés par des modèles de langage pour générer des planificateurs généralisés interprétables en Python qui surpassent les méthodes basées sur le prompting et rivalisent avec les planificateurs de l'état de l'art en termes de performance et d'efficacité.

L'essentiel

🚀 GenePlan : L'Art de faire grandir un "Super-Planificateur"

Imaginez que vous devez organiser un voyage complexe pour des milliers de personnes, avec des règles strictes : qui peut monter dans quel bus, où ils doivent aller, et comment éviter les embouteillages. C'est ce qu'on appelle un problème de planification.

Habituellement, les ordinateurs sont très forts pour résoudre ces énigmes, mais ils doivent recalculer tout le trajet à chaque fois qu'une nouvelle personne s'ajoute au groupe. C'est lent et énergivore.

GenePlan, c'est une nouvelle méthode inventée par des chercheurs de J.P. Morgan qui change la donne. Au lieu de demander à l'ordinateur de résoudre le problème à chaque fois, GenePlan apprend à l'ordinateur à écrire son propre manuel d'instructions (un programme informatique) qui fonctionne pour n'importe quelle situation dans ce domaine.

Voici comment cela fonctionne, étape par étape, avec des analogies simples :

1. Le Défi : L'IA qui "rêve" mais ne "réfléchit" pas assez

Les grands modèles de langage (comme ceux qui écrivent des textes ou du code) sont comme des génies très créatifs mais un peu étourdis. Si vous leur demandez de planifier un trajet, ils peuvent proposer une solution qui semble logique, mais qui contient des erreurs cachées ou qui n'est pas la plus courte. C'est comme si un chef cuisinier vous donnait une recette qui manque de sel ou qui brûle le gâteau.

2. La Solution : L'Évolution par "Survie du Plus Apt"

GenePlan utilise une idée tirée de la nature : l'évolution. Imaginez une pépinière où l'on fait pousser des milliers de plantes (des programmes informatiques).

• La Graine (Le LLM) : On demande à l'IA de générer une première ébauche de programme (une "plante").
• Le Test (L'Environnement) : On lance ce programme sur plusieurs problèmes différents.
• La Sélection (Le Jardinier) :
  • Si le programme plante (fait des erreurs) ou prend trop de temps, il est éliminé.
  • Si le programme fonctionne bien, il est gardé.
• La Reproduction (La Mutation) : On prend les meilleurs programmes et on demande à l'IA de les "croiser" (mélanger leurs meilleures parties) et de les "muter" (faire de petits changements pour les améliorer).

C'est comme si vous aviez un coach sportif (l'IA) qui entraîne une équipe de coureurs. À chaque séance, il observe qui court le mieux, garde les meilleurs, et leur donne de nouveaux conseils pour courir encore plus vite à la séance suivante. Au bout de quelques générations, vous avez un champion du monde.

3. Le Résultat : Un "Cerveau" sur mesure

À la fin de ce processus, GenePlan ne vous donne pas juste une réponse. Il vous donne un programme Python (un petit logiciel) qui est :

• Interprétable : On peut le lire et comprendre ce qu'il fait (contrairement à une "boîte noire" mystérieuse).
• Rapide : Une fois créé, ce programme résout de nouveaux problèmes en moins d'une demi-seconde.
• Économique : Cela coûte très peu cher (environ 1,80 $ par domaine) pour entraîner ce "cerveau".

4. Pourquoi c'est impressionnant ?

Dans les tests, GenePlan a réussi à créer des planificateurs aussi bons que les meilleurs logiciels spécialisés du monde (qui sont très complexes et lents à exécuter), mais en étant beaucoup plus rapide à utiliser une fois entraîné.

• Avant (Méthodes classiques) : C'est comme si vous deviez dessiner un itinéraire à la main à chaque fois que vous sortez de chez vous.
• Avec GenePlan : C'est comme si vous appreniez une fois pour toutes la logique de votre ville, et que vous aviez un GPS intégré dans votre cerveau qui vous dit instantanément le meilleur chemin, peu importe où vous allez.

En résumé

GenePlan, c'est comme un jardinier numérique qui utilise l'intelligence artificielle pour faire évoluer, génération après génération, des programmes informatiques capables de résoudre des énigmes complexes de manière intelligente, rapide et efficace. Au lieu de chercher la solution à chaque fois, il apprend comment chercher la solution.

C'est une avancée majeure car cela rend l'IA plus fiable, plus rapide et moins coûteuse pour des tâches réelles comme la logistique, la gestion de stocks ou l'organisation de ressources.

Résumé technique

Voici un résumé technique détaillé du papier "GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models", rédigé en français.

1. Problématique et Contexte

Le papier aborde le défi de la planification généralisée (Generalized Planning) dans le cadre de la planification classique décrite en PDDL (Planning Domain Definition Language).

• Le problème : Les modèles de langage (LLM) actuels, bien que performants pour de nombreuses tâches, montrent des résultats médiocres dans les tâches de prise de décision séquentielle et de planification. Les approches existantes basées sur les LLM (comme le Chain-of-Thought ou CoT) génèrent souvent des solutions "satisfaisantes" (satisficing) mais non optimisées, sans garantir la qualité du plan (longueur minimale) ni la validité stricte sur des instances variées.
• L'objectif : Développer un cadre capable de générer des planificateurs généralisés (des fonctions Python réutilisables) qui minimisent le nombre d'actions (coût du plan) sur un ensemble d'instances de problèmes partageant la même structure de domaine, mais avec des états initiaux et des objectifs différents.

2. Méthodologie : GenePlan

Les auteurs proposent GenePlan (GENeralized Evolutionary Planner), un cadre novateur qui combine les algorithmes évolutionnaires avec l'assistance des LLM. L'idée centrale est de traiter la planification généralisée comme un problème d'optimisation où l'espace de recherche est constitué de code Python exécutable.

Architecture et Processus

Le système fonctionne selon une boucle évolutionnaire itérative :

1. Formulation comme problème d'optimisation :
   L'objectif est de trouver un planificateur $\Phi$ (une méthode Python) qui minimise la longueur moyenne des plans sur un ensemble d'entraînement $\Pi_{train}$ :
   $$\arg \min_{\Phi} \frac{1}{|\Pi_{train}|} \sum_{\Pi \in \Pi_{train}} |\Phi(\Pi)|$$
   où $|\Phi(\Pi)|$ est la longueur du plan généré.

2. Population et Évaluation (Fitness) :

   • Une population de planificateurs candidats (code Python) est maintenue.
   • Chaque candidat est exécuté sur les tâches d'entraînement.
   • La fonction de fitness calcule la longueur moyenne des plans. Si un planificateur échoue à résoudre une instance, il reçoit une pénalité massive (score $F \gg 0$).
   • Les plans sont validés par un validateur PDDL externe pour garantir leur validité sémantique.

3. Boucle Évolutionnaire Assistée par LLM :

   • Sélection : Des planificateurs parents sont sélectionnés probabilistiquement en fonction de leur fitness (méthode de Boltzmann avec une température décroissante pour favoriser l'exploration au début et l'exploitation à la fin).
   • Recombinaison et Mutation (via LLM) : Au lieu des opérateurs génétiques classiques (croisement de chaînes de caractères), le LLM est sollicité pour générer de nouveaux candidats. Le prompt inclut le domaine PDDL, des exemples de code de parents (avec leurs scores et messages d'erreur), et des instructions explicites pour effectuer des "mutations" (optimisations, élimination d'actions redondantes) et des "croisements" (fusion de stratégies efficaces).
   • Filtrage (AST) : Le code généré par le LLM est d'abord parse par un Analyseur Syntaxique Abstrait (AST) pour s'assurer qu'il respecte une liste blanche de fonctions et de bibliothèques autorisées (sécurité et validité structurelle).
   • Remplacement : À la fin de chaque génération, les planificateurs les moins performants sont éliminés et remplacés par les meilleurs de la nouvelle génération (stratégie de remplacement élitiste $\mu + \lambda$).

4. Sortie :
   Après un nombre fixe de générations, le meilleur planificateur (la méthode Python la plus performante) est extrait. Ce planificateur est ensuite capable de résoudre de nouvelles instances du domaine en quelques millisecondes.

3. Contributions Clés

• Nouveau Paradigme d'Optimisation : Passage de la génération directe de plans à la génération de planificateurs (code) via une optimisation évolutionnaire guidée par les LLM.
• Interprétabilité : Contrairement aux modèles de boîte noire, GenePlan produit du code Python lisible et modifiable, permettant de comprendre la stratégie adoptée (heuristiques, logique de contrôle).
• Efficacité et Coût : Le coût de génération est faible (environ 1,82 $ par domaine avec GPT-4o) et le temps d'exécution pour résoudre une nouvelle instance est extrêmement rapide (moyenne de 0,49 seconde), une fois le planificateur généré.
• Performance Comparable aux SOTA : Le cadre atteint des performances comparables aux planificateurs classiques les plus avancés (comme Fast Downward) tout en étant beaucoup plus rapide à l'inférence.

4. Résultats Expérimentaux

Les auteurs ont évalué GenePlan sur 8 domaines (6 benchmarks existants + 2 nouveaux : Trading et Research).

• Comparaison avec les Bases :
  • GenePlan (evo) a obtenu un score SAT moyen de 0,91.
  • Cela le place très près des planificateurs de l'état de l'art (Fast Downward avec 30 min de temps de calcul, score 0,93).
  • Il surpasse significativement les approches basées uniquement sur les LLM (CoT avec GPT-4o : score moyen de 0,64).
• Analyse Statistique : Les tests de Friedman et Nemenyi confirment que GenePlan est statistiquement supérieur aux méthodes CoT et comparable aux meilleurs solveurs classiques.
• Coût et Temps :
  • Coût de génération : ~1,82 $/domaine (GPT-4o).
  • Temps d'inférence : ~0,49 s/instance (contre des minutes pour Fast Downward sur des problèmes complexes).
  • Le temps de génération du planificateur est un coût unique (one-time cost) amorti par la réutilisation rapide sur de nombreuses instances.
• Limites : Sur des domaines complexes sans stratégie simple (ex: Sokoban ou Blocksworld avec des états irréversibles), GenePlan a tendance à essayer de construire des algorithmes de recherche internes, ce qui est moins efficace que les solveurs dédiés.

5. Signification et Perspectives

Ce travail démontre que les LLM, lorsqu'ils sont intégrés dans une boucle d'optimisation évolutionnaire, peuvent dépasser leurs limites de raisonnement séquentiel direct pour générer des algorithmes de planification robustes et optimisés.

• Impact : Cela ouvre la voie à la création de planificateurs spécialisés, interprétables et très rapides pour des domaines spécifiques, sans nécessiter de réentraînement de modèles massifs.
• Futur : Les auteurs suggèrent d'explorer des critères d'arrêt anticipé (early stopping) pour réduire les coûts de calcul, d'intégrer d'autres métriques d'optimisation que la simple longueur du plan, et d'utiliser les LLM comme orchestrateurs pour sélectionner dynamiquement entre GenePlan et des solveurs de recherche traditionnels selon la complexité du problème.

En résumé, GenePlan représente une avancée majeure en combinant la puissance générative des LLM avec la rigueur de l'optimisation évolutionnaire pour résoudre des problèmes de planification classique de manière efficace et économique.