On Sample-Efficient Generalized Planning via Learned Transition Models

Deze paper toont aan dat het formuleren van gegeneraliseerd plannen als het leren van een expliciet transitiemodel, in plaats van directe actie-voorspelling, leidt tot betere generalisatie en hogere sample-efficiëntie met kleinere modellen.

De kern

De Kern: Leren van de Regels in plaats van het Antwoord

Stel je voor dat je iemand wilt leren een legpuzzel te maken. Er zijn twee manieren om dit te doen:

1. De oude manier (Actie-gericht): Je geeft de persoon duizenden foto's van voltooide puzzels en vraagt ze om de volgende stap te raden op basis van wat ze eerder hebben gezien. Ze leren de puzzel "uit het hoofd". Als ze een nieuwe, grotere puzzel krijgen die ze nog nooit hebben gezien, raken ze in de war. Ze weten niet waarom een stukje ergens hoort, ze weten alleen dat het er vaak zo uitziet. Dit is wat de huidige AI-modellen (zoals PlanGPT) doen. Ze zijn slim, maar ze hebben enorme hoeveelheden data nodig en maken vaak fouten bij grote, nieuwe problemen.
2. De nieuwe manier van dit onderzoek (Staat-gericht): In plaats van de hele puzzel te laten zien, leer je de persoon de regels van de natuur van de puzzel. "Als je dit blokje hier legt, valt dat andere blokje er af." Je leert ze hoe de wereld verandert. Zodra ze die regels begrijpen, kunnen ze elke puzzel oplossen, of het nu 4 blokjes zijn of 100. Ze hoeven de puzzel niet uit het hoofd te leren; ze kunnen het voorspellen.

Dit onderzoek (van de Universiteit van South Carolina) zegt: "Laten we AI leren hoe de wereld verandert, in plaats van alleen welke knoppen ze moeten indrukken."

---

Hoe werkt het? (De Analogie van de Spelregels)

De onderzoekers hebben een systeem gebouwd dat werkt als een slimme voorspeller:

1. De Voorspeller (Het Model):
   Stel je voor dat je een bal gooit. Een oude AI zou zeggen: "Ik heb gezien dat mensen de bal vaak naar rechts gooien, dus ik ga naar rechts." Een nieuwe AI (deze) zegt: "Ik weet dat de zwaartekracht de bal naar beneden trekt en mijn arm hem naar voren duwt. Ik kan precies berekenen waar de bal landt."
   In dit onderzoek leert de AI niet welke actie (bijv. "pak het blok") ze moeten doen, maar welke toestand (bijv. "het blok ligt nu op de tafel") het resultaat is.

2. De Vertaler (De "Weisfeiler-Leman" Embedding):
   Dit is het magische trucje. Stel je voor dat je een taal spreekt die alleen werkt met 4 blokjes. Als je plotseling 100 blokjes krijgt, is die taal nutteloos.
   De onderzoekers hebben een "vertaler" bedacht die elk probleem, groot of klein, omzet in een vast formaat. Het is alsof je een enorme berg blokken in een compacte, samenvattende tekening zet. Of je nu 4 of 400 blokjes hebt, de tekening ziet er qua structuur hetzelfde uit. Hierdoor kan de AI, die is getraind op kleine puzzels, perfect werken met gigantische puzzels.

3. De Controleur (Neuro-Symbolische Verificatie):
   De AI maakt soms fouten in haar voorspelling (net als wij soms). Om dit op te vangen, hebben de onderzoekers een controleur toegevoegd.

   • De AI zegt: "Ik denk dat het blok hier landt."
   • De controleur (een traditionele, strikte computer) kijkt na: "Wacht, volgens de spelregels is dat onmogelijk!"
   • De controleur corrigeert de AI en kiest de juiste, wiskundig correcte stap.
     Dit zorgt ervoor dat de AI nooit een onmogelijke zet doet, zelfs als ze twijfelt.

Waarom is dit zo belangrijk?

