Drone placement for optimal barrier coverage

A. I. Erzin^a, A. V. Shadrina<sup>b

a</sup> Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, 630090 Novosibirsk, Russia
^b Novosibirsk State University, 2 Pirogov Street, 630090 Novosibirsk, Russia

Abstract: On the plane, a straight line segment (barrier) is specified, as well as the location of depots in which mobile devices (sensors or drones) are to be placed. Each drone starts from and returns to its depot and is able to travel along the barrier passing through a limited-length path. The part of the barrier along which a drone moved is covered by this drone. The barrier is covered if each point of it is covered by at least one drone. It is necessary to place some number of drones in each depot in order to cover the entire barrier and minimize the number of drones used (MinNum), or to minimize the total length of paths travelled by drones (MinSum), or to minimize the maximum distance traveled by a drone (MinMax).
Previously, the authors investigated a similar problem with an unlimited number of drones and, for its solution, proposed a pseudo-polynomial algorithm depending on the length of the barrier $L.$ In this paper, a generalized problem with a limited number of drones is considered and, to construct an optimal solution, we propose an algorithm with the same complexity. However, in the case of an unlimited number of drones, the new algorithm has complexity $L$ times less than the previous one. Illustr. 2, bibliogr. 20.

Keywords: barrier covering, linear routing, mobile device (drone), limited energy, optimization.

UDC: 519.8+518.25

Received: 10.02.2025
Revised: 11.03.2025
Accepted: 22.04.2025

DOI: 10.33048/daio.2025.32.828