💻 computer science

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

Dit artikel introduceert een efficiënte holistische codering en een geabstraheerde IW(1)-benadering die Relational GNNs benut om schaalbaarheids- en expressiviteitsbeperkingen in generalisatieplanning te overwinnen, waarmee een state-of-the-art prestatie wordt behaald op de IPC 2023-benchmark door eerdere methoden, waaronder de klassieke planner LAMA, te overtreffen.

Oorspronkelijke auteurs: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

Gepubliceerd 2026-05-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, 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 een robot leert een enorme, voortdurend veranderende doolhof op te lossen. Het doolhof verandert elke keer dat je speelt: soms zijn er 10 kamers, soms 10.000. Het doel is om de robot één enkele "regelschrift" (een beleid) te leren dat werkt voor elke versie van het doolhof, ongeacht hoe groot het wordt.

Dit artikel presenteert een nieuwe manier om die robot te leren, waarmee twee grote problemen worden opgelost die eerdere methoden hebben beperkt: geheugensoverbelasting en trage denkprocessen.

Hier is de uiteenzetting van hun oplossing met behulp van eenvoudige analogieën:

1. Het Probleem: De "Bibliotheek van Babel"

In het verleden, toen de robot probeerde zijn volgende zet te plannen, keek hij naar elke mogelijke toekomstige stap, één voor één.

