🤖 AI

Learning to Search and Searching to Learn for Generalization in Planning

Dit artikel stelt een zelfverbeterend raamwerk voor dat een relationeel grafisch neurale netwerk integreert met $\mathrm{WA}^\star$ -zoektocht om diepe versterkingsleeragenten in staat te stellen sterke zero-shot generalisatie te bereiken in domeinen voor planning met schaarse beloningen, waarbij aanzienlijk grotere probleeminstanties worden opgelost zonder zoektocht of expertdemonstraties.

Oorspronkelijke auteurs: Michael Aichmüller, Yannik Hesse, Hector Geffner

Gepubliceerd 2026-05-26

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Michael Aichmüller, Yannik Hesse, Hector Geffner

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een robot te leren hoe hij een complex puzzel moet oplossen, zoals een gigantisch spelletje Sokoban (waarbij je dozen naar specifieke plekken duwt) of Blocksworld (blokken stapelen in een bepaalde volgorde).

De grote uitdaging is niet alleen het oplossen van één puzzel; het is de robot leren om elke versie van die puzzel op te lossen, zelfs die welke hij nog nooit heeft gezien, met meer dozen, andere startposities of grotere doelen. Dit wordt generalisatie genoemd.

Hieronder wordt uitgelegd hoe het artikel "Learning to Search and Searching to Learn" dit probleem aanpakt, in eenvoudige bewoordingen:

1. Het Probleem: Verdwalen in het Labyrint

Bij standaard AI-training (Deep Reinforcement Learning) leert de robot meestal door één stap te zetten, te kijken wat er gebeurt, en dan een volgende stap te zetten. Dit is als door een donker labyrint lopen terwijl je met je hand tegen de muur voelt.

Het Probleem: Bij deze planningspuzzels zijn "beloningen" (het vinden van de oplossing) zeer zeldzaam. Als de robot gewoon willekeurig rondzwerft, kan het een miljoen jaar duren voordat hij de uitgang vindt. Hij blijft hangen in doodlopende straten of lussen.
De Oude Manier: Sommige methoden proberen de robot eerst de oplossing te laten zien (zoals een leraar die het antwoordblad laat zien), maar dat is valsspelen. Anderen proberen te leren door vanaf het doel terug te lopen, wat niet altijd werkt voor deze specifieke soorten logische puzzels.

2. De Oplossing: De "Slimme Kaart" en de "Zelfverbeterende Lus"

De auteurs stellen een nieuwe methode voor genaamd GSP (Generalized Search for Planning). In plaats van blind te lopen, geven ze de robot twee superkrachten die elkaar helpen:

A. De "Slimme Kaart" (De Heuristiek)

Stel je voor dat de robot een magische kaart heeft (een neurale netwerken) die naar de huidige puzzel kijkt en raadt: "Als ik deze doos hierheen duw, hoe dichterbij zal ik dan bij de finishlijn zijn?"

Deze kaart raadt niet zomaar; hij leert van ervaring.
Cruciaal is dat deze kaart is gebouwd met Relationele Grafische Neurale Netwerken. Stel je de puzzelstukken (blokken, dozen) voor als personages in een verhaal. De kaart begrijpt de relaties tussen hen (bijvoorbeeld: "Doos A staat op Doos B") in plaats van ze alleen als pixels te zien. Dit stelt de kaart in staat de regels te begrijpen, zelfs als de puzzel enorm groot wordt.

B. De "Slimme Zoeking" (De Ontdekkingsreiziger)

In plaats van één stap per keer te zetten, gebruikt de robot een Best-First Search (specifiek een algoritme genaamd WA*).

De Analogie: Stel je voor dat je op zoek bent naar een verloren hond in een bos.
- Standaard RL (Real-time search): Je kiest een willekeurig pad, loopt 10 stappen, en controleert of de hond daar is. Zo niet, dan ga je terug en probeer je een ander willekeurig pad. Je verspillt veel energie.
- GSP (Best-first search): Je kijkt naar je Slimme Kaart. Hij wijst naar de 5 meest veelbelovende paden. Je verkent die paden allemaal tegelijk in je gedachten, en controleert welke er het beste uitziet. Je committeert je alleen tot het pad dat de kaart aangeeft als het meest waarschijnlijk om naar de hond te leiden.

