Размещение дронов для оптимального покрытия барьера

Размещение дронов для оптимального покрытия барьера

Ерзин А. И., Шадрина А. В.
Дискретный анализ и исследование операций, 32, 2, 54-71 (2025)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2025.32.828

Аннотация:

На плоскости задан отрезок прямой линии (барьер), а также координаты депо, в которых нужно разместить мобильные устройства (сенсоры или дроны). Каждый дрон стартует из своего депо к некоторой точке барьера, двигается вдоль барьера и возвращается в своё депо, пройдя путь ограниченной длины. Часть барьера, вдоль которой двигался дрон, считается покрытой этим дроном. Барьер покрыт, если каждая его точка покрыта хотя бы одним дроном. Требуется разместить ограниченное число дронов в заданном множестве депо и определить траектории дронов таким образом, чтобы покрыть весь барьер и при этом число дронов было минимальным (MinNum), или общая длина путей дронов была минимальной (MinSum), или длина самого протяжённого пути среди всех дронов была минимальной (MinMax). 

Ранее авторы исследовали аналогичную задачу с неограниченным числом дронов и предложили псевдополиномиальный алгоритм для её решения, зависящий от длины барьера $L$. В этой статье рассматривается обобщённая задача, в которой число дронов ограниченно, и для построения её оптимального решения предложен алгоритм такой же трудоёмкости. Вместе с тем, в случае неограниченного числа дронов новый алгоритм имеет трудоёмкость в $L$ раз меньше трудоёмкости ранее разработанного алгоритма. 

Ил. 2, библиогр. 20.

Литература:
  1. Bhattacharya B., Burmester M., Hu Y., Kranakis E. Optimal movement of mobile sensors for barrier coverage of a planar region // Theor. Comput. Sci. 2009. V. 410, No. 52. P. 5515–5528. DOI: 10.1007/978-3-540-85097-7_ 10.
     
  2. Czyzowicz J., Kranakis E., Krizanc D. [et al.]. On minimizing the sum of sensor movements for barrier coverage of a line segment // Ad-hoc, mobile and wireless networks. Proc. 9th Int. Conf. (Edmonton, Canada, Aug. 20–22, 2010). Heidelberg: Springer, 2010. P. 29–42. (Lect. Notes Comput. Sci.; V. 6288). DOI: 10.1007/978-3-642-14785-2_3.
     
  3. Dobrev S., Durocher S., Eftekhari M. [et al.]. Complexity of barrier coverage with relocatable sensors in the plane // Theor. Comput. Sci. 2015. V. 579. P. 64–73. DOI: 10.1016/j.tcs.2015.02.006.
     
  4. Wang H., Zhang X. Minimizing the maximum moving cost of interval coverage // Algorithms and computation. Proc. 26th Int. Symp. (Nagoya, Japan, Dec. 9–11, 2015). Heidelberg: Springer, 2015. P. 188–198. (Lect. Notes Comput. Sci.; V. 9472). DOI: 10.1007/978-3-662-48971-0_17.
     
  5. Cherry A., Gudmundsson J., Mestre J. Barrier coverage with uniform radii in 2D // Algorithms for sensor systems. Rev. Sel. Pap. 13th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Vienna, Austria, Sept. 4–8, 2017). Cham: Springer, 2017. P. 57–69. (Lect. Notes Comput. Sci.; V. 10718). DOI: 10.1007/978-3-319-72751-6_5.
     
  6. Erzin A. I., Lagutkina N. A. FPTAS for barrier covering problem with equal circles in 2D // Optim. Lett. 2021. V. 15, No. 4. P. 1397–1406. DOI: 10.1007/s11590-020-01650-8.
     
  7. Erzin A. I., Lagutkina N. A., Ioramishvili N. Barrier covering in 2D using mobile sensors with circular coverage areas // Learning and intelligent optimization. Rev. Sel. Pap. 13th Int. Conf. (Chania, Greece, May 27–31, 2019). Cham: Springer, 2020. P. 342–354. (Lect. Notes Comput. Sci.; V. 11968). DOI: 10.1007/978-3-030-38629-0_28.
     
  8. Erzin A. I., Lagutkina N. A. Barrier coverage problem in 2D // Algorithms for sensor systems. Rev. Sel. Pap. 14th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Helsinki, Finland, Aug. 23–24, 2018). Cham: Springer, 2019. P. 118–130. (Lect. Notes Comput. Sci.; V. 11410). DOI: 10. 1007/978-3-030-14094-6_8.
     
  9. Erzin A. I., Shadrina A. V. Optimal placement of mobile sensors for the distance-constrained line routing problem // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 23th Int. Conf. (Omsk, Russia, June 30 – July 6, 2024). Cham: Springer, 2024. P. 172–184. (Commun. Comput. Inf. Sci.; V. 2239). DOI: 10.1007/978-3-031-73365-9_12.
     
  10. Bar-Noy A., Rawitz D., Terlecky P. «Green» barrier coverage with mobile sensors // Algorithms and complexity. Proc. 9th Int. Conf. (Paris, France, May 20–22, 2015). Cham: Springer, 2015. P. 33–46. (Lect. Notes Comput. Sci.; V. 9079). DOI: 10.1007/978-3-319-18173-8_2.
     
  11. Benkoczi R., Friggstad Z., Gaur D., Thom M. Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line // Algorithms for sensor systems. Rev. Sel. Pap. 11th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Patras, Greece, Sept. 17–18, 2015). Cham: Springer, 2015. P. 98–111. (Lect. Notes Comput. Sci.; V. 9536). DOI: 10.1007/978-3-319-28472-9_8.
     
  12. Andrews A. M., Wang H. Minimizing the aggregate movements for interval coverage // Algorithmica. 2017. V. 78, No. 1. P. 47–85. DOI: 10.1007/ s00453-016-0153-8.
     
  13. Coutinho W. P., Battarra M., Fliege J. The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review // Comput. Ind. Eng. 2018. V. 120. P. 116–128. DOI: 10.1016/j.cie.2018.04.037.
     
  14. Campbell J. F., Corberan A., Plana I., Sanchis J. M. Drone arc routing problems // Networks. 2018. V. 72, No. 4. P. 543–559. DOI: 10.1002/net. 21858.
     
  15. Kek A. G. H., Cheu R. L., Meng Q. Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots // Math. Comput. Model. 2008. V. 47. P. 140–152. DOI: 10.1016/j.mcm.2007.02.007.
     
  16. Erzin A. I., Plotnikov R. V. Distance-constrained line routing problem // Optimization and applications. Rev. Sel. Pap. 10th Int. Conf. (Petrovac, Montenegro, Sep. 30 – Oct. 4, 2019). Cham: Springer, 2020. P. 43–55. (Commun. Comput. Inf. Sci.; V. 1145). DOI: 10.1007/978-3-030-38603-0_4.
     
  17. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 334 с.
     
  18. Vidal R. V. V. Optimal partition of an interval— The discrete version // Applied simulated annealing. Heidelberg: Springer, 1993. P. 291–312. (Lect. Notes Econ. Math. Syst.; V. 396). DOI: 10.1007/978-3-642-46787-5_15.
     
  19. Jackson B., Scargle J. D., Barnes D. [et al.]. An algorithm for optimal partitioning of data on an interval // IEEE Signal Proces. Lett. 2005. V. 12, No. 2. P. 105–108. DOI: 10.1109/LSP.2001.838216.
     
  20. Tilli P., Zucco D. Optimal partitioning of an interval and applications to Sturm–Liouville eigenvalues // J. Differ. Equ. 2019. V. 268, No. 8. P. 4900–4919. DOI: 10.1016/j.jde.2019.12.026.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Ерзин Адиль Ильясович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: adilerzin@math.nsc.ru

