Задача максимізації зваженої кількості об’єктів, обстежених дроном

In the context of rapid advancements in unmanned technologies, the task of efficient drone trajectory planning is gaining particular relevance. This includes, in particular, optimization of a drone's flight path to maximize coverage of target objects. The research is relevant to both civil and military applications of unmanned aerial vehicles (UAVs), including territory monitoring, search and rescue operations, and patrolling. The problem under consideration consists in maximizing the weighted number of objects that a drone can survey while moving along a straight-line trajectory. Given the discrete distribution of target objects and continuous nature of the parameter space for straight lines, it becomes necessary to apply discretization to use methods of discrete optimization. The aim of this paper is to develop and compare combinatorial methods for constructing a line that maximizes the total weight of covered objects. Three approaches are analyzed: a greedy algorithm based on recursive subdivision of the area, a partial search method that evaluates sectors formed between objects, and a heuristic algorithm called “Floating Line,” which gradually rotates a line around the center of the area using a fixed angular step. The paper provides mathematical justification for the discretization of the space of lines and defines criteria for determining whether an object is covered by the trajectory. The computational complexity of the proposed algorithms is analyzed, and their effectiveness is evaluated experimentally. Experimental results show that the greedy algorithm offers high computational speed (tens or even hundreds of times faster), but with reduced accuracy. The “Floating Line” algorithm demonstrates a good balance between accuracy and computation time, whereas the partial search method ensures the highest precision and stability, though it is the most resource-intensive. Depending on the accuracy requirements and available computational resources, the user can choose the most appropriate approach. The proposed algorithms are effective tools for improving drone mission planning in practical scenarios. The problem can serve as a standalone component within more complex drone mission planning models, which additionally account for energy constraints, course corrections, zone prioritization, and the presence of obstacles. Its solution can form the basis for constructing efficient and adaptive flight paths.