💻 computer science

Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning

Cet article présente un codage holistique efficace et une approche IW(1) abstraite qui exploitent les GNN relationnels pour surmonter les limites d'évolutivité et d'expressivité dans la planification généralisée, atteignant des performances de pointe sur le benchmark IPC 2023 en surpassant les méthodes antérieures, y compris le planificateur classique LAMA.

Auteurs originaux : Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

Publié 2026-05-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, 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 enseigniez à un robot comment résoudre un labyrinthe massif et en constante évolution. Le labyrinthe change à chaque partie : parfois il y a 10 pièces, parfois 10 000. L'objectif est d'enseigner au robot un seul « code de règles » (une politique) qui fonctionne pour n'importe quelle version du labyrinthe, quelle que soit sa taille.

Ce papier présente une nouvelle méthode pour enseigner ce robot, résolvant deux problèmes majeurs qui ont freiné les méthodes précédentes : la surcharge de mémoire et la lenteur de réflexion.

Voici la décomposition de leur solution à l'aide d'analogies simples :

1. Le Problème : La « Bibliothèque de Babel »

Dans le passé, lorsque le robot tentait de planifier son prochain mouvement, il examinait chaque étape future possible, une par une.

L'Ancienne Méthode : Imaginez que vous êtes dans une bibliothèque contenant un million de livres. Pour décider quel livre lire ensuite, vous devez vous rendre à chaque livre individuellement, lire la première page, prendre une note, puis revenir en arrière. Si vous avez 1 000 livres, cela représente 1 000 allers-retours. Si vous en avez un million, vous n'achèverez jamais la tâche.
La Limite : À mesure que le « labyrinthe » (le problème de planification) s'agrandit, le nombre de « livres » (mouvements possibles) explose. Les méthodes d'IA précédentes manquaient de mémoire informatique ou prenaient trop de temps pour réfléchir, surtout lorsque le nombre d'objets (comme des blocs ou des voitures) atteignait les milliers observés dans les récentes compétitions.

2. La Première Innovation : La « Capture Delta » (Encodage Delta Agrégé)

Les auteurs ont réalisé qu'ils n'avaient pas besoin de relire toute la bibliothèque à chaque fois. Ils avaient seulement besoin de savoir ce qui avait changé.

L'Analogie : Au lieu de prendre une photo de toute la bibliothèque à chaque fois que vous déplacez un livre, vous posez simplement un petit « post-it » indiquant : « Le Livre A a été déplacé de l'Étagère 1 à l'Étagère 2. »
Fonctionnement : La nouvelle méthode, appelée Delta Agrégé (AD), traite l'arbre de planification du robot comme une seule carte connectée. Au lieu de traiter chaque état futur comme une image séparée et lourde, elle encode uniquement les différences (les « deltas ») entre l'état actuel et le suivant.
Le Résultat : Le robot peut examiner l'ensemble de la carte des possibilités d'un seul coup d'œil (un « passage avant ») plutôt que de les vérifier un par un. Cela a réduit les besoins en mémoire de plus de 10 fois, permettant au robot de gérer des problèmes massifs qui faisaient auparavant planter l'ordinateur.

3. La Deuxième Innovation : La « Lentille Floue » (Largeur Abstraite)

Même avec cette nouvelle astuce de mémoire, le robot devait encore vérifier si un mouvement spécifique était « nouveau » ou « novateur ». Dans un monde comportant des milliers d'objets, vérifier chaque détail spécifique individuellement est lent.

L'Analogie : Imaginez que vous cherchez une voiture rouge spécifique dans un parking.
- L'Ancienne Méthode : Vous vérifiez chaque voiture individuellement : « Est-ce la Ford rouge ? Est-ce la Toyota rouge ? Est-ce la Honda rouge ? »
- La Nouvelle Méthode (Largeur Abstraite - AIW) : Vous mettez une « lentille floue ». Vous arrêtez de vérifier les modèles spécifiques de voitures. Au lieu de cela, vous vous demandez simplement : « Y a-t-il une voiture rouge ici ? » Vous traitez toutes les voitures rouges comme le même « type » d'objet.
Fonctionnement : Ils ont introduit la Largeur Abstraite (AIW). Lorsqu'il vérifie si un mouvement est nouveau, l'IA ignore l'identité spécifique des objets (comme « Bloc #452 ») et ne regarde que leur type général (comme « Bloc »).
Le Résultat : Cela transforme une recherche qui croît de façon exponentielle avec le nombre d'objets en une recherche qui croît de façon linéaire. C'est comme vérifier une liste de 100 types de voitures au lieu de 10 000 voitures individuelles. C'est beaucoup plus rapide, mais cela trouve toujours les « sous-objectifs » importants nécessaires pour résoudre l'énigme.

4. Le Résultat : Un Super-Planificateur

En combinant l'astuce de mémoire du « Post-it » avec le style de réflexion de la « Lentille Floue », les auteurs ont créé un planificateur qui :

