# Autonomous 3D Exploration of Large Structures Using an UAV Equipped with a 2D LIDAR
## 2 Related Work  
The problem of exploration is well known in research. The theoretical exercise of considering a robot a geometrical point has been progressively adapted to the reality of guiding a UAV as it maps a 3D, unknown world. The exploration strategies proposed in [26] have been repeatedly adapted to UAVs, solving also path planning with the Rapid Exploring Random Trees (RRT) algorithm. [PERSON] et al. [19] proposes an architecture where RRT plans online with a receding horizon, sampling possible positions. It is an example of modular architecture, where the choice of the objective function switches planning for either the exploration of unknown volume or inspection of a given surface. [PERSON] et al. [20] uses RRT to tackle the added challenge of exploring a degraded visual (dark) GPS-denied environment. The RRT is part of a two-step, receding horizon, belief space-based approach that first generates branches to maximise information gain and in a second step, a new tree is sampled to minimise localisation uncertainty, generating collision-free paths. [PERSON] and [PERSON] [27] present a system for high-resolution 3D reconstruction combining both the volumetric map and the reconstructed surfaces to evaluate the model completeness. Space is divided into visiting sectors, taking advantage of the spatial organisation of the octree that is given a visitation order with A*. The algorithm first extracts inaccurately reconstructed surfaces by analysing the quality and trend of the surfaces from the Truncated Signed Distance Fields (TSDFs) and extracts frontiers from the volumetric map. Frontiers, introduced by [PERSON] [28], are defined as known, free space that has neighbouring unknown space. RRT is used to select a goal within a sector, maximizing the unknown visible space and penalizing distance. Focusing on the speed of the UAV, [PERSON] et al. [29] takes advantage of the camera's field of view to restrain the search space in a way that enables the UAV to sustain the speed. The classical frontier algorithm is responsible for selecting the goal, first searching inside the field of view, and then, when there are no frontiers inside the frustum of the camera, searching globally. Again, sampling-based RRT* is responsible for generating the path. [PERSON] et al. [30] also used the field of view to restrict the search space coupled with a RRT path planner. Instead of frontier finding, the goals are selected using a historically aware Next Best View Planner (NBV), adjusting the orientation of the UAV to maximise information gain. Other approaches do not use sampling based algorithms for path planning, as is the case in [PERSON] et al. [14]. This work solves both the exploration and the coverage problems with a two-step approach. Firstly, the goal state is chosen through maximization of the information gain, weighted by the cost to get there. Then, a path to the goal is generated maximizing coverage, with the given path cost and planning time budgets. To cross a high-density scenario, such as a forest, [PERSON] et al. [31] use a methodology similar to the NBV problem. Sampling from within the view of the sensor, multiple intermediate goals are selected to maximise a goal-seeking reward and exploration gain. [PERSON] et al. [16] achieves active mapping with a two-stage approach of local and global planning. As a first step, several paths are calculated using [PERSON]'s algorithm with the motion primitives to reach frontiers clustered into regions of high information gain. The selected trajectory is then refined using a gradient-based approach by maximizing an information-theoretic objective function based on Cauchy-Schwarz quadratic mutual information. However, the stochastic nature of the sampling-based approaches makes the certification for industrial use more complex. [PERSON] et al. [32] employs Information Potential Fields (IPF) for planning. The IPF contains both frontiers as interest regions and the obstacles as repelling fields. The exploration strategy is history aware to avoid local minima.