Repositorio Institucional de Documentos

Proyecto Fin de Carrera Ingeniería Industrial PLANIFICACIÓN Y CONTROL CON RESTRICCIONES DE FORMACIONES DE ROBOTS Autora: Davinia Vera Soriano Septiembre 2011 Departamento de Informática e Ingeniería de Sistemas Universidad de Zaragoza Director: Eduardo Montijano Muñoz Ponente: Carlos Sagüés Blázquiz Universidad de Zaragoza Centro Politécnico Superior PLANIFICACIÓN Y CONTROL CON RESTRICCIONES DE FORMACIONES DE ROBOTS RESUMEN La idea de robots autónomos que se mueven por el entorno de forma automática plantea numerosas ventajas para los seres humanos. Disponer de un sistema multi-robot permite realizar las tareas de manera eficiente, segura y robusta, colaborando por ejemplo en la exploración de un determinado recinto. En este contexto se deben tener en cuenta las estrategias de coordinación, con el fin de conseguir que los miembros del sistema multi-robot optimicen la percepción del entono. Sin embargo, a medida que se incrementa el número de robots que participan en estas tareas, la ejecución de las mismas se vuelve más complicada debido a las restricciones de movimiento de los robots. El objetivo principal del proyecto es el estudio de algoritmos de planificación y control que permitan a un equipo de robots obtener la ruta más interesante de exploración y moverse de manera coordinada siguiendo la misma. Dichos algoritmos deben considerar las restricciones del entorno, como los obstáculos, y deben incorporar las limitaciones de comunicación, de percepción y de movilidad de los robots involucrados. Para el proyecto se ha partido de dos artículos de investigación para el estudio del control de sistemas multi-robot. Se ha analizado un control mediante una abstracción geométrica y otro basado en particiones de Voronoi. Ambos controles se han implementado desde cero, y en el caso del control basado en particiones de Voronoi, se ha extendido la propuesta original para que admita entornos dinámicos en el tiempo. De esta manera se ha podido usar dicho control para el movimiento de la abstracción dentro de un escenario de simulación. En cuanto al planificador de trayectorias, se ha utilizado el algoritmo de búsqueda A*. Se ha modificado el algoritmo estándar para que considere diferentes tamaños de abstracción y costes en función del entorno en la planificación. Con las modificaciones implementadas se ha conseguido una mejor adaptación de la trayectoria generada por el planificador en función de las características y limitaciones que ofrece el escenario en el que se trabaja. Finalmente se han adaptado mapas de escenarios realistas de interiores y exteriores al entorno de simulación, un piso y un parque respectivamente. Se han propuesto diferentes trayectos sobre ellos, y se ha estudiado la influencia de las modificaciones en el planificador y la eficacia del control del sistema seleccionado. ÍNDICE 1. INTRODUCCIÓN ........................................................................................................ 5 1.1 MOTIVACIÓN ................................................................................................................. 5 1.2 OBJETIVOS ..................................................................................................................... 5 1.3 ALCANCE ........................................................................................................................ 6 1.4 CONTENIDO DE LA MEMORIA ....................................................................................... 6 2. CONTROL DE FORMACIONES ..................................................................................... 9 2.1 DESCRIPCIÓN DE LOS ROBOTS ...................................................................................... 9 2.2 CONTROL MEDIANTE UNA ABSTRACCIÓN GEOMÉTRICA ........................................... 10 2.3 CONTROL MEDIANTE PARTICIONES DE VORONOI ...................................................... 13 2.4 ANÁLISIS ...................................................................................................................... 17 3. PLANIFICACIÓN DE TRAYECTORIAS .......................................................................... 19 3.1 PLANIFICACIÓN CON ABSTRACCIÓN VARIABLE .......................................................... 19 3.2 PLANIFICACIÓN CON COSTE EN FUNCIÓN DEL ENTORNO .......................................... 22 3.3 ANÁLISIS ...................................................................................................................... 24 4. APLICACIÓN ........................................................................................................... 27 4.1 LIMPIEZA DE INTERIORES ............................................................................................ 27 4.2 EXTERIORES ................................................................................................................. 31 5. CONCLUSIONES ...................................................................................................... 41 5.1 VALORACIÓN DEL TRABAJO REALIZADO ..................................................................... 41 5.2 LÍNEAS FUTURAS ......................................................................................................... 42 BIBLIOGRAFÍA .................................................................................................................... 43 ÍNDICE DE FIGURAS ............................................................................................................ 45 ÍNDICE DE TABLAS ............................................................................................................. 47 1. INTRODUCCIÓN 5 1. INTRODUCCIÓN 1.1 MOTIVACIÓN Desde hace siglos, la humanidad ha intentado crear artilugios que simplifiquen la vida de las personas realizando tareas cotidianas de manera automática. Este tema, muy desarrollado en el cine y la literatura con infinidad de películas y novelas de ciencia ficción, ha despertado siempre la fascinación del ser humano. Lo que en su momento se antojaba inalcanzable, se ve cada vez más cercano, ya que se puede disponer en nuestros hogares de dispositivos móviles programables que hacen más fácil el día a día cotidiano. Dispositivos como “Roomba”, un robot comercial para el barrido del hogar, consiguen por ejemplo calcular las dimensiones de una estancia, efectuando una limpieza eficaz con el único movimiento por parte del usuario de darle al botón de encendido. Todo ello se lo debemos de agradecer a la ingeniería electrónica, mecánica y de control. Sin embargo, aunque se posean varios ejemplares de dicho robot, no es posible hacer que trabajen coordinadamente, ya que a fecha de hoy no se encuentra en el mercado software comercial capaz de coordinar varios dispositivos. Trabajar con sistemas multi-robot resulta interesante, ya que permiten realizar cualquier tarea de manera más eficiente, segura y robusta, colaborando en la manipulación o transporte de objetos o en la exploración de un determinado recinto. Pero a medida que se incrementa el número de robots que participan en estas tareas, la ejecución de las mismas se vuelve más complicada debido a las restricciones de movimiento de los robots. En el ámbito de la investigación, en los últimos años, se han propuesto diferentes técnicas para abordar este problema. En este proyecto se estudiarán algunas de estas propuestas, analizando las ventajas e inconvenientes de las mismas. El estudio tendrá en cuenta restricciones de los dispositivos y del entorno. Se valorará la escalabilidad de los algoritmos con el número de robots y la capacidad de los mismos de ejecutarse de forma distribuida. En una segunda fase, dicho estudio se utilizará para proponer nuevos algoritmos de planificación de trayectorias en escenarios realistas. 1.2 OBJETIVOS El objetivo principal del proyecto es el estudio de algoritmos de planificación y control que permitan a un equipo de robots obtener la ruta más interesante de exploración y moverse de manera coordinada siguiendo la misma. Dichos algoritmos deben considerar las restricciones del entorno, como los obstáculos, y deben incorporar las limitaciones de comunicación, de percepción y de movilidad de los robots involucrados. 6 Más en detalle, los objetivos a alcanzar en este proyecto son tres: - Comparación de diferentes técnicas de control descentralizado para equipos de robots con el objetivo de alcanzar una configuración deseada. - Propuesta de nuevos algoritmos de planificación de trayectorias que tengan en cuenta las características del entorno y las restricciones de percepción, comunicación y movimiento de los robots. - Combinación de las técnicas de control y planificación propuestas en escenarios realistas empleando un entorno de simulación. 1.3 ALCANCE Para este proyecto se ha partido de dos artículos de investigación para el estudio del control de sistemas multi-robot. El primer control que se ha estudiado, control basado en una abstracción geométrica, se ha extraído de [3]. El segundo tipo de control distribuido a analizar, basado en las particiones de Voronoi, se ha obtenido de [2]. Ambos controles se han implementado desde cero, y en el caso del control basado en las particiones de Voronoi, se ha extendido la propuesta inicial para que la representación abstracta sea dinámica. En cuanto al planificador de trayectorias, se ha utilizado el algoritmo de búsqueda A*. Tanto la planificación con abstracción variable como el coste añadido en función del entorno han sido creados específicamente en este proyecto, para lograr una mejor adaptación de la trayectoria generada por el planificador en función de las características y limitaciones que ofrece el escenario en el que se trabaja. Finalmente se han adaptado mapas de escenarios realistas de interiores y exteriores al entorno de simulación, un piso y un parque respectivamente. Se han propuesto diferentes trayectos sobre ellos, y se ha estudiado la influencia de las modificaciones en el planificador y la eficacia del control del sistema seleccionado. 1.4 CONTENIDO DE LA MEMORIA La presente memoria explica los pasos seguidos en la realización del proyecto, así como los resultados alcanzados durante la elaboración del mismo. En este primer capítulo se ha realizado una introducción al proyecto, donde se presenta el trabajo anterior en este ámbito y se especifican y justifican los objetivos a lograr. El segundo capítulo se basa en la explicación, simulación y análisis de dos técnicas de control descentralizado para conjuntos de robots, con intención de conseguir una configuración especificada. Se comparan ambas implementaciones en función de los resultados obtenidos para seleccionar la más eficiente y adecuada para el desarrollo del proyecto. 1. INTRODUCCIÓN 7 El tercer capítulo consiste en la exposición de los fundamentos del algoritmo de búsqueda A* y la propuesta de modificaciones sobre esta función, teniendo en cuenta las condiciones del entorno en el que se ejecuta la tarea y las necesidades de tamaño de superficie ocupada por la formación. El cuarto capítulo representa la combinación de las técnicas de control y planificación estudiadas en los capítulos anteriores y la aplicación de éstas sobre escenarios de interior y exterior recreados para el entorno de simulación. En el quinto y último capítulo se exponen las conclusiones obtenidas de este proyecto, presentado a su vez las dificultades encontradas durante su proceso y las posibles líneas de trabajo futuras. Se complementa la información desarrollada en esta memoria con tres anexos. El anexo A corresponde a más simulaciones de dos tipos de control descritos en el capítulo 2 y al cálculo de los parámetros de la abstracción geométrica del primer control. En el anexo B se añaden nuevas figuras de prueba realizadas mediante las mejoras aportadas al algoritmo A* en el capítulo 3. Finalmente en el anexo C se amplían las simulaciones realizadas sobre la aplicación a entornos realistas en el capítulo 4. MEMORIA 14 Dada una región de Voronoi se definen su masa y su centroide como: , 2.18 , 2.19 donde es la función de densidad de masa de la abstracción, que determina que zonas de la región resultan más interesantes. Cuando dos regiones de Voronoi y son adyacentes, esto es que comparten una arista, se dice que los robots y son vecinos. En la Figura 5 se muestra un ejemplo de partición de Voronoi para un entorno con forma de circunferencia y 3 robots. Se puede ver como en color cyan se muestran los centriodes de la región asociada a cada robot y en azul la circunferencia que representa a la abstracción y las líneas que parten las áreas de movimiento de cada robot. Figura 5: Particiones de Voronoi para 3 robots Estas particiones son las que minimizan la función de localización óptima H para la mejor percepción de los robots, evitando ruido causado por grandes distancias [2]: 2.20 La función f corresponde con la función de percepción de los dispositivos, dependiente de la distancia entre los puntos de su partición y su posición, y la que da el peso de cada punto de la abstracción como se ha visto antes. Los centroides de cada una de las regiones de Voronoi minimizan a su vez la función H (ecuación 2.20) dentro de del área de la partición, asegurando una mejor percepción de la abstracción y el óptimo recubrimiento posible del área de la abstracción [2]. 2.21 Para calcular la región de Voronoi correspondiente a cada robot se ha de hallar en primer lugar la línea de puntos que están a igual distancia del robot que se ha seleccionado y sus vecinos, emparejándolos dos a dos. Estas rectas son las que corresponden a la mediatriz entre las posiciones de las parejas de robots. 2. CONTROL DE FORMACIONES 15 A continuación se obtienen los puntos de corte de cada una de estas rectas entre sí y con los límites del entorno y se seleccionan cuáles son los puntos que realmente determinan el espacio de puntos más cercanos a este robot, ya que algunos puntos de corte se encuentran fuera de esta región o incluso fuera del entorno y no determinan el área de movimiento de los dispositivos. Se ha de destacar que para que un robot calcule su partición ha de conocer únicamente la posición de sus vecinos y las variables de la abstracción. Con esos puntos límite de la partición de cada dispositivo se obtiene el peso y el centroide de la misma, lugar hacia el cual se desplaza dicho robot con el fin de evitar golpes entre ellos. Se ha considerado una abstracción con peso constante en toda su extensión, por lo que el peso total de la partición se corresponde con el área de la zona. Una vez hallado el diagrama de Voronoi a partir de las posiciones iniciales de los robots, cada uno calcula la acción proporcional al error entre su situación actual y el centroide de su región de Voronoi, de modo que el movimiento hacia el centroide garantiza que los robots mejoran la percepción del entorno, , 2.22 con la ganancia del control. Adicionalmente, es interesante destacar el hecho de que con este control se garantiza la ausencia de colisiones entre los robots, ya que éstos se mueven siempre dentro de sus regiones. El control propuesto en [2] considera un entorno estático Q. En este proyecto se ha extendido dicho control para que se considere un entorno dinámico, el cual va evolucionando hasta conseguir una nueva configuración. De esta manera se puede entender que el entorno representa la abstracción que engloba al conjunto de robots. Las entradas a aplicar, seleccionando en esta ocasión una abstracción circular, son proporcionales al error entre los parámetros de la formación objetivo y los actuales: , 2.23 . 2.24 La constante de la entrada para los dispositivos, , debe ser mayor que la de los parámetros de la abstracción, y , ya que si se produjesen cambio muy brusco en alguno de ellos los robots se podrían ver fuera su partición de Voronoi. Los parámetros de la abstracción se actualizan mediante las siguientes ecuaciones: , 2.25 . 2.26 A medida que se van desplazando los robots se va recalculando en cada iteración un nuevo diagrama con referencia a la situación de la abstracción, que se va moviendo para llegar sin error a la formación deseada. En todo momento los robots circulan hacia su centroide, de forma que el control no finaliza hasta conseguir que la abstracción cumpla todos los parámetros de destino y a su vez los dispositivos se encuentran sobre el centroide de su región. MEMORIA 16 Se representa en el esquema siguiente un breve resumen del bucle de control. > requiere ; > mientras , , repetir > calcular (ecuaciones 2.18 y 2.19); > calcular (ecuación 2.22); > calcular (ecuación 2.5); > calcular y (ecuaciones 2.23 y 2.24); > actualizar (ecuaciones 2.2 a 2.4); > actualizar centro y radio (ecuaciones 2.25 y 2.26); Tabla 2: Pseudocódigo del bucle de control mediante particiones de Voronoi A continuación se muestra un ejemplo de control considerando una abstracción en forma de círculo. Se representan las configuraciones iniciales y finales con sus correspondientes particiones de Voronoi y las acciones aplicadas a los robots. En primer lugar se muestran los resultados correspondientes a una abstracción formada por 8 robots. Se ha seleccionado una configuración final de centro (7,7) y radio 2. Se puede ver la simulación completa en el vídeo “controlVoronoi.avi”. Figura 6: Configuraciones inicial y final con particiones de Voronoi con N = 8 y = (7,7) y = 2 En la Figura 6 se observan las configuraciones iniciales y finales de los dispositivos, en azul y magenta respectivamente. En ambos casos se aprecia que todos los robots llegan a la configuración deseada, sin error en su posición respecto al centroide de su correspondiente partición de Voronoi. En la formación inicial se ve el cálculo inicial de las particiones, antes de comenzar a moverse. En la parte derecha se representa el trayecto desarrollado por los dispositivos entre las formaciones inicial y destino. Se aprecia que el movimiento es lineal, sin cambios bruscos de trayectoria y libre de colisiones. En cuanto a la acción aplicada a cada uno de los dispositivos, se muestran las acciones respecto a los ejes absolutos y las acciones lineal y angular en la Figura 7. 2. CONTROL DE FORMACIONES 17 Figura 7: Acción para control mediante particiones de Voronoi con N = 8 y = (7,7) y = 2 En las gráficas se observa que la velocidad es continua en el tiempo y que se respetan los límites en la acción. Se aprecia a su vez que la acción es mucho mayor e irregular al comienzo de la simulación, es decir, cuando los robots buscan su centroide inicial. Una vez en él se trasladan prácticamente a la par que la abstracción. Se encuentran simulaciones con este tipo de control en el anexo A.1, incrementando el número de robots y con formaciones decrecientes. Se adjunta un ejemplo de partición de Voronoi sobre una abstracción cuadrada. 2.4 ANÁLISIS En el apartado correspondiente al control mediante una abstracción geométrica, se ha reducido con éxito el número de variables a controlar y se ha conseguido que la formación llegue a una configuración objetivo, sin error en ninguna variable y manteniendo una acción lineal. Sin embargo se ha visto que la elipse no engloba a todos los dispositivos. Esta desventaja es importante, ya que a la hora de que la abstracción pase por un espacio reducido, como por ejemplo una puerta, no se asegura la ausencia de colisiones con el entorno. Si aplicamos una configuración en rectángulo se consigue que todos los robots estén dentro de la abstracción, pero se ha desestimado por ser un procedimiento demasiado conservador en el cálculo de los límites de la abstracción. También se ha de mencionar que este control no asegura la ausencia de choques entre los dispositivos. Otro inconveniente de este método es que necesita información global para obtener las variables que determinan la abstracción en cada momento. Por lo tanto el método no es escalable con el número de robots y surge el problema de la comunicación entre dispositivos para que todos puedan hallar las características de la abstracción a cada momento. Por último, tampoco existe la posibilidad de conseguir que los robots se muevan formando un patrón determinado, sino que únicamente se mueven para lograr una configuración final que cumpla con la abstracción objetivo. Por todo lo ello se ha desestimado su uso en las aplicaciones de este proyecto y se ha estudiado un control basado en las particiones de Voronoi. MEMORIA 18 Se ha comprobado que con el control mediante particiones de Voronoi tampoco hay error en la abstracción deseada y que, al contrario que con el anterior control estudiado, todos los robots se encuentran dentro de la circunferencia global, ya que se desplazan siempre dentro de su partición. Por ello se puede garantizar que no haya choques entre los dispositivos y el entorno. Los recorridos realizados por todos los robots son lineales y sin cambios bruscos en su trayecto, y la acción aplicada a cada uno de ellos es continua en el tiempo. Con dicho control cada robot determina su zona de movimiento conociendo únicamente las posiciones de sus vecinos y la de la abstracción, sin ser necesario datos tales como la situación de todos los dispositivos, de forma que se reducen los problemas de comunicación entre dispositivos lejanos entre sí. Además se asegura la optimización del área de la abstracción, con la única condición de que sea un espacio convexo y cerrado. Se ha de tener en cuenta que con este control se consiguen formaciones finales tanto crecientes como decrecientes, al contrario que en el control anterior que sólo funciona con configuraciones estrictamente crecientes. A pesar de que en este proyecto no se ha implementado, con este tipo de control existe la posibilidad de definir una determinada configuración a seguir por los robots dentro de la abstracción, así como seleccionar sus posiciones finales dentro de la misma. Por todas las ventajas mencionadas se ha decidido aplicar el control basado en las particiones de Voronoi con una abstracción dinámica para en el capítulo 4 a trayectorias en escenarios realistas. 3. PLANIFICACIÓN DE TRAYECTORIAS 19 3. PLANIFICACIÓN DE TRAYECTORIAS Se ha visto como se puede controlar el equipo de robots hasta una configuración objetivo. Resulta interesante calcular ahora, para un entorno dado, cuáles deben ser las características de la abstracción deseada. Para ello, en este capítulo se va a trabajar en la planificación de trayectorias. Se partirá del algoritmo de búsqueda denominado A* que encuentra un camino entre dos puntos en un mapa bidimensional siempre que sea posible, el cual queda descrito en el anexo B.1. A partir de él se realizarán mejoras que aporten mayor aprovechamiento del entorno respecto de la solución inicial dada por esta función, considerando posibles variaciones en la abstracción o mapas en los cuales se obtenga más beneficio al recorrer unas zonas u otras. 3.1 PLANIFICACIÓN CON ABSTRACCIÓN VARIABLE El algoritmo A* genera un recorrido entre dos posiciones dadas, pero todas las casillas tienen la misma medida, es decir, no considera variaciones en la abstracción. Para tareas como la exploración de superficies usando varios robots puede resultar más interesante cubrir la máxima superficie posible, o para poder pasar por una puerta, reducir el tamaño de la abstracción. La introducción de cambios en el radio de la abstracción plantea tres cuestiones en el algoritmo A*. En primer lugar hay que definir que casillas de diferentes radios son adyacentes en el mapa. En segundo lugar se han de modificar los obstáculos en función del tamaño de la abstracción. Por último hace falta definir el coste asignado al cambio de radio en la formación. Al comienzo de la planificación se determina un radio inicial, al igual que las coordenadas iniciales en el mapa. Con esta nueva posibilidad se puede añadir también un radio final para que la formación llegue a su destino o por el contrario dejar la posibilidad de que llegue en el radio que menor coste genere. Así como en posición se consideran como vecinas a una casilla aquellas que son adyacentes a la misma, el planificador únicamente considera como vecinas las casillas con radios inmediatamente superior e inferior al radio actual, evitando de esta forma cambios demasiado bruscos en la superficie que abarca la formación. Puesto que el planificador trabaja en un entorno discreto, únicamente se considera un subconjunto de posibles radios para la abstracción. En cuanto a los obstáculos, es obvio que éstos son distintos para diferentes radios de la abstracción. En función del tamaño de la formación se recalculan los obstáculos del mapa, garantizando así la ausencia de colisiones con el entorno para cada radio. En la Figura 8 se muestra el plano representado en la imagen, considerando abstracciones de tamaño 1, 3 y 5 respectivamente. Se aprecia como aumentan los obstáculos a medida que se incrementa el radio de la abstracción. Para cada tamaño de la abstracción se ven en blanco las casillas por las que se puede circular con dicha dimensión, quedando marcadas como obstáculos las casillas en negro. MEMORIA 20 Figura 8: Mapa 1 para radios 1, 3 y 5 Para añadir la posibilidad del cambio de radio en la abstracción se ha incluido un nuevo coste a minimizar. El coste en posición es claro y sencillo, la distancia euclídea entre casillas. Sin embargo el coste de modificar la forma de la abstracción, haciéndola más grande o más pequeña, requiere un análisis más profundo. En el proyecto se han propuesto 3 funciones de coste diferentes, analizándose las propiedades de cada una de ellas. En primer lugar se plantea la posibilidad de que no se asigne ningún coste al cambio de radio de la abstracción, de tal manera que: 3.1 A continuación se ha formulado una segunda función de coste inversamente proporcional al área, siendo una constante arbitraria, el número de radios disponibles y la posición que ocupa el radio a estudiar en el vector formado por los posibles radios, ordenados de menor a mayor. 3.2 Finalmente se ha propuesto asignar un coste constante a cada variación en el radio de la abstracción, con una constante arbitraria, la posición que ocupa el radio a estudiar en el vector formado por los posibles radios e la posición del radio del padre de la casilla actual en dicho vector. 3.3 En la Figura 9 se muestran las pruebas con las funciones anteriores sobre el mapa de la imagen izquierda de la Figura 8, definiéndose un vector de 4 posibles radios: (1, 3, 5, 7). La posición inicial y final es la misma en todas las representaciones, viéndose en rojo la primera y en azul la segunda. Para la realización de estas simulaciones se ha seleccionado siempre un radio inicial y final máximo, dando prioridad a que se empiece y se acabe el recorrido de la forma más expandida posible. Las casillas del recorrido se representan como círculos con centro en el punto central de la casilla y radio el que corresponde en cada caso. Figura 9: Trayectorias en mapa 1 con radio variable para diferentes funciones de coste asociado al radio 3. PLANIFICACIÓN DE TRAYECTORIAS 21 En la imagen izquierda de la Figura 9 se ha utilizado la función de la ecuación 3.1, en la que no se asigna ningún coste al cambio de radio ni a cada uno de los valores de la superficie abarcada. Claramente se aprecia que la función selecciona las casillas con menor radio posible, creciendo únicamente al final porque se le ha asignado un radio final máximo. Esto sucede debido a que se exploran primero las casillas con menor radio, por simple cuestión de programación. Al tener el mismo coste f todas las casillas la primera en la lista de abiertas siempre es la de menor radio. Para la trayectoria representada en la imagen central de dicha figura se ha asignado coste definido en la ecuación 3.2. En esta ocasión se asignan unos costes asociados a cada superficie inversamente proporcionales a su valor, para dar prioridad a cualquier trayectoria que maximice la superficie cubierta por la abstracción. Se observa que el radio siempre tiende a ser el máximo, encogiéndose únicamente para pasar entre obstáculos y volviendo a tener el mayor radio en cuanto es posible. Este tipo de coste podría ser interesante como se ha dicho antes en labores de exploración. En relación a esta función de coste, se ha de destacar que si se desea el mínimo radio posible se podría aplicar una función similar, ordenando en este caso el vector de radios de mayor a menor. Igualmente serviría para seleccionar un radio deseado, asignándole coste nulo a éste y mayores valores al resto. Finalmente en la imagen derecha de la Figura 9 se asigna un coste constante a cada variación de superficie para evitar que la abstracción esté constantemente creciendo o disminuyendo y tienda a un radio constante en la medida de lo posible (ecuación 3.3). Se ve que la superficie abarcada por la formación decrece para pasar por el primer espacio reducido y se mantiene constante en diámetro 3 hasta que, al llegar a la zona más estrecha, se reduce a 1 para poder atravesarla. En adelante se mantiene con el radio mínimo hasta llegar al final, donde vuelve a crecer de tamaño para cumplir las especificaciones de radio final. Se muestran más resultados en el anexo B.2. Parece obvio que dependiendo de las necesidades de cada tarea puede aportar mayor beneficio una función de coste u otra, lo que contiene una gran versatilidad al algoritmo para adaptarse a diferentes labores. MEMORIA 22 3.2 PLANIFICACIÓN CON COSTE EN FUNCIÓN DEL ENTORNO Hasta ahora se ha trabajado con planos en los cuales todas las casillas poseen coste cero. En este apartado se emplean mapas en los cuales haya casillas que tengan un coste menor que otras en función del entorno en el que se mueva la abstracción, es decir, que el paso por las mismas aporte un mayor beneficio que recorrer otras. De esta manera se incluyen las condiciones del entorno. Se plantea la posibilidad de leer a partir de un mapa de colores el valor que posee cada casilla o asignar su coste directamente en el código del programa, modificando el algoritmo de búsqueda A*. Se pueden asociar beneficios (valores negativos) o incremento de coste (valores positivos) a cada una de las casillas. A su vez se puede escoger si el valor que tiene una casilla en particular puede afectar a sus adyacentes, modificándose de esta forma la matriz de coste inicial del entorno. El coste de una casilla con coordenadas en el plano (i,j) se define como la suma de su coste inicial ( ) más el de las casillas con coste a extender dividido por la distancia euclídea a dicha casilla (c/d ), . 3.4 El coste a minimizar para el planificador es el mismo que en el algoritmo A* añadiéndole el valor en función del entorno, de tal manera que sigue primando el recorrido más corto posible aunque matizado por los requerimientos del plano, . 3.5 Se muestra en la imagen izquierda de la Figura 10 un ejemplo en el que se han seleccionado algunas zonas del plano donde es beneficioso pasar, en color rojo, y otras en las cuales es más costosa la circulación, en verde. Se puede ver en la figura central el mapa de costes calculado mediante la ecuación 3.4, donde las casillas beneficiosas obtienen menor valor en magnitud que las costosas. A pesar de ello se advierte en la imagen derecha que estos valores son suficientes para atraer la trayectoria hacia esas zonas y para sortear los lugares de mayor coste, modificando así su trayecto menos costoso en distancia. Figura 10: Mapa 2 con zonas con diferente valor, mapa de coste y trayectoria con diámetro constante 3 3. PLANIFICACIÓN DE TRAYECTORIAS 23 La prueba anterior se ha realizado con una abstracción constante, pero se puede modificar ampliando el subconjunto de radios. Cada una de las casillas en este caso tiene un valor equivalente a todas las casillas que cubra. A partir de la matriz de coste obtenida con la ecuación 3.4 se calcula el valor para cada casilla, con la suma de los costes de todas las casillas que abarcar la abstracción con ese radio, . 3.6 Se realiza una prueba con el mapa anterior donde el tamaño de la abstracción puede ser de 3 o 5 y se ha seleccionado para modelar el coste en función del radio la ecuación 3.2, siendo favorable el máximo tamaño de la formación. En la imagen izquierda de la Figura 11 se aprecia el mapa de coste para un tamaño de la abstracción mayor, 5. Se puede ver que los valores son mayores a los de la Figura 10, ya que en este caso abarca más casillas. En la figura derecha se ve que el camino recorrido por la formación es similar al del caso anterior, pero en esta ocasión circula en la mayor parte del trayecto con tamaño máximo, reduciendo su tamaño a 3 únicamente cuando no puede esquivar las zonas costosas con ese radio. Figura 11: Mapa de coste y trayectoria con diámetro variable 3 o 5 También se ha considerado la posibilidad de atraer la formación hacia las paredes, y para conseguir esta tarea se selecciona para determinar la trayectoria el coste acumulado de cada casilla y el valor asociado al entorno, calculado mediante la ecuación 3.4. 3.7 De esta manera no se tiene en cuenta la mayor brevedad en el trayecto, haciendo la función h igual a cero, sino más proximidad a una parte marcada. Mediante valores negativos se prima más desplazarse a zonas concretas que la mínima distancia, puesto que cuanto mayores (en módulo) sean estos valores negativos, más le interesará a la abstracción acercarse a ellos. En la imagen izquierda de la Figura 12 se aprecia un mapa de beneficios calculado mediante la ecuación 3.4, donde las paredes tienen un valor de -1 y al modificar sus adyacentes se obtiene dicho mapa. En el plano de la derecha se ve la trayectoria que se genera entre los puntos inicial y final, donde en este caso la formación circula en las zonas próximas a la pared sin tener en cuenta la distancia al destino, como se ha formulado en la ecuación 3.7. MEMORIA 30 Figura 16: Recorrido en habitación para limpieza de zonas puntuales El vídeo que reproduce este plan corresponde con “aplicacionesLimpiezaPuntual.avi”. Se pueden ver en el anexo C.1 más pruebas con un tamaño mayor y con abstracción variable. ANÁLISIS En este apartado se ha observado que mediante un código basado en mapas con beneficios (valores negativos) se puede conseguir una trayectoria en la cual lo más importante sea recorrer ciertas partes del mapa en lugar de conseguir un recorrido lo más corto posible entre dos puntos. Mediante un simple plan que una las habitaciones de un hogar, se asegura la limpieza de las esquinas donde más polvo se acumula. Del mismo modo, se puede modelar el algoritmo para obtener un camino que circule por zonas de gran suciedad. Por otra parte, el algoritmo tiene la pequeña desventaja de que se han de ajustar manualmente los parámetros que determinan cada uno de los mapas de coste del entorno. En el futuro sería interesante la asignación de estos costes de manera automática, usando la información de limpiezas previas, como por ejemplo la localización de lugares donde se suele acumular más la suciedad, las zonas que la ocasión anterior no se limpiaron, etc. Es interesante destacar que si se desea incluir un nuevo dispositivo de limpieza, si el tamaño de la abstracción es suficiente para su incorporación, se puede añadir sin tener que volver a hallar la trayectoria ni modificar el control, ya que el planificador es independiente del número de robots de la formación y el control escalable con dicha cantidad de dispositivos. 4. APLICACIÓN 31 4.2 EXTERIORES En lugares abiertos como pueden ser parques o bosques se plantean como tareas interesantes la exploración o el cuidado de jardines mediante formaciones de robots que trabajen coordinadamente. Para estas labores se apuesta por una formación lo más expandida posible que abarque así mayor superficie en cada recorrido. A su vez se considera un aspecto importante para la exploración que los dispositivos se muevan por zonas de fácil tránsito, como pueden ser calzadas o carreteras asfaltadas en lugar de charcos o barrizales. De esta manera no se estropean los robots con tanta facilidad. Del mismo modo en el caso de la limpieza de jardines se han de buscar los lugares de hierba y evitar las partes arenosas en la medida de lo posible. En primer lugar se ha adaptado un plano del entorno por el que se va a trabajar, donde también se ha contemplado la posibilidad de que haya partes encharcadas, para posteriormente crear una matriz de coste para cada casilla en función de la superficie que ocupe la formación. Para realizar las simulaciones correspondientes a exteriores se ha escogido el “Parque José Antonio Labordeta” de Zaragoza, antes denominado “Parque Primo de Rivera”. Para la construcción del plano se ha partido de un plano del lugar y una vista satélite del parque. Ambas imágenes se muestran en las figuras representadas a continuación (Figura 17 y Figura 18) y han sido extraídas de Google Maps (http//maps.google.es/). Figura 17: Plano del “Parque José Antonio Labordeta” Figura 18: Vista satélite del “Parque José Antonio Labordeta” El plano se ha adaptado manualmente, creando varias figuras en las que se resaltan las zonas de calzada, césped, tierra, agua y árboles u otros obstáculos por separado (Figura 19) y que el algoritmo integra en una matriz de valores única. MEMORIA 32 De esta manera se puede modificar fácilmente el mapa, por ejemplo si se realizan obras en alguna calzada, únicamente editando el plano que las representa, sin afectar al resto de las zonas. Figura 19: Planos por zonas: calzada, césped, arena, charcos y obstáculos En la imagen izquierda de la Figura 20 se muestra el mapa final combinando todos los anteriores en un día sin lluvias y en la derecha tras una tormenta. Se pueden ver las zonas de calzada en gris, las de hierba en verde, las de arena en marrón, los obstáculos y árboles en negro y los charcos en azul. Figura 20: Plano adaptado del “Parque José Antonio Labordeta” (sin y con charcos) Mediante la escala de las vistas satélites se ha determinado que cada pixel en la figura corresponde con 2 m en la realidad, por lo que éste será el mínimo diámetro que posea la formación de robots. Con el mapa inicial, se calculan los diferentes mapas de obstáculos, correspondientes a distintos radios, como se ha explicado en el apartado 3.2. En este caso se han escogido radios desde 1 m a 5 m, con 4. APLICACIÓN 33 saltos de un metro entre cada uno de ellos. En la Figura 21 se muestran los mapas correspondientes a abstracciones de tamaño 1, 3 y 5 metros de radio. Figura 21: Planos parque para radios 1, 3 y 5 m A continuación se asignan costes positivos a cada zona, siendo ordenadas de mayor a menor: charcos, tierra, césped y zonas de calzada para el caso de la exploración. En cuanto al cuidado de jardines serán las parcelas verdes las que obtengan mayor beneficio, teniendo estas zonas un valor negativo. De esta manera se sigue manteniendo que circular por la calzada no cuesta nada pero es más beneficioso para la formación circular por el césped. El resto de las partes conservan el mismo coste que en exploración. Los costes de cada zona se ven en la Tabla 3: Carretera Césped Tierra Agua Exploración 0 10 20 30 Cuidado de jardines 0 -10 20 30 Tabla 3: Costes asociados a cada zona de parque para exploración y cuidado de jardines MEMORIA 34 Los mapas de costes correspondientes a exploración y cuidado de jardines se muestran en la Figura 22 y la Figura 23. Figura 22: Mapa de costes del entorno para exploración en parque (radio 1 m) Figura 23: Mapa de costes del entorno para cuidado de jardines en parque (radio 1 m) La Figura 24 y Figura 25 corresponden al mismo mapa considerando un día de lluvia. Figura 24: Mapa de costes del entorno para exploración en parque con charcos (radio 1 m) Figura 25: Mapa de costes del entorno para cuidado de jardines en parque con charcos (radio 1 m) Para la planificación de trayectorias se ha seleccionado como coste total el propuesto en la ecuación 3.5, siendo el nuevo valor de cada casilla la suma de los valores de todas las que la formación ocupe (ecuación 3.6). También se asocian valores a cada uno de los diámetros de la configuración de dispositivos. En este caso se desea obtener una formación más expandida, por lo que serán más costosas las configuraciones de 4. APLICACIÓN 35 menor superficie que las más amplias, teniendo como coste asociado el coste enunciado en la ecuación 3.2 . De esta forma se consigue que los dispositivos minimicen el recorrido pero a la vez el coste del entorno hace que, si es necesario, se desplacen de la trayectoria más corta para obtener mayor beneficio por la zona por la que se mueven y que el coste de la superficie haga que, siempre que sea mejor, la formación se expanda lo máximo posible. A continuación se muestran los resultados obtenidos en dos simulaciones, una para labores de exploración y otra para cuidado de jardines. Para cada una de ellas se representan pruebas sobre escenario seco y con charcos, observándose que en algunos casos genera menor coste desplazarse por unas zonas en lugar de por otras. En estas simulaciones se han empleado 5 robots de r = 0.2m, iguales al de la Figura 1. EXPLORACIÓN A continuación se muestra el camino seleccionado para una formación con radio variable entre 1 y 5 m, aumentando cada uno un metro respecto de su radio anterior. El trayecto comienza en la zona inferior y la casilla de destino está en el centro del parque. El vídeo correspondiente es el “aplicacionesExploracion1.avi”. Figura 26: Exploración en parque con radio variable de 1 a 5 m MEMORIA 36 En la Figura 26 se aprecia que el algoritmo genera una trayectoria en la cual en la medida de lo posible se circula por zonas con coste del entorno nulo, a pesar de que el camino más corto sería siempre la línea recta. Al final del recorrido se desplaza por una parte arenosa, pero es la mínima posible, ya que al llegar al cruce de caminos podría ir por la tierra directamente y sin embargo aprovecha la carretera hasta que se encuentra más cerca de la casilla destino. Durante la mayor parte del recorrido la abstracción circula con el radio máximo permitido (5 m), encogiéndose hasta radio 1m en las zonas de mayor coste. De esta forma se consigue la máxima expansión en carreteras anchas, hasta que al llegar al cruce con la siguiente calzada a seguir la formación se encoge para no salirse de ella. Se adjuntan más pruebas en el anexo C.2, en las cuales se comprueba cómo afectan las diferentes funciones que modelan el cambio de tamaño, determinadas en las ecuaciones 3.1 y 3.2 y las diferentes trayectorias seleccionadas para varios valores de radio constante. Finalmente se presenta una prueba con radio variable (de 1 a 5 m), pero en esta ocasión simulando un día de lluvia en el que se han formado charcos que dificultan la circulación. El vídeo que representa esta prueba corresponde al “aplicacionesExploracion2.avi”. Figura 27: Exploración en parque con charcos con radio variable de 1 a 5 m Se puede ver en la Figura 27 que el camino es el mismo que cuando el parque está seco (Figura 26). Sin embargo se aprecia claramente que varias veces la formación se encoge para evitar pasar por zonas en las que haya charcos, volviendo a crecer inmediatamente una vez esquivados éstos. 4. APLICACIÓN 37 De esta manera se combina la importancia de la circulación abarcando la mayor superficie posible con la necesidad de evitar desplazarse sobre lugares con altos costes del entorno. CUIDADO DE JARDINES El trayecto comienza al norte del mapa y la casilla de destino se sitúa en el centro del parque. Se representa una prueba con radio variable de 1 a 5 m, al igual que se ha podido observar en las simulaciones para la exploración de parques. Se puede ver la simulación en el vídeo “aplicacionesJardines1.avi”. Figura 28: Cuidado de jardines en parque con radio variable de 1 a 5 m En este caso (Figura 28) se observa que el recorrido transcurre en su mayor parte por zonas con césped, en las cuales se obtiene beneficio del entorno. Al poco de comenzar el camino se traslada a partes con hierba, buscándolas en todo momento en su trayectoria. Para pasar entre unos jardines y otros la formación se mueve por la calzada, ya que estos lugares tienen coste nulo como se ha comentado anteriormente. Aunque la formación puede variar su tamaño, se ha considerado importante para estas pruebas que la superficie que cubran los robots sea la máxima posible. Como para el cuidado de jardines las zonas verdes aportan beneficios y las carreteras no suponen coste, en este camino no es necesario que se encoja la abstracción porque en ningún caso circular con este diámetro más grande aporta coste alguno. MEMORIA 38 En el anexo C.2 se pueden ver varias pruebas con diferentes costes asociados a las zonas del parque y simulaciones con radio constante. En último lugar se muestra una simulación con radio variable de 1 a 5 m sobre el parque representando un día de tormenta. El vídeo que representa este plan es el “aplicacionesJardines2.avi”. Figura 29: Cuidado de jardines en parque con charcos con radio variable de 1 a 5 m Se aprecia en la Figura 29 que la mayor parte del recorrido transcurre con superficie máxima, de manera que únicamente se encoge una vez para poder esquivar zonas encharcadas. El recorrido es similar al realizado con el parque seco, a excepción de las situaciones en las que tiene que desviar un poco su trayectoria para evitar pasar sobre lugares mojados que puedan estropear los dispositivos. ANÁLISIS Se ha observado en los resultados obtenidos que este programa puede aportar grandes beneficios para generar trayectorias a través de parques y bosques, ya que aunque se ha de modelar el plano del lugar para cada ocasión, una vez ajustado se pueden aplicar variantes para conseguir diferentes recorridos. 4. APLICACIÓN 39 Es interesante la posibilidad de asignar un valor en función del entorno a cada zona y así evitar que los dispositivos circulen por lugares en los que el territorio por el que se desplazan cause deterioro con mayor facilidad que otros sitios, como por ejemplo teniendo coste nulo en zonas asfaltadas y alto coste en las arenosas. Se considera a su vez importante que conociendo el terreno y las zonas con mayor facilidad de formación de charcos tras unos días de tormenta se pueda crear un nuevo plano en el que éstas se sitúen y se puedan esquivar en la medida de lo posible al planificar el recorrido. 47 ÍNDICE DE TABLAS Tabla 1: Pseudocódigo del bucle de control mediante una abstracción geométrica .................................................................................................... 12 Tabla 2: Pseudocódigo del bucle de control mediante particiones de Voronoi ............................................................................................................. 16 Tabla 3: Costes asociados a cada zona de parque para exploración y cuidado de jardines .......................................................................................... 33