Handling Infinite Domain Parameters in Planning Through Best-First Search with Delayed Partial Expansions

Each language version is independently generated for its own context, not a direct translation.

Het Grote Planningsprobleem: Hoe je een oneindige wereld in kaart brengt

Stel je voor dat je een super slimme robot wilt programmeren om een taak te voltooien, bijvoorbeeld: "Bak de perfecte cake" of "Vlieg van punt A naar punt B". In de wereld van kunstmatige intelligentie noemen we dit automatisch plannen.

Normaal gesproken werkt dit als een spelletje met een eindig aantal zetten. Je hebt een schaakbord met 64 vakjes en een beperkt aantal pionnen. De computer kan simpelweg alle mogelijke zetten uitrekenen en de beste kiezen.

Maar wat als je robot niet alleen moet kiezen welke zet hij doet, maar ook hoe hij het doet?
Stel je voor dat de robot een knop moet draaien om de temperatuur van de oven te regelen. Die knop kan op oneindig veel standen staan: 180 graden, 180,1 graden, 180,0001 graden... Het aantal mogelijke waarden is oneindig.

Dit is het probleem waar dit papier over gaat: hoe maak je een plan als er oneindig veel keuzemogelijkheden zijn?

Het oude probleem: De "Lijst van Verboden"

Tot nu toe hebben slimme computers dit opgelost door de oneindige keuzes te verstoppen in een lijst met regels. Ze zeggen: "Oké, de temperatuur moet tussen 150 en 200 graden liggen, en we gebruiken wiskunde om te kijken of dat lukt."
Het nadeel? De computer ziet de temperatuur niet als een echte keuze die hij moet maken, maar als een strakke beperking. Het is alsof je probeert een route te plannen door alleen te kijken welke wegen gesloten zijn, in plaats van te kiezen welke weg je neemt.

De nieuwe oplossing: De "Vertraagde Verkenner"

De auteurs van dit papier (Angel, Diego, Enrico en Eva) hebben een nieuwe manier bedacht. Ze behandelen die oneindige keuzes als echte beslispunten. Maar omdat je niet alle oneindige opties tegelijk kunt checken, gebruiken ze een slimme truc genaamd "Vertraagde Gedeeltelijke Uitbreiding".

Laten we dit uitleggen met een analogie:

De Analogie: De Ontdekkingsreiziger in een Mistig Bos
Stel je voor dat je een ontdekkingsreiziger bent in een enorm, mistig bos (de oneindige wereld). Je hebt een kaart (je plan) en je moet een pad vinden naar een schat (het doel).

Het oude probleem: Je probeert eerst alle mogelijke paden in het bos te tekenen voordat je een stap zet. Omdat het bos oneindig groot is, ben je nooit klaar en loop je vast.
De nieuwe aanpak (S-BFS): Je loopt een stukje, en dan stop je even. Je kijkt niet naar alle paden die vanaf hier vertrekken, maar je kiest er één willekeurig uit (of een paar) om te verkennen.
- Je loopt dat pad een stukje.
- Als het er goed uitziet, houd je het in je hoofd.
- Als het er slecht uitziet, gooi je het weg.
- De truc: Je komt terug naar je startpunt en probeert een ander pad. Je laat je startpunt niet "dicht" (gesloten), maar je komt er steeds weer terug om een nieuwe kans te proberen.

Dit is wat ze Sampling Best-First Search (S-BFS) noemen. In plaats van alles tegelijk te doen, "stippelen" ze stukjes van de toekomst uit.

De Twee Belangrijke Regels

Om te zorgen dat deze methode werkt en niet in een cirkel blijft lopen, gebruiken ze twee slimme regels:

De "Stoch" (Sampling): Je mag niet altijd dezelfde weg kiezen. Je moet willekeurig (of slim) nieuwe paden kiezen, zodat je uiteindelijk elk mogelijk pad in het bos hebt geprobeerd als je lang genoeg zoekt.
De "Straf" (Rectification): Als je een punt in het bos vaak bezoekt zonder een oplossing te vinden, moet je dat punt een beetje "straffen". Je maakt het minder aantrekkelijk om daar weer naartoe te gaan, zodat je juist nieuwe, onbekende gebieden gaat verkennen. Dit zorgt ervoor dat de robot niet vastloopt in één hoekje van het bos.

Wat zeggen de resultaten?

