Cost-Effective Placement of Recharging Stations in Drone Path Planning for Surveillance Missions on Large Farms

Abstract

The energy limitation remains one of the biggest constraints in drone path planning, since it prevents drones from performing long surveillance missions. To assist drones in such missions, recharging stations have recently been introduced. They are platforms where the drone can autonomously land to recharge its battery before continuing the mission. However, the cost of those platforms remains a significant obstacle to their adoption. Consequently, it is important to reduce their number while planning the path of the drone. This work introduces the Single Drone Multiple Recharging Stations on Large Farm problem (SD-MRS-LF). A large farm is considered as an area of interest to cover with a set of candidate locations where recharging stations can be installed. The aim is to determine the path of the drone that minimizes the number of locations for recharging stations as well as the completion time of the surveillance mission. This path planning problem falls within the realm of computational geometry and is related to similar problems that are encountered in the field of robotics. The problem is complicated due to environmental constraints on farms such as wind speed and direction, which produce asymmetries in the optimal solution. A back-and-forth-k-opt simulated annealing (BFKSA) approach is proposed to solve the defined problem. The new approach is compared to the basic back-and-forth (BF) and a K-opt variant of the well-known simulated annealing (KSA) approach over a set of 20 random topologies in different environmental conditions. The results from computational experiments show that the BFKSA approach outperforms the others, in terms of providing feasible solutions and minimizing the number of recharges.

Keywords

• drone path planning
• recharging stations
• back-and-forth-k-opt simulated annealing
• large farms