Improving Plan Execution Flexibility using Block-Substitution

Dit artikel introduceert een methode die de uitvoeringsflexibiliteit van AI-plannen verbetert door subplannen te vervangen door externe acties binnen een hiërarchisch Block Decomposed Partial-Order (BDPO) raamwerk, wat resulteert in aanzienlijk flexibeler plannen zonder in te leveren op dekking of uitvoeringstijd.

De kern

🚀 De Kunst van het Plannen: Van Strikte Lijst naar Flexibele Dans

Stel je voor dat je een reis moet plannen. Een strikte planning (zoals een traditioneel computerplan) is als een treinrit: je moet op station A om 08:00 zijn, dan direct naar station B, en pas daarna naar C. Als er een vertraging is op station A, of als station B gesloten is, is je hele reis in de war. Je kunt niet makkelijk van plan veranderen.

In de kunstmatige intelligentie (AI) willen we echter flexibele plannen. Een flexibel plan is meer als een danspartij. Je weet dat je eerst moet dansen met iemand, en later met iemand anders, maar wie je eerst ontmoet, maakt niet uit, zolang de volgorde maar logisch is. Dit noemen we een deels-geordend plan (Partial-Order Plan). Hoe minder strakke regels je hebt, hoe flexibeler je bent om op onverwachte situaties te reageren.

🧱 Het Probleem: De Bouwstenen zijn te Stijf

De auteurs van dit artikel, Sabah Binte Noor en Fazlul Hasan Siddiqui, kijken naar hoe we deze plannen nog flexibeler kunnen maken.

Stel je een plan voor als een reusachtige legpuzzel. Traditionele methoden proberen de puzzelstukken (acties) losser te maken door ze niet meer in een vaste volgorde te leggen. Ze noemen dit deordering (ontkoppelen).

• Voorbeeld: In een lift-systeem moet je misschien eerst een passagier ophalen en dan naar een andere verdieping gaan. Traditionele methoden zeggen: "Oké, deze twee stappen kunnen in willekeurige volgorde."

Maar de auteurs zeggen: "Dat is nog niet genoeg! Wat als we een hele groep stappen (een blok) kunnen vervangen door een ander, slimmer blok?"

🔄 De Oplossing: De "Block-Substitution" (Blok-vervanging)

De kern van hun nieuwe methode heet FIBS (Flexibility Improvement via Block-Substitution).

Stel je voor dat je een recept voor een taart hebt.

1. Het oude recept: Je moet eerst deeg maken, dan eieren kloppen, dan bakken.
2. De oude methode (Deordering): Ze zeggen: "Je kunt het deeg en de eieren in willekeurige volgorde doen." Dat helpt al een beetje.
3. De nieuwe methode (FIBS): Ze kijken naar het hele blok "eieren kloppen" en zeggen: "Wacht even, in plaats van dat we eieren kloppen, kunnen we niet gewoon een kant-en-klare mix gebruiken die sneller klaar is en minder rommel maakt?"

Ze vervangen een groepje acties (een blok) in het plan door een ander blok dat dezelfde taak uitvoert, maar op een slimme manier.

• Voorbeeld uit de tekst: Stel je hebt een lift die twee mensen moet vervoeren. De lift moet eerst naar de 3e verdieping, dan naar de 2e, dan naar de 1e.
  • Oude plan: Lift gaat naar beneden, pikt persoon 1 op, gaat omhoog, zet af, gaat weer naar beneden... (veel stappen).
  • Nieuwe plan: Er is een tweede lift beschikbaar! In plaats van dat de eerste lift alles doet, laten we de tweede lift persoon 2 ophalen. Dit vervangt een groot blok stappen van de eerste lift door een korter blok van de tweede lift.
  • Resultaat: De twee liftbewegingen kunnen nu tegengelijk gebeuren (ze hoeven niet meer op elkaar te wachten). Het plan wordt veel flexibeler en sneller.

🛠️ Hoe werkt het in de praktijk?

De auteurs hebben een algoritme ontwikkeld dat als volgt werkt:

1. Verpakken in blokken: Ze nemen een bestaand plan en groeperen logische stappen samen in "blokken" (zoals dozen in een verhuiswagen).
2. Zoeken naar vervangers: Voor elk blok vragen ze aan een slimme planner: "Kun je dit blok doen op een andere manier, met minder regels of andere hulpmiddelen?"
3. Vervangen en Controleren: Als ze een beter blok vinden, vervangen ze het oude. Ze controleren streng of het nieuwe plan nog steeds werkt (geen "rampen" veroorzaakt, zoals een lift die wegrijdt terwijl er nog iemand in staat).
4. Opruimen: Soms zijn er stappen die helemaal niet nodig zijn na de vervanging. Die worden verwijderd, net als het weggooien van overbodig inpakmateriaal.