De auteurs hebben hun nieuwe robot (S-BFS) getest tegen andere bekende robots (zoals NextFLAP).

Resultaat: Hun robot kan veel meer problemen oplossen dan de anderen. Hij is beter in het vinden van een oplossing in die enorme, oneindige wereld.
De prijs: De oplossingen die hij vindt zijn soms niet de perfecte (kortste) oplossing, maar ze zijn wel bruikbaar. Het is alsof je een route vindt die 10 minuten duurt in plaats van 9, maar je komt wel aan, terwijl de andere robot helemaal vastliep.
De beste strategie: Het bleek dat het niet slim is om te proberen de "beste" weg te voorspellen met een heuristiek (een slimme gok). Het is beter om gewoon systematisch of willekeurig nieuwe paden te proberen.

Conclusie in het kort

Dit papier is een doorbraak omdat het een manier biedt om met oneindige keuzes om te gaan zonder vast te lopen. In plaats van te proberen alles in één keer te berekenen, laten ze de computer stap voor stap "proberen en leren".

Het is alsof je een enorm raadsel oplost door niet alle stukjes tegelijk te zoeken, maar door er één voor één te proberen, en telkens als je vastloopt, een ander stukje te pakken. Zo kun je zelfs de meest complexe, oneindige wereld plannen.

Each language version is independently generated for its own context, not a direct translation.

Probleemstelling

In het traditionele automatische plannen (automated planning) zijn de actie-instantiaties beperkt door een eindige set objecten. Hoewel PDDL2.1 numerieke variabelen (fluents) introduceerde voor hulpbronnen, werden continue numerieke argumenten in acties expliciet uitgesloten om de logische toestandsruimte eindig te houden. Recentere uitbreidingen, zoals control parameters (besturingsparameters), stellen planningsystemen in staat om continue numerieke waarden te kiezen om de effecten van acties te sturen (bijvoorbeeld de snelheid van een robot of de hoeveelheid brandstof).

Het huidige probleem is dat bestaande state-of-the-art planners (zoals POPCORN en NextFLAP) deze parameters vaak impliciet behandelen als extra beperkingen (constraints) die samen met temporele en numerieke restricties worden opgelost via Lineaire Programmering (LP) of Satisfiability Modulo Theories (SMT). Hierdoor worden ze niet gezien als echte beslispunten in de zoekruimte, maar als constraints die moeten worden voldaan. Dit beperkt de zoekstrategie en maakt het moeilijk om systematisch te zoeken in oneindige beslissingsruimtes.

Methodologie: Sampling Best-First Search (S-BFS)

De auteurs stellen een nieuwe aanpak voor die control parameters behandelt als expliciete decisiepunten binnen een systematische zoekstrategie. De kern van hun methode is het Sampling Best-First Search (S-BFS) algoritme.

1. Formele Definitie

Het probleem wordt gemodelleerd als een numeriek planningsprobleem met een set van numerieke control variabelen ( $U$ ) die onbeperkt kunnen evolueren binnen een interval $[l, u]$ . In plaats van een actie direct te evalueren met een parameter, worden fluents gedefinieerd die later in acties worden gebruikt. De beslissingsruimte bestaat uit paren van $(actie, waarde\_toewijzing)$ , wat oneindig is omdat de waarden continu zijn.

2. Kernconcepten van S-BFS

Om de oneindige uitbreidingsfactor van een knoop (node) in de zoekboom te omzeilen, introduceert het algoritme twee cruciale modificaties op de standaard Best-First Search (BFS):

Vertraging en Partiële Uitbreiding (Delayed Partial Expansions):
In plaats van alle mogelijke opvolgers van een staat te genereren (wat onmogelijk is bij oneindige ruimtes), wordt een knoop slechts partiëel uitgebreid. Een sampling-functie ( $\phi$ ) selecteert een subset van opvolgers door willekeurig te bemonsteren uit de beslissingsruimte.
Heruitbreiding en Rectificatie:
Een partiëel uitgebreide knoop wordt niet gesloten (closed), maar teruggevoegd naar de open lijst (open list) voor potentiële heruitbreiding in latere iteraties. Om te voorkomen dat deze knopen de zoekruimte domineren of in oneindige lussen terechtkomen, wordt hun Node Evaluation Criterion (NEC)-waarde aangepast door een rectificatie-functie ( $r_h$ $r_{h}$ ).
- De NEC wordt berekend als $f(s) = g(s) + r_h(n, s)$ , waarbij $n$ het aantal keren is dat de knoop al is heruitgebreid.
- De functie $r_h$ moet monotoon toenemen na een bepaald punt om te garanderen dat knopen uiteindelijk worden geselecteerd.

