🤖 AI

Learning to Search and Searching to Learn for Generalization in Planning

Ce papier propose un cadre d'auto-amélioration qui intègre un Réseau de Neurones à Graphes Relationnels avec une recherche $\mathrm{WA}^\star$ pour permettre aux agents d'apprentissage par renforcement profond d'atteindre une forte généralisation zéro-shot dans des domaines de planification à récompenses rares, en résolvant des instances de problèmes significativement plus grandes sans recherche ni démonstrations d'experts.

Auteurs originaux : Michael Aichmüller, Yannik Hesse, Hector Geffner

Publié 2026-05-26

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Michael Aichmüller, Yannik Hesse, Hector Geffner

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 essayez d'enseigner à un robot comment résoudre un puzzle complexe, comme un gigantesque jeu de Sokoban (où vous poussez des boîtes vers des emplacements spécifiques) ou Blocksworld (empiler des blocs dans un certain ordre).

Le grand défi ne consiste pas seulement à résoudre un puzzle ; il s'agit d'enseigner au robot à résoudre n'importe quelle version de ce puzzle, même celles qu'il n'a jamais vues auparavant, avec plus de boîtes, des positions de départ différentes ou des objectifs plus vastes. C'est ce qu'on appelle la généralisation.

Voici comment l'article « Learning to Search and Searching to Learn » (Apprendre à chercher et chercher pour apprendre) aborde ce problème, expliqué simplement :

1. Le Problème : Se perdre dans le labyrinthe

Dans l'entraînement standard de l'IA (Apprentissage par Renforcement Profond), le robot apprend généralement en effectuant une étape, en observant ce qui se passe, puis en en effectuant une autre. C'est comme traverser un labyrinthe sombre en suivant le mur à la main.

Le Problème : Dans ces puzzles de planification, les « récompenses » (trouver la solution) sont très rares. Si le robot erre au hasard, il pourrait mettre un million d'années à trouver la sortie. Il reste coincé dans des impasses ou des boucles.
L'Ancienne Méthode : Certaines méthodes tentent de montrer la solution au robot au préalable (comme un enseignant montrant la clé des réponses), mais c'est tricher. D'autres tentent d'apprendre en marchant depuis l'objectif vers l'arrière, ce qui ne fonctionne pas toujours pour ces types spécifiques de puzzles logiques.

2. La Solution : La « Carte Intelligente » et la « Boucle d'Auto-amélioration »

Les auteurs proposent une nouvelle méthode appelée GSP (Generalized Search for Planning). Au lieu de marcher à l'aveugle, ils donnent au robot deux super-pouvoirs qui s'aident mutuellement :

