Autonomous 3D Online Exploration of Large Unknown Environments with a UAV equipped with a 2D Laser

Abstract

This Thesis sets out to develop an architecture for the 3D autonomous exploration of an industrial complex without prior knowledge of the environment with a UAV equipped with a low-cost 2D laser sensor. Following the Model Based Systems Engineering (MBSE) methodology, the architecture has a modular design that is agnostic of the on-board autopilot and the particular vehicle characteristics. One of the main goals of the design is reusability through hardware abstraction while imposing few requirements to the execution capabilities of the vehicle. Thus, autonomous vehicles from different manufacturers and research groups can be easily adapted to fit within the architecture. The first step in achieving efficient autonomous exploration is to choose a suitable data structure where the information about the environment is stored. The world representation is the fundamental infrastructure over which the architecture is built because it is the component that recurrently supplies the information needed to select sampling locations and to generate both the path and the sampling manoeuvre. Our results show the octomap implementation of a sparse octree to be suitable to store and organize the spatial information of large, unstructured, near-static scenarios, reducing for instance the number of iterations needed for pathfinding in 75% of the queries. The octree allows for primitive computation time compatible with limited processing power and memory usually available on-board UAVs. This world representation is generic, decoupled both from the sensor supplying the data and from the platform executing the tasks. Additionally, the generation of the octree is deterministic - each stream of data will always generate the same octomap instance. During the environment exploration, autonomous path planning should ensure safe maneuvers avoiding the obstacles around based on the chosen sparse grid representation. In an exploration scenario, the unexplored space can contain obstacles, and for this reason, the planner conservatively treats the unknown space as an obstacle. In addition, the map is constructed during exploration, so each path request evolves over different versions of the map as the UAV is moving, and precalculated distances from previous iterations cannot be fully exploited. On one hand, due to the large dimensions of the space to be explored, the computation time must scale well with the length of the generated path. On the other hand, for industrial or commercial use the path planner must provide performance guarantees and repeatability about the results. Taking into account all these requirements, we have chosen the Lazy Theta Star algorithm for path planning and we have implemented it over the sparse grid world representation. The planner scales to paths up to a hundred times the maximum resolution size of the environment representation and treats unknown space as an obstacle. Its performance has been tested in outdoor flights in the framework of the MarineUAS and SAFEDRONE European projects and the generated ROS library was presented at the RosCon conference in 2018. We have developed and implemented an autonomous exploration strategy based on the frontier algorithm over the sparse grid representation mentioned above. This strategy successfully identifies interesting sample locations with the frontier algorithm, taking advantage of the spatial organization embedded into the octree to order the frontiers. First, the search for frontiers is done locally to minimize the length of the flight path, and then, if no frontier is available, the global exploration ensures full coverage of the map. For each frontier, the exploration strategy searches for a flyby sampling manoeuver that fits into the available free space. We have compared an heuristic which follows the spatial organization of the octree for exploration with two other approaches from the literature: the classic nearest neighbour approach and an occupied space centric heuristic. The results show that the median of the execution time of the three heuristics is similar, but our heuristic enables the system to explore more volume. Finally, it should be mentioned that the whole approach has been tested using both Software-in-the-Loop (SitL) and Hardware-in-the-Loop (HitL) development environoments, as well as with a real multi-copter in outdoors flights.