3. De Magische Lus: "Leren om te Zoeken, Zoeken om te Leren"

Dit is de kerninnovatie. De twee bovenstaande onderdelen voeden elkaar in een cyclus:

Zoeken om te Leren: De robot gebruikt zijn huidige, onvolmaakte Slimme Kaart om een Slimme Zoeking uit te voeren op een puzzel. Hij vindt een oplossing (of komt er dichtbij).
De Data: Het zoekproces genereert een schatkist aan data: "Toen ik in deze situatie zat, leidde die actie tot een oplossing."
Leren om te Zoeken: De robot gebruikt deze nieuwe data om de Slimme Kaart te updaten en te verbeteren. De kaart wordt beter in het raden welke zetten goed zijn.
Herhalen: Nu, met een betere kaart, kan de robot zelfs moeilijkere puzzels efficiënter zoeken. De zoektocht vindt betere data, waardoor de kaart nog slimmer wordt.

Het is een zelfverbeterende cyclus: De zoektocht leert de kaart, en de kaart leidt de zoektocht.

4. De Resultaten: Het Oplossen van het Onmogelijke

Het artikel testte dit op enkele zeer moeilijke benchmarks:

Blocksworld: De robot werd getraind op puzzels met minder dan 30 blokken. Toen hij werd getest op een puzzel met 488 blokken (een enorme sprong in grootte), loste hij deze op zonder überhaupt te hoeven zoeken. Hij keek gewoon naar de kaart en wist precies wat hij moest doen. Dit wordt "zero-shot generalization" genoemd.
Sokoban & The Witness: Hij loste bijna 100% van deze complexe puzzels op, vaak met oplossingen die veel sneller waren (met minder stappen) dan andere top-AI-methoden.
PushWorld: Hij hanteerde nieuwe, moeilijkere levels die hij nog nooit had gezien, en presteerde beter dan standaard AI die afhankelijk is van willekeurige exploratie.

Samenvatting

Het artikel introduceert een systeem waarbij een AI leert logische puzzels op te lossen door gebruik te maken van een slimme, op leren gebaseerde kaart om een systematische zoektocht te leiden.

In plaats van blind te zwerven, gebruikt hij de kaart om de beste paden te kiezen.
In plaats van slechts één puzzel te memoriseren, leert hij de relaties tussen objecten zodat hij puzzels van elke grootte kan oplossen.
De zoektocht en het leren versterken elkaar, waardoor een robot ontstaat die beter wordt in het oplossen van nieuwe, onbekende problemen door simpelweg te oefenen op oude.

Kortom: Ze leerden de AI om te stoppen met gokken en te beginnen met plannen, en leerden vervolgens de planner hoe hij uit zijn eigen plannen kan leren.

Technische Samenvatting: Leren om te zoeken en zoeken om te leren voor generalisatie in planning

Probleemstelling

Combinatorische generalisatie blijft een centrale uitdaging in Deep Reinforcement Learning (DRL), waarbij beleidslijnen of waardefuncties moeten generaliseren naar scenario's buiten de verdeling die worden gedefinieerd door een gemeenschappelijke probleemstructuur. Klassieke planning biedt een ideale testomgeving voor dit probleem, omdat de onderliggende relationele structuur (predicaten en actieschema's) vast en expliciet is, terwijl instanties variëren in aantal objecten, beginstaten en doelen.

Echter, standaard DRL-benaderingen kampen met moeilijkheden in planningsdomeinen met schaarse beloningen. Real-time zoeken (iteratieve staat-tot-staat overgangen), typisch voor RL-algoritmen zoals LRTA* of RTDP, is inefficiënt voor het vinden van plannen in deze situaties. Omgekeerd gebruiken klassieke planners best-first search (bijv. A*, WA*), maar vertrouwen ze op handgemaakte heuristieken. Hoewel recent werk heeft geprobeerd om algemene beleidslijnen of heuristieken te leren, vertrouwen bestaande methoden vaak op real-time zoeken, toezichtleren van expertdemonstraties of hindsight relabeling, en slagen ze er niet in een zelfverbeterende lus te vestigen waarin zoeken en leren elkaar wederzijds versterken om zero-shot generalisatie te bereiken over variërende probleemgroottes.

