I problemi di pianificazione in molti scenari realistici spesso coinvolgono aspetti temporali: le attività da svolgere richiedono tempo e sono sottoposte a vincoli temporali.
Tra i diversi approcci alla pianificazione temporale rientrano
quelli basati sulle
cosiddette
La soluzione di un problema
di pianificazione (un piano) è costituito da un insieme di
timeline che rispettano i vincoli del problema. Nel caso dei
cosiddetti
Per una descrizione astratta dell'approccio alla pianificazione e scheduling mediante timeline si veda Planning and execution with flexible timelines: a formal account (Cialdea, Orlandini, Umbrico, Acta Informatica, 2016).
Nell'ambito di questo progetto è stato sviluppato il framework di pianificazione EPSL (Extensible Planning and Scheduling Library), descritto ad esempio in EPSL: Enriching a Temporal Planner with Resources and a Hierarchy-Based Heuristic (AIxIA 2015).
In questo contesto di ricerca, sono disponibili argomenti per diverse tesi o tirocini.
Quando un piano flessibile è stato generato dal
pianificatore, si pone il problema della sua esecuzione. Nel caso in
cui sono presenti componenti o eventi non controllabili dal sistema,
non è detto che il piano possa sempre essere eseguito,
qualunque sia il comportamento degli eventi esterni. Inoltre, anche
quando potrebbe esserlo, il successo potrebbe essere compromesso da
scelte sbagliate fatte, stadio per stadio, dall'esecutore. È quindi
importante generare (quando possibile) una
Molti sistemi di pianificazione a timeline rappresentano internamente gli insiemi di timeline mediante reti temporali con incertezza (STNU: simple temporal network with uncertainty, si veda ad esempio questo tutorial di Luke Hunsberger), per le quali sono stati definiti algoritmi di verifica di controllabilità. Una tecnica alternativa per la verifica della controllabilità di piani flessibili con incertezza si basa sulla rappresentazione del piano in termini di reti di Timed Game Automata (TGA). Si veda An executable semantics of flexible plans in terms of Timed Game Automata (Cialdea, Orlandini, Time 2015), in cui viene presentata la metodologia di rappresentazione e l'uso del tool UPPAAL TIGA per generare strategie di esecuzione.
L'agomento di questa tesi è la progettazione e implementazione di un sistema che codifichi i piani flessibili in termini di STNU e gli applichi uno degli algoritmi per la verifica della controllabilità delle STNU (anch'esso da implementare). Successivamente, il sistema andrà sperimentato ed i suoi risultati confrontati con quelli che si ottengono mediante la tecnica di riduzione a reti di TGA.
Questo argomento, strettamente collegato al precedente, riguarda l'implementazione di un tool che traduca in codice eseguibile le strategie generate da UPPAAL TIGA e l'applicazione dell'intero approccio in qualche scenario realistico.
Sempre in relazione all'esecuzione di piani flessibili, un argomento di lavoro riguarda la definizione e implementazione di una traduzione dei piani generati dal pianificatore EPSL nel linguaggio PLEXIL (Plan Execution Interchange Language), un linguaggio sviluppato da NASA per rappresentare piani, unito ad una tecnologia di esecuzione da parte di sistemi reali o simulatori. PLEXIL comprende infatti diversi tools, tra cui:
In molti domini di pianificazione realistici si devono rispettare non soltanto vincoli temporali, ma anche vincoli relativi a un determinato insieme di risorse che devono essere gestite durante l'esecuzione del piano. In generale, una risorsa può essere consumata e/o prodotta dalle attività del sistema, ha una capacità che può variare in un determinato intervallo e ha un dato livello iniziale. L'esempio tipico di una risorsa di questo tipo è un serbatoio di carburante. Perché un piano rispetti i vincoli sulle risorse, si deve garantire che in nessun momento della sua esecuzione il livello di una risorsa scenda sotto il minimo consentito o salga oltre il massimo. Quindi, in particolare, si deve prestare attenzione all'uso contemporaneo della stessa risorsa da parte di diverse attività.
Attualmente, il sistema EPSL gestisce soltanto un tipo particolare di risorse, quelle dette "rinnovabili" (o "discrete"), caratterizzate dal fatto che un'attività consuma, quando inizia, una determinata quantità della risorsa e rilascia (produce) la stessa quantità quando termina.
L'obiettivo di questo lavoro è quello di estendere il framework EPSL in modo che possa gestire il tipo più generale di risorse, in modo coerente con una caratterizzazione formale delle risorse stesse nella pianificazione a timeline.