Planificación de movimiento de robots mediante la asignación aleatoria de puntos

Abstract

[ES] El presente trabajo consiste en el estudio, comparación e implementación de varios algoritmos destinados a la planificación de movimiento de robots utilizando MATLAB. Estos algoritmos están basados en la asignación aleatoria de puntos y garantizan la obtención de trayectorias entre dos puntos dados, en un entorno con obstáculos a evitar. Se han implementado más de diez de estos algoritmos entre los que se encuentran los algoritmos de Dijkstra y A* usados en la búsqueda en grafos, varias versiones de los algoritmos PRM y RRT que se centran plenamente en la asignación aleatoria de puntos sin tener en cuenta la cinemática del robot y las trayectorias de Dubins y Reeds-Shepp que se centran en obtener trayectorias teniendo en cuenta las restricciones cinemáticas de los vehículos en entornos sin obstáculos. Adicionalmente se ha optado por combinar las trayectorias de Reeds-Shepp con el algoritmo RRT para lograr un algoritmo que garantiza la generación de trayectorias en entornos con obstáculos y que dichas trayectorias puedan ser realizadas por un robot real. Algunos de los algoritmos implementados ya se encuentran en MATLAB mientras que otros no están disponibles en el momento de la realización del trabajo. A pesar de esto, se han comparado los resultados entre las versiones implementadas y las disponibles en MATLAB y se ha comprobado que las versiones implementadas logran mejorar en muchas ocasiones los tiempos de ejecución obtenidos con MATLAB. Asimismo, todos los algoritmos implementados se han comparado entre sí con el fin de comprobar cuales ofrecen mejores resultados evaluando su tiempo de respuesta y la distancia de la trayectoria obtenida y se ha concluido que para la mayoría de los casos el RRT Bidireccional ofrece los tiempos de ejecución más reducidos y el RRT* las distancias más cortas.

[EN] This work consists of the study, comparison and implementation of several algorithms for robot motion planning using MATLAB. These algorithms are based on the random assignment of points and guarantee the obtention of trajectories between two given points, in an environment with obstacles to avoid. More than ten of these algorithms have been implemented, including the Dijkstra and A* algorithms used in graph search, several versions of the PRM and RRT algorithms that focus fully on random point assignment without taking into account the kinematics of the robot, and the Dubins and Reeds-Shepp trajectories that focus on obtaining trajectories taking into account the kinematic constraints of vehicles in obstacle-free environments. Additionally, the Reeds-Shepp trajectories have been combined with the RRT algorithm to achieve an algorithm that guarantees the generation of trajectories in environments with obstacles and that these trajectories can be carried out by a real robot. Some of the implemented algorithms are already in MATLAB while others are not available at the time of the work. Despite this, the results have been compared between the implemented versions and those available in MATLAB and it has been found that the implemented versions manage to improve in many occasions the execution times obtained with MATLAB. Likewise, all the implemented algorithms have been compared with each other in order to check which ones offer better results by evaluating their response time and the distance of the trajectory obtained and it has been concluded that for most of the cases the Bidirectional RRT offers the shortest execution times and the RRT* the shortest distances.

[CA] El present treball consisteix en l’estudi, comparació e implementació de varis algoritmes destinats a la planificació de moviment de robots utilitzant MATLAB. Aquests algoritmes estan basats en l’assignació aleatòria de punts i garanteixen l’obtenció de trajectòries entre dos punts donats, en un entorn amb obstacles per evitar. S’han implementat més de deu algoritmes entre els quals es troben els algoritmes de Dijkstra i A* utilitzats en la cerca en grafs, varis versions dels algoritmes PRM y RRT que es centren plenament en la assignació aleatòria de punts sense tindre en compte la cinemàtica del robot i les trajectòries de Dubins i Reeds-Shepp que es centren en obtindre trajectòries tenint en compte les restriccions cinemàtiques del robot en entorns sense obstacles. Addicionalment, s’ha optat per combinar les trajectòries de ReedsShepp amb l’algoritme RRT per aconseguir un algoritme que garanteix la generació de trajectòries en entorns amb obstacles i que aquestes trajectòries puguen ser realitzades per un robot reial.