Unmanned Surveillance Problem: Mathematical Formulation, Solution Algorithms, and Experiments

摘要

Modern technologies used in military operations, as well as in many civil applications, have become common in recent years. Unmanned aerial vehicles play a key role in tasks such as monitoring and inspection, reconnaissance, surveillance, mapping, and networking. This article deals with the unmanned surveillance problem, which is a problem of the path planning for a fleet of unmanned aerial vehicles performing persistent surveillance of a ground area of interest. The surveillance is performed via sensor systems of individual drones from a set of waypoints deployed in the area of operations. The objective of the problem is to plan a route (that is, the order in which the waypoints are visited) of every vehicle in the fleet to ensure the best observation of the area of interest. This article presents a new mathematical formulation of the problem. The novelty in this formulation consists of a new perspective on the objective function, which is based on an integral of time function to minimize time between observations of portions of the area conducted from waypoints. For the solution, three deterministic approaches are proposed. To evaluate the results, a set of benchmark instances for the problem is defined. The solution algorithms are analyzed and evaluated by experiments conducted on the benchmark instances. The best approach is shown to be the algorithm that uses a multidepot vehicle routing problem solution as a template to generate a solution for the unmanned surveillance problem.