Monte en Échelle : Il peut résoudre des problèmes comportant des centaines d'objets (comme une tour de 488 blocs) qui ont mis en échec les IA précédentes.
Surpasse les Meilleurs : Lors de la Compétition Internationale de Planification 2023 (un test majeur pour les planificateurs d'IA), leur méthode a battu les champions précédents, y compris un planificateur classique très performant appelé LAMA.
Gère des Énigmes Difficiles : Il a résolu des domaines complexes (comme « Satellite » et « Rovers ») qui nécessitent une logique plus avancée que ce que la plupart des modèles d'IA peuvent généralement gérer.

Résumé

Ce papier traite de l'enseignement à une IA d'arrêter d'essayer de mémoriser chaque détail d'un monde massif et changeant. Au lieu de cela, il enseigne à l'IA à :

Se souvenir uniquement de ce qui a changé (économisant d'énormes quantités de mémoire).
Regrouper les choses similaires (réfléchissant plus vite en ignorant les détails inutiles).

Le résultat est une politique générale capable de naviguer efficacement dans d'immenses labyrinthes complexes, résolvant des problèmes qui étaient auparavant trop vastes pour être gérés par les ordinateurs.

Résumé Technique : Encodage Efficace par Anticipation et Largeur Abstraite pour l'Apprentissage de Politiques Générales en Planification Classique

Énoncé du Problème

La planification généralisée vise à apprendre des politiques qui se généralisent à de vastes collections d'instances de planification au sein d'un même domaine, ne différant que par les états initiaux, les objectifs et les nombres d'objets. Bien que les approches récentes utilisant des Réseaux de Neurones à Graphes (GNN) aient montré des promesses, elles font face à des limitations significatives d'évolutivité et d'expressivité lorsqu'elles sont appliquées à des instances à grande échelle, telles que celles trouvées dans la Compétition Internationale de Planification (IPC) 2023.

Plus précisément, les travaux antérieurs sur les politiques de Largeur Itérée (IW) utilisent des recherches d'anticipation IW(1) pour définir des « sauts » au-dessus de multiples transitions, simplifiant ainsi la structure du problème. Cependant, les implémentations existantes souffrent de deux goulots d'étranglement principaux :

Inefficacité Computationnelle : L'évaluation individuelle de chaque état successeur entraîne un encodage redondant des descriptions d'états partagées, provoquant une mauvaise mise à l'échelle des coûts de mémoire et de calcul à mesure que le nombre d'objets et d'atomes augmente.
Limites d'Expressivité et de Mise à l'Échelle : Les vérifications de nouveauté standard IW(1) évoluent linéairement avec le nombre d'atomes instanciés. Dans des domaines comportant des milliers d'objets, le nombre d'atomes instanciés croît de manière polynomiale, rendant la recherche d'anticipation inefficace. De plus, les modèles restreints aux successeurs immédiats manquent souvent d'expressivité pour dériver les caractéristiques nécessaires aux domaines complexes (par exemple, ceux nécessitant une logique au-delà du fragment C2).

Méthodologie

L'article propose une approche unifiée combinant deux innovations clés : un nouvel encodage Delta-Agrégé (AD) pour les GNN Relationnels (R-GNN) et une Largeur IW(1) Abstraite (AIW(1)) pour la recherche d'anticipation.

1. Encodage Delta-Agrégé (AD)

Au lieu de traiter l'état actuel $s$ et chaque état successeur $s'$ indépendamment, les auteurs introduisent un encodage holistique qui représente l'arbre d'anticipation entier comme un seul graphe relationnel.

Représentation Jointe : L'état racine $s$ est encodé implicitement via son ensemble de relations. Les états successeurs sont représentés non pas par leurs descriptions d'état complètes, mais par des nœuds-objets d'état ( $o_{s'}$ ) qui encodent uniquement les différences (prédicats ajoutés et supprimés) par rapport à la racine.
Structure de l'Arbre : L'encodage inclut des atomes explicites représentant les transitions entre les successeurs et des nœuds de profondeur pour capturer la profondeur de la recherche. Cela permet au R-GNN d'échanger des informations directement entre les nœuds successeurs et de calculer des plongements pour tous les états en une seule passe avant.
Efficacité : Cette approche évite le ré-encodage des descriptions d'états partagées, réduisant l'utilisation de la mémoire d'un ordre de grandeur (de >24 Go à <4 Go de VRAM dans les scénarios testés) et permettant l'évaluation simultanée de toutes les transitions.

2. Largeur IW(1) Abstraite (AIW(1))

Pour résoudre le goulot d'étranglement de mise à l'échelle des vérifications de nouveauté, les auteurs proposent une variante relâchée de IW(1) qui abstrait les atomes d'état lors des tests de nouveauté.