📊 Wat zeggen de resultaten?

Ze hebben hun methode getest op honderden problemen uit internationale wedstrijden voor AI-planning (zoals het "Elevator" domein of "Logistiek").

• Flexibiliteit: Hun methode (FIBS) maakt plannen aanzienlijk flexibeler dan de oude methoden. Het plan heeft minder strakke regels, waardoor een robot of software beter kan omgaan met onverwachte gebeurtenissen.
• Snelheid: Andere methoden die proberen plannen te optimaliseren (zoals MaxSAT), zijn vaak extreem traag. Ze doen er uren over. FIBS is veel sneller (gemiddeld minder dan 2 minuten) en werkt bijna altijd.
• Kostenefficiëntie: Door redundantie (overbodige stappen) te verwijderen, worden de plannen vaak ook goedkoper (minder brandstof, minder tijd).

💡 De Grootste Les

Deze paper leert ons dat we niet hoeven te blijven hangen in de eerste oplossing die we vinden. Door te kijken naar groepen acties en die te vervangen door slimmere alternatieven, kunnen we plannen creëren die niet alleen werken, maar ook aanpasbaar zijn.

Het is alsof je van een stijve robot die precies elke beweging moet volgen, verandert in een acrobaat die weet dat er meerdere wegen zijn naar hetzelfde doel. En dat maakt het verschil tussen een plan dat faalt bij de eerste storing, en een plan dat gewoon doorgaat.

Technische samenvatting

1. Probleemstelling

In het domein van AI-planning is het cruciaal dat agenten flexibel kunnen reageren op onverwachte veranderingen in een dynamische omgeving. Partiële-orde-plannen (POP) bieden deze flexibiliteit door minder strikte volgordebeperkingen tussen acties te hanteren dan sequentiële plannen, waardoor acties parallel kunnen worden uitgevoerd of in verschillende lineaire volgordes kunnen worden uitgevoerd.

Echter, bestaande methoden om de flexibiliteit van plannen te maximaliseren, zoals plan deordering (het verwijderen van onnodige volgordebeperkingen) en plan reordering (het willekeurig aanpassen van volgorde), hebben beperkingen:

• Traditionele deordering-technieken (zoals EOG en Block Deordering) verwijderen alleen bestaande beperkingen maar veranderen de acties zelf niet.
• Bestaande reordering-technieken (zoals MaxSAT-gebaseerde methoden) kunnen redundantie verwijderen of parameters opnieuw toewijzen, maar ze staan doorgaans niet toe om een actie te vervangen door een actie met een andere naam of een compleet ander subplan.
• Het vinden van het minst beperkte POP is een NP-hard probleem, wat efficiënte benaderingen vereist.

Het artikel introduceert een nieuw probleem: hoe kan de uitvoeringsflexibiliteit van een plan worden verbeterd door substitutie van subplannen (blokken) met andere acties of subplannen die buiten het oorspronkelijke plan liggen, terwijl de geldigheid en kosten van het plan behouden blijven?

2. Methodologie

De auteurs stellen een nieuwe methode voor genaamd FIBS (Flexibility Improvement via Block-Substitution). Deze methode bouwt voort op het concept van Block Decomposed Partial-Order (BDPO) plannen.

Kernconcepten:

• BDPO-plannen: Een hiërarchische structuur waarbij coherente acties worden gegroepeerd in "blokken". Dit maakt het mogelijk om blokken als onafhankelijke eenheden te behandelen.
• Block-Substitutie: In plaats van alleen bestaande volgordebeperkingen te verwijderen, vervangt FIBS een bestaand blok (subplan) in het BDPO-plan door een nieuw blok. Dit nieuwe blok kan zijn afgeleid van het oorspronkelijke plan of gegenereerd door een externe planner.
• Subprobleem-vorming: Om een vervangend blok te genereren, wordt voor elk kandidaat-blok een subprobleem geformuleerd. De starttoestand van dit subprobleem wordt afgeleid door de opeenvolgende blokken vóór het doelblok te simuleren, en het doel wordt bepaald door de feiten die het doelblok aan zijn opvolgers levert.
• Bedreigingsoplossing (Threat Resolution): Bij het vervangen van een blok moeten nieuwe causale koppelingen worden gelegd en potentiële bedreigingen (threats) worden opgelost. De auteurs definiëren strategieën (promotie, demotie, of interne substitutie) om cycli te voorkomen en de geldigheid van het plan te garanderen.

Het FIBS-algoritme:

Het algoritme werkt in vier fasen:

