Analysis of implementation techniques for an A* search based on the LM-Cut heuristic

Implement and develop efficient and informative heuristic functions is a key step in automated planning, where the efficiency of algorithms such as A* strongly depends on the quality of the heuristic. This work studies the Landmark-Cut (LM-Cut) heuristic, an admissible heuristic derived from delete relaxation and cost partitioning. We present a complete implementation of LM-Cut in C++, including optimizations such as incremental h_max updates. We also implement a simplified variant, Quick Cutting, which reduces the time execution for cut extraction by "approximate" the cut. Experimental evaluation on standard IPC benchmark domains shows that our implementation LMCut beat the planning solver Fast Downward in many instances, and Quick Cutting achieves significantly lower computation times at the expense of expanded nodes. Our results confirm that LM-Cut is a practical and effective admissible heuristic, that its approximation, Quick Cutting, can be valuable in practice, and that careful implementation choices have a strong impact on performance.

L'implementazione e lo sviluppo di funzioni euristiche è un punto chiave negli automated planning, dove l'efficienza degli algoritmi come A* dipende fortemente dalla qualità della stima della funzione euristica. In questa tesi esploriamo l'euristica denominata Landmark-Cut (LM-Cut), un'euristica ammissibile che sfrutta il sistema delete relaxation con il concetto del cost partitioning. Alla fine di questo paper presenteremo la nostra implementazione di LM-Cut in C++, con ottimizzazioni come il calcolo incrementale di h_max. Oltre a LM-Cut, implementeremo una variazione dell'eurisitica, denominata Quick Cutting, che tenta di ridurre il tempo di calcolo dell'eurisitica, approssimando la fase di taglio. I risultati sperimentali effettuati su problemi IPC mostreranno che il nostro algoritmo con LM-Cut batte Fast Downward in molti problemi, e Quick Cutting ottiene un significativo miglioramento nei tempi di esecuzione. I nostri risultati confermano la qualità di LM-Cut come euristica pratica, e come la sua approssimazione, Quick Cutting, possa essere un'euristica vincente in implementazioni pratiche.