Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу

Розглянуто проблему пошуку рухомих об’єктів та моніторингу території групою безпілотних літальних апаратів (БПЛА). Показано, що модель руху транспортних засобів з декількома депо можна застосувати для планування польоту груп БПЛА. Запропонована постановка задачі дозволяє прискорити пошук об’єктів та...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2018
Hauptverfasser:	Гуляницький, Л.Ф., Корольов, В.Ю., Огурцов, М.І., Ходзінський, О.М.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Schriftenreihe:	Компьютерная математика
Schlagworte:	Информационные технологии в экологии
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/161884
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу / Л.Ф. Гуляницький, В.Ю. Корольов, М.І. Огурцов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 2. — С. 38-47. — Бібліогр.: 19 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-161884
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1618842025-02-23T19:18:47Z Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу Проблемы маршрутизации БПЛА в задачах поиска и мониторинга Problems of UAV routing in search and monitoring Гуляницький, Л.Ф. Корольов, В.Ю. Огурцов, М.І. Ходзінський, О.М. Информационные технологии в экологии Розглянуто проблему пошуку рухомих об’єктів та моніторингу території групою безпілотних літальних апаратів (БПЛА). Показано, що модель руху транспортних засобів з декількома депо можна застосувати для планування польоту груп БПЛА. Запропонована постановка задачі дозволяє прискорити пошук об’єктів та мінімізувати необхідну кількість БПЛА. Рассмотрены проблемы поиска подвижных объектов и мониторинга территории группой беспилотных летательных аппаратов (БПЛА). Показано, что модель движения транспортных средств с несколькими депо можно применить для планирования полета групп БПЛА. Предложенная постановка задачи позволяет ускорить поиск объектов и минимизировать необходимое количество БПЛА. The problems of search for mobile objects and territory monitoring with a group of unmanned aerial vehicles (UAVs) are considered. We show that a model of vehicles traffic with several depots can be applied to planning UAV group flight. The proposed problem statement allows us to accelerate the search of objects and minimize the required number of UAVs. 2018 Article Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу / Л.Ф. Гуляницький, В.Ю. Корольов, М.І. Огурцов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 2. — С. 38-47. — Бібліогр.: 19 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161884 004.942 uk Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Информационные технологии в экологии Информационные технологии в экологии
spellingShingle	Информационные технологии в экологии Информационные технологии в экологии Гуляницький, Л.Ф. Корольов, В.Ю. Огурцов, М.І. Ходзінський, О.М. Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу Компьютерная математика
description	Розглянуто проблему пошуку рухомих об’єктів та моніторингу території групою безпілотних літальних апаратів (БПЛА). Показано, що модель руху транспортних засобів з декількома депо можна застосувати для планування польоту груп БПЛА. Запропонована постановка задачі дозволяє прискорити пошук об’єктів та мінімізувати необхідну кількість БПЛА.
format	Article
author	Гуляницький, Л.Ф. Корольов, В.Ю. Огурцов, М.І. Ходзінський, О.М.
author_facet	Гуляницький, Л.Ф. Корольов, В.Ю. Огурцов, М.І. Ходзінський, О.М.
author_sort	Гуляницький, Л.Ф.
title	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу
title_short	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу
title_full	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу
title_fullStr	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу
title_full_unstemmed	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу
title_sort	проблема маршрутизації груп бпла в задачах пошуку і моніторингу
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2018
topic_facet	Информационные технологии в экологии
url	https://nasplib.isofts.kiev.ua/handle/123456789/161884
citation_txt	Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу / Л.Ф. Гуляницький, В.Ю. Корольов, М.І. Огурцов, О.М. Ходзінський // Компьютерная математика. — 2018. — № 2. — С. 38-47. — Бібліогр.: 19 назв. — укр.
series	Компьютерная математика
work_keys_str_mv	AT gulânicʹkijlf problemamaršrutizacíígrupbplavzadačahpošukuímonítoringu AT korolʹovvû problemamaršrutizacíígrupbplavzadačahpošukuímonítoringu AT ogurcovmí problemamaršrutizacíígrupbplavzadačahpošukuímonítoringu AT hodzínsʹkijom problemamaršrutizacíígrupbplavzadačahpošukuímonítoringu AT gulânicʹkijlf problemymaršrutizaciibplavzadačahpoiskaimonitoringa AT korolʹovvû problemymaršrutizaciibplavzadačahpoiskaimonitoringa AT ogurcovmí problemymaršrutizaciibplavzadačahpoiskaimonitoringa AT hodzínsʹkijom problemymaršrutizaciibplavzadačahpoiskaimonitoringa AT gulânicʹkijlf problemsofuavroutinginsearchandmonitoring AT korolʹovvû problemsofuavroutinginsearchandmonitoring AT ogurcovmí problemsofuavroutinginsearchandmonitoring AT hodzínsʹkijom problemsofuavroutinginsearchandmonitoring
first_indexed	2025-11-24T15:51:01Z
last_indexed	2025-11-24T15:51:01Z
_version_	1849687499672125440
fulltext	38 ISSN 2616-938Х. Компьютерная математика. 2018, № 2 Информационные технологии в экологии Розглянуто проблему пошуку ру- хомих об’єктів та моніторингу території групою безпілотних літальних апаратів (БПЛА). По- казано, що модель руху тран- спортних засобів з декількома депо можна застосувати для планування польоту груп БПЛА. Запропонована постановка задачі дозволяє прискорити пошук об’єк- тів та мінімізувати необхідну кількість БПЛА. © Л.Ф. Гуляницький, В.Ю. Корольов, М.І. Огурцов, О.М. Ходзінський, 2018 УДК 004.942 Л.Ф. ГУЛЯНИЦЬКИЙ, В.Ю. КОРОЛЬОВ, М.І. ОГУРЦОВ, О.М. ХОДЗІНСЬКИЙ ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ Вступ. Масове виробництво БПЛА призвело до їх суттєвого здешевлення та зробило еко- номічно прийнятним використання їх груп [1 – 10]. Наразі для визначення розташування позицій супротивника активно використову- ються одиночні БПЛА з відеокамерою або тепловізором, що дистанційно керуються з захищеної позиції. Застосування об’єднаних у мережі груп БПЛА [3 – 8] з комбінованим навантаженням дозволяє прискорити вияв- лення і стеження за малими групами супро- тивника, які мають високу динаміку перемі- щень, діють під прикриттям засобів радіо- електронної боротьби (РЕБ) і радіоелектрон- ної розвідки (РЕР) та мають маскування від тепловізорів [11 – 16]. 1. Постановка задачі пошуку об’єкта. Висока динаміка подій у сучасних гібридних війнах та використання автономних груп за- собів технічної розвідки з штучним інтелек- том, що з’являться у найближчий час, вима- гають перегляду постановок задач оптиміза- ції військових операцій та методів їх роз- в’язання. Перш ніж атакувати групу супро- тивника, необхідно за короткий інтервал часу визначити його координати, тип озброєння, чисельність, параметри руху, можливі контр- заходи та інше для вибору раціональних засобів його знищення. Тому прискорення процесів розвідки і побудови шляхів патру- лювання, котрі є простими і багатократно повторюваними діями при подібних почат- кових умовах, є актуальною проблемою для оптимізації виконання операцій пошуку ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ ISSN 2616-938Х. Компьютерная математика. 2018, № 2 39 та управління. Розрахунок величин, що характеризують ефективність операції, дозволяє, окрім оцінки раціональності використання застосованих груп БПЛА, також виявити зміну тактики супротивника та ініціювати контрзаходи [14]. Загальне формулювання задачі пошуку цілі в області. Задачею пошуку є огляд певної області або об’єму оптимальним чином для виявлення цілей [15, 16]. Припустимо, що область розділена на райони або клітини (не обов'яз- ково ідентичні), а рі – ймовірність того, що ціль знаходиться в i-му районі, де (і = 1,…, n). Розглянемо постановку задачі, у якій потрібно знайти такий поділ загальної кількості часу t на часові інтервали it для кожного району таким чином, щоб максимізувати ймовірність виявлення цілі. Задача має аналітичне розв’язання за умови, що у кожному регіоні ймовірність виявлення цілі має рів- номірний розподіл [16]. Це базується на припущенні, що розмір району є вели- ким порівняно з площею, що зчитується датчиком у цій області. Імовірність виявлення цілі, з огляду на те, що вона знаходиться в районі i, становить: 1 exp ,i i i t p T           де Ti – середній час для виявлення в області i . Тоді задача дискретної оптимізації для пошуку цілі в області формулюється наступним чином [16]: 1 1 max 1 exp . , 0. n i i i i n i i i tP p T t t t                     Подібні постановки не враховують можливість використання групи літаль- них засобів, що одночасно шукатимуть об’єкт. Також інколи розглядають пошук, як вже оптимальний, і шукають параметри просторового розподілу в групі [15]. Аналіз способів оцінки якості пошуку та критеріїв його ефективності. Проблеми пошуку бойових одиниць супротивника почали вирішуватись ще під час Другої світової війни на базі підходів визначення продуктивності діяльності бізнесу у США, які пізніше увійшли у теорію дослідження операцій [12 – 16]. Накопичені дані про бойові дії дозволили виділити критичні параметри для оцінки результату операції, сформулювати критерії ефективності і виконати змі- стовну постановку задач оптимізації. Розв’язання задачі дозволило в рази під- вищити результативність власних дозорних засобів, зменшити їх кількість, ви- явити проблеми в їх розподілі по зонах відповідальності та ін. Критерії ефективності розвідки або пошуку можуть бути використані для розрахунку вхідних даних задачі маршрутизації для групи БПЛА. Л.Ф. ГУЛЯНИЦЬКИЙ, В.Ю. КОРОЛЬОВ, М.І. ОГУРЦОВ, О.М. ХОДЗІНСЬКИЙ ISSN 2616-938Х. Компьютерная математика. 2018, № 240 Відносна швидкість пошуку. Розглянемо оцінки ефективності пошуку, що використовуються в теорії дослідження операцій у військовій справі для побу- дови критеріїв оптимізації операцій розвідки і патрулювання [14, 15]. Міра ефективності EZ вводиться як відношення реальної p до теоретично досяжної m швидкостей пошуку: p E m v Z v  , що є, по суті, відношенням середньої щільно- сті бойових одиниць супротивника у зоні пошуку до кількості їх виявлення за- собами розвідки за одиницю часу. Реальна швидкість пошуку у зоні: р K Ov T S             , де К – кількість виявле- них бойових одиниць, Т – проміжок часу за який виявлено ці бойові одиниці, О – потенційно можлива кількість бойових одиниць у зоні, S – площа зони пошуку. Теоретична швидкість пошуку рухомим технічним засобом розвідки: ,тv L v  де L – ефективна дальність виявлення бойової одиниці супротивни- ка засобом розвідки, v – швидкість переміщення технічного засобу розвідки. Відношення EZ визначає продуктивність застосування власних розвіду- вальних засобів і дієвість методів та засобів супротивника, що дозволяють йому уникати виявлення. Порівняння реальної і теоретичної ефективності пошуку є способом відслідковування продуктивності розвідувальних операцій у процесі розвитку збройного конфлікту. Ця міра ефективності не призначена для безпо- середнього застосування під час розвідки району групою БПЛА, оскільки вико- ристовує багато апостеріорної інформації; у прикладах її застосування показник заміряється впродовж місяця [14, 15]. Відносна площа обстеженої території. Як критерій ефективності розвідки за виявленням супротивника у заданому районі може використовуватись також середнє значення розвіданої площі S із заданою достовірністю до означеного моменту часу [12, 13]. Якщо по місцям зосередження супротивника планується вогневе ураження, то територія розділяється на квадрати, площа яких має відпо- відати можливостям ураження зброї з метою прискорення розрахунку кількості пострілів. Ефективність повітряної розвідки визначається так: ,ПР SZ p S   де S – площа, розвідана одним БПЛА, S – як і раніше, загальна площа району розвідки, р – ймовірність виконання завдання. Виконання завдання пошуку цілі БПЛА ґрунтується на аналізі незалежних подій: правильному розпізнаванню цілі й уникненню впливу засобів РЕБ, тому ймовірність виконання завдання буде їх добутком: ймовірності правильного розпізнавання цілі ВЦp та ймовірності уни- кнення впливу засобів РЕБ, тобто стійкості керування СКp : .ВЦ СКp p p  ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ ISSN 2616-938Х. Компьютерная математика. 2018, № 2 41 Для групи з N БПЛА, проти якої здійснюється M спроб заглушення каналу керування засобами РЕБ, справедлива теорема повторення дослідів Бернуллі для визначення ймовірності успіху дій супротивника [13]: (1 ) ,M M N M РЕБ М NP C W W   де W – ймовірність заглушення каналу керування од- ного БПЛА. Оскільки група тактичних БПЛА має малий радіус дії, то вони по- падуть у зону дії однієї станції РЕБ, відповідно ймовірність заглушення керу- вання буде однаковою. Оскільки такі події, як стійкість керування БПЛА і заглушення каналу керу- вання станцією РЕБ є взаємно виключними, то: .1СК РЕБр р  . Якщо у районі задіяно N БПЛА, тоді за умови, що БПЛА виявляють об’єкти незалежно один від одного, траєкторії обстеження перетинаються, дуплікація даних не усувається, ефективність повітряної розвідки дорівнює:   1 1 1 1 , N k ПР N k k Z S p S        де kS – площа, обстежена одним БПЛА. Ця формула може використовуватись для планування пошуку і повітряної розвідки. У монографії [15] показано, що при пошуку об’єкта за оптимальним планом відстань між технічними засобами розвідки повинна бути не менше половини дальності виявлення цілі: 1 2 , r i i B d L    де В – ширина району спостереження, id – відстань між технічними засобами розвідки, L – максимальна дальність виявлення цілі, r – кількість рухомих технічних засобів розвідки. Дотримання значення відстані між БПЛА групи за формулою дозволяє запобігти пропуску об’єкта без повторної реєстрації фотозображень поверхні. Наведені залежності дозволяють отримати початкові умови і параметри для змістовної постановки задачі комбінаторної оптимізації. Перелічені підходи до організації пошуку не передбачали використання групи БПЛА, об’єднаних у мережу, для виконання операцій пошуку [3 – 8]. 2. Змістовна постановка задач комбінаторної оптимізації Задача 1. Загальна розвідка території. Є певна територія, на якій слід вико- нати заходи за визначенням поточної ситуації. Вона може містити місця особли- вого інтересу, що потребують першочергової уваги і обов’язково мають бути відвідані. Задачею є виконати розвідку наявними БПЛА якомога більшого від- сотку заданої території за вказаний час із зазначеними витратами пального. Цю задачу можна було б розглядати як задачу маршрутизації транспорту з випадковими даними (Stochastic VRP, SVRP). Але на даний час при виконанні реальних розвідувальних завдань є достатньо початкових даних, щоб не викори- стовувати такий підхід. Л.Ф. ГУЛЯНИЦЬКИЙ, В.Ю. КОРОЛЬОВ, М.І. ОГУРЦОВ, О.М. ХОДЗІНСЬКИЙ ISSN 2616-938Х. Компьютерная математика. 2018, № 242 Перелік точок, які потрібно відвідати, визначається на основі поведінки об’єкта, який потрібно знайти, наприклад, тактикою його застосування супро- тивником [10]. Змістовна постановка задачі маршрутизації груп БПЛА для пошуку об’єктів може бути подана так. Вхідні дані: кількість БПЛА у групі; дальність польоту кожного БПЛА; координати границь зон, безпечних для польоту БПЛА. Параметри: максимальна дальність передачі сигналу зв’язку між БПЛА групи та наземним пунктом керування; дальність польоту при заданій кількості пального і вазі корисного навантаження; відстань між БПЛА у групі при вико- нанні пошуку. Вихідні дані: таблиця маршрутів БПЛА. Критерії: мінімум часу виконання завдання; мінімум БПЛА. 3. Математична модель. Ця проблема маршрутизації відноситься до задач оптимізації комбінаторно- го типу, які можна подати за допомогою спеціального графа [1 – 9, 17]. Є задана множина точок ,eV які треба відвідати, щоб уникнути протидії засобів ППО і РЕБ та дістатись зони наведення на ціль, є множина aV (депо) точок, з яких можуть запускатись БПЛА, а також bV – множина точок, куди вони можуть повертатись. Таким чином, на основі цих множин будується планарний граф, накладений на карту. Введемо такі позначення.  ,G V E – граф задачі, де a b eV V V V   , а Е – множина ребер; С – матриця невід’ємних відстаней (вартостей шляху) ijc між точками , ;i jv v V m  кількість БПЛА; iR – маршрут і-го БПЛА  1, ,i m  ; R – сукупність мар- шрутів    1,..., ; iiR i m С R – вартість маршруту  1, ,iR i m  ;  K v – вага кожної вершини ,ev V що визначає важливість її відвідування; iq – ресурс руху i -го БПЛА  1, ,i m  . Кожна точка (вершина графа задачі G ) vi задається координатами  , .i ix y Задача маршрутизації полягає у визначенні такої множини m маршрутів з міні- мальною загальною вартістю, щоб кожна вершина підмножини Ve була відвіда- на тільки одним БПЛА мінімум разів. Крім того, маршрути мають починатися у вершинах підмножини Va і закінчуватися в будь-якій точці з підмножини Vb. Визначення відстані між точками для доставки відбувається за стандартною формулою для прямокутної системи координат:    2 2 2 1 2 1d x x y y    . (1) ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ ISSN 2616-938Х. Компьютерная математика. 2018, № 2 43 Розв’язок задачі – розбиття множини eV на підмножини з приписуванням їм конкретного наявного БПЛА та визначення порядку обходу вершин у кожній такій підмножині (перестановка вершин маршруту). Розв'язки задачі, при яких не всі точки з множини eV відвідуються, є недопустимими. Цільова функція в загальному випадку – вартість розв'язку задачі:     1 1 m i i VRP m i i K V F C R      , (2) де K(vi) – вага вершин vi, що входять до маршруту Ri, i = 1,…, m; C(Ri) – сума довжин ребер маршруту Ri, i = 1,…, m. Також введено такі обмежуючі умови задачі: кожна вершина множини Ve обов’язково має бути відвідана; довжина кожного маршруту Ri не повинна пере- вищувати заданої максимальної дальності польоту БПЛА qi; вартості ребер графа, тобто шляхів між точками відповідно до формули (1) можуть моди- фікуватись додатковими обмеженнями – погодними умовами, загрозами тощо [18 – 19]. Задача 1. Потрібно знайти допустимий розв'язок з максимальним значенням цільової функції (2) з урахуванням зазначених обмежень. Таким чином, ця задача подібна до задачі Multiple Depot VRP, MDVRP (або задачі маршрутизації транспортних засобів із декількома депо) за наявності до- даткових обмежень [1, 2]. Аналогічним чином можуть бути формалізовані й за- дачі, які будуть розглянуті далі. Задача є динамічною – в будь-який момент часу умови можуть змінитись. В цьому випадку слід виконати перебудову маршрутів на основі змінених умов та з урахуванням частини маршруту БПЛА, що вже подолана. Задача 2. Розвідка заданих точок. В цьому випадку не потрібно обстежувати певну територію. Необхідно лише відвідати ряд заданих точок з метою виконан- ня наявних завдань. До таких завдань можуть відноситись перевірка блокпостів супротивника та інших об’єктів ворожої інфраструктури, перехресть доріг, місць потенційних засідок, контроль можливих шляхів підступу до своїх пози- цій, цілевказання тощо. Подібні обмеження враховуються шляхом введення штрафних значень, які додаються до наявної ваги ребер графа задачі. Єдиною відмінністю у порівнянні із задачею 1 є те, що БПЛА мають потра- пити в усі точки із наявних. Тобто усі точки підмножини Ve обов’язково мають бути відвідані. Таким чином, задача 2 – окремий випадок задачі 1, що не має особливостей при розв’язуванні та не потребує розробки окремого математично- го апарата. Задача 3. Спостереження. В цьому випадку треба спостерігати за певною ділянкою місцевості за регулярним принципом з метою виявлення будь-яких змін. Ця задача відноситься до задач маршрутизації транспорту з періодичною мар- шрутизацією (Periodic VRP, PVRP). Математично не відрізняється від задачі 1. Може містити або не містити місця особливої цікавості для спостереження. Л.Ф. ГУЛЯНИЦЬКИЙ, В.Ю. КОРОЛЬОВ, М.І. ОГУРЦОВ, О.М. ХОДЗІНСЬКИЙ ISSN 2616-938Х. Компьютерная математика. 2018, № 244 Принципово розв’язується тим же способом, що і задача 1. Є лише одна відмінність: оскільки патрулювання виконується багаторазово, то у випадку, якщо оптимальний розв’язок для першого вильоту не охопив усі точки з множи- ни V, даний маршрут зберігається. Для другого вильоту в рамках тієї ж задачі усі точки з множини Ve, не охоплені попереднім вильотом, отримують вищу вагу Ki у розв’язку (вищу ніж у звичайних точок, але нижчу ніж у точок особливої ціка- вості). Таким чином, при повторному виконанні завдання патрулювання буду- ється інший маршрут (що забезпечує ефективний захист для запобігання запам’ятовування маршруту патрулювання супротивником з метою уникнення потрапляння в зони обстеження). Задача 4. Патрулювання. Ця задача – окремий випадок задачі спостережен- ня. Відмінність те, що спостерігається не просто зона відповідальності, а певні відомі маршрути патрулювання або периметри позицій. Розв’язується задача тим же шляхом, що і задача 3. Але у більшості випадків БПЛА за один раз змо- же відвідати усі задані точки, що складатимуть маршрут патрулювання або пе- риметр позиції, тому збереження його маршруту та побудова нового не будуть потрібні. Крім того, оскільки час патрулювання звичайно чітко визначений, ця задача є задачею маршрутизації транспорту з часовими обмеженнями або «часо- вими вікнами» (VRP with Time Windows, VRPTW). Задача 5. Задача доставки. Є ряд об’єктів, які слід відвідати та доставити їм певний вантаж. У військових застосуваннях це може бути ракета чи керована бомба. Можливо також доставлення інших вантажів та навіть поранених війсь- ковослужбовців. Усі об’єкти мають обов’язково бути відвідані. Після завершен- ня виконання завдання БПЛА має повернутись до одного з місць приземлення. Таким чином, вхідні дані: 1) координати об’єктів, куди має виконуватись доставка; 2) вантажі, що мають бути доставлені до кожного з об’єктів; 3) коор- динати депо (точки, з яких можуть запускатись БПЛА); 4) координати місця посадки БПЛА – найчастіше не співпадають з місцем запуску з питань безпеки пунктів керування та обслуговуючого персоналу; 5) кількість БПЛА, що можуть бути застосовані для розв’язання даної задачі. Загальна кількість працездатних БПЛА, що може бути запущена у повітря або кількість пілотів-операторів, які одночасно можуть керувати БПЛА. Вихідні дані: Побудований маршрут кожного БПЛА, поданий у вигляді послідовності точок для відвідування. Має починатись у підмножині вершин aV та закінчуватись у bV , тобто місця старту і посадки обов’язково розділяють. Критерій: загальна довжина маршрутів усіх БПЛА. Обмеження: 1) вантажі мають бути доставлені в усі задані точки; 2) загальна вантажопідйомність БПЛА. Для окремих випадків – кількість ракет або керова- них бомб, що може нести БПЛА, додаткового обладнання для повітряної розвід- ки; 3) максимально допустима дальність польоту БПЛА. Максимальна допусти- ма дальність польоту з ретрансляцією команд керування і без, зони ретрансляції ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ ISSN 2616-938Х. Компьютерная математика. 2018, № 2 45 радіосигналу; 4) максимальна швидкість БПЛА; 5) середня швидкість БПЛА; 6) додаткові умови та обмеження (координати зон з погодними умовами, що ускладнюють виконання завдання, зон потенційної небезпеки через засоби протиповітряної оборони тощо). Задача маршрутизації полягає у визначенні такої множини маршрутів m з мінімальною загальною вартістю, щоб кожна вершина множини Ve була відві- дана тільки одним БПЛА і тільки один раз. При цьому вантажопідйомність кож- ного БПЛА не повинна бути перевищена. Крім того, всі маршрути мають почи- натись у підмножині вершин aV , та закінчуватись у .bV Розв’язком задачі є розбиття множини V на підмножини, кожна з яких обов’язково містить одну вершину із aV , та визначення порядку обходу на кож- ній підмножині (перестановка вершин маршруту). Розв’язки задачі, при яких не всі точки з множини Ve відвідуються або вантажопідйомність хоча б одного ТЗ перевищена, є недопустимими. Цільова функція в загальному випадку – це оцінка вартості розв’язку задачі згідно значення функції:   1 m VRP i i F C R   , (3) де C(Ri) – сума довжин ребер маршруту Ri, i = 1,..., m. Потрібно знайти допустимий розв’язок з мінімальною вартістю за форму- лою (3). При цьому вартості шляхів між точками можуть модифікуватись додат- ковими обмеженнями – погодними умовами, загрозами тощо. Висновки. Вперше запропоновано змістовну постановку задачі маршру- тизації для виконання пошуку об’єктів групою БПЛА, як задачі комбінаторної оптимізації. Показано, що математична модель руху групи БПЛА, яка шукає об’єкти, може бути зведена до моделі маршрутизації транспортних засобів із декількома депо. Запропоновано розраховувати значення вхідних даних для розв’язування задачі комбінаторної оптимізації за допомогою критеріїв ефективності операцій пошуку. Подані змістовні постановки і математичні моделі задач маршрутизації дозволяють скоротити кількість БПЛА, що використовуються у групі для виконання поставлених задач та прискорити виконання таких завдань, як пошук об’єкта, розвідка місцевості та доставка вантажів, у тому числі за умови дії засобів РЕБ. Напрямком подальших досліджень може бути оптимальний синтез траєкто- рій пошуку об’єкта для групи БПЛА. Л.Ф. ГУЛЯНИЦЬКИЙ, В.Ю. КОРОЛЬОВ, М.І. ОГУРЦОВ, О.М. ХОДЗІНСЬКИЙ ISSN 2616-938Х. Компьютерная математика. 2018, № 246 Л.Ф. Гуляницкий, В.Ю. Королев, А.Н. Ходзинский, М.И. Огурцов ПРОБЛЕМЫ МАРШРУТИЗАЦИИ БПЛА В ЗАДАЧАХ ПОИСКА И МОНИТОРИНГА Рассмотрены проблемы поиска подвижных объектов и мониторинга территории группой беспилотных летательных аппаратов (БПЛА). Показано, что модель движения транспортных средств с несколькими депо можно применить для планирования полета групп БПЛА. Пред- ложенная постановка задачи позволяет ускорить поиск объектов и минимизировать необхо- димое количество БПЛА. L.F. Hulianytskyi, V.Yu. Korolyov, O.M. Khodzinsky, M.I. Ogurczov PROBLEMS OF UAV ROUTING IN SEARCH AND MONITORING The problems of search for mobile objects and territory monitoring with a group of unmanned aerial vehicles (UAVs) are considered. We show that a model of vehicles traffic with several depots can be applied to planning UAV group flight. The proposed problem statement allows us to accelerate the search of objects and minimize the required number of UAVs. Список літератури 1. Golden B., Raghavan S., Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges, New York: Springer, 2008. 2. Гуляницкий Л.Ф. Проблема оптимизации маршрутов транспортных средств с временны- ми окнами. Компьютерная математика. 2007. № 1. С. 122 – 132. 3. Корольов В.Ю., Огурцов М.І., Ходзінський О.М. Математичне моделювання маршрутів рухомих дистанційно керованих систем та їх груп при обстеженні території. Інтелек- туальні системи прийняття рішень і проблеми обчислювального інтелекту: Матеріали міжнародної наукової конференції. Херсон: Видавництво ПП Вишемирський В.С. 2017. С. 199 – 201. 4. Корольов В.Ю., Огурцов М.І. Транспортно-комунікаційна задача для груп безпілотних апаратів. Математичні машини і системи. 2017. № 1. С. 82 – 89. 5. Огурцов М.І., Ходзінський О.М. Розробка алгоритмів розв’язання задачі маршрутизації транспортних засобів з часовими вікнами. Компьютерная математика. 2016. №1. С. 134 –142. 6. Корольов В.Ю., Огурцов М.І., Ходзінський О.М. Про задачу побудови маршрутів руху для групи рухомих дистанційно керованих систем. Обчислювальний інтелект (результа- ти, проблеми, перспективи). Пр. міжн. наук-практ. конф. (12 – 15 травня 2015 р., Київ). Наук. ред. В.Є. Снітюк / Мін-во освіти і науки України, Київ. нац. ун-т імені Тараса Шевченка. Черкаси: Видавець Чабаненко Ю. 2015. С. 247 – 248. 7. Корольов В.Ю., Ходзінський О.М. Тополого-комбінаторна модель побудови мереж для транспортних засобів. Компьютерная математика. 2018. № 1. С. 11 – 19. 8. Корольов В.Ю., Поліновський В.В., Огурцов М.І. Моделювання мереж зв’язку рухомих дистанційно керованих систем на базі HLA. Вісник Хмельницького національного уні- верситету. 2017. № 1(245). С. 160 – 165. 9. Гуляницький Л.Ф. Прикладні методи комбінаторної оптимізації: навч. посіб. / Л.Ф. Гу- ляницький, О.Ю. Мулеса. К.: Видавничо-поліграфічний центр «Київський університет», 2016. 133 с. ПРОБЛЕМА МАРШРУТИЗАЦІЇ ГРУП БПЛА В ЗАДАЧАХ ПОШУКУ І МОНІТОРИНГУ ISSN 2616-938Х. Компьютерная математика. 2018, № 2 47 10. Баранов А.Р., Маслак Ю.Г. Тактико-специальная подготовка войскового разведчика вну- тренних войск: Учебно-практическое пособие. М.: Академический Проект; Екатерин- бург, Деловая книга, 2006. 368 с. 11. Мельников Ю.П. Воздушная радиотехническая разведка (методы оценки эффективно- сти). М.: Радиотехника, 2005. 304 с. 12. Чуев Ю.В. Исследование операций в военном деле. М.: Воениздат, 1970. 256 с. 13. Вентцель Е.С. Введение в исследование операций. М.: Советское радио, 1964. 390 с. 14. Морз Ф., Кимбелл Дж. Методы исследования операций. М.: Советское радио, 1956. 308 с. 15. Емельянов Л.А., Абчук В.А., Лапшин В.П., Суздаль В.Г. Теория поиска в военном деле. М.: Воениздат, 1964. 208 с. 16. Jaiswal N.K. Military operations research: quantitative decision making, Springer Science, New York, 1997. 397 р. 17. Гуляницький Л.Ф., Рибальченко О.В. Формалізація та розв’язування одного типу задач маршрутизації БПЛА. Теорія оптимальних рішень. 2018. 17. С. 107 – 114. 18. Ходзінський О.М., Огурцов М.І. Про формалізацію задачі маршрутизації транспортних засобів із часовими вікнами. XXI Всеукр. наук. конф. «Сучасні проблеми прикладної ма- тематики та інформатики» (APAMCS-2015), 24 – 25 вересня 2015. Львів: Львівський національний університет імені Івана Франка. 2015. С. 320 – 322. 19. Ходзінський О.М., Огурцов М.І. Паралельний наближений алгоритм розв’язання задачі оптимізації маршрутів транспортних засобів з часовими вікнами. Обчислювальний інте- лект (результати, проблеми, перспективи): праці міжнар. наук-практ. конф. 12 – 15 трав- ня 2015 р. Київ – Черкаси / М-во освіти і науки України, Київ. Нац. ун-т імені Тараса Шевченка та [ін.]; наук. ред В.Є. Снітюк. Черкаси: видавець Чабаненко Ю. 2015. С. 113 – 114. Одержано 31.10.2018 Про авторів: Гуляницький Леонід Федорович, зав. відділу, доктор технічних наук, старший науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Е-mail: lh_dar@hotmail.com Королев Вячеслав Юрійович, кандидат технічних наук, старший науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Е-mail: korolev@i.ua Огурцов Максим Ігоревич, науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Е-mail: romantic84@gmail.com Ходзінський Олександр Миколайович, кандидат фізико-математичних наук, старший науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України. Е-mail: okhodz@gmail.ua

Проблема маршрутизації груп БПЛА в задачах пошуку і моніторингу

Institution

Ähnliche Einträge