Improving Execution Concurrency in Partial-Order Plans via Block-Substitution

Dit artikel introduceert een algoritme dat de gelijktijdige uitvoering in deeltijds-plannen verbetert door subplannen te vervangen en blokken te gebruiken om de concurrentie te maximaliseren, wat experimenteel is gevalideerd op IPC-benchmarks.

De kern

Samenvatting: Hoe je een slimme planningsrobot sneller en slimmer maakt

Stel je voor dat je een enorme hoeveelheid klusjes moet regelen voor een groot feest. Je hebt een lijst met taken: brood bakken, de tafel dekken, muziek kiezen en de gasten verwelkomen.

In de wereld van kunstmatige intelligentie (AI) noemen we zo'n lijst een plan. Vaak maken computers een heel strikt plan: "Eerst brood bakken, dan pas de tafel dekken, daarna muziek kiezen." Dit is een sequentieel plan. Het werkt, maar het is star. Als de oven het even niet doet, staat alles stil.

1. Het probleem: Te veel regels

De onderzoekers in dit papier werken met iets slimmers: een deels-volgorde plan (Partial-Order Plan).

• Vergelijking: In plaats van een strikte rij, krijg je een doos met losse taken. De computer zegt: "Je moet de tafel dekken voordat je de gasten verwelkomt, maar het maakt niet uit of je eerst het brood bakt of de muziek kiest."
• Het voordeel: Dit geeft flexibiliteit. Je kunt taken in willekeurige volgorde doen.
• Het nadeel: De computer probeert vaak alles tegelijk te doen (parallel), maar stuit op een muur. Soms zegt de computer: "Je kunt het brood bakken en de tafel dekken niet tegelijk doen, want je hebt maar één oven en één tafel." Zelfs als de taken los van elkaar staan, blokkeren ze elkaar door bronconflicten (zoals één oven).

2. De oplossing: Blokken en Vervanging

De auteurs, Sabah en Fazlul, hebben een nieuwe manier bedacht om deze blokkades op te heffen. Ze noemen hun methode CIBS (Concurrency Improvement via Block-Substitution).

Laten we het uitleggen met een verhuisscenario:

Stap 1: Groeperen (De "Blokken")

Stel je hebt een verhuisplan.

• Blok A: Alles wat te maken heeft met de woonkamer (meubels slepen, kast leegmaken).
• Blok B: Alles wat te maken heeft met de slaapkamer.

In het originele plan staat misschien: "Eerst Blok A, dan Blok B."
De onderzoekers gebruiken een truc (genaamd Block Deordering) om te zeggen: "Wacht, Blok A en Blok B hebben geen directe relatie. We kunnen ze in willekeurige volgorde doen!"

• Resultaat: Meer vrijheid. Maar... stel dat beide blokken dezelfde verhuiswagen nodig hebben. Dan kunnen ze nog steeds niet tegelijkertijd werken, ook al staat er geen volgorde op. Ze blokkeren elkaar nog steeds.

Stap 2: Vervangen (De "Magische Substitutie")

Hier komt de echte magie van dit papier.
De onderzoekers zeggen: "Als Blok A en Blok B niet tegelijk kunnen omdat ze dezelfde verhuiswagen nodig hebben, laten we dan Blok A vervangen door een ander plan."

• Het oude plan (Blok A): "Gebruik verhuiswagen 1 om de woonkamer leeg te halen."
• Het nieuwe plan (Vervanging): "Gebruik in plaats daarvan een tweede verhuiswagen (die toevallig ook in de buurt staat) om de woonkamer leeg te halen."

Door dit slimme vervangen (Block-Substitution) kunnen Blok A en Blok B nu tegelijkertijd werken, omdat ze elk hun eigen wagen hebben. De "muur" van de bronconflicten is geslecht.

3. De resultaten: Sneller en slimmer

De onderzoekers hebben hun methode getest op duizenden complexe problemen (zoals het regelen van liften in een flat, vrachtwagens in een magazijn of robots in een fabriek).

• De maatstaf: Ze gebruiken een score genaamd cflex. Dit is als een "snelheidsmeter" voor hoe goed taken tegelijk kunnen.
  • Een lage score = alles moet wachten op elkaar (traag).
  • Een hoge score = veel taken gebeuren tegelijk (snel).
