On Theoretical Trajectory Planning of Multiple Drones To Minimize Latency in Search-and-Reconnaissance Operations

Abstract

Following the recent advances in drone technologies, various algorithmic optimization problems related to the effective operation of drones are drawing lots of attentions. This paper considers two interesting multiple-drone-assisted search-and-reconnaissance scenarios, in each of which, the trajectory optimization of multiple drones is of great significance to minimize the latency in the system. In the first scenario, multiple drones, whose moments of mobilization are not necessarily the same, are trying to urgently collect intelligence from a given point of interest, and we would like to minimize the task completion time, i.e., the time period between the moment that the first drone commences its operation to the moment that the intelligence from all of the points are collected, by optimizing their trajectories. In the second scenario, multiple drones with different speeds, are hovering around the same routes to regularly collect intelligence from highly geographically-diversified points of interest over an extended time period, and we would like to minimize the worst-case data refreshment rate, the largest time gap between two consecutive observations over the same point of interest. In this paper, we formally define each problem, prove its NP-hardness, and propose an approximation algorithm for it. We also conduct a simulation to study the performance of our result.