Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version

Questo articolo presenta una compilazione pratica e polinomiale che traduce la pianificazione temporale con azioni durative nel linguaggio PDDL+, mantenendo la semantica completa e dimostrando efficacia sperimentale su problemi temporali numerici complessi.

L'essenziale

Immagina di essere il regista di un film d'azione molto complesso. Hai una lista di scene (le azioni) che devono essere girate. Alcune scene durano pochi secondi, altre richiedono minuti o ore. Alcune richiedono che due attori parlino contemporaneamente, altre che un attore tenga la posa mentre un'altra scena si svolge sullo sfondo.

Il problema è che il tuo assistente regista (il computer) parla due lingue diverse:

1. La lingua del "Tempo Reale" (PDDL 2.1): Qui le azioni hanno una durata. "L'attore corre per 10 secondi". È molto preciso, ma i computer faticano a gestire queste durate continue.
2. La lingua delle "Macchine Automatiche" (PDDL+): Qui non ci sono azioni che durano. Ci sono solo istanti: "Premi il pulsante", "La macchina si muove", "Se succede X, allora fai Y". È più facile da calcolare, ma sembra meno naturale per descrivere azioni che durano.

Il problema: Fino a oggi, non c'era un modo pratico e affidabile per tradurre il "Tempo Reale" nella lingua delle "Macchine Automatiche" senza perdere informazioni o creare errori. I pianificatori esistenti faticavano con problemi complessi che univano tempo e numeri (come calcolare il carburante mentre si guida).

La soluzione di questo paper: Gli autori (Andrea, Enrico e Alessandro) hanno creato un traduttore universale (una compilazione). Hanno inventato un metodo per trasformare qualsiasi piano temporale complesso in un piano per "Macchine Automatiche", mantenendo tutto perfetto.

Ecco come funziona, usando una metafora culinaria:

🍳 La Metafora della Cucina

Immagina di dover cucinare una cena complessa.

• Azione temporale: "Cuocere la pasta per 10 minuti".
• Azione istantanea: "Buttare la pasta nell'acqua".

Il tuo nuovo traduttore trasforma l'azione "Cuocere per 10 minuti" in tre piccoli passaggi magici:

1. Il Campanello d'Allarme (L'Evento di Inizio): Suona il campanello che dice "Inizia a cuocere!". Metti un timer (una variabile numerica) a zero e accendi un lucchetto verde che dice "La pasta è nel pentolone".
2. L'Acqua che Bolle (Il Processo): Mentre il timer è attivo, c'è un "processo" che fa scorrere l'acqua. Il timer aumenta di 1 ogni secondo. È come se avessi un rubinetto che versa acqua nel timer.
3. Il Campanello di Fine (L'Evento o Azione di Fine):
   • Se la pasta deve cuocere esattamente 10 minuti: Un evento automatico scatta quando il timer arriva a 10 e dice "Spegni il fuoco".
   • Se la pasta può cuocere tra 8 e 12 minuti: Un'azione ti permette di dire "Spegni il fuoco" quando vuoi, purché il timer sia tra 8 e 12.

🔒 Il Segreto: I Lucchetti (Locks)

Il problema più grande quando si traducono queste azioni è evitare il caos. Immagina due persone che provano a scrivere sullo stesso foglio di carta nello stesso istante: il risultato sarebbe illeggibile.

Gli autori hanno inventato un sistema di lucchetti magici:

• Prima di toccare un ingrediente (una variabile), devi avere il lucchetto verde.
• Se lo stai leggendo, il lucchetto diventa rosso.
• Se lo stai modificando, un altro lucchetto diventa rosso.
• La magia: Dopo ogni istante di tempo, un "giardiniere" (un evento speciale) passa e riapre tutti i lucchetti, ma solo se è passato un po' di tempo reale. Questo impedisce a due azioni di "scontrarsi" nello stesso istante, garantendo che tutto avvenga in ordine perfetto.

🏆 Cosa hanno scoperto?

Hanno testato questo traduttore su problemi molto difficili (come gestire l'acqua per le piante o salvare persone con una barca in mare).

• Risultato sorprendente: I computer che parlano la lingua delle "Macchine Automatiche" (PDDL+), una volta ricevuta la traduzione, sono diventati più bravi di quelli specializzati nel "Tempo Reale" su problemi complessi che mescolano numeri e tempo.
• È come se avessi dato a un ingegnere meccanico (il pianificatore PDDL+) lo schema di un orologio svizzero (il problema temporale) e lui, grazie al traduttore, lo ha riparato più velocemente dell'orologiaio stesso.

In sintesi

Questo paper ci dice che non serve inventare nuovi motori complessi per gestire il tempo. Basta prendere i problemi temporali, tradurli in una lingua che i computer attuali capiscono meglio (usando processi, eventi e lucchetti), e lasciarli lavorare. È un ponte teorico solido che si è rivelato anche praticamente utilissimo per risolvere problemi del mondo reale.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "Compiling Temporal Numeric Planning into Discrete PDDL+: Extended Version" in italiano.

Titolo e Contesto

Il paper presenta un metodo di compilazione pratico e formale che trasforma problemi di pianificazione temporale con azioni durative (specificati nel linguaggio PDDL 2.1, livello 3) in problemi equivalenti nel linguaggio PDDL+. L'obiettivo è sfruttare la ricchezza espressiva di PDDL+ (che modella sistemi ibridi tramite processi, eventi e azioni istantanee) per risolvere problemi di pianificazione temporale complessi, in particolare quelli che coinvolgono variabili numeriche.

Il Problema

La pianificazione temporale richiede di trovare una sequenza di azioni che durano per un certo intervallo di tempo, soddisfacendo precondizioni all'inizio, alla fine e durante l'esecuzione, nonché invarianti globali. Sebbene sia noto teoricamente che PDDL+ possa esprimere azioni durative, non esisteva in letteratura una compilazione pratica, completa e formalmente provata che garantisse la correttezza semantica, specialmente per problemi con variabili numeriche e vincoli di sovrapposizione.

Metodologia e Compilazione

Gli autori propongono una compilazione che mappa ogni azione durativa del PDDL 2.1 in una combinazione di azioni istantanee, processi ed eventi in PDDL+. La compilazione assume la semantica "non auto-sovrapposta" (non-self-overlapping), ovvero due istanze della stessa azione non possono sovrapporsi nel tempo.

Struttura della Compilazione

Per ogni azione durativa $a$ nel problema originale, la compilazione introduce:

1. Variabili di stato ausiliarie:

   • ra: Predicato booleano che indica se l'azione $a$ è in esecuzione.
   • ca: Flusso numerico che misura il tempo trascorso dall'inizio dell'azione.
   • oc: Contatore numerico per tracciare le azioni aperte ma non terminate.
   • gc: Flusso numerico per gestire la sincronizzazione temporale e i lock.
   • ok: Predicato booleano globale che, se falso, invalida il piano (usato per rilevare violazioni di invarianti).
   • Lock (rlf, alf, ilf): Predicati booleani per ogni fluente per prevenire interferenze (lettura/scrittura simultanea).

2. Trasformazione delle Azioni:

   • Azioni Istantanee: Vengono arricchite con precondizioni di lock e effetti di lock per garantire l'assenza di interferenze.
   • Azioni Durative a Durata Fissa ($A_{fix}$):
     • Iniziano con un'azione istantanea (a⊢) che imposta ra, azzera ca e incrementa oc.
     • Terminano tramite un evento (e⊣) che si attiva esattamente quando ca raggiunge la durata fissa.
   • Azioni Durative a Durata Variabile ($A_{var}$):
     • Iniziano come sopra.
     • Terminano tramite un'azione istantanea (a⊣) che può essere eseguita in qualsiasi momento entro i vincoli di durata, purché ra sia vero e i vincoli temporali siano soddisfatti.

3. Meccanismo di Lock e Non-Interferenza:
   Il contributo chiave è un meccanismo sofisticato per garantire che due azioni non interferiscano sullo stesso fluente nello stesso istante temporale (semantica "superdensa" di PDDL+):

   • Ogni lettura di un fluente imposta un lock di lettura (rlf).
   • Ogni scrittura/assegnazione imposta un lock di scrittura (alf).
   • Ogni incremento imposta un lock di incremento (ilf).
   • Le precondizioni delle azioni richiedono che i lock appropriati siano attivi.
   • Un processo incrementa continuamente gc (tempo trascorso).
   • Un evento (eE) resetta tutti i lock a true e azzera gc ogni volta che il tempo avanza (quando gc > 0). Questo simula il passaggio del tempo, permettendo alle azioni di interferire solo in istanti temporali distinti, non contemporaneamente.

4. Gestione delle Invarianti:
   Se un'azione durativa è in esecuzione (ra è vero) ma la sua condizione globale (γa) non è soddisfatta, un evento specifico imposta ok a false, rendendo il piano invalido (poiché ok non può essere ripristinato).

Contributi Chiave

1. Formalizzazione Completa: È la prima descrizione formale rigorosa della compilazione da PDDL 2.1 a PDDL+, fornendo prove di correttezza.
2. Correttezza e Completezza:
   • Soundness (Correttezza): Se esiste un piano valido in PDDL+, il piano corrispondente nel dominio originale è valido.
   • Completeness (Completezza): Per ogni piano temporale valido, esiste un $\delta$ (quantum temporale) sufficientemente piccolo tale che esiste un piano valido in PDDL+.
3. Complessità: La compilazione è polinomiale rispetto alla dimensione del problema e la lunghezza del piano risultante aumenta al massimo di un fattore costante.
4. Supporto Numerico: La compilazione gestisce nativamente variabili numeriche, effetti ritardati e letterali temporali iniziali.

Risultati Sperimentali

Gli autori hanno valutato la compilazione su diversi domini numerici temporali (MatchCellar, MaJSP, T-Sailing, T-Plant-Watering) confrontando il pianificatore PDDL+ ENHSP (con due motori: LG e WA*) contro i migliori pianificatori temporali nativi (ARIES, NextFLAP, TFLAP, OPTIC, TAMER, Patty).

• Performance: Il pianificatore ENHSP-WA (basato su compilazione PDDL+) ha ottenuto la copertura più alta (numero di istanze risolte), superando spesso i pianificatori temporali nativi, specialmente nei domini numerici complessi.
• Complementarità: Mentre i pianificatori temporali nativi (come ARIES) performano meglio in domini puramente temporali, l'approccio basato su compilazione PDDL+ eccelle nei domini che richiedono un ragionamento intrecciato tra aspetti temporali e numerici.
• Scalabilità: L'approccio dimostra di essere pratico e competitivo per problemi difficili.

Significato e Conclusioni

Questo lavoro dimostra che la compilazione in PDDL+ non è solo un esercizio teorico, ma una strategia pratica ed efficace per risolvere problemi di pianificazione temporale complessi. Sfruttando la potenza dei pianificatori PDDL+ esistenti, si possono affrontare problemi che i pianificatori temporali dedicati faticano a gestire, in particolare quando sono coinvolti vincoli numerici intricati.

Il paper suggerisce che le difficoltà fondamentali nella pianificazione temporale potrebbero risiedere più nella gestione delle interazioni numeriche e temporali che nella logica temporale stessa. Come lavoro futuro, gli autori intendono estendere la compilazione al livello 4 di PDDL 2.1 (cambiamento continuo) e studiare semantici temporali continue per PDDL+.