Implementation, comparison, and advances in global planners using Ackerman motion primitives

Motion planning plays an important role in autonomous navigation, it can be defined as the search for a collision-free path from an initial state to a final state. A good path planner, specially when dealing with non-holonomic vehicles, should also take into considerations the capabilities of the vehicle (kinematic and dynamic constraints), so that the path is not only collision-free, but feasible for the robot. Path planning has been generally divided in two parts, a global path planning and a local path planning, both parts are complementary and in most cases used together. This thesis is focused on the global planning problem for non-holonomic vehicles in an (x, y, θ) space, with the by product of implementing novel global planners in the Robot Op- erating System (ROS) framework, nowadays, widely used in the robotics community. To tackle our goal, two ROS nodes are created, the first uses the search-based algorithms implementations by SBPL (Search Based Planning Library [3]). The second uses random sampling planners implementations provided by OMPL (Open Motion Planning Library [1]). To deal with the non-holonomic constraints of the vehicle, motion primitives can be used; which for the SBPL environment has already support to access motion primitives. In the case of OMPl planners, even though spaces like Dubins and Reeds-Shepp exist, the use of motion primitives is not given. Therefore an implementation of RRT* with Motion Primitives done by Basak Sakcak [4] was modified, to work with the same motion primitives used in the SBPL approach. Then, three new methods of setting a sample set were created to improve the performance of the planner, and achieve real-time performance. Finally, performance comparisons were done between the different planners in terms of length of the path and planning time on two real world use cases.

La pianificazione del movimento svolge un ruolo importante nella navigazione autonoma, può essere definita come la ricerca de un percorso senza collisioni da uno stato iniziale a uno stato finale. Un buon pianificatore di percorsi, specialmente quando si tratta di veicoli non-olonomici, dovrebbe anche prendere in considerazione le caratteristiche del veicolo (vincoli cinematici e dinamici), in modo che il percorso sia percorribile per il robot. La pianificazione del percorso viene generalmente suddivisa in due parti, una pianificazione globale e una locale, che sono complementari e nella maggior parte dei casi utilizzate insieme. L’obiettivo principale della tesi è lo studio di pianificatori globali per veicoli non-olonomici nello spazio (x, y, θ). Per affrontare il nostro obiettivo, abbiamo creato due pianificatori, il primo, che utilizza gli algoritmi di ricerca su grafo, basato sulla libreria SBPL (Search Based Planning Library [3]). Il secondo sfrutta la libreria OMPL (Open Motion Planning Library [1]) che implementa al- goritmi basati sul campionamento. Per gestire i vincoli non-olonomici del veicolo, è possibile utilizzare le primitive di movi- mento.Nel caso di SBPL l’uso delle primitive è supportato mentre nel caso dei pianificatori OMPL, anche se esistono spazi come Dubins e Reeds-Shepp, l’uso delle primitive di movimento non è previsto. L’implementazione di RRT* che sfrutta le primitive di movimento realizzata da Basak Sakcak[4] è stata usata come punto di partenza per la tesi, e modificata per lavorare con le stesse primitive di movimento utilizzate nell’approccio con SBPL e ottenere prestazioni real-time. I risultati presentano il confronto delle prestazioni tra i diversi pianificatori in termini di lunghezza del percorso e tempo di pianificazione.