Development of a modified A-Star Algorithm for path planning

Path planning plays an essential role in mobile robot navigation, and the A* algorithm is one of the best-known path planning algorithms. However, the conventional A* algorithm and the subsequent improved algorithms still have some limitations in terms of robustness and efficiency. These limitations include slow algorithm efficiency, weak robustness and collision. In this work of thesis is proposed a modified implementation of A* algorithm, this algorithm is chosen after the study of the state of the art. The new algorithm introduces the expansion distance, a new method to construct the OPEN list and heuristic function optimization .The expansion distance extends a certain distance from obstacles to improve path robustness by avoiding collisions. Heuristic function optimization designs a new heuristic function to replace the traditional heuristic function. Furthermore another improvement is performed to solve the problem of slow search speed and low efficiency of the algorithm. When a set of nodes contains obstacle, this node is defined as an untrusted point, it is pre-inserted in the CLOSED list, and will not be searched or evaluated. The rest of the thesis activity concerns the simulation of autonomous driving, aimed to reproduce the behavior of a work vehicle able to carry out its activity in autonomous or semi-autonomous way. In this case the vehicle has to move from its starting position to a certain point of arrival, avoiding collisions with any type of obstacle. To carry out the simulation are used Simulink and ROS, and two type of kinematics: differential drive and four-wheel steering, that is then approximated with the bicycle model.

La pianificazione del percorso svolge un ruolo essenziale nella navigazione dei robot mobili e l’algoritmo A* è uno degli algoritmi di pianificazione del percorso più noti. Tuttavia, l’algoritmo A* convenzionale e i successivi algoritmi migliorati presentano ancora alcune limitazioni in termini di robustezza ed efficienza. Queste limitazioni includono la bassa efficienza dell’algoritmo , debole robustezza e la collisione. In questo lavoro di tesi viene proposta un’implementazione modificata dell’algoritmo A*, tale algoritmo viene scelto dopo una fase di studio dello stato dell’arte. Il nuovo algoritmo introduce la distanza di espansione, un nuovo metodo per costruire la lista OPEN e l’ottimizzazione della funzione euristica. La distanza di espansione introduce una certa distanza dagli ostacoli per migliorare la robustezza del percorso evitando collisioni. Ottimizzazione della funzione euristica vuol dire progettare una nuova funzione euristica per sostituire quella tradizionale. Inoltre viene eseguito un altro miglioramento per risolvere il problema della bassa velocità di ricerca e della bassa efficienza dell’algoritmo. Quando un insieme di nodi contiene un ostacolo, questo nodo viene definito come un punto non attendibile, viene preinserito nella CLOSED list e non verrà ricercato o valutato. Il resto dell’attività di tesi riguarda la simulazione e la guida autonoma, volta a riprodurre il comportamento di un mezzo da lavoro in grado di svolgere la propria attività in modo autonomo o semi-autonomo. In questo caso il veicolo deve spostarsi dalla sua posizione di partenza ad un certo punto di arrivo, evitando collisioni con qualsiasi tipo di ostacolo. Per effettuare la simulazione vengono utilizzati Simulink e ROS, e due tipi di cinematica: trazione differenziale e modello bicicletta, derivato dal più complesso modello a 4 ruote sterzanti.