• Efficiëntie: De oude modellen (zoals PlanGPT) zijn als een olifant: ze zijn groot, zwaar en hebben enorme hoeveelheden voedsel (data) nodig om te leren. Het nieuwe model is als een mier: klein, snel en leert met heel weinig data. Het onderzoek laat zien dat hun kleine model net zo goed (of zelfs beter) presteert bij nieuwe, grote problemen als die enorme olifanten.
• Generalisatie: Als je een AI traint op een kamer met 3 stoelen, kan een oude AI vaak niet werken in een zaal met 30 stoelen. Dit nieuwe model begrijpt het concept van "stoel" en "ruimte", dus het werkt in beide kamers.
• Geen "Hallucinaties": Omdat de AI de regels van de wereld volgt en niet zomaar raadt, verdwijnt het probleem van "state drift" (waarbij de AI na een tijdje vergeet hoe de wereld eruitziet en onzin gaat doen).

Samenvatting in één zin

In plaats van AI te laten gissen naar het antwoord door miljoenen voorbeelden te zien, hebben de onderzoekers de AI geleerd hoe de wereld werkt met een slimme vertaler en een strenge controleur, waardoor ze met veel minder moeite en minder data complexe problemen kan oplossen die ze nog nooit heeft gezien.

Kortom: Ze hebben de AI niet leren rekenen, maar ze hebben haar leren redeneren.

Technische samenvatting

Probleemstelling

Het paper adresseert het probleem van gegeneraliseerd plannen (Generalized Planning - GP). Het doel is om oplossingsstrategieën te ontwikkelen die niet alleen werken voor één specifiek probleem, maar generaliseren over een hele familie van planningsproblemen binnen eenzelfde domein.

Traditionele benaderingen gebruiken symbolische abstracties en expliciete redenering over de overgangsfunctie $\gamma: S \times A \rightarrow S$. Recentere, op deep learning gebaseerde methoden (zoals PlanGPT en Plansformer) benaderen dit echter als een actie-gecentreerd probleem: ze voorspellen direct een reeks acties ($p(\pi | \Pi)$) zonder de wereldtoestand expliciet te modelleren.

De beperkingen van bestaande methoden zijn:

1. State Drift: Door het ontbreken van een expliciet wereldmodel, hopen fouten zich op in lange planninghorizons, wat leidt tot een toestand die afwijkt van de werkelijkheid (state drift).
2. Data- en Model-efficiëntie: Transformer-achtige modellen vereisen enorme datasets en zeer grote modelgroottes om te generaliseren.
3. Schaalbaarheid: Ze worstelen vaak met generalisatie naar grotere probleeminstanties (extrapolatie) dan die in de trainingsdata voorkwamen.

Methodologie: Toestandsgecentreerd Plannen

De auteurs stellen een nieuwe formulering voor: gegeneraliseerd plannen als het leren van een overgangsmodel (transition-model learning). In plaats van de volgende actie te voorspellen, leert het model de volgende wereldtoestand te voorspellen.

De kerncomponenten van de pipeline zijn:

1. Toestandsrepresentatie (Size-Invariant):

   • Om generalisatie naar willekeurige aantallen objecten mogelijk te maken, gebruiken ze Weisfeiler-Leman (WL) graf-embeddings.
   • Symbolische toestanden en doelen worden omgezet in een vaste dimensie vector $\phi(s, g)$, ongeacht het aantal objecten in het probleem. Dit zorgt voor permutatie- en schaalinvariantie.
   • Dit wordt vergeleken met "Fixed-Size Factored" (FSF) encodings, die een vast aantal object-slots vereisen en falen bij extrapolatie.

2. Transitiemodel Leren:

   • Het model $f_\theta$ voorspelt de update van de toestand in de embedding-ruimte.
   • Er wordt gebruik gemaakt van een residuele formulering: $\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$.
   • Het model leert dus een delta-vector ($\Delta_t$) in plaats van de volledige nieuwe toestand. Dit benut de sparsiteit van STRIPS-domeinen (waar de meeste predicates ongewijzigd blijven) en verbetert de sample-efficiëntie.
   • Twee modelarchitecturen worden getest: een parametrisch LSTM (voor sequentiële geheugen) en een niet-parametrische XGBoost regressor (voor lokale benadering).

