Planificación de trayectorias para robots no holonómicos en entornos con fuertes restricciones dimensionales

Abstract

La mayoría de los algoritmos de cálculo de trayectorias existentes trabajan con objetos móviles que, o bien tienen dimensiones despreciables con respecto a la resolución del mapa utilizado, pudiéndose considerar objetos puntuales; o bien son objetos de forma más o menos cilíndrica, de forma que se puede asemejar el problema al caso anterior mediante la técnica de “engordar” los obstáculos presentes en el mapa para garantizar que una vez obtenida una trayectoria que salve dichos obstáculos, no se produzcan colisiones. Otra problemática de muchos algoritmos existentes es la suposición de que el objeto móvil es un sistema holonómico; esto es, capaz de modificar su dirección instantáneamente y sin necesidad de rotar previamente. Esta suposición, de nuevo, es apropiada sólo en caso de que los nodos del mapa sean muy grandes en relación con el tamaño del vehículo, o para el caso de vehículos muy especiales, como pueden ser cuadricópteros o robots de forma esférica. Cuando el vehículo autónomo para el que se quiere obtener una trayectoria presenta gran esbeltez (planta rectangular, por ejemplo) la técnica de engordar los obstáculos presentes en el mapa no es adecuada, siendo necesario tener en cuenta la orientación del vehículo en el cálculo de la trayectoria. Así por ejemplo, un camión puede aparcarse pegado al costado de una nave industrial siempre que se encuentre paralelo a la pared, pero en sentido perpendicular la distancia del centro geométrico del camión a dicha pared deberá ser mucho mayor para evitar colisionar con ella. En la presente tesis se pretende abordar el problema del cálculo de trayectorias en los casos que presenten simultáneamente las siguientes características: •Vehículo no holonómico. •Vehículo de gran esbeltez. •Nodos del mapa de dimensiones muy inferiores a las del vehículo, lo que permite obtener gran precisión. •Necesidad de gran maniobrabilidad para ajustarsea pasos estrechos en el mapa. Se estudiarán las posibilidades de modificación de algoritmos de búsqueda (A*, D*…) para incluir información acerca de la orientación del vehículo, discretizando sus valores de orientación igual que se realiza con los de posición (x, y), añadiendo así una dimensión más al problema. Se estudiará también la modificación de estos algoritmos para utilizar caminos precalculados entre nodos que respeten las restricciones dinámicas del vehículo, así como las técnicas que permitan la selección de un subconjunto finito de estos caminos, en teoría infinitos, que permita la ejecución del algoritmo con un tiempo de cálculo y un consumo de memoria razonables.

A maioría dos algoritmos de cálculo de traxectorias existentes traballan con obxectos móbiles que, ou ben teñen dimensións despreciables con respecto á resolución do mapa utilizado, podéndose considerar obxectos puntuais; ou ben son obxectos de forma máis ou menos cilíndrica, de forma que se pode asemellar o problema ao caso anterior mediante a técnica de engordar os obstáculos presentes no mapa para garantir que unha vez obtida unha traxectoria que salve devanditos obstáculos, non se produzan colisións. Outra problemática de moitos algoritmos existentes é a suposición de que o obxecto móbil é un sistema holonómico; isto é, capaz de modificar a súa dirección instantaneamente e sen necesidade de rotar previamente. Esta suposición, de novo, é apropiada só no caso de que os nodos do mapa sexan moi grandes en relación co tamaño do vehículo, ou para o caso de vehículos moi especiais, como poden ser cuadricópteros ou robots de forma esférica. Cando o vehículo autónomo para o que se quere obter unha traxectoria presenta gran esbeltez (planta rectangular, por exemplo) a técnica de engordar os obstáculos presentes no mapa non é axeitada, sendo necesario ter en conta a orientación do vehículo no cálculo da traxectoria. Así por exemplo, un camión pode aparcarse pegado ao costado dunha nave industrial sempre que se atope paralelo á parede, pero en sentido perpendicular a distancia do centro xeométrico do camión á devandita parede deberá ser moito maior para evitar chocar con ela. Na presente tese preténdese abordar o problema do cálculo de traxectorias nos casos que presenten simultaneamente as seguintes características: - Vehículo non holonómico. - Vehículo de gran esbeltez. - Nodos do mapa de dimensións moi inferiores ás do vehículo, o que permite obter gran precisión. - Necesidade de gran manobrabilidade para se axustar a pasos estreitos no mapa. Estudaranse as posibilidades de modificación de algoritmos de procura (A*, D*) para incluír información acerca da orientación do vehículo, discretizando os seus valores de orientación igual que se realiza cos de posición (x, y), engadindo así unha dimensión máis ao problema. Estudarase tamén a modificación destes algoritmos para utilizar camiños precalculados entre nodos que respecten as restricións dinámicas do vehículo, así como as técnicas que permitan a selección dun subconxunto finito destes camiños, en teoría infinitos, que permita a execución do algoritmo cun tempo de cálculo e un consumo de memoria razoables.

The majority of the present path planning calculation algorithms work with mobile objects that, either have negligible dimensions compared with the resolution of the map used; either have shapes more or less cylindrical, so that the problem can be reduced to the previous case by means of the technic of growing the obstacles in the map by the radius of the robot to guarantee a collision free trajectory. Another problematic of many of the present algorithms is the assumption that the mobile object is an holonomic system; that is, a vehicle capable of modify its direction instantly and without the need of previous rotations. This supposition, again, is appropriate only in the case that the nodes of the map are very big with respect to the size of the vehicle, or for the case of very special vehicles, as quadricopters or spherical robots. When the autonomous vehicle presents a slender shape (rectangular plant, for example) the technic of growing the obstacles present in the map is not suitable, being necessary to take into account the orientation of the vehicle in the calculation of the path. For example, a truck can park parallel to the wall of a warehouse and very close to it but the same truck will collide with this wall if we try to present it on the same position while rotated ninety degrees. In the present thesis we try to overcome the problems of the calculation of paths in situations that presents simultaneously the following characteristics: - Non holonomic vehicles. - Slender vehicles. - Nodes of the map with very smaller dimensions compared with the size of the vehicle, which allows to obtain big precision. - Need of great manoeuvrability for passing narrow corridors in the map. We will study the possibilities of modification of suitable graph search algorithms (A*, D*) to include vehicle orientation information, discretizing this values on the same way as it is done usually with position (x, y), adding one more dimension to the problem. We will also explore the modification of these algorithms to use precalculated steps between nodes that are compliant with the dynamic restrictions of the vehicle, as well as technics that allow the selection of a finite subset of these compliant steps, in order to allow the execution of the algorithm within a reasonable time and with a reasonable memory consumption.