GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models

GenePlan is een nieuw raamwerk dat grote taalmodellen combineert met evolutionaire algoritmen om interpreteerbare, domein-specifieke PDDL-planners te genereren die presteren op het niveau van de state-of-the-art en aanzienlijk beter zijn dan andere LLM-baselines.

De kern

Stel je voor dat je een super slimme, maar soms wat chaotische assistent hebt die je kunt vragen om een route te plannen voor een vrachtwagen, een robot die blokken moet stapelen, of een agent die kranten moet bezorgen. Je geeft de assistent de regels (in een speciale taal genaamd PDDL) en vraagt: "Hoe kom ik van A naar B met de minste stops?"

Het probleem is dat deze assistent (een Groot Taalmodel of LLM, zoals de AI die dit artikel schreef) vaak wel een goed idee heeft, maar de oplossing niet altijd perfect is. Soms maakt hij een omweg, soms vergeet hij een regel, en soms is de route gewoon niet de kortste.

GenePlan is een nieuwe methode ontwikkeld door onderzoekers van J.P. Morgan om dit probleem op te lossen. Ze noemen het een "evolutionaire planner". Laten we het uitleggen met een paar creatieve vergelijkingen.

1. De "Kookwedstrijd" in plaats van één chef-kok

Stel je voor dat je een perfecte recept wilt voor een taart die in precies 10 minuten klaar is.

• De oude manier (Chain-of-Thought): Je vraagt één beroemde chef-kok (de AI) om het recept te bedenken. Hij denkt na, schrijft het op, en hopelijk lukt het. Maar als hij een foutje maakt, heb je een mislukte taart.
• De GenePlan-methode: Je start een kookwedstrijd. Je nodigt 10 chefs uit (een "populatie"). Ze proberen allemaal een recept te bedenken.
  • De chefs die de taart te langzaam bakken of hem verbranden, krijgen een lage score.
  • De chefs die het snelst en lekkerst bakken, krijgen een hoge score.
  • Nu komt het slimme deel: Je neemt de beste chefs en laat hen hun geheimen mixen (zoals een kruising in de natuur). Ze nemen de beste ingrediënten van elkaars recepten en maken een nieuw, nog beter recept.
  • Soms laten ze een beetje "geluk" toe: ze voegen een heel klein, raar nieuw ingrediënt toe (een mutatie) om te zien of dat misschien nog beter werkt.

Dit proces herhalen ze keer op keer. Na een paar rondes (generaties) hebben ze niet zomaar één goed recept, maar een ultieme, geoptimaliseerde taart die perfect is.

2. De AI als "Evolutionair Bioloog"

In de wereld van GenePlan is de AI niet de persoon die het plan direct maakt, maar de bioloog die de evolutie stuurt.

• De AI kijkt naar de recepten (de Python-code) van de vorige ronde.
• Hij zegt: "Jullie waren goed, maar jullie maakten te veel omwegen. Laten we de beste stukjes van jullie code samenvoegen en een nieuwe versie maken."
• De AI schrijft dan de nieuwe code, test hem, en kijkt of het beter werkt.

3. Waarom is dit zo slim?

