Implementación y análisis de algoritmos de planificación de caminos. Aplicación a sistemas aéreos no tripulados.

Equation Chapter 1 Section 1 Trabajo Fin de Grado Grado en Ingeniería Aeroespacial Implementación y análisis de algoritmos de planificación de caminos. Aplicación a sistemas aéreos no tripulados. Autor: Nikita Tretiyakov Tutor: Anibal Ollero Baturone Dpto. Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Trabajo Fin de Grado Ingeniería Aeroespacial Implementación y análisis de algoritmos de planificación de caminos. Aplicación a sistemas aéreos no tripulados. Autor: Nikita Tretiyakov Tutor: Anibal Ollero Baturone Catedrático Dpto. de Ingeniería de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 Trabajo Fin de Grado: Implementación y análisis de algoritmos de planificación de caminos. Aplicación a sistemas aéreos no tripulados. Autor: Nikita Tretiyakov Tutor: Anibal Ollero Baturone El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2017 El Secretario del Tribunal Agradecimientos La realización de trabajo ha sido posible gracias a Anibal Ollero Baturone, mi tutor y profesor, que me ha transmitido los conocimientos necesarios y a Álvaro Caballero Gómez que me ha ayudado y me ha guiado durante la realización de este proyecto. 1 Resumen El objetivo de este trabajo es el análisis y la comparación de los algoritmos de búsqueda de camino más usados hoy en día para los Vehículos Aéreos No Tripulados (UAVs). La búsqueda de camino es un problema fundamental dentro del campo de la robótica y su resolución permite que los vehículos sean totalmente autónomos y puedan ir desde un punto inicial o otro nal sin ayuda del ser humano. Dentro de las metodologías existentes, se va a centrar en los algoritmos de búsqueda basados en descomposición en celdas y planicadores probabilísticos. Para el estudio de estas metodologías,se han seleccionado 5 algoritmos: A*, θ∗ , RRT, RRT* y RRT-Connect, y se han programado en MATLAB siguiendo las pautas de su funcionamiento teórico. Una vez programados, se han estudiado sus posibles modicaciones y mejoras y, se ha hecho un análisis comparativo entre ellos 3 Índice de algoritmos 1. Pseudocódigo de A*. . . . . . . . . . . . . . . . . . . . . . . . . . 30 2. Algoritmo AP- θ∗ . Primera parte. . . . . . . . . . . . . . . . . . . 34 3. Algoritmo AP- θ∗ . Segunda parte. . . . . . . . . . . . . . . . . . . 35 4. Pseudocódigo de RRT básico. . . . . . . . . . . . . . . . . . . . . 38 5. RRT*................................... 41 6. RRT-Connect. ............................. 42 10 Capítulo 1 Introducción 1.1. Estado del arte Los Vehículos Aéreos No Tripulados, UAVs (Unmanned Aereal Vehicles), o también denominados Drones, han existido desde la Primera guerra mundial (1917). Durante la mayor parte de su existencia, no gozaban de mucha popularidad debido a su poca abilidad y autonomía limitada en esa época. A partir de los años 90, se ha visto un aumento en producción de UAVs militares que cumplían misiones de vigilancia de alto riesgo. Sin embargo, en la última década, gracias a los últimos avances tecnológicos en los campos de robótica y electrónica, se ha producido un auge de su popularidad y sus aplicaciones se han multiplicado rápidamente en campos muy diversos, tanto militares como civiles [17]. (a) General Atomics MQ-9 Reaper. UAV estadounidense militar diseñado para misiones de vigilancia a grandes altitudes. (b) UAV de transporte desarrollado por Connect Robotics. Figura 1.1: Ejemplos de UAVs. 11 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 1.2: Kettering Bug desarrollado durante la Primera Guerra Mundial. Figura 1.3: UAV militar AAI RQ-2 Pioneer. Estuvo en servicio en los años 1986-2007. 12 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Hoy en día existen numerosas aplicaciones para estas máquinas, que vienen en diferentes formas y tamaños. Cabe destacar que el empleo civil se desarrolla muy rápido ya que, las posibilidades son innumerables. Se han creado muchas investigaciones, la mayoría de las cuales se plantearon hace tiempo pero estaban en desuso. A continuación se van a enumerar algunas de las aplicaciones más importantes (ver Figura 1.4 como ejemplo) que se usan por todo el mundo: Búsqueda y rescate : los drones pueden usarse para tener contacto visual en todo momento con las personas que se encuentran en una situación peligrosa e, incluso, traer objetos necesarios para mantener a alguien con vida con una velocidad muy elevada. Por ejemplo: ayuda al rescate de personas en el mar o que están dentro de un edicio incendiado. Seguridad y vigilancia : los UAVs resultan ser ideales para supervisión de zonas de difícil acceso y seguimiento de objetivos móviles, como, por ejemplo los drones de vigilancia del parque natural Doñana. Inspecciones : la mayoría de las infraestructuras de difícil acceso pueden ser inspeccionadas desde aire y a una distancia mínima gracias a los drones. El mantenimiento de las turbinas eólicas y las líneas eléctricas es un buen ejemplo de la mejora de la seguridad gracias a los drones. Ciencia e investigación : el uso de los drones ha abierto numerosas posibilidades de observar la naturaleza sin perturbarla o alcanzar sitios de difícil acceso. Cartografía : los UAVs también se utilizan para crear mapas de alta resolución de paisajes o edicios. Sobre todo destaca su uso para crear mapas 3D. Grabación de vídeos : vista aérea crea nuevas perspectivas en cinematografía y grabaciones a distancia. Transporte : como cualquier otro vehículo, los drones pueden transportar objetos y, se cree que en un futuro, serán lo sucientemente seguros, como para transportar personas. En la actualidad, debido a su gran popularidad, los drones están siendo el objetivo de numerosas investigaciones de desarrollo y siguen apareciendo innumerables aplicaciones al ver que estos pueden ofrecer un servicio muy versátil, viable y, sobre todo, por un precio razonable. El objetivo principal de esta tecnología es automatizar los procesos, minimizar el trabajo humano y, sobre todo, aumentar la seguridad, ya que, la mayoría de los fallos o de accidentes se deben al error humano. Al automatizar los procesos también se mejora la rapidez y la precisión de los aparatos y se reducen los costes operativos. 13 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Dron de rescate RTS. (b) DJI MAVIC PRO. Realiza fotografías y grabaciones profesionales. (c) UAV realizando operaciones de inspección y mantenimiento en las turbinas eólicas. Figura 1.4: Algunos ejemplos de usos variados de UAVs. 14 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov 1.1.1. Tipos de algoritmos existentes A fecha de hoy, existen numerosos algoritmos, que resuelven el problema de encontrar un camino hacia el objetivo, teniendo en cuenta diferentes enfoques y la tecnología disponible. A continuación, se van a describir algunos de los algoritmos mas usados: 1.1.1.1. Bug algorithm Estos algoritmos fueron unos de los primeros en implementarse y son de los más sencillos que existen (ver Figura 1.5). Bug algorithm [15] está creado para los los entornos 2D en los que el vehículo tiene un sensor de contacto o de un rango nito. El comportamiento básico de estos algoritmos se puede resumirse en 2 actividades: Movimiento hacia el objetivo. Seguimiento de las fronteras de los obstáculos. Como ya se ha dicho antes, destaca por su sencillez pero, al mismo tiempo, esto conlleva a que las soluciones no sean las óptimas. Figura 1.5: Ejemplo de camino seguido por Bug. 15 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov 1.1.1.2. Campos potenciales Los algoritmos basados en los campos potenciales [10], utilizan las funciones diferenciables, reales, cuyo valor es la energía potencial articial, y el gradiente de dicha función es la fuerza que afectaría al vehículo. La función potencial se dene normalmente como la suma de un potencial de atracción hacia el objetivo y un potencial de repulsión de los obstáculos, como se indica en la Figura 1.6. Estos algoritmos se usan en aplicaciones donde se requiere bajo coste computacional. Sin embargo, su mayor desventaja consiste en la existencia de los mínimos locales donde el programa puede quedarse atrapado. Figura 1.6: Ejemplo de campo potencial con obstáculos. 1.1.1.3. Algoritmos basados en grafos/ Roadmaps Los algoritmos basados en grafos, o también llamados Roadmaps, construyen una red de rutas conectados entre sí. Antes de empezar describiendo los algoritmos, se va a explicar brevemente lo que es un grafo: un grafo es un conjunto de nodos unidos por los enlaces llamados arcos, que posibilitan representar relaciones entre los dichos nodos. Un ejemplo claro de esto está representado en la Figura 1.7 16 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 1.7: Ejemplo de un grafo básico con costes indicados. Al ser bastante reciente el estudio de búsqueda de caminos de forma autónoma, no existe una clara diferenciación entre distintos tipos de algoritmos, por lo que en este trabajo se propone a diferenciar dos grupos: grafos jos o constantes, y grafos probabilísticos. Se va a denominar como grafos jos los que obtienen toda la información necesaria para su construcción exclusivamente del mapa dado (En este trabajo solo se van a contemplar los espacios estáticos). Es decir, son independientes del camino que elija el algoritmo y se mantienen igual. Algunas de las técnicas de obtención más conocidas de este tipo de grafos son: Grafos de visibilidad : se construyen conectando los vértices de los obstáculos presentes en el mapa. Eso genera rutas directas y cortas, pero suelen tener un coste computacional muy elevado [18]. Ver Figura 1.8. Diagramas de Voronoi : es una alternativa que pretende que el camino este lo más alejado posible de los obstáculos. Se consigue dividiendo el espacio con lineas equidistantes de los obstáculos. Este método es muy efectivo si los obstáculos son puntuales. Sin embargo, no existen modi- caciones elementales para detectar obstáculos complejos, por lo que su eciencia baja notablemente si estos son polígonos complicados e irregulares [1]. Ver Figura 1.9. Descomposición en celdas : se basa en un simple principio: dividir un espacio complejo en fragmentos sencillos y pequeños. Habitualmente, la zona de trabajo se divide en regiones cuadradas, trapezoidales o triangulares, de tal forma que estos fragmentos se puedan denir con un sistema binario, dependiendo de si son accesibles o no. Esta descomposición permite tratar el mapa como una matriz, que es muy apropiado para el uso computacional. Figura 1.10. Una vez construido el grafo, se utilizan los algoritmos de búsqueda de ruta para encontrar la solución deseada. Los algoritmos más usados para los espa- 17 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 1.8: Grafos de visibilidad. Figura 1.9: Diagramas de Voronoi. Figura 1.10: Descomposición en celdas. 18 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov cios estáticos son Dijkstra [5], A* [7] y sus modicaciones como θ∗ [4], y otros como ANYA [6]. Algunos de ellos, en concreto, A* y θ∗ se van a explicar más detenidamente en el siguiente capítulo. Los planeadores probabilísticos, también llamados SBP (Sampling-Based Planning) [14], a diferencia de los anteriores, se basan en generación aleatoria de los estados para construir el camino. Es decir, su función es la de aproximar la conectividad del espacio mediante una estructura de grafos, muestreando las zonas de este espacio. La aleatoriedad de este método permite resolver problemas muy complejos en relativamente poco tiempo, ya que el tiempo empleado en encontrar la solución no tiene relación directa con la complejidad del mapa. La desventaja del enfoque probabilístico es que las soluciones obtenidas no son óptimas en los casos reales. Además, el muestreo aleatorio no garantiza encontrar la solución, si es que existe. Aunque, teóricamente, si el programa se deja funcionando durante un tiempo innito, sí obtiene una solución y la optimiza. Por lo tanto, este tipo de planicación no es completamente exhaustivo, donde por exhaustivo se entiende que tiene que resolver el problema y hacerlo en un tiempo nito. Por esta razón, para este tipo de planicadores, se admite una noción de exhaustividad más débil, denominada exhaustividad probabilística, lo que signica que la probabilidad de encontrar una solución converge a uno a medida que pasa más tiempo. La velocidad de esta convergencia es lo que indica la ecacia del planicador. Los planeadores probabilísticos comparten entre sí los siguientes elementos: Muestreo : el procedimiento que selecciona un punto nuevo al azar y lo agrega al grafo o arbol ya existente. El punto puede estar en el espacio inaccesible, lo que permite explorar más opciones que otros métodos. Dependiendo del tipo del planicador este punto puede ser válido o no. El generador de estados tiene que tener una cierta uniformidad para poder explorar todo el espacio, aunque se le puede introducir una cierta parcialidad. Métrica : dene la distancia o el esfuerzo que hay entre dos estados qa y qb . Es importante tenerlo en cuenta para que la solución sea la de menor coste posible. Vecino más cercano : busca y selecciona el nodo más cercano al punto propuesto por el muestreo. Selección de predecesor : esta operación selecciona uno o varios nodos existentes para conectarse con el el nodo recién generado. El algoritmo RRT, por ejemplo, selecciona el nodo más cercano, mientras que PRM conecta varios vecinos a la vez. Planicación local : dados dos nodos qa y qb , esta operación intenta conectarlos de forma adecuada. Aquí pueden intervenir las restricciones cinemáticas o dinámicas del modelo, cambiando el resultado. 19 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 2.3: Descomposición de un obstáculo en celdas para A* y θ∗ . En la Figura 2.3 se ve como se descompone un obstáculo circular y lo marca con celdas que indican una zona inaccesible. 26 Capítulo 3 Algoritmos de planicación de caminos estudiados Como ya se ha visto en la introducción, existen numerosos métodos para planicar el movimiento de una máquina autónoma. Aquí se van a comentar con más profundidad los algoritmos más usados para los vehículos aéreos. En concreto, se van a explicar algunos de los algoritmos de búsqueda de grafos y varios algoritmos probabilísticos que se expondrán continuación. Siendo el objetivo de este trabajo, comparar el comportamiento de diferentes algoritmos, lo primero que hay que hacer es denir los criterios de la evaluación. Se van a tener en cuenta los siguientes parámetros: El tiempo de resolución: es una de las características más importantes de los algoritmos, ya que, muchas veces determina su viabilidad para diferentes aplicaciones. Esto también engloba el coste computacional y el uso de la memoria, que están estrechamente relacionados con el tiempo dedicado. La calidad del camino encontrado: esta característica indica si la ruta encontrada se parece a una real, que elegiría una persona o no. También se tiene en cuenta el coste del camino encontrado y cuánto de óptimo es. Por coste se entiende una función que calcula el esfuerzo que tiene que hacer el UAV para llegar a un punto determinado, y puede ser cualquier parámetro: coste energético, consumo de combustible, etc. En este caso, por simplicidad, el coste va a ser equivalente a la distancia que recorre el dron. Por tanto va a ser una función lineal. 3.1. Algoritmos de búsqueda (Search algorithms) 3.1.1. Algoritmo A* Este algoritmo de búsqueda de camino es uno de los más usados debido a su alto rendimiento, fácil implementación y robustez. A* [7] es una variación 27 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Funcionamiento de A* y dos heurísticas diferentes, aplicables. (b) Ejemplo del resultado nal Figura 3.1: Ejemplo de A* del Dijkstra [5] que incluye una tendencia hacia la meta, lo que ayuda a reducir los tiempos de computación y ahorra la exploración innecesaria. Básicamente, el algoritmo explora todos los posibles recorridos desde el inicio hasta la meta y encuentra el menos costoso de todos. Se aplica, sobre todo, en mapas de carreteras ya construidos o espacios divididos en celdas. En este caso, al tener obstáculos denidos como polígonos, el algoritmo necesita una función de preprocesamiento del mapa, para poder crear la cuadrícula sobre la que va a trabajar. Una vez creada la cuadrícula, esta actúa como un grafo, donde el algoritmo tiene que encontrar la ruta desde el inicio hasta la meta. En cada iteración del bucle principal, A* determina qué nodo quiere expandir para seguir construyendo la senda. Para hacerlo, necesita estimar el coste (peso) del nodo actual. En concreto, el algoritmo utiliza la siguiente función f(s) = g(s) + h(s) donde s es el último nodo en el camino g(s) es el coste del recorrido desde el inicio hasta el nodo s , y h(s) es la heurística que estima el coste del camino mas corto desde el nodo n hasta el nal. La idea es encontrar, entre todos las sendas posibles, la que minimiza esta función, habiendo llegado a este nodo. Es decir, estando en el nodo s , el programa estima si este podría ser uno de los nodos del camino más corto. Para poder hacerlo, la heurística ha de cumplir el criterio de admisibilidad. Por admisibilidad se entiende que el valor h(s) nunca puede sobrestimar el coste real de de llegar al objetivo hr(s) , asimismo asegurándose de que el trayecto encontrado es siempre el menos costoso. Hay varias formas de estimar el valor de h(s) , pero en este caso se ha decidido elegir la distancia directa entre el nodo y la meta, también llamada distancia Euclidiana. En principio, todos los nodos disponibles para la exploración están marcados como abiertos. A medida que va avanzando, el programa marca los nodos ya 28 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov explorados o no alcanzables como cerrados. Teniendo los datos de los nodos abiertos/cerrados se consigue que el algoritmo no explore el mismo más de una vez, lo que aumenta su eciencia. El algoritmo está representado en la Figura 3.1a y funciona de la siguiente forma: 1. El programa busca un nodo sucesor, abierto y adyacente a los ya explorados, y que tenga el mínimo valor de f(s) . 2. Una vez encontrado el nodo, lo marca como cerrado y calcula los costes estimados f(s0) de los nodos cercanos. En este caso, al tratarse de un mapa dividido en celdas, un nodo puede tener como máximo 8 vecinos que lo rodean. 3. Si el nodo sucesor es el objetivo, la exploración se para. Si no lo es, vuelve al paso 1 Si hay una solución posible, el programa siempre la encontrará, de lo contrario, se parará cuando no queden más nodos abiertos para la exploración. Este planicador se describe con más detalle en Algoritmo 1. Dentro del algoritmo aparecen las siguientes funciones principales: Main : el bucle principal que explora los nodos abiertos, sigue funcionando hasta que no encuentre la solución o hasta que todos los nodos no estén explorados. UpdateVertex: función que se encuentra dentro del bucle principal y se encarga de dar el paso al siguiente nodo de coste mínimo 3.1.2. Algoritmo θ∗ El algoritmo A* es muy eciente, sin embargo, al estar unicamente construidos sobre los bordes de la cuadrícula, los caminos encontrados suelen tener un aspecto poco realista y no ser óptimos del todo. De la necesidad de mejorar dicho aspecto y diminuir el coste, nace la idea del algoritmo θ∗ [4]. Esencialmente se trata de quitar la limitación de solo poder construir la ruta siguiendo tan solo 8 direcciones, características del algoritmo A*. Esto se consigue combinando el algoritmo A* con los grafos de visibilidad, lo que permite crear caminos en cualquier dirección. La principal diferencia entre θ∗ y A* es que el nodo padre del nodo sucesor tiene que estar a su lado usando A*, mientras que con θ∗ el nodo padre puede ser cualquiera. El algoritmo θ∗ básico es casi idéntico al A*, con la excepción de que cuando este actualiza el valor de g(s) y el padre del nodo inexplorado s0 , vecino cercano del nodo s , considera dos caminos diferentes: Camino 1: Este camino es el mismo que toma el algoritmo A*, es decir, al camino ya existente del inicio hasta el nodo s , le añade la linea que une s con s0 . 29 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Algoritmo 1: Pseudocódigo de A*. 1 begin Main() 2 g(sstart) := 0 ; 3 parent(sstart) := (sstart) ; 4 open := ∅ ; 5 open.Insert(sstart, g(sstart) + h(sstart)) ; 6 closed := ∅ ; 7 while open 6=∅ do 8 s:= open.Pop() ; 9 if s:= sgoal then 10 return "path found" ; 11 end 12 closed := closed ∪ {s} ; 13 [UpdateBounds( s )] Solo se usa en θ∗ ; 14 for s0∈succ(s) do 15 if s0/∈closed then 16 if s0/∈open then 17 g(s0) := ∞ ; 18 parent(s0) := NULL ; 19 end 20 UpdateVertex( s, s0 ) ; 21 end 22 end 23 end 24 end 25 begin UpdateVertex( s, s0 ) 26 if g(s) + c(s, s0)< g(s0) then 27 g(s0) := g(s) + c(s, s0) ; 28 parent (s0) := s ; 29 if s0∈open then 30 open.Remove(s') ; 31 end 32 open.Insert (s0, g(s0) + h(s0)) ; 33 end 34 end 30 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Camino 2: θ∗ considera también otro camino que va desde el padre del vértice s , directamente hasta s0 en línea recta. Si el camino esta libre de obstáculos, esta opción siempre será menos costosa que la anterior por la desigualdad de triángulos. El programa comprueba si es posible avanzar por el Camino 2, si no, se toma el Camino 1, lo que asegura que siempre el algoritmo siempre encuentre la solución, si es que la hay. En la Figura 3.2 se puede ver la diferencia entre los caminos encontrados de θ∗ y A*. Es importante señalar que la comprobación de si el camino es libre de obstáculos no es tan trivial. La solución que utiliza θ∗ básico es bastante rápida, ya que utiliza el algoritmo de Bresenham [3]. Este algoritmo consiste en examinar las celdas por donde pasaría el camino y ver, una por una, si alguna de esas celdas esta obstaculizada. Si no se encuentra con ningún obstáculo, el camino se considerará como válido. En este trabajo en concreto, se ha programado AP- θ∗ [4], que es otra modicación del algoritmo que usa nociones de visibilidad. La visibilidad indica si se ve el nodo deseado s0 desde el nodo predecesor de s . Si hay un obstáculo en medio, este impide que haya una linea de visión entre ellos, lo que signicaría que no hay camino directo. En la Figura 3.3 se muestra como un obstáculo bloquea el campo de visión del nodo padre. En otras palabras, los nodos dentro del cono no serán capaces de conectarse directamente al nodo seleccionado. Teniendo esto en mente, se ha programado el algoritmo line-of-sight que utiliza ángulos θ1 y θ2 , que son los ángulos que forma la recta entre sparent y s , con los vértices de los obstáculos más cercanos, para para denir el campo de visión. El algoritmo implementado no sigue exactamente el procedimiento teórico. En vez de usar unicamente los ángulos, también incluye comprobación de si algún punto del obstáculo se encuentra dentro del triángulo formado por sparent , s y s0 . El procedimiento viene explicado con detalle en la Figura 3.4. Dicho algoritmo se describe con más detalle en el pseudocódigo teórico que se muestra en los Algoritmos 2 y 3. El algoritmo principal sigue siendo igual a A* pero las funciones dentro de este cambian: UpdateVertex : ahora considera dos caminos posibles: el que tomaría A* y el que actualiza sparent de s0 , para acortar el camino. UpdateBounds: calcula el cono de visión del nodo predecesor. Lo consigue buscando los ángulos límite entre los que el camino estaría libre de obstáculos. Si los nodos s0 están dentro de estos límites, signica que están en su campo de visión. 31 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 3.2: θ∗ comparado con A*. Figura 3.3: Visibilidad de un nodo. El área roja se encuentra fuera de su campo de visión. 32 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) El algoritmo comprueba los ángulos del cono de visión necesario para conectar todos los nodos s0 al nodo predecesor. (b) Se forman dos triángulos, con la máxima apertura posible, que comprueban si hay algún punto del obstáculo dentro del camino. Si resulta que el triángulo se corta con un obstáculo, s0 que lo forma no tiene visibilidad del padre. (c) Se coge el siguiente triángulo que forma el mayor ángulo de θ posible y se vuelve a hacer la comprobación. Si no colisiona, todos los s0 que se encuentren dentro de θ tienen visibilidad sobre sparent . (d) Aquí se muestran los caminos nales. Figura 3.4: Metodología de detección del campo de visión, utilizado por θ∗ implementado. 33 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Algoritmo 2: Algoritmo AP- θ∗ . Primera parte. 1 begin UpdateVertex( s, s0 ) 2 if s6=sstart AND lb(s)≤Θ(s, parent(s), s0)≤ub(s) then 3 /* Path 2 */ ; 4 if g(parent(s)) + c(parent(s), s0)< g(s0) then 5 g(s0) := g(s) + c(s, s0) ; 6 parent(s0) := parent(s) ; 7 if s0∈open then 8 open.Remove( s0 ) ; 9 end 10 open.Insert (s0, g(s0) + h(s0)) ; 11 end 12 else 13 /* Path 1 */ ; 14 if g(s) + c(s, s0)< g(s0) then 15 g(s0) := g(s) + c(s, s0) ; 16 parent (s0) := s ; 17 if s0∈open then 18 open.Remove(s') ; 19 end 20 open.Insert (s0, g(s0) + h(s0)) ; 21 end 22 end 23 end 34 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Algoritmo 3: Algoritmo AP- θ∗ . Segunda parte. 1 begin UpdateBounds( s ) 2 lb(s) := −∞ ; ub(s) := ∞ ; 3 if s6=sstart then 4 foreach blocked cell b adjacent to s do 5 if ∀s0∈corners(b) : parent(s) = s0 OR Θ(s, parent(s), s0)<0 OR (Θ(s, parent(s), s0)) = 0 AND c(parent(s), s0)≤c(parent(s), s)) then 6 lb(s)=0 ; 7 end 8 if ∀s0∈corners(b) : parent(s) = s0 OR Θ(s, parent(s), s0)>0 OR (Θ(s, parent(s), s0)=0 AND c(parent(s), s0)≤c(parent(s), s)) then 9 ub(s)=0 ; 10 end 11 end 12 foreach s0∈nghbrsvis(s) do 13 if s0∈closed AND parent(s) = parent(s0) AND s06=sstart then 14 if lb(s0) + Θ(s, parent(s), s0)≤0 then 15 lb(s) := max(lb(s), lb(s0) + Θ(s, parent(s), s0)) ; 16 end 17 if ub(s0) + Θ(s, parent(s), s0)≥0 then 18 ub(s) := min(ub(s), ub(s0) + Θ(s, parent(s), s0)) ; 19 end 20 end 21 if c(parent(s), s0)< c(parent(s), s)) AND parent(s)6=s0 AND (s0/∈closed OR parent(s)6=parent(s0)) then 22 if Θ(s, parent(s), s0)<0 then 23 lb(s) := max(lb(s),Θ(s, parent(s), s0)) ; 24 end 25 if Θ(s, parent(s), s0)>0 then 26 ub(s) := max(ub(s),Θ(s, parent(s), s0)) ; 27 end 28 end 29 end 30 end 31 end 35 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov algoritmo, haciendo que los dos arboles conecten al tener algunos de los nodos en su campo de visión. Esta alteración debería permitir bajar bastante el tiempo de computación a expensas del coste de camino, que podría ser lejos del óptimo. En las Figuras 3.8 y 3.9 se puede observar el comportamiento de este método, mientras que el pseudocódigo viene descrito en el Algoritmo 6. Las funciones nuevas dentro de este algoritmo son las siguientes: Connect: esta función conecta directamente xnearest con xrand . ExtendUntilObstacle: si se da el caso que la linea obtenida gracias a Connect está obstaculizada, esta función hace que se pare justo delante del obstáculo sin tocarlo. Este nuevo punto se tomaría por xnew . Algoritmo 6: RRT-Connect. 1 begin RRT-Connect Data: Terrain map M , start conguration ps , end conguration pe 2 V← {xinit};E← ∅ ; 3 while The end node pe , is not connected to the tree: pe/∈V do 4 xrand ← SampleFree i ; 5 xnearest ← Nearest( G= (V, E), xrand ) ; 6 xnew ← Connect( xnearest, xrand ) ; 7 if Obstaclefree( xnearest, xnew ) then 8 V←V∪ {xnew};E←E∪ {xnearest, xnew} ; 9 else 10 xnew ← extendUntilObstacle ( xnearest ) 11 end 12 end 13 return G= (V, E) ; 14 end 3.3. Modicaciones y mejoras Los algoritmos descritos anteriormente están presentados en su forma más general, lo que signica, que están en su forma más básica para poder ser adaptados a las aplicaciones posteriores. A continuación se van a explicar algunas modicaciones de lo algoritmos que pueden tener un gran interés para las aplicaciones reales. 3.3.1. Introducción del Sesgo/Bias El tiempo de resolución de los algoritmos basados en RRT depende totalmente del azar de los puntos generados, lo que hace imposible predecir la duración de la ejecución. Por ello, es interesante introducir un sesgo, o también llamado 42 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) El algoritmo empieza en una rama, escogiendo un punto al azar. Si este punto no está obstaculizado se convierte en el nodo nuevo. (b) Se comprueba si es visible algún punto de otro árbol desde el primero. (c) Se intercambian los árboles, y el bucle empieza de nuevo. Se escoge un punto al azar. (d) Si el punto no esta accesible, el nodo nuevo se pone en la misma línea justo al tocar el obstáculo. SE comprueba si tiene visibilidad sobre el otro árbol (e) Se vuelven a intercambiar los árboles. El azul vuelve a poner un punto y comprueba la visibilidad. (f) Si el otro árbol puede conectarse directamente con el nuevo punto, se crea la unión y se traza el camino encontrado. Figura 3.8: Procedimiento de búsqueda de RRT-Connect. 43 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 3.9: RRT-Connect. En la imagen se observan dos árboles: uno cían con la raíz en el punto verde y otro azul con la raíz en el punto rojo. Ambos están conectados por un camino nal verde. Se puede intuir la rápida expansión de los árboles ya que apenas hay nodos explorados en el mapa. También se ve que el camino encontrado está lejos de ser óptimo. 44 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Bias, dentro del algoritmo principal que marca una tendencia hacia la meta, lo que ayudaría a reducir el tiempo de búsqueda en muchos casos. En este trabajo, para todos los algoritmos RRT, se ha introducido una tendencia en la que un cierto por ciento de los puntos de aleatorios se sustituye por xgoal . Esto hace posible una convergencia más rápida hacia el resultado, sobre todo si se tiene una vista directa del objetivo desde el árbol. Al variar el porcentaje, varía la rapidez de la convergencia, aunque esto puede dar lugar a la aparición de los mínimos locales, igual que en los métodos de campos potenciales. Sobre todo, es peligroso aumentar el sesgo en entornos muy complicados como, por ejemplo, un laberinto. En un laberinto, el porcentaje de los puntos sesgados es desperdiciado, ya que, se encuentra con muchas barreras que impiden su funcionamiento. 3.3.2. Dimensiones del UAV Es interesante también considerar el tamaño del UAV en los entornos de dimensiones reducidas, para poder simular las situaciones reales. Una forma de hacerlo es modicando los obstáculos: ensanchando su tamaño o poniendo un margen de seguridad alrededor de estos. Este método es bastante rápido y fácil de utilizar, pero aumentando el tamaño de los obstáculos puede conllevar a la eliminación de posibles soluciones. La otra forma consiste en simular el movimiento del UAV completo, teniendo en cuenta sus dimensiones reales y no solo siguiendo su centro de gravedad teórico. Al estar en un espacio 2D , solo se necesitan dos dimensiones. En este trabajo en particular, los entornos pequeños están contenidos en los planos verticales, por lo que la forma del vehículo se ha asimilado a un rectángulo de dimensiones 90 ×20cm , correspondientes a la longitud y la altura respectivamente. Suponiendo que los trabajos realizados en espacios reducidos son de precisión, resulta razonable proponer la siguiente hipótesis: Los trabajos de precisión requieren movimientos lentos, lo que conlleva a ángulos de inclinación y aceleraciones pequeños, por tanto, se puede considerar que el UAV siempre se mantiene paralelo al suelo. Teniendo en cuenta la hipótesis anterior, es posible simular el comportamiento de un dron, cuyas dimensiones no son despreciables, sin implicarse en la dinámica ni la cinemática del problema. Esto permite plantear un problema puramente geométrico, como se representa en la Figura 3.10. La función utilizada para ello, Hull, intenta simplicar al máximo la geometría del vehículo durante en movimiento. Supongamos que tenemos un segmento cualquiera por el que se mueve el UAV. Para no tener que hacer múltiples comprobaciones a lo largo de todo el segmento que une dos nodos, se asemeja el paso entre ellos a una forma geométrica, en concreto, un polígono. Esto se puede ver en la Figura 3.11. 45 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 3.10: Trayectoria del UAV teniendo en cuenta sus dimensiones. (a) Comprobación con estados intermedios. Como se ve, la abilidad de este método depende de la cantidad de puntos intermedios que hay en el segmento. Más puntos consumen más tiempo (b) Comprobación con un único polígono creado por Hull. Este método no requiere puntos para su abilidad y es bastante preciso. Figura 3.11: Comparación de métodos de comprobación de colisiones. 46 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 3.12: Ejempo RRT Smooth Path. El camino verde es el original y el rojo se consigue aplicando esta función. 3.3.3. RRT Smooth Path Como una posible mejora para los algoritmos de tipo RRT, se ha incluido un suavizado de camino, para optimizar el coste de los resultados e intentar mejorar el aspecto de estas. Esta modicación posibilita acortar la ruta de un camino ya encontrado, saltando los nodos innecesarios. Su funcionamiento es similar al algoritmo θ∗ , donde el algoritmo, en vez unir de los nodos más cercanos, intenta unir los que están en su campo de visión. El pseudocódigo utilizado puede verse el ejemplo puesto en la práctica en la Figura 3.12 3.3.4. RRT*2 Como alternativa al algoritmo RRT*, en este apartado se propone otra modicación de este que se ha llamado RRT*2. En si, el programa cumple la misma función que RRT*: intenta construir el árbol quitando conexiones redundantes. La principal diferencia consiste en que a la hora de reconectar, se toma un enfoque diferente. El procedimiento original consiste en reconectar los nodos vecinos al nuevo, de forma que el coste disminuya si se cambia el predecesor. En cambio, esta modicación comprueba si es posible reconectar toda la rama del árbol que conduce al nodo xnear para disminuir el coste de todos los nodos sucesores de la rama. Esto permite optimizar más los costes en los arboles muy rizados. En las Figuras 3.13 y 3.14 se puede ver la explicación gráca y la comparación 47 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov de los dos funcionamientos: se consigue una disminución de costes considerable aplicando este algoritmo. Para comprender con mas detalle su funcionamiento, a continuación se va a explicar la nueva función que sustituye a Rewire de RRT*, llamada Chain. La función Chain reconecta los nodos de la misma forma, sin embargo la principal diferencia esta en la eliminación de enlaces. Una vez reconectado el nodo, se crea un círculo cerrado de nodos: una cadena, donde los enlaces son sus eslabones (Figura 3.15). La cadena empieza por el punto que tiene el menor coste acumulado Xc . Después se busca el eslabón más cargado, es decir, donde se alcanza el mayor coste relativo al nodo del comienzo de la cadena Xc , avanzando por los dos lados como se indica en la Figura 3.16. A continuación se rompe el enlace indicado y se reestructura la rama que empieza a partir de Xc . De esta forma, se consigue minimizar los costes en toda la rama cuyo predecesor es Xc , mientras que con RRT* solo se ven afectados los nodos xnear y sus sucesores. 48 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Suponiendo que se tiene este árbol, donde la distancia entre los nodos es 1, y que el nuevo nodo xnew tiene varios vecinos cercanos. (b) Los dos algoritmos buscan si los vecinos xnear se pueden reconectar de tal forma que el nuevo camino sea menos costoso. Figura 3.13: Comparación de funcionamiento de RRT* y RRT*2. Comparten el mismo comienzo. 49 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) RRT* reconecta el nodo 12, eliminando la conexión con su predecesor, si esto minimiza el coste. (b) RRT*2 reestructura la rama y desconecta otro arco, de manera que se minimiza los costes en toda la parte afectada. (c) RRT* recalcula los costes de los nodos sucesores. (d) RRT*2 reestructura toda la rama y recalcula los costes nuevos. Este proceso afecta a todos los nuevos sucesores de xnew. Figura 3.14: Comparación de funcionamiento de RRT* y RRT*2. Diferencias. 50 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Figura 3.15: Cadena cerrada. El nodo de comienzo en este caso es el 2, que coincide xnearest . Figura 3.16: Cálculo de costes relativos siguiendo la cadena. Eslabón más costoso es eliminado, minimizando los costes en toda la rama. 51 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Mapa 1. (b) Mapa 2. (c) Mapa 3. (d) Mapa 4. Figura 4.4: Costes obtenidos después de 50 pruebas. 58 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov Mapa Mín. teórico A* θ∗ RRT RRT* RRT-Connect 1 451.12 499.41 477.86 559.2 555.74 616.99 2 677.92 729.12 684.76 998.18 948.77 1266.2 3 544.83 579.41 557.20 772.38 727.42 850.67 4 568.9 600.83 577.36 710.83 691.44 848.44 Como lo muestra la tabla, ningún algoritmo es totalmente óptimo en cuanto al coste. Los resultados más bajos han sido obtenidos por θ∗ , cuyos costes son, como máximo, superan en 5% los costes teóricos. Le sigue A*, con costes más altos debido a la limitación de poder expandirse en solo 8 direcciones diferentes. Los planeadores probabilísticos, como cabía de esperar, están lejos del camino óptimo, pero sigue habiendo una notable diferencia entre ellos. RRT* ha logrado los mejores costes entre ellos, siendo aproximadamente un 5% más e- ciente que RRT. Esta ventaja no es muy grande en comparación con la que ofrecen los planicadores deterministas, pero sigue siendo importante. Una propiedad importante de este algoritmo es que si se deja funcionando más tiempo, el coste obtenido se va acercando al óptimo, ya que el árbol se va reestructurando y acortando la ruta. En cambio, RRT-Connect ha obtenido los peores resultados, ya que sacrica algunas de las características del RRT, que disminuyen el coste, por la rapidez. Además sus resultados son bastante inconsistentes, por lo que no se recomienda su uso en trabajos que requieren precisión. Es interesante también comprobar cómo el algoritmo RRT* optimiza las trayectorias con el tiempo. En la Figura 4.5, se muestra como el algoritmo se va optimizando a medida que pasa el tiempo, hasta llegar casi al óptimo. Después del intervalo de 2 segundos, el árbol, teniendo pocos nodos, tiene un aspecto muy parecido a RRT, sin embargo, al pasar 20 segundos, va tomando una estructura característica y, en el último intervalo de 200 segundos, el árbol se extiende como si fuera un campo potencial. El camino encontrado, después de tanto tiempo, es tan solo 1% mayor que el óptimo, e iría reduciendo la diferencia, hasta alcanzar el mínimo teórico en un tiempo innito. En la siguiente tabla se exponen los costes obtenidos tras un tiempo de 100 segundos en comparación con θ∗ , cuyas soluciones suelen estar más cerca del óptimo. Mapa Mín. teórico θ∗ RRT* 1 451.12 477.86 455.35 2 677.92 684.76 689.77 3 544.83 557.20 558.80 4 568.9 577.36 594.83 Lo primero que destaca a la vista, es la diferencia que existe entre los dos algoritmos en el Mapa 1. Al ser un obstáculo circular, la división en celdas rectangulares pierde su ecacia. Por ello, el coste de θ∗ es mucho mayor, al no ser capaz de adaptarse por completo a la geometría del problema. En los Mapas 2 y 3 los costes son muy parecidos y, en el 4, RRT* se ralentiza mucho por la gran cantidad de obstáculos, por lo que obtiene un resultado mucho peor. Estos algoritmos están especializados en encontrar caminos cortos manteniendo tiempos razonablemente cortos. Después de analizar a los dos, se ha 59 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Tiempo: 2 segundos. Coste nal: 1022 (b) Tiempo: 20 segundos. Coste nal: 737 (c) Tiempo: 2 segundos. Coste nal: 683 Figura 4.5: Muestra de caminos obtenidos por RRT* en el Mapa 2, durante intervalos diferentes del tiempo. observado que RRT*, siendo un planicador probabilístico, está mejor adaptado a los entornos con obstáculos de geometría circular, irregular o cualquier otra, que resulte más difícil a la hora de descomponer en celdas. En cambio, θ∗ obtiene ventaja en los entornos con muchos obstáculos. 4.2. Inuencia del Sesgo/Bias En este apartado se va a estudiar la inuencia que tiene el sesgo sobre los resultados. Hay que tener en cuenta de que solo se aplica a RRT y RRT*, y el objetivo principal del Bias es mejorar el rendimiento de los programas. Por ello, se ha decidido añadir dos niveles de sesgo de 1% y 5%, para ver cuál obtiene mejores resultados. Cabe recordar que un porcentaje demasiado alto puede conllevar a la aparición del mismo efecto que crean los mínimos locales, así pues, por lo general, suelen estar por debajo del 10%. También es importante tener en cuenta la geometría del mapa, que puede facilitar o dicultar este proceso, dependiendo de la colocación de obstáculos. En las Figuras 4.6 y 4.7 se ven las comparaciones de tiempos y costes para todos los mapas, para los dos algoritmos Se observa que el tiempo de resolución disminuye notablemente al aumentar el sesgo, incluso en los mapas donde es posible que se originen los mínimos locales. La variación se nota, sobre todo, con el sesgo del 5% , cuyo efecto puede reducir el tiempo total en unos 50%. Esto es debido al carácter aleatorio del RRT, que explora todo el espacio disponible rápidamente pero algunas veces no consigue llegar a un punto determinado, hasta que el nuevo punto se elija justo en esa zona, que podría ser el objetivo. Teniendo una ayuda del sesgo, se elimina esa posibilidad, ya que si el árbol está cerca del nal, unas iteraciones son sucientes para que lo encuentre. También se ha incluido el coste del camino en el estudio del sesgo. Al observar el coste, se intuye una leve mejora ya que la tendencia introducida ayuda a dirigir el camino hacia la meta pero no hay una diferencia tan apreciable, por lo que se puede suponer que el coste es invariable. 60 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Mapa 1 (b) Mapa 2 (c) Mapa 3 (d) Mapa 4 Figura 4.6: Inuencia del Bias en el tiempo de resolución. RRT. 61 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Mapa 1 (b) Mapa 2 (c) Mapa 3 (d) Mapa 4 Figura 4.7: Inuencia del Bias en el coste de resolución. RRT. 62 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov La inuencia del Bias sobre los resultados del algoritmo RRT*es prácticamente idéntica a la del RRT, por lo que su estudio detallado no es de gran interés. Para el resto de los apartados se va a mantener el Bias de 5%, el que ha obtenido los mejores tiempos. 4.3. Inuencia de la dimensión de pasos D Una vez estudiado el comportamiento general de los de los algoritmos, se va a ver la inuencia del tamaño de pasos D en los resultados. Se han hecho pruebas del comportamiento en dos algoritmos: A* y RRT en diferentes mapas, pero en este apartado se muestran los resultados obtenidos del Mapa 2, que resume elmente el comportamiento en el resto de Mapas. Los demás algoritmos, al ser basados en estos dos, obtendrían unos resultados muy parecidos. Al aumentar el parámetro D , la exploración se hace más rápida pero menos exhaustiva. En las Figuras 4.8 y 4.9 se observa la tendencia general de los tiempos y de los costes obtenidos: El tiempo decrece de forma exponencial a medida que aumenta D . También disminuye la dispersión de los resultados, es decir, tienden a ser más uniformes. En el caso de A* la dispersión se debe a que el ordenador no tarda siempre el mismo tiempo en resolver un problema determinado, sin embargo la dispersión obtenida es despreciable. El coste, al contrario que el tiempo, crece, pero de forma más suave. Asimismo, en el caso de RRT, aumenta la dispersión de este, obteniendo un rango de valores más ancho. En el caso de A*, el coste depende más de la disposición de obstáculos que del tamaño de las celdas usadas debido a su limitación de 8 direcciones: diferentes caminos pueden tener el mismo coste. 4.4. RRT*2 En este apartado, se van a mostrar los resultados obtenidos de este algoritmo en comparación con RRT*, ya que son bastante semejantes. RRT* también sirve de una buena referencia por ser un algoritmo bastante conocido y bien estudiado en este proyecto. Las pruebas se han hecho con los mismos parámetros que para todos los demás algoritmos, con condición de parada de encontrar el camino. En las Figuras 4.10 y 4.11 se muestran los resultados para todos los mapas. Como se observa en las imágenes, RRT*2 es algo más lento en la mayoría de situaciones, sin embargo en el Mapa 4, con muchos obstáculos y, teniendo un camino más directo, el tiempo es ligeramente inferior al algoritmo original. En los peores casos de los Mapas 2 y 3, la desigualdad llega a ser abismal: los tiempos de RRT*2 son casi el doble de RRT*. Sin embargo, la tendencia general de los valores de tiempo en el Mapa 1 es solamente ligeramente superior y, en el caso del Mapa 4, como ya se ha dicho, es menor. De aquí se puede concluir 63 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Tiempos obtenidos en función de D. (b) Costes obtenidos en función de D. Figura 4.8: Inuencia de D sobre el comportamiento de RRT. Se han representado los resultados en el Mapa 2. En otros Mapas, los efectos son parecidos. (a) Tiempos obtenidos en función de D. (b) Costes obtenidos en función de D. Figura 4.9: Inuencia de D sobre el comportamiento de A*. Se han representado los resultados en el Mapa 2. En otros Mapas, los efectos son parecidos. 64 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Mapa 1. (b) Mapa 2. (c) Mapa 3. (d) Mapa 4. Figura 4.10: Comparación de tiempos entre RRT* y RRT*2. 65 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov (a) Mapa 1. (b) Mapa 2. (c) Mapa 3. (d) Mapa 4. Figura 4.11: Comparación de costes entre RRT* y RRT*2. 66 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov que RRT*2 Funciona más rápido en los entornos donde las rutas no se desvían demasiado y el camino, en general, es directo. En cuanto a los costes, se puede decir que, igual que pasaba con el tiempo, resultan más favorecidos los mapas que no hacen desviar mucho la trayectoria. En este caso en los Mapas 1 y 4 se han obtenido mejores resultados y en los Mapas 2 y 3 han sido peores. La diferencia entre los resultados en el casos de mejora ha sido de un 3% mientras que en los otros, supera los 5%. De los estudios posteriores a este, se ha averiguado que el parámetro D , también inuye en los resultados. Parece ser, que RRT*2 funciona mejor con pasos más largos, disminuyendo las diferencias en los Mapas 2 y 3, y aumentando levemente la ventaja obtenida en el Mapa 4. En conclusión, para este tipo de pruebas, se puede decir que, en general, el algoritmo original RRT* supera al RRT*2, pero RRT*2 le gana la ventaja cuando se trata de espacios abiertos, con muchos obstáculos de pequeñas dimensiones y que no haya desviaciones importantes. Como ya se sabe, RRT* no destaca en la prueba de rapidez, pero si puede optimizar el camino, si se deja funcionando más tiempo. En la Figura 4.12 se muestran los resultados obtenidos en la prueba a tiempo donde el objetivo era llegar a los costes que superen los óptimos tan solo un 10%. Como cabía de esperar, en los tres primeros entornos no tarda mucho, sin embargo el último Mapa crece signicativamente. Mientras que los tiempos de RRT* están cerca del orden de 5 segundos, los tiempos de RRT*2, se disparan hasta 2 minutos, ya que, el algoritmo reconecta solo un nodo a la vez. También se han hecho pruebas jando el tiempo de trabajo. Como se ha visto en el apartado anterior, hay una inmensa diferencia entre los dos algoritmos si se dejan funcionando mucho tiempo. Por ello, en esta prueba se ha decidido que la duración máxima del funcionamiento sea de tan solo 2 segundos. Los resultados esta vez son los costes conseguidos, como se ve en la Figura 4.13. En esta prueba, RRT* también supera a RRT*2. Con esto se puede concluir que RRT* es mejor que RRT*2 en la gran mayoría de los casos, pero, siendo ambos algoritmos aleatorios, su comportamiento sigue sin estar totalmente denido y, pueden darse casos contrarios. 4.5. RRT Smooth Path El suavizado (o acortamiento) del camino trae muchas ventajas a la hora de usar los planicadores probabilísticos. Es una simple modicación del algoritmo que se aplica una vez que el camino haya sido encontrado. Este código modica el camino nal intentando saltar todos los nodos posibles para unir dos nodos alejados en linea recta como se ve en la Figura 4.14. De esta forma, se obtiene un camino considerablemente más corto aunque no se acerca demasiado al óptimo. En la Figura 4.15 se observa la inuencia de la modicación sobre los costes y los tiempos de ejecución. El coste promedio baja un 35% mientras que el tiempo de ejecución apenas varía. Es un resultado sobresaliente para una modicación tan simple. 67 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov RRT: este planicador probabilístico es más lento que A* en la mayoría de veces. Además el camino encontrado suele ser mucho más largo. Sin embargo, obtiene una gran ventaja en espacios con obstáculos trampa y su aleatoriedad le permite encontrar caminos en situaciones muy difíciles. Además de esto, no necesita un preprocesado o descomposición en celdas para su funcionamiento, lo que puede llegar a tener una duración de varios segundos dependiendo de la complejidad del mapa. En general, este algoritmo consigue mejores resultados en entornos con pocos obstáculos, ya que la comprobación de colisiones llega a ser bastante costosa en cuanto a la computación. En cuanto a las mejoras implementadas se tiene que: • Como ya se ha dicho, los costes de los caminos obtenidos están muy lejos de los óptimos. Para ello se ha creado RRT Smooth Path que los reduce signicativamente en poco tiempo, llegando a obtener los costes similares a A*. • La consideración de las dimensiones del UAV, empeora los resultados del algoritmo, pero puede tener una inmensa utilidad práctica en muchas aplicaciones. • Ambas mejoras pueden ser implementadas en cualquier programa que deriva del RRT simple. RRT*: este algoritmo es una modicación del anterior que reestructura el árbol creado, minimizando los costes. La característica principal de este planicador es que, una vez encontrado el camino, si el programa se sigue ejecutando, el camino se sigue optimizando hasta llegar casi al óptimo. La modicación RRT*2 implementada no obtiene ninguna ventaja clara sobre este algoritmo. RRT-Connect: esta versión del RRT se libera de las limitaciones impuestas para su predecesor. En concreto, se elimina el tamaño máximo de los pasos, lo que hace que el árbol se expanda mucho más rápido. Aparte de esto, el crecimiento desde los estados inicial y nal, mejora considerablemente las posibilidades de que estos se encuentren, haciéndolo más rápido. La principal desventaja es que la rápida expansión conlleva a cambios bruscos de dirección, por lo que se obtienen los peores costes de todos los algoritmos. Por último, la implementación de las dimensiones del UAV en los algoritmos de búsqueda, añade más profundidad al problema, pero permite obtener resultados más realistas. Este método permite introducir geometría compleja del UAV y de los obstáculos sin eliminar posibles resultados y no incluye preprocesamiento del mapa. Además de esto, aplicando las hipótesis correctas, se puede usar para hallar soluciones aproximadas a problemas complejos que requieren implementación de la dinámica y de la cinemática del problema. 74 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov 5.2. Líneas futuras Los algoritmos de búsqueda de caminos implementados son de carácter muy general, para su posterior aplicación se proponen varias mejoras: Integración de la dinámica y de la cinemática del problema ya que, en este trabajo, se ha visto su aplicación puramente geométrica. Estudio de sus aplicaciones en 2.5D y 3D. En este trabajo se ha centrado en movimiento plano, el espacio con más dimensiones puede abrir más posibilidades y crea nuevos problemas que serían interesantes de estudiar. Estudio e implementación de geometría mas compleja: considerando las dimensiones más detalladas y posibles obstáculos reales. Implementación de los algoritmos en el lenguaje C, lo que mejoraría los tiempos de ejecución. 75 Bibliografía [1] Randal W. Beard and Timothy W. McLain. Small Unmanned Aircraft : Theory and Practice . Princeton University Press, 2012. [2] Norman Biggs, E Keith Lloyd, and Robin J Wilson. Graph Theory, 1736- 1936 . Oxford University Press, 1976. [3] Jack E Bresenham. Algorithm for computer control of a digital plotter. IBM Systems journal , 4(1):2530, 1965. [4] Kenny Daniel, Alex Nash, Sven Koenig, and Ariel Felner. Theta*: Anyangle path planning on grids. CoRR , abs/1401.3843, 2014. [5] E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math. , 1(1):269271, December 1959. [6] Daniel Harabor and Alban Grastien. An optimal any-angle pathnding algorithm. Twenty-Third International Conference on Automated Planning and Scheduling , 2013. [7] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics , 4(2):100107, July 1968. [8] Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. The international journal of robotics research , 30(7):846894, 2011. [9] Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional conguration spaces. IEEE transactions on Robotics and Automation , 12(4):566580, 1996. [10] Oussama Khatib. Real-time obstacle avoidance for manipulators and mobile robots. The international journal of robotics research , 5(1):9098, 1986. [11] James J Kuner and Steven M LaValle. Rrt-connect: An ecient approach to single-query path planning. In Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on , volume 2, pages 9951001. IEEE, 2000. 77 Implementación y análisis de los algoritmos de planicación de caminos. Aplicación a sistemas aereos no tripulados. Nikita Tretiyakov [12] Andrew M Ladd and Lydia E Kavraki. Motion planning in the presence of drift, underactuation and discrete system changes. In Robotics: Science and Systems , pages 233240, 2005. [13] Steven M LaValle. Rapidly-exploring random trees: A new tool for path planning. 1998. [14] Steven M LaValle. Planning algorithms . Cambridge university press, 2006. [15] Vladimir J Lumelsky and Alexander A Stepanov. Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica , 2(1):403430, 1987. [16] Ioan A ucan and Lydia E Kavraki. Kinodynamic motion planning by interior-exterior cell exploration. In Algorithmic Foundation of Robotics VIII , pages 449464. Springer, 2009. [17] Kimon P Valavanis. Advances in unmanned aerial vehicles: state of the art and the road to autonomy , volume 33. Springer Science & Business Media, 2008. [18] Paul Keng-Chieh Wang. Visibility-based Optimal Path and Motion Planning . Springer International Publishing, 2015. 78