Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement
Every year, the scope of unmanned aerial vehicles use is growing, and the amount of such applications is expanding. To enhance efficiency, the focus of development is shifting from individual unmanned aerial vehicles to utilizing swarms for various applications such as agricultural surveys, irrigati...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут програмних систем НАН України
2024
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/632 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-632 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/95/cf0a409470ccc59a2fb8c7d3516f2f95.pdf |
| spelling |
pp_isofts_kiev_ua-article-6322025-02-15T11:56:00Z Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement Розробка алгоритму локальної навігації зграї сільськогосподарських БПЛА під час руху рою Korolyov, V.Yu. Ogurtsov, M.I. Rybalchenko, O.V. Khodzinskyi, O.M. UAV; drone, swarm; swarm control; local positioning; multilateration; triangulation; Euclidean space UDC 621.396.96 БПЛА; дрон; рій; ройове керування; локальне позиціювання; мультилатерація; триангуляція; Евклідів простір УДК 621.396.96 Every year, the scope of unmanned aerial vehicles use is growing, and the amount of such applications is expanding. To enhance efficiency, the focus of development is shifting from individual unmanned aerial vehicles to utilizing swarms for various applications such as agricultural surveys, irrigation, etc. The purpose of this work is to develop an algorithm for building a local positioning system for a swarm of unmanned aerial vehicles to maintain a stable structure during the swarm movement while performing its tasks in two-dimensional and three-dimensional settings. At the same time, it should be assumed that the swarm is controlled by one operator, regardless of the number of swarm elements. An additional limitation of the developed algorithm should be the prevention of potential collisions of unmanned aerial vehicles during aerial maneuvers. As part of the work, the task of forming and maintaining the structure and configuration of an agricultural unmanned aerial vehicles flock in two-dimensional and three-dimensional settings was set. The formalization of the given task has been completed. Considered possible methods of mapping the graph formed by an unmanned aerial vehicles swarm into two-dimensional Euclidean space by the forming a basic triangle method to create a relative coordinate system. To determine the coordinates of the remaining graph vertices on the plane and correspondingly increase the accuracy of local positioning, the multilateration method is used. Considered simplified options – application of the trilateration and triangulation algorithms. For the problem in a three-dimensional setting, the possibility of applying the multidimensional scaling algorithm using the methods of multidimensional scaling/reduction of dimensions is considered. The developed practical implementation of the created algorithm showed its efficiency during practical experiments, allowing to determine the local positioning of elements of a swarm containing from three to twenty elements.Prombles in programming 2024; 2-3: 155-162 З кожним роком зростають обсяги застосування безпілотних літальних апаратів та розширюються сфери такого застосування. Водночас поступово акцент зміщується від застосування окремих безпі=лотних літальних апаратів до використання роїв безпілотних літальних апаратів, оскільки для багатьох задач (наприклад, обстеження сільськогосподарських ділянок, зрошення і т.д.) це є ефективнішим, ніж застосування окремих безпілотних літальних апаратів. Метою даної роботи є розробка алгоритму побудови системи локального позиціювання рою безпілотних літальних апаратів для утримання сталої структури під час руху рою впродовж виконання ним поставлених задач в двовимірній та тривимірній постановках. Однак слід вважати, що роєм керує один оператор, незважаючи на кількість елементів рою. Додатковим обмеженням розробленого алгоритму має бути запобігання потенційних зіткнень безпілотних літальних апаратів під час повітряних маневрів. У рамках виконання роботи поставлено задачу формування та підтримання структури та конфігурації зграї сільськогосподарських безпілотних літальних апаратів у двовимірній та тривимірній постановках. Виконано формалізацію поставленої задачі. Розглянуті можливі методи відображення графа, що утворюється роєм безпілотних літальних апаратів, у двовимірний Евклідів простір методом формування базового трикутника для створення відносної системи координат. Для визначення координат решти вершин графа на площині та відповідного підвищення точності локального позиціювання застосований метод мультилатерації. Розглянуті спрощені варіанти – застосування алгоритму трилатерації та триангуляції. тановці розглянуто можливість застосування алгоритму багатовимірного масштабування з використанням методів багатовимірного масштабування/скорочення вимірів. Розроблена практична реалізація створеного алгоритму показала свою працездатність під час проведення практичних експериментів, дозволяючи визначити локальне позиціювання елементів рою, що містить від трьох до двадцяти елементів.Prombles in programming 2024; 2-3: 155-162 Інститут програмних систем НАН України 2024-12-17 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/632 10.15407/pp2024.02-03.155 PROBLEMS IN PROGRAMMING; No 2-3 (2024); 155-162 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2024); 155-162 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2024); 155-162 1727-4907 10.15407/pp2024.02-03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/632/684 Copyright (c) 2024 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-02-15T11:56:00Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
UAV; drone swarm; swarm control; local positioning; multilateration; triangulation; Euclidean space UDC 621.396.96 |
| spellingShingle |
UAV; drone swarm; swarm control; local positioning; multilateration; triangulation; Euclidean space UDC 621.396.96 Korolyov, V.Yu. Ogurtsov, M.I. Rybalchenko, O.V. Khodzinskyi, O.M. Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| topic_facet |
UAV; drone swarm; swarm control; local positioning; multilateration; triangulation; Euclidean space UDC 621.396.96 БПЛА дрон рій ройове керування локальне позиціювання мультилатерація триангуляція Евклідів простір УДК 621.396.96 |
| format |
Article |
| author |
Korolyov, V.Yu. Ogurtsov, M.I. Rybalchenko, O.V. Khodzinskyi, O.M. |
| author_facet |
Korolyov, V.Yu. Ogurtsov, M.I. Rybalchenko, O.V. Khodzinskyi, O.M. |
| author_sort |
Korolyov, V.Yu. |
| title |
Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| title_short |
Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| title_full |
Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| title_fullStr |
Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| title_full_unstemmed |
Development of the local navigation algorithm of the agricultural UAVS flock during swarm movement |
| title_sort |
development of the local navigation algorithm of the agricultural uavs flock during swarm movement |
| title_alt |
Розробка алгоритму локальної навігації зграї сільськогосподарських БПЛА під час руху рою |
| description |
Every year, the scope of unmanned aerial vehicles use is growing, and the amount of such applications is expanding. To enhance efficiency, the focus of development is shifting from individual unmanned aerial vehicles to utilizing swarms for various applications such as agricultural surveys, irrigation, etc. The purpose of this work is to develop an algorithm for building a local positioning system for a swarm of unmanned aerial vehicles to maintain a stable structure during the swarm movement while performing its tasks in two-dimensional and three-dimensional settings. At the same time, it should be assumed that the swarm is controlled by one operator, regardless of the number of swarm elements. An additional limitation of the developed algorithm should be the prevention of potential collisions of unmanned aerial vehicles during aerial maneuvers. As part of the work, the task of forming and maintaining the structure and configuration of an agricultural unmanned aerial vehicles flock in two-dimensional and three-dimensional settings was set. The formalization of the given task has been completed. Considered possible methods of mapping the graph formed by an unmanned aerial vehicles swarm into two-dimensional Euclidean space by the forming a basic triangle method to create a relative coordinate system. To determine the coordinates of the remaining graph vertices on the plane and correspondingly increase the accuracy of local positioning, the multilateration method is used. Considered simplified options – application of the trilateration and triangulation algorithms. For the problem in a three-dimensional setting, the possibility of applying the multidimensional scaling algorithm using the methods of multidimensional scaling/reduction of dimensions is considered. The developed practical implementation of the created algorithm showed its efficiency during practical experiments, allowing to determine the local positioning of elements of a swarm containing from three to twenty elements.Prombles in programming 2024; 2-3: 155-162 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2024 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/632 |
| work_keys_str_mv |
AT korolyovvyu developmentofthelocalnavigationalgorithmoftheagriculturaluavsflockduringswarmmovement AT ogurtsovmi developmentofthelocalnavigationalgorithmoftheagriculturaluavsflockduringswarmmovement AT rybalchenkoov developmentofthelocalnavigationalgorithmoftheagriculturaluavsflockduringswarmmovement AT khodzinskyiom developmentofthelocalnavigationalgorithmoftheagriculturaluavsflockduringswarmmovement AT korolyovvyu rozrobkaalgoritmulokalʹnoínavígacíízgraísílʹsʹkogospodarsʹkihbplapídčasruhuroû AT ogurtsovmi rozrobkaalgoritmulokalʹnoínavígacíízgraísílʹsʹkogospodarsʹkihbplapídčasruhuroû AT rybalchenkoov rozrobkaalgoritmulokalʹnoínavígacíízgraísílʹsʹkogospodarsʹkihbplapídčasruhuroû AT khodzinskyiom rozrobkaalgoritmulokalʹnoínavígacíízgraísílʹsʹkogospodarsʹkihbplapídčasruhuroû |
| first_indexed |
2025-07-17T10:07:55Z |
| last_indexed |
2025-07-17T10:07:55Z |
| _version_ |
1838410684686139392 |
| fulltext |
155
Прикладне програмне забезпечення
УДК 621.396.96 http://doi.org/10.15407/pp2024.02-03.155
В.Ю. Корольов, М.І. Огурцов, О.В. Рибальченко, О.М. Ходзінський
РОЗРОБЛЕННЯ АЛГОРИТМУ ЛОКАЛЬНОЇ НАВІГАЦІЇ
ЗГРАЇ СІЛЬСЬКОГОСПОДАРСЬКИХ БПЛА
ПІД ЧАС РУХУ РОЮ
З кожним роком зростають обсяги застосування безпілотних літальних апаратів та розширюються
сфери такого застосування. Водночас поступово акцент зміщується від застосування окремих безпі-
лотних літальних апаратів до використання роїв безпілотних літальних апаратів, оскільки для бага-
тьох задач (наприклад, обстеження сільськогосподарських ділянок, зрошення і т.д.) це є ефективні-
шим, ніж застосування окремих безпілотних літальних апаратів.
Метою даної роботи є розробка алгоритму побудови системи локального позиціювання рою безпіло-
тних літальних апаратів для утримання сталої структури під час руху рою впродовж виконання ним
поставлених задач в двовимірній та тривимірній постановках. Однак слід вважати, що роєм керує
один оператор, незважаючи на кількість елементів рою. Додатковим обмеженням розробленого алго-
ритму має бути запобігання потенційних зіткнень безпілотних літальних апаратів під час повітряних
маневрів.
У рамках виконання роботи поставлено задачу формування та підтримання структури та конфігура-
ції зграї сільськогосподарських безпілотних літальних апаратів у двовимірній та тривимірній поста-
новках. Виконано формалізацію поставленої задачі. Розглянуті можливі методи відображення графа,
що утворюється роєм безпілотних літальних апаратів, у двовимірний Евклідів простір методом фор-
мування базового трикутника для створення відносної системи координат. Для визначення коорди-
нат решти вершин графа на площині та відповідного підвищення точності локального позиціювання
застосований метод мультилатерації. Розглянуті спрощені варіанти – застосування алгоритму трила-
терації та триангуляції.
тановці розглянуто можливість застосування алгоритму багатовимірного масштабування з викорис-
танням методів багатовимірного масштабування/скорочення вимірів. Розроблена практична реаліза-
ція створеного алгоритму показала свою працездатність під час проведення практичних експеримен-
тів, дозволяючи визначити локальне позиціювання елементів рою, що містить від трьох до двадцяти
елементів.
Ключові слова: БПЛА, дрон, рій, ройове керування, локальне позиціювання, мультилатерація, триан-
гуляція, Евклідів простір.
V. Korolyov, M. Ogurtsov, O. Rybalchenko, O. Khodzinskyi
DEVELOPMENT OF THE LOCAL NAVIGATION
ALGORITHM OF THE AGRICULTURAL UAVS FLOCK
DURING SWARM MOVEMENT
Every year, the scope of unmanned aerial vehicles use is growing, and the amount of such applications is
expanding. To enhance efficiency, the focus of development is shifting from individual unmanned aerial ve-
hicles to utilizing swarms for various applications such as agricultural surveys, irrigation, etc.
The purpose of this work is to develop an algorithm for building a local positioning system for a swarm of
unmanned aerial vehicles to maintain a stable structure during the swarm movement while performing its
tasks in two-dimensional and three-dimensional settings. At the same time, it should be assumed that the
swarm is controlled by one operator, regardless of the number of swarm elements. An additional limitation
of the developed algorithm should be the prevention of potential collisions of unmanned aerial vehicles dur-
ing aerial maneuvers.
As part of the work, the task of forming and maintaining the structure and configuration of an agricultural
unmanned aerial vehicles flock in two-dimensional and three-dimensional settings was set. The formaliza-
tion of the given task has been completed. Considered possible methods of mapping the graph formed by an
unmanned aerial vehicles swarm into two-dimensional Euclidean space by the forming a basic triangle
method to create a relative coordinate system. To determine the coordinates of the remaining graph vertices
© В.Ю. Корольов, М.І. Огурцов, О.В. Рибальченко, О.М. Ходзінський, 2024
ISSN 1727-4907. Проблеми програмування. 2024. №2-3
156
Прикладне програмне забезпечення
on the plane and correspondingly increase the accuracy of local positioning, the multilateration method is
used. Considered simplified options – application of the trilateration and triangulation algorithms.
For the problem in a three-dimensional setting, the possibility of applying the multidimensional scaling al-
gorithm using the methods of multidimensional scaling/reduction of dimensions is considered. The devel-
oped practical implementation of the created algorithm showed its efficiency during practical experiments,
allowing to determine the local positioning of elements of a swarm containing from three to twenty ele-
ments.
Key words: UAV, drone, swarm, swarm control, local positioning, multilateration, triangulation, Euclidean
space.
Вступ
З кожним роком зростають обсяги
застосування безпілотних літальних апара-
тів (БПЛА) та розширюються сфери такого
застосування. При цьому поступово акцент
зміщується від застосування окремих БП-
ЛА до використання роїв БПЛА, оскільки
для багатьох задач (наприклад, об-
стеження сільськогосподарських ділянок,
зрошення і т.д.) це є ефективнішим, аніж
застосування окремих БПЛА [1]. Підви-
щення ефективності досягається за раху-
нок зменшення кількості операторів, пот-
рібних для функціонування тієї ж кількості
БПЛА як елементів рою, замість їх вико-
ристання в режимі «один оператор – один
БПЛА». До того ж використання роїв
уможливлює застосування групового ке-
рування з елементами штучного інтелекту,
що в багатьох задачах перевершує можли-
вості та швидкість реакції людини-
оператора [2]. Але водночас існує ряд про-
блем, зокрема, у ряді випадків недоступ-
ність GPS для сільськогосподарських дро-
нів, які виконують завдання обробки сіль-
ськогосподарських угідь від шкідників чи
моніторингу посівів [3].
Мета
Метою даної роботи є розроблення
алгоритму побудови системи локального
позиціювання рою БПЛА для утримання
сталої структури під час руху рою впро-
довж виконання ним поставлених завдань
в двовимірній та тривимірній постановках.
Водночас слід зважати, що роєм керує
один оператор, незалежно від кількості
елементів рою. Додатковим обмеженням
для розробленого алгоритму має бути за-
побігання потенційних зіткнень БПЛА під
час повітряних маневрів.
Зазвичай в подібних задачах не ви-
користовують варіант з розробкою систе-
ми локального взаємного позиціювання
елементів рою, поданий в даній роботі.
Аналіз попередніх розробок
В існуючих наукових дослідженнях,
присвячених розв'язуванню поставленої
задачі [1-7], слід виділити підходи, засно-
вані на використанні парадигми Інтернету
речей та засобах штучного інтелекту [4].
Варто зазначити, що вони є ресурсоємни-
ми, вимагають значних обчислювальних
потужностей, що обмежує сферу можливо-
го застосування. Цікавим також є застосу-
вання паралельних генетичних алгоритмів
та інших методів комбінаторної оптиміза-
ції [5], хоча слід підкреслити, що, на думку
авторів, розв’язування поставленої задачі у
низці застосувань можливе без викорис-
тання подібних методів простішим шля-
хом.
Іншим підходом є попереднє плану-
вання маршрутів рою БПЛА [6], але це
значно звужує сферу застосування роїв на
основі такого підходу.
Найпопулярнішим варіантом є ви-
користання алгоритмів оптимізації роєм
частинок [6-7], хоча цей метод також є до-
статньо обчислювально трудомістким.
Основна частина
Розглянемо спочатку, як задача мо-
же розв’язуватися у спрощеній, двовимір-
ній постановці, яка є застосовною, коли
рій рухається на приблизно однаковій ви-
соті, і різницею висоти можна знехтувати.
Цей варіант застосовний для рою наземних
дронів, що комунікують в зоні прямого
поширення радіохвиль. Розглядатимемо
157
Прикладне програмне забезпечення
елементи рою як гомогенні, хоча із дода-
ванням додаткових параметрів та обме-
жень можливе використання гетерогенних
БПЛА.
Змістовно маємо набір дронів, які
мають сформувати рій. В даній роботі роз-
глядається рій до 20 дронів. Кожен дрон
оснащений набором датчиків (GPS, ком-
пас, акселерометр, висотомір), що дозво-
лятимуть визначати взаємні позиції та по-
будову й утримання структури рою. Зада-
чею є досягнення потрібної конфігурації
взаємного розміщення рою за мінімальний
час та подальше утримання цієї конфігу-
рації з мінімальними витратами сумарного
льотного ресурсу всіх елементів рою. Ал-
горитм має функціонувати ітеративно, з
частотою повторення не менше, ніж раз на
кілька секунд, щоб враховувати можливі
зміни взаємного положення елементів рою.
Конфігурація, яку має сформувати рій, по-
винна забезпечувати рівні відстані між су-
міжними елементами рою, тобто три БП-
ЛА утворять рівносторонній трикутник,
чотири – квадрат і так далі. Таким чином
маємо:
Вхідні дані – дані з датчиків кожно-
го елемента рою:
- координати GPS;
- напрям руху;
- швидкість;
- висота.
Параметри:
- максимальна швидкість руху
БПЛА;
- максимально допустима висота
польоту БПЛА;
- мінімально допустима висота
польоту БПЛА;
- максимальна дальність польоту
БПЛА;
- мінімально допустима відстань
між БПЛА.
Обмеження:
Мінімізація сумарного додаткового
руху всіх БПЛА рою, потрібного для від-
новлення заданої конфігурації.
Вихідні дані:
GPS координати точок, куди має
переміститись кожен БПЛА для віднов-
лення заданої конфігурації рою.
1. Двовимірна постановка
задачі
Двовимірна постановка задачі пе-
редбачатиме відображення графа, що
утворюється роєм БПЛА, спочатку у три-
вимірний Евклідів простір [8], який потім
має бути приведений до двовимірного
простору.
Розглянемо формальну постановку
задачі:
( , )G V E – повний граф БПЛА, за-
даний
n V= – кількість вершин графа,
1{ ,..., }nV v v= , кожна вершина представ-
ляє собою елемент рою, окремий БПЛА,
що має набір із трьох координат
( , , ), 1,i i ix y z i n= – координати
цих вершин, де ,i ix y невідомі, а iz відо-
мі.
12 13 1,{ , ,..., }n nE e e e −= – відомі до-
вжини ребер.
Розглянемо тепер відображення
графа з тривимірного Евклідова простору
до задачі на площині (Рис. 1).
Рис. 1. Зведення тривимірної задачі
до задачі на площині
З рисунка легко побачити, що дов-
жина проєкції ребра ije між вершинами
,i jv v на площину XOY:
2 2' ( )ij ij j ie e z z= − −
Для того, щоб сформувати на основі
відомих координат елементів рою, потріб-
ну конфігурацію, спочатку треба обрати
базовий (найбільший) трикутник. Його ви-
158
Прикладне програмне забезпечення
користання дозволить формувати потрібну
конфігурацію всередині базового трикут-
ника та не вимагатиме збільшення макси-
мальної відстані між будь-якими двома
елементами рою.
Базовий трикутник у графі можна
вибирати за такими ознаками:
- найбільша сума сторін a b c+ + ,
де , ,a b c – ребра графа для де-
якої трійки вершин.
або
- найбільша площа
( )( )( )S p p a p b p c= − − − , де
2
a b cp + +
= – півпериметр.
В даній роботі використаний саме
базовий трикутник за найбільшою пло-
щею.
При виборі базового трикутника де-
які конфігурації рою призводитимуть до
того, що частина елементів рою можуть
опинитись ззовні базового трикутника (на-
приклад, квадрат для рою з чотирьох еле-
ментів). Це штатна ситуація, в подальшому
позиція елементів буде скоригована і вони
перемістяться всередину базового трикут-
ника.
2. Фіксація базового трикутника
на площині
Після вибору базового трикутника
зберігається кілька ступенів свободи у разі
розміщення проєкції графа на площині.
Виберемо такі: початок системи координат
(перша вершина трикутника), напрямок осі
абсцис (друга вершина трикутника), на-
прямок осі ординат (третя вершина трику-
тника).
1) Зафіксуємо координати вершини
bv як початок координат: (0,0)bv =
2) Сторона b cv v нехай буде части-
ною осі OX : ( ' ,0) ( ,0)c bcv e a= =
3) аy – координату вершини av ви-
значимо з площі трикутника:
( )( )( )
2
aayS p p a p b p c= − − − =
4) аx – координату вершини av ви-
значимо за теоремою Піфагора:
2 2
a ax c y= −
Для визначення координат решти
вершин графа на площині можна застосу-
вати метод мультилатерації [9].
Оскільки доступні дані супутнико-
вого позиціонування, то задача підтримки
структури рою може бути зведена до підт-
римки позиції БПЛА у заданій локації ге-
ометричної фігури на основі абсолютних
значень координат. Але у випадку малих
відстаней між БПЛА точність визначення
координат може бути недостатньою та по-
рушуватись мінімальна відстань між БП-
ЛА, введена для запобігання зіткненням.
3. Проблема підвищення точності
локального позиціонування
Глобальне позиціювання часто не
дає достатнього рівня точності для вико-
нання поставленої задачі – потенційні по-
хибки, що у випадку двох БПЛА, які шви-
дко рухаються, можуть накладатись та су-
муватись, що може викликати зіткнення
елементів рою. Одним з варіантів з вирі-
шення цієї проблеми є застосування мето-
дів мультилатерації – локального позиціо-
нування, яке не залежить від супутникових
систем глобального позиціонування і є то-
чнішим за GPS [10].
Спрощений алгоритм трилатерації
складається з наступних кроків:
Етап 0. Калібрування відстані між
вузлами за потужністю.
Вхідні дані: таблиця відстані на ос-
нові калібрування.
Вихідні дані: відстань між вузлами.
Етап 1. Кожний вузол мережі отри-
мує інформацію про потужність сигналу
від інших вузлів і передає цим вузлам свої
дані.
Етап 2. Кожний вузол для всіх ви-
димих вузлів розраховує відстані за табли-
цею та розраховує локальні координати,
розв’язуючи систему рівнянь трилатерації.
Отримані значення надсилаються всім ву-
злам [11].
Наступним етапом стає застосуван-
ня алгоритмів триангуляції.
159
Прикладне програмне забезпечення
4. Задача в тривимірній
постановці
Розглянемо тепер тривимірну пос-
тановку задачі. Маємо до двадцяти
об’єктів, відстані між якими відомі, та
НСК, до якої теж відома відстань. Крім то-
го, всі об’єкти (1-20 шт.) можуть постійно
окремо дистанційно керуватись (тобто на
НСК отримується телеметрія і вимірюєть-
ся відстань за силою сигналу та часом від-
правлення/отримання пакетів даних), коли
це потрібно оператору. Для НСК відомі
абсолютні координати. Таким чином має-
мо таку постановку задачі:
Дано матрицю відстаней між двома-
двадцять однією точкою тривимірного
простору. Для однієї з цих точок відомі її
абсолютні координати. Треба розробити
алгоритм побудови відносної системи ко-
ординат для цих точок.
Алгоритм багатовимірного масш-
табування. Задачу визначення координат
об’єктів за відстанями між ними можна
звести до відомої задачі скорочення розмі-
рності вхідних даних. Загальний підхід до
вирішення проблеми скорочення розмір-
ності даних полягає у виконанні послідов-
них кроків для зменшення кількості змін-
них, що описують ці дані, а результатом
роботи відповідних алгоритмів є впоряд-
кована множина головних змінних.
Методи багатовимірного масштабу-
вання/скорочення вимірів (Multidimensional
Scaling – MDS) застосовані до різних типів
даних [12].
Основна ідея MDS полягає в тому,
щоб знайти загальний процес у низькови-
мірному просторі, який мінімізує диспер-
сію (D) у високовимірному просторі та за-
лежну дисперсію (d) у низьковимірному
просторі. Маючи матрицю несхожості або
відстані D, що представляє різницю між
точками i та j у просторі, де Dij є, евклідо-
вою відстанню, MDS намагається знайти
набір координат xi та xj. Це робиться в ни-
зьковимірному просторі, щоб евклідова ві-
дстань між точками i та j (позначена dij)
була якомога ближчою до різниці Dij.
Метрикою алгоритму MDS є функ-
ція напруги S (цільова функція):
( )2
ij ij ijS W d D = −
де Wij — це вага, яку можна вико-
ристовувати для підкреслення або змен-
шення акценту на певних відстанях.
dij — евклідова відстань між точка-
ми даних i та j у просторі нижчого виміру.
Dij — це відмінність (відстань) між
точками даних i та j у просторі великої ви-
мірності.
Функція напруги S визначається як:
( )2
2
1
, ,
1 1
ˆ
n n
i j i jn
i j
S l l
= =
= −
де lij — відстань між точками даних
i та j у вихідному просторі, ,î jl — відстань
між точками даних i та j у просторі нижчої
вимірності, а n — число точок даних. Фун-
кція напруги S є мірою відхилення відста-
ней у нижньовимірному просторі від відс-
таней у вихідному просторі та використо-
вується для оцінки якості проєкції.
Для створення відносної системи
координат у кількості точок від трьох до
двадцяти однієї у тривимірному просторі
на основі матриці відстаней та абсолютних
координат однієї точки, ми використали
розроблену нами модифікацію алгоритму
MDS. Додатково потрібно було налашту-
вати вихідні координати, щоб включити
відомі абсолютні координати однієї точки.
При цьому акцент робився на виконанні
обчислень на одноплатних комп’ютерах
типу Raspberry Pi 4B на борту дронів [13].
Для практичної реалізації поставле-
ної задачі на основі розробленого алгори-
тму був створений сценарій Python, який
використовує бібліотеку scikit-learn для
випадку 10 БПЛА. Вони миістяться у ло-
кальній системі координат та один керую-
чий об’єкт прив’язаний до глобальної сис-
теми координат.
Алгоритм MDS застосований до ма-
триці відстаней між дронами дозволив
знайти відносні координати десяти точок у
тривимірному просторі (локальна система
координат рою), а потім відкоригував ці
відносні координати, щоб включити відомі
абсолютні координати однієї точки (Рис. 2).
Таким чином десять об’єктів знахо-
дяться у локальній системі координат без
160
Прикладне програмне забезпечення
прив’язування до абсолютної географічної
системи координат.
Розроблений сценарій застосовує
MDS до матриці відстаней, щоб знайти
відносні координати точок (у прикладі –
десяти) у тривимірному просторі, а потім
коригує ці відносні координати, з метою
включення відомих абсолютних координат
однієї точки.
Рис. 2. Подання матриці відстаней
між одинадцятьма об’єктами у вигляді не-
орієнтованого повнозв’язного графу
Нарешті, він малює точки на триви-
мірному графіку за допомогою matplotlib,
причому кожна точка позначена для іденти-
фікації. Можна налаштувати масив
distances_matrix і змінну absolute_coordinates
для представлення різних відстаней між то-
чками та різними відомими абсолютними
координатами відповідно (Рис. 3).
Рис. 3. Результат розв’язання задачі
MDS для десятьох об’єктів з побудовою
локальної системи координат
Отож, модифікований алгоритм
MDS, застосований до матриці відстаней
між дронами, дозволяє знайти відносні ко-
ординати точок у тривимірному просторі
(локальна система координат рою) для ви-
падків від трьох до двадцяти БПЛА.
У разі його застосування побудова
локальної системи позиціювання елементів
рою є менш обчислювально складною, ніж
в альтернативних постановках [1-7].
Висновки
У рамках виконання роботи постав-
лено задачу формування та підтримання
структури та конфігурації зграї сільськогос-
подарських БПЛА в двовимірній та триви-
мірній постановках. Виконано формалізацію
поставленої задачі. Розглянуті можливі ме-
тоди відображення графа, що утворюється
роєм БПЛА, у двовимірний Евклідів простір
методом формування базового трикутника
для створення відносної системи координат.
Для визначення координат решти вершин
графа на площині та відповідного підви-
щення точності локального позиціювання
застосований метод мультилатерації. Розг-
лянуті спрощені варіанти – застосування ал-
горитму трилатерації та триангуляції.
Для задачі в тривимірній постановці
розглянуто можливість застосування алго-
ритму багатовимірного масштабування з
використанням методів багатовимірного
масштабування/скорочення вимірів. Роз-
роблена практична реалізація створеного
алгоритму показала свою працездатність
під час проведення практичних експери-
ментів, дозволяючи визначити локальне
позиціювання елементів рою, що містить
від трьох до двадцяти елементів.
Напрямом подальших досліджень є
розроблення алгоритму, що дозволяє на ос-
нові визначених локальних координат лікві-
дувати збурення, внесені в структуру рою
через внутрішні чи зовнішні чинники, на-
приклад, втрату одного з елементів рою [14].
Література
1. Y. Zhou, R. Bin, W. Wei, UAV
swarm intelligence: Recent advances
and future trends, Ieee Access 8
(2020): 183856-183878.
2. M. Campion, R. Prakash, F. Saleh,
UAV swarm communication and con-
161
Прикладне програмне забезпечення
trol architectures: a review, Journal of
Unmanned Vehicle Systems, 2018. 7.2.
Pp. 93-106.
3. Сучасні методи цифрового моніто-
рингу в рослинництві: монографія/
Зозуля О.Л. та ін. К.: КНУ імені Та-
раса Шевченка, 2023. 254 с.
4. X. Wang, G. Chen, H. Gong, J. Jiang,
UAV swarm autonomous control
based on Internet of Things and artifi-
cial intelligence algorithms, Journal of
Intelligent & Fuzzy Systems, 2021.
40(4). Pp. 7121-7133.
5. V. Roberge, M. Tarbouchi, G. Labon-
té, Comparison of parallel genetic al-
gorithm and particle swarm optimiza-
tion for real-time UAV path planning.
IEEE Transactions on industrial in-
formatics, 2012. 9(1). Pp. 132-141.
http://dx.doi.org/10.1109/TII.2012.21
98665
6. S. Shao, Y. Peng, C. He, Y. Du, Effi-
cient path planning for UAV for-
mation via comprehensively improved
particle swarm optimization. ISA
transactions, 2020. 97. Pp. 415-430.
7. M. D. Phung, Q. P. Ha, Safety-
enhanced UAV path planning with
spherical vector-based particle swarm
optimization. Applied Soft Computing,
2021. 107. Pp. 107376.
http://dx.doi.org/10.1016/j.asoc.2021.
107376
8. D. Sikeridis, E. EleniTsiropoulou, M.
Devetsikiotis, S. Papavassiliou, Self-
adaptive energy efficient operation in
UAV-assisted public safety networks,
2018 IEEE 19th international work-
shop on signal processing advances in
wireless communications (SPAWC)
2018, June, IEEE. 2018. Pp. 1-5.
9. S. N. Othman, Node positioning in
zigbee network using trilateration
method based on the received signal
strength indicator (RSSI). European
Journal of Scientific Research, 2010.
46(1). Pp. 048-061.
10. F. He, T. Zhou, W. Xiong, S. M.
Hasheminnasab, A. Habib, Automated
aerial triangulation for UAV-based
mapping, Remote Sensing, 10(12).
2018, p. 1952.
http://dx.doi.org/10.3390/rs10121952
11. B. Yang, E. Yang, L. Yu, A. Loeliger,
High-precision UWB-based localisa-
tion for UAV in extremely confined
environments, IEEE Sensors Journal,
2021. 22(1). Pp. 1020-1029.
12. R. Chen, B. Yang, W Zhang, Distrib-
uted and collaborative localization for
swarming UAVs, IEEE Internet of
Things Journal, 2020. 8(6). Pp. 5062-
5074.
13. M. Ogurtsov, V. Korolyov, O. Kho-
dzinskyi, Improving the Productivity
of UAV Operations Based on Granu-
lar Computing and Fuzzy Sets, 2021
IEEE 6th International Conference on
Actual Problems of Unmanned Aerial
Vehicles Development (APUAVD)
19-21 Oct. 2021. 2021, Pp. 33-36.
https://doi.org/10.1109/APUAVD538
04.2021.9615419
14. V.P. Horbulin, L.F. Hulianytskyi, I.V.
Sergienko, Planning of Logistics Mis-
sions of the “UAV+Vehicle” Hybrid
Systems, Cybernetics and System
Analysis, 59, 2023. Pp. 733–742.
https://doi.org/10.1007/s10559-023-
00609-8
References
1. Y. Zhou, R. Bin, W. Wei, UAV
swarm intelligence: Recent advances
and future trends, Ieee Access 8
(2020): 183856-183878.
2. M. Campion, R. Prakash, F. Saleh,
UAV swarm communication and con-
trol architectures: a review, Journal of
Unmanned Vehicle Systems, 2018. 7.2.
Pp. 93-106.
3. Modern methods of digital monitoring
in crop production: monography/
Zozylya et al. K.: Taras Shevchenko
National University of Kyiv, 2023. 254
p.
4. X. Wang, G. Chen, H. Gong, J. Jiang,
UAV swarm autonomous control
based on Internet of Things and artifi-
cial intelligence algorithms, Journal of
Intelligent & Fuzzy Systems, 2021.
40(4). Pp. 7121-7133.
162
Прикладне програмне забезпечення
5. V. Roberge, M. Tarbouchi, G. Labon-
té, Comparison of parallel genetic al-
gorithm and particle swarm optimiza-
tion for real-time UAV path planning.
IEEE Transactions on industrial in-
formatics, 2012. 9(1). Pp. 132-141.
http://dx.doi.org/10.1109/TII.2012.21
98665
6. S. Shao, Y. Peng, C. He, Y. Du, Effi-
cient path planning for UAV for-
mation via comprehensively improved
particle swarm optimization. ISA
transactions, 2020. 97. Pp. 415-430.
7. M. D. Phung, Q. P. Ha, Safety-
enhanced UAV path planning with
spherical vector-based particle swarm
optimization. Applied Soft Computing,
2021. 107. Pp. 107376.
http://dx.doi.org/10.1016/j.asoc.2021.
107376
8. D. Sikeridis, E. EleniTsiropoulou, M.
Devetsikiotis, S. Papavassiliou, Self-
adaptive energy efficient operation in
UAV-assisted public safety networks,
2018 IEEE 19th international work-
shop on signal processing advances in
wireless communications (SPAWC)
2018, June, IEEE. 2018. Pp. 1-5.
9. S. N. Othman, Node positioning in
zigbee network using trilateration
method based on the received signal
strength indicator (RSSI). European
Journal of Scientific Research, 2010.
46(1). Pp. 048-061.
10. F. He, T. Zhou, W. Xiong, S. M.
Hasheminnasab, A. Habib, Automated
aerial triangulation for UAV-based
mapping, Remote Sensing, 10(12).
2018, p. 1952.
http://dx.doi.org/10.3390/rs10121952
11. B. Yang, E. Yang, L. Yu, A. Loeliger,
High-precision UWB-based localisa-
tion for UAV in extremely confined
environments, IEEE Sensors Journal,
2021. 22(1). Pp. 1020-1029.
12. R. Chen, B. Yang, W Zhang, Distrib-
uted and collaborative localization for
swarming UAVs, IEEE Internet of
Things Journal, 2020. 8(6). Pp. 5062-
5074.
13. M. Ogurtsov, V. Korolyov, O. Kho-
dzinskyi, Improving the Productivity
of UAV Operations Based on Granu-
lar Computing and Fuzzy Sets, 2021
IEEE 6th International Conference on
Actual Problems of Unmanned Aerial
Vehicles Development (APUAVD)
19-21 Oct. 2021. 2021, Pp. 33-36.
https://doi.org/10.1109/APUAVD538
04.2021.9615419
14. V.P. Horbulin, L.F. Hulianytskyi, I.V.
Sergienko, Planning of Logistics Mis-
sions of the “UAV+Vehicle” Hybrid
Systems, Cybernetics and System
Analysis, 59, 2023. Pp. 733–742.
https://doi.org/10.1007/s10559-023-
00609-8
Одержано: 09.04.2024
Внутрішня рецензія отримана: 19.04.2024
Зовнішня рецензія отримана: 28.04.2024
Про авторів:
1 Корольов Вячеслав Юрійович,
Кандидат технічних наук,
Старший науковий співробітник
https://orcid.org/0000-0003-1143-5846.
1Огурцов Максим Ігорович,
Науковий співробітник
https://orcid.org/0000-0002-6167-5111.
1Рибальченко Олег Валерійович,
доктор філософії,
молодший науковий співробітник
https://orcid.org/0000-0002-5716-030X.
1 Ходзінський Олександр Миколайович,
Кандидат фізико-математичних наук,
Старший науковий співробітник
https://orcid.org/0000-0003-4574-3628.
Місце роботи авторів:
1Інститут кібернетики
імені В.М. Глушкова
НАН України,
тел. +38-044-526-55-85
E-mail: incyb@incyb.kiev.ua,
Сайт: www.incyb.kiev.ua
|