ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОКРЫТИЯ ТЕРРИТОРИИ ГРУППОЙ БЕСПИЛОТНЫХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ ПРИ ПОДДЕРЖКЕ НАЗЕМНОЙ МОБИЛЬНОЙ ЗАРЯДНОЙ СТАНЦИИ: ФОРМИРОВАНИЕ ХРОМОСОМЫ
Аннотация
Статья посвящена решению актуальной проблемы покрытия территории при помощи
беспилотных летательных аппаратов (БЛА) с использованием мобильных зарядных станций.
Современные практические задачи покрытия территории требуют одновременного участия
нескольких БЛА с целью оптимизации временных затрат в ходе миссии. Другим ограничи-
вающим фактором в контексте охвата территории с использованием БЛА является дли-
тельность автономной работы этих систем. Из-за ограниченной дальности полета на од-
ном заряде батареи может возникнуть необходимость в использовании зарядных станций
для завершения миссии охвата. Статичные зарядные станции позволяют зарядить аккуму-
ляторы БЛА, однако это приводит к прерыванию миссии и увеличивает время, необходимое
для завершения охвата. При использовании статичных зарядных станций важно так же
правильно выбрать их местоположение, учитывая доступные места для установки. При
этом сам процесс установки зарядных станций требует времени, что делает их использова-
ние нецелесообразным в миссиях, где покрытие территории нужно осуществить в кратчай-
шие сроки, например, при спасательных или поисковых операциях. Мобильные зарядные
станции, которые способны перемещаться по территории для оптимизации процесса заря-
да или замены аккумуляторов БЛА лишены этих недостатков. Возникает задача планирова-
ния траекторий движения не только для БЛА, но и мобильной зарядной станции. При совме-
стном планировании движения повышается эффективность охвата, но одновременно воз-
растает и вычислительная сложность при поиске траекторий. В настоящей статье реша-
ется задача эффективного покрытия территории с использованием нескольких БЛА и мо-
бильной зарядной станции при помощи генетического алгоритма. Для адаптации задачи к
использованию генетического алгоритма предлагается и обосновывается способ формирова-
ния хромосомы, которая корректно отражает решение задачи и позволяет закодировать
траектории движения БЛА, мобильной зарядной станции, а также учитывает время и ме-
сто проведения подзарядки или замены аккумулятора БЛА. Для исследования предложенного
алгоритма разработано программное обеспечение на языке программирования Python. Адек-
ватность предложенного подхода подтверждена результатами моделирования
Литература
Systems, 2013, No. 12 (61), pp. 1258-1276.
2. Semenas R., Bausys R. Adaptive Strategy for Environment Exploration in Search and Rescue
Missions by Autonomous Robot Lecture Notes in Networks and Systems, ed. by H. Sharma
[et al.]. Singapore: Springer Singapore, 2021б зз. 335-353.
3. Almadhoun R., Taha T., Seneviratne L., Zweiri Y. A survey on multi-robot coverage path planning
for model reconstruction and mapping, SN Applied Sciences, 2019, No. 8 (1), pp. 847.
4. Cabreira T., Brisolara L., Ferreira Jr. P.R. Survey on Coverage Path Planning with Unmanned
Aerial Vehicles, Drones, 2019, No. 1 (3), pp. 4.
5. Bai Y., Wang Y., Svinin M., Magid E., Sun R. Adaptive Multi-Agent Coverage Control With
Obstacle Avoidance, IEEE Control Systems Letters, 2022, 6, pp. 944-949.
6. Hayat S., Yanmaz E., Brown T.X., Bettstetter C. Multi-objective UAV path planning for search
and rescue. Singapore, Singapore: IEEE, 2017, pp. 5569-5574.
7. Kalyaev I.A., Kapustyan S.G. Gruppovoe upravlenie robotami: problemy, resheniya [Group control
of robots: problems, solutions], Izvestiya vysshikh uchebnykh zavedeniy. Mashinostroenie [News of
higher educational institutions. Mechanical engineering], 2011, 13, pp. 7-12.
8. Karapetyan N., Benson K., McKinney C., Taslakian P., Rekleitis I. Efficient Multi-Robot Coverage
of a Known Environment, 2017, pp. 1846-1852.
9. Vasil'ev I.A, Polovko S.A., Smirnova E.Yu. Organizatsiya gruppovogo upravleniya mobil'nymi
robotami dlya zadach spetsial'noy robototekhniki [Organization of group control of mobile robots
for special robotics tasks], Informatika, telekommunikatsii i upravlenie [Informatics, telecommunications
and control], 2013, pp. 119-123.
10. Di Franco C., Buttazzo G. Energy-Aware Coverage Path Planning of UAVs. – Vila Real:
IEEE, 2015. – P. 111-117.
11. Suzuki K.A.O., Kemper Filho P., Morrison J.R. Automatic Battery Replacement System for UAVs:
Analysis and Design, Journal of Intelligent & Robotic Systems, 2012, No. 1–4 (65), pp. 563-586.
12. Li B., Patankar S., Moridian B., Mahmoudian, N. Planning Large-Scale Search and Rescue
using Team of UAVs and Charging Stations Philadelphia, PA, USA: IEEE, 2018, pp. 1-8.
13. Li B., Page B. R., Hoffman J., Moridian B., Mahmoudian N. Rendezvous Planning for Multiple
AUVs With Mobile Charging Stations in Dynamic Currents, IEEE Robotics and Automation
Letters, 2019, No. 2 (4), pp. 1653-1660.
14. Wei M., Isler V. Coverage Path Planning Under the Energy Constraint Brisbane, QLD: IEEE,
2018, pp. 368-373.
15. Tan C.S., Mohd-Mokhtar R., Arshad M.R. A Comprehensive Review of Coverage Path Planning in
Robotics Using Classical and Heuristic Algorithms, IEEE Access, 2021, 9, pp. 119310-119342.
16. Denisov E., Sagitov A., Yakovlev K.S., Su K.L., Svinin M.M., Magid E. Towards Total Coverage
in Autonomous Exploration for UGV in 2.5D Dense Clutter Environment: Prague, Czech
Republic: SCITEPRESS - Science and Technology Publications, 2019, pp. 409-416.
17. Pshikhopov V.Kh., Medvedev Yu.M., Kostyukov V.A., Khusseyn F. Kadim A. Trajectory planning
algorithms in two-dimensional environment with obstacles, Informatika i avtomatizatsiya
[Computer science and automation], 2022, 21 (3), pp. 459-492.
18. Gladkov L., Kureychik V., Kureychik V. Geneticheskie algoritmy [Genetic algorithms]. Moscow:
Fizmatlit, 2010, 368 p.
19. Umbarkar A.J., Sheth P.D. Crossover operators in genetic algorithms: a review, ICTACT
Journal on Soft Computing, 2015, No. 01 (06), pp. 1083-1092.
20. Lozano M., Herrera F., Cano J. Replacement strategies to preserve useful diversity in steadystate
genetic algorithms, Information Sciences, 2008, No. 23 (178), pp. 4421-4433.
21. Deb K., Deb A. Analysing mutation schemes for real-parameter genetic algorithms, International
Journal of Artificial Intelligence and Soft Computing, 2014, No. 1 (4), pp. 1.
22. Tuncer A., Yildirim M. Chromosome Coding Methods in Genetic Algorithm for Path Planning of Mobile
Robots,ed. by E. Gelenbe, R. Lent, G. Sakellari. London: Springer London, 2011, pp. 377-383.
23. Guruji A. K., Agarwal H., Parsediya D. K. Time-efficient A* Algorithm for Robot Path Planning,
Procedia Technology, 2016, 23, pp. 144-149.
24. Koenig S., Likhachev M. D* lite, In Eighteenth national conference on Artificial intelligence,
2002, pp. 476-483.