A. La « Carte Intelligente » (L'Heuristique)

Imaginez que le robot possède une carte magique (un réseau de neurones) qui examine le puzzle actuel et devine : « Si je pousse cette boîte ici, à quel point serai-je proche de la ligne d'arrivée ? »

Cette carte ne fait pas que deviner ; elle apprend de l'expérience.
Crucialement, cette carte est construite à l'aide de Réseaux de Neurones à Graphes Relationnels. Imaginez les pièces du puzzle (blocs, boîtes) comme des personnages dans une histoire. La carte comprend les relations entre eux (par exemple, « La boîte A est au-dessus de la boîte B ») plutôt que de simplement les voir comme des pixels. Cela permet à la carte de comprendre les règles même si le puzzle devient énorme.

B. La « Recherche Intelligente » (L'Explorateur)

Au lieu de faire un pas à la fois, le robot utilise une Recherche Meilleur-D'Abord (spécifiquement un algorithme appelé WA*).

L'Analogie : Imaginez que vous cherchez un chien perdu dans une forêt.
- RL Standard (Recherche en temps réel) : Vous choisissez un chemin au hasard, marchez 10 pas, vérifiez si le chien est là. Si non, vous revenez en arrière et essayez un autre chemin au hasard. Vous gaspillez beaucoup d'énergie.
- GSP (Recherche Meilleur-D'Abord) : Vous regardez votre Carte Intelligente. Elle pointe vers les 5 chemins les plus prometteurs. Vous explorez ces chemins tous en même temps dans votre esprit, vérifiant lequel semble le meilleur. Vous ne vous engagez que sur le chemin que la carte indique comme étant le plus susceptible de mener au chien.

3. La Boucle Magique : « Apprendre à Chercher, Chercher pour Apprendre »

C'est l'innovation centrale. Les deux parties ci-dessus s'alimentent mutuellement dans un cycle :

Chercher pour Apprendre : Le robot utilise sa Carte Intelligente actuelle, imparfaite, pour lancer une Recherche Intelligente sur un puzzle. Il trouve une solution (ou s'en rapproche).
Les Données : Le processus de recherche génère une mine d'or de données : « Quand j'étais dans cette situation, effectuer cette action a mené à une solution. »
Apprendre à Chercher : Le robot utilise ces nouvelles données pour mettre à jour et améliorer la Carte Intelligente. La carte devient meilleure pour deviner quels mouvements sont bons.
Répéter : Maintenant, avec une meilleure carte, le robot peut rechercher des puzzles encore plus difficiles plus efficacement. La recherche trouve de meilleures données, ce qui rend la carte encore plus intelligente.

C'est un cycle d'auto-amélioration : La recherche enseigne à la carte, et la carte guide la recherche.

4. Les Résultats : Résoudre l'Impossible

L'article a testé cela sur des benchmarks très difficiles :

Blocksworld : Le robot a été entraîné sur des puzzles avec moins de 30 blocs. Lorsqu'il a été testé sur un puzzle avec 488 blocs (un saut massif en taille), il l'a résolu sans avoir besoin de chercher du tout. Il a simplement regardé la carte et savait exactement quoi faire. C'est ce qu'on appelle la « généralisation zéro-shot ».
Sokoban & The Witness : Il a résolu près de 100 % de ces puzzles complexes, trouvant souvent des solutions beaucoup plus rapides (avec moins d'étapes) que les autres méthodes d'IA de pointe.
PushWorld : Il a géré de nouveaux niveaux plus difficiles qu'il n'avait jamais vus auparavant, surpassant l'IA standard qui repose sur une exploration aléatoire.

Résumé

L'article présente un système où une IA apprend à résoudre des puzzles logiques en utilisant une carte intelligente et apprenante pour guider une recherche systématique.

Au lieu d'errer à l'aveugle, elle utilise la carte pour choisir les meilleurs chemins.
Au lieu de simplement mémoriser un puzzle, elle apprend les relations entre les objets afin de pouvoir résoudre des puzzles de n'importe quelle taille.
La recherche et l'apprentissage se renforcent mutuellement, créant un robot qui devient meilleur pour résoudre de nouveaux problèmes jamais vus simplement en s'entraînant sur d'anciens.

En bref : Ils ont enseigné à l'IA d'arrêter de deviner et de commencer à planifier, puis ont enseigné au planificateur comment apprendre de sa propre planification.

Résumé Technique : Apprendre à Rechercher et Rechercher pour Apprendre en vue de la Généralisation dans la Planification

Énoncé du Problème

La généralisation combinatoire demeure un défi central en Apprentissage par Renforcement Profond (DRL), où les politiques ou les fonctions de valeur doivent généraliser à des scénarios hors distribution définis par une structure de problème commune. La planification classique offre un terrain d'essai idéal pour ce problème car la structure relationnelle sous-jacente (prédicats et schémas d'actions) est fixe et explicite, tandis que les instances varient en nombre d'objets, états initiaux et objectifs.

Cependant, les approches DRL standard peinent dans les domaines de planification à récompense sparse. La recherche en temps réel (transitions itératives état-à-état), typique des algorithmes d'RL comme LRTA* ou RTDP, est inefficace pour trouver des plans dans ces contextes. À l'inverse, les planificateurs classiques utilisent la recherche best-first (par exemple A*, WA*) mais s'appuient sur des heuristiques conçues à la main. Bien que des travaux récents aient tenté d'apprendre des politiques ou des heuristiques générales, les méthodes existantes reposent souvent sur la recherche en temps réel, l'apprentissage supervisé à partir de démonstrations d'experts, ou le reétiquetage rétrospectif, échouant à établir une boucle d'auto-amélioration où la recherche et l'apprentissage se renforcent mutuellement pour atteindre une généralisation zero-shot à travers des tailles de problèmes variables.

Méthodologie : Recherche Généralisée pour la Planification (GSP)

Les auteurs proposent GSP, un cadre d'auto-amélioration qui combine la recherche best-first avec l'apprentissage Q pour apprendre des fonctions générales action-valeur ( $Q_\theta$ ).

Boucle Principale

Apprentissage Guidé par la Recherche : Au lieu de la recherche en temps réel, GSP utilise Weighted A (WA)** pour résoudre les instances d'entraînement. La recherche est guidée par les valeurs $Q_\theta(s, a)$ apprises actuelles.
Génération de Données : Au fur et à mesure que WA* développe des nœuds, il génère un tampon de replay de transitions. Crucialement, la recherche fournit des signaux de supervision que l'RL standard ne possède pas :
- Chemins vers l'Objectif : Lorsqu'un objectif est atteint, l'algorithme remonte pour attribuer des valeurs de retour réel à l'objectif aux paires sur le chemin de la solution.
- Impasses : Si un état est une impasse (aucune action applicable), la paire parente se voit attribuer une pénalité de retour fixe.
- Bornes Inférieures : La recherche fournit une borne inférieure sur le retour optimal pour toute paire état-action rencontrée sur un chemin de solution.
Mise à Jour Q-Learning : Le réseau $Q_\theta$ est mis à jour en utilisant ces cibles dérivées de la recherche. Pour les paires de chemins vers l'objectif, la cible est $\max(R, \hat{y})$ , où $R$ est la borne inférieure dérivée de la recherche et $\hat{y}$ est la cible standard de bootstrap. Cela empêche les estimations de valeur de chuter en dessous de ce que la recherche a déjà prouvé réalisable.
Sélection d'Instances : Pour optimiser l'efficacité de l'apprentissage, le cadre maintient trois pools d'instances (non résolues, résolues et satisfaites) et en échantillonne avec des poids croissant exponentiellement, priorisant les instances qui fournissent les mises à jour les plus informatives (par exemple, celles avec des solutions sous-optimales).

Représentation : R-GNN Relationnels

Pour assurer la généralisation à travers différents nombres d'objets et d'objectifs, $Q_\theta$ est représenté par un Réseau de Neurones Graphiques Relationnel (R-GNN).

Entrée : Un état $s$ et un objectif $g$ sont encodés comme un ensemble d'atomes ground. Les actions applicables sont explicitement représentées en introduisant des "objets d'action" et des atomes auxiliaires, permettant au réseau d'évaluer des choix d'actions spécifiques dans le contexte de l'état.
Architecture : Le réseau utilise un passage de messages sur la structure relationnelle. Des MLP spécifiques aux prédicats génèrent des messages basés sur les rôles des arguments, qui sont agrégés via des fonctions invariantes par permutation.
Sortie : Un MLP de lecture partagé combine l'embedding de l'objet d'action spécifique avec un résumé mis en commun de l'état et de l'objectif pour produire la valeur Q. Cette architecture garantit que le modèle apprend un principe de notation commun pour les actions ancrées plutôt que des prédicteurs séparés pour chaque schéma.

Contributions Clés

Boucle d'Auto-Amélioration Recherche-Apprentissage : L'article introduit un cadre où la recherche best-first (WA*) génère des données d'entraînement de haute qualité (incluant des bornes inférieures et des signaux d'impasse) pour mettre à jour une heuristique apprise, qui à son tour guide des recherches futures plus efficaces.
Généralisation Zero-Shot : Les fonctions Q apprises fonctionnent comme des politiques générales capables de résoudre des instances avec significativement plus d'objets et des objectifs différents de ceux vus pendant l'entraînement, sans nécessiter de recherche au moment du test dans de nombreux cas.
Cadre Unifié : L'approche s'applique uniformément à des domaines divers, des benchmarks du Concours International de Planification (IPC) 2023 aux puzzles combinatoires (Sokoban, The Witness) et au domaine PushWorld, en utilisant une architecture unique et un ensemble d'hyperparamètres.
Supériorité sur la Recherche en Temps Réel : Le travail démontre que le remplacement de la recherche en temps réel par la recherche best-first dans la boucle d'apprentissage est crucial pour le succès dans les domaines de planification à récompense sparse et fort facteur de branchement.

Résultats Expérimentaux

Les auteurs ont évalué GSP sur trois catégories de benchmarks :

Piste d'Apprentissage IPC 2023 :
- Exécution Gourmande ( $GSP_\pi$ ) : A atteint 100 % de couverture sur Blocksworld, Miconic et Spanner, surpassant des bases de référence comme Lifted HER, LAMA et des politiques de style AlphaZero.
- Guidé par la Recherche ( $GSP_{WA^*}$ ) : A montré des résultats mitigés ; bien qu'il ait amélioré la couverture sur des puzzles comme Sokoban (14 % $\to$ 32 %), il a parfois réduit la couverture sur des domaines à facteurs de branchement massifs (par exemple Blocksworld) où l'heuristique apprise, bien que bonne pour le classement local, manquait de calibration globale.
- Mise à l'Échelle : Les heuristiques entraînées sur des instances de Blocksworld avec <30 blocs ont résolu avec succès des instances avec 488 blocs sans recherche.
Puzzles Combinatoires (Sokoban, The Witness, 24-Puzzle) :
- Sur Sokoban, $GSP_{WA^*}$ a résolu 100 % des instances avec une moyenne de 207 développements, surpassant significativement WA* avec des heuristiques standards (3298 développements) et DeepCubeA (1050 développements).
- Sur The Witness, la méthode a résolu toutes les instances, démontrant la valeur de l'entraînement sur les états d'impasse.
- Sur 24-Puzzle, la méthode a échoué à trouver des solutions pendant l'entraînement, soulignant que l'approche nécessite la capacité de trouver au moins une solution pour amorcer l'apprentissage, ce qui est difficile dans des puzzles fixes extrêmement difficiles sans heuristiques informées initiales.
PushWorld :
- Entraîné sur le Niveau 0, le modèle a généralisé au Niveau 1. $GSP_{WA^*}$ a résolu 48/63 instances du Niveau 1 avec des plans plus courts et ~30 $\times$ moins de développements que le planificateur classique LAMA.
- En tant que politique gourmande, il a surpassé significativement les bases de référence d'RL sans modèle (DQN, PPO).

Signification et Revendications

L'article revendique que la recherche best-first est un mécanisme d'exploration supérieur pour l'apprentissage par renforcement généralisé lorsque le modèle de transition est connu, particulièrement dans les domaines à récompense sparse où la recherche en temps réel échoue à découvrir des trajectoires informatives.

La signification principale réside dans la démonstration d'un cycle d'auto-renforcement : la recherche fournit les cibles d'entraînement (bornes inférieures, impasses) qui permettent à l'heuristique de s'améliorer, et l'heuristique améliorée rend les recherches ultérieures plus efficaces. Cela permet au système d'apprendre des politiques générales capables de résoudre des problèmes de taille et de complexité arbitraires sans recherche, ou des heuristiques hautement efficaces guidant la recherche vers des solutions optimales.

Les auteurs notent modestement des limitations : la fonction Q apprise agit souvent comme un fort mécanisme de classement local des actions mais peut manquer de calibration globale sur l'ensemble du front de recherche, ce qui peut conduire à des performances sous-optimales en WA* sur des domaines à facteurs de branchement extrêmement grands. Ils suggèrent que les travaux futurs pourraient se concentrer sur l'amélioration de la généralisation de la valeur à travers les états et sur la combinaison de la recherche best-first avec les forces complémentaires de la recherche en temps réel et du reétiquetage rétrospectif d'expérience.