# Autonomous 3D Exploration of Large Structures Using an UAV Equipped with a 2D LIDAR
## 6 Results and Discussion
### Execution Time  
To understand the bottlenecks of the system, the execution time of the mission manager was broken down into tasks. From the view of the mission manager, the time of the mission was divided into one of three tasks: Visiting waypoints, planning the path, or analysing the known world to find the next sample point. A preliminary study showed exploration to be the longest task to execute. The data is illustrated in Figure 10. In this graph, the task of exploration had an uneven execution time. The task could complete faster when restricting the search space to local exploration. Oppositely it could take longer when all the space is analysed (global exploration). Due to the impact on the overall execution time, the global search was optimised. As a first approach, the map is always searched from the same starting point. Figure 10b shows a detail containing the last four global searches as well as the execution time of the frontier algorithm. Each search was fast, but an increasing number of searches were needed. Moreover, for each frontier, all the safety checks were performed. For each potential goal, up to nine flyby options were analysed. For each flyby, space was discretised to search for unknown space and obstacles, along with all the required checks. In short, for each flyby, the goal manager went through each requirement of safety. The critical insight of Figure 10b is that fewer frontier searches resulted in a shorter task time. The off the shelf iterator of octomap started the search always at the same point. As the mission progressed, it became less likely that the first frontiers found would be suitable goals. If these voxels were still frontiers, it was because there were obstacles in their vicinity that prevented safe sampling. A circular iterator was introduced to disperse the focus of the search through the whole tree. With this iterator, the search began where the last global search selected a goal. One voxel was only considered again after examining the whole tree. The circular search ensured that the known space has significantly changed when next considering that particular voxel. The impact is shown in Figure 11. There were only two instances of exploration taking over 8 min, as opposed to the six occurrences seen in Figure 10a. Additionally, the maximum exploration time dropped from 30 min to 19 min. Figure 11a shows all tasks together. Except for global exploration, none of the tasks took more than 2 min. By adjusting the maximum search time of the planner, it resulted in a success rate of 84% to find a path. The bottleneck of the system was the global exploration. The last global search was the one that took more time. It served only to verify that the exploration had finished, the collection of data ended with the last waypoint visited. Figure 11b is a detail of the same dataset. The global exploration was removed. The last waypoint visited roughly 45 min, which was 19 min sooner than the end of the exploration. When this analysis extended to all the runs, as shown in Figure 12, the global exploration was consistently responsible for over half the total mission time. In terms of computation time per view, the average was 6 min and 38 s \(\pm\) 1 min and 56 s. The median was 6 min, bounded by 5 min and 19 s in the best case and 10 min and 28 s in the worst case. Due to the limited options to sample the unknown space, the frontiers were often not observable. Although the resulting processing time per view was high, the location variability increased as more voxels were analysed, affording a higher information acquisition. Figure 10: Time used in exploration in one run with a linear iterator. (**a**) Elapsed time for each task. (**b**) The total time for the exploration task and the time used in the frontiers algorithm. Figure 11: The execution time the mission manager spent in each task, in one run with a circular iterator. (**a**) All four tasked scaled together and (**b**) just local exploration, path planning, and visit waypoints.