On Sample-Efficient Generalized Planning via Learned Transition Models

Cet article propose une approche de planification généralisée fondée sur l'apprentissage de modèles de transition explicites par des réseaux de neurones, démontrant que cette méthode surpasse les modèles prédictifs directs en termes de généralisation hors distribution et d'efficacité des échantillons tout en nécessitant moins de données et de paramètres.

L'essentiel

🎯 Le Problème : Apprendre à jouer aux échecs sans connaître les règles

Imaginez que vous voulez apprendre à un robot à ranger sa chambre (ou à déplacer des blocs, comme dans le jeu Blocksworld).

Les méthodes traditionnelles d'intelligence artificielle (comme les grands modèles de type "ChatGPT" ou PlanGPT) fonctionnent un peu comme un étudiant qui mémorise par cœur. On lui montre des milliers d'exemples de chambres rangées, et il apprend à répéter la séquence de mouvements : "Prends le bloc rouge, pose-le ici, prends le bleu...".

Le problème ? Si vous lui donnez une chambre avec plus de blocs que ceux qu'il a jamais vus (par exemple, 10 blocs au lieu de 5), il panique. Il essaie de deviner le prochain mouvement, mais comme il n'a pas vraiment compris comment les blocs bougent, il commence à faire des erreurs. C'est ce qu'on appelle la "dérive d'état" : il perd le fil de la réalité et imagine des choses qui ne sont pas possibles. De plus, pour apprendre par cœur, il a besoin de livres entiers (des milliards de données) et d'un cerveau énorme (des modèles très lourds).

💡 La Solution : Apprendre la "Physique" du monde

Les auteurs de ce papier proposent une approche différente. Au lieu de demander au robot : "Quel mouvement dois-je faire ?", ils lui demandent : "À quoi ressemblera la chambre après mon mouvement ?".

C'est la différence entre :

1. Mémoriser une recette (Action-centrée) : "Je dois faire A, puis B, puis C."
2. Comprendre la cuisine (État-centré) : "Si je mets du beurre dans la poêle chaude, il va fondre. Si je mets un œuf, il va cuire."

Ils entraînent le modèle à prédire l'état futur (la photo de la chambre après l'action) plutôt que l'action elle-même. C'est comme apprendre la physique du monde : comprendre que si je lâche un objet, il tombe, peu importe la taille de la pièce.

🧱 Les Trois Ingénients Magiques

Pour que cela fonctionne bien, ils utilisent trois astuces créatives :

1. La Carte Universelle (Représentation Invariante)

Imaginez que vous devez décrire une ville à un ami.

• L'ancienne méthode (FSF) : Vous lui donnez une liste de maisons numérotées de 1 à 100. Si la ville a 101 maisons, votre liste ne sert plus à rien.
• La méthode du papier (WL) : Vous lui donnez une carte topologique. Vous ne dites pas "Maison 1", vous dites "Il y a un parc, entouré de 3 maisons". Peu importe si la ville a 10 maisons ou 1000, la structure de la carte reste compréhensible.
  Cela permet au robot de généraliser : il comprend que "ranger 10 blocs" est le même type de problème que "ranger 100 blocs", juste plus grand.

2. Le Moteur de Prévision (Modèle de Transition)

Le robot utilise un petit cerveau (un modèle mathématique simple) pour simuler le futur.

• Il regarde l'état actuel.
• Il imagine : "Si je fais cette action, à quoi ressemblera la prochaine image ?"
• Il compare cette image imaginaire avec toutes les images réelles possibles (selon les règles strictes du jeu).
• Il choisit l'action qui correspond le mieux à son imagination.

C'est comme si vous jouiez à un jeu vidéo en mode "simulation" : vous prévoyez le coup, vérifiez si c'est légal, et ne jouez que si c'est bon. Cela évite les erreurs de logique.

3. L'Effet "Delta" (Le changement, pas tout le monde)

