Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos

i –– Trabajo Fin de Máster MIT Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Autora: Iratxe Espartza Chueca Tutor: Daniel Gutiérrez Reina Dept. de Ingeniría Electrónica Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2017 ii Trabajo Fin de Máster MIT Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Autora: Iratxe Espartza Chueca Tutor: Daniel Gutiérrez Reina Doctor Ingeniero en Electrónica Dept. de Ingeniería Electrónica Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 iv Trabajo Fin de Máster: Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Autora: Iratxe Espartza Chueca Tutor: Daniel Gutiérrez Reina El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2018 El Secretario del Tribunal v A mi familia por animarme a no parar quieta y a la oficina de Cooperación al Desarrollo de la US, así como a Dani y Sergio, por darme la oportunidad de realizar mi TFM en Paraguay. vii Agradecimientos Los estilos adoptados por nuestra Escuela y utilizada en este texto es una versión y adaptación a Word® del la versión L A T E X que el Prof. Payán realizó para un libro que desde hace tiempo viene escribiendo para su asignatura. Por ello, la Escuela le está agradecida. Por otro lado, la adaptación se hizo sobre un formato que el prof. Aguilera arregló, basándose en su tesis doctoral. Su aportación ha sido muy relevante para que este formato vea la luz. Esta adaptación la llevamos a cabo el alumno Silvio Fernández, becario del Centro de Cálculo, y yo mismo, sobre un trabajo preliminar del alumno Julián José Pérez Arias. A esta hoja de estilos se le incluyó unos nuevos diseños de portada. El diseño gráfico de las portadas para proyectos fin de grado, carrera y máster, está basado en el que el prof. Fernando García García, de la Facultad de Bellas Artes de nuestra Universidad, hiciera para los libros, o tesis, de la sección de publicación de nuestra Escuela. Nuestra Escuela le agradece que pusiera su arte y su trabajo a nuestra disposición. Juan José Murillo Fuentes Subdirección de Comunicaciones y Recursos Comunes Sevilla, 2013 ix Resumen El objetivo de este trabajo es el diseño un algoritmo de path planning para un drone acuático de superficie autónomo que mida la calidad del agua en diferentes puntos del Lago Ypacaraí. Para este fin, se ha partido de un trabajo previo en el que se empleaban circuitos Hamiltonianos junto con Algoritmos Genéticos para la búsqueda del camino a realizar por el drone, adaptándose la forma en la que se genera la población inicial, de circuitos Hamiltonianos a Eulerianos. Para ello se ha creado un algoritmo con el que generar circuitos Eulerianos basándose en un grupo de balizas repartidas a lo largo del perímetro del lago. A partir de ese algoritmo se ha procedido a comparar los dos métodos planteados, y seguidamente a experimentar con diferentes parámetros para ver las diferencias de rendimiento del algoritmo. Finalmente, se ha podido comprobar que el nuevo algoritmo ha superado el rendimiento del método del que se partía. 16 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos utilizando un catamarán de (2x4) m 2 dotado de paneles solares para su funcionamiento continuo. Este drone deberá ser totalmente autónomo, es decir, se moverá sin necesidad de ser guiado por alguien, sorteando los posibles obstáculos que pueda encontrar por el camino. Además, será el encargado de generar por sí mismo un recorrido que pase por las diferentes balizas que se hallarán a lo largo del perímetro del lago, intentando que se recorra la mayor área posible. Para una primera fase de pruebas se ha sustituido el catamarán por una embarcación de menores dimensiones y que de momento tiene que ser guiada mediante un control remoto, con el fin de poder hacer las primeras mediciones y comprobar el correcto funcionamiento de los diferentes sensores. En paralelo se ha estado trabajando en una primera propuesta del algoritmo que creará la ruta a seguir por el drone. Esta primera propuesta se basa en el empleo de Algoritmos Genéticos (Genetic Algorithms, GAs) aplicados al Problema del Vendedor Viajero o Travelling Salesman Problem (TSP), que se encarga de encontrar la ruta más corta con la que conectar todas las balizas, pero para el caso del drone se invertiría con el fin de encontrar la ruta más larga y por lo tanto cubrir la mayor superficie del lago posible. La idea que subyace de este propuesta es que la distancia que recorre el drone está relacionada con el área que el drone será capaz de monitorizar del lago. El objetivo, pues, es intentar optimizar la distancia que recorre el drone en lago. También se tendrá en cuenta que no exista redundancia en los datos obtenidos, penalizándose para ello las intersecciones entre rutas. Este algoritmo ha dado buenos resultados con los que poder empezar, pero para una segunda fase de optimización se ha considerado oportuno intentar buscar solución a una importante limitación que introduce, que todas las balizas tengan que ser visitadas una sola vez. Esta limitación implica que por cada baliza sólo pueden existir dos rutas, una de entrada y otra de salida. Sin embargo, existen ciertas balizas que ocupan posiciones relevantes en la orilla del lago, que de ser visitadas varias veces aumentaría notablemente el áre cubierta por el drone. Lo que en en este trabajo se plantea es dejar de lado la limitación de visitar cada baliza una única vez para poder buscar combinaciones de balizas que resulten en un recorrido más óptimo; de este modo, algunas balizas se visitarán varias veces y otras quedarán inutilizadas. Para conseguir un recorrido de estas características, se propone el uso de recorridos Eulerianos como manera de optimizar el conocido Chinese Postman Problem (CPP). 17 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos 2 I NTRODUCCIÓN l seguimiento de la calidad de las aguas del Lago Ypacaraí es de suma importancia para poder comenzar a recuperar el estado original del lago, libre de vertidos que contaminan el lago y que favorecen la aparición de cianobacterias dañinas para el ecosistema. Para ello, es necesario el empleo de varias tecnologías de manera conjunta, como son los drones acuáticos de superficie y las técnicas de path planning, que para el caso de este proyecto comprenden algoritmos para encontrar rutas óptimas y también procedimientos que ayuden a resolver los anteriores. 2.1 Drones Acuáticos de Superficie Los Drones Acuáticos de Superficie, conocidos en inglés como Autonomous Surface Vehicles/Vessels (ASVs) o Unmanned Surface Vehicles/Vessels (USVs), son vehículos que operan sobre la superficie del agua y que no precisan de una tripulación. Esta característica hace que sean muy útiles a la hora de llevar a cabo tareas que puedan ser peligrosas para los humanos o que requieran mucho tiempo y por lo tanto tiene varias aplicaciones tanto militares o de seguridad, como comerciales o de investigación. Entre las aplicaciones del primer grupo se encuentran, entre otras, la seguridad y vigilancia de costas o el monitoreo de actividad submarinos de guerra. De las aplicaciones del segundo grupo destacan la observación de entornos marinos, los estudios geofísicos o la inspección de centrales de energía offshore [3]. Los ASVs pueden manejarse de dos maneras: con control remoto (Remote Control, RC) o autónomamente. En cualquiera de los dos casos no es necesario contar con una tripulación, pero en el caso de RC sí hace falta tener a alguien que dirija el ASV desde tierra. De la otra manera, basta con determinar un recorrido a seguir por el ASV. Todos los ASVs comparten características similares. La forma del vehículo suele ser de dos tipos, que son los catamaranes y los vehículos de un solo casco. Los catamaranes proporcionan mayor estabilidad debido a su diseño multi-casco (con dos cascos paralelos y del mismo tamaño) y por esta causa son los más empleados para la mayoría de aplicaciones. Algunos ejemplos de ASVs de esta forma que se pueden encontrar en el mercado son C-CAT 3 de ASV Global [3] o la gama WAM-V USV de Marine Advanced Research [4]. En cuanto a los vehículos monocasco, algunos ejemplos que se comercializan son la gama C-WORKER de ASV Global o AutoNaut USV de Autonaut ltd [5]. E 18 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Como carga de estas embarcaciones se añaden los componentes electrónicos necesarios para cada aplicación, tales como sensores (acústicos, metereológicos, batimétricos...), sistemas de comunicación, paneles solares, etc. Anteriormente ya se ha hecho uso de ASVs para estudiar las condiciones del agua en entornos marítimos o en lagos. Algunos ejemplos en el mar son las pruebas realizadas en el puerto de Livorno en Italia [6], protegido de olas y tráfico marino, o las mediciones de floración de algas dañinas en el estrecho de Johor de Singapur [7]. En cuanto a lagos o acuíferos, también se han hecho mediciones en torno a la floración de algas en el Lago Zurich [8], o de calidad del agua en general en un estanque de acuicultura cerca de La Paz (Mexico) [9]. 2.2 Path Planning Tal y como se ha comentado anteriormente, el ASV puede funcionar de manera completamente autónoma, es decir, sin necesidad de intervención de ningún humano. Para el funcionamiento autónomo del ASV es necesario que este tenga la capacidad de crear un recorrido a seguir, lo que se conoce como Path Planning. Como condiciones del recorrido se pueden establecer una serie de puntos que se han de visitar, caminos que no se pueden recorrer, puntos de comienzo o de final de la ruta, etc. Por otro lado, el recorrido se busca en función de un parámetro que se quiera optimizar, como puede ser la búsqueda de un recorrido con la menor distancia posible, el menor tiempo de recorrido, etc. Anteriormente ya se han buscado soluciones a problemas de path planning en entornos acuáticos. Por ejemplo, en el Lago Keller en Minnesota querían controlar la invasión de carpas y optaron por un algoritmo conjunto de TSPN (Travelling Salesman Problem with Neighborhoods) que visitaría todas las áreas rectangulares propuestas, y otro algoritmo que se encargaría de hacer el barrido de cada rectángulo [10]. En el Lago Winippeg en Canadá midieron la concentración de clorofila-A valiéndose de un sistema inteligente basado en aprendizaje estadístico para clasificar las regiones y más tarde utilizando redes neuronales para cuantificar la concentración [11]. Por otro lado, también se ha planteado el problema desde el punto de vista de un recorrido entre dos puntos A y B con obstáculos, como en el caso de una simulación usando MATLAB donde se calculó el trayecto más corto posible utilizando el algoritmo de la colonia de hormigas [12], o en el del ASV Springer de la Universidad de Plymouth donde hicieron uso del Fast Marching Method (FMM) para intentar dar solución al mismo problema [13]. Figura 2 - Los ASVs C-CAT 3 (catamarán) y WORKER-8 (monocasco) de ASV Global [1] 19 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos En el caso del problema del Lago Ypacaraí, el objetivo es hacer mediciones de la calidad del agua por toda la extensión del lago con tal de obtener la mayor cantidad de información posible sobre su estado en diferentes puntos. Por lo tanto, hay que planificar la ruta de modo que recorra la mayor área del lago posible, es decir, maximizar la distancia del recorrido por el que transita el ASV. Se parte de la base de que se tiene un número fijo de balizas o nodos que el ASV puede visitar a lo largo de su recorrido, realizando en total un número de conexiones igual al número de balizas. La distancia a maximizar sería, en este caso, la resultante de la suma de las distancias equivalentes a cada tramo o conexión del recorrido. Un problema de tales características puede abordarse desde el punto de vista de la teoría de grafos, representando las balizas como vértices y las conexiones como aristas. Hay varios teoremas que se encargan de dar solución a la trazabilidad de un grafo, que se dividen entre los que crean un recorrido tocando todos los vértices y los que crean un recorrido pasando por todas las aristas. La teoría de grafos fecha su origen en 1736 cuando el matemático Leonhard Euler resolvió el famoso Problema de los Siete Puentes de Könisberg. El problema trataba de dar respuesta a si existía la posibilidad de cruzar los 7 puentes de la ciudad e Könisberg (Prusia) pasando una sola vez por cada uno de ellos. Se vio que este problema podía expresarse como un problema de teoría de grafos, un área todavía inexistente en 1736, y basándose en ello surgió el concepto de grafo Euleriano. Un grafo Euleriano es aquel grafo conectado en el que cada nodo (vértice) tiene un número par de conexiones (aristas). Más adelante, y relacionado con lo anterior, se planteó el Chinese Postman Problem, que busca encontrar el camino más corto que pase por todas las conexiones al menos una vez, es decir, la trazabilidad del grafo pasando por todas las aristas. Por otro lado, están los recorridos que pasan por todos los vértices. El estudio de este tipo de recorridos lo empezó el matemático irlandés William Rowan Hamilton, y de ahí se ha desarrollado el concepto de grafo Hamiltoniano, que sería el grafo que se pueda recorrer pasando por todos los vértices. Aunque no se ha podido encontrar una caracterización para grafos de este tipo, sí que se han demostrado varias condiciones suficientes para que un grafo pueda considerarse Hamiltoniano. Basado en esto, se planteó el Travelling Salesman Problem, que efectivamente busca el recorrido más corto que pase por todos los nodos al menos una vez. 2.2.1 Los Siete Puentes de Könisberg Euler resumió su solución al problema de los Siete Puentes de Könisberg definiendo las siguientes reglas que se podían aplicar a cualquier problema similar con un número diferente de áreas de tierra o de puentes: “Así, cualquiera que sea la solución propuesta, uno puede fácilmente determinar si un recorrido puede o no ser realizado, cruzando cada puente una vez y siguiendo las siguientes normas: - Si hay más de dos areas a las que llegan un número impar de puentes, el recorrido es imposible de realizar. - De todos modos, si el número de puentes es impar para exactamente dos áreas, el recorrido es Figura 3 - Mapa de los siete puentes de Könisberg y su representación como grafo [14] 20 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos possible de realizer siempre que se empiece por una de estas áreas. - Finalmente, si no hay áreas a las que lleguen un número impar de puentes, el recorrido puede realizarse sea cual sea el punto de inicio. Con las normas presentadas, el problema propuesto puede ser resuelto [14].” 2.2.2 Chinese Postman Problem (CPP) Este problema fue planteado por el matemático chino Meigu Guan (también conocido como Mei-Ko Kwan) en 1962 y habla de un cartero que sale de la oficina de correos y tiene que entregar cartas en casas que están en diferentes calles para luego volver a la oficina. El problema reside en encontrar el recorrido cerrado de menor distancia que cumpla con su objetivo. [14] Si recordamos el concepto de grafo Euleriano como grafo conectado en el que cada nodo tiene un número de conexiones par, y relacionándolo con el tercer punto de la solución de Euler, se puede ver que en el caso de tener un grafo Euleriano la distancia mínima a recorrer será la suma de las distancias de todas las conexiones: = siendo l la distancia a recorrer y m la suma de las distancias de las conexiones. Por lo contrario, si el grafo no es Euleriano, alguna de las conexiones tendrá que ser recorrida más de una vez, por lo que esa distancia será mayor a la suma de las distancias de todas las conexiones. En este caso, el número de conexiones a repetir será de: 2−1! 2  −1! siendo 2k el número de nodos con conexiones impares. Para cada par de nodos con conexiones impares, se calcula la distancia que tendría una nueva arista que conectara los dos nodos y en función de esto se elige la de menor distancia. De esta manera, la distancia final a recorrer sería: =+ donde a m se le suma d que es la menor de las distancias entre los nodos impares. Puede observarse que con añadir conexiones entre los nodos impares se obtiene un grafo Euleriano, ya que todos los nodos pasan a tener un número par de conexiones. Al recorrido que pasa por cada arista al menos una vez se le llama camino Euleriano, y si además el recorrido es el de menor distancia posible, como es el resultado del problema descrito, se dice que es camino Euleriano mínimo. El CPP varía en complejidad dependiendo del tipo de grafo. Normalmente, si se trata de un grafo dirigido como de uno no dirigido, el problema puede resolverse en tiempo polinomial. Si en cambio el grafo es mixto, es decir, si contiene rutas tanto dirigidas como no dirigidas; o si el problema se altera de alguna manera puede llegar a ser NP-hard también [15]. 2.2.3 Travelling Salesman Problem El problema presentado es el siguiente: un comerciante quiere hacer un viaje de ida y vuelta en el que visite ciertas ciudades, pasando una vez por cada una de ellas; conociendo las distancias entre cada par de ciudades, quiere buscar el recorrido de menor distancia posible. El problema recién descrito puede traducirse en un grafo ponderado donde los vértices corresponderían a las ciudades y las distancias entre estas serían los diferentes pesos. La solución a este problema vendría a ser la minimización de la suma los de pesos de las aristas por las que pasa el recorrido. Si el número de ciudades n es alto, el número de recorridos posibles entre ellas también lo será, dado por la siguiente expresión: −1! 2 por lo que se presenta como un problema muy difícil de resolver en general, categorizado como NP-hard o NP-complejo. Debido a la complejidad, hay técnicas que resultan de ayuda para resolver este tipo de 21 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos problemas, como pueden ser por ejemplo los algoritmos genéticos, dentro de los algoritmos metaheurísticos. 2.3 Algoritmos Genéticos Tal y como se ha comentado en apartados anteriores, el TSP está categorizado como un problema NP-hard o NP-complejo. Esto significa que no puede resolverse en tiempo polinomial y por lo tanto hay que buscar alternativas para tratar de encontrar una solución, ya que intentar todas las combinaciones, lo que se llama fuerza bruta, sería inviable. El CPP por su parte sí puede ser resuelto en tiempo polinomial, si se trata de un grafo dirigido o de uno no dirigido. Para hacer frente a problemas NP-hard, hay que buscar alternativas a la fuerza bruta. Una alternativa que se emplea frecuentemente es el uso de Algoritmos Genéticos (GAs). Los GAs están inspirados en la evolución natural: parten de una populación candidata y van escogiendo las que mejor solución dan al problema, para basándose en ellas crear nuevas soluciones. Este tipo de algoritmos actúan como algoritmos heurísticos, realizando la búsqueda entre un conjunto de soluciones a un problema [16]. Volviendo a la evolución natural, todo organismo vivo tiene un conjunto de cromosomas único que lo describe. Un cromosoma es una molécula larga de ADN, que se conforma de genes, siendo cada gen representativo de una característica del individuo. En el momento en el que un organismo se reproduce, pasa copias de sus cromosomas a los siguientes individuos, ocurriendo ocasionalmente algún tipo de mutación que altera las características de esa copia, y por lo tanto pudiendo mejorar la descendencia. En la reproducción sexual, se combinan cromosomas de dos individuos generando nuevos individuos que son una mezcla de los anteriores, pudiendo de esta mezcla surgir mejoras también. Para los AGs se mantiene la terminología utilizada para la evolución natural, y al equivalente a la reproducción sexual se le conoce como crossover. Al igual que en la naturaleza los mejores individuos tienen más probabilidades de sobrevivir, lo mismo pasa con los AGs. La metodología utilizada en los AGs puede dividirse en dos pasos básicos: la selección de los mejores individuos y la reproducción de los seleccionados. La selección de los mejores individuos se hace basándose en el fitness de cada individuo, que depende de una función de evaluación que recibe una posible solución y devuelve un número indicando cómo de buena es esa solución. Para el segundo paso, se utilizan las operaciones de crossover y mutación y así se obtiene una nueva generación de individuos. El funcionamiento de los GAs puede verse reflejado en la Figura 5: Figura 4 - Operaciones de crossover y mutación 22 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Figura 5 – Funcionamiento de los GAs Como puede verse, el primer paso en un algoritmo genético es la creación de una población inicial. Para ello se escoje un número de individuos, las simulaciones se han realizado con 100, que se crean aleatoriamente para poder comenzar con el algoritmo. Seguidamente y si todavía no se cumple con el criterio de parada, que para este proyecto se trata de un número de generaciones, se procede a la selección de los padres. Esta selección puede realizarse con diferentes criterios, tratándose en este caso de la selección de los mejores individuos de la población. De esa selección de individuos se consigue un offspring o descendencia mediante los procesos de crossover y mutación anteriormente descritos y se vuelve una vez más a calcular el fitness de cada individuo, para volver a empezar con el proceso. Una vez se ha llegado al número de generaciones propuesto (el criterio de parada en este caso), se para el algoritmo. El output del algoritmo será por lo tanto una población del tamaño inicial, de donde podrá extraerse el indiviuo de mayor fitness. Los AGs no dejan de ser métodos aproximados, así que de ellos se pueden esperar soluciones válidas pero que no tienen por qué ser óptimas. De todos modos, se pueden ajustar diferentes parámetros para conseguir resultados que se acerquen más al objetivo de la búsqueda. 23 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos 3 D ESCRIPCIÓN GENERAL DEL PROBLEMA on el objetivo de abordar el proyecto del Lago Ypacaraí, se describireron los detalles del problema a resolver y sobre ello se efectuó una primera aproximación que diera solución al problema descrito. Esta primera aproximación ya dio unos resultados válidos y buenos, pero se ha intentado replantear el modelado del problema para intentar buscar una solución más óptima y por lo tanto unos resultados mejores. 3.1. Problema de cobertura basado en putos de interés Tal y como se ha explicado en el apartado de motivación del proyecto, el Lago Ypacaraí ha visto la calidad de sus aguas comprometida por el vertido de residuos tanto domésticos, como de procedencia agraria e industrial. Los residuos que se vierten en las aguas que desembocan en el lago han disparado los niveles de nitrógeno y fósforo, favoreciendo la floración de cianobacterias, con su consiguiente producción de toxinas que son perjudiciales para los organismos del entorno. Para recuperar el estado natural del lago, es de suma importancia hacer un seguimiento de la calidad del agua así como de los focos de contaminación. La detección de los puntos de contaminación es el primer paso a seguir para poder acabar con la floración de cianobacterias, ya que una vez erradicados los vertidos, el lago por sí mismo será capaz de recuperarse y volver a su estado original. En pos de dar una solución para hacer un seguimiento eficiente de la calidad del agua en el Lago Ypacaraí, se ha planteado el uso de un conjunto de balizas que estarían situadas por todo el perímetro del lago. El número de balizas a utilizar será en un principio de 60 (las cuales estarán numeradas con números entre 0 y 59), y cada baliza se encontrará a menos de 1 km de la siguiente. Las balizas se han dispuesto con una separación de 1 km porque se pretende plantear el conjunto de balizas como una red de sensores, donde el drone pueda enviar los datos recopilados. La disposición de las balizas se ve ilustrada en la Figura 6: El ASV debe viajar visitando las diferentes balizas (puntos de interés) y recogiendo muestras de agua por el camino. De esta manera, se podrá obtener un rango de muestras más completo que utilizando unos puntos fijos de muestreo. Durante el recorrido se evaluarán los niveles de ficocianina, que es un pigmento que alerta de la presencia de cianobacterias. Este pigmento absorbe la luz natural a 620 nms y la fluorescente a 650 nm, que es lo que hace que pueda ser detectado por los sensores. A partir de los resultados obtenidos de esas mediciones se puede C Figura 6 - Posición de las balizas sobre el Lago Ypacaraí [17] 24 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos categorizar la presencia de cianobacterias como perjudicial para el ser humano, a nivel moderado por encima de 20,000 cells/mL y a nivel alto si alcanza los 100,000 cells/mL [17]. Además del uso de estos sensores, el ASV también servirá para medir otras características del lago, empleando sensores de PH, de temperatura, de batimetría etc. Para que las muestras sean representativas de todo el lago, el objetivo del ASV es el de cubrir la mayor área del lago posible, cosa que intentará conseguir recorriendo la mayor distancia posible entre las diferentes balizas. Teniendo en cuenta que las balizas más cercanas se encuentran a menos de 1 km de distancia y la distancia mayor entre balizas es de alrededor de 14 kms, el ASV tiene que ser capaz de encontrar la combinación de balizas que le permita acercarse a un recorrido óptimo desde el punto de vista de la distancia máxima. La idea principal es que la distancia que recorre el ASV está correlada con la cobertura del lago sensada por este. 3.2. Modelo del problema basado en TSP Una primera solución dada al problema del lago se basó en el Traveling Salesman Problem (TSP), tratando de encontrar la distancia máxima que se pueda recorrer pasando por todas las balizas, una vez por cada una de ellas. El problema original trata de encontrar la distancia mínima con la que poder realizar ese recorrido, por lo que para el caso del lago se cambió la función objetivo para buscar el resultado contrario. Otra diferencia con el TSP original es que en el caso del Lago Ypacaraí hay que añadir restricciones referentes a las rutas inválidas, es decir, las que pasan por tierra. En la introducción que se ha hecho sobre el TSP en el apartado anterior, ya se ha mencionado que el número de combinaciones de un problema de estas características es muy elevado; por un número de balizas n concretamente sería de: −1! 2 por lo tanto, para nuestro caso con n = 60 balizas el uso de la fuerza bruta para resolverlo sería impensable, ya que hay 6.93 · 10 79 diferentes combinaciones de balizas, sin tener en cuenta las restricciones por rutas inválidas. No por nada se cataloga al TSP como NP-hard o complejo. Para poder abordar un problema de tal magnitud, se planteó el uso de algoritmos genéticos (GAs). De esta manera, se parte de una población inicial creada a partir de rutas válidas que pasan por todas las balizas, y utilizando los GAs se intenta llegar a una solución más óptima a efectos de distancia recorrida. Para ello, se definieron varias funciones para calcular el fitness o la calidad de cada individuo. Las rutas creadas para la población inicial deben contener, como se ha dicho, todas las balizas y sin repetirse. Además de eso, tienen que ser creadas de manera que no incluyan rutas inválidas, es decir, que no contengan ninguna ruta que pase por tierra, ya que a efectos prácticos esto sería imposible de implementar. En cuanto a la función de fitness, esta se encarga de valorar el área total que se cubre dependiendo de la distancia recorrida y del número de veces que se pasa por el mismo punto, para no considerarlo como un área nueva recorrida. La función de fitness también aplica penalizaciones a sus rutas inválidas, que se han definido de dos maneras diferentes: la primera, con Death Penalty, descarta cualquier recorrido que contenga rutas inválidas asignándole un -1 como valor de fitness; la segunda, con Penalty Factor, considera los individuos inválidos para la evolución, pero les aplica una penalización en el fitness [18]. Una muestra de una solución obtenida mediante el uso del TSP se puede ver en la Figura 7, a la izquierda utilizando el Penalty Factor y a la derecha con el Death Penalty: 25 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Como puede observarse, el recorrido de la izquierda contiene varias rutas inválidas, pero el de la derecha está libre de ellas. 3.3. Modelo del problema basado en CPP Como un intento de mejorar los resultados previamente obtenidos, se ha planteado la posibilidad de quitar una restricción que se respetaba para el caso del TSP, la que dicta que hay que pasar por todas las balizas una única vez. Se ha creído conveniente probar a hacerlo de esta manera después de ver que en las soluciones obtenidas mediante el uso del TSP, que pueden verse en el apartado anterior, el centro se transitaba varias veces en contraste con otros puntos del lago. Si se tiene en cuenta de que las intersecciones entre rutas no son útiles, ya que simplemente nos ofrecen información redundante, no conviene pasar por el mismo sitio más de una vez. De esta manera, para este nuevo planteamiento del problema se ha abierto la posibilidad de pasar varias veces por la misma baliza y por lo tanto de dejar otras balizas sin visitar. Este nuevo planteamiento busca favorecer el uso de balizas ubicadas en sitios estratégicos, ya sea porque cuentan con rutas largas o porque no tienen muchas rutas inválidas, sobre otras balizas que pueden encontrarse peor colocadas. También se ha decidido cambiar la manera de crear la población inicial, planteándolo desde un punto de vista de grafos. Así, en vez de ir añadiendo paradas al recorrido, se partirá de una matriz de conexiones para crear los individuos de esa población inicial. Figura 7 - Ejemplo de los resultados obtenidos mediante el uso del TSP [17] 32 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos cubierta con duplicidad se restaba del valor del fitness calculado a partir de la distancia o área total. La función de fitness resultante cumple la siguiente relación: KF@GLL=%M NOP ∙1 R STU R V +W R X R XYU * #Z[ =−M NOP ∙ #*!'",'( donde M NOP se refiere al área que cubre mientras avanza,  #*!'",'( es el número de intersecciones que se producen durante el recorrido (i.e., número de veces que el drone pasa por un lugar anteriormente visitado), y  R \ R ] es la distancia entre dos balizas consecutivas. Ya se ha comentado anteriormente que debido al perfil del Lago Ypacaraí hay varias conexiones entre balizas que no pueden realizarse, ya que para ello necesitarían cruzar por tierra. Por lo tanto, es necesario que el fitness penalice dichas rutas inválidas en caso de que las haya. Se plantearon dos maneras diferentes de incorporar la penalización por rutas inválidas: Death Penalty y Penalty Factor. En el caso del Death Penalty, si el recorrido contiene una ruta inválida el valor del fitness pasa a ser -1 directamente, como se muestra a continuación: KF@GLL ^_ =`%M NOP ∙1 R STU R V +W R X R XYU * #Z[ =−M NOP ∙ #*!'",'( ,%%%%%Da%>?@L%FbáFL %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%−1,%%%%%LF%>?@L%FbáFL Por lo tanto, los recorridos que contengan rutas inválidas quedarán descartados inmediatamente, y no se tendrán en cuenta para futuras generaciones. En el Penalty Factor, en cambio, la penalización que se le da a las rutas inválidas no es tan drástica, regiéndose por la siguiente expresión: KF@GLL _c =%1−  "#*.  R' ()* −1∙dM NOP ∙1 R STU R V +W R X R XYU * #Z[ =−M NOP ∙ #*!'",'( e donde  "#*. es el número de rutas inválidas contenidas en la solución y  R' ()* es el número de balizas que existen. En este caso el valor del fitness irá a peor por cada ruta inválida que se incluya en el recorrido, pero eso no descartará necesariamente la solución, por lo que se tendrá en cuenta para futuras generaciones. 4.3 Selección de individuos Cada vez que se obtiene una población, y si se quiere seguir con el algoritmo genético durante más generaciones, es necesario seleccionar un número de individuos entre los que realizar los procedimientos de crossover y mutación. Esta selección se lleva a cabo mediante dos técnicas en paralelo: por un lado el elitismo y por el otro el método de la ruleta. La proporción de la población que se obtiene mediante cada uno de los dos procedimientos se representa mediante una probabilidad de elitismo que puede ajustarse para cada simulación. La técnica del elitismo trata simplemente de pasar los individuos con mejor valor de fitness a la siguiente generación, sin que estos sufran ninguna alteración debida al crossover o mutación. De esta manera, se garantiza que los mejores individuos no se pierdan de una generación a otra. En el método de la ruleta se le asigna a cada individuo un espacio proporcional al valor de fitness que tiene. Es decir, cuanto mejor sea el fitness de un individuo, mayor es la representación que obtiene en la ruleta. Un ejemplo de este método puede verse en la Figura 12: 33 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Figura 12 – Ejemplo de selección por ruleta En este ejemplo, el Individuo 1 es el que mayor fitness tiene y por lo tanto es también el que mayor representación tiene en la ruleta, ocupando un 33% de la misma. En el otro extremo está el Individuo 2, que es el de menor fitness y consecuentemente el de menor representación. En el momento de hacer girar la ruleta, el individuo 1 tendrá casi el doble de probabilidad de ser elegido como “padre” para la siguiente generación que el individuo 2, pero ambos tienen esa posibilidad. 4.4 Operaciones genéticas Una vez se ha hecho la selección de los individuos que actuaran como padres, se procede al crossover y la mutación de las que se obtendrán los nuevos individuos de la generación. Para ello, cada vez se escogerán dos individuos “padres” que mediante crossover producirán dos individuos “hijos”, a los que dependiendo de una probabilidad también se les aplicará un procedimiento de mutación. Hay diferentes maneras de realizar el crossover y para este problema se ha escogido el crossover ordenado (Ordered Crossover, OX). Este crossover funciona de la siguiente manera: primero, se coge un segmento de uno de los padres y se mantiene intacto y en la misma posición; luego partiendo desde la primera posición libre que ha quedado en el hijo, se va rellenando con los datos del segundo padre. La misma operación se repite cambiando el orden de los padres, para obtener un segundo hijo. Un ejemplo del procedimiento puede verse en la Figura 13: Figura 13 - Ejemplo de crossover Como puede verse en el ejemplo, para crear al Hijo 1 primero se copia la secuencia [3, 4, 5] directamente del Padre 1 y en la misma posición. Luego, empezando desde la primera posición libre, se va rellenando con los datos del Padre 2 empezando también desde la misma posición. Es decir, para rellenar la última posición del Hijo 1 se mira la última posición del Padre 2, pero como en este caso el número 4 ya va incluido por la Individuo 1; 16,95; 33% Individuo 2; 8,63; 17% Individuo 3; 11,2; 21% Individuo 4; 14,86; 29% Fitness Individuo 1 Individuo 2 Individuo 3 Individuo 4 34 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos herencia del Padre 1 se pasa al siguiente (que sería el correspondiente a la primera posición); como el número 3 también está ya en el hijo, se mira el siguiente que sería el 1 y este es el que se incluye en la última posición del Hijo 1. Se procede de esta manera hasta completar todas las posiciones del Hijo 1, y lo mismo se hace para la generación del Hijo 2. Una vez se han obtenido los dos individuos “hijos”, se procede con la mutación. La mutación, como ya se ha dicho, depende de una probabilidad (de mutación): ese porcentaje de individuos será mutado y el resto se mantendrá tal y como se ha obtenido en el crossover. Cuando un individuo es mutado, cada gen o atributo puede intercambiar posiciones con otro de los genes dentro del mismo individuo, estando este cambio sujeto a otra probabilidad. Por lo tanto, posición por posición el gen se intercambiará con otro o se mantendrá en su lugar original dependiendo de esta última probabilidad. Este tipo de mutación es habitual en secuencias de índices, por lo que es aplicable en las secuencias de balizas que componen el recorrido de cada solución. Para finalizar, se calcula el fitness de cada uno de los individuos de la nueva generación y se comprueba que el mejor de ellos no contenga rutas inválidas. En el caso de que así sea, ya se tiene una generación válida con la que seguir el algoritmo; pero si por lo contrario el individuo contiene rutas inválidas se comienza con la generación desde el principio. 4.5 Criterio de parada de la evolución El algoritmo genético se repite tantas veces como generaciones se quieran realizar. A mayor complejidad del problema, mayor será el número de generaciones necesario para que el algoritmo llegue a convergir. Para este problema se ha empleado una variable con la que poder cambiar el número de generaciones a realizar y de esta manera poder adecuarlo a cada fase. Es importante ajustar adecuadamente el número de generaciones para cada caso, ya que hay que garantizar que el algoritmo converja para poder encontrar una solución válida y estable, pero por otro lado cada generación alarga el tiempo necesario para llegar a esa solución y por lo tanto hay que intentar no excederse. . 35 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos 5 R ESULTADOS a primera parte del apartado de resultados se divide en tres diferentes fases. En una primera fase de pruebas se compara el algoritmo del TSP con el planteado con circuitos Eulerianos y CPP. Para esta etapa no se tiene en cuenta la restricción de las rutas inválidas, en un simplemente intento de tener una primera impresión de la posible mejora o no de los resultados obtenidos. Para el segundo conjunto de resultados, se ha añadido la condición de las rutas inválidas con tal de adecuarlo al problema del Lago Ypacaraí y comprobar que la solución obtenida sigue siendo válida y mejor que el TSP. Por último, se han hecho simulaciones para diferentes números de balizas con el objetivo de poder medir las distancias recorridas en cada caso y encontrar una relación. Para todas las simulaciones se utilizan probabilidades de mutación y de crossover de 0.2 y 0.8 respectivamente, a no ser que se especifique lo contrario, y el número de generaciones se fija a 1000. En la última parte de los resultados se hacen diferentes pruebas para decidir si los parámetros recién descritos resultan los más óptimos para las simulaciones que se llevan a cabo, o por si lo contrario hay que hacer algún ajuste en los mismos con tal de poder encontrar soluciones óptimas. Los valores utilizados habitualmente para los parámetros más relevantes del algoritmo genético se han recogido en la Tabla 1: Tabla 1 - Parámetros GA Número de balizas 60 Probabilidad de crossover 0.8 Probabilidad de mutación 0.2 Proporción de elitismo 0.2 Nº individuos en la población 100 Nº de generaciones 1000 5.1 Plataforma de simulación En la fase anterior del proyecto se planteó una solución basada en el TSP, donde cada baliza se visitaba una única vez y no había ninguna que quedara en desuso. Para poder simular dicho algoritmo, se implementó un programa en Python versión 2.7. en el que se empleó el módulo Distributed Evolutionary Algorithm for Python (DEAP). Este módulo contiene las funciones necesarias para implementar los algoritmos genéticos, entre ellas cxOrdered para el crossover ordenado, mutShuffleIndexes para la mutación, selRoulette para la selección de ruleta y selBest para el elitismo. Para poder marcar las balizas se guardaron las coordenadas reales del lugar que ocuparía cada una de ellas en el perímetro del lago, para a partir de ahí poder calcular las distancias que hay entre cada una de las balizas. Por otro lado, se recogió en una matriz la información referente a las rutas inválidas, para de este modo poder determinar si un recorrido pasaba por tierra o no. En lo que se refiere al cálculo del fitness, también se creó una matriz que contiene las intersecciones que puede haber entre las rutas, a fin de poder aplicar las penalizaciones pertinentes a los recorridos que las contengan. Con todos estos datos, el simulador crea una primera población inicial que sea válida con la que alimentar el algoritmo genético. Esta primera población se trata de un recorrido por todas las balizas teniendo en cuenta la restricción de las rutas inválidas, y de que cada baliza no puede ser visitada en más de una ocasión. De ahí en adelante, haciendo uso de las funciones ofrecidas por el módulo DEAP, se llevan a cabo los procesos de selección, crossover y mutación para obtener una nueva generación con la que retomar el algoritmo genético L 36 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos paso por paso. Finalmente, al alcanzar el número de generaciones propuesto, se escoge al mejor individuo, i.e., el que mejor valor de fitness tiene. Para esta fase del proyecto se ha mantenido la estructura del programa, empleando el algoritmo genético previamente programado, pero con dos cambios significativos. Por un lado, se desecha la restricción de visitar cada baliza una única vez. Por otro lado, se ha creado una nueva función para obtener la población inicial, basándose en los recorridos Eulerianos. 5.2 Sin tener en cuenta las rutas inválidas No todas las conexiones entre las balizas son posibles de implementar en el caso del Lago Ypacaraí, ya que por su morfología hay varias de estas rutas que pasan por tierra en algún punto del trayecto. De todas maneras, como una primera aproximación, se han hecho pruebas sin tener en cuenta estas restriccionesa aplicar por las rutas inválidas. De esta manera, se puede tener una primera idea de los resultados que se puedan obtener más adelante, y lo que es más importante, se va a poder comparar el algoritmo propuesto con la implementación anterior basada en el TSP, para basándose en esta comparación seguir adelante para buscar esas mejoras o desechar la idea. En la Tabla 2 pueden verse los resultados obtenidos utilizando el algoritmo del TSP. Se han hecho tres pruebas diferentes: 1. Sin intersecciones: no se aplica ninguna penalización por tener intersecciones, es decir, no se penaliza el hecho de pasar dos veces por el mismo punto. 2. Death Penalty: se tienen en cuenta las intersecciones y se penalizan con un fitness de -1 las rutas inválidas. 3. Penalty Factor: se tienen en cuenta las intersecciones y se aplica una penalización en el fitness por las rutas inválidas. 37 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 2 - TSP sin tener en cuenta las rutas inválidas TRAVELLING SALESMAN PROBLEM Sin Intersecciones Death penalty Factor de penalización Sim Fitness Sim Fitness Sim Fitness 0 16,62 0 16,018 0 16,149 1 16,691 1 16,1 1 16,199 2 16,634 2 16,162 2 16,074 3 16,554 3 16,133 3 16,168 4 16,602 4 16,052 4 16,095 5 16,665 5 15,967 5 16,042 6 16,553 6 16,112 6 16,09 7 16,668 7 16,104 7 16,067 8 16,594 8 16,099 8 16,237 9 16,57 9 16,065 9 16,143 10 16,615 10 16,16 10 16,125 11 16,577 11 16,053 11 15,979 12 16,616 12 16,124 12 16,169 13 16,619 13 16,17 13 16,112 14 16,648 14 16,205 14 15,966 15 16,637 15 16,095 15 16,166 16 16,653 16 16,07 16 16,025 17 16,643 17 16,121 17 16,166 18 16,666 18 16,163 18 16,2 19 16,614 19 16,205 19 16,054 Media 16,621 Media 16,109 Media 16,111 Std. Dev. 0,039 Std. Dev. 0,061 Std. Dev. 0,074 Mejor fit 16,691 Mejor fit 16,205 Mejor fit 16,237 Al no tener rutas inválidas en estas simulaciones, el Death Penalty y el Penalty Factor dan el mismo resultado. Teniendo en cuenta que la diferencia entre el Death Penalty y el Penalty Factor reside en el tratamiento que se les da a las rutas inválidas, que en este caso no se tienen en cuenta, los dos medidores funcionan de la misma manera. Es decir, en ambos casos siemplemente se tienen en cuenta las intersecciones. Es lógico por lo tanto que para los apartados 2 y 3 el fitness que se obtiene sea menor que para el apartado 1, donde no hay penalizaciones de ningún tipo. Los resultados obtenidos sin tener en cuenta las intersecciones son del orden de 16.6 de fitness, mientras que teniendo en cuenta las intersecciones esa puntuación baja hasta el orden de 16.1-16.2. La desviación estándar obtenida es bastante baja por lo que los resultados de las diferentes simulaciones no tienen una gran variación, parece que el algoritmo converge. Los resultados obtenidos utilizando el CPP se pueden observar en la Tabla 3: 38 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 3 – CPP sin tener en cuenta las rutas inválidas CHINESE POSTMAN PROBLEM Sin Intersecciones Death penalty Factor de penalización Sim Fitness Sim Fitness Sim Fitness 0 17,507 0 18,253 0 16,881 1 16,95 1 17,75 1 17,651 2 18,062 2 17,219 2 16,928 3 17,801 3 17,445 3 17,427 4 17,665 4 17,36 4 18,432 5 18,397 5 17,509 5 17,174 6 17,609 6 17,128 6 17,017 7 18,96 7 17,842 7 16,618 8 17,663 8 17,328 8 17,675 9 17,542 9 16,942 9 17,326 10 19,767 10 17,757 10 16,878 11 17,553 11 17,281 11 18,152 12 17,15 12 18,153 12 17,395 13 17,531 13 17,664 13 16,229 14 17,191 14 18,124 14 17,367 15 16,827 15 17,014 15 16,955 16 17,786 16 17,889 16 16,761 17 16,942 17 16,429 17 17,863 18 17,614 18 18,101 18 16,928 19 16,993 19 17,339 19 17,602 Media 17,675 Media 17,526 Media 17,263 Std. Dev. 0,710 Std. Dev. 0,470 Std. Dev. 0,535 Mejor fit 19,767 Mejor fit 18,253 Mejor fit 18,432 Para este caso también las simulaciones sin tener en cuenta las intersecciones dan mejor resultado que las que sí las tienen en cuenta, como era de esperar. También puede verse que los valores de fitness en general son considerablemente mejores que en el caso del TSP, siendo el mejor resultado obtenido con el CPP (19.767) 3 puntos mayor que el obtenido con el TSP (16.691). Otro dato que puede extraerse de los dos conjuntos de soluciones es que la desviación estándar para el caso del TSP es mucho menor que para el CPP, lo que significa que los resultados del segundo varían mucho más que para el primer caso. Esto puede significar que hacer las simulaciones con 1000 generaciones puede no ser suficiente para que el CPP converja. Un ejemplo de una ruta obtenida en este apartado puede verse en la Figura 14. Como puede observarse, hay varias rutas inválidas, ya que el recorrido pasa varias veces por tierra. También parece a simple vista que, en comparación con la Figura 7 obtenida de los resultados del TSP en el apartado 3.2 (página 18), las rutas están más distribuidas por el área del lago en vez de pasar mucho por la zona del centro, y que por lo tanto se cubre más superficie que con el TSP. 39 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Figura 14 - Ejemplo de recorrido con rutas inválidas. TSP (izquierda) y CPP (derecha). 5.3 Teniendo en cuenta las rutas inválidas Tal y como se ha dicho, existen varias balizas sobre el perímetro del Lago Ypacaraí que no pueden ser conectadas en línea recta a no ser que se cruce por tierra. Al tratarse del recorrido de un catamarán, las rutas tienen que ser por agua en su totalidad, por lo que hay que tener en cuenta esas conexiones inválidas a la hora de preparar el camino que el ASV seguirá. Esto se traduce en varias restricciones a tener en cuenta. El número de estas rutas inválidas es bastante elevado, por lo que dificulta en gran medida encontrar una ruta que sea válida, además de empeorar el fitness del restulado obtenido. Volviendo a la Figura 14 del apartado anterior, puede verse que en la zona superior derecha de la imagen hay una concentración de rutas inválidas muy significativa, que por otro lado es la que posibilita que se recorra toda el área del lago de manera balanceada en vez de concentrarse en algunas regiones concretas de la misma, como podía pasar con el algoritmo previamente utilizado, el TSP. Los resultados que se han obtenido de las simulaciones teniendo en cuenta las rutas inválidas se han recogido en la Tabla 4. Tal y como puede apreciarse, los resultados que da el CPP siguen siendo mejores que los obtenidos con el TSP, con una diferencia de 1.8 puntos en el mejor fitness y de 0.8 en la media de todos los fitness. En ambos casos el Death Penalty da mejor resultado que el Penalty Factor, y a eso hay que añadirle que con el Penalty Factor no es raro que el recorrido final contenga alguna ruta inválida, lo cual hace que la solución sea inservible. Por esta razón, de aquí en adelante las simulaciones se han realizado únicamente con el Death Penatly, dejando a un lado el Penalty Factor. 40 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 4 - Comparacion teniendo en cuenta las rutas inválidas TRAVELLING SALESMAN PROBLEM CHINESE POSTMAN PROBLEM Death Penalty Penalty Factor Death Penalty Penalty Factor Sim R. Inv. Fitness Sim R. Inv. Fitness Sim R. Inv. Fitness Sim R. Inv. Fitness 0 0 14,758 0 0 14,222 0 0 15,385 0 0 15,117 1 0 14,535 1 2 14,21 1 0 14,913 1 0 14,517 2 0 14,435 2 1 14,046 2 0 15,022 2 2 14,634 3 0 14,247 3 0 14,511 3 0 15,326 3 2 14,945 4 0 14,585 4 0 14,431 4 0 15,476 4 0 15,486 5 0 14,606 5 1 14,388 5 0 15,943 5 0 15,644 6 0 14,769 6 0 14,449 6 0 15,388 6 0 14,997 7 0 14,641 7 0 14,645 7 0 15,443 7 0 14,782 8 0 14,715 8 0 14,54 8 0 15,217 8 1 14,438 9 0 14,531 9 0 14,293 9 0 15,499 9 2 14,964 10 0 14,823 10 0 14,546 10 0 15,52 10 1 15,181 11 0 14,532 11 0 14,723 11 0 14,721 11 3 15,267 12 0 14,518 12 0 14,407 12 0 14,561 12 1 15,593 13 0 14,581 13 0 14,587 13 0 16,357 13 1 15,892 14 0 14,456 14 1 14,417 14 0 16,198 14 2 15,798 15 0 14,376 15 1 14,187 15 0 15,182 15 2 14,806 16 0 14,502 16 2 14,23 16 0 15,524 16 0 15,391 17 0 14,382 17 0 14,515 17 0 16,612 17 0 14,677 18 0 14,559 18 0 14,751 18 0 14,717 18 0 15,38 19 0 14,232 19 2 14,257 19 0 14,971 19 1 15,042 Media fit 14,539 Media fit 14,418 Media fit 15,39875 Media fit 15,127 Media r. inv. 0 Media r. inv. 0,5 Media r. inv. 0 Media r. inv. 0,9 Std. Dev. 0,159 Std. Dev. 0,190 Std. Dev. 0,54512286 Std. Dev. 0,423 Mejor fit 14,823 Mejor fit 14,751 Mejor fit 16,612 Mejor fit 15,892 Un ejemplo de una ruta obtenida a partir de una simulación utilizando el Death Penalty puede verse en la Figura 15. En este caso, y a diferencia de en la Figura 14, no hay ninguna ruta inválida, por lo que todo el recorrido transcurre por el agua y no es necesario cruzar por tierra. A causa de esto, puede verse también que el área “conflictiva” que se ubica en la parte superior derecha de la imagen ya no es tan concurrida como antes. Esto se debe a que muchas veces no es rentable visitar las balizas que se ubican en esa área porque cuentan con muchas rutas inválidas y eso hace empeorar el fitness, por lo que el algoritmo decide visitar otras balizas más cómodas varias veces y dejar de visitar algunas como la 2 o la 5 por ejemplo. Pueden reconocerse las balizas que no se visitan como las de color rojo, y las que sí se visitan son las de color azul. 41 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Figura 15 - Ejemplo de recorrido sin rutas inválidas. TSP (izquierda) y CPP (derecha). 5.4 Distancia recorrida por número de balizas utilizadas En este apartado se ha buscado encontrar una relación entre balizas utilizadas y distancia total recorrida. Tener esta relación es importante ya que sabiendo la velocidad a la que viaja el catamarán y la duración de las baterías que lo impulsan, se puede fácilmente calcular la distancia que el ASV puede recorrer, que sería la dada por la siguiente expresión: FL@DF%=b%G%D@>á%f g%×?@aaí%G%L%@G>íL%f Y sabiendo la distancia que se puede recorrer, puede ajustarse el número de balizas a utilizar para que el algoritmo devuelva un recorrido realizable por el ASV. El valor de la duración de las baterías que se emplearía en este caso sería en ausencia de sol, ya que en un día soleado las baterías se cargarían mientras el catamarán estuviera en marcha a través de los paneles solares instalados en su cubierta. Incluso en días nublados las baterías podrían cargarse ligeramente. De todos modos, para una primera aproximación y como valor mínimo es conveniente usar esta medida. Las mediciones se han hecho para 10, 20, 30, 40, 50 y 60 balizas, siendo este último valor el que se venía utilizando hasta el momento, ya que corresponde al total de las balizas disponibles. La Tabla 5 muestra los valores obtenidos con 10, 20 y 30 balizas, mientras que en la Tabla 6 se muestran los resultados para 40, 50 y 60 balizas; todos ellos representados en metros. Hay que indicar, por último, que la restricción del número de balizas que se puedan usar no define cuáles son las balizas que puedan usarse, por lo que es el algoritmo el que elije el conjunto de balizas que mejor resultado de en términos de valor del fitness. 48 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 10 - Anova para diferentes probabilidades de mutación RESUMEN Grupos Cuenta Suma Promedio Varianza Columna 1 20 317,737 15,88685 0,2030474 Columna 2 20 319,704 15,9852 0,11201512 Columna 3 20 317,721 15,88605 0,17491952 Columna 4 20 321,338 16,0669 0,0793762 Columna 5 20 322,692 16,1346 0,15899331 ANÁLISIS DE VARIANZA Origen de las variaciones Suma de cuadrados Grados de libertad Promedio de los cuadrados F Valor crítico para F Entre grupos 0,96545806 4 0,24136451 1,65692321 2,46749362 Dentro de los grupos 13,8386793 95 0,14567031 Total 14,8041374 99 5.5.3 Número de generaciones Como ya se ha comentado en apartados anteriores, por los resultados obtenidos de las simulaciones con 1000 generaciones parecía que el algoritmo no estaba convergiendo. Es importante saber a partir de qué cantidad de generaciones converge el algoritmo, para conocer cuándo pueden tomarse los resultados obtenidos como óptimos. De todos modos, cabe destacar que la convergencia del algoritmo por si no nos da el mejor resultado, ya que siempre queda la probabilidad de que se caiga en un máximo local y el algoritmo converja en cuanto a ese valor. En la Tabla 11 pueden verse los resultados para 1000, 2000 y 3000 generaciones. Como puede apreciarse, a medida que se aumenta el número de generaciones la calidad de los resultados también mejora, obteniendo cada vez mejores valores de fitness. Otro dato que se puede extraer de los resultados es que aunque la media de los fitness obtenidos mejore, en todos los conjuntos de resultados pueden verse valores de fitness basante “malos” en comparación con el resto, como por ejemplo en la simulación 18 con 2000 generaciones, donde el fitness es de solo 14.966, significantemente peor que para la mayoría de los valores obtenidos con 1000 o 15000 generaciones. Esto puede ser debido a que el algoritmo se haya quedado en algún máximo local y por lo tanto no haya podido llegar a un resultado mejor. 49 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 11 - Resultados para 1000, 2000 y 3000 generaciones NGEN = 1000 NGEN = 1500 NGEN = 2000 Death Penalty Death Penalty Death Penalty Simulación Fitness Simulación Fitness Simulación Fitness 0 15,385 0 15,722 0 15,19 1 14,913 1 15,208 1 16,519 2 15,022 2 15,759 2 15,442 3 15,326 3 16,204 3 16,372 4 15,476 4 15,216 4 16,072 5 15,943 5 15,084 5 15,402 6 15,388 6 15,741 6 15,872 7 15,443 7 15,886 7 15,205 8 15,217 8 14,969 8 16,048 9 15,499 9 15,179 9 16,827 10 15,52 10 16,149 10 16,184 11 14,721 11 15,372 11 16,653 12 14,561 12 15,828 12 16,586 13 16,357 13 15,536 13 16,143 14 16,198 14 15,565 14 15,399 15 15,182 15 16,171 15 15,23 16 15,524 16 16,194 16 15,497 17 16,612 17 16,184 17 16,286 18 14,717 18 16,409 18 14,966 19 14,971 19 16,34 19 16,37 Media 15,399 Media 15,736 Media 15,913 Std. Dev. 0,545 Std. Dev. 0,454 Std. Dev. 0,573 Mejor fit 16,612 Mejor fit 16,409 Mejor fit 16,827 Dibujando en una gráfica el fitness obtenido generación tras generación, para cada uno de los tres casos de la Tabla 11, se han obtenido los resultados mostrados en la Figura 18 (de izquierda a derecha los gráficos para 1000, 1500 y 2000 generaciones),. Como puede observarse el algoritmo no llega a converger en ninguno de los casos . Por lo tanto es necesario aumentar el número de generaciones si se quiere llegar a obtener mejores resultados. En el siguiente conjunto de simulaciones se ha probado con 2500, 5000 y 10000 generaciones, y se han recogido los resultados en la Tabla 12 - Resultados para 2500, 5000 y 10000 generaciones: Figura 18 - Convergencia con 1000, 1500 y 2000 generaciones 50 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Tabla 12 - Resultados para 2500, 5000 y 10000 generaciones NGEN = 2500 NGEN = 5000 NGEN = 10000 Death Penalty Death Penalty Death Penalty Simulación Fitness Simulación Fitness Simulación Fitness 0 16,508 0 15,374 0 15,756 1 15,536 1 16,583 1 16,179 2 15,44 2 15,702 2 15,867 3 16,277 3 16,282 3 16,019 4 15,801 4 16,734 4 16,773 5 16,014 5 16,053 5 16,181 6 15,248 6 16,489 6 16,465 7 16,623 7 16,558 7 15,423 8 16,155 8 16,017 8 15,985 9 16,082 9 16,623 9 16,269 10 16,381 10 15,832 10 16,233 11 16,113 11 16,515 11 15,928 12 15,67 12 17,065 12 15,826 13 16,356 13 15,555 13 16,027 14 14,813 14 15,192 14 15,929 15 15,977 15 16,17 15 16,489 16 15,676 16 16,977 16 15,222 17 16,071 17 16,797 17 15,664 18 16,125 18 16,176 18 16,315 19 15,951 19 16,043 19 15,84 Media 15,941 Media 16,237 Media 16,019 Std. Dev. 0,444 Std. Dev. 0,523 Std. Dev. 0,365 Mejor fit 16,623 Mejor fit 17,065 Mejor fit 16,773 Con las nuevas simulaciones puede verse que la tendencia de mejora del fitness sigue junto con el aumento del número de generaciones hasta llegar a las 5000 generaciones, ya que los resultados obtenidos con 10000 no presentan mejoras. Esto se debe a que, aunque con más generaciones el algoritmo converge más, hay varios máximos locales y por lo tanto la solución obtenida no siempre es la referente al máximo global, de modo que dependiendo de la simulación puede obtenerse un fitness mejor o peor. Figura 19 - Convergencia con 2500, 5000 y 10000 generaciones 51 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Mirando en la Figura 19 las convergencias para las generaciones de la Tabla 12 (de izquierda a derecha los gráficos para 2500, 5000 y 10000 generaciones), puede verse que sigue sin conseguirse que el algoritmo converja. Por lo que ha podido verse, es necesario aumentar el número de generaciones con tal de encontrar el punto en el que el algoritmo converja. Es así que se han realizado un nuevo conjunto de simulaciones utilizando 20000 generaciones. Los resultados para estas nuevas simulaciones pueden verse en la Tabla 13. Tabla 13 - Resultados para 20000 generaciones NGEN = 20000 Death Penalty Simulación Fitness 0 16,368 1 17,002 2 16,099 3 15,967 4 16,14 5 16,49 6 16,556 7 15,924 8 15,026 9 16,425 10 15,983 11 16,284 12 15,945 13 16,593 14 15,526 15 15,867 16 15,667 17 15,037 18 16,226 19 16,495 Media 16,081 Std. Dev. 0,499 Mejor fit 17,002 Una vez más, puede verse que los resultados ya no se mejoran, ya que en este caso siguen siendo peores que los obtenidos con 5000 aunque algo mejores que los obtenidos con 10000. De todos modos, tal y como ya se ha comentado esto responde a que el algoritmo a veces se queda en máximos locales y por lo tanto no mejora a partir de un punto. Lo que sí que puede verse ahora es que el algoritmo por fin converge, como puede apreciarsen en las diferentes gráficas recogidas en la Figura 20: 52 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Como puede apreciarse, dependiendo de la simulación la generación a la que el algoritmo converge varía, pero en todos los casos llega a converger antes de alcanzar las 20000 generaciones. De hecho, con 15000 también se consigue en todos los casos, siendo en la mayoría de ellos suficiente llegar a 125000 generaciones. Figura 20 – Convergencia con 20000 generaciones 53 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos 6 C ONCLUSIONES Y FUTUROS TRABAJOS e ha visto que la utilización de algoritmos genéticos para el diseño de algoritmos de path planning ofrece una interesante solución al problema propuesto para el Lago Ypacaraí. El trabajo previo realizado basándose en el problema del viajero o Traveling Salesman Problem (TSP) que tomaba las balizas repartidas a lo largo del perímetro del lago como “ciudades” a visitar, dio una primera alternativa al problema planteado, con buenos resultados. Para esta primera solución se tuvieron en cuenta varias restricciones como que cada baliza solo podía visitarse una vez (condición impuesta por el TSP) o que varias rutas no eran válidas (aquellas que necesitaban pasar por tierra). También se plantearon diferentes escenarios, con diferentes funciones de fitness para la evaluación del algotirmo, para de esta manera buscar el que mejores resultados obtenía. Partiendo de esta primera aproximación, se ha planteado el problema basándose esta vez en el Chinese Postman Problem (CPP). De acuerdo a este problema, el objetivo es pasar por todas las rutas, no por todas las “ciudades”, por lo que desaparece la restricción de visitar cada baliza una única vez aunque se mantengan las rutas inválidas. Para conseguir un escenario en el que poder aplicar el CPP se ha desarrollado una técnica para buscar circuitos Eulerianos con los que poder alimentar el algoritmo. Como primer paso se ha comparado el rendimiento de ambas soluciones sin tener en cuenta la restricción de las rutas inválidas, con intención de comprobar a primera vista podía tratarse de una mejora de los resultados y proseguir con las pruebas. El segundo paso ha sido añadir las rutas inválidas, con lo que el resultado obtenido ha seguido siendo mejor que el que se tenía de base. Por último, se ha calculado una relación entre el número de balizas empleados y la distancia recorrida, con el objetivo de poder ajustar el funcionamiento del drone a las necesidades del momento. El resultado obtenido mediante el uso de este método ha conseguido mejorar al anterior, pasando de un valor de fitness máximo de 16.612 a uno de 14.823 en el escenario con rutas inválidas y 60 balizas utilizando Death Penalty y 2000 generaciones; una mejora de un 12.1%. En el caso del Penalty Factor para el mismo escenario, la mejora es del 7.7%, con un fitness de 14.751 para el caso de TSP y un 15.892 para CPP. Sobre la comparativa de estos dos métodos se ha escrito un artículo que está a espera de revisión para ser publicado. Todavía quedan muchas variaciones del problema con los que experimentar como trabajos futuros. Por un lado, se podría cambiar de técnica de optimización. Se ha visto que los algoritmos genéticos dan resultados competentes, pero también existen otros algoritmos como por ejemplo el Particle Swarn Optimization (PSO) donde un grupo de soluciones candidatas van cambiando para acercarse a máximos locales conocidos, o el Simulated Annealing (SA) donde se va disminuyendo la probabilidad de aceptar soluciones “malas” hasta llegar a una aproximación del máximo que se pueda obtener. En relación al Algoritmo Genético (AG), también queda la opción de explorar la utilización de diferentes técnicas de crossover o de mutación. En este caso se ha empleado el Ordered Crossover (OC) junto con unos parámetros de mutación específicos, pero variando en estos procedimientos podría llegarse a soluciones diferentes, tal y como ya se ha visto con la variación de las probabilidades de ocurrencia de los dos eventos. Otros aspectos específicos del problema del Lago Ypacaraí sobre los que profundizar pueden ser el procedimiento para la creación de individuos válidos con los que alimentar el AG, por ejemplo en lo que respecta a la eliminación de rutas inválidas en la matriz de conexiones, o las posiciones de las balizas del lago. Esto último por sí solo constituiría un problema de optimización diferente. S 54 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos 55 R EFERENCIAS [1] [En línea]. Available: http://rescatemosnuestrolago.gov.py/. [Último acceso: Julio 2017]. [2] [En línea]. Available: http://www.lagoypacarai.com/. [Último acceso: Julio 2017]. [3] [En línea]. Available: https://www.asvglobal.com/. [Último acceso: Julio 2017]. [4] [En línea]. Available: http://www.wam-v.com/. [Último acceso: Julio 2017]. [5] [En línea]. Available: http://www.autonautusv.com/. [Último acceso: 2017 Julio]. [6] G. Ferri, A. Manzi, F. Fornai, F. Ciuchi y C. Laschi, «The HydroNet ASV, a Small- Sized Autonomous Catamaran for Real-Time Monitoring of Water Quality: From Design to Missions at Sea,» IEEE Journal of Oceanic Engineering, vol. 40, July 2015. [7] S. C. Y. Leong, P. Tkalich y N. M. Patrikalakis , «Monitoring harmful algal blooms in Singapore: Developing a HABs observing system,» OCEANS, 2012. [8] G. Hitz, F. Pomerleau, M. Garneau, C. Pradelier, T. Posch, J. Pernthaler y R. Y. Siegwart, «Autonomous Inland Water Monitoring: Design and Application of a Surface Vessel,» IEEE Robotics & Automation Magazine, vol. 19, 2012. [9] J. Gutierrez, F. Vila-Medina y M. A. Porta- Gandara, «Autonomous Surface Vehicle for Measuring Water Body Parameters,» de IEEE Conference on Electronics, Robotics and Automotive Mechanics Conference (CERMA), 2010. [10 ] P. Tokekar, E. Branson, J. V. Hook y V. Isler, «Tracking Aquatic Invaders: Autonomous Robots for Monitoring Invasive Fish,» IEEE Robotics & Automation Magazine, vol. 20, 2013. [11 ] F. Halal, P. Pedrocca, T. Hirose, A. M. Cretu y M. B. Zaremba, «Remotesensing based adaptive path planning for an aquatic platform to monitor water quality,» Robotic and Sensors Environments (ROSE), 2014. [12 ] W. Yuan-hiu y C. Cen, «Research on optimal planning method of USV for complex obstacles,» de IEEE International Conference on Mechatronics and Automation (ICMA), 2016. [13 ] Y. Liu, R. Song y R. Bucknall, «A practical path planning and navigation a lgorithm for an unmanned surface vehicle using the fast marching algorithm,» OCEANS, 2015. [14 ] F. Fugie y P. Zhang, Covering Walks in Graphs, Springer, 2010. [15 ] H. Jiang, L. Kang, S. Zhang y F. Zhu, Genetic Algorithm for Mixed Chinese Postman Problem, 2010. [16 ] L. D. Chambers, de Practical Handbook of Genetic Algorithms: Complex Coding Systems, CRC Press, 1998 , pp. 29-33. [17 ] M. Arzamendia, D. G. Reina, S. L. Toral y D. Gregor, «An Event Detection and Tracking Adaptative Strategy for an Autonomous Surface Vehicle in Lake Environments using Evolutionary Computation». 56 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos [18 ] M. Arzamendia, D. G. Reina, S. L. Toral y D. Gregor, «An Evolutionary Approach to Constrained Path Planning of an Autonomous Surface Vehicle for Maximizing the Covered Are a of Ypacaraí Lake,» de International Conference on Developments in eSystems Engineering (DeSE), Liverpool, 2016. [19 ] D. Pearson y V. Bryant, de Decision Maths 1: Advancing Maths for AQA, Heinemann, 2004, pp. 44-64. 57 Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos Í NDICE DE F IGURAS Figura 1 - Ubicación del Lago Ypacaraí 15 Figura 2 - Los ASVs C-CAT 3 (catamarán) y WORKER-8 (monocasco) de ASV Global [1] 18 Figura 3 - Mapa de los siete puentes de Könisberg y su representación como grafo [14] 19 Figura 4 - Operaciones de crossover y mutación 21 Figura 5 – Funcionamiento de los GAs 22 Figura 6 - Posición de las balizas sobre el Lago Ypacaraí [17] 23 Figura 7 - Ejemplo de los resultados obtenidos mediante el uso del TSP [17] 25 Figura 8 - Generación de matriz de conexiones 27 Figura 9 – Proceso de eliminar rutas inválidas 28 Figura 10 - Obtención de grafos Eulerianos 30 Figura 11 - Obtención de un circuito Euleriano 31 Figura 12 – Ejemplo de selección por ruleta 33 Figura 13 - Ejemplo de crossover 33 Figura 14 - Ejemplo de recorrido con rutas inválidas. TSP (izquierda) y CPP (derecha). 39 Figura 15 - Ejemplo de recorrido sin rutas inválidas. TSP (izquierda) y CPP (derecha). 41 Figura 16 - Relación de la distancia recorrida por número de balizas empleado 44 Figura 17 - Convergencias para las diferentes cantidades de balizas utilizadas 44 Figura 18 - Convergencia con 1000, 1500 y 2000 generaciones 49 Figura 19 - Convergencia con 2500, 5000 y 10000 generaciones 50 Figura 20 – Convergencia con 20000 generaciones 52