• Het resultaat: Hun nieuwe methode (CIBS) zorgde ervoor dat veel plannen een veel hogere cflex-score kregen.
  • Vergelijking: Het is alsof je van een file op de snelweg (waar iedereen wacht) naar een meerbanenweg gaat waar iedereen tegelijk kan rijden.
  • Tijdswinst: Omdat meer taken tegelijk gebeuren, duurt het totale proces (de "verhuizing" of het "feest") aanzienlijk korter.

Waarom is dit belangrijk?

Vroeger moesten AI-systemen vaak kiezen tussen:

1. Een heel flexibel plan (maar langzaam uitvoeren).
2. Een heel snel plan (maar heel star en kwetsbaar voor fouten).

Deze paper laat zien dat je beide kunt hebben. Door slim te kijken welke onderdelen van een plan je kunt vervangen door alternatieve methoden (zoals een tweede lift of een tweede robot), kun je de taken versnellen zonder de flexibiliteit te verliezen.

Kortom:
De onderzoekers hebben een manier gevonden om AI-plannen te "ontwarren". Ze groeperen taken in blokken, kijken waar ze vastlopen door gebrek aan middelen (zoals één lift), en vervangen die blokken door slimme alternatieven. Het resultaat? Robots en software die niet alleen slimmer plannen, maar ook sneller werken door dingen echt tegelijk te doen.

Technische samenvatting

Probleemstelling

In het domein van AI-planning zijn Partiële-Order Plannen (POP) waardevol omdat ze flexibiliteit bieden door minder strikte volgorde-eisen aan acties te stellen dan sequentiële plannen. Hoewel bestaande technieken zoals plan deordering (het verwijderen van onnodige volgorde-eisen) en reordering de flexibiliteit van uitvoering in verschillende volgordes hebben verbeterd, is er beperkte aandacht besteed aan het maximaliseren van concurrente uitvoering (parallelle uitvoering).

Een POP specificeert welke acties onafhankelijk zijn, maar garandeert niet dat ze daadwerkelijk parallel kunnen worden uitgevoerd. Als twee ongerangschikte acties dezelfde bronnen gebruiken (bijvoorbeeld dezelfde lift of robot), kunnen ze niet gelijktijdig draaien. Bestaande methoden modelleren dit vaak als "interferentie" of voegen expliciete beperkingen toe, maar ze focussen niet actief op het elimineren van deze beperkingen door de structuur van het plan te wijzigen. Het doel van dit onderzoek is om de concurrentie van een plan te maximaliseren, wat leidt tot een kortere totale uitvoeringstijd, zonder de validiteit van het plan te schaden.

Methodologie

De auteurs introduceren een nieuwe aanpak die bestaat uit drie fasen, geïmplementeerd in een algoritme genaamd CIBS (Concurrency Improvement via Block-Substitution). De methode maakt gebruik van de Finite Domain Representation (FDR) en Domain Transition Graphs (DTG) om de afhankelijkheden tussen variabelen en bronnen nauwkeurig te modelleren.

1. Van Sequentieel naar Parallel (EOG):
   Het proces begint met een sequentieel plan dat wordt omgezet in een POP met behulp van Explanation-based Order Generalization (EOG). Dit elimineert onnodige volgorde-eisen. Vervolgens worden niet-concurrentie-beperkingen (non-concurrency constraints) geïdentificeerd. Twee acties kunnen niet parallel zijn als ze conflicterende precondities, effecten of resource-gebruik hebben op dezelfde state-variabelen.

2. Block Deordering (BD):
   Om de structuur te vereenvoudigen, worden coherente sets acties gegroepeerd in blokken. Dit resulteert in een Block Decomposed Partial-Order (BDPO) plan. Hierdoor worden veel volgorde-eisen tussen individuele acties verwijderd en vervangen door eisen tussen blokken. Dit creëert een hiërarchisch plan. Echter, zelfs als blokken ongerangschikt zijn, kunnen ze nog steeds niet-concurrent zijn als ze dezelfde bronnen gebruiken.