De Oude Manier: Stel je voor dat je in een bibliotheek staat met een miljoen boeken. Om te beslissen welk boek je als volgende moet lezen, moet je naar elk enkel boek lopen, de eerste pagina lezen, een notitie schrijven en dan teruglopen. Als je 1.000 boeken hebt, zijn dat 1.000 tochten. Als je er een miljoen hebt, zul je het nooit afmaken.
De Beperking: Naarmate het "doolhof" (het planningsprobleem) groter wordt, explodeert het aantal "boeken" (mogelijke zetten). Vorige AI-methoden liepen tegen het einde van het computergeheugen aan of deden er te lang over om na te denken, vooral wanneer het aantal objecten (zoals blokken of auto's) de duizenden bereikte die in recente wedstrijden werden gevonden.

2. De Eerste Innovatie: De "Delta-Snapshot" (Aggregated-Delta Encoding)

De auteurs realiseerden zich dat ze niet elke keer de hele bibliotheek opnieuw hoefden te lezen. Ze hoefden alleen te weten wat er veranderde.

De Analogie: In plaats van elke keer dat je een boek verplaatst, een foto van de hele bibliotheek te maken, neem je gewoon een klein "post-it" dat zegt: "Boek A verplaatst van Plank 1 naar Plank 2."
Hoe het werkt: De nieuwe methode, genaamd Aggregated-Delta (AD), behandelt de planningsboom van de robot als één enkele, verbonden kaart. In plaats van elke toekomstige staat als een apart, zwaar beeld te verwerken, codeert het alleen de verschillen (de "deltas") tussen de huidige staat en de volgende.
Het Resultaat: De robot kan in één enkele blik (een "forward pass") naar de hele kaart van mogelijkheden kijken, in plaats van ze één voor één te controleren. Dit verlaagde de benodigde geheugenruimte met meer dan 10 keer, waardoor de robot enorme problemen kon aanpakken die eerder de computer laten crashen.

3. De Tweede Innovatie: De "Vage Lens" (Abstracted Width)

Zelfs met de nieuwe geheugentruc moest de robot nog steeds controleren of een specifieke zet "nieuw" of "novel" was. In een wereld met duizenden objecten is het controleren van elk specifiek detail traag.

De Analogie: Stel je voor dat je op zoek bent naar een specifieke rode auto op een parkeerterrein.
- De Oude Manier: Je controleert elke auto individueel: "Is dit de rode Ford? Is dit de rode Toyota? Is dit de rode Honda?"
- De Nieuwe Manier (Abstracted IW): Je zet een "vage lens" op. Je stopt met het controleren van de specifieke automodellen. In plaats daarvan vraag je gewoon: "Is er hier een rode auto?" Je behandelt alle rode auto's als hetzelfde "type" object.
Hoe het werkt: Ze introduceerden Abstracted IW (AIW). Bij het controleren of een zet nieuw is, negeert de AI de specifieke identiteit van objecten (zoals "Blok #452") en kijkt alleen naar hun algemene type (zoals "Blok").
Het Resultaat: Dit verandert een zoektocht die exponentieel groeit met het aantal objecten in een die lineair groeit. Het is alsof je een lijst van 100 soorten auto's controleert in plaats van 10.000 individuele auto's. Het is veel sneller, maar het vindt nog steeds de belangrijke "sub-doelen" die nodig zijn om de puzzel op te lossen.

4. Het Resultaat: Een Super-Planner

Door de "Post-it" geheugentruc te combineren met de "Vage Lens" denkwijze, creëerden de auteurs een planner die:

Schaalt: Het kan problemen oplossen met honderden objecten (zoals een 488-blokken toren) die eerdere AI in de steek lieten.
Presteert Beter dan de Beste: In de Internationale Planningswedstrijd van 2023 (een grote test voor AI-planners) versloeg hun methode de vorige kampioenen, waaronder een zeer sterke klassieke planner genaamd LAMA.
Hanteert Moeilijke Puzzels: Het lost complexe domeinen op (zoals "Satelliet" en "Rovers") die logica vereisen die geavanceerder is dan wat de meeste AI-modellen normaal gesproken aankan.

Samenvatting

Het artikel gaat over het leren aan een AI om te stoppen met het proberen om elk enkel detail van een enorme, veranderende wereld te onthouden. In plaats daarvan leert het de AI om:

Alleen te onthouden wat veranderde (wat enorme hoeveelheden geheugen bespaart).
Vergelijkbare dingen samen te groeperen (door onnodige details te negeren, sneller te denken).

Het resultaat is een algemeen beleid dat enorme, complexe doolhoven efficiënt kan navigeren en problemen oplost die eerder te groot waren voor computers om aan te pakken.

Technische Samenvatting: Efficiënte Vooruitkijkende Encoding en Geabstraheerde Breedte voor het Leren van Algemene Beleidslijnen in Klassieke Planning

Probleemstelling

Algemene planning heeft tot doel beleidslijnen te leren die generaliseren over grote verzamelingen van planningsinstanties binnen één enkel domein, die alleen verschillen in beginsituaties, doelen en aantallen objecten. Hoewel recente benaderingen met Graph Neural Networks (GNN's) veelbelovend zijn, lopen ze tegen aanzienlijke beperkingen in schaalbaarheid en expressiviteit aan wanneer ze worden toegepast op grootschalige instanties, zoals die in de International Planning Competition (IPC) 2023.

Specifiek maken eerdere werken over Iterated Width (IW)-beleidslijnen gebruik van IW(1)-vooruitkijkende zoekopdrachten om "sprongen" over meerdere transities te definiëren, waardoor de probleemstructuur wordt vereenvoudigd. Echter, bestaande implementaties kampen met twee hoofdflessenhals:

Rekenkundige inefficiëntie: Het individueel evalueren van elke opvolgerstaat leidt tot redundante encoding van gedeelde staatbeschrijvingen, waardoor de kosten voor geheugen en rekenkracht slecht schalen naarmate het aantal objecten en atomen toeneemt.
Beperkingen in expressiviteit en schaal: Standaard IW(1)-nieuwheidscontroles schalen lineair met het aantal grondatomen. In domeinen met duizenden objecten groeit het aantal grondatomen polynomiëel, waardoor de vooruitkijkende zoekopdracht inefficiënt wordt. Bovendien missen modellen die beperkt zijn tot directe opvolgers vaak de expressiviteit om de nodige kenmerken af te leiden voor complexe domeinen (bijvoorbeeld die welke logica vereisen die verder gaat dan het C2-fragment).

Methodologie

Het artikel stelt een geünificeerde aanpak voor die twee kerninnovaties combineert: een nieuwe Aggregated-Delta (AD)-encoding voor Relational GNN's (R-GNN's) en Abstracted IW(1) (AIW(1)) voor vooruitkijkende zoekopdrachten.

1. Aggregated-Delta (AD)-encoding

In plaats van de huidige staat $s$ en elke opvolgerstaat $s'$ onafhankelijk te verwerken, introduceren de auteurs een holistische encoding die de volledige vooruitkijkende boom als één relationeel graf voorstelt.

Gecombineerde representatie: De wortelstaat $s$ wordt impliciet gecodeerd via zijn relatiestel. Opvolgerstaten worden niet voorgesteld door hun volledige staatbeschrijvingen, maar door staat-objectknooppunten ( $o_{s'}$ ) die alleen de verschillen (toegevoegde en verwijderde predicaten) coderen ten opzichte van de wortel.
Boomstructuur: De encoding bevat expliciete atomen die transities tussen opvolgers voorstellen en diepteknooppunten om de zoekdiepte vast te leggen. Dit stelt de R-GNN in staat om informatie direct tussen opvolgerknooppunten uit te wisselen en embedding's voor alle staten in één enkele forward-pass te berekenen.
Efficiëntie: Deze aanpak vermijdt het opnieuw coderen van gedeelde staatbeschrijvingen, wat het geheugengebruik met meer dan een orde van grootte verlaagt (van >24GB naar <4GB VRAM in geteste scenario's) en het mogelijk maakt om alle transities simultaan te evalueren.

2. Abstracted IW(1) (AIW(1))

Om de schaalproblematiek van nieuwheidscontroles aan te pakken, stellen de auteurs een verzachte variant van IW(1) voor die staatatomen tijdens de nieuwheidstest abstraheert.

Relationele abstractie: In plaats van volledig geïnstancierde atomen te testen, vervangt AIW(1) iteratief alle maar één argument van een $n$ -air atoom door zijn meest specifieke type (bijvoorbeeld het vervangen van object $o$ door $type(o)$). Een atoom wordt als nieuw beschouwd als een van zijn geabstraheerde vormen nieuw is.
Verschuiving in complexiteit: Deze wijziging verplaatst de worst-case complexiteit van de nieuwheidszoekopdracht van lineair met het aantal grondatomen naar lineair met het aantal objecten.
Behoud van doel: Atomen die in het doel worden genoemd, worden niet geabstraheerd om te waarborgen dat doeldetectie nauwkeurig blijft.
Voordeel: Dit stelt de vooruitkijkende zoekopdracht in staat om te schalen naar instanties met duizenden objecten, terwijl het nog steeds zinvolle subdoelstructuren vastlegt en de kostenstructuur voor het lerende agent vereenvoudigt.

Trainingsprocedure

De R-GNN wordt getraind met diepe Q-learning met een geliftte variant van Hindsight Experience Replay (HER). De beloning wordt gedefinieerd als -1 per stap, waardoor de Q-waarde het negatief verwachte aantal transities naar het doel vertegenwoordigt. Een aanvullende rangschikkingsverliesfunctie wordt geïntroduceerd om de dieptevolgorde in de vooruitkijkende boom af te dwingen, zodat de agent leert om doodlopende wegen te vermijden die worden veroorzaakt door te ver vooruit te springen (bijvoorbeeld in het Spanner-domein).

Belangrijkste Bijdragen

Aggregated-Delta (AD)-encoding: Een nieuwe input-encoding voor R-GNN's die volledige vooruitkijkende bomen gezamenlijk voorstelt via staatverschillen. Dit maakt evaluatie in één doorgang van alle opvolgers mogelijk, wat de geheugenvoetafdruk en de trainingstijd drastisch verlaagt.
Abstracted IW(1) (AIW(1)): Een schaalbaar vooruitkijkend mechanisme dat de complexiteit van de nieuwheidszoekopdracht verlaagt van polynomiëel in atomen naar lineair in objecten door gebruik te maken van type-gebaseerde abstractie.
State-of-the-art prestaties: De combinatie van AIW en AD bereikt nieuwe prestatiebenchmark op het IPC 2023 Learning Track en andere domeinen, en overtreft zowel eerdere geleerde beleidslijnen als sterke klassieke planners zoals LAMA.

Experimentele Resultaten

De auteurs evalueerden hun aanpak op de IPC 2023-benchmark (900 instanties over 10 domeinen) en een uitgebreide set van domeinen (waaronder Grid en Logistics).

IPC 2023-prestaties: De AIW–AD-methode bereikte een totale dekking van 74% (668/900 instanties), wat significant beter presteert dan:
- IW–AD (59%): Dit demonstreert de waarde van abstractie.
- AIW–Ext (51%) en IW–Ext (51%): Dit demonstreert de waarde van de AD-encoding.
- LAMA (65%): De sterke klassieke baseline.
- Flat AA (58%): Flat-beleidslijnen zonder vooruitkijken.
Domeinspecifieke details:
- Satellite: AIW–AD loste 98% van de instanties op en loste het domein volledig op, terwijl andere geleerde methoden hier moeite mee hadden.
- Rovers & Childsnack: Er werden aanzienlijke verbeteringen waargenomen, hoewel moeilijke instanties in Childsnack uitdagend blijven vanwege enorme vertakkingsfactoren (miljoenen acties).
- Sokoban & Floortile: De prestaties bleven laag, wat consistent is met de bekende moeilijkheid van deze PSPACE-volledige of structureel complexe domeinen voor zoekvrije beleidslijnen.
Schaalbaarheid: De methode slaagde erin instanties met tot wel 488 blokken (Blocksworld) en meer dan 290.000 atomen (Rovers) te verwerken, waar eerdere IW-beleidsformuleringen faalden vanwege geheugenbeperkingen.
Expressiviteit: De aanpak slaagde erin te generaliseren naar domeinen die kenmerken vereisen die verder gaan dan het C2-logica-fragment (bijvoorbeeld Satellite, Rovers, Grid, Logistics), wat suggereert dat het vooruitkijkende mechanisme de expressieve last op de neurale architectuur vermindert.

Betekenis en Beweringen

Het artikel beweert dat efficiënte breedte-gebaseerde vooruitkijkende zoekopdrachten een kritieke katalysator zijn voor het schalen van algemene planning. De betekenis van het werk ligt op twee hoofdgebieden:

Schaalbaarheid: Door de complexiteit van de vooruitkijkende zoekopdracht te ontkoppelen van het aantal grondatomen (via AIW) en de complexiteit van de neurale encoding van het aantal transities (via AD), maakt deze aanpak het haalbaar om beleidslijnen te leren voor massale planningsinstanties die voorheen onbereikbaar waren voor geleerde methoden.
Verminderde eisen aan expressiviteit: Het vooruitkijkende mechanisme vereenvoudigt de probleemstructuur voor het lerende agent. Door "sprongen" te maken over sequenties van primitieve beslissingen, hoeft het beleid alleen maar hoogwaardige beslissingen te leren. Dit stelt modellen met beperkte expressiviteit (standaard R-GNN's) in staat om domeinen op te lossen die anders complexe kenmerken zouden vereisen die verder gaan dan het C2-logica-fragment.

De auteurs concluderen dat hun aanpak een nieuwe state-of-the-art in algemene planning vertegenwoordigt, en aantonen dat het combineren van principiële zoekopdrachten (vooruitkijken) met efficiënte neurale encoding het mogelijk maakt dat geleerde beleidslijnen effectief schalen terwijl ze hoge prestaties behouden over diverse en complexe domeinen.