Efficient robot cooperation using MTSP

Proyecto Fin de Carrera Ingeniería de Telecomunicación Formato de Publicación de la Escuela Técnica Superior de Ingeniería Autor: F. Javier Payán Somet Tutor: Juan José Murillo Fuentes Dep. Teoría de la Señal y Comunicaciones Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2013 Trabajo Fin de Máster Ingeniería Electrónica, Robótica y Automática Efficient robot cooperation using MTSP Autor: Jesús Caballero Rodríguez Tutores: Begoña C. Arrue Ullés y Aníbal Ollero Baturone Dpto. Teoría de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 Trabajo Fin de Máster Ingeniería Electrónica, Robótica y Automática Efficient robot cooperation using MTSP Autor: Jesús Caballero Rodríguez Tutores: Begoña C. Arrue Ullés y Aníbal Ollero Baturone Profesor Titular Dpto. Teoría de Sistemas y Automática Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2019 Trabajo Fin de Máster: Efficient robot cooperation using MTSP Autor: Jesús Caballero Rodríguez Tutores: Begoña C. Arrue Ullés y Aníbal Ollero Baturone El tribunal nombrado para juzgar el trabajo arriba indicado, compuesto por los siguientes profesores: Presidente: Vocal/es: Secretario: acuerdan otorgarle la calificación de: El Secretario del Tribunal Fecha: Resumen El objetivo principal de este trabajo consiste en implementar una solución del denominado Problema del Viajero (TSP) en el recorrido de un UAV simulado en el entorno de ROS (Robotic Operating System). En dicho problema, concebiremos al UAV que recorre una serie de waypoints de su recorrido como el viajero que se plantea recorrer una serie de ciudades, optimizando la distancia recorrida en el viaje. Con ayuda de dicha analogía, supondremos que el viajero parte de una ciudad origen y pretende llegar a una ciudad destino pasando tan solo una vez por las ciudades intermedias del recorrido. Posteriormente, abordaremos la variante del MTSP (Multiple Traveling Salesman Problem) en la que se consideran varios viajeros que deben llegar a sus respectivos destinos, partiendo del mismo origen y repartiéndose entre ellos las ciudades intermedias del recorrido con el fin de obtener una solución aceptable conjuntamente. III 1.3 Metodología 3 La solución del Problema del Viajero basada en nuestra propuesta, que se explicará a continuación, puede permitir facilitar una supuesta misión de inspección de UAVs, en la que sea necesario abarcar un territorio de extensión considerable dadas coordenadas de puntos del recorrido. Por ejemplo, en un entorno de placas solares sería interesante usar esta técnica para decidir el orden de inspección y tratamiento de defectos. En el apartado correspondiente, una vez que se haya expuesto y resuelto el problema del viajero, se explicará de qué manera se incluye la librería del MTSP desarrollada en este ejemplo de UAV. Metodología Se ha llevado a cabo la programación necesaria para resolver el problema, tanto del TSP como del MTSP, empleando el lenguaje de programación C. Se han empleado nuevas herramientas de programación, con respecto a la solución propuesta en MATLAB del algoritmo, que simplifican su resolución. Además de esta simplicidad, otra ventaja asociada al empleo de estas nuevas herramientas consiste en la sencillez con la que se puede implementar el código en la librería de ROS. Se explicará posteriormente en qué consisten dichas técnicas de programación y en qué medida mejora el algoritmo con respecto al caso sintetizado anteriormente en MATLAB. Estructura de la memoria En los próximos apartados, se tratará de explicar con detenimiento en qué consiste cada uno de los dos problemas de optimización presentados anteriormente, el TSP y el MTSP. Comenzando por el TSP, se explicará en qué consiste, de qué manera se puede plantear el problema de la manera más simple y, una vez aclarado el planteamiento general del problema, se recordará a grandes rasgos cómo se resolvió en problema empleando el lenguaje de programación MATLAB. Una vez hecho esto, se propondrá la nueva solución empleada en el entorno de ROS, empleando el lenguaje de programación C. Posteriormente indagaremos en el MTSP: introduciremos brevemente el problema, aclararemos variables introducidas en el código del TSP relacionadas con este nuevo problema, y presentaremos las variantes del MTSP que se han considerado. Hablaremos, en primer lugar, de la solución usada con Matlab para compararla posteriormente con la solución hecha en el entorno de ROS. Una vez se hayan explicado cada una de las variantes, qué se quiere conseguir y cómo queremos lograrlo, presentaremos las clases usadas para resolver tanto TSP como MTSP en ROS con el empleo del lenguaje C. Tras esto, se explicará de qué manera se implementa la solucion de este problema de optimización en el vuelo de un UAV (Vehículo Aéreo no Tripulado) en una simulación en Gazebo, que forma parte del entorno de ROS. Para concluir, se hablará de posibles mejoras en el código y en la metodología empleada para mejorar las soluciones propuestas del problema. También se comparará con otros métodos que pueden resolver el problema, algo que servirá de punto de partida para discutir tanto las ventajas como los inconvenientes del método propuesto. Descripción del sistema y algoritmia: TSP Introducción A pesar de que la idea de recorrer diversas ciudades hasta llegar a un destino puede parecer bastante intuitiva para el ser humano, cuando es una máquina la encargada de dar el resultado más óptimo dentro de sus posibilidades no es algo trivial. Si tuviésemos, además de un solo destino y un solo comienzo, tan sólo dos ciudades intermedias por las que pasar, no resulta complicado dar la solución óptima del recorrido mínimo; hay muy pocas posibilidades de ruta respetando las premisas necesarias (partir de un origen, recorrer las ciudades intermedias, y llegar a un destino). Incluso con tres ciudades intermedias puede resultar un problema relativamente sencillo a resolver por el ser humano, si se persigue el óptimo en nuestro recorrido. Sin embargo, ¿qué hacer cuando se nos presenta un número relativamente elevado de ciudades intermedias? ¿Y si tengo 9 o 10 ciudades intermedias? No es en absoluto discutible que una persona proporcione una buena solución ante este problema, aunque dado el enorme número de posibilidades que ahora existen para planificar una ruta, una máquina podría dar una solución más optima que la proporcionada por la intuición humana, haciendo uso de los algoritmos apropiados. 5 6Capítulo 2. Descripción del sistema y algoritmia: TSP Resumen del método anterior (MATLAB) En la implementación que se llevó a cabo en MATLAB, considerábamos un grafo que ilustraba los posibles recorridos que el viajero podía llevar a cabo desde la ciudad de origen hasta el destino. Los nodos que conformaban dicho grafo almacenaban información bastante relevante en cuanto al recorrido. Principalmente, proporcionaban información acerca de la distancia total recorrida hasta la ciudad actual del viaje, nos decía por qué ciudades habíamos viajado anteriormente (y en qué orden) y en la ciudad en la que el viajero se encontraba en ese momento. Además, cada nodo del grafo almacenaba más información relacionada con las posibles rutas que quedaban por explorar en el grafo para obtener más soluciones del problema de optimización. Sin embargo, en cuanto a las transiciones entre nodos, estas no guardaban ningún tipo de información; tan sólo aparecían en el grafo del viaje para ilustrar la conexión entre varios nodos o estados del árbol. Por ejemplo, una representación del grafo para tres ciudades intermedias podía ser la siguiente: 1 2 5 11 17 6 12 18 3 7 13 19 8 14 20 4 9 15 21 10 16 22 Figura 2.1 Grafo de estado para tres ciudades intermedias. CO C1 C2 C3 CF C3 C2 CF C2 C1 C3 CF C3 C1 CF C3 C1 C2 CF C2 C1 CF Figura 2.2 Grafo de estado para tres ciudades intermedias; ciudades. En esta última representación, se muestra el grafo de estados con el nombre de la ciudad asociada a cada nodo. Por ejemplo, el nodo padre del árbol (CO) almacena toda la información asociada a ese punto del viaje; el viajero ha pasado por la ciudad origen y puede ir a las ciudades C1,C2, o C3. Toda esta información, como se comentó, asociada a los nodos. De esta menera, se obtiene una base de datos considerable con estructuras de nodos, en las que se guarda toda la información. 2.3 Método de implementación en ROS: empleo de clases 7 Por otra parte, los hijos de un nodo padre siempre aparecen ordenados de menor a mayor distancia en el viaje entre ciudades, de manera que el viaje CO-C1 es el que almacena menor distancia. Una posible solución del grafo se podría representar de esta otra forma: 1 2 5 11 17 6 12 18 3 7 13 19 8 14 20 4 9 15 21 10 16 22 Figura 2.3 Posible solución del grafo para 3 ciudades intermedias. En concreto, la última solución mostrada en imagen representa el recorrido del viajero pasando a la ciudad más cercana desde la que de encuentra en ese momento. Esto no implica que la mejor solución sea la rama situada más a la izquierda del grafo, pero sí que suela proporcionar una buena solución. A continuación, a partir del próximo apartado, se explicará cómo se ha reformulado el problema para obtener soluciones con una complejidad a nivel de programación mucho menor. Incluso, se baraja la posibilidad de servirse del paralelismo entre procesos que brindan los hilos o subprocesos, para poder obtener más soluciones de este problema de programación en menos tiempo. Método de implementación en ROS: empleo de clases Para reestructurar el problema desde cero, como se acaba de comentar en el apartado anterior, es necesario adoptar un enfoque distinto al que se ha llevado a cabo hasta ahora para resolver este problema de optimización. En concreto, a partir de ahora nos serviremos de la programación orientada a objetos para concebir distintos tipos de variables con información que se complemente entre sí; todo esto para poder resolver este problema de una manera mucho más liviana. Por ejemplo, a partir de ahora emplearemos objetos de la clase Node que no tendrán por qué almacenar toda la información del recorrido que ha llevado a cabo el viajero hasta ese momento (como se hacía anteriormente). En lugar de ello, la clase Branch definirá un tipo de objeto que será capaz de obtener información acerca del recorrido completo del viajero, sirviéndose a su vez de la clase Node. También emplearemos una clase llamada Path que almacenará la distancia entre ciudades del recorrido, de manera que los nodos no almacenen más información de la necesaria (que es algo que ocurría en la implementación con Matlab). En los próximos apartados, se explicará con detenimiento el cometido de cada una de las clases definidas y qué papel jugarán cuando tratemos de abordar el problema completo. Toda la implementación de clases se llevará a cabo, además de para disminuir la complejidad de programación, para prescindir de una base de datos de un tamaño considerable en la que se almacene toda la información, como se hacía en el caso explicado en el apartado anterior con MATLAB. Introducción a las clases definidas Un buen ejemplo para ilustrar el tipo de objetos que se manejará a nivel de programación lo podemos encontrar en la estructura que presenta un árbol normal y corriente. 8Capítulo 2. Descripción del sistema y algoritmia: TSP ¿Por qué razón? Nuestro objetivo principal es obtener la solución que haga que la ruta del viajero sea la de menor recorrido posible o, al menos, la de menor distancia en el viaje considerando el resto de soluciones obtenidas. Si considerásemos el árbol mencionado anteriormente, podríamos imaginar que la ciudad de inicio del viaje se corresponde con el tronco del árbol, mientras que el extremo de todas y cada una de las ramas del árbol se corresponden con las soluciones al problema del viajero. Podríamos entender las bifurcaciones en las ramas del árbol como las ciudades intermedias, a partir de las cuales podemos viajar a otras ciudades. Figura 2.4 Algoritmo en clases: símil con un árbol. Si nos interesase obtener las mejores soluciones, posiblemente la mejor opción sería buscar la ramificación más corta que parta del tronco del árbol y que llegue hasta el extremo final de una rama. Vemos que estamos materializando el problema que tratamos de resolver en un objeto del mundo real, que se encuentra en la naturaleza: un árbol. Este árbol está formado por lo que podrían ser objetos con características distintas. Por una parte, podemos considerar las bifurcaciones entre las ramas, así como las ramas que van uniendo bifurcaciones entre sí. Teniendo en cuenta las bifurcaciones y las secciones de las ramas en el árbol, podrían definirse a su vez ramas más largas que partan desde el tronco y lleguen cerca del extremo final, el cual se puede definir como ciudad de destino. Todas estas partes del árbol (así como el propio árbol) se pueden definir como objetos en un contexto de programación. A continuación, hablaremos de las clases que definen a dichos objetos y del tipo de información que tienen asociada. 2.3 Método de implementación en ROS: empleo de clases 9 City En el árbol mencionado, podemos considerar las bifurcaciones como puntos en los que cambiar el recorrido de una rama hacia otra distinta, para obtener soluciones distintas a su vez. En estos puntos de inflexión estará la información asociada a las ciudades por las que el viajero irá pasando al llevar a cabo su recorrido. Por ello, en primer lugar, podemos definir la clase City que contenga las coordenadas de las ciudades consideradas en todo el recorrido del viajero, así como un identificador unívoco que permita distinguirlas del resto de ciudades que se tienen en cuenta en el viaje. De ahora en adelante, ilustraremos mediante diagramas UML (Unified Modeling Language Diagram [ 13 ]) las clases que definirán a los objetos que se emplearán en nuestro programa. Haciendo alusión a dicho diagrama, el de la clase City tendría esta forma: City + id : int + city : vector<float> + fill : void + get-string-data : vector<string> Figura 2.5 Diagrama UML: Clase City. En el diagrama mostrado, podemos apreciar que hay tres secciones divididas horizontalmente y que definen conjuntamente la clase City, con la que se podrán definir los objetos que serán las ciudades. En las tres divisiones, respectivamente, aparece información acerca de: 1. Nombre de la clase. (City) 2. Atributos de la clase City (valores almacenados). 3. Métodos de la clase (funciones que permiten operar sobre los atributos de la clase). En cuanto a la marca que aparece antes de nombre del atributo o método, nos dará información acerca de la visibilidad del atributo o método al que esté haciendo referencia ("+" significa público, mientras que "-" significa privado). A nivel de código, la clase City quedaría definida de esta manera en lenguaje C, en el anexo [A.1]. Node Aunque en el subapartado anterior hayamos definido las ciudades que formarán parte del recorrido del viajero, esta información no es suficiente para definir de manera unívoca las bifurcaciones en el árbol que presentamos anteriormente. Dicho de otra manera: necesitamos un identificador que distinga una misma ciudad por la que se ha pasado en rutas diferentes del algoritmo. Para ello, consideraremos y definiremos una nueva clase en la que se almacenarán tanto la ciudad del recorrido como su identificador en en árbol. El identificador, a nivel de programación, lo definiremos como un entero. A esta nueva clase la llamaremos clase Node . En el siguiente esquema, tratamos de ilustrar mediante un diagrama UML la definición que acabamos de aportar: Como consideraremos un grafo de estados, igual que hicimos en el caso del algoritmo resuelto con MATLAB, también declararemos un atributo que almacene el nivel que ocupa el nodo dentro del grafo. Esto se hará para facilitar la implementación de la clase Branch (que presentaremos más adelante). Con respecto a los métodos de la clase, hemos definido los siguientes: 10 Capítulo 2. Descripción del sistema y algoritmia: TSP Node + label : int + level : int + city : City + Node: + fill: void + convert-element : void Figura 2.6 Diagrama UML: Clase Node. 1. Node: Constructor de la clase. 2. fill: Dados los atributos como argumentos de entrada, define el nodo. 3. convert-element: Convierte un elemento a la clase Node. Más tarde explicaremos la clase Element. A nivel de código, los métodos de la clase Node se han definido de la siguiente manera en el anexo [A.2]. Path Los objetos definidos con la clase Node representaban las bifurcaciones en el árbol, y almacenaban las coordenadas de las ciudades del recorrido del viajero. Ahora, definiremos la unión entre dichas bifurcaciones; lo que serán porciones de la rama del árbol que representan los caminos que unen las bifurcaciones (los nodos). Para ello, daremos nombre a una nueva clase; la clase Path . En primer lugar, mostraremos el diagrama UML que ilustra esquemáticamente tanto los atributos como los métodos de la clase. Posteriormente, explicaremos brevemente en qué consiste cada campo. Path + origin-id: int + destiny-id: int + distance: float + Path: + fill: void Figura 2.7 Diagrama UML: Clase Path. •ATRIBUTOS: 1. origin-id: Entero que almacenará el id de origen del objeto definido. Posteriormente, asociaremos este identificador al identificador del nodo del que parte este camino. 2. destiny-id: Entero que almacenará el id de destino del objeto definido. Posteriormente, asociaremos este identificador al identificador del nodo al que llega este camino. 3. distance: Almacena la distancia recorrida en este camino. •MÉTODOS: 1. Path: Constructor de la clase. 2. fill: Dados los atributos como argumento de entrada, define el objeto de la clase Path. A nivel de código, los métodos de la clase Path se han definido de la siguiente manera, en el anexo [A.3]. 2.3 Método de implementación en ROS: empleo de clases 11 Branch Necesitamos crear un tipo de objeto nuevo que contenga tanto objetos tipo Node como objetos tipo Path , para saber por qué ciudades ha pasado el viajero, el orden en que las ha recorrido y la distancia que ha acumulado hasta ese momento. Necesitaremos objetos de la clase Node para conocer las dos primeras características de la rama, mientras que la distancia total de las ramas la obtendremos acumulando las distancias de los muchos objetos de la clase Path. De esta manera, se definirá la clase Branch , que tendrá una asociación con la clase Elements , la cual explicaremos en el próximo apartado. El diagrama UML de la clase Branch presenta esta forma: Branch + elements : deque <Element> + last-element : int vector<float> + Branch : + get-cities : vector<City> + get-route : vector<Node> + add-element : void + get-total-distance : float + get-total-distance-destiny-id : float + search-node : bool + search-path : bool Figura 2.8 Diagrama UML: Clase Branch. •ATRIBUTOS: 1. elements: Se trata de una cola que almacena los elementos que conforma la rama. Reseñaremos que los elementos pueden ser o bien objetos de la clase Node, u objetos de la clase Path. 2. last-element: Puede tomar tres valores "NODE", "PATH" o "-1", si no se encuentra definido. •MÉTODOS: 1. Branch: Constructor de la clase: inicializa "last-element" a "-1". Es decir, creamos una rama que aún no tiene elementos. 2. get-cities: Devuelve un vector con las ciudades de la rama que estamos considerando. Los elementos del vector (las ciudades) están ordenados desde el inicio del recorrido del viajero hasta la última ciudad de la rama. 3. get-route: Devuelve un vector con los nodos del recorrido de la rama que estamos considerando, hasta llegar al nodo de la rama que se toma como argumento de entrada de este método. 4. add-element: Inserta un elemento al final de la rama. Cuando indaguemos en el código de este método, se explicarán más detalles. 5. get-total-distance: Devuelve la distancia total de la rama, acumulando las distancias de los elementos que son Path. 6. get-total-distance-destiny-id: Devuelve la distancia de la rama hasta llegar a un objeto Path con el destiny-id especificado como argumento de entrada del método. 7. search-node: Nos dice si, en la rama considerada, se encuentra el nodo (objeto de la clase Node) que se toma como argumento de entrada del método. 8. search-path: Nos dice si, en la rama considerada, se encuentra el camino (objeto de la clase Path) que se toma como argumento de entrada del método. 12 Capítulo 2. Descripción del sistema y algoritmia: TSP El código de la cabecera de esta clase Branch tiene el siguiente aspecto, en el anexo [A.4]. Hay que señalar que el tamaño de las distintas ramas que se definen en el algoritmo no tendrán el mismo tamaño necesariamente. Esto significa que, en ciertas ocasiones, se pueden llevar a cabo inserciones de distintas ramas entre ellas, con el fin de conformar una sola rama quu abarque el recorrido completo del viajero, desde la ciudad de inicio hasta la ciudad de destino. Descripción del sistema y algoritmia: MTSP Introducción Una vez resuelto el problema del TSP, trataremos de complicarlo un poco considerando, en esta ocasión, varios viajeros que parten de una misma ciudad de inicio, se reparten las ciudades intermedias definidas en el espacio de una manera u otra (en función de los casos que se consideren, explicados más adelante) y, además, tratan de llegar cada uno a su respectiva ciudad destino. A esta variante del TSP la denominamos MTSP (Multiple Traveling Salesman Problem). Se tratará en profundidad la manera en la que hemos abordado el problema con los conceptos de clase introducidos en apartados anteriores, para implementar el algoritmo en ROS. Debido a que la idea empleada es similar al caso del MTSP resuelto con MATLAB, se explicará la nueva clase Mtsp para resolver esta variante, y de qué manera maneja los objetos del tipo WholeGraph que representan los grafos de cada viajero. MTSP: variantes consideradas Se considerarán tres variantes para resolver el Multiple Traveler Salesman Problem, definidas en función del tipo que tendrán las ciudades intermedias en el problema. Las ciudades intermedias podrán ser: •Ciudades Restringidas: aquellas en las que se sabe de antemano qué viajero debe pasar por ella. •Ciudades Auxiliares : aquellas que no tienen un viajero asignado de antemano para que pase por ellas. Es este tipo de ciudad la que hará que el algoritmo del MTSP deba barajar qué viajero debe pasar por qué ciudad intermedia. A continuación se explican brevemente cada uno de los casos considerados. Sólo ciudades restringidas Todas las ciudades intermedias del problema son restringidas y, por tanto, cada viajero ya tiene asignadas las ciudades por las que debe pasar hasta llegar a su destino. Resolver este problema equivale a resolver n problemas del viajero simples (TSP); uno para cada viajero del MTSP considerado. Sólo ciudades auxiliares En esta variante, todas las ciudades deben repartiese entre los distintos viajeros que definen el MTSP. En función del número total de viajeros (suponemos que es n ), se hará un reparto equitativo del número de ciudades auxiliares del problema ( aux ) entre los viajeros. En caso de que la división aux n no tenga resto, no habrá inconveniente y cada viajero tendrá el mismo número de ciudades auxiliares asignadas que cualquier otro. Si, por el contrario, el resto es mayor a 0, repartiremos dicho valor de manera equitativa entre los viajeros, sin mostrar especial preferencia en el reparto. Una vez asignado el número de ciudades intermedias a cada viajero, se resolverá el problema del TSP para cada viajero sucesivamente. 19 20 Capítulo 3. Descripción del sistema y algoritmia: MTSP ¿De qué manera? El primer viajero considerará aux1 ciudades auxiliares de entre todas las ciudades intermedias del MTSP . El siguiente viajero, considerará aux2 ciudades auxiliares solo que, a diferencia del caso anterior, no considera las ciudades intermedias ya asignadas a anteriores viajeros (primer viajero, en este caso) . Se procederá de esta manera, resolviendo el TSP para cada viajero hasta llegar al último viajero, que se enfrente al problema del viajero simple en el cual su número de ciudades auxiliares asignado coincide con el número de ciudades intermedias sobrantes (las que no se asignaron a viajeros anteriores en el reparto). Todo lo explicado se aprecia mucho mejor en el código, en el cual se define una lista con el número total de ciudades auxiliares de la que se van quitando aquellas que se van asignando a viajeros anteriores. Una vez que se obtenga un resultado con la distancia optimizada de cada viajero, se observará cual es el viajero con mayor distancia recorrida, y se asignará al viajero con menor distancia en el recorrido esa ciudad que retrasó al otro viajero. Se volverá a resolver el algoritmo con esta nueva asignación, e iremos procediendo de esta manera iterativamente hasta alcanzar un punto en el cual no se produzcan más mejoras. Ciudades restringidas y auxiliares En este caso, se consideran tanto ciudades restringidas para cada viajero como ciudades auxiliares a repartir. El reparto de las ciudades auxiliares se llevará a cabo de la manera que se explicó en el apartado anterior. Método de implementación en ROS: empleo de clases Tal y como se hizo en el apartado en el que se explicó el TSP simple, a continuación se explicará de qué manera se ha implementado en el lenguaje C la solución de este problema de optimización recurriendo al empleo de clases. Tan solo consideramos una clase, a la que se ha llamado Mtsp . En el próximo subapartado, explicaremos su significado, sus atributos asociados y los métodos que realizan modificaciones en los objetos de esta clase. Todas las explicaciones serán introductorias, ya que se indagará con mayor profoundidad en las secciones del código en un apartado posterior de la memoria. Mtsp En el anexo [A.8] se presenta el código de la cabecera de la clase Mtsp con el atributo y los métodos que definen la clase. •ATRIBUTOS: 1. min-distance: Vector en el que se almacenarán las distancias mínimas obtenidas para cada viajero. El orden de las componentes se corresponderá por el orden de los viajeros definidos inicialmente en el código. •MÉTODOS: 1. solve-only-res: Tomando las ciudades intermedias y las ciudades origen y destino del problema, además de otros parámetros que se explicarán en el siguiente apartado, se trata de resolver n problemas TSP. La variable res-ids almacena una serie de vectores, donde cada uno de ellos almacena los ids de las ciudades por los que debe pasar un viajero determinado. 2. solve-only-aux: También toma los mismos argumentos de entrada que el método anterior, reemplazando res-ids por aux-ids . El nuevo argumento del método hace alusión a los ids de las ciudades a repartir. Nótese que esta variable es un vector con los ids, mientras que res-ids era un vector de vectores enteros, ya que la componente iésima se correspondía con el viajero iésimo a resolver. En este propio método se hace el reparto, por lo que no existe una correspondencia inicial entre viajero e identificadores. 3. solve-aux-and-res: Se mezclan ambos métodos anteriores para resolver el problema conjunto. Una vez que se asignan ciudades auxiliares con los ids almacenados en res-ids , me olvido de dicha variable y realizo la asignación con aux-ids de la misma manera en la que se procedió en el método Mtsp::solve-only-aux. 3.3 Método de implementación en ROS: empleo de clases 21 4. solve-tsp: Se recurre a este método dentro del código de los tres anteriores. Define un vector de viajeros (objetos de la clase WholeGraph ). A cada componente de este vector (a cada viajero) se le asignan ciudades auxiliares y/o ciudades restringidas para resolver el problema del viajero con ellas. Una vez hecho esto, se vuelca en el vector return-cities-ids los ids de las ciudades por las que ha viajado cada viajero para obtener su mejor solución, considerando inicialmente todos los identificadores de las ciudades auxiliares por las que se puede pasar (aux-ids-list). Fichero principal Código En el anexo [A.9] se incluye el código del fichero principal de extensión ".cpp", en el cual se ha incluido la librería del MTSP para resolver el problema del viajero, con el procedimiento explicado hasta ahora. En él, se detalla de qué manera de ha llevado a cabo la declaración de las ciudades que se consideran en el problema del viajero. Así mismo, se detalla en el código asociado al hilo tsp-thread la declaración de los ids asociados a las ciudades auxiliares y a las ciudades restringidas, tomados en base a todas las ciudades declaradas previamente. Posteriormente, se resuelve el algoritmo con el método apropiado dentro de la clase Mtsp. Visualización RVIZ En este caso consideraremos un solo hilo, mediante el cual se trata de resolver el problema del MTSP con tres viajeros y únicamente ciudades restringidas. Como se señaló anteriormente, equivale a resolver tres TSP por separado. Se define un nuevo método en la clase Mtsp , con el cual se devuelven los ids de las ciudades por las que pasa cada viajero. A dicho método lo hemos llamado return-cit-ids. En el anexo [A.10] se definen, a nivel de código, las ciudades consideradas en esta visualización en RVIZ. Por otra parte, en el anexo [A.11] se especifican las líneas de código con las cuales se devuelven los ids mencionados anteriormente por la clase Mtsp. Ya que tenemos definidas las ciudades con sus coordenadas y sus respectivos identificadores al comienzo de este fichero principal, y que además conocemos los ids del resultado del algoritmo (volcados en la variable def-track-points), podemos visualizar en RVIZ fácilmente las ciudades por las que pasa cada viajero. Por un lado, el código que se encarga de representar en RVIZ el resultado del algoritmo sería el mostrado en el anexo [A.12]. El resultado, en este caso, quedaría de la siguiente manera: 23 24 Capítulo 4. Fichero principal Figura 4.1 Resultado en RVIZ con tres viajeros. 1,2.3 3,2 -7,2 7,-9 -2,9 5,5 5,-5 -9,5 0,1.1 Figura 4.2 Coordenadas de las ciudades. Resultados RVIZ. Se aprecia la representación de cada una de las rutas del viajero en un color distinto. En la segunda imagen, se especifican las coordenadas de cada ciudad y las rutas de los tres viajeros, en colores diferentes. El punto gris se corresponde con la ciudad de origen del viaje (común para todos los 4.2 Visualización RVIZ 25 viajeros), mientras que los puntos negros representan las ciudades de destino de cada una de las rutas. Por simplicidad en la representación del resultado, se ha supuesto que trabajamos en dos dimensiones, asignando un valor nulo a la tercera coordenada de las ciudades. Resultados de los algoritmos A continuación, se mostrarán ejemplos que se han puesto en el código principal tanto para TSP como para MTSP. En el caso del TSP, se mostrarán dos ejemplos: uno en el que se resuelve el Problema del Viajero con un solo hilo de ejecución, y otro caso en el que se resuelve el mismo problema con cuatro hilos de ejecución. Por otra parte, abordaremos el caso del MTSP con un solo hilo de ejecución. Se mostrarán los resultados de terminal para los tres casos: MTSP resuelto solo con ciudades restringidas, solo con ciudades auxiliares, o con ambas ciudades. Además, para todos los casos, se enseñará por terminal la salida que se obtiene con los resultados más significativos. TSP En el apartado anterior, en el que se mostraba el código principal, aparecía una sección de código en la que se definían como vectores las ciudades por las que pasaría el viajero (o varios viajeros, en el caso de que nos enfrentaśemos al MTSP). A lo largo de todo el apartado del TSP, consideraremos las mismas ciudades de origen y de destino, así como las siete ciudades intermedias que se detallan a continuación en el código. De dichas ciudades intermedias, tan solo usaremos algunas de ellas para resolver el Problema del Viajero, asignando los ids de ciudades restringidas. Todas las ciudades consideradas se definen de la forma especiifacada en el anexo [A.13]: A pesar de no comentarlo anteriormente, se define un hilo en el código en el cual hay un objeto de la clase MTPS con el cual se resuelve el problema de optimización. Se especifican, entre otros parámetros, ciudades restringidas del problema, número de iteraciones del algoritmo, etc. El código que define el hilo se encuentra en el anexo [A.14]. Señalemos que el mutex que toma el método Mtsp::solve-only-res como argumento de entrada se emplea para que la salida por pantalla de los resultados de los distintos hilos no se mezclen, y se puedan ver por separado en el terminal a la salida. Tsp con un solo hilo (Graph) Veamos la salida por terminal en el caso de que, con los ids de las ciudades restringidas especificados anteriormente, se resuelva el TSP simple. En lo referente al código, las líneas especificadas en el anexo [A.15] tienen asociadas la salida por terminala anterior. Comentemos los resultados más relevantes: • El tiempo de ejecución del algoritmo es de unos 12 milisegundos. Más adelante, compararemos con el caso multihilo para apreciar mejor la mejora que se verá posteriormente. • Ya que hemos considerado cuatro ciudades intermedias en el problema, se observa a la salida por terminal el número de posibles ramas: 4! =24. 27 28 Capítulo 5. Resultados de los algoritmos Figura 5.1 TSP: un solo hilo. • Hemos especificado, como número deseado de soluciones, 500. Es decir, que el algoritmo deberá ser capaz de obtener 500 ramas del grafo que se está considerando. Si hay menos soluciones, como ocurre en este caso, se obtendrá el máximo número de soluciones posible (24 en este caso). • Se muestran las ciudades en el orden en el que el viajero las recorre. La primera ciudad que se muesta es el origen, mientras que la última es el destino. Se van mostrando a la derecha de cada ciudad la distancia que se acumula con respecto la ciudad anterior, en unidades. • Después, se muestra la distancia asociada a la mejor solución encontrada, el id de la rama con dicha solución, y por último el número de ciudades intermedias consideradas en el problema. Con el fin de visualizar con mayor claridad la solución, a continuación se muestra el árbol de nodos que representa la solución que se considera. 1 2 6 1 1 1 1 1 1 1 13 1 1 1 1 5 1 1 1 1 6 3 1 1 1 1 2 1 1 1 1 7 1 1 1 1 8 4 1 1 1 1 3 1 1 1 1 9 1 1 1 1 10 5 1 1 1 1 4 1 1 1 1 11 1 1 1 1 12 Figura 5.2 Solución del TSP en el caso de un solo hilo. Los nodos que aparecen en el esquema anterior conforman las ramas que definen el árbol de nodos hasta ese momento. Aparece destacada la rama que tiene asociada la solución mostrada por terminal anteriormente (la mejor de todas). En violeta, aparecen numeradas las ramas completas del grafo, en el orden en el que se crean hasta llegar a la solución final. Aunque el árbol se siga desarrollando hasta obtener todas las soluciones, se ha mostrado el esquema anterior con el fin de ilustrar de qué manera se va desglosando hasta llegar a nuestra solución. De hecho, en azul están numerados los nodos que se han desglosado hasta ese momento. Métodos implementados en el algoritmo A lo largo de este apartado, iremos presentando los métodos asociados a cada una de las clases con las que se ha implementado el Problema del Viajero en el lenguaje de programación C. Llevaremos a cabo una descripción más exhaustiva del código que la que hemos hecho en los apartados anteriores, en los cuales tan sólo presentábamos las clases y mencionábamos los métodos que se definían. Clase "City" fill La sección de código correspondiente aparece referenciada en el anexo [A.21]. Con este método, asignamos valores a los atributos de la clase City. get-string-data La sección de código correspondiente aparece referenciada en el anexo [A.22]. Devuelve una cadena con dos componentes; en la primera de ellas, el id de la ciudad considerada, miestras que en el segundo elemento aparecen las coordenadas de la ciudad en cuestión. Clase "Node" fill La sección de código correspondiente aparece referenciada en el anexo [A.23]. Con este método, asignamos valores a los atributos de la clase Node. convert-element La sección de código correspondiente aparece referenciada en el anexo [A.24]. Dado un objeto del tipo Element como argumento del método, volcamos en los atributos del nodo considerado los campos del elemento de entrada. Este método se encarga de inicializar un nodo a partir de un objeto del tipo Element. Clase "Path" fill La sección de código correspondiente aparece referenciada en el anexo [A.25]. Con este método, asignamos valores a los atributos de la clase Node. 35 36 Capítulo 6. Métodos implementados en el algoritmo Clase "Branch" add-element La sección de código correspondiente aparece referenciada en el anexo [A.26]. Añade un elemento a la rama considerada. Es decir, volcamos en el componente último del atributo elements el elemento a añadir, considerando lo siguiente: •El primer elemento de elements (la rama considerada) siempre debe ser un nodo. • Los elementos añadidos han de ser del tipo opuesto al del último elemento añadido al atributo. Es decir, elementos del tipo Node y del tipo Path deben ir alternándose conforme se añaden a la rama. get-total-distance La sección de código correspondiente aparece referenciada en el anexo [A.27]. Recorre todos los elementos de la rama considerada, con el fin de acumular las distancias de cada uno de los caminos que ha tomado el viajero. Para ello, en el bucle de iteración, solo se consideran los elementos que se corresponden con caminos. get-total-distance-destiny-id La sección de código correspondiente aparece referenciada en el anexo [A.28]. Devuelve la distancia acumulada en los caminos de la rama, hasta llegar al id especificado como argumento del método . Hay que señalar que se empiezan a acumular distancias de los viajes desde la ciudad origen, hasta llegar al elemento de la clase Node con el id especificado. get-cities La sección de código correspondiente aparece referenciada en el anexo [A.29]. Devuelve un vector de tipo City con las ciudades por las que el viajero ha pasado, de la rama considerada. Para lograrlo, se consideran los elementos Node y se toma su atributo asociado a la clase City. search-node La sección de código correspondiente aparece referenciada en el anexo [A.30]. Devuelve true o false en función de si el nodo que toma el método como entrada se encuentra en la rama considerada. Este método resulta bastante útil si se desea encontrar un nodo determinado en el árbol completo; basta con aplicarlo a todas las ramas que almacene el árbol. search-path La sección de código correspondiente aparece referenciada en el anexo [A.31]. Devuelve true o false en función de si el camino que toma el método como entrada se encuentra en la rama considerada. Como comentamos para el método anterior, este método resulta bastante útil si se desea encontrar un camino determinado en el árbol completo; basta con aplicarlo a todas las ramas que se encuentren almacenadas en el árbol. get-route La sección de código correspondiente aparece referenciada en el anexo [A.32]. Devuelve un vector con los nodos de la rama que forman parte de la ruta hasta llegar al nodo n, que es el argumento de entrada del método . En este método, se emplea Node::convert-element para convertir los elementos nodos de la rama a objetos de la clase Node. Clase "Graph" Graph (constructor) La sección de código correspondiente aparece referenciada en el anexo [A.33]. Se explicará por orden las secciones de código empleadas para definir el constructor: 6.5 Clase "Graph" 37 • Almacenamos en cities (atributo de la clase Graph) todas las ciudades del viaje completo del viajero, incluyendo origen y destino. •Se inicializa la base de datos con el nodo padre. •Se inializan los punteros del viajero y de desglose (traveler ybreak-down, respectivamente). •Se crea la primera rama del grafo. •Se ejecuta el algoritmo principal en este mismo constructor (main-algorithm). explore-and-order La sección de código correspondiente aparece referenciada en el anexo [A.34]. Por sencillez, se irán mencionando las secciones del código que se presenta, con su número de línea correspondiente, para hacer alusión a cada una de las partes que se vaya comentando a continuación: •Líneas 2-8: Se definen, en este orden: – res: Salida que almacenará los nodos y los caminos obtenidos en este método. – route: Vector que almacena los nodos por los que se ha pasado hasta llegar hasta donde se encuentra el viajero en este momento. – El resto de variables se irán comentando posteriormente, conforme se vayan empleando en el método. •Líneas 10-13 : Se define una lista en la que se vuelcan las ciudades almacenadas en el grafo. Se emplea una lista como variable local de este método por mayor facilidad en eliminar elementos determinados durante su uso. •Líneas 15-17 : En la lista de ciudades que se acaba de definir ( list-of-cities ), descartamos aquellas por las que el viajero ya ha pasado. •Líneas 21-29 : Se crean tanto nodos como caminos (almacenados, respectivamente, en nodes-created ypaths-created) con la información asociada a la lista de ciudades definida anteriormente. •Líneas 33-50 : Mientras quede algún nodo o camino almacenado en sus respectivas listas ( nodescreated ypaths-created), se llevan a cabo las siguientes instrucciones: – Buscamos el camino de la lista con la distancia mínima, de entre todos los caminos creados. Lo almacenamos en el iterador path-it. – Posteriormente, se busca el nodo que tenga la misma etiqueta que la etiqueta origen del camino almacenado en path-it. – Añadimos a nodes-right y paths-right los objetos ordenados por menor distancia. Eliminamos de las listas desordenadas los objetos que acabamos de añadir a las listas ordenadas, con el fin de no volver a considerarlos en posteriores iteraciones del bucle while. •Líneas 52-54: Devolvemos res, con los caminos y nodos ordenados. distance-between-nodes La sección de código correspondiente aparece referenciada en el anexo [A.35]. Dados dos nodos a la entrada, se calcula y devuelve a la salida el módulo de la distancia entre sus ciudades almacenadas. travel-nearest-city La sección de código correspondiente aparece referenciada en el anexo [A.36]. Por sencillez, se irán mencionando las secciones del código que se presenta, con su número de línea correspondiente, para hacer alusión a cada una de las partes que se vaya comentando a continuación: •Línea 3 : Se definen dos listas en las que se vuelcan los nodos y caminos obtenidos del desglose del nodo del viajero, realizado con el método Graph::explore-and-order. •Línea 8: Añadimos el nodo viajero a la rama del grafo (su atributo branches). 38 Capítulo 6. Métodos implementados en el algoritmo •Líneas 11-13 : Buscamos el mínimo camino que parta del nodo en el que se encuentra el viajero (al que apunta traveler) y lo almacenamos en p-it. •Línea 16: Añadimos dicho camino a la rama del grafo. •Líneas 19-20 : Buscamos el nodo con el mismo id que el atributo id-destiny del camino mínimo que hemos encontrado anteriormente, y lo guardamos en el iterador n-it. •Líneas 24-25 : Se realiza una búsqueda en la base de datos de nodos del grafo ( nodes ). Buscamos el nodo almacenado en n-it , y modificamos la dirección de memoria del puntero traveler por la de este nuevo nodo. •Líneas 28: Añadimos a la rama del grafo este último nodo. A modo de resumen, observamos que con este método actualizamos la dirección de memoria del puntero viajero conforme se va viajando a la siguiente ciudad. Además, se van insertando en la rama del grafo los elementos correspondientes que van definiendo el viaje hasta el momento. Cabe señalar que, ya que empleamos el método Branch::add-element , en caso de que queramos insertar el nodo del viajero de la siguiente iteración una vez que acabamos de insertar el mismo nodo en la iteración anterior, no podremos hacerlo, y el siguiente elemento insertado en la rama será el próximo camino. refresh-graph-data La sección de código correspondiente aparece referenciada en el anexo [A.37]. En este método, se llevan a cabo las siguientes modificaciones en el árbol: • Se modifica la dirección de memoria del puntero move-bd en función de si decidimos hacerlo o no durante la ejecución de Graph::main-algorithm . Una vez que epliquemos el algoritmo principal en este mismo apartado, se comprenderá mejor en qué caso cambiamos el puntero de desglose. •Actualizamos la dirección de memoria del puntero del viajero, traveler. • Creamos una nueva rama en el árbol, con el fin de llenar sus elementos en las iteraciones posteriores de Graph::main-algorithm. •Reseteamos las bases de datos, tanto paths como nodes. •Insertamos el primer nodo en la base de datos; será el nodo al que apunta el puntero del viajero. •Tanto break-down como traveler apuntan a dicho nodo que se ha insertado en la base de datos. remove-branches-elements La sección de código correspondiente aparece referenciada en el anexo [A.38]. Este método se aplica justo después de Graph::explore-and-order . Su cometido principal consiste en eliminar de los elementos de entrada (nodos y caminos) aquellos objetos que ya formen parte de otras ramas creadas hasta ahora. ¿Por qué es importante este método? Porque todas las ramas nuevas que se vayan creando deben ser distintas a las creadas anteriormente, ya que que vamos buscando soluciones nuevas constantemente. En el caso de que todavía no se hayan creado ramas anteriormente, este método no modifica de manera alguna el atributo que almacena las ramas del grafo; branches. Por sencillez, se irán mencionando las secciones del código que se presenta, con su número de línea correspondiente, para hacer alusión a cada una de las partes que se vaya comentando a continuación: •Líneas 11-15: Se eliminan los nodos que formen parte de otras ramas anteriores del grafo. •Líneas 18-22: Se eliminan los caminos que formen parte de otras ramas anteriores del grafo. •Líneas 25-27: Se actualiza la base de datos de los nodos. •Líneas 30-32: Se actualiza la base de datos de los caminos. •Líneas 34: Devuelvo los nodos y los caminos almacenados en la variable local ret-elements. 6.5 Clase "Graph" 39 break-down-son La sección de código correspondiente aparece referenciada en el anexo [A.39]. Con este método, devolvemos el identificador adecuado para seguir etiquetando a los nodos que se seguirán creando en el grafo. En primer lugar, buscamos la rama en la que se encuentre el nodo al que apunta break-down . Una vez que la hayamos encontrado, guardamos en el iterador e-it el elemento que se corresponde con el nodo al que apunta el puntero de desglose. Hay que tener en cuenta que, considerando el orden en el que se han ido defieniendo las ramas del grafo, se asegura que este método devolverá el hijo del nodo de desglose con el camino de la menor distancia. En caso de que no se haya encontrado el nodo con la dirección de break-down , el método devuelve un -1 . create-branch La sección de código correspondiente aparece referenciada en el anexo [A.40]. Llegamos al método que crea las ramas del árbol. Analizaremos paso a paso las secciones del código y comentaremos el cometido de las variables más importantes que se declaran al comienzo. Antes de ello, es importante resaltar lo siguiente. Las ramas del grafo almacenadas en branches no tienen por qué abarcar todo el recorrido del viajero. El primer nodo de la primera rama almacenará la ciudad de origen del viaje, y el último nodo de dicha rama almacenará la ciudad de destino. Sin embargo, conforme vamos creando mas y más ramas, su longitud disminuye, ya que el primer nodo de las mismas tienen asignado un nivel más profundo en el grafo. Una imagen que intenta ilustrar esta explicación puede tener la siguiente forma: 1 2 5 11 17 6 12 18 3 7 13 19 8 14 20 4 9 15 21 10 16 22 Figura 6.1 Subramas en el caso de tres ciudades intermedias. En cuanto a la imagen anterior, las tres ramas azules que parten del nodo padre del grafo son las tres primeras ramas creadas en el grafo. Estamos desglosando el NODO 1, por lo que estamos obteniendo ramas que parten de dicho nodo hasta la ciudad de destino (nodos 17,19 y 21, respectivamente). Una vez desglosado el NODO 1, tratamos de hacer lo mismo con el NODO 2. Como la primera rama pasa por el NODO 2, cuando tratemos de desglosar dicho nodo tan solo obtendremos una rama. Dicha rama tendrá como nodo final el NODO 18, y partirá del NODO 2. Es una de las ramas que aparece representada en rojo, más corta que las tres anteriores. En el caso en el que nos encontremos ante un grafo con más ciudades intermedias, los desgloses de los nodos irán asociados con una creación de ramas cada vez más cortas. Esto se traduce en una menor carga de información almacenada por el programa (lo cual es una ventaja). Comencemos a abordar el código que se presenta a continuación: •El código se compone por un bucle do-while , sujeto a una condición que depende del cumplimiento de una expresión booleana, llamada c . Esta condición estará definida de una manera u otra según se aborde el problema del TSP simple o el problema con múltiples viajeros y múltiples ciudades destino; el MTSP. En concreto, dependerá de una variable externa a este método, threshold. 40 Capítulo 6. Métodos implementados en el algoritmo Dicha variable define el nivel límite hasta el cual queremos que las ramas del grafo almacenen elementos. Dicho de otra manera, con threshold decidimos cuántas ciudades intermedias queremos incluir en el problema. En función de esto, hay una condición if-else dentro de este bucle que distingue dos casos: – Añado la ciudad de destino a la rama y la doy por finalizada ( líneas 11-24 ). En este caso, el viajero apunta al nodo con el nivel denotado por threshold. – Se van creando las ramas en el caso de que el viajero no haya llegado a threshold ( líneas 25-42 ). Dicho esto comentaremos ambas condiciones. •Líneas 11-24: 1. Creamos el nodo n que almacene la ciudad destino del viajero; lo incluimos en la base de datos nodes y hacemos que el puntero traveler apunte a dicho nodo de la base de datos. 2. Del mismo modo, creamos el camino p que crea el tramo que tiene como destiny-id la etiqueta asociada al nuevo nodo del viajero. 3. Añadimos el camino py el nodo nal la rama actual. 4. Definimos la condición c: el bucle while se ejecuta mientras el número de elementos de la rama actual sea menor al tamaño deseado de la rama, teniéndose en cuenta desde dónde se empieza el desglose (break-down) y el valor de threshold. •Líneas 25-42: 1. En primer lugar, refrescamos la variable global-node-id en función del nodo al que apunte breakdown . En el caso de que apunte al nodo del viajero, el global-node-id con el que se etiquetan los nuevos nodos toma el valor del id del hijo de break-down , como se comentó en el método Graph::break-down-son . En otro caso, se toma el id con el que se etiquetó al último nodo para seguir etiquetando al resto. 8 2 5 8 5 6 2 2 3 2 2 2 2 2 2 4 2 2 2 2 2 2 Figura 6.2 Numeración de ramas: viajero y desglose en distintos nodos. En la figura anterior, se ilustra el caso en el cual el puntero de desglose (marca roja) tiene una dirección distinta a la del puntero del viajero (marca azul). Por ello, a la hora de hacer el próximo desglose, se tomará el último identificador que se ha asignado a un nodo en la base de datos, en este caso el número 6 (marcado en rojo). De esta manera, el nodo actual al que apunta el viajero se numera con un 7 y se sigue incrementando el indicador hasta completar la rama actual. Hay que señalar que en el grafo representado tan solo se han creado los nodos numerados (y los caminos que unen los nodos existentes entre sí). Aquellos que no aparecen sombreados y que están numerados, se corresponden con los nodos que solo pertenecen a la base de datos de la rama actual . Por otro lado, los nodos que aparecen sombreados pertenecen a la rama actual (y también a los de la base de datos, que se crearon antes). Para los caminos, se aplica el mismo razonamiento. 6.5 Clase "Graph" 41 88 2 5 7 8 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 Figura 6.3 Numeración de ramas: viajero y desglose en el mismo nodo. En la segunda imagen del grafo, se contempla el caso en el que el viajero y el desglose apuntan al mismo nodo. Por ello, se toma como último identificador aquel que se corresponde con el primer nodo hijo del nodo de desglose actual. Se procede de esta manera porque hay que crear una nueva base de datos, ya que se empieza a crear una nueva rama que parte desde el nodo padre del grafo. De esta manera, se numeran los nodos del segundo nivel de manera idéntica con respecto a la imagen anterior, y los nodos adquieren un identificador unívoco en el grafo. 2. Creo caminos y nodos desglosando el nodo del viajero actual. En caso de que no obtenga elementos en elements-created , significa que que he llegado al final de la rama y que debo cambiar la dirección del puntero de desglose break-down. 3. Actualizamos el id de numeración de los nodos, en función de la consideración previa que se ha llevado a cabo con respecto a los hijos de break-down. 4. Definimos la condición c: el bucle while se ejecuta mientras el número de elementos de la rama actual sea menor al tamaño deseado de la rama, teniéndose en cuenta desde dónde se empieza el desglose (break-down). move-break-down La sección de código correspondiente aparece referenciada en el anexo [A.41]. Actualizamos el valor del puntero de desglose; apuntará al nodo con su identificador una unidad mayor que el nodo de desglose actual. print-results No es necesario mostrar código; imprime los valores más significativos que resultan de ejecutar el algoritmo del TSP. get-total-distance La sección de código correspondiente aparece referenciada en el anexo [A.42]. Devuelve la distancia total de la rama del grafo que tenga el identificador branch-id. Comentaremos las secciones más reseñables del código: •Líneas 7-13 : Se definen los condiciones booleanas minor y equal , las cuales se emplearán más adelante en el propio código. 1. Líneas 7-10 : En caso de que el límite threshold no tome el valor del último nivel del grafo, se define las condiciones equal y minor como verdadera siempre y cuando el número de elementos de la rama actual sea menor al deseado considerando el threshold. 2. Líneas 11-13 : En caso de que no se considere threshold (y, por tanto, su valor coincidiese con el último nivel del grafo) se definen minor yequal sin considerarse el valor del threshold. 42 Capítulo 6. Métodos implementados en el algoritmo •Líneas 19-32 : En caso de que la rama tenga elementos y de que se cumpla minor , añadimos al acumulador ret-distance la distancia de la rama actual. Posteriormente, trataremos de buscar en todas las ramas del grafo hasta encontrar una rama con un camino con el destiny-id que sea igual al origin-id del primer camino de la última rama considerada; de id branch-id-aux. Con la siguiente imagen, trataremos de ilustrar cómo queremos obtener la distancia total de la rama, partiendo del nodo destino hasta llegar al nodo origen, buscando ramas intermedias con coincidencias de id. 1 2 5 11 17 6 12 18 3 7 13 19 8 14 20 4 9 15 21 10 16 22 Figura 6.4 Elementos de una rama completa del grafo. Una vez que lleguemos a una rama en la que su primer nodo sea el nodo padre del grafo, significa que ya tenemos la distancia total del viaje y que podemos devolver la distancia total acumulada. •Líneas 35-38 : Si se cumple equal, significa que la rama en la que estamo contiene los nodos que almacenan, respectivamente, la ciudad origen y la ciudad destino. •Líneas 41-42 : En caso de que la rama esté vacía (sin elementos), devuelvo un 0 en la distancia total acumulada. get-route La sección de código correspondiente aparece referenciada en el anexo [A.43]. Como se comentó en apartados anteriores con menor detalle, con Graph::get-route pretendemos devolver un vector con los nodos que conforman la ruta del viajero hasta llegar al nodo n , que es la entrada del método considerado. Básicamente, buscamos en las ramas que conforman el grafo de manera similar a como hacíamos en Graph::get-total-distance , solo que ahora no consideramos los caminos de las ramas, sino los nodos. Dichos nodos se van añadiendo al vector que devolvemos a la salida; out-. main-algorithm La sección de código correspondiente aparece referenciada en el anexo [A.44]. Algoritmo principal, que implementa la mayoría de los métodos explicados hasta el momento. Analicemos las líneas más importantes del código: •Línea 12 : Damos valor a begin , para contabilizar el tiempo de ejecución del algoritmo posteriormente. •Líneas 15-17 : Definimos el factorial-value , que nos da información acerca del número de posibles soluciones del problema del viajero. Lo hemos llamado de esta manera aunque realmente no sea un factorial; factorial-value toma el valor del factorial del número de ciudades intermedias consideradas en el problema, que no tiene por qué coincidir con el número de ciudades intermedias totales . La distinción entre ambas consideraciones la lleva a cabo la variable threshold , tal y como se contempla en las líneas de código. 6.6 Clase "WholeGraph" 43 •Líneas 20-25 : Bucle encargado de la creación de una rama en el grafo. También se vuelca en distances el valor de la distancia total asociada a la rama asociada, considerando la explicación que se dio con respecto al funcionamiento de Graph::get-total-distance . El bucle do-while sigue creando ramas mientras el número de ramas creadas no haya alcanzado el número deseado, o mientras dicho número no haya llegado al número de soluciones posibles del problema. •Líneas 31-35 : Por un lado, se almacena en f-it el número de componente del vector distances con la distancia mínima conseguida y, por tanto, asociado a la mejor solución. Por otro lado, almaceno en n el nodo de la rama asociada a la mejor solución, y obtengo la ruta completa del viajero usando Branch::get-route. route-output La sección de código correspondiente aparece referenciada en el anexo [A.45]. Se encarga de devolver la ruta de nodos que conforma la solución del problema del viajero. Se almacena en el atributo denominado route-out. min-distance-output La sección de código correspondiente aparece referenciada en el anexo [A.46]. Devuelve la distancia mínima asociada a la mejor solución del algoritmo. Tanto este método como el del apartado anterior se implementaron con el fin de emplearse en la clase WholeGraph. Clase "WholeGraph" output-little-branches Muestra la salida de los resultados más significativos del algoritmo para el caso en el que se emplean varios hilos. output-whole-graph La sección de código correspondiente aparece referenciada en el anexo [A.47]. Muestra la salida de los resultados más significativos del algoritmo para el caso en el que se emplea un solo hilo hilos. main-algorithm La sección de código correspondiente aparece referenciada en el anexo [A.48]. Algoritmo principal de la clase WholeGraph. En función del valor de sub-branch-id , resolveremos el grafo completo o ramificaciones concretas del mismo. Se ha supuesto que, en caso de que su valor sea 99, se resuelve el grafo completo . En el caso de que sub-branch-id tome el valor de un id asociado a alguna de las ciudades del tsp, se resolveran solo las ramificaciones del árbol con el nodo hijo del nodo padre que tenga sub-branch-id como identificador de su ciudad . Dicho de otra manera; en este caso se resuelve el tsp partiendo de uno de los hijos del nodo con la ciudad origen. De esta manera, no se consideran las soluciones vinculadas a los otros hijos del nodo con la ciudad de origen, ya que parten de otras ramas. 44 Capítulo 6. Métodos implementados en el algoritmo Con las siguientes imágenes, se ilustra la explicación anterior: 1 2 5 11 15 6 12 16 3 7 13 17 8 14 18 4 9 19 19 10 21 20 Figura 6.5 Grafo del viajero completo. 1 2 5 11 15 6 12 16 3 7 13 17 8 14 18 4 9 19 19 10 21 20 Figura 6.6 División en subramas del grafo del viajero. A lo largo de todo el código presentado, se definen listas locales en las que se manejan las ciudades intermedias del problema de manera que se consideren aquellas adecuadas en cada uno de los casos que define sub-branch-id. add-aux-cities La sección de código correspondiente aparece referenciada en el anexo [A.49]. Añade ciudades auxiliares en aux-cities. Dichas ciudades se especifican a la entrada. add-res-cities La sección de código correspondiente aparece referenciada en el anexo [A.50]. Añade ciudades restringidas en res-cities. Dichas ciudades se especifican a la entrada. Clase "Mtsp" solve-only-res La sección de código correspondiente aparece referenciada en el anexo [A.51]. Conclusiones Comparando con la solución desarrolada anteriormente en el entorno de MATLAB, se puede afirmar lo siguiente: •No se emplea una base de datos enorme , sino que se almacenan las ramas dentro de cada grafo. Tan solo se emplea una base de datos al definir cama rama, en la clase Graph. • Con respecto a MATLAB, se emplean hilos (que aportan concurrencia) para poder resolver el mismo problema en menor tiempo para el mismo número de soluciones deseado. Ejecución paralela del código en lugar de secuencial. • En el caso en el que nos encontremos ante un grafo con muchas ciudades intermedias, los desgloses de los nodos irán asociados con una creación de ramas cada vez más cortas. Esto se traduce en una menor carga de información almacenada por el programa (lo cual es una ventaja). • En lugar de considerar todos los datos almacenados en una base de datos de nodos (lo que se hacía en MATLAB), en esta ocasión se define serie de clases para crear objetos que operen y almacenen sobre los datos más cruciales. Permite diferenciar tareas de alto y bajo nivel. Una vez enumeradas estas mejoras, a modo de conclusión, se puede establecer que con esta nueva menera de abordar el algoritmo del Problema del Viajero se obtienen: •Más soluciones en menor tiempo, sirviéndonos del paralelismo que nos proporcionan varios hilos. •Menor información asociada a las soluciones , debido a que almacenamos la información más relevante en objetos del tipo rama, y que su longitud disminuye conforme avanza el algoritmo que recorre el grafo. 51 Posibles mejoras De entre las principales mejoras que se podrían llevar a cabo, partiendo de la solución y los resultados propuestos a lo largo de esta memoria, se pueden considerar las siguientes: • Emplear un número de hilos que se adecúe al procesador del ordenador para resolver el problema del viajero de la manera más eficiente posible (bajo coste computacional para el mayor número de soluciones posible). • Volviendo al tema de los hilos, considerar que se puede emplear esta técnica para niveles inferiores del grafo. Es decir, en lugar de resolver las ramas principales del grafo (asociadas a las ciudades/nodos del primer nivel), emplear hilos para subramas del segundo o tercer nivel. • En el caso del MTSP con ciudades auxiliares, mejorar el reparto de ciudades entre viajeros. En vez de hacerse de manera aleatoria, averiguar qué ciudad retrasa más a cada viajero para cederla a otro viajero. De la misma manera, podría considerarse a qué viajero perjudica menos obtener una ciudad cedida, sin tener por qué ser el viajero con menos coste asociado a su solución. •Usar varios UAVS en el caso de la simulación en GAZEBO y resolver un MTSP. 53 Anexo I: Código empleado Clases del TSP Código A.1 Declaración de clase City. 1 2class City 3{ 4 5public: 6int id; 7std::vector<float> city; 8 9// For using "find_if" with cities 10 bool operator == (const City& s) const {return city == s.city && id == s.id; } 11 bool operator != (const City& s) const {return !operator==(s); } 12 13 void fill(int id_, std::vector<float> city_); 14 std::vector<std::string> get_string_data(); 15 }; Código A.2 Declaración de clase Node. 1 2class Node: public Element { 3public: 4Node(){element_type=NODE;} 5 6// For using "find_if" with nodes 7bool operator == (const Node& s) const {return label == s.label && city == s. city && level == s.level; } 8bool operator != (const Node& s) const {return !operator==(s); } 9 10 void fill(City city_,int label_,int level_); 11 void convert_element(Element e); 12 }; 55 56 Capítulo A. Anexo I: Código empleado Código A.3 Declaración de clase Path. 1 2class Path: public Element { 3public: 4Path(){element_type=PATH;} 5 6// For using "find_if" with paths 7bool operator == (const Path& s) const {return origin_id == s.origin_id && destiny_id == s.destiny_id && traveled == s.traveled && distance == s. distance; } 8bool operator != (const Path& s) const {return !operator==(s); } 9bool operator < (const Path& s) const {return distance < s.distance; } 10 11 void fill(int origin_id_,int destiny_id_,bool traveled_,float distance_); 12 }; Código A.4 Declaración de clase Branch. 1 2class Branch 3{ 4public: 5std::deque<Element> elements; 6int last_element; // "NODE" "PATH" or "-1" 7 8// CONSTRUCTOR 9Branch(){ finished=false; last_element=-1; } 10 11 std::vector<City> get_cities(); 12 std::vector<Node> get_route(Node n); 13 void add_element(Element e); 14 float get_total_distance(); 15 float get_total_distance_destiny_id(int d_id); 16 bool search_node(Node n); 17 bool search_path(Path n); 18 19 }; Código A.5 Declaración de clase Element. 1 2class Element { 3public: 4int element_type=-1; // NODE or PATH 5// PATH CLASS DATA 6int origin_id=-1; 7int destiny_id=-1; 8bool traveled=-1; 9float distance=-1; 10 // NODE CLASS DATA 11 int label=-1; 12 int level=-1; 13 City city; 14 }; A.1 Clases del TSP 57 Código A.6 Declaración de clase Graph. 1 2class Graph 3{ 4private: 5 6Node * traveler; 7Node * break_down; 8std::deque<Node> nodes; 9std::deque<Path> paths; 10 int global_node_id, global_path_id; 11 int branches_id; 12 13 public: 14 std::vector<Branch> branches; 15 std::vector<City> cities; 16 17 // OUTPUT VARIABLES 18 int n_branches_private; 19 int factorial=1; 20 std::vector<float> distances; 21 int level_; 22 std::vector<Node> route_out; 23 ros::Time begin; 24 float min_distance; 25 26 Graph(std::vector<City> origin, 27 std::vector<City> cities, 28 std::vector<City> destiny, 29 int n_branches,std::mutex &mtx, int level__,int &threshold); // CONSTRUCTOR 30 void print_nodes_data_base(); 31 void print_paths_data_base(); 32 void print_data_base(); 33 std::pair<std::list<Node>,std::list<Path>> explore_and_order(); 34 float distance_between_nodes(Node n1, Node n2); 35 void travel_nearest_city(std::pair<std::list<Node>,std::list<Path>> elements); 36 void main_algorithm(int n_branches,std::mutex &mtx, int level__,int &threshold); 37 std::pair<std::list<Node>,std::list<Path>> remove_branches_elements(std::pair<std:: list<Node>,std::list<Path>> elements); 38 39 int break_down_son(); 40 void create_branch(int &global_node_id_saved,int &move_bd,int &threshold); 41 void refresh_graph_data(Element e, Node n,Node save_traveler,int &move_bd ,std:: vector<float> &distances,int &threshold); 42 void move_break_down(); 43 std::vector<Node> get_route(Node n); 44 std::vector<int> print_results(std::mutex &mtx,int &threshold); 45 float get_total_distance(int branch_id_,int &threshold); 46 47 // OUTPUT METHODS 48 std::vector<Node> route_output(); 49 float min_distance_output(); 50 }; 58 Capítulo A. Anexo I: Código empleado Código A.7 Declaración de clase WholeGraph. 1 2class WholeGraph 3{ 4private: 5 6public: 7 8std::vector<City> res_cities; 9std::vector<City> aux_cities; 10 float min_distance; 11 12 void output_little_branches(Graph up, Graph down,std::mutex &mtx); 13 std::vector<int> output_whole_graph(Graph down,std::mutex &mtx,int &threshold); 14 std::vector<int> main_algorithm(std::vector<std::vector<float>> origin, 15 std::vector<float> destiny,int cities_size, 16 int sub_branch_id,int iterations, 17 std::mutex &mtx,int number_cities_traveled); 18 19 void add_aux_cities(std::vector<City> cities,std::vector<int> ids_to_include); 20 void add_res_cities(std::vector<City> cities,std::vector<int> ids_to_include); 21 22 }; Clases del MTSP Código A.8 Declaración de clase Mtsp. 1 2class Mtsp 3{ 4 5public: 6 7std::vector<float> min_distances; 8 9void solve_only_res(std::vector<std::vector<float>> origin, 10 std::vector<std::vector<float>> cities, 11 std::vector<std::vector<float>> destiny, 12 int sub_branch_id,int iterations, 13 std::vector<std::vector<int>> res_ids,std::mutex &mtx); 14 15 void solve_only_aux(std::vector<std::vector<float>> origin, 16 std::vector<std::vector<float>> cities, 17 std::vector<std::vector<float>> destiny, 18 int sub_branch_id,int iterations, 19 std::vector<int> aux_ids,std::mutex &mtx); 20 21 void solve_aux_and_res(std::vector<std::vector<float>> origin, 22 std::vector<std::vector<float>> cities, 23 std::vector<std::vector<float>> destiny, 24 int sub_branch_id,int iterations, 25 std::vector<std::vector<int>> res_ids, 26 std::vector<int> aux_ids,std::mutex &mtx); 27 28 void solve_tsp(std::vector<std::vector<float>> &origin, 29 std::vector<std::vector<float>> &cities, A.3 Código del fichero principal 59 30 std::vector<std::vector<float>> &destiny, 31 int sub_branch_id,int iterations, 32 std::vector<int> &aux_ids, 33 std::vector<std::vector<int>> &res_ids, 34 std::mutex &mtx, 35 std::vector<City> &c, 36 std::vector<std::vector<int>> &return_cities_ids, 37 std::vector<int> &cities_to_travel, 38 std::list<int> &aux_ids_list); 39 40 41 }; Código del fichero principal Código A.9 Fichero principal: codigo-principal.cpp. 1 2#include "mtsp_files/clases/Mtsp.h" 3 4using namespace std; 5using std::vector; 6 7std::mutex mtx; 8 9// Required in order to split .txt data 10 void split(const string &s, char delim, vector<string> &elems) { 11 stringstream ss(s); 12 string item; 13 while (getline(ss, item, delim)) { elems.push_back(item);}} 14 vector<string> split(const string &s, char delim) { 15 vector<string> elems; 16 split(s, delim, elems); 17 return elems;} 18 19 20 21 int main( int argc, char** argv ){ 22 23 ros::init(argc, argv, "codigo_principal"); 24 ros::NodeHandle n; 25 ros::Publisher marker_pub = n.advertise<visualization_msgs::Marker>(" visualization_marker", 10); 26 ros::Rate r(30); 27 float f = 0.0; 28 29 // Defining vectors with CITIES, ORIGIN and DESTINY 30 std::vector<std::vector<float>> origin, destiny; 31 std::vector<std::vector<float>> cities; 32 33 origin.push_back({0,1.1,0}); // Origin City 1 34 35 // Intermediate Cities 36 cities.push_back({1,2.3,-4}); // 2 37 cities.push_back({3,2,3}); // 3 38 cities.push_back({-2,8.4,4}); // 4 39 cities.push_back({7,9,9}); // 5 40 cities.push_back({2,-9,9}); // 6 60 Capítulo A. Anexo I: Código empleado 41 cities.push_back({7,9,2}); // 7 42 cities.push_back({7,2,2}); // 8 43 44 destiny.push_back({10,10,10}); // Destiny City 1 45 destiny.push_back({1.5,-2,1}); // Destiny City 2 46 47 48 // Thread with a single TSP 49 auto tsp_thread = [](std::vector<std::vector<float>> origin, 50 std::vector<std::vector<float>> cities, 51 std::vector<std::vector<float>> destiny, 52 int sub_branch_id,int iterations) { 53 Mtsp mtsp; 54 55 std::vector<std::vector<int>> res_ids ={{7,5},{2}} ; 56 std::vector<int> aux_ids={6,3,4}; 57 mtsp.solve_aux_and_res(origin,cities,destiny,sub_branch_id,iterations,res_ids, aux_ids,mtx); 58 // mtsp.solve_only_res(origin,cities,destiny,sub_branch_id,iterations,res_ids, mtx); 59 // mtsp.solve_only_aux(origin,cities,destiny,sub_branch_id,iterations,aux_ids, mtx); 60 61 62 }; 63 64 65 66 thread th01(tsp_thread,origin,cities,destiny,WHOLE_GRAPH,ITERATIONS); 67 68 69 th01.join(); 70 71 return 0; 72 } Visualización RVIZ Código A.10 Ciudades consideradas en la visualización de RVIZ. 1 2origin.push_back({0,1.1,0}); // Origin City 1 3 4// Intermediate Cities 5cities.push_back({1,2.3,0}); // 2 6cities.push_back({3,2,0}); // 3 7cities.push_back({2,-8.4,0}); // 4 8cities.push_back({7,-9,0}); // 5 9cities.push_back({-2,9,0}); // 6 10 cities.push_back({-7,2,0}); // 7 11 cities.push_back({-7,9,0}); // 8 12 13 destiny.push_back({5,5,0}); // Destiny City 1 14 destiny.push_back({5,-5,0}); // Destiny City 2 15 destiny.push_back({-9,5,0}); // Destiny City 3 A.7 Métodos implementados en el algoritmo 67 Código A.23 Clase Node: fill. 1 2void Node::fill(City city_,int label_,int level_){ 3city=city_; 4label=label_; 5level=level_; }; Código A.24 Clase Node: convert-element. 1 2void Node::convert_element(Element e){ 3city=e.city; 4label=e.label; 5level=e.level;}; Código A.25 Clase Path: fill. 1 2void Path::fill(int origin_id_,int destiny_id_,bool traveled_,float distance_){ 3origin_id=origin_id_; 4destiny_id=destiny_id_; 5traveled=traveled_; 6distance=distance_;}; Código A.26 Clase Branch: add-element. 1 2void Branch::add_element(Element e){ 3std::string s; 4if(e.element_type==PATH){s="PATH";} 5if(e.element_type==NODE){s="NODE";} 6 7if(last_element==e.element_type){} 8// std::cout << "CANNOT ADD THE ELEMENT" << std::endl; 9else if(last_element!=e.element_type){ 10 if(last_element==-1 && e.element_type==PATH){} 11 // std::cout << "CANNOT ADD THE ELEMENT" << std::endl; 12 else{ 13 // std::cout << "ADDED " << s << std::endl; 14 last_element=e.element_type; 15 elements.push_back(e); }} }; Código A.27 Clase Branch: get-total-distance. 1 2float Branch::get_total_distance(){ 3float branch_distance=0; 4for(int i=0;i<elements.size();i++){ 5if(elements[i].element_type==PATH){branch_distance=branch_distance+elements[i]. distance;};} 6return branch_distance ;}; 68 Capítulo A. Anexo I: Código empleado Código A.28 Clase Branch: get-total-distance-destiny-id. 1 2float Branch::get_total_distance_destiny_id(int d_id){ 3float branch_distance=0; 4for(int i=0;i<elements.size();i++){ 5if(elements[i].element_type==PATH){branch_distance=branch_distance+elements[i]. distance; 6if(elements[i].destiny_id==d_id){return branch_distance ;}};} 7} Código A.29 Clase Branch: get-cities. 1 2std::vector<City> Branch::get_cities(){ 3std::vector<City> c; 4for(int i=0;i<elements.size();i++){ 5if(elements[i].element_type==NODE){c.push_back(elements[i].city);};} 6return c ;}; Código A.30 Clase Branch: search-node. 1 2bool Branch::search_node(Node n){ 3for(int i=0;i<elements.size();i=i+2){ // Only search for nodes 4if((n.level==elements[i].level) 5&&(n.city==elements[i].city) && 6(n.label==elements[i].label)){return true;}} 7return false;} Código A.31 Clase Branch: search-path. 1 2bool Branch::search_path(Path n){ 3for(int i=1;i<elements.size();i=i+2){ // Only search for paths 4if((n.destiny_id==elements[i].destiny_id)){return true;}} 5return false;} Código A.32 Clase Branch: get-route. 1 2std::vector<Node> Branch::get_route(Node n){ 3std::vector<Node> nodes_route; Node aux_node; 4for(int i=0;i<elements.size();i=i+2){ // Only search for nodes 5aux_node.convert_element(elements[i]); 6nodes_route.push_back(aux_node); 7if(elements[i].label==n.label){break;/*Found the element and return*/ }} 8return nodes_route; // Element not found 9} A.7 Métodos implementados en el algoritmo 69 Código A.33 Clase Graph: Graph (constructor). 1 2Graph::Graph(std::vector<City> origin_, 3std::vector<City> cities_, 4std::vector<City> destiny_, 5int n_branches,std::mutex &mtx, int level__,int &threshold){ 6 7// Local variables 8Node n; Element e; 9 10 // Id that defines "label" in each node/path from the graph 11 global_node_id=1; branches_id=1; 12 13 // Fill private vector of "cities" 14 cities.push_back(origin_[0]); 15 for(int i=0;i<cities_.size();i++){ cities.push_back(cities_[i]); } 16 cities.push_back(destiny_[0]); 17 18 // Create first node in DATABASE 19 n.fill(cities[0],global_node_id,1); 20 nodes.push_back(n); 21 22 //"Traveler" and "break_down" point to the first node 23 traveler = &nodes[0]; 24 break_down = traveler; 25 26 // Create first BRANCH with first ELEMENT (node; *travel) 27 e=*traveler; 28 branches.resize(branches_id); 29 branches[branches_id-1].add_element(e); 30 31 // Algorithm Code 32 main_algorithm( n_branches,mtx, level__,threshold); 33 34 }; Código A.34 Clase Graph: explore-and-order. 1 2std::pair<std::list<Node>,std::list<Path>> Graph::explore_and_order(){ 3std::pair<std::list<Node>,std::list<Path>> res; // Method output (Next (*traveler) 's paths and nodes) 4std::vector<Node> route=get_route(*traveler); // Elements route until reaching father's node 5std::list<City> list_of_cities; std::list<Node> nodes_created, nodes_right; // DISORDERED / ORDERED by distance 6Node n; Path p; std::list<Path> paths_created, paths_right; // DISORDERED / ORDERED by distance 7int id_variable, node_label = global_node_id; // The second label is the private one (global_node_id) 8Branch b; int cities_considered; // Local variable for lambda expression & cities considered in the break down 9 10 // Defining "cities" in a list (except DESTINY) 11 if((traveler->level)==(cities.size()-1)){cities_considered=cities.size();} // Only DESTINY is missed in graph 12 else{cities_considered=(cities.size()-1);} // Previous travels than the DESTINY one. 70 Capítulo A. Anexo I: Código empleado 13 for(int i=0;i<cities_considered;i++){ list_of_cities.push_back(cities[i]); } // Filling list_of_cities 14 15 // Removing cities from the "list_of_cities" (belonging to the "route") 16 for(int i=0;i<(route.size());i++){ 17 list_of_cities.remove(route[i].city);} 18 19 20 // Creating both "nodes" and "paths" for the cities remaining in the " list_of_cities" 21 for(auto it=list_of_cities.begin();it!=list_of_cities.end();++it){ 22 23 // Label for sons 24 node_label++; 25 26 // Nodes & Paths Created; DISORDERED 27 n.fill(*it,node_label,(traveler->level)+1); 28 p.fill(traveler->label,node_label,false,distance_between_nodes((*traveler),n)); 29 nodes_created.push_back(n);paths_created.push_back(p);} 30 31 32 // Putting the DISORDERED data in the ORDERED data 33 while(!paths_created.empty() && !nodes_created.empty()){ 34 35 // Search the path with minimum distance (store in *path_it) 36 auto path_it = find_if(paths_created.begin(), paths_created.end(), [& paths_created] (const Path& s) 37 {auto it=std::min_element(paths_created.begin(), paths_created.end()); 38 return ((s.distance)==(it->distance));} ); 39 40 // Search the node with the city associated with (*path_it) 41 auto node_it = find_if(nodes_created.begin(), nodes_created.end(), [path_it ] (const Node& s) 42 {return ((s.label)==(path_it->destiny_id));} ); 43 44 // Filling "node_right/path_right" , with ordered data (ids-distance relation). 45 global_node_id++; 46 n.fill(node_it->city,global_node_id,(traveler->level)+1); 47 p.fill(traveler->label,global_node_id,false,path_it->distance); 48 nodes_right.push_back(n);paths_right.push_back(p); 49 paths_created.remove(*path_it); nodes_created.remove(*node_it); // Remove from DISORDERED lists and go on 50 } 51 52 // Return nodes and paths ordered (_right) 53 res.first=nodes_right; res.second=paths_right; 54 return res; 55 56 } Código A.35 Clase Graph: distance-between-nodes. 1 2float Graph::distance_between_nodes(Node n1, Node n2){ 3float accum=0; 4 5// Cities from both nodes with same length (supposed) 6for(int i=0;i<n1.city.city.size();i++){ A.7 Métodos implementados en el algoritmo 71 7accum=accum+pow((n1.city.city[i]-n2.city.city[i]),2);} 8return std::sqrt(accum);} Código A.36 Clase Graph: travel-nearest-city. 1 2void Graph::travel_nearest_city(std::pair<std::list<Node>,std::list<Path>> elements){ 3// Inserts PATH and NODE in the branch 4std::list<Node> n=elements.first; std::list<Path> p=elements.second; 5Path * path_pointer; Element * e; 6 7//(Add (*traveler) to the branch 8e=&(*traveler); branches[branches_id-1].add_element(*e); 9 10 // Search for MIN PATH below the traveler 11 auto p_it = find_if(p.begin(), p.end(), [&p] (const Path& s) 12 {auto it=std::min_element(p.begin(), p.end()); 13 return ((s.distance)==(it->distance));} ); 14 15 // Add MIN PATH to the branch 16 e=&(*p_it); branches[branches_id-1].add_element(*e); 17 18 // Search the node with the city associated with (*p_it) 19 auto n_it = find_if(n.begin(), n.end(), [p_it] (const Node& s) 20 {return ((s.label)==(p_it->destiny_id));} ); 21 22 // (*traveler) travels 23 // (USE "NODES" TO CONSERVE ADDRESS WHEN THIS METHOD ENDS) 24 for (int i=0;i<nodes.size();i++){ 25 if(nodes[i]==(*n_it)){traveler = &nodes[i];break;}} 26 27 // Add NODE to the branch 28 e=&(*traveler); branches[branches_id-1].add_element(*e); 29 30 } Código A.37 Clase Graph: refresh-graph-data. 1 2void Graph::refresh_graph_data(Element e, Node n,Node save_traveler,int &move_bd,std ::vector<float> &distances, int &threshold ){ 3 4// Refresh the (*break_down) pointer, and erase the last branch created 5// (because is empty and useless) 6if(move_bd==1){ move_break_down(); 7branches.erase(branches.end() - 1); 8distances.erase(distances.end() - 1); 9branches_id--; 10 move_bd=0; } 11 12 // Refresh (*traveler) and save its address 13 traveler=break_down; 14 save_traveler=*traveler; 15 e=*traveler; 16 72 Capítulo A. Anexo I: Código empleado 17 // Create another branch 18 branches_id++; 19 branches.resize(branches_id); 20 branches[branches_id-1].add_element(e); 21 22 // Clear NODE and PATH databases 23 nodes.clear(); paths.clear(); 24 25 // Create first node in DATABASE 26 n.fill(save_traveler.city,save_traveler.label,save_traveler.level); 27 nodes.push_back(n); 28 29 // "Traveler" and "break_down" point to the first node in DATABASE 30 traveler = &nodes[0]; 31 break_down = traveler; 32 33 } Código A.38 Clase Graph: remove-branches-elements. 1 2std::pair<std::list<Node>,std::list<Path>> Graph::remove_branches_elements(std ::pair<std::list<Node>,std::list<Path>> elements){ 3std::list<Node> nn=elements.first; std::list<Path> pp=elements.second; 4std::pair<std::list<Node>,std::list<Path>> ret_elements=elements; 5std::vector<Branch> b=branches; 6 7std::list<Node>::iterator it_n; 8std::list<Path>::iterator it_p; 9 10 // REMOVE NODES from OUTPUT VALUE (ret_elements) 11 for(int j=0;j<b.size();j++){ 12 auto n_it = find_if(nn.begin(), nn.end(), [&b,j] (const Node& s) 13 {return b[j].search_node(s);} ); 14 if(n_it!=nn.end()){ 15 ret_elements.first.remove(*n_it);}} 16 17 // REMOVE PATHS from OUTPUT VALUE (ret_elements) 18 for(int j=0;j<b.size();j++){ 19 auto p_it = find_if(pp.begin(), pp.end(), [&b,j] (const Path& s) 20 {return b[j].search_path(s);} ); 21 if(p_it!=pp.end()){ 22 ret_elements.second.remove(*p_it);}} 23 24 // UPDATE NODES DATABASE 25 it_n = ret_elements.first.begin(); 26 while (it_n!=ret_elements.first.end()){ 27 nodes.push_back(*it_n);it_n++;} 28 29 // UPDATE PATHS DATABASE 30 it_p = ret_elements.second.begin(); 31 while (it_p!=ret_elements.second.end()){ 32 paths.push_back(*it_p); it_p++;} 33 34 return ret_elements; 35 } A.7 Métodos implementados en el algoritmo 73 Código A.39 Clase Graph: break-down-son. 1 2int Graph::break_down_son(){ 3std::deque<Element> e; Node *bd=break_down; 4 5 6// Search BREAK_DOWN in branches 7for(int j=0;j<branches.size();j++){ 8if(branches[j].search_node(*break_down)==true && branches[j].elements.size() >1){ 9e=branches[j].elements; 10 auto e_it = find_if(e.begin(), e.end(), [&bd,&e] (const Element& s) 11 {return bd->label==s.label;} ); // Search (*break_down) ID 12 if(e_it!=e.end() && e_it!=(e.end()-1)){return ((e_it+2)->label)-1;} // Return (*break_down) son's minimum ID 13 } 14 } 15 return -1; // If I dont find (*break_down) 16 } Código A.40 Clase Graph: create-branch. 1 2void Graph::create_branch(int &global_node_id_saved,int &move_bd,int &threshold){ 3std::pair<std::list<Node>,std::list<Path>> elements_created; 4int a; Path p; Node n; Element e; Node* traveler_aux; 5bool c; 6 7// (*traveler) travels in each iteration, until reaching destiny and defining branch 8do{ 9 10 // When I use THRESHOLD in MTSP. ADD DESTINY WHEN THIS CONDITION IS SATISFIED. 11 if(threshold!=(cities.size()) && threshold==traveler->level){ 12 global_node_id_saved++; 13 traveler_aux=traveler; 14 n.fill(cities[cities.size()-1],global_node_id_saved,(traveler->level)+1); 15 nodes.push_back(n); traveler=&nodes[nodes.size()-1]; 16 p.fill(traveler_aux->label,traveler->label,false,distance_between_nodes((* traveler),(*traveler_aux))); 17 paths.push_back(p); 18 e=p; branches[branches_id-1].add_element(e); 19 e=n; branches[branches_id-1].add_element(e); 20 21 c=((branches[branches_id-1].elements.size()))< 22 ((((2*(cities.size()-(break_down->level)))-1)+2)-(2*(cities.size()-1threshold))); 23 24 } 25 else{// NORMAL tsp (or threshold==cites.size()) 26 27 // Global id (consider global or (*break_down)'s son id) 28 if(traveler==break_down){global_node_id=break_down_son(); 29 a=0; 30 if(global_node_id==-1){global_node_id=global_node_id_saved;a=1;}} 31 else{global_node_id=global_node_id_saved;a=1;} 32 74 Capítulo A. Anexo I: Código empleado 33 // Consider possible (*traveler)'s sons. 34 elements_created=explore_and_order(); // (*traveler)'s sons, ordered by distance. 35 elements_created=remove_branches_elements(elements_created); // remove elements from previous branches. 36 if(elements_created.first.size()==0 && elements_created.second.size()==0){ // All elements removed 37 move_bd=1; break;} // (EXIT FROM DO-WHILE) (*break_down) goes to the next global id 38 travel_nearest_city(elements_created); // (*traveler) travels to the next city 39 if(a==1){global_node_id_saved=global_node_id;} // Refresh global id 40 41 c=((branches[branches_id-1].elements.size()))<((((2*(cities.size()-( break_down->level)))-1)+2)); 42 } 43 44 }while(c); 45 // Do until traveler reaches destiny (WHILE CONDITION BASED ON NUMBER OF LEVELS FROM GRAPH) 46 } Código A.41 Clase Graph: move-break-down. 1 2void Graph::move_break_down(){ 3std::deque<Element> e; Node *bd=break_down, nn; 4 5 6// Search BREAK_DOWN in branches 7for(int j=0;j<branches.size();j++){ 8e=branches[j].elements; 9auto e_it = find_if(e.begin(), e.end(), [&bd,&e] (const Element& s) 10 {return (bd->label)+1==s.label;} ); 11 if(e_it!=e.end()){ 12 nn.convert_element(*e_it); 13 nodes.push_back(nn); 14 break_down=&(nodes[nodes.size()-1]);} 15 } 16 17 } Código A.42 Clase Graph: get-total-distance. 1 2float Graph::get_total_distance(int branch_id_,int &threshold){ 3float ret_distance=0; int branch_id_aux=branch_id_; // ID from branch I am considering 4std::vector<Branch> b=branches; bool minor,equal; 5 6// Condition for setting branches resize 7if(threshold!=(cities.size())){ // THRESHOLD FOR MTSP 8minor=((branches[branches_id-1].elements.size()))<((((2*(cities.size()-1))-1) +2)-(2*(cities.size()-1-threshold))); 9equal=((branches[branches_id-1].elements.size()))==((((2*(cities.size()-1)) -1)+2)-(2*(cities.size()-1-threshold))); A.7 Métodos implementados en el algoritmo 75 10 } 11 else{// USING NORMAL TSP 12 minor=((branches[branches_id-1].elements.size()))<(((2*(cities.size()-1))-1) +2); 13 equal=((branches[branches_id-1].elements.size()))==(((2*(cities.size()-1))-1) +2);} 14 15 16 // BRANCH WITH ELEMENTS 17 if(branches[branch_id_-1].elements.size()>0){ 18 // Branch SMALLER than the one that starts in ORIGIN and reaches DESTINY 19 if(minor){ 20 21 // DISTANCE OF THE CURRENT LITTLE BRANCH 22 ret_distance=ret_distance+branches[branch_id_aux-1].get_total_distance(); 23 24 // Add little branches until the ORIGIN (origin_id=1) 25 for(float i=(b.size()-1);i>-1;i--){ // SMALL TO LARGER ONES (I mean BRANCHES) 26 for(float j=(b[i].elements.size()-1);j>-1;j--){ // HIGHER TO LOWER LEVELS 27 // Search for little branches that end with the same node than " branch_id_aux" (and connect) 28 if(b[i].elements[j].destiny_id==branches[branch_id_aux-1].elements[1]. origin_id){ 29 ret_distance=ret_distance+b[i].get_total_distance_destiny_id(b[i]. elements[j].destiny_id); 30 if(b[i].elements[1].origin_id==1){return ret_distance;} 31 else{branch_id_aux=i+1;} } 32 }} } 33 34 // Branch that starts in ORIGIN and reaches DESTINY 35 else if(equal){ 36 return branches[branch_id_-1].get_total_distance();} 37 38 } 39 40 // BRANCH WITHOUT ELEMENTS (It won't be the case) 41 else{std::cout <<"Branch " << branch_id_ <<" doesn't have elements. Return 0 as distance." << std::endl<< std::endl; 42 return 0;} 43 44 45 } Código A.43 Clase Graph: get-route. 1 2std::vector<Node> Graph::get_route(Node n){ 3std::vector<std::vector<Node>> var; std::vector<Node> out_; Node nn=n; 4 5do{ 6for(int i=0;i<branches.size();i++){ // Search all branches 7if(branches[i].search_node(nn)==1){ 8var.push_back(branches[i].get_route(nn)); // Search branch with (*traveler) 9nn=var[var.size()-1][0];break;}} // Refresh node I want to search... 10 }while(var[var.size()-1][0].level>1); // ... until I reach top node (FATHER) 11 12 // OUTPUT NODE VECTOR 13 for(float i=(var.size()-1);i>-1;i--){ 76 Capítulo A. Anexo I: Código empleado 14 for(auto j=0;j<(var[i].size());j++){ 15 16 // Put in "out_" all nodes from route stored in "var" 17 // (without repeating nodes values twice) 18 if(j==0 && i==(var.size()-1)){out_.push_back(var[i][j]);} 19 else if(i>0 && j==(var[i].size()-1)){} 20 else if(i==0 && j==(var[i].size()-1)){ out_.push_back(var[i][j]);} 21 else{ out_.push_back(var[i][j]);} 22 }} 23 24 return out_; // Return route ("out_") 25 } Código A.44 Clase Graph: main-algorithm. 1 2void Graph::main_algorithm(int n_branches,std::mutex &mtx, int level__,int & threshold){ 3Node n, save_traveler=*traveler; int factorial_value; 4Element e; int global_node_id_saved=global_node_id, move_bd=0; 5 6level_=level__; // Filling private variable 7 8n_branches++; 9n_branches_private=n_branches; 10 11 // Start execution time 12 begin = ros::Time::now(); 13 14 // Calculate factorial (number of possible solutions of the graph) 15 factorial_value=(cities.size()-2); 16 for(int i = factorial_value; i>0; i--){factorial *= i; 17 if(((factorial_value-i)+2)==threshold){break;}} 18 19 // Create a single branch for the graph 20 do{ create_branch(global_node_id_saved,move_bd,threshold); // Creates the branch 21 distances.push_back(get_total_distance(branches_id,threshold)); // Vector of graph branches'distances 22 // print_data_base(); // See database (PATHS AND NODES) if needed to debug 23 refresh_graph_data(e,n,save_traveler,move_bd,distances,threshold); // Refreshes (*break_down) and (*traveler) 24 25 }while(branches.size()<(n_branches) && (branches.size()<factorial+1)); // Limit of solutions calculated 26 27 //std::cout << "ENTRO EN Graph::main_algorithm" << std::endl; 28 29 30 // Minimum distance 31 auto f_it=std::min_element(distances.begin(), distances.end()); 32 33 // Getting route of cities 34 n.convert_element(branches[f_it-distances.begin()].elements[branches[f_itdistances.begin()].elements.size()-1]); 35 route_out=get_route(n); 36 37 } A.7 Métodos implementados en el algoritmo 83 74 previous_cities_ids.push_back(return_cities_ids[i]);} 75 76 std::cout << "(GO ON) MAX ID VALUE ("<< it_dis-previous_distances.begin()<<") : "<< max_value << std::endl; 77 78 // Improvements TSP 79 it_min=std::min_element(min_distances.begin(), min_distances.end()); 80 it_max=std::max_element(min_distances.begin(), min_distances.end()); 81 z_min=(it_min-min_distances.begin()); 82 z_max=(it_max-min_distances.begin()); 83 cities_to_travel[z_min]++; 84 cities_to_travel[z_max]--; 85 86 }// IF this condition gets satisfied, go on with iterations in "solve_only_aux" 87 else{end=1; 88 std::cout << "(FINISHED) MAX ID VALUE: "<< max_value << std::endl;} 89 90 91 92 }// END WHILE 93 94 std::cout << std::endl<< std::endl<< std::endl<< std::endl; 95 std::cout << "previous_cities_ids DATA: "<< std::endl; 96 97 for(int i=0;i<previous_cities_ids.size();i++){ 98 for(int j=0;j<previous_cities_ids[i].size();j++){ 99 std::cout << previous_cities_ids[i][j] << std::endl;}std::cout << std::endl;} 100 101 }; Código A.54 Clase Mtsp: solve-tsp. 1 2void Mtsp::solve_tsp(std::vector<std::vector<float>> &origin, 3std::vector<std::vector<float>> &cities, 4std::vector<std::vector<float>> &destiny, 5int sub_branch_id,int iterations, 6std::vector<int> &aux_ids, 7std::vector<std::vector<int>> &res_ids, 8std::mutex &mtx, 9std::vector<City> &c, 10 std::vector<std::vector<int>> &return_cities_ids, 11 std::vector<int> &cities_to_travel, 12 std::list<int> &aux_ids_list){ 13 14 std::list<int>::iterator it_list; 15 std::vector<WholeGraph> tsp; 16 tsp.resize(destiny.size()); 17 18 19 20 // Solving TSPs 21 for(int z=0;z<destiny.size();z++){ 22 23 // z traveler considers all AUX cities 24 tsp[z].add_aux_cities(c,aux_ids); 25 26 // ADDING RES CITIES TO TRAVELERS (DIRECTLY) 27 if(res_ids.size()>0){ 84 Capítulo A. Anexo I: Código empleado 28 tsp[z].add_res_cities(c,res_ids[z]); } 29 30 // z traveler 31 if(res_ids.size()>0){ // AUX AND RES CITIES 32 33 return_cities_ids[z]=tsp[z].main_algorithm(origin,destiny[z], 34 cities.size(),sub_branch_id,iterations,mtx,cities_to_travel[z ]+res_ids[z].size()); 35 } 36 else{// ONLY AUX CITIES 37 return_cities_ids[z]=tsp[z].main_algorithm(origin,destiny[z], 38 cities.size(),sub_branch_id,iterations,mtx,cities_to_travel [z]);} 39 40 41 // Remove "return_cities_ids[z]" from "aux_ids" 42 // Copy IDs to a list (in order to remove later) 43 for(int i=0;i<aux_ids.size();i++){ 44 aux_ids_list.push_back(aux_ids[i]);} 45 // Remove from list ids stored in "return_cities_ids[0]" 46 for(int i=0;i<return_cities_ids[z].size();i++){ 47 aux_ids_list.remove(return_cities_ids[z][i]);} 48 // Put in vector values from list again 49 it_list=aux_ids_list.begin(); 50 aux_ids.clear(); 51 for(int i=0;i<aux_ids_list.size();i++){ 52 aux_ids.push_back(*it_list); 53 std::advance(it_list, 1);} 54 55 // See "min_distance" output 56 min_distances.push_back(tsp[z].min_distance); 57 // std::cout << " MIN DISTANCE "<< z <<": " << min_distances[z] << std::endl; 58 59 } 60 61 } Simulación en Gazebo Código A.55 Ciudades especificadas para Gazebo.. 1 2// For MTSP 3// ----------------------------------------------------------- 4// Defining vectors with CITIES, ORIGIN and DESTINY 5std::vector<std::vector<float>> origin, destiny; 6std::vector<std::vector<float>> cities; 7std::vector<std::vector<int>> def_track_points; 8 9origin.push_back({0,1.1}); // Origin City 1 10 11 // 4 Intermediate Cities 12 cities.push_back({1,2.3}); // 2 13 cities.push_back({3,2}); // 3 14 cities.push_back({2,-8.4}); // 4 15 cities.push_back({7,-9}); // 5 16 cities.push_back({-2,9}); // 6 17 cities.push_back({-7,2}); // 7 A.8 Simulación en Gazebo 85 18 cities.push_back({-7,9}); // 8 19 20 destiny.push_back({5,5}); // Destiny City 1 21 22 // ----------------------------------------------------- 23 24 Mtsp mtsp; 25 std::vector<std::vector<int>> res_ids ={{2,3,4,5}} ; 26 mtsp.solve_only_res(origin,cities,destiny,WHOLE_GRAPH,10,res_ids,mtx); 27 def_track_points=mtsp.return_cit_ids(); Código A.56 Asignación de coordenadas de las ciudades. 1 2// Loop for adding MTSP track points 3for(int i=0;i<def_track_points[0].size()+2;i++){ 4grvc::ual::Waypoint waypoint; 5waypoint.header.frame_id = "map"; 6if(i==0){ // ORIGIN 7waypoint.pose.position.x = origin[0][0]; 8waypoint.pose.position.y = origin[0][1]; 9} 10 else if(i==(def_track_points[0].size()+1)){ // DESTINY 11 waypoint.pose.position.x = destiny[0][0]; 12 waypoint.pose.position.y = destiny[0][1]; 13 } 14 else if(i>0 && i<(def_track_points[0].size()+1)){ // CITIES 15 waypoint.pose.position.x = cities[def_track_points[0][i-1]-2][0]; 16 waypoint.pose.position.y = cities[def_track_points[0][i-1]-2][1]; 17 } 18 waypoint.pose.position.z = flight_level; //flight_level; 19 waypoint.pose.orientation.x = 0; 20 waypoint.pose.orientation.y = 0; 21 waypoint.pose.orientation.z = 0; 22 waypoint.pose.orientation.w = 1; 23 path.push_back(waypoint);} Código A.57 Sección de código encargada del movimiento del UAV. 1 2std::cout << "Blocking version of goToWaypoint" << std::endl; 3for (auto p : path) { 4std::cout << "Waypoint: " << p.pose.position.x << ","<< \ 5p.pose.position.y << ","<< p.pose.position.z << ", frame_id: " << p. header.frame_id << std::endl; 6ual.goToWaypoint(p); 7std::cout << "Arrived!" << std::endl; 8} 9 10 // Land 11 ual.land(); Índice de Figuras 2.1 Grafo de estado para tres ciudades intermedias 6 2.2 Grafo de estado para tres ciudades intermedias; ciudades 6 2.3 Posible solución del grafo para 3 ciudades intermedias 7 2.4 Algoritmo en clases: símil con un árbol 8 2.5 Diagrama UML: Clase City 9 2.6 Diagrama UML: Clase Node 10 2.7 Diagrama UML: Clase Path 10 2.8 Diagrama UML: Clase Branch 11 2.9 Elementos de la rama. En rojo los nodos. En azul los caminos 13 2.10 Diagrama UML: Herencia de la clase Element 14 2.11 Algoritmo en clases: símil con un árbol 17 4.1 Resultado en RVIZ con tres viajeros 24 4.2 Coordenadas de las ciudades. Resultados RVIZ 24 5.1 TSP: un solo hilo 28 5.2 Solución del TSP en el caso de un solo hilo 28 5.3 TSP: cuatro hilos 29 5.4 Solución del TSP en el caso multihilo 30 5.5 MTSP: primera iteración para ciudades auxiliares 31 5.6 MTSP: resultados de primera iteración (ciudades auxiliares) 31 5.7 MTSP: segunda iteración para ciudades auxiliares 31 5.8 MTSP: resultados de segunda iteración (ciudades auxiliares) 31 5.9 MTSP: resultados globales (ciudades auxiliares) 32 5.10 MTSP: resultados con ciudades restringidas 32 5.11 MTSP: primera iteración para ciudades auxiliares y restringidas 33 5.12 MTSP: resultados de primera iteración (ciudades auxiliares y restringidas) 33 5.13 MTSP: segunda iteración para ciudades auxiliares y restringidas 33 5.14 MTSP: resultados de segunda iteración (ciudades auxiliares y restringidas) 33 5.15 MTSP: resultados globales (ciudades auxiliares y restringidas) 34 6.1 Subramas en el caso de tres ciudades intermedias 39 6.2 Numeración de ramas: viajero y desglose en distintos nodos 40 6.3 Numeración de ramas: viajero y desglose en el mismo nodo 41 6.4 Elementos de una rama completa del grafo 42 6.5 Grafo del viajero completo 44 6.6 División en subramas del grafo del viajero 44 7.1 Simulación en Gazebo: solución del TSP 48 7.2 Simulación en Gazebo: primera parte del recorrido 49 7.3 Simulación en Gazebo: segunda parte del recorrido y aterrizaje 49 87 Índice de Códigos 7.1 Modificación en el CMakeLists 47 7.2 Compilación de los paquetes requeridos 47 A.1 Declaración de clase City 55 A.2 Declaración de clase Node 55 A.3 Declaración de clase Path 56 A.4 Declaración de clase Branch 56 A.5 Declaración de clase Element 56 A.6 Declaración de clase Graph 57 A.7 Declaración de clase WholeGraph 58 A.8 Declaración de clase Mtsp 58 A.9 Fichero principal: codigo-principal.cpp 59 A.10 Ciudades consideradas en la visualización de RVIZ 60 A.11 Código para resolver el Problema del Viajero solo con ciudades restringidas 61 A.12 Código RVIZ 61 A.13 Ciudades intermedias consideradas en TSP (main) 64 A.14 Código de un hilo para TSP 64 A.15 Ejecución en main para un hilo (TSP) 64 A.16 Ejecución en main para cuatro hilos (TSP) 64 A.17 Ciudades intermedias consideradas en MTSP (main) 65 A.18 Código de un hilo para MTSP: ciudades auxiliares 65 A.19 Código de un hilo para MTSP: ciudades restringidas 65 A.20 Código de un hilo para MTSP: ciudades restringidas y auxiliares 66 A.21 Clase City: fill 66 A.22 Clase City: get-string-data 66 A.23 Clase Node: fill 67 A.24 Clase Node: convert-element 67 A.25 Clase Path: fill 67 A.26 Clase Branch: add-element 67 A.27 Clase Branch: get-total-distance 67 A.28 Clase Branch: get-total-distance-destiny-id 68 A.29 Clase Branch: get-cities 68 A.30 Clase Branch: search-node 68 A.31 Clase Branch: search-path 68 A.32 Clase Branch: get-route 68 A.33 Clase Graph: Graph (constructor) 69 A.34 Clase Graph: explore-and-order 69 A.35 Clase Graph: distance-between-nodes 70 A.36 Clase Graph: travel-nearest-city 71 A.37 Clase Graph: refresh-graph-data 71 A.38 Clase Graph: remove-branches-elements 72 89 90 Índice de Códigos A.39 Clase Graph: break-down-son 73 A.40 Clase Graph: create-branch 73 A.41 Clase Graph: move-break-down 74 A.42 Clase Graph: get-total-distance 74 A.43 Clase Graph: get-route 75 A.44 Clase Graph: main-algorithm 76 A.45 Clase Graph: route-output 77 A.46 Clase Graph: min-distance-output 77 A.47 Clase WholeGraph: output-whole-graph 77 A.48 Clase WholeGraph: main-algorithm 77 A.49 Clase WholeGraph: add-aux-cities 78 A.50 Clase WholeGraph: add-res-cities 79 A.51 Clase Mtsp: solve-only-res 79 A.52 Clase Mtsp: solve-only-aux 80 A.53 Clase Mtsp: solve-aux-and-res 81 A.54 Clase Mtsp: solve-tsp 83 A.55 Ciudades especificadas para Gazebo. 84 A.56 Asignación de coordenadas de las ciudades 85 A.57 Sección de código encargada del movimiento del UAV 85 Bibliografía [1] M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on evolutionary computation, vol. 1, no. 1, pp. 53–66, 1997. [2] S. Lin, “Computer solutions of the traveling salesman problem,” Bell System Technical Journal, vol. 44, no. 10, pp. 2245–2269, 1965. [3] C. C. Murray and A. G. Chu, “The flying sidekick traveling salesman problem: Optimization of droneassisted parcel delivery,” Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86–109, 2015. [4] E. Semsch, M. Jakob, D. Pavlicek, and M. Pechoucek, “Autonomous uav surveillance in complex urban environments,” in Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology-Volume 02. IEEE Computer Society, 2009, pp. 82–85. [5] C.-W. Lim, S. Park, C.-K. Ryoo, K. Choi, and J.-H. Cho, “A path planning algorithm for surveillance uavs with timing mission constrains,” in ICCAS 2010. IEEE, 2010, pp. 2371–2375. [6] J. Isaacs and J. Hespanha, “Dubins traveling salesman problem with neighborhoods: A graph-based approach,” Algorithms, vol. 6, no. 1, pp. 84–99, 2013. [7] J. Faigl and P. Váňa, “Unsupervised learning for surveillance planning with team of aerial vehicles,” in 2017 International Joint Conference on Neural Networks (IJCNN). IEEE, 2017, pp. 4340–4347. [8] K. Obermeyer, “Path planning for a uav performing reconnaissance of static ground targets in terrain,” in AIAA Guidance, Navigation, and Control Conference, 2009, p. 5888. [9] X. Zhang, J. Chen, B. Xin, and Z. Peng, “A memetic algorithm for path planning of curvature-constrained uavs performing surveillance of multiple ground targets,” Chinese Journal of Aeronautics, vol. 27, no. 3, pp. 622–633, 2014. [10] C. Lim, C. Ryoo, K. Choi, and J.-H. Cho, “Path generation algorithm for intelligence, surveillance and reconnaissance of an uav,” in Proceedings of SICE Annual Conference 2010. IEEE, 2010, pp. 1274–1277. [11] S. Rathinam and R. Sengupta, “Lower and upper bounds for a multiple depot uav routing problem,” in Proceedings of the 45th IEEE Conference on Decision and Control. IEEE, 2006, pp. 5287–5292. [12] D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The traveling salesman problem: a computational study. Princeton university press, 2006. [13] S. Kuske, M. Gogolla, R. Kollmann, and H.-J. Kreowski, “An integrated semantics for uml class, object and state diagrams based on graph transformation,” in International Conference on Integrated Formal Methods. Springer, 2002, pp. 11–28. [14] A. Snyder, “Encapsulation and inheritance in object-oriented programming languages,” in ACM Sigplan Notices, vol. 21, no. 11. ACM, 1986, pp. 38–45. 91 92 Bibliografía [15] P. R. S. J. C. Fran Real, Arturo Torres-Gonzalez and A. Ollero, “Ual: an abstraction layer for unmanned vehicles,” in 2nd International Symposium on Aerial Robotics (ISAR), 2018.