ОПТИМІЗАЦІЯ ТРАЄКТОРІЇ РУХУ ДАТЧИКІВ З УРАХУВАННЯМ ВАЖЛИВОСТІ ДІЛЯНОК ТЕРИТОРІЇ МОНІТОРИНГУ ТА ЙМОВІРНОСТІ ВИЯВЛЕННЯ ОБ’ЄКТІВ

Завантажити статтю

УДК: 004.94+004.021

Петрівський Володимир Ярославович, Київський національний університет імені Тараса Шевченка, vovapetrivskyi@gmail.com

Петрівський Ярослав Борисович, Рівненський державний гуманітарний університет,  prorectorsgu@ukr.net

Шевченко Віктор Леонідович, Київський національний університет імені Тараса Шевченка,  gii2014@ukr.net

Сініцин Ігор Петрович, Інститут програмних систем Національної академії наук України, ips2014@ukr.net

DOI: http://doi.org/10.34229/2786-6505-2022-2-1

pages 6-21

У зв’язку з поширенням використання датчиків у задачах збору та обробки даних одними із ключових критеріїв є об’єм накопиченої інформації та енергоефективність. Під час моніторингу території поширений рух об’єктів дослідження, в результаті можлива зміна ймовірності їх виявлення у ділянці території. Також ділянки території можуть бути різної важливості. Врахування даних факторів суттєво збільшить кількість накопиченої інформації. Представлено метод побудови оптимальної траєкторії руху датчиків з урахуванням важливості ділянок території та ймовірності виявлення об’єктів. Метод ґрунтується на представленні розподілу ймовірності виявлення об’єктів та важливості ділянок території у вигляді шарів та їх об’єднання у шар ймовірної цінності виявлених об’єктів. Розглянуто сім класів ймовірної цінності виявлених об’єктів з відповідними числовими та графічними еквівалентами. Під оптимальною траєкторією розглядаємо траєкторію руху датчика, що забезпечує мінімальні енерговитрати. Енергоефективність досягається шляхом побудови траєкторії мінімальної довжини. Задача побудови траєкторії мінімальної довжини, що проходить всі задані точки, знаходиться як розв’язок задачі комівояжера. Набір точок, за якими будується траєкторія, формується на основі шару ймовірної цінності виявлених об’єктів після проведення процедури заміни вузлів. Для кожного класу ймовірної цінності виявлених об’єктів запропоновано окремий клас заміни вузлів або суперпозицію класів їх заміни. Описано заміну п’яти, трьох та двох вузлів. Для пошуку розв’язку представленої задачі використано генетичний алгоритм з модифікацією правил схрещування та селекції. З використанням запропонованого алгоритму побудовано сімейство траєкторій. Аналіз отриманих результатів підтвердив ефективність розробленого методу та дозволив збільшити енергоефективність при покритті конкретної території на 76 %.

  1. Chapter 5 — Technology Fundamentals. V. Tsiatsis et al. Internet of Things (Second edition). Technologies and Applications for a New Age of Intelligence. 2019. P. 67–126.
  2. Kumbhar V. Types of sensors, advantages & disadvantages of all types sensors, applications of sensors. URL: https://www.plctutorialpoint.com/2015/05/types-of-sensors-advantages.html.
  3. Petrivskyi V., Shevchenko V., Bychkov O., Pokotylo O. Models and information technologies of coverage of the territory by sensors with energy consumption optimization. In: Shkarlet S. et al. (eds). Mathematical Modeling and Simulation of Systems. MODS 2021. Lecture Notes in Networks and Systems. 2022. 344. Springer, Cham. P. 17–30. DOI: https://doi.org/10.1007/978-3-030-89902-8_2.
  4. Petrivskyi V., Shevchenko V., Yevseiev S., Milov O., Laptiev O., Bychkov O., Fedoriienko V., Tkachenko M., Kurchenko O., & Opirskyy, I. Development of a modification of the method for constructing energy-efficient sensor networks using static and dynamic sensors. Eastern-European Journal of Enterprise Technologies. 2022. 1(9(115), P. 15–23. DOI: https://doi.
    org/10.15587/1729-4061.2022.252988. 
  5. Mechali O., Xu L., Huang Ya, Shi M., Xie X. Observer-based fixed-time continuous nonsingular terminal sliding mode control of quadrotor aircraft under uncertainties and disturbances for robust trajectory tracking: Theory and experiment. Control Engineering Practice. 2021. 111. P. 104806. DOI: https://doi.org/10.1016/j.conengprac.2021.104806.
  6. Яковлев К., Макаров Д., Баскин Е. Метод автоматического планирования траектории беспилотного летательного аппарата в условиях ограничений на динамику полета. Искусственный интеллект и принятие решений. 2014. № 4. C. 3–17.
  7. Ryu H. A revisiting method using a covariance traveling salesman problem algorithm for landmark-based simultaneous localization and mapping. Sensors. 2019. 19, N 22.
  8. Isaacs J. T., Klein D. J., Hespanha J. P. Algorithms for the traveling salesman problem with neighborhoods involving a Dubins vehicle. Proceedings of the American Control Conference. 2011.
  9. Nedjat A., Vizvarib B. Robot path planning by traveling salesman problem with circle neighborhood: modeling, algorithm, and applications. DOI: https://arxiv.org/ftp/arxiv/papers/
    2003/2003.06712.pdf.
  10. Шевченко В.Л. Оптимізаційне моделювання в стратегічному плануванні. К. : ЦВСД НУОУ, 2011. 283 с.
  11. Diveev A.I., Bobr O.V. Variational genetic algorithm for NP-hard scheduling problem solution. Procedia Computer Science. 2017. 103. P. 52–58. DOI: https://doi.org/10.1016/j.procs.
    2017.01.010.
  12. The crossover operator of a genetic algorithm as applied to the task of a production planning. S.L. Podvalny et al. Procedia Computer Science. 2019. 150. P. 603–608. DOI: https://doi.org/10.1016/j.procs.2019.02.100.