Esta Tesis aborda el desarrollo de una arquitectura para la exploración autónoma en tres dimensiones de complejos industriales sin información a priori del entorno mediante un vehículo aéreo no tripulado (Unmanned Aerial Vehicle -UAV- en inglés) equipado con un láser 2D de bajo coste. Siguiendo la metodología MBSE (Model Based Systems Engineering), la arquitectura tiene un diseño modular que es independiente del autopiloto a bordo y de las características particulares del vehículo. Uno de los objetivos pricipales del diseño es una reusabilidad mediante la abstracción del hardware imponiendo pocos requisitos a las capacidades de ejecución del vehículo. De ese modo, distintos vehículos de diversos fabricantes se pueden adaptar fácilmente a la arquitectura. El primer paso para lograr una exploración autónoma eficiente es la elección de una estructura de datos adecuada en la que almacenar la información del entorno. La representación del mundo es la infraestructura fundamental sobre la que se construye la arquitectura dado que es el componente que de manera recurrente proporciona la información necesaria para seleccionar localizaciones en las que muestrear el entorno y para generar tanto el camino como la maniobra de muestreo. Nuestros resultados muestran que la implementación octomap con un árbol tipo octree es adecuada para almacenar y organizar la información espacial de escenarios casi estáticos, no estructurados y de grandes dimensiones, reduciendo por ejemplo el número de iteraciones necesarias para la búsqueda de caminos libres de obstáculos en un 75% de las peticiones. El octree permite un tiempo de cálculo de las primitivas compatible con las limitaciones en capacidad de cómputo y memoria típicas a bordo de un UAV. Esta representación del entorno es genérica y está desacoplada tanto de la plataforma que ejecuta las tareas como del sensor a bordo que proporciona las medidas. Además la generación del octree es determinista - cada flujo de datos siempre generará el mismo octomap. Durante la exploración del entorno, la planificación de caminos autónoma debe asegurar maniobras libres de obstáculos en base a la representación del entorno elegida. En un escenario de exploración, el espacio no explorado puede contener obstáculos, y por ese motivo, el planificador trata ese espacio desconocido de manera conservadora como obstáculos. Además, el mapa se construye durante la exploración por lo que cada petición de cálculo de camino evoluciona sobre distintas versiones del mapa a medida que el UAV de mueve, por lo que no se puede explotar totalmente el uso de distancias precalculadas de iteraciones anteriores. Por un lado, dadas las grandes dimensiones del espacio a explorar, el tiempo de cálculo debe escalar bien con la longitud del camino generado. Por otro lado, la uso comercial o industrial, el planificador de caminos debe ofrecer unas ciertas garantías de rendimiento y repetibilidad. Teniendo en cuenta todos estos requisitos, hemos seleccionado el algoritmo Lazy Theta Star para la planificación de caminos y lo hemos implementado sobre la representación del entorno descrita anteriormente. Este planificador escala bien para caminos cien veces mayores que el tamaño de la máxima resolución de la representación del entorno y trata el espacio desconocido como obstáculos. Su rendimiento se ha probado en vuelos en exteriores en el marco de los proyectos europeos MarineUAS y SAFEDRONE y la librería ROS (Robot Operating System) generada fue presentada en la conferencia RosCon en 2018. Se ha desarrollado e implementado una estrategia de exploración autónoma basada en el algoritmo de fronteras sobre la representación del entorno elegida. Dicha estrategia identifica con éxito lugares interesantes de muestreo con el algoritmo de fronteras aprovechando la organización espacial dentro del octree para ordenar las fronteras. En primer lugar, la búsqueda de fronteras se hace localmente para minimizar la longitud del camino a generar, y después, si no se encuentra ninguna frontera, la exploración global asegura que se cubre el mapa por completo. Para cada frontera, la estrategia de exploración busca una maniobra de exploración dentro del espacio libre. Hemos comparado una heurística que sigue la organización espacial del octree para la exploración con otras dos aproximaciones de la literatura: la clásica del vecino más cercano y una heurística centrada en el espacio ocupado. Los resultados muestran que la mediana del tiempo de ejecución para las tres heurísticas es similar, pero nuestra heurística permite al sistema explorar más volumen. Finalmente cabe mencionar que toda la aproximación presentada en la Tesis ha sido validada utilizando entornos de desarrollo SitL (Software-in-the-Loop) y HitL (Hardwarein- the-Loop), así como en vuelos realizados con un multicóptero en exteriores