ADJ: un sistema per l’adattamento automatico di piani

Il sistema ADJ, è stato sviluppato presso l’Università degli Studi di Brescia, è scritto in C e si basa in parte sul codice del pianificatore IPP3 (sviluppato presso la Freiburg University) del quale si sono inizialmente utilizzate alcune strutture dati e l’algoritmo di ricerca sistematica (fino alla versione 1.3 di ADJ). Si tratta di un sistema per l’adattamento automatico di piani che utilizza un algoritmo di ricerca sistematica.

Utilizzando ADJ sono stati effettuati numerosi esperimenti al fine di verificare l’efficienza delle tecniche proposte per l’adattamento di piani. Con ADJ 2.0 si è sostituito l’algoritmo di ricerca interno con la possibilità di utilizzare un pianificatore esterno (IPP4 e FF) dato che l’algoritmo precedentemente utilizzato è stato ormai ampiamente sorpassato dai nuovi pianificatori (come FF per l’appunto).

Al fine di valutare le prestazioni di ADJ nell’adattamento di piani, sono state considerate numerose varianti di alcuni problemi tratti dalle competizioni internazionali che si sono tenute nel corso di AIPS98 e AIPS2000 (specificati in STRIPS ed in PDDL) normalmente utilizzati per testare le prestazioni dei diversi sistemi di pianificazione. Ciascuna variante è stata ottenuta cambiando uno o più fatti nella descrizione dello stato iniziale e/o stato finale (goal) del problema originale.
ADJ riceve quindi in ingresso la descrizione del problema modificato ed un piano per il problema originale che risulta essere non valido per il nuovo problema (tutte le varianti sono state costruite in modo da rendere il piano di ingresso non valido per il problema modificato).

I risultati di questi esperimenti mostrano che, sotto certe condizioni, ADJ (in fase di adattamento) può essere fino a 4 ordini di grandezza più veloce rispetto ad una ripianificazione completa (utilizzando Graphplan o IPP) e 2 ordini di grandezza più rapido del già efficientissimo FF.

Implementazioni disponibili

  • ADJ 1.0 (prima versione sperimentale basata su planning graph)
  • ADJ 1.3 (versione ottimizzata, fa un uso “leggero” del planning graph ed utilizza varie euristiche per il calcolo dei goal (es: link causali) oltre ad una goal agenda per l’ordinamento degli stessi)
  • ADJ 2.0.2 (versione in grado di gestire i domini PDDL, utilizza per le fasi di ricerca un pianificatore esterno – attualmente FF e IPP4 – e sfrutta il metodo degli invarianti calcolati da DISCOPLAN per gestire le relazioni di mutua esclusione; l’output è compatibile con il formato AIPS2002)

Programmi & Utilities

  • SIMULATOR 0.9 (simula l’applicazione di un piano in presenza di rumore casuale opportunamente generato)
  • TEST-DOMAINS (domini strips e pddl utilizzati per i test sperimentali + script bash/perl per la raccolta dei dati)
  • FCT2PDDL (convertitore di files *.fct da STRIPS a PDDL)