Improved Generalized Planning with LLMs through Strategy Refinement and Reflection

1. Problématique

Le planification généralisée (Generalized Planning) vise à générer des plans qui ne résolvent pas un seul problème spécifique, mais qui s'appliquent à l'ensemble des tâches d'un domaine donné (par exemple, tous les problèmes de logistique possibles). Ces plans contiennent généralement des boucles et des conditions (si-alors-else) pour gérer la variabilité de la taille des tâches et des états initiaux.

Récemment, les Modèles de Langage (LLM) ont été utilisés pour générer des programmes Python représentant ces plans généralisés. L'approche précédente (Silver et al., 2024) suivait un pipeline en trois étapes :

1. Génération d'un résumé du domaine en langage naturel (NL).
2. Génération d'une stratégie en langage naturel.
3. Implémentation de cette stratégie sous forme de code Python, suivie d'un débogage automatique.

Limites de l'approche précédente :

• Bottleneck de la stratégie : Si la stratégie en langage naturel est incorrecte, le code généré le sera aussi. L'approche précédente ne permettait pas de valider ou de corriger la stratégie avant la génération du code.
• Manque de réflexion : Le débogage se limitait souvent à une correction directe du code sans analyse profonde de la cause racine de l'erreur.
• Scalabilité et coût : Bien que la génération d'un plan généralisé réduise le coût par rapport à la génération de plans instance par instance, la qualité des solutions restait insuffisante sur de nombreux domaines complexes.

2. Méthodologie

Les auteurs proposent un nouveau cadre de travail qui traite la génération de stratégie comme une sous-tâche critique, permettant sa validation et son raffinement avant la génération de code. Le pipeline se compose de trois phases principales :

A. Génération et Raffinement de Stratégies (Niveau Pseudocode)

Au lieu de demander une stratégie en langage naturel pur, le LLM génère une stratégie sous forme de pseudocode.

• Avantage : Le pseudocode est plus proche de la structure cible (Python) et permet une validation plus fine.
• Validation Indirecte : Comme le pseudocode n'est pas exécutable, les auteurs utilisent une approche indirecte :
  1. Le LLM reçoit le pseudocode et un problème de débogage (en NL).
  2. Il doit générer un plan PDDL en suivant strictement le pseudocode.
  3. Ce plan est validé par un validateur symbolique (VAL).
  4. Si le plan est incorrect, un message de retour (feedback) est généré.

B. Étape de Réflexion (Reflection)

Avant de demander au LLM de corriger le pseudocode ou le code Python, une étape de réflexion est introduite.

• Le LLM est invité à analyser l'erreur : Quelle partie spécifique de la stratégie/code a causé l'erreur ? Pourquoi est-elle inadéquate ?
• Cette étape force le modèle à identifier la cause racine (ex: manque d'une étape de déchargement d'un objet avant de le charger sur un avion) avant de proposer une correction.
• Le pseudocode est ensuite mis à jour itérativement jusqu'à ce qu'il génère des plans corrects pour l'ensemble des tâches de débogage.

C. Génération de Code et Sélection

Une fois la stratégie validée :

1. Génération de multiples variantes : Inspirés par les techniques de génération de code, les auteurs génèrent plusieurs versions initiales du programme Python en variant l'ordre des objets et des faits dans l'entrée (tout en gardant une température de 0 pour la cohérence).
2. Débogage avec réflexion : Chaque programme subit le même processus de débogage avec réflexion que la stratégie.
3. Sélection : Le meilleur programme est sélectionné en fonction de sa performance sur les tâches de débogage.

3. Contributions Clés

1. Validation de Stratégie par Pseudocode : Introduction d'une boucle de rétroaction pour valider et corriger la logique de haut niveau (pseudocode) avant la génération de code exécutable, résolvant le problème de la propagation d'erreurs de logique.
2. Intégration de la Réflexion (Reflection) : Ajout d'une étape explicite où le LLM analyse la cause de l'échec (dans la stratégie ou le code) avant de proposer une correction, améliorant la précision des itérations.
3. Génération de Variants et Sélection : Utilisation de l'ensemblage (génération de plusieurs programmes) et sélection du meilleur candidat, augmentant la robustesse face aux erreurs de génération aléatoire.
4. Évaluation Rigoureuse : Tests sur 17 domaines PDDL (incluant ceux de Silver et al. et de nouveaux domaines) avec quatre LLMs (GPT-4o, Llama 3.3, DeepSeek-V3.2, Qwen3-Thinking), incluant des variantes "costumées" (noms modifiés) pour tester la généralisation sémantique.

4. Résultats

Les expériences montrent une amélioration substantielle par rapport à l'état de l'art (Silver et al., 2024) et aux lignes de base réimplémentées.

• Performance Globale : La configuration optimale (F5-3 avec DeepSeek) atteint une couverture moyenne de 82 % sur les 17 domaines testés.
  • Amélioration de +23 points de pourcentage avec GPT-4o.
  • Amélioration de +14 points avec DeepSeek.
• Généralisation : Les programmes générés avec une couverture de 100 % sur les données d'évaluation ont été vérifiés manuellement et se sont avérés généraliser à des tâches de taille arbitraire générées par les générateurs d'instances, dépassant ainsi la simple mémorisation.
• Robustesse aux Variations :
  • Sur les variantes "costumées" (noms d'objets/actions modifiés mais sémantique préservée), la performance reste élevée, indiquant une capacité de raisonnement réel et non une simple récitation de données d'entraînement.
  • Sur les variantes "anonymisées" (noms génériques sans sémantique), la performance chute, confirmant que le modèle s'appuie sur la compréhension sémantique du domaine.
• Efficacité Temporelle : Les programmes Python générés exécutent les plans beaucoup plus rapidement que les planificateurs symboliques (comme FF ou LM-cut) pour les tâches résolues, bien que les plans soient parfois légèrement plus longs (environ 1,1 fois la longueur des plans optimaux).
• Coût : Bien que le pipeline soit plus coûteux en tokens et en appels LLM par domaine (car il génère plusieurs stratégies et programmes), ce coût est unique par domaine. Une fois le programme généré, il peut résoudre un nombre infini de tâches dans ce domaine à un coût d'exécution négligeable.

5. Signification et Conclusion

Cet article démontre que l'utilisation des LLMs pour la planification généralisée peut être considérablement améliorée en traitant la génération de stratégie comme un processus itératif de raffinement, similaire au développement logiciel.

• Changement de paradigme : Passer d'une génération directe "NL -> Code" à une approche "NL -> Pseudocode (Validé/Réfléchi) -> Code" permet de capturer la logique complexe nécessaire à la généralisation.
• Synergie Symbolique/Neuronale : L'approche combine la puissance de raisonnement des LLMs pour la conception de stratégies avec la rigueur des validateurs symboliques (VAL) pour la vérification de la correction.
• Impact : Cela ouvre la voie à des systèmes de planification capables de résoudre des problèmes complexes et de grande échelle de manière autonome, en générant des contrôleurs réutilisables plutôt que des plans éphémères pour chaque instance.

En résumé, la combinaison du pseudocode, de la réflexion sur les erreurs et de la génération multiple permet de surmonter les limites actuelles des LLMs en matière de planification, offrant des solutions robustes et généralisables.