Improving Plan Execution Flexibility using Block-Substitution

Questo studio propone un metodo per migliorare la flessibilità di esecuzione dei piani di pianificazione AI sostituendo i sottopiani con azioni esterne, integrando la deordinazione a blocchi e strategie di riduzione per ottenere piani gerarchici più adattabili senza compromettere la copertura o i tempi di esecuzione.

L'essenziale

🚀 Il Viaggio del Pianificatore: Come rendere i piani più flessibili

Immagina di dover organizzare un grande viaggio in famiglia. Hai una lista di cose da fare: fare le valigie, andare in aeroporto, prendere il volo, atterrare e andare in hotel.
Un piano rigido (come quelli che fanno i vecchi computer) ti direbbe: "Prima le valigie, poi l'aeroporto, poi il volo, poi l'hotel. Non puoi cambiare nulla. Se ti fermi a comprare un gelato, il piano si rompe."

I pianificatori moderni (l'Intelligenza Artificiale) sono più intelligenti: creano un piano parziale. Ti dicono: "Devi fare le valigie prima di andare in aeroporto, e devi prendere il volo prima di andare in hotel. Ma puoi fare le valigie e prendere il caffè prima di partire in qualsiasi ordine tu voglia." Questo è un piano flessibile: ti lascia spazio per imprevisti.

Tuttavia, a volte questi piani sono ancora troppo rigidi. Il paper di Sabah Binte Noor e Fazlul Hasan Siddiqui propone un nuovo modo per rendere questi piani ancora più elastici, come un elastico che si allunga senza spezzarsi.

---

🧩 L'Idea Principale: "Sostituisci il Blocco"

Il cuore della loro scoperta è un concetto chiamato Sostituzione di Blocchi (Block-Substitution).

Immagina il tuo piano di viaggio non come una lista di azioni singole, ma come una serie di scatole (o blocchi) contenenti azioni correlate.

• Blocco A: "Preparazione" (fare valigie, chiudere la porta).
• Blocco B: "Viaggio" (andare in aeroporto, imbarcarsi).

Spesso, il piano dice: "Il Blocco A deve finire prima che inizi il Blocco B". Questo crea un vincolo rigido.

Cosa fanno gli autori?
Invece di cercare di togliere solo i vincoli (come fanno i metodi vecchi), dicono: "E se invece di usare il Blocco B originale, usassimo un altro Blocco B, fatto da un'altra persona o con un altro metodo, che fa la stessa cosa ma in modo più libero?"

🌰 L'Esempio dell'Ascensore (Il "Caso Pratico")

Immagina un palazzo con un solo ascensore.

• Piano originale: L'ascensore deve scendere al piano 3, prendere una persona, salire al piano 2, scendere al piano 1, prendere un'altra persona, e salire di nuovo. È un viaggio lungo e pieno di fermate obbligate.
• La magia della Sostituzione: Il sistema dice: "Aspetta! C'è un secondo ascensore libero al piano 1. Invece di usare il primo ascensore per tutto il tragitto (Blocco B), usiamo il secondo ascensore (Nuovo Blocco B) per prendere la seconda persona."

Risultato? Il primo ascensore non deve più scendere al piano 1. I due compiti (portare la prima persona e la seconda) possono ora essere fatti in parallelo o in ordine diverso. Il piano diventa molto più flessibile e veloce.

---

🛠️ Come funziona la loro "Scatola Magica" (FIBS)

Gli autori hanno creato un algoritmo chiamato FIBS (Flexibility Improvement via Block-Substitution). Ecco come lavora, passo dopo passo, con un'analogia culinaria:

1. La Ricetta Base (EOG): Prendi una ricetta rigida (un piano sequenziale) e la trasformi in una ricetta con istruzioni parziali (puoi impastare mentre bolle l'acqua).
2. Raggruppare gli Ingredienti (Block Deordering): Metti insieme gli ingredienti che vanno usati insieme in "scatole" (blocchi).
3. Il Sostituto Perfetto (Sostituzione): Per ogni scatola, il sistema chiede: "Esiste un altro modo per fare questa parte della ricetta? Forse usando un ingrediente diverso o un metodo diverso che non richiede di aspettare l'altro?"
   • Se trova un "sostituto" che fa la stessa cosa ma permette di saltare un vincolo, sostituisce la scatola.
4. Pulizia (Riduzione): Alla fine, controlla se ci sono ingredienti ridondanti (es. hai messo il sale due volte) e li toglie per risparmiare tempo e fatica.

🏆 Perché è meglio dei metodi precedenti?

Prima di questo lavoro, esistevano due modi principali per migliorare i piani:

1. Togliere i vincoli (Deordering): Come cercare di togliere i tasselli da un puzzle senza romperlo. Funziona, ma ha dei limiti.
2. Riordinare tutto (Reordering con MaxSAT): Come provare a rimettere insieme il puzzle in mille modi diversi usando un super-calcolatore. È potente, ma lento e spesso si blocca se il puzzle è troppo grande.

Il vantaggio di FIBS:

• È veloce: Non prova milioni di combinazioni a caso. Cerca solo "sostituti intelligenti" per le parti specifiche del piano.
• È flessibile: Riesce a trovare soluzioni che gli altri metodi non vedono, specialmente quando ci sono risorse extra disponibili (come il secondo ascensore nell'esempio).
• Funziona su piani grandi: Mentre i metodi vecchi si bloccano su piani complessi, FIBS continua a lavorare bene.

📊 I Risultati: Cosa hanno scoperto?

Hanno testato il loro metodo su centinaia di problemi reali (dai robot che puliscono il pavimento, agli ascensori, fino alla logistica dei camion).

• Flessibilità: I piani creati da FIBS sono stati molto più "elastici" (fino al 60% in più di flessibilità rispetto ai metodi base).
• Velocità: FIBS ha trovato queste soluzioni molto più velocemente dei metodi basati su MaxSAT (che richiedevano ore, mentre FIBS ne richiedeva minuti o secondi).
• Risparmio: Spesso, sostituendo i blocchi, hanno anche ridotto il numero di azioni necessarie, risparmiando "carburante" o tempo.

💡 In Conclusione

Immagina di avere un piano di viaggio scritto su un foglio di carta rigida. Se piove, il piano si rompe.
I metodi vecchi provano a piegare il foglio.
FIBS, invece, ti dice: "Non preoccuparti del foglio. Se piove, prendi un ombrello (sostituisci il blocco 'camminata' con 'auto') o cambia destinazione (sostituisci il blocco 'spiaggia' con 'museo')."

Il risultato è un piano che non solo resiste agli imprevisti, ma si adatta così bene da diventare più efficiente e veloce dell'originale. È un passo avanti verso un'intelligenza artificiale che non solo "pianifica", ma improvvisa con intelligenza.

Sommario tecnico

1. Il Problema

Nell'ambito della pianificazione automatica (AI Planning), i piani parzialmente ordinati (POP) sono fondamentali per la loro flessibilità di esecuzione. A differenza dei piani sequenziali, che impongono un ordine totale tra le azioni, i POP permettono l'esecuzione parallela e offrono multiple linearizzazioni valide. Questa flessibilità è cruciale per adattarsi a cambiamenti imprevisti, fluttuazioni delle risorse o variazioni nella durata delle azioni.

Tuttavia, le strategie tradizionali per massimizzare la flessibilità, come il deordinamento (rimozione di ordinamenti non necessari) e il riordinamento (modifica arbitraria degli ordinamenti), presentano limiti:

• Operano principalmente sulla struttura esistente del piano senza introdurre nuove azioni.
• Non permettono di sostituire sottopiani con azioni esterne o diverse per nome.
• Spesso non riescono a eliminare azioni ridondanti che, se rimosse, potrebbero creare vincoli di ordinamento aggiuntivi o, al contrario, aumentare la flessibilità complessiva.

L'obiettivo del paper è superare questi limiti migliorando la flessibilità di esecuzione di un piano sostituendo i suoi sottopiani (blocchi) con alternative più efficienti o flessibili, anche provenienti dall'esterno del piano originale.

2. Metodologia

Gli autori propongono un nuovo algoritmo chiamato FIBS (Flexibility Improvement via Block-Substitution). La metodologia si basa su una struttura gerarchica chiamata BDPO (Block Decomposed Partial-Order) plan.

Concetti Chiave:

• BDPO Plan: Un piano POP in cui le azioni coerenti sono raggruppate in "blocchi". I blocchi possono essere nidificati e, se non ordinati tra loro, possono essere eseguiti in qualsiasi sequenza.
• Block-Substitution (Sostituzione di Blocchi): Il cuore dell'algoritmo. Consiste nel sostituire un blocco esistente in un BDPO plan con un nuovo blocco (sottopiano), generato dinamicamente risolvendo un sottoproblema di pianificazione.
  • Il nuovo blocco deve soddisfare le precondizioni del blocco originale e fornire gli stessi effetti necessari ai successori.
  • Il processo deve garantire che non vengano introdotti conflitti (minacce) che invalidino il piano o che creino cicli negli ordinamenti.
• Flessibilità (Flex): Misurata come il rapporto tra le coppie di azioni non ordinate e il numero totale di coppie di azioni. Un valore più alto indica un piano più flessibile.

L'Algoritmo FIBS:

L'algoritmo opera in quattro fasi iterative:

1. EOG (Explanation-based Order Generalization): Trasforma un piano sequenziale iniziale in un POP.
2. SD1 (Substitution-Deorder 1): Applica la sostituzione di blocchi sui blocchi primitivi (singole azioni) per eliminare ordinamenti.
3. Block Deordering (BD): Raggruppa le azioni coerenti in blocchi composti per rimuovere ulteriori ordinamenti.
4. SD2 (Substitution-Deorder 2): Applica nuovamente la sostituzione di blocchi, questa volta su entrambi i blocchi primitivi e composti, per massimizzare la flessibilità.

In ogni fase, l'algoritmo genera sottoproblemi di pianificazione per trovare candidati di sostituzione che migliorino la flessibilità mantenendo o riducendo il costo del piano (criterio RFO - Relative Flexibility Optimization).

Riduzione dei Piani:

Oltre alla sostituzione, FIBS integra strategie di giustificazione (Backward e Greedy Justification) per identificare ed eliminare azioni o blocchi ridondanti. Questo riduce il costo totale del piano, anche se a volte può introdurre vincoli di ordinamento, ma il beneficio netto in termini di efficienza è positivo.

3. Contributi Chiave

1. Nuova Strategia di Sostituzione: A differenza dei metodi precedenti (come MaxSAT o EOG) che modificano solo gli ordinamenti o i parametri delle azioni esistenti, FIBS permette di sostituire interi sottopiani con azioni completamente diverse (anche con nomi diversi), purché semanticamente equivalenti per il sottoproblema.
2. Integrazione Gerarchica: L'uso dei blocchi BDPO permette di trattare i sottopiani come unità atomiche per la sostituzione, rendendo la ricerca di alternative più efficiente rispetto alla ricerca cieca su tutte le possibili combinazioni di azioni.
3. Gestione delle Minacce: Gli autori definiscono formalmente come gestire le minacce introdotte dalla sostituzione (promozione, demozione o sostituzione interna di blocchi conflittuali) per garantire la validità del piano risultante.
4. Algoritmo "Anytime": FIBS è progettato per migliorare progressivamente il piano man mano che il tempo di calcolo aumenta, offrendo soluzioni valide in ogni momento.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su 3.826 piani provenienti da 32 domini delle International Planning Competitions (IPC), utilizzando il planner LAMA come generatore di piani iniziali.

• Miglioramento della Flessibilità:
  • FIBS ha mostrato un miglioramento significativo della flessibilità rispetto alle tecniche di deordinamento (EOG) e riordinamento basati su MaxSAT (MR e MRR).
  • La flessibilità media è passata da 0.20 (dopo EOG) a 0.32 (dopo FIBS completo).
  • FIBS ha superato MR e MRR in 25 e 19 domini rispettivamente, con una copertura del 100% dei piani (mentre MaxSAT fallisce spesso su piani grandi a causa della complessità computazionale).
• Efficienza Computazionale:
  • FIBS è molto più veloce dei metodi basati su MaxSAT. Il tempo medio di esecuzione è di 106 secondi contro i 1039 secondi di MRR e 242 secondi di MR.
  • FIBS scala meglio con la dimensione del piano, mantenendo tempi di esecuzione lineari, mentre MaxSAT diventa rapidamente intrattabile per piani con più di 200-300 azioni.
• Riduzione dei Costi:
  • L'integrazione di strategie di giustificazione (Backward e Greedy) ha permesso di ridurre il costo medio dei piani del 5.33% - 5.91%, competendo favorevolmente con l'approccio MPR (Minimal Plan Reduction) basato su MaxSAT.
• Combinazione con MaxSAT:
  • Applicare FIBS sui piani già ottimizzati da MaxSAT (MR o MRR) ha ulteriormente migliorato la flessibilità, dimostrando che le due tecniche sono complementari.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo avanti significativo nella pianificazione automatica per la sua capacità di modificare la struttura semantica del piano (sostituendo azioni) piuttosto che limitarsi a riorganizzarla.

• Robustezza Operativa: Permette agli agenti di adattarsi meglio a scenari dinamici offrendo più percorsi di esecuzione validi.
• Scalabilità: Offre un compromesso efficace tra qualità della soluzione (flessibilità) e tempo di calcolo, rendendolo adatto a problemi reali di grandi dimensioni dove i metodi esatti (MaxSAT) falliscono.
• Flessibilità vs. Costo: Dimostra che è possibile migliorare la flessibilità senza sacrificare il costo del piano, e anzi, spesso riducendolo attraverso l'eliminazione di ridondanze.

In conclusione, FIBS introduce un paradigma di ottimizzazione dei piani che combina la potenza della decomposizione gerarchica (blocchi) con la capacità di generare nuovi sottopiani, superando i limiti delle tecniche di riordinamento puramente strutturali.