Methodologie: Generalized Search for Planning (GSP)

De auteurs stellen GSP voor, een zelfverbeterend raamwerk dat best-first search combineert met Q-learning om algemene actie-waardefuncties ( $Q_\theta$ ) te leren.

Kernlus

Zoekgeleid leren: In plaats van real-time zoeken, gebruikt GSP Weighted A (WA)** om trainingsinstanties op te lossen. Het zoeken wordt geleid door de huidige geleerde $Q_\theta(s, a)$ -waarden.
Datageneratie: Terwijl WA* knopen uitbreidt, genereert het een replay-buffer van transities. Cruciaal biedt het zoeken supervisiesignalen die standaard RL mist:
- Doelpaden: Wanneer een doel wordt bereikt, backtrack het algoritme om daadwerkelijke return-to-go-waarden toe te wijzen aan de paren op het oplossingspad.
- Doodlopende straten: Als een staat een doodlopende straat is (geen toepasbare acties), krijgt het ouderpaar een vaste strafreturn toegewezen.
- Ondergrenzen: Het zoeken biedt een ondergrens voor de optimale return voor elke staat-actie-paar die op een oplossingspad wordt aangetroffen.
Q-Learning-update: Het $Q_\theta$ -netwerk wordt bijgewerkt met deze zoekafgeleide doelen. Voor doelpad-paren is het doel $\max(R, \hat{y})$ , waarbij $R$ de zoekafgeleide ondergrens is en $\hat{y}$ het standaard bootstrap-doel. Dit voorkomt dat de waarde-schattingen dalen onder wat het zoeken al heeft bewezen haalbaar te zijn.
Instantie-selectie: Om leerefficiëntie te optimaliseren, onderhoudt het raamwerk drie pools van instanties (onopgelost, opgelost en bevredigend) en steekt er exponentieel toenemende gewichten uit, met prioriteit voor instanties die de meest informatieve updates bieden (bijv. die met suboptimale oplossingen).

Representatie: Relationele GNN's

Om generalisatie over verschillende aantallen objecten en doelen te waarborgen, wordt $Q_\theta$ gerepresenteerd door een Relationeel Graph Neural Network (R-GNN).

Input: Een staat $s$ en doel $g$ worden gecodeerd als een verzameling grondatomen. Toepasbare acties worden expliciet weergegeven door het introduceren van hulp-"actie-objecten" en atomen, waardoor het netwerk specifieke actiekeuzes kan evalueren binnen de context van de staat.
Architectuur: Het netwerk gebruikt berichtuitwisseling over de relationele structuur. Predicaatspecifieke MLP's genereren berichten op basis van argumentrollen, die worden geaggregeerd via permutatie-invariante functies.
Output: Een gedeelde readout-MLP combineert de embedding van het specifieke actieobject met een gepoolde samenvatting van de staat en het doel om de Q-waarde te produceren. Deze architectuur zorgt ervoor dat het model een gemeenschappelijk scoreprincipe leert voor gegronde acties in plaats van aparte voorspellers voor elk schema.

Belangrijkste Bijdragen

Zelfverbeterende zoek-leerlus: Het paper introduceert een raamwerk waarbij best-first search (WA*) hoogwaardige trainingsdata genereert (inclusief ondergrenzen en doodlopende straat-signalen) om een geleerde heuristiek bij te werken, die op zijn beurt efficiënter toekomstig zoeken leidt.
Zero-shot generalisatie: De geleerde Q-functies fungeren als algemene beleidslijnen die in staat zijn instanties op te lossen met aanzienlijk meer objecten en verschillende doelen dan tijdens het trainingstijdperk zijn gezien, zonder in veel gevallen zoeken tijdens de testfase te vereisen.
Unificerend raamwerk: De benadering is uniform toepasbaar op diverse domeinen, van de 2023 International Planning Competition (IPC) benchmarks tot combinatorische puzzels (Sokoban, The Witness) en het PushWorld-domein, met behulp van één architectuur en één set hyperparameters.
Superioriteit ten opzichte van real-time zoeken: Het werk toont aan dat het vervangen van real-time zoeken door best-first search in de leerlus cruciaal is voor succes in planningsdomeinen met schaarse beloningen en hoge vertakkingsfactoren.