3. Neuro-Symbolische Decoding:

   • Tijdens het plannen (inference) wordt de werkelijke symbolische toestand $s_t$ bijgehouden.
   • Het neurale model voorspelt een doel-embedding $v_t$.
   • Er wordt een symbolische zoekopdracht uitgevoerd over alle geldige opvolgers $Succ(s_t)$ (berekend via de domeinoperatoren).
   • De opvolger waarvan de embedding het dichtst bij $v_t$ ligt, wordt geselecteerd als de volgende toestand $s_{t+1}$. De bijbehorende actie wordt vervolgens afgeleid.
   • Dit garandeert dat elke stap symbolisch geldig is en corrigeert neurale voorspellingsfouten online.

Belangrijkste Bijdragen

1. Formulering: Een nieuwe, toestandsgecentreerde formulering van generaliseerd plannen via het voorspellen van opvolger-toestanden (in plaats van acties).
2. Systematische Evaluatie: Een uitgebreide studie naar de impact van verschillende toestandsrepresentaties (WL vs. FSF) en modelarchitecturen op de generalisatie-eigenschappen.
3. Empirisch Bewijs: Het aantonen dat compacte modellen (met veel minder parameters) concurrerende of betere prestaties behalen dan grote Transformer-baselines, vooral bij generalisatie naar grotere probleemgroottes (extrapolatie).

Resultaten

De experimenten zijn uitgevoerd op vier IPC-benchmarks: Blocksworld, Gripper, Logistics en VisitAll.

• Generalisatie (Extrapolatie):
  • Bestaande actie-gecentreerde methoden (Plansformer, PlanGPT, SymT) behalen vaak 0% succes bij strikte extrapolatie (problemen groter dan de trainingsdata).
  • De voorgestelde toestandsgecentreerde methoden (vooral WL-XGBoost met delta-modus) behalen aanzienlijk hogere success rates. Bijvoorbeeld in VisitAll bereikt het model 87% succes tegenover 64% voor de beste Transformer-baseline.
• Efficiëntie:
  • De auteurs gebruiken modellen met slechts ~1 miljoen parameters (LSTM) of ~115.000 boomknooppunten (XGBoost).
  • Dit staat in schril contrast met de baselines die 25 tot 220 miljoen parameters vereisen.
  • De methoden presteren goed zonder data-augmentatie, terwijl baselines vaak uitgebreide symmetrie-expansie nodig hebben.
• Representatie:
  • WL-embeddings zijn cruciaal: FSF-encodings (zonder relationele structuur) falen bijna volledig bij extrapolatie.
  • Residuele (delta) modellering verbetert de prestaties aanzienlijk in domeinen met sparsere transities.
• Beperkingen:
  • In het Logistics-domein (gekenmerkt door diepe, hiërarchische causale koppelingen) falen alle geleerde modellen bij strikte extrapolatie. Dit suggereert dat één-staps toestandvoorspelling onvoldoende is voor complexe, langdurige afhankelijkheden.

Betekenis en Conclusie

Het paper toont aan dat het expliciet leren van domein-dynamica (transitiemodellen) een sterkere inductieve bias biedt voor generalisatie dan het simpelweg vergroten van modelgrootte of data-augmentatie in actie-gecentreerde benaderingen.

Door de combinatie van schaalinvariante relationele representaties (WL) en neuro-symbolische decoding, kunnen compacte modellen robuust plannen in onbekende, grotere scenario's. Dit biedt een efficiëntere en betrouwbaardere route voor generaliseerd plannen dan de huidige trend van grote taalmodellen die direct acties voorspellen. De aanpak benadrukt dat het begrijpen van "hoe de wereld verandert" fundamenteel belangrijker is dan het memoriseren van "welke acties te nemen" voor het generaliseren van planningsstrategieën.