1. EOG (Explanation-based Order Generalization): Converteert een sequentieel plan naar een initiële POP.
2. SD1 (Substitution-Deorder 1): Probeert primitieve blokken (enkele acties) te vervangen om volgordebeperkingen te verwijderen.
3. Block Deordering (BD): Groepeert acties in compound-blokken om extra volgordebeperkingen te verwijderen.
4. SD2 (Substitution-Deorder 2): Probeert nu zowel primitieve als compound-blokken te vervangen om de flexibiliteit verder te maximaliseren.

Het algoritme gebruikt een Relative Flexibility Optimization (RFO) criterium: een substitutie wordt alleen geaccepteerd als de flexibiliteit van het plan stijgt en de kosten niet toenemen. Daarnaast wordt er een Plan Reduction stap toegevoegd (via Backward of Greedy Justification) om overbodige acties te verwijderen.

3. Belangrijkste Bijdragen

1. Nieuwe Strategie (Block-Substitutie): Het introduceren van het concept om subplannen te vervangen door alternatieve subplannen (binnen of buiten het plan) om flexibiliteit te verhogen, in plaats van alleen bestaande beperkingen te verwijderen.
2. BDPO-gebaseerde Vervanging: Het gebruik van BDPO-plannen als basis voor substitutie, wat het zoeken naar geschikte vervangers efficiënter maakt dan het blind zoeken in de hele zoekruimte.
3. Correctheid en Volledigheid: De auteurs bewijzen de correctheid van hun substitutie-algoritme (Theorema 1) en tonen aan dat het algoritme niet volledig is (Theorema 2), maar dat dit een acceptabele afweging is voor de efficiëntie.
4. Integratie met Bestaande Methoden: De methode wordt geëvalueerd in combinatie met state-of-the-art MaxSAT-reordering technieken (MR en MRR), waarbij wordt aangetoond dat FIBS deze methoden kan verbeteren.
5. Efficiënte Reductie: Het integreren van technieken voor het verwijderen van redundante acties (Backward/Greedy Justification) in het BDPO-framework.

4. Experimentele Resultaten

De methode is getest op 3826 plannen uit 32 domeinen van de International Planning Competitions (IPC), gegenereerd door de LAMA-planner.

• Flexibiliteitsverbetering: FIBS toonde een aanzienlijke verbetering in de uitvoeringsflexibiliteit (gemeten als de verhouding van ongeordende actieparen) vergeleken met alleen EOG of Block Deordering. De gemiddelde flexibiliteit steeg van 0,20 (EOG) naar 0,325 (na FIBS).
• Vergelijking met MaxSAT:
  • FIBS presteerde beter dan MaxSAT-based reordering (MR en MRR) in 25 van de 32 domeinen.
  • Schaalbaarheid: MaxSAT-methoden kampen met hoge rekentijden en lage dekking voor grote plannen (MRR had slechts 54% dekking). FIBS behaalde 100% dekking met een gemiddelde rekentijd van slechts 106 seconden.
  • Synergie: Het toepassen van FIBS na MaxSAT-oplossingen (bijv. MR+FIBS) leverde vaak nog betere flexibiliteit op dan MaxSAT alleen, wat aantoont dat de methoden complementair zijn.
• Kostenreductie: Door het verwijderen van redundante acties (via FIBS_GJ) werd een gemiddelde kostenreductie van 5,91% bereikt, vergelijkbaar met of beter dan de Minimal Plan Reduction (MPR) methode in veel domeinen.
• Anytime-eigenschap: FIBS toont een "anytime"-gedrag, waarbij de flexibiliteit continu verbetert naarmate de rekentijd toeneemt, in tegenstelling tot MaxSAT-methoden die vaak vastlopen bij de tijdslimiet.

5. Betekenis en Conclusie

Dit onderzoek biedt een significante doorbraak in het optimaliseren van AI-plannen voor dynamische omgevingen. De belangrijkste implicaties zijn:

• Flexibiliteit vs. Kosten: Het bewijst dat het mogelijk is om de uitvoeringsflexibiliteit van plannen drastisch te verhogen zonder de kosten te verhogen, en zelfs kosten te verlagen door redundante acties te verwijderen.
• Efficiëntie: De block-substitutie-methode is computatie-efficiënter dan globale optimalisatie via MaxSAT, waardoor het toepasbaar is op grotere en complexere planningsproblemen.
• Toekomstperspectief: De auteurs suggereren dat het concept van blokken als vervangbare eenheden breder kan worden toegepast, bijvoorbeeld in assumptie-gebaseerde planning en kwaliteitsoptimalisatie.

Samenvattend biedt FIBS een robuust, schaalbaar en effectief kader voor het creëren van robuustere plannen die beter bestand zijn tegen onzekerheid en veranderingen in de wereld, wat essentieel is voor de toepassing van autonome agenten in de praktijk.