Experimentele Resultaten

De auteurs evalueerden GSP op drie categorieën benchmarks:

2023 IPC Learning Track:
- Gierige uitvoering ( $GSP_\pi$ ): Bereikte 100% dekking op Blocksworld, Miconic en Spanner, en presteerde beter dan baselines zoals Lifted HER, LAMA en AlphaZero-achtige beleidslijnen.
- Zoekgeleid ( $GSP_{WA^*}$ ): Toonde gemengde resultaten; hoewel het de dekking verbeterde op puzzels zoals Sokoban (14% $\to$ 32%), verminderde het soms de dekking op domeinen met enorme vertakkingsfactoren (bijv. Blocksworld), waarbij de geleerde heuristiek, hoewel goed voor lokale ranking, een gebrek aan globale kalibratie vertoonde.
- Schalen: Heuristieken getraind op Blocksworld-instanties met <30 blokken losten succesvol instanties op met 488 blokken zonder zoeken.
Combinatorische Puzzels (Sokoban, The Witness, 24-Puzzle):
- Op Sokoban loste $GSP_{WA^*}$ 100% van de instanties op met gemiddeld 207 uitbreidingen, aanzienlijk beter dan WA* met standaard heuristieken (3298 uitbreidingen) en DeepCubeA (1050 uitbreidingen).
- Op The Witness loste de methode alle instanties op, wat de waarde van training op doodlopende staten aantoont.
- Op 24-Puzzle slaagde de methode er niet in oplossingen te vinden tijdens het trainingstijdperk, wat benadrukt dat de benadering de mogelijkheid vereist om ten minste één oplossing te vinden om het leren te bootstrappen, wat moeilijk is in uiterst moeilijke puzzles met vaste grootte zonder initiële geïnformeerde heuristieken.
PushWorld:
- Getraind op Niveau 0, generaliseerde het model naar Niveau 1. $GSP_{WA^*}$ loste 48/63 Niveau 1-instanties op met kortere plannen en ongeveer 30 $\times$ minder uitbreidingen dan de klassieke planner LAMA.
- Als gierig beleid presteerde het aanzienlijk beter dan model-vrije RL-baselines (DQN, PPO).

Betekenis en Beweringen

Het paper beweert dat best-first search een superieure exploratiemechanisme is voor generalisatieversterkt leren wanneer het transitiemodel bekend is, met name in domeinen met schaarse beloningen waar real-time zoeken er niet in slaagt informatieve trajecten te ontdekken.

De primaire betekenis ligt in de demonstratie van een zichzelf versterkende cyclus: het zoeken levert de trainingsdoelen (ondergrenzen, doodlopende straten) die het mogelijk maken de heuristiek te verbeteren, en de verbeterde heuristiek maakt daaropvolgend zoeken efficiënter. Dit stelt het systeem in staat algemene beleidslijnen te leren die problemen van willekeurige grootte en complexiteit kunnen oplossen zonder zoeken, of uiterst efficiënte heuristieken die zoeken leiden naar optimale oplossingen.

De auteurs merken bescheiden beperkingen op: de geleerde Q-functie fungeert vaak als een sterk lokaal actie-rangschikkingsmechanisme, maar kan een gebrek aan globale kalibratie vertonen over de gehele zoekfront, wat kan leiden tot suboptimale prestaties in WA* op domeinen met extreem grote vertakkingsfactoren. Zij suggereren dat toekomstig werk zich zou kunnen richten op het verbeteren van waardegeneralisatie over staten en het combineren van best-first search met complementaire sterke punten van real-time zoeken en hindsight experience relabeling.