3. Block Substitution (SC) - De Kerninnovatie:
   Dit is de meest innovatieve stap. Als twee blokken een niet-concurrentie-beperking hebben (bijvoorbeeld omdat ze dezelfde lift gebruiken), probeert het algoritme één van de blokken te substitueren door een alternatief subplan.

   • Extensie: Soms is een blok niet direct substitueerbaar omdat het afhankelijk is van eerdere acties. Het algoritme gebruikt de EXTEND procedure om het blok uit te breiden met voorgangers of opvolgers, zodat het een zelfstandige taak wordt die kan worden herschreven.
   • Substitutie: Het algoritme genereert nieuwe subplannen voor de geëxtendeerde taak (met behulp van een externe planner zoals LAMA) die dezelfde precondities en effecten bereiken, maar geen conflicterende bronnen gebruiken.
   • Validatie: Als een nieuw blok wordt gevonden dat geen niet-concurrentie-beperking heeft met het andere blok, wordt de vervanging uitgevoerd. Dit proces herhaalt zich totdat geen verdere verbeteringen mogelijk zijn.

Belangrijkste Bijdragen

• Noodzakelijke en Voldoende Voorwaarden: De auteurs formuleren strikte voorwaarden voor niet-concurrentie tussen acties of subplannen in termen van state-variabelen (precondities, effecten en deleties). Dit gaat verder dan eerdere werk van Bäckström door rekening te houden met de specifieke resource-gebruik binnen FDR.
• Parallel Block Decomposed (PBD) Plan: Een nieuwe semantiek wordt geïntroduceerd voor plannen die zowel volgorde-eisen als expliciete niet-concurrentie-beperkingen bevatten, waardoor parallelle uitvoering van ongerangschikte blokken mogelijk is zolang er geen resource-conflict is.
• Block-Substitution Algoritme: Een procedure om blokken in een plan te vervangen door alternatieve subplannen die dezelfde taak uitvoeren maar met andere resources, waardoor resource-conflicten worden opgelost.
• De Metric cflex: De auteurs introduceren cflex (concurrency flexibility), gedefinieerd als de verhouding tussen het aantal concurrente actiepares en het totale aantal actiepares. Ze tonen empirisch aan dat een hogere cflex sterk correleert met een kortere minimale uitvoeringstijd.

Resultaten

De methode is getest op 3.303 plannen uit 33 verschillende domeinen van de International Planning Competitions (IPC).

• Verbetering in Concurrentie: De cflex-waarde nam significant toe door de drie fasen. De gemiddelde cflex steeg van 0,237 (na EOG) naar 0,241 (na Block Deordering) en verder naar 0,242 (na Substitutie). Hoewel het percentage klein lijkt, vertegenwoordigt dit een aanzienlijke toename in het aantal mogelijke parallelle uitvoeringen.
• Statistische Significantie: Met de Wilcoxon signed-rank test werd aangetoond dat de verbeteringen in veel domeinen (zoals elevator, logistics, depots, pipesworld) statistisch significant zijn.
• Vergelijking met MaxSAT: In vergelijking met geavanceerde MaxSAT-gebaseerde methoden (zoals MR en MRR) die proberen plannen te herschikken, presteert CIBS beter in termen van dekking (het percentage problemen waarvoor een oplossing wordt gevonden binnen de tijdslimiet) en snelheid. MaxSAT-methoden zijn vaak te rekenintensief voor grote plannen, terwijl CIBS snelle, iteratieve verbeteringen biedt.
• Schalbaarheid: De methode werkt het beste voor plannen van gemiddelde grootte (50-300 acties). Bij zeer grote plannen (>350 acties) neemt de verbetering af, voornamelijk door de computertijdslimiet en de beperkte beschikbaarheid van alternatieve resources in de testproblemen.

Betekenis en Conclusie

Dit onderzoek biedt een praktische en efficiënte manier om de uitvoeringstijd van AI-plannen te verkorten door parallelle uitvoering te maximaliseren. In plaats van alleen te focussen op het verwijderen van volgorde-eisen, lost de voorgestelde methode de onderliggende resource-conflicten op door het plan zelf te herschrijven (substitutie).

De belangrijkste implicatie is dat het mogelijk is om plannen te genereren die niet alleen flexibel zijn in volgorde, maar ook in tijd, wat essentieel is voor multi-agent systemen en robotten die tegelijkertijd moeten werken. De methode balanceert effectiviteit en rekentijd, waardoor ze geschikt is voor real-world toepassingen waar MaxSAT-oplossingen vaak te traag zijn. De auteurs wijzen er echter op dat toekomstig werk zich moet richten op het vinden van betere kandidaat-subplannen buiten de huidige blokkenstructuur om de concurrentie in nog grotere plannen te verbeteren.