Abstraction Relationnelle : Au lieu de tester des atomes entièrement instanciés, AIW(1) remplace itérativement tous les arguments d'un atome $n$ -aire, sauf un, par son type le plus spécifique (par exemple, remplacer l'objet $o$ par $type(o)$). Un atome est considéré comme nouveau si l'une de ses formes abstraites est nouvelle.
Changement de Complexité : Cette modification déplace la complexité dans le pire des cas de la recherche de nouveauté d'une dépendance linéaire par rapport au nombre d'atomes instanciés à une dépendance linéaire par rapport au nombre d'objets.
Préservation de l'Objectif : Les atomes mentionnés dans l'objectif ne sont pas abstraits pour garantir que la détection de l'objectif reste précise.
Avantage : Cela permet à l'anticipation de s'adapter à des instances comportant des milliers d'objets tout en capturant toujours des structures de sous-objectifs significatives et en simplifiant la structure des coûts pour l'agent d'apprentissage.

Procédure d'Entraînement

Le R-GNN est entraîné en utilisant l'apprentissage Q profond avec une variante levée de l'Expérience de Regret Rétrospectif (HER). La récompense est définie comme -1 par étape, faisant en sorte que la valeur Q représente le nombre négatif attendu de transitions vers l'objectif. Une fonction de perte de classement auxiliaire est introduite pour imposer l'ordre de profondeur dans l'arbre d'anticipation, garantissant que l'agent apprend à éviter les impasses causées par des sauts trop lointains (par exemple, dans le domaine Spanner).

Contributions Clés

Encodage Delta-Agrégé (AD) : Un nouvel encodage d'entrée pour les R-GNN qui représente des arbres d'anticipation entiers de manière conjointe via les différences d'état. Cela permet une évaluation en une seule passe de tous les successeurs, réduisant considérablement l'empreinte mémoire et le temps d'entraînement.
Largeur IW(1) Abstraite (AIW(1)) : Un mécanisme d'anticipation évolutif qui réduit la complexité de la recherche de nouveauté de polynomiale en atomes à linéaire en objets en utilisant une abstraction basée sur les types.
Performances de l'État de l'Art : La combinaison de AIW et AD établit de nouvelles références de performance sur la piste d'apprentissage de l'IPC 2023 et d'autres domaines, surpassant à la fois les politiques apprises précédemment et des planificateurs classiques puissants comme LAMA.

Résultats Expérimentaux

Les auteurs ont évalué leur approche sur le benchmark IPC 2023 (900 instances réparties sur 10 domaines) et un ensemble étendu de domaines (incluant Grid et Logistics).

Performance IPC 2023 : La méthode AIW–AD a atteint une couverture totale de 74 % (668/900 instances), surpassant significativement :
- IW–AD (59 %) : Démontrant la valeur de l'abstraction.
- AIW–Ext (51 %) et IW–Ext (51 %) : Démontrant la valeur de l'encodage AD.
- LAMA (65 %) : La forte base de référence classique.
- Flat AA (58 %) : Politiques plates sans anticipation.
Spécificités par Domaine :
- Satellite : AIW–AD a résolu 98 % des instances, résolvant entièrement le domaine où d'autres méthodes apprises peinaient.
- Rovers & Childsnack : Des améliorations significatives ont été observées, bien que les instances difficiles dans Childsnack restent un défi en raison de facteurs de branchement massifs (des millions d'actions).
- Sokoban & Floortile : Les performances sont restées faibles, cohérentes avec la difficulté connue de ces domaines PSPACE-complets ou structurellement complexes pour les politiques sans recherche.
Évolutivité : La méthode a géré avec succès des instances comportant jusqu'à 488 blocs (Blocksworld) et plus de 290 000 atomes (Rovers), là où les formulations précédentes de politiques IW échouaient en raison de contraintes de mémoire.
Expressivité : L'approche s'est généralisée avec succès à des domaines nécessitant des caractéristiques au-delà du fragment logique C2 (par exemple, Satellite, Rovers, Grid, Logistics), suggérant que le mécanisme d'anticipation réduit la charge d'expressivité sur l'architecture neuronale.

Importance et Revendications

L'article revendique que l'anticipation basée sur la largeur efficace est un facilitateur critique pour la mise à l'échelle de la planification généralisée. L'importance du travail réside dans deux domaines principaux :

Évolutivité : En découplant la complexité de la recherche d'anticipation du nombre d'atomes instanciés (via AIW) et la complexité de l'encodage neuronal du nombre de transitions (via AD), l'approche rend possible l'apprentissage de politiques pour des instances de planification massives qui étaient auparavant intraitables pour les méthodes apprises.
Réduction des Exigences d'Expressivité : Le mécanisme d'anticipation simplifie la structure du problème pour l'agent d'apprentissage. En « sautant » par-dessus des séquences de décisions primitives, la politique n'a besoin d'apprendre que des décisions de haut niveau. Cela permet à des modèles à expressivité limitée (R-GNN standards) de résoudre des domaines qui nécessiteraient autrement des caractéristiques complexes au-delà du fragment logique C2.

Les auteurs concluent que leur approche représente un nouvel état de l'art en planification généralisée, démontrant que la combinaison d'une recherche raisonnée (anticipation) avec un encodage neuronal efficace permet aux politiques apprises de s'adapter efficacement tout en maintenant des performances élevées à travers des domaines divers et complexes.