Safe Optimistic Path Planning for Autonomous Drones under Dynamic Energy Costs

Abstract

Unmanned aerial vehicles or so-called drones are already used in several applications to perform different sensing and monitoring missions. A central problem is to plan these missions so as to minimize the completion time. This planning must also consider the typically limited autonomy of drones and the need to change their batteries in order to support longer missions. The problem becomes even harder when multiple drones are involved and there is uncertainty about the energy that will be consumed to move between the points of interest in the target area. In this paper, we present a heuristic algorithm for tackling this problem in an online fashion, which takes into account the actual energy costs that occur during the mission in order to adapt the planned paths. The algorithm works in an optimistic way, assuming that the costs will not always be the worst possible. Still, it guarantees that all vehicles will always make it back to the base station. The algorithm is evaluated via simulation experiments for a range of scenarios. Our results show that the proposed heuristic can significantly reduce the mission time of a conservative offline solution by up to 51%, while achieving up to 18% better results compared to a pessimistic online variant that plans the paths of the vehicles assuming the worst possible costs. © 2021 IEEE.