Effective Approaches for Handling Plan Constraints and Temporally Extended Goals in Automated Planning

A significant challenge in Artificial Intelligence (AI) is to design autonomous systems that can act in complex environments to achieve a final objective while adhering to many constraints. This challenge is tackled by Automated Planning, which is a field of AI that deals with the problem of synthesizing a sequence of actions, i.e. a plan, to achieve a set of goals. A significant body of research focuses on classical planning models, where goals are defined as conditions that must hold in the final state reached by the plan execution. However, there are some major limitations to this approach; many goals of autonomous agents may involve the maintenance of a safety condition over the whole plan execution, reactions to certain inputs within a limited time frame, and intermediate objectives to achieve. Moreover, multiple constraints may dictate the agent's behavior and influence the structure of desired plans. This thesis addresses the problem of planning under these specifications and explores three different ways of formulating these constraints. Firstly, we consider state trajectory constraints as defined in PDDL3, one of the most popular planning languages. Secondly, we introduce a new formalism for expressing trajectory constraints over actions rather than traversed states. Lastly, we consider temporally extended goals expressed in Pure-Past Linear Temporal Logic. For each formalism, we propose a compilation schema to translate planning problems with these specifications into equivalent representations that can be handled by off-the-shelf classical planners. All proposed compilations are polynomial, sound, complete, and preserve the size of the solution. Experimental analysis shows that the proposed approaches perform better than other state-of-the-art techniques in the majority of the considered benchmark domains.

Una delle più importanti sfide dell'Intelligenza Artificiale (IA) è progettare agenti autonomi in grado di agire in ambienti complessi per raggiungere un obiettivo finale rispettando molteplici vincoli. Questa sfida è attualmente affrontata dalla Pianificazione Automatica, un campo dell'IA che si occupa del problema della sintesi di una sequenza di azioni, ovvero un piano, per raggiungere un insieme di obiettivi. Una parte rilevante della ricerca scientifica si concentra sui modelli di pianificazione classica, in cui gli obiettivi sono definiti come condizioni che devono essere soddisfatte nello stato finale raggiunto dall'esecuzione del piano. Tuttavia, questo approccio presenta alcune limitazioni significative; molti obiettivi degli agenti autonomi possono coinvolgere il mantenimento di una condizione di safety durante l'intera esecuzione del piano, reazioni a determinati input entro un periodo di tempo limitato, ed obiettivi aggiuntivi da raggiungere. Inoltre, diversi vincoli possono influenzare il comportamento dell'agente e la struttura dei piani desiderati. Questa tesi affronta il problema della pianificazione con queste specifiche, ed esplora tre diverse modalità di formulazione di questi vincoli. In primo luogo, vengono considerati i vincoli sulla traiettoria degli stati definiti in PDDL3, uno dei linguaggi di pianificazione più diffusi. In secondo luogo, viene introdotto un nuovo formalismo per esprimere vincoli di traiettoria sulle azioni di un piano. Infine, vengono consideriati goal temporali espressi in Pure-Past Linear Temporal Logic. Per ciascun formalismo, viene proposto uno schema di compilazione per tradurre problemi di pianificazione con queste specifiche in rappresentazioni equivalenti gestibili da pianificatori già esistenti. Tutte le compilazioni proposte sono polinomiali, corrette, complete e preservano la dimensione della soluzione. Un’analisi sperimentale mostra che gli approcci proposti ottengono prestazioni migliori rispetto ad altre tecniche all'avanguardia nella maggior parte dei domini di pianificatione considerati.