Departamento de Computación

El uso de micro vehculos aéreos (MAVs^₁, por sus siglas en inglés) en la exploración y el mapeo 3D de locaciones interiores desconocidas puede evitar peligros potenciales para los seres humanos. Entre estos peligros se encuentran derrumbes de edicios, exposición a sustancias tóxicas y activación accidental de explosivos. En sitios de gran tamaño, la exploración puede llevarle mucho tiempo a un solo MAV, cuya duración de vuelo ininterrumpido es de aproximadamente 20 minutos. Dicho aspecto difícilmente puede ser mejorado con la incorporación de baterías de gran tamaño, debido a las capacidades de carga limitadas de los MAVs. El problema principal de realizar exploración y mapeo 3D de locaciones interiores, utilizando multiples MAVs, es coordinar el movimiento de dichos MAVs para generar un mapa de ocupacion 3D de un entorno desconocido. Entre las dificultades que se presentan, al tratar este problema, se encuentran las posibles colisiones entre MAVs durante la exploración de una región o la exploración de una misma región múltiples veces. La construcción del mapa también presenta inconvenientes, debido a que los MAVs pueden llegar a mapearse mutuamente como parte del entorno, obteniendo como consecuencia la adición de elementos externos al mapa. El problema de exploración y mapeo 3D multi-MAV ha sido poco tratado en la literatura relacionada, ya que los trabajos existentes utilizan un solo MAV o se limitan a exploración multi-MAV en dos dimensiones con una altura de vuelo fija. La propuesta presentada en este trabajo de tesis consiste en asignar una region a explorar a cada MAV, utilizando una partición del espacio definida por un diagrama de Voronoi en 3D, y posteriormente construir el mapa de dichas regiones, utilizando un algoritmo de exploración basada en frontera. Debido a que el diagrama de Voronoi genera particiones independientes del espacio para un conjunto de puntos, los MAVs pueden explorar sus respectivas regiones sin riesgo de colisiones entre sí. Puesto que el espacio total a explorar es el mismo, el uso de multiples MAVs puede reducir el tiempo total de exploración. Con respecto a la construcción del mapa, se propone un proceso de limpieza en el cual se eliminen los rastros dejados por los MAVs mapeados entre sí, a través del algoritmo de relleno por inundación. Este proceso de limpieza es posible debido a que, durante la exploración, los MAVs nunca están en contacto con el resto del mapa. Por último, se realizó una implementación de esta propuesta en la plataforma robótica abierta ROS, utilizando componentes existentes de mapeo, exploración y planificacion de movimiento. Dicha implementación se encarga de coordinar la exploración de MAVs ARdrone 2 simulados en Gazebo. En los experimentos realizados se observó que, a medida que se incrementa el número de MAVs, la exploración empeora. Esta stiuación se debe principalmente a la carga computacional de la simulación. Palabras clave: exploracion, mapeo, coordinacion, Voronoi, multi-MAVs.

¹Micro Aerial Vehicles

Abstract

The use of micro aerial vehicles (MAVs) in the 3D exploration of unknown indoor locations can avoid potential hazards for humans. Some of these hazards are the collapse of buildings, the exposure to toxic substances, and the accidental activation of explosives. In large buildings, exploration can long last for a MAV, whose ying time is around of 20 minutes. This aspect can hardly be improved by mounting bigger batteries, due to the payload restrictions of MAVs. The main problem with doing 3D exploration in indoor locations using multiple MAVs is the coordination of the MAVs movement to generate a 3D occupancy map of an unknown destination. Some of the difficulties that appear when solving this problem are the possible collisions among MAVs during the exploration of a region and the exploration of the same area multiple times. The map building also shows issues because MAVs can map to each other as part of the indoor location, obtaining as a consequence the addition of extra elements to the map. The multi-MAV 3D exploration problem has been few solved in the related literature, since the existent proposals use only one MAV or are limited to multi-MAV exploration in two dimensions using a fixed height. The proposal shown in this thesis consists in the assignation of a region to be explored by each MAV using a space partition defined by a 3D Voronoi diagram and then building a map of those regions, using a frontier-based algorithm. Since the Voronoi diagram generates independent partitions of the space for a set of points, the MAVs can explore their perspectives regions without risk of collisions with each other. Since the total space to be explored is the same, the use of multiple MAVs can reduce the total exploration time. Concerning the map building, a cleaning process is proposed in which the traces left by the mapped MAVs are eliminated through the flood fill algorithm. This cleaning process is possible because MAVs are never in contact with the map. Finally, an implementation of our proposal was performed on the open robotics platform ROS, using existing components for mapping, exploration, and motion planning. This implementation coordinates the exploration of simulated MAVs AR.Drone 2.0 in Gazebo. In the experiments performed we observed that as the number of MAVs increases, the exploration deteriorates. This situation is mainly due to the computational requirements of the simulation. Keywords: exploration, mapping, coordination, Voronoi, multi-MAV