Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

Dit paper presenteert een praktische, polynoomtijd-compilatie die tijdsgebonden numerieke planning met durende acties volledig omzet naar het PDDL+-formaat, waarbij de semantiek behouden blijft en de planlengte slechts met een constante factor toeneemt.

De kern

De Kunst van het Vertalen: Hoe complexe tijdsplanning makkelijker wordt

Stel je voor dat je een super ingewikkelde dagplanning moet maken voor een groot feest. Je hebt niet alleen te maken met wat er moet gebeuren (eten koken, muziek zetten, gasten verwelkomen), maar ook met hoe lang het duurt en wanneer het precies moet gebeuren. Sommige taken overlappen elkaar (de kok snijdt groenten terwijl de muziek al aan staat), en sommige dingen moeten op het exacte moment gebeuren (de taart moet op 20:00 uur op tafel staan).

In de wereld van kunstmatige intelligentie (AI) noemen we dit temporale planning. Computers moeten deze plannen maken, maar ze spreken verschillende "talen" om dit te beschrijven.

Het Probleem: Twee Talen, Eén Doel

De auteurs van dit paper, Andrea, Enrico en Alessandro, kijken naar twee specifieke talen die AI-systemen gebruiken:

1. PDDL 2.1 (De "Duurzame" Taal): Dit is een taal die goed is om taken te beschrijven die tijd nodig hebben. Het zegt: "De taart bakken duurt 45 minuten en moet klaar zijn om 20:00."
2. PDDL+ (De "Proces" Taal): Dit is een krachtigere, maar complexere taal. In plaats van te zeggen "dit duurt 45 minuten", beschrijft het de wereld als een stroom van gebeurtenissen. Het zegt: "Er is een proces 'oven' dat de temperatuur elke seconde verhoogt, en er is een 'alarm' dat afgaat als de tijd voorbij is."

De uitdaging: Er was al lang bekend dat je de eerste taal (PDDL 2.1) in de tweede taal (PDDL+) kon vertalen. Maar niemand had ooit een werkend recept (een compilatie) gemaakt dat dit goed en betrouwbaar deed. Het was als weten dat je een Italiaans gerecht in een Frans gerecht kunt omzetten, maar niemand wist hoe je de ingrediënten precies moest vervangen zonder dat het proefde als rommel.

De Oplossing: Een Slimme Vertaler

De auteurs hebben nu eindelijk dat recept geschreven. Ze hebben een vertaler bedacht die een planning in PDDL 2.1 omzet naar PDDL+.

Hoe werkt deze vertaler? Ze gebruiken een slimme truc met sloten en sleutels (in het Engels "locks").

• Het Slot: Stel je voor dat elke taak een slot heeft. Als je een taak start (bijvoorbeeld "taart bakken"), doe je het slot dicht. Niemand mag dan iets anders doen dat met die taart te maken heeft (zoals de taart eruit halen) voordat de taart klaar is.
• De Snelheid: De vertaler zorgt ervoor dat de computer precies weet wanneer een taak begint en eindigt, zelfs als er duizenden kleine dingen tegelijk gebeuren.
• De "Oké"-knop: Ze hebben een speciale knop toegevoegd genaamd ok. Als er ergens in het plan een fout zit (bijvoorbeeld: iemand probeert de taart te eten terwijl hij nog in de oven zit), gaat deze knop op "nee". De computer ziet dan: "Oh, dit plan is fout, probeer een ander."

Waarom is dit zo'n groot ding?

1. Het werkt in de praktijk: Ze hebben dit getest op moeilijke problemen, zoals het plannen van waterpompen voor planten of het redden van mensen met een boot op zee.
2. Het is sneller: In hun experimenten bleek dat planners die de nieuwe taal (PDDL+) gebruikten, vaak beter presteerden dan de specialisten die direct op de oude taal (PDDL 2.1) werkten. Het is alsof je een oude, rommelige fiets vervangt door een strakke racefiets; het doel is hetzelfde, maar je komt veel sneller en efficiënter aan.
3. Het is wiskundig bewezen: Ze hebben niet alleen gezegd "het werkt", maar ook bewezen dat het altijd werkt en dat er geen informatie verloren gaat tijdens het vertalen.

De Conclusie

Kortom: De auteurs hebben een brug gebouwd tussen twee werelden. Ze hebben laten zien dat je complexe tijdsplanningen (waarbij dingen tegelijkertijd gebeuren en tijd een rol speelt) kunt vertalen naar een taal die beter wordt begrepen door moderne AI-systemen.

Het resultaat? Computers kunnen nu nog beter plannen maken voor de echte wereld, waar dingen niet altijd op het exacte seconde gebeuren, maar waar tijd en samenwerking cruciaal zijn. Het is alsof ze een nieuwe, krachtige motor hebben geïnstalleerd in de AI-motor van de toekomst.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version" in het Nederlands.

Probleemstelling

Automatisch plannen (automated planning) omvat het vinden van een reeks acties om een doel te bereiken vanuit een beginsituatie. Temporeel plannen breidt dit uit door acties te modelleren die een bepaalde tijdsduur hebben (duurzame acties), waarbij condities gelden aan het begin, het einde en tijdens de uitvoering van de actie. Deze problemen worden vaak gemodelleerd in PDDL 2.1.

