Confronto di algoritmi di pianificazione di traiettoria sampling-based per robot mobili

The purpose of this thesis is to analyze and compare some Sampling-based algorithms for Motion Planning of a mobile robot. The goal of a trajectory planner is to assign an efficient way to drive the robot from an initial state to a final con figuration avoiding collisions with obstacles. Unlike some classical techniques, Sampling-based algorithms are not based on the a priori knowledge of the complete configuration space. Instead, they sample the space with a fixed number of randomly generated nodes. The complexity of exact planning algorithms is often esponential in the dimensionality of the configuration space and thus they are hardly applicable in practice. The main advantage of Sampling-based algorithms is their efficiency for high-dimension con figuration spaces. For this reason, these methods have been succesful also in the field of industrial robots. Here, only mobile robots are considered, but the theory could be applied to more complex robots. The treated algorithms are PRM, RRT and some of their variants such as their optimal versions PRM* and RRT*. Furthermore, the application of these algorithms to kynodynamic models are reported. In particular Kinodynamic RRT* will be presented and simulated. In this work the new algorithm Kinodynamic-PRM* is introduced, that is an evolution of PRM* for a kino-dynamic model of a mobile robot.

Il lavoro svolto in questa tesi si concentra sull'analisi e il confronto di alcuni algoritmi Sampling-based per la pianificazione di traiettoria di un robot mobile. Un algoritmo di pianificazione di traiettoria ha lo scopo di calcolare un tragitto il più possibile efficiente che conduca il robot da uno stato iniziale ad uno finale, evitando collisioni con eventuali ostacoli. A differenza di alcune tecniche classiche che prevedono la conoscenza dell'intero spazio delle configurazioni, gli algoritmi Sampling-based campionano lo spazio in maniera casuale, generando un numero fissato di nodi. La probabilità con cui questi nodi vengono generati è uniforme; per questo, fissando un adeguato numero di iterazioni, si può assumere di coprire gran parte dello spazio libero. Se negli algoritmi classici il carico computazionale risultava esponenziale all'aumentare dei gradi di libertà del robot, negli algoritmi Sampling-based questo non accade. Grazie a questo vantaggio gli algoritmi Sampling-based hanno avuto un grande successo anche nell'ambito della robotica industriale. Qui verranno considerati solo robot mobili, ma la teoria che sta alla base degli algoritmi analizzati potrà essere facilmente applicabile a robot più complessi. Oltre agli algoritmi PRM e RRT, in questo lavoro verranno analizzate le loro versioni ottime PRM* e RRT*. Inoltre un capitolo intero verrà dedicato all'applicazione degli algoritmi Sampling-based a modelli kinodinamici, ovvero modelli più complessi dotati di vincoli anolonomi. Verrà quindi analizzato e implementato l'algoritmo Kinodynamic-RRT* e, applicando la stessa teoria all'algoritmo PRM* si è ottenuto un nuovo algoritmo chiamato Kinodynamic-PRM*.