Studio e Sperimentazione dell'Algoritmo di Pathfinding "Hierarchical Annotated A*"

This thesis focuses on the study and experimentation of the pathfinding algorithm Hierarchical Annotated A* (HAA*). It is a variant of the well-known pathfinding algorithm A*. HAA* allows us to map an extended pathfinding problem, which introduces agents of different sizes and a heterogeneous environment with various terrain types, into a canonical problem defined by A* that considers only two types of terrain: traversable and non-traversable. It presents an optimized search thanks to the use of macro-operations defined on a smaller hierarchical representation of the original map (this is known as hierarchical path planning). In this work, we also present an implementation of a demonstrator that allows us to interact with and visualize HAA*.

Questa tesi si incentra sullo studio e la sperimentazione dell'algoritmo di pathfinding Hierarchical Annotated A* (HAA*). Si tratta di una variante del noto algoritmo A* che ci permette di ricondurre un problema di pathfinding esteso, caratterizzato da agenti di varie dimensioni e un ambiente eterogeneo composto da diverse tipologie di terreno, al problema classico, o canonico, definito da A* che presenta solo due tipologie di terreni: attraversabili e non attraversabili. Inoltre permette di ottimizzare la ricerca definendo macro-operazioni su una rappresentazione gerarchica di dimensioni ridotte (questa metodologia è conosciuta come path planning gerarchico) della mappa originale. Inoltre si presenta l'implementazione di un dimostratore che ci permette di interagire e visualizzare l'algoritmo.