Path and Route Planning for Indoor Monitoring with UAV : An Evaluation of Algorithms for Time-constrained Path and Route Planning in an Indoor Environment with Several Waypoints and Limited Battery Time

Abstract: Unmanned flying vehicles (UAVs) are tools that can be used in a variety of scenarios. The most common areas of application are outdoors, where there are not many obstacles to take into consideration when planning a route. In indoor scenarios, the requirements on the path planning system of the UAV becomes stricter, as these scenarios tend to contain more obstacles compared to flying at higher altitude outdoors. Considering a drone with multiple objectives (waypoints to visit), two problems initially come to mind, namely path planning and combinatorial optimization. To finish the objectives in the most effective way, the optimal path between the waypoints needs to be calculated, as well as the order in which the waypoints need to be visited. Another challenge is the fact that the UAV runs on limited battery capacity, and thus might not be able to finish the objectives before running out of battery. Therefore, the combinatorial optimization needs to include visits to a recharging station. The objective of this thesis is to combine and modify methods for path planning and combinatorial optimization in a way that a route can be calculated within a limited time budget, to allow the computation to be executed “on the fly”. The method used for path planning is ANYA, and the two methods used for the combinatorial optimization are ant colony optimization (ACO) as well as the Lin-Kernighan-Helsgaun (LKH) method. The nearest neighbor method (NN) will be used as a baseline for comparison. We propose an algorithm to include the battery constraint in the optimization. To evaluate the algorithms, we measure the computational time, to know if the method works in real-time, and also the estimated time for the UAV to finish the route, which will determine the energy efficiency of the route. We find that the ACO’s solutions improve over time, but require a long computational time, which makes it not suitable for small time budgets. LKH produces better routes than the NN method, and does so within the chosen time budget, as long as the number of waypoints is limited. The algorithm to optimize the trips to the recharging station works better than the previous use of LKH for this specific problem.