Dans un jeu de blocs, quand vous bougez un bloc, 99% de la pièce reste exactement pareil. Seule une petite partie change.
Au lieu d'essayer de redessiner toute la pièce à chaque fois (ce qui est difficile et lent), le modèle ne prédit que le changement (le "delta"). C'est comme dire : "Rien ne bouge, sauf ce bloc qui passe de la table au sol". Cela rend l'apprentissage beaucoup plus rapide et précis.

🏆 Les Résultats : Petit et Efficace vs Géant et Gourmand

Les chercheurs ont comparé leur méthode avec les géants actuels (les Transformers massifs) :

• Les Géants (PlanGPT, Plansformer) : Ils ont besoin de centaines de millions de paramètres (un cerveau énorme) et de milliers d'exemples. Quand on leur donne un problème plus grand que ceux qu'ils ont vus, ils échouent souvent (0% de réussite).
• La Méthode du Papier : Ils utilisent un modèle minuscule (des milliers de fois plus petit) et s'entraînent sur très peu d'exemples.
  • Résultat ? Ils réussissent souvent mieux à résoudre des problèmes plus grands que ceux de l'entraînement.
  • Ils sont plus robustes, plus rapides à entraîner et consomment beaucoup moins d'énergie.

🚀 En Résumé

Ce papier nous dit que pour enseigner à une IA à planifier des tâches complexes (comme ranger une chambre ou livrer des colis), il ne faut pas lui faire apprendre par cœur des listes de mouvements. Il vaut mieux lui apprendre les règles du jeu (comment l'état du monde évolue) et lui donner des outils pour visualiser le futur.

C'est la différence entre un perroquet qui répète des phrases et un ingénieur qui comprend la mécanique. Avec cette approche, on peut créer des robots intelligents, petits, économes en énergie et capables de s'adapter à des situations qu'ils n'ont jamais vues auparavant.

Résumé technique

1. Problématique : La Planification Généralisée (GP)

La planification généralisée vise à construire des stratégies de résolution qui s'appliquent à une famille de problèmes partageant un même modèle de domaine, défini formellement par une fonction de transition $\gamma : S \times A \to S$.

• Limites des approches récentes (Action-Centric) : Les méthodes basées sur l'apprentissage profond, telles que PlanGPT et Plansformer, traitent la planification comme une prédiction directe de séquences d'actions ($p(\pi | \Pi)$). Bien que performantes sur des données en distribution, elles souffrent de deux défauts majeurs :
  1. Dérive d'état (State Drift) : En l'absence de modélisation explicite de l'évolution du monde, les erreurs s'accumulent sur les horizons longs, surtout dans des régimes hors distribution (OOD).
  2. Inefficacité : Elles nécessitent des modèles massifs (Transformers de 100M+ paramètres) et de vastes ensembles de données pour généraliser.
• Le défi de l'invariance de taille : Une solution généralisée doit fonctionner pour des instances avec un nombre d'objets ($|O|$) bien supérieur à celui des données d'entraînement. Les représentations d'état classiques (vecteurs à taille fixe) échouent souvent à cette tâche car elles ne sont pas invariantes à la permutation ou à la taille.

2. Méthodologie : Apprentissage de Modèles de Transition (State-Centric)

Les auteurs proposent une reformulation de la planification généralisée comme un problème d'apprentissage de modèle de transition, où le modèle apprend à prédire l'état successeur plutôt que l'action suivante.

A. Représentation d'État Invariante à la Taille

Pour garantir que le modèle fonctionne sur des instances de tailles variables, l'article utilise des encodages de graphes Weisfeiler-Leman (WL) :

• L'état et l'objectif sont convertis en un graphe relationnel (Instance Learning Graph).
• Une procédure de raffinement de couleurs WL (k itérations) génère un vecteur d'embedding de dimension fixe $\phi(s, g) \in \mathbb{R}^D$.
• Cette représentation est invariante à la permutation (l'ordre des objets n'a pas d'importance) et invariante à la taille (la dimension $D$ ne dépend pas du nombre d'objets).

B. Modélisation de la Transition

Au lieu d'apprendre une politique $\pi_\theta(a_t | s_t, g)$, le système apprend une fonction de transition $f_\theta$ dans l'espace des embeddings :

• Formulation Résiduelle (Delta) : Compte tenu de la nature éparses des transitions STRIPS (la plupart des prédicats restent inchangés), le modèle prédit le vecteur de différence $\Delta_t$ plutôt que l'état complet.
  $$\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$$
• Architectures testées :
  • LSTM (Paramétrique) : Pour capturer les dépendances temporelles.
  • XGBoost (Non-paramétrique) : Pour tester si une approximation locale suffit, offrant une grande efficacité.

C. Décodage Neuro-Symbolique

Pour garantir la validité symbolique et corriger les erreurs de prédiction neuronale, les auteurs utilisent une boucle de décodage hybride (Algorithme 1) :

1. Le modèle neural prédit l'embedding cible $\hat{\phi}(s_{t+1})$.
2. Un solveur symbolique énumère tous les successeurs valides possibles $Succ(s_t)$ via la fonction de transition réelle $\gamma$.
3. Le successeur dont l'embedding est le plus proche de la prédiction neuronale est sélectionné :
   $$s_{t+1} = \arg \min_{s' \in Succ(s_t)} \| \phi(s') - \hat{\phi}(s_{t+1}) \|$$
4. L'action correspondante est extraite et ajoutée au plan.

3. Contributions Clés

1. Formulation State-Centric : Introduction d'une approche où le modèle apprend explicitement la dynamique du monde (transition d'état) plutôt que la séquence d'actions, permettant une validation et une correction en ligne.
2. Évaluation Systématique des Représentations : Démonstration que les représentations invariantes à la taille (WL) sont indispensables pour la généralisation hors distribution, contrairement aux encodages factorisés à taille fixe (FSF).
3. Efficacité Échantillonnaire et Paramétrique : Preuve empirique que des modèles compacts (LSTM ~1M de paramètres, XGBoost ~115k nœuds) surpassent ou égalent les Transformers massifs (25M–220M de paramètres) avec des données d'entraînement non augmentées et beaucoup moins d'échantillons.