Hoewel bekend was dat PDDL 2.1 theoretisch kan worden vertaald naar PDDL+ (een taal die systemen modelleert via processen, gebeurtenissen en instantane acties in plaats van duurzame acties), ontbrak er tot nu toe een praktische, volledige en formele compilatie in de literatuur. Bestaande oplossingen voor PDDL 2.1 zijn vaak beperkt tot specifieke zoekalgoritmen of satisfiability-benaderingen, maar missen de flexibiliteit om de expressiviteit van PDDL+ (zoals numerieke variabelen en complexe tijdsafhankelijkheden) te benutten.

Methodologie

De auteurs presenteren een compilatie die een temporeel planningsprobleem (PDDL 2.1 niveau 3) omzet in een equivalent PDDL+ probleem. De kern van de methode is het emuleren van duurzame acties door een combinatie van instantane acties, processen en gebeurtenissen.

1. Vertaalmechanisme

Elke duurzame actie $a$ in het originele probleem wordt vertaald naar een triplet in PDDL+:

• Voor vaste duur: Een start-actie, een proces dat de tijd bijhoudt, en een gebeurtenis die de actie beëindigt op het exacte tijdstip.
• Voor variabele duur: Een start-actie, een proces, en een eind-actie die door de planner zelf wordt gekozen binnen de toegestane tijdslimieten ($l_a \leq d \leq u_a$).

2. Handhaving van Semantiek (De "Lock"-Machinerie)

Een cruciale uitdaging is het garanderen van de niet-overlappende semantiek (non-self-overlapping) en het voorkomen van interfererende acties op hetzelfde tijdstip. De auteurs introduceren een innovatief "lock"-systeem:

• Lock-predicaten: Voor elke numerieke of booleaanse variabele worden drie extra predicaten toegevoegd: rlf (read-lock), alf (assignment-lock) en ilf (increment-lock).
• Voorwaarden en Effecten: Bij het lezen van een variabele wordt de lees-lock geblokkeerd; bij toewijzing of increment wordt de respectievelijke schrijf-lock geblokkeerd.
• Interferentiepreventie: Als een actie een variabele leest terwijl een andere actie deze in hetzelfde tijdsinterval wijzigt, wordt de actie geblokkeerd omdat de lock niet is vrijgegeven.
• Tijdsreset: Een speciaal proces (pE) verhoogt continu een teller gc. Een gebeurtenis (eE) reset alle locks naar waar zodra gc positief is. Dit creëert een "superdense" tijdstructuur waarin acties binnen één tijdstip kunnen plaatsvinden, maar waarbij locks automatisch worden vrijgegeven zodra de tijd echt vordert. Dit voorkomt oneindige cycli (Zeno-gedrag) in discrete tijd.

3. Validatie en Correctheid

De compilatie introduceert een ok-predicaat. Als een conditie wordt geschonden (bijvoorbeeld een invariant tijdens een actie wordt geschonden of een actie te lang duurt), wordt ok op false gezet, waardoor het plan ongeldig wordt.

Belangrijkste Bijdragen

1. Eerste Volledige Formele Compilatie: Dit is het eerste werk dat een volledige, uitgewerkte formele account biedt voor het compileren van PDDL 2.1 (met numerieke variabelen en duurzame acties) naar PDDL+.
2. Polynoom Complexiteit: De compilatie is polynoom in grootte ten opzichte van het inputprobleem en verdubbelt de planlengte hoogstens met een constante factor.
3. Soundness en Compleetheid: De auteurs bewijzen wiskundig dat:
   • Soundness: Elk geldig PDDL+-plan correspondeert met een geldig PDDL 2.1-plan.
   • Compleetheid: Voor elk geldig PDDL 2.1-plan bestaat er een voldoende kleine tijdsdiscretisatie ($\delta$) zodat een corresponderend geldig PDDL+-plan bestaat.
4. Uitbreidbaarheid: De methode ondersteunt ook functies die vaak slecht worden ondersteund door temporele planners, zoals vertraagde effecten (delayed effects) en getimede initieel literalen.

Experimentele Resultaten

De auteurs hebben de compilatie getest op een reeks temporeel-numerieke domeinen (zoals MatchCellar, MAJSP, T-Sailing en T-Plant-Watering) en vergeleken met state-of-the-art temporele planners (zoals ARIES, OPTIC, TAMER, TFLAP).

• Performantie: De PDDL+ planner ENHSP (met een WA* zoekstrategie) presteerde verrassend goed en vaak superieur aan gespecialiseerde temporele planners, vooral op complexe problemen met numerieke variabelen.
• Complementariteit: Hoewel pure temporele planners sneller waren op puur temporele domeinen, bleek de compilatie zeer effectief voor domeinen waar numerieke en temporele redenering sterk verweven zijn.
• Coverage: ENHSP-WA behaalde de hoogste dekking (aantal opgeloste instanties) over de geteste domeinen.

Significantie

Dit onderzoek is significant omdat het de theoretische gap tussen PDDL 2.1 en PDDL+ overbrugt met een praktische implementatie. Het toont aan dat het compileren van temporele problemen naar een taal met processen en gebeurtenissen geen theoretische curiositeit is, maar een praktisch krachtige strategie kan zijn voor het oplossen van moeilijke temporeel-numerieke planningsproblemen.

De studie suggereert dat de kernmoeilijkheden in temporeel plannen misschien beter kunnen worden aangepakt door gebruik te maken van de expressiviteit van PDDL+ in plaats van het ontwikkelen van gespecialiseerde zoekalgoritmen voor PDDL 2.1. Toekomstig werk richt zich op het uitbreiden naar PDDL 2.1 niveau 4 (continue verandering) en het onderzoeken van compilaties met continue tijdsemantiek.