De onderzoekers hebben dit getest op 8 verschillende soorten puzzels (zoals het verplaatsen van auto's met een veerboot, of het stapelen van zware dozen).

• Snelheid: Zodra GenePlan de "ultieme planner" heeft gevonden, kan die planner nieuwe problemen oplossen in 0,49 seconden. Dat is sneller dan bliksem!
• Kwaliteit: De oplossingen die GenePlan vond, waren net zo goed als die van de allerbeste, traditionele planningssystemen (die vaak duizenden keren meer rekenkracht nodig hebben).
• Kosten: Het kostte slechts ongeveer $1,82 om een planner voor een hele domein te "evoluëren". Dat is heel goedkoop voor zo'n slimme oplossing.

4. Wat levert het op?

Het mooie aan GenePlan is dat het geen "zwarte doos" is. De AI schrijft leesbare Python-code. Je kunt dus echt zien hoe de planner denkt.

• Bijvoorbeeld: "Neem eerst de zwaarste doos, leg die onderop, en stapel daarna de lichtere erboven."
• Dit is heel anders dan een AI die gewoon een antwoord geeft zonder te kunnen uitleggen waarom. Hier zien we de logica van de oplossing.

Samenvattend

GenePlan is als een slimme kweektunnel voor ideeën. In plaats van te hopen dat een AI in één keer het perfecte antwoord vindt, laat je de AI duizenden kleine versies van een oplossing "evolueren". De slechte vallen af, de goede worden gemixt en verbeterd, tot er één overblijft die zo efficiënt is dat hij elke puzzel in een flits oplost.

Het is een manier om de creativiteit van AI te combineren met de discipline van evolutie, zodat we niet alleen een oplossing krijgen, maar de beste oplossing.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "GenePlan: Evolving Better Generalized PDDL Plans using Large Language Models" in het Nederlands.

Titel: GenePlan: Het evolueren van betere gegeneraliseerde PDDL-plannen met behulp van Large Language Models

Auteurs: Andrew Murray, Danial Dervovic, Alberto Pozanco, Michael Cashmore (J.P. Morgan AI Research)

---

1. Het Probleem

Het paper adresseert de uitdaging van gegeneraliseerd plannen (Generalized Planning) in klassieke AI-planningsproblemen, beschreven in de Planning Domain Definition Language (PDDL).

• Achtergrond: Traditionele planners lossen één specifiek probleeminstance op. Gegaliseerd plannen vereist echter het vinden van één strategie (een "planner" of algoritme) die werkt voor alle mogelijke problematische instances binnen een bepaald domein.
• Huidige beperkingen:
  • LLM's: Hoewel Large Language Models (LLM's) goed zijn in code genereren, presteren ze vaak slecht in sequentiële besluitvorming en plannen wanneer ze direct worden gebruikt (bijv. via Chain-of-Thought prompting). Ze genereren vaak "bevredigende" (satisficing) oplossingen zonder optimalisatie voor planlengte of kwaliteit.
  • Bestaande methoden: Aanpakken die LLM's gebruiken om heuristieken of zoekstrategieën te genereren, missen vaak een mechanisme om de kwaliteit van het gegenereerde plan systematisch te verbeteren en te optimaliseren.
• Doel: Het ontwikkelen van een framework dat interpreteerbare, Python-gebaseerde gegeneraliseerde planners genereert die de planlengte (aantal acties) minimaliseren over een reeks trainingsproblemen, met prestaties die vergelijkbaar zijn met de state-of-the-art zoekplanners.

2. Methodologie: GenePlan Framework

GenePlan (GENeralized Evolutionary Planner) behandelt gegeneraliseerd plannen als een optimalisatieprobleem. Het combineert LLM's met evolutionaire algoritmen om een populatie van kandidaat-planners te evolueren.

Kerncomponenten:

1. Optimalisatieformulering:

   • Het doel is het vinden van een functie $\Phi$ (geschreven in Python) die een valid plan $\pi$ genereert voor elke probleeminstance $\Pi$ in een set $\Pi_G$, waarbij de gemiddelde kosten (planlengte) worden geminimaliseerd:
     $$\arg \min_{\Phi} \frac{1}{|\Pi_{train}|} \sum_{\Pi \in \Pi_{train}} |\Phi(\Pi)|$$
   • De zoekruimte bestaat uit geldige Python-code.

2. Evolutionaire Cyclus:

   • Populatie: Een verzameling van kandidaat-Python-methoden (planners).
   • Fitness Functie: De gemiddelde planlengte over een trainingsset. Als een planner een probleem niet kan oplossen, krijgt het een hoge "failure score".
   • Selectie: Planners worden geselecteerd als ouders voor de volgende generatie op basis van hun fitness. GenePlan gebruikt een temperatuurgebaseerde selectie (Boltzmann-verdeling) met een afnemende temperatuur (hyperbolisch verval). Dit stimuleert exploratie in vroege generaties en exploitatie in latere generaties.
   • Crossover & Mutatie (via LLM): In plaats van traditionele bit-flips of string-crossover, gebruikt GenePlan de LLM om nieuwe kandidaten te genereren. De LLM ontvangt een prompt met voorbeelden van bestaande planners (ouders), hun code, en feedback over hun prestaties (succes/foutmeldingen). De instructies vragen de LLM om:
     • Crossover: De beste componenten van de ouderplanners te combineren.
     • Mutatie: Strategische wijzigingen aan te brengen (bijv. efficiëntieverbeteringen, eliminatie van redundante acties).
   • Validatie & AST-Parser: De gegenereerde Python-code wordt eerst gecontroleerd via een Abstract Syntax Tree (AST) parser om te zorgen dat deze alleen veilige en toegestane operaties bevat. Vervolgens wordt de code gecompileerd en uitgevoerd om de fitness te berekenen.
   • Vervanging: Na elke generatie worden de slechtst presterende planners verwijderd en vervangen door de beste nieuwe kandidaten (elitair vervangingsstrategie).

3. Input/Output:

   • Input: PDDL-domein, trainingsproblemen, en een prompt-template.
   • Output: Een geoptimaliseerde Python-functie (get_plan) die nieuwe problem instances in dat domein snel en efficiënt oplost.

3. Belangrijkste Bijdragen

• Nieuw Framework: GenePlan is het eerste framework dat LLM-assisted evolutionaire algoritmen toepast op gegeneraliseerd PDDL-plannen om kwaliteit (planlengte) te optimaliseren, in plaats van alleen oplossingen te genereren.
• Interpreteerbaarheid: De gegenereerde oplossingen zijn leesbare Python-code, in tegenstelling tot "black-box" neurale netwerken of complexe zoekbomen.
• Kostenefficiëntie: Het framework is ontworpen om goedkoop te zijn in gebruik (API-kosten) en genereert planners die extreem snel zijn in inferentie.
• Ablatie Studies: Het paper biedt inzicht in welke componenten essentieel zijn voor succes (bijv. de noodzaak van volledige PDDL-context versus samenvattingen in natuurlijke taal).

4. Resultaten

Het framework werd geëvalueerd op 8 domeinen (6 bestaande benchmarks + 2 nieuwe: Trading en Research).

• Prestaties (SAT Score):
  • GenePlan (met GPT-4o) behaalde een gemiddelde SAT-score van 0,91.
  • Dit is zeer vergelijkbaar met de state-of-the-art planner Fast Downward (met een 30-minuten tijdslimiet), die een score van 0,93 behaalde.
  • GenePlan presteerde significant beter dan andere LLM-baselines zoals Chain-of-Thought prompting (CoT), die slechts een gemiddelde score van 0,64 behaalde.
• Snelheid:
  • De gegenereerde planners lossen nieuwe instances op in gemiddeld 0,49 seconden per taak, wat aanzienlijk sneller is dan traditionele zoekalgoritmen.
  • De generatietijd voor een planner is een eenmalige kostenpost (gemiddeld ~10-15 minuten per domein in de experimenten).
• Kosten:
  • De gemiddelde kosten voor het genereren van een planner bedroegen slechts $1,82 per domein (met GPT-4o).
  • Met GPT-4o mini waren de kosten lager ($0,10), maar met een lagere plankwaliteit.
• Statistische Significantie:
  • Statistische tests (Friedman en Nemenyi) bevestigden dat GenePlan significant beter presteert dan CoT-baselines en vergelijkbaar is met geavanceerde zoekplanners.
• Beperkingen:
  • In domeinen zonder eenvoudige strategieën (zoals Sokoban, waar acties irreversibel kunnen zijn), faalde GenePlan om een goede planner te vinden en probeerde het een zoekalgoritme te bouwen, wat minder efficiënt was dan Fast Downward. Dit onderstreept dat de aanpak het beste werkt voor domeinen met herhaalbare patronen.

5. Betekenis en Toekomstperspectief

• Paradigmaverschuiving: Het paper toont aan dat LLM's niet alleen als "chatbots" voor plannen kunnen dienen, maar als krachtige evolutionaire optimalisatoren die bruikbare, hoogwaardige algoritmen kunnen synthetiseren.
• Toepasbaarheid: De methode is ideaal voor domeinen met terugkerende planningsbehoeften waar de initiële generatiekosten worden gecompenseerd door de hoge snelheid en lage kosten van de gegenereerde planner bij herhaald gebruik.
• Toekomstig Werk:
  • Ontwikkeling van criteria voor early stopping om de generatiekosten te verlagen.
  • Uitbreiden van de optimalisatiemetrics naast planlengte (bijv. robuustheid, tijdscomplexiteit).
  • Het gebruik van LLM's als een orchestratielaag die dynamisch kiest tussen een gegenereerde gegeneraliseerde planner en een traditionele zoekplanner, afhankelijk van de complexiteit van het specifieke probleem.

Conclusie: GenePlan demonstreert dat de combinatie van evolutionaire algoritmen en LLM's een krachtige route is om interpreteerbare, kosteneffectieve en hoogwaardige gegeneraliseerde planners te creëren die concurreren met de beste traditionele zoekmethoden.