MODELS AND ALGORITHMS FOR RESILIENT PLANNING UNDER ACTION FAILURES

Classical planning typically assumes that an agent’s actions are executed successfully as planned. However, in real-world scenarios, this assumption rarely holds: actions may fail in unpredictable ways that are not explicitly captured in the planning model. To address this challenge, this thesis introduces the Resilient Planning problem, whose goal is to ensure that an agent can achieve its objectives even in the presence of a bounded number of action failures. Within this new problem, the ResPlan algorithm is presented for the generation of k-resilient plans, that is, plans guaranteeing goal achievement as long as no more than k action failures occur during execution. Building upon this foundation, the thesis also proposes an enhanced version of ResPlan that incorporates two main improvements. The first is a pruning strategy based on landmarks, which discards paths that are guaranteed to be inconsistent with the recovery constraints a priori. This approach reduces the search space, particularly in unsatisfiable instances where no resilient plan exists, by preventing the exploration of branches that cannot lead to a valid solution. The second introduces a planning adaptation strategy where regressed state formulas are used to identify resilient plan suffixes. This allows the search to reconnect to previously verified states, avoiding redundant planner calls and reducing the number of iterations to identify a resilient plan when one exists. The proposed methods are experimentally evaluated against the original ResPlan algorithm and approaches based on Fully Observable Non-Deterministic (FOND) planning, demonstrating substantial improvements in terms of efficiency and robustness. Overall, the thesis advances the state of the art in robust automated planning, contributing to the development of agents capable of acting reliably in unpredictable environments subject to action failures.

a pianificazione classica si basa tipicamente sull’ipotesi intrinseca che le azioni di un agente vengano eseguite con successo come pianificato. Tuttavia, negli scenari del mondo reale, questa ipotesi si rivela troppo ottimistica: le azioni possono fallire in modi imprevedibili che non sono esplicitamente definiti nel modello di pianificazione. Per affrontare questa sfida, questa tesi introduce il problema della Pianificazione Resiliente (Resilient Planning problem), il cui obiettivo `e garantire che un agente possa raggiungere i propri obiettivi anche in presenza di un numero limitato di fallimenti delle azioni. All’interno di questo nuovo problema, viene presentato l’algoritmo ResPlan per la generazione di piani k-resilienti, ovvero piani che garantiscono il raggiungimento dell’obiettivo a condizione che non si verifichino pi`u di k fallimenti delle azioni durante l’esecuzione. Basandosi su queste fondamenta, la tesi propone anche una versione potenziata di ResPlan che incorpora due miglioramenti principali. Il primo `e una strategia di potatura basata sui landmarks, che scarta a priori i percorsi che non soddisfano le condizioni di ripristino. Questo approccio riduce lo spazio di ricerca, in particolare nelle istanze insoddisfacibili dove non esiste alcun piano resiliente, prevenendo l’esplorazione di rami che non possono portare a una soluzione valida. Il secondo introduce una strategia di adattamento della pianificazione in cui le formule di stato regredite vengono utilizzate per identificare suffissi di piano resilienti. Ci`o consente, durante la ricerca, di riconnettersi a stati precedentemente verificati, evitando chiamate ridondanti al pianificatore e riducendo il numero di iterazioni necessarie per identificare un piano resiliente, qualora ne esista uno. I metodi proposti sono valutati sperimentalmente rispetto all’algoritmo ResPlan originale e agli approcci basati sulla pianificazione Non Deterministica Completamente Osservabile (FOND), dimostrando miglioramenti sostanziali in termini di efficienza e robustezza. Complessivamente, la tesi offre un contributo allo stato dell’arte della pianificazione automatica robusta, permettendo lo sviluppo di agenti capaci di agire con affidabilit`a in ambienti incerti e soggetti a errori di esecuzione.