4. Résultats Expérimentaux

Les expériences ont été menées sur quatre domaines de référence (Blocksworld, Gripper, Logistics, VisitAll) avec des splits de données incluant l'extrapolation stricte (taille d'instance > taille d'entraînement).

• Performance en Extrapolation (OOD) :
  • Les méthodes Action-Centric (Plansformer, PlanGPT, SymT) échouent presque totalement (0% de succès) sur l'extrapolation stricte, sauf dans des cas très limités.
  • Les modèles State-Centric avec WL et Delta (notamment WL-XGBoost) atteignent des taux de succès significatifs (ex: 0.45 sur Blocksworld, 0.87 sur VisitAll), surpassant les baselines Transformer.
• Impact de la Représentation : Les encodages FSF (taille fixe) échouent à généraliser au-delà de la taille d'entraînement, confirmant la nécessité de l'invariance structurelle.
• Impact du Modèle Résiduel : La prédiction de delta améliore considérablement les performances des modèles non-paramétriques (XGBoost) en exploitant la parcimonie des transitions STRIPS.
• Limites : La méthode échoue sur le domaine Logistics en extrapolation stricte, en raison de couplages causaux hiérarchiques complexes qui dépassent la capacité d'une prédiction de transition à un pas.

5. Signification et Conclusion

Cet article démontre que l'apprentissage explicite de la physique du domaine (modèle de transition) constitue un biais inductif plus fort pour la généralisation que l'augmentation de la taille des modèles (scale) ou des données.

• Efficacité : Il est possible d'obtenir une planification généralisée robuste avec des modèles légers et peu de données, à condition d'utiliser des représentations structurelles appropriées (WL).
• Robustesse : L'interface neuro-symbolique assure que chaque étape du plan reste valide par rapport aux règles du domaine, éliminant la dérive d'état.
• Perspectives : Le travail ouvre la voie à des approches de planification généralisée plus économes en ressources, bien que des défis subsistent pour les domaines à dépendances hiérarchiques profondes.

En résumé, l'article propose un retour aux modèles basés sur l'état, modernisés par l'apprentissage profond et les graphes, pour surmonter les limites des approches purement séquentielles basées sur les Transformers.