Шадрина Анжела Викторовна
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: shadrinanzhela@gmail.com

Статья поступила 10 февраля 2025 г.
После доработки — 11 марта 2025 г.
Принята к публикации 22 апреля 2025 г.

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 pseudopolynomial 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.

References:
  1. B. Bhattacharya, M. Burmester, Y. Hu, and E. Kranakis, Optimal movement of mobile sensors for barrier coverage of a planar region, Theor. Comput. Sci. 410 (52), 5515–5528 (2009), DOI: 10.1007/978-3-540-85097-7_10.
     
  2. J. Czyzowicz, E. Kranakis, D. Krizanc, [et al.], On minimizing the sum of sensor movements for barrier coverage of a line segment, in Ad-Hoc, Mobile and Wireless Networks (Proc. 9th Int. Conf., Edmonton, Canada, Aug. 20–22, 2010) (Springer, Heidelberg, 2010), pp. 29–42 (Lect. Notes Comput. Sci., Vol. 6288), DOI: 10.1007/978-3-642-14785-2_3.
     
  3. S. Dobrev, S. Durocher, M. Eftekhari, [et al.], Complexity of barrier coverage with relocatable sensors in the plane, Theor. Comput. Sci. 579, 64–73 (2015), DOI: 10.1016/j.tcs.2015.02.006.
     
  4. H. Wang and X. Zhang, Minimizing the maximum moving cost of interval coverage, in Algorithms and Computation (Proc. 26th Int. Symp., Nagoya, Japan, Dec. 9–11, 2015) (Springer, Heidelberg, 2015), pp. 188–198 (Lect. Notes Comput. Sci., Vol. 9472), DOI: 10.1007/978-3-662-48971-0_17.
     
  5. A. Cherry, J. Gudmundsson, and J. Mestre, Barrier coverage with uniform radii in 2D, in Algorithms for Sensor Systems (Rev. Sel. Pap. 13th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Vienna, Austria, Sept. 4–8, 2017) (Springer, Cham, 2017), pp. 57–69 (Lect. Notes Comput. Sci., Vol. 10718), DOI: 10.1007/978-3-319-72751-6_5.
     
  6. A. I. Erzin and N. A. Lagutkina, FPTAS for barrier covering problem with equal circles in 2D, Optim. Lett. 15 (4), 1397–1406 (2021), DOI: 10.1007/ s11590-020-01650-8.
     
  7. A. I. Erzin, N. A. Lagutkina, and N. Ioramishvili, Barrier covering in 2D using mobile sensors with circular coverage areas, in Learning and Intelligent Optimization (Rev. Sel. Pap. 13th Int. Conf., Chania, Greece, May 27–31, 2019) (Springer, Cham, 2020), pp. 342–354 (Lect. Notes Comput. Sci., Vol. 11968), DOI: 10.1007/978-3-030-38629-0_28.
     
  8. A. I. Erzin and N. A. Lagutkina, Barrier coverage problem in 2D, in Algorithms for Sensor Systems (Rev. Sel. Pap. 14th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Helsinki, Finland, Aug. 23–24, 2018) (Springer, Cham, 2019), pp. 118–130 (Lect. Notes Comput. Sci., Vol. 11410), DOI: 10.1007/978-3-030-14094-6_8.
     
  9. A. I. Erzin and A. V. Shadrina, Optimal placement of mobile sensors for the distance-constrained line routing problem, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 23th Int. Conf., Omsk, Russia, June 30 – July 6, 2024) (Springer, Cham, 2024), pp. 172–184 (Commun. Comput. Inf. Sci., Vol. 2239), DOI: 10.1007/978-3-031-73365-9.
     
  10. A. Bar-Noy, D. Rawitz, and P. Terlecky, “Green” barrier coverage with mobile sensors, in Algorithms and Complexity (Proc. 9th Int. Conf., Paris, France, May 20–22, 2015) (Springer, Cham, 2015), pp. 33–46 (Lect. Notes Comput. Sci., Vol. 9079), DOI: 10.1007/978-3-319-18173-8_2.
     
  11. R. Benkoczi, Z. Friggstad, D. Gaur, and M. Thom, Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line, in Algorithms for Sensor Systems (Rev. Sel. Pap. 11th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Patras, Greece, Sept. 17–18, 2015) (Springer, Cham, 2015), pp. 98–111 (Lect. Notes Comput. Sci., Vol. 9536), DOI: 10.1007/978-3-319-28472-9_8.
     
  12. A. M. Andrews and H. Wang, Minimizing the aggregate movements for interval coverage, Algorithmica 78 (1), 47–85 (2017), DOI: 10.1007/ s00453-016-0153-8.
     
  13. W. P. Coutinho, M. Battarra, and J. Fliege, The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review, Comput. Ind. Eng. 120, 116–128 (2018), DOI: 10.1016/j.cie.2018.04.037.
     
  14. J. F. Campbell, A. Corberan, I. Plana, and J. M. Sanchis, Drone arc routing problems, Networks 72 (4), 543–559 (2018), DOI: 10.1002/net.21858.
     
  15. A. G. H. Kek, R. L. Cheu, and Q. Meng, Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots, Math. Comput. Model. 47, 140–152 (2008), DOI: 10.1016/j.mcm.2007. 02.007.
     
  16. A. I. Erzin and R. V. Plotnikov, Distance-constrained line routing problem, in Optimization and Applications (Rev. Sel. Pap. 10th Int. Conf., Petrovac, Montenegro, Sep. 30 – Oct. 4, 2019) (Springer, Cham, 2020), pp. 43–55 (Commun. Comput. Inf. Sci., Vol. 1145), DOI: 10.1007/978-3-030-38603-0_4.
     
  17. V. L. Beresnev, Eh. Kh. Gimadi, and V. T. Dementyev, Extremal Problems of Standardization (Nauka, Novosibirsk, 1978) [Russian].
     
  18. R. V. V. Vidal, Optimal partition of an interval — The discrete version, in Applied Simulated Annealing, (Springer, Heidelberg, 1993), pp. 291–312 (Lect. Notes Econ. Math. Syst., Vol. 396), DOI: 10.1007/ 978-3-642-46787-5_15.
     
  19. B. Jackson, J. D. Scargle, D. Barnes, [et al.], An algorithm for optimal partitioning of data on an interval, IEEE Signal Proces. Lett. 12 (2), 105–108 (2005), DOI: 10.1109/LSP.2001.838216.
     
  20. P. Tilli and D. Zucco, Optimal partitioning of an interval and applications to Sturm–Liouville eigenvalues, J. Differ. Equ. 268 (8), 4900–4919 (2019), DOI: 10.1016/j.jde.2019.12.026.