Design and Evaluation of a Novel Heuristic for Delete-Free AI Planning

In this thesis, we present a novel heuristic for solving delete-free AI planning problems. Delete-free planning, where actions do not remove facts from the world state, offers a simplified yet meaningful subset of classical planning. Our proposed heuristic estimates, for each action, the cost of the shortest path required to reach a goal fact. This is complemented by a pruning strategy that identifies and excludes actions which do not contribute to achieving the goal. We evaluate our method against established primal heuristics on a comprehensive set of benchmark problems. The results demonstrate that our method achieves superior performance, solving the most instances and producing higher-quality plans with greater stability across random seeds. While iterative refinement techniques showed limited gains, the core heuristic proves to be a highly effective constructive method for delete-free planning.

In questa tesi, viene presentata una nuova euristica per la risoluzione dei problemi di delete-free AI planning. Questo contesto, in cui le azioni non rimuovono fatti che sono già verificati, costituisce un sottoinsieme del classical planning che, pur nella sua semplicità, si rivela di grande interesse. Il nostro metodo si basa su una stima del costo del percorso più breve per raggiungere un fatto-obiettivo per ogni singola azione. Tale approccio è ulteriormente potenziato da una strategia di pruning che permette di escludere preventivamente le azioni ritenute non utili al raggiungimento dell' obiettivo. Abbiamo condotto una valutazione della nostra strategia su un'ampia serie di problemi benchmark, confrontandolo con euristiche primali consolidate. I risultati ottenuti dimostrano una performance superiore, con un maggior numero di istanze risolte e la generazione di piani di qualità più elevata e con maggiore stabilità. Sebbene le tecniche di affinamento iterativo abbiano mostrato benefici limitati, la nostra euristica si conferma un metodo costruttivo altamente efficace per il delete-free planning.