3. Varianten

Het artikel onderscheidt twee specifieke instanties van het algoritme:

S-G: Gebruikt alleen de heuristiek voor de evaluatie ( $f = r_h$ ).
S-A: Gebruikt een combinatie van kosten en heuristiek ( $f = g + r_h$ ), analoog aan A*.

Belangrijkste Bijdragen

Systematische Zoekstrategie voor Oneindige Ruimtes: Het is een van de eerste werken dat control parameters expliciet behandelt als beslissingsvariabelen in een systematische zoektocht, in plaats van ze als constraints te maskeren.
Probabilistische Volledigheid (Probabilistic Completeness): De auteurs bewijzen dat S-BFS probabilistisch compleet is onder specifieke voorwaarden. Dit betekent dat als er een oplossing bestaat, de kans om deze te vinden naar 1 convergeert naarmate het aantal stappen naar oneindig gaat.
- Voorwaarde: De sampling-functie moet een steun (support) hebben die de hele beslissingsruimte dekt (elk mogelijk opvolger heeft een niet-nul kans om te worden geselecteerd).
- Voorwaarde: De rectificatie-functie moet monotoon toenemen om oneindige blokkades te voorkomen.
Kwaliteitsgarantie voor S-A: Voor de S-A variant wordt bewezen dat de kosten van een gevonden oplossing begrensd zijn door de $f$ -waarde van de startknoop op het moment van oplossing, mits de heuristiek doelbewust is (goal-aware).
Nieuwe Zoekschema's: De introductie van het concept van "delayed partial expansion" gecombineerd met bemonstering voor continue planningsproblemen.

Resultaten en Experimentele Evaluatie

De auteurs hebben S-BFS getest op een reeks domeinen (o.a. CASHPOINT, PROCUREMENT, TERRARIA, en IPC-uitbreidingen) en vergeleken met:

NextFLAP: Een state-of-the-art planner die control parameters via SMT en discrete POP-zoektochten behandelt.
MCTS (Monte Carlo Tree Search): Met Progressive Widening voor oneindige ruimtes.

Kernbevindingen:

Dekking (Coverage): S-BFS (vooral de S-G variant) lost significant meer probleeminstanties op dan NextFLAP en MCTS. S-G loste alle 140 geteste problemen op, terwijl NextFLAP en MCTS aanzienlijk minder oplost.
Kwaliteit van Oplossing: NextFLAP produceert vaak kortere plannen (minder acties) voor de problemen die beide systemen oplossen. Dit wordt toegeschreven aan de optimalisatiemodules in NextFLAP en het ontbreken van strikte optimaliteitsgaranties in S-BFS (vanwege de probabilistische aard). Echter, de auteurs betogen dat het vermogen om veel meer problemen op te lossen (dekking) de iets lagere planlengte compenseert.
Invloed van Sampling: Systematische bemonstering (extremen en middelpunten) en uniforme bemonstering presteerden beter dan heuristisch geleide bemonstering. De heuristiek bleek vaak "plateaus" te hebben, waardoor geleide bemonstering niet effectiever was dan willekeurige bemonstering, maar wel meer rekentijd kostte.
Invloed van Rectificatie: Logaritmische groei van de rectificatie-functie ( $r_{log}$ ) bleek het meest effectief, omdat het de heuristiek laat domineren zonder te snel te straffen, wat leidt tot betere dekking.

Betekenis en Conclusie

Dit werk legt de fundamenten voor het behandelen van control parameters via systematische zoektochten in plaats van via constraint-oplossing. De belangrijkste implicatie is dat het mogelijk is om probabilistische volledigheid te bereiken in oneindige beslissingsruimtes door een slimme balans te vinden tussen exploratie (via bemonstering) en exploitatie (via heuristiek en rectificatie).

Hoewel de huidige implementatie nog geen optimale oplossingen garandeert en geen duuratieve acties (PDDL+) ondersteunt, biedt het een robuust alternatief voor bestaande methoden die vastlopen bij complexe continue variabelen. De auteurs plannen toekomstig werk om dit kader uit te breiden naar temporeel plannen en het ontwikkelen van heuristieken die specifiek zijn ontworpen voor oneindige ruimtes.