HyperTensioN: Ottimizzare la Pianificazione Gerarchica con Astuzia

Ciao a tutti! Oggi voglio parlarvi di un argomento che mi appassiona da matti: come insegnare alle macchine a pianificare in modo intelligente, quasi come faremmo noi umani, ma… molto più velocemente! Nello specifico, ci tufferemo nel mondo affascinante della Pianificazione Gerarchica a Reti di Task (HTN – Hierarchical Task Network) e di come un approccio chiamato HyperTensioN stia cambiando le carte in tavola.

Cos’è la Pianificazione HTN e Perché è Complicata?

Immaginate di dover preparare una torta. Non pensate subito a “prendi la farina, aggiungi le uova…”, vero? Probabilmente pensate a macro-fasi: “prepara l’impasto”, “inforna”, “decora”. Ecco, la pianificazione HTN funziona un po’ così. Forniamo al sistema una sorta di “ricetta” (il cosiddetto domain knowledge) che spiega come scomporre compiti complessi (task di alto livello, come “prepara l’impasto”) in sotto-compiti più semplici (come “mescola ingredienti secchi”, “aggiungi liquidi”), fino ad arrivare ad azioni elementari (task primitivi) che la macchina sa eseguire direttamente (gli operatori).

Sembra figo, no? Lo è! Ma c’è un “ma”. Spesso, queste ricette contengono delle ricorsioni. È come se la ricetta per “prepara l’impasto” includesse, in certe condizioni, di nuovo il task “prepara l’impasto”. Se non gestita bene, questa cosa può mandare il pianificatore in un loop infinito, un po’ come un disco rotto. Qui entra in gioco la necessità di algoritmi furbi o di “ricette” scritte apposta per un certo pianificatore.

HyperTensioN: L’Architettura a Tre Stadi

Ed è qui che vi presento il mio “gioiellino”: HyperTensioN. È il pianificatore che ha vinto la competizione internazionale IPC 2020 nella categoria total-order HTN. Cosa lo rende speciale? Beh, una delle sue forze è l’architettura, pensata come un compilatore a tre stadi:

• Front-end: Si occupa di “leggere” e capire la descrizione del problema di pianificazione, scritta in linguaggi come PDDL o HDDL.
• Middle-end: Qui avviene la magia! Questo stadio applica una serie di ottimizzazioni e trasformazioni alla descrizione del problema. Possiamo concatenare diverse ottimizzazioni per massimizzare l’efficienza.
• Back-end: Genera il codice (nel nostro caso, Ruby) che il pianificatore vero e proprio eseguirà per trovare la soluzione.

Questa separazione è fantastica perché ci permette di aggiungere facilmente supporto per nuovi linguaggi (nel front-end) o nuove ottimizzazioni (nel middle-end) senza dover stravolgere tutto il resto. È come avere dei mattoncini LEGO: aggiungi o cambi un pezzo senza disfare tutta la costruzione.

HyperTensioN si basa su un algoritmo chiamato Total-order Forward Decomposition (TFD). In pratica, affronta i task uno alla volta, in sequenza, scomponendoli passo dopo passo. È un approccio “lifted”, il che significa che lavora direttamente con le descrizioni astratte dei task e degli operatori, senza dover generare prima tutte le possibili istanze concrete (un processo chiamato grounding che può essere pesantissimo).

Le Ottimizzazioni Chiave: Typredicate, Pullup e Dejavu

Ma veniamo al cuore pulsante, le ottimizzazioni del middle-end che fanno davvero la differenza. Ne abbiamo sviluppate tre principali per l’IPC 2020:

1. Typredicate: Specializzare per Semplificare

Avete presente quando in una ricetta c’è scritto “aggiungi frutta”? Typredicate è come se specificasse meglio: “aggiungi mele” o “aggiungi pere”. Tecnicamente, analizza i tipi di oggetti usati nei predicati (le condizioni o le proprietà del mondo, tipo `(at ?oggetto ?luogo)`). Se un predicato viene usato sia per le auto (`vehicle`) che per i pacchi (`package`), ma un operatore specifico (come `drive`) riguarda solo le auto, Typredicate crea predicati specializzati (tipo `at_vehicle_location`). Perché? Perché così, quando il pianificatore deve verificare le condizioni, lavora con insiemi di oggetti più piccoli e specifici, velocizzando la ricerca delle corrispondenze (unification). È un po’ come cercare un libro in una sezione specifica della biblioteca invece che in tutto l’edificio.

2. Pullup: Anticipare i Controlli Cruciali

Questa è forse l’ottimizzazione più potente. Immaginate un metodo (una “ricetta” per scomporre un task) che ha vari sotto-passaggi, ognuno con le sue precondizioni. Se una precondizione di un passaggio finale è “rigida” (cioè non può essere modificata dai passaggi precedenti all’interno di quel metodo) e magari è comune a tutte le possibili “ricette” per quel task, perché aspettare la fine per controllarla? Pullup la “tira su” (pulls up) nella gerarchia, mettendola come precondizione del metodo stesso, o addirittura del task genitore.

È come se, dovendo costruire un mobile IKEA, controllassimo subito di avere la chiave a brugola necessaria per l’ultimo passaggio, invece di scoprirlo solo alla fine. Questo permette di “potare” rami di ricerca inutili molto prima, risparmiando un sacco di tempo. Pullup rimuove anche task o metodi che diventano irraggiungibili o contraddittori dopo queste “pulizie”. È un po’ come fare “dead code elimination” nei compilatori software.

3. Dejavu: Rompere i Loop Ricorsivi

Vi ricordate il problema della ricorsione infinita? Dejavu è la nostra arma segreta contro questo. Quando rileva un task che rischia di entrare in un loop (scomponendosi in sé stesso, direttamente o indirettamente), Dejavu fa due cose:

• Modifica il dominio aggiungendo dei task “invisibili” speciali (che non appariranno nel piano finale) per “marcare” quando si entra e si esce dalla scomposizione di quel task ricorsivo.
• Usa una cache esterna (che non viene cancellata quando il pianificatore torna indietro sui suoi passi, il cosiddetto backtracking) per ricordarsi quali combinazioni di task e stati ha già esplorato e che hanno portato a un fallimento.

In pratica, se il pianificatore sta per imboccare una strada che sa già essere un vicolo cieco perché l’ha già percorsa prima in una situazione identica, Dejavu lo ferma subito. Fondamentale per domini complessi con cicli!

Non Solo Middle-end: Ottimizzazioni nel Back-end

Anche il back-end fa la sua parte. Prima di generare il codice finale, analizziamo la struttura del problema:

• Separazione Stato Rigido/Fluente: Le informazioni che non cambiano mai (come i tipi o certe relazioni fisse) vengono separate da quelle che cambiano durante la pianificazione (lo stato “fluente”). Questo rende più efficiente la gestione dello stato.
• Ordinamento Intelligente delle Precondizioni: Quando un operatore o un metodo ha più precondizioni da verificare, non le controlliamo a caso. Mettiamo prima quelle “ground” (senza variabili) e poi quelle “lifted” (con variabili), ordinando queste ultime per minimizzare i tentativi di unificazione. È come rispondere prima alle domande facili di un test!

Come Si Comporta HyperTensioN sul Campo?

Abbiamo testato HyperTensioN e le sue ottimizzazioni su diversi domini usati nella competizione IPC 2020. I risultati sono stati illuminanti!

• Woodworking (Lavorazione del legno): Qui Pullup ha dato una piccola mano, permettendoci di risolvere un paio di problemi in più entro il tempo limite.
• Rover (Robot su un pianeta): Sorprendentemente, in questo dominio le ottimizzazioni non hanno portato grandi benefici. Probabilmente il dominio era già ben scritto dall’esperto, quasi “pre-ottimizzato”.
• Transport (Trasporto pacchi): Questo è stato un caso da manuale! Ogni singola ottimizzazione (Typredicate, Pullup, Dejavu) ha contribuito a ridurre drasticamente i tempi. Combinandole tutte, abbiamo risolto problemi complessi in meno di un secondo! Pullup è stato cruciale perché il dominio originale aveva poche precondizioni nei metodi, Pullup le ha “scoperte” negli operatori e le ha portate su. Dejavu ha gestito i cicli inevitabili nel muoversi tra le città.
• Snake (Serpenti che si muovono): Qui Dejavu è stato il re. Senza di esso, il pianificatore rischiava di perdersi in loop infiniti muovendo i serpenti avanti e indietro. Pullup ha comunque dato una bella accelerata sui problemi più tosti.

In generale, abbiamo visto che la combinazione Typredicate + Pullup + Dejavu (TPD), o anche solo Pullup + Dejavu (PD) o Dejavu (D) da solo, sono le configurazioni più performanti sulla maggior parte dei domini. Typredicate da solo serve a poco, ma diventa utile in combinazione con gli altri, specialmente in domini come Transport.

E Rispetto agli Altri?

Ci siamo anche chiesti: queste ottimizzazioni, che modificano la *descrizione* del problema, potrebbero aiutare anche altri pianificatori? Abbiamo provato a dare le versioni ottimizzate dei domini in pasto ad altri sistemi noti come PANDA_Pi, Lilotane e SIADEX. I risultati sono stati misti. Per alcuni (come SIADEX in certi casi), le nostre ottimizzazioni hanno effettivamente migliorato le performance senza toccare il codice del pianificatore! Per altri, le modifiche (specialmente la gestione dei tipi di Typredicate) sembravano interferire con i loro meccanismi interni (es. il grounding di PANDA o la gestione dei tipi di Lilotane). Questo dimostra quanto l’interazione tra la descrizione del dominio e l’algoritmo del pianificatore sia delicata e importante.

Conclusioni e Futuro

HyperTensioN, con la sua architettura flessibile e le sue potenti ottimizzazioni (specialmente Pullup e Dejavu), ha dimostrato di poter affrontare domini HTN complessi e ricorsivi in modo molto efficiente. È un po’ come avere un motore di ricerca super veloce che sa anche evitare i vicoli ciechi e le strade già battute.

Cosa ci riserva il futuro? Vogliamo approfondire la teoria dietro queste tecniche, sviluppare ottimizzazioni ancora più spinte, supportare descrizioni di dominio ancora più ricche (magari con numeri o tempo) e integrare euristiche per guidare la ricerca in modo ancora più intelligente. La strada della pianificazione AI è ancora lunga e piena di sfide affascinanti!

Fonte: Springer