Heuristic Drone Pathfinding Over Optimized Charging Station Grid

Abstract

We proposed a novel optimisation framework for drone-based operations which consists of the optimised Charging Station (CS) grid and the pathfinding heuristics for the drone. The proposed pathfinding heuristics are assessed for two different (triangular and square) CS grid configurations that are optimised for the drone range. We presented the case study of a boat rescue operation that is carried out in the sea. The minimisation of the “flight distance” and “number of chargings” are the objectives for the drone party and the minimisation of the “average waiting distance” (AWD) is the objective for the boat party. We studied the “single drone with many entities” case which is a form of Travelling Salesman Problem (TSP). We presented mathematical analysis and simulation results for the effectiveness of the pathfinding heuristic which we called the “red-grey path” heuristic. A novel and fast TSP heuristic was also proposed as part of the pathfinding heuristics and its performance was assessed.

Keywords

• UAV path optimization
• heuristic pathfinding for UAVs
• optimized charging station grids for electric vehicles
• multi-objective multi-party optimization
• TSP heuristics