Математический метод расчета целевой функции на графах и решение задач маршрутизации

Динамика, баллистика, управление движением летательных аппаратов


Авторы

Аллилуева Н. В.1*, Руденко Э. М.2**

1. Научно-производственное предприятие «Радар ммс», ул. Новосельковская, 37 лит. А, Санкт-Петербург, 197375, Россия
2. Военная академия Ракетных войск стратегического назначения имени Петра Великого, ул. Бригадная, 17, Серпухов, Московская обл., 142210, Россия

*e-mail: allilueva_nv@radar-mms.com
**e-mail: eduard5529@yandex.ru

Аннотация

В статье рассматривается алгоритм расчета оптимального маршрута БПЛА на взвешенном графе реперных точек на местности с применением генетического алгоритма. Алгоритм основан на построении целевой аналитической функции нескольких переменных в виде суммы функций заданных на ребрах и на вершинах математического графа. Аргумент целевой функции, минимизирующий ее значение, представляет собой последовательность номеров реперных точек оптимального замкнутого маршрута. Статья отражает взаимосвязь прикладной задачи мониторинга объектов на местности БПЛА с математической задачей оптимизации на графах средствами генетического алгоритма.

Ключевые слова

граф, реперные точки, оптимальные замкнутые маршруты, автоморфизм, целевая функция, генетический алгоритм

Библиографический список

  1. Кристофидес Н. Теория графов. – М.: Мир, 1978. – 427 с.

  2. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. – Новосибирск: Наука, 1990. – 515 с.

  3. Дьяконов В.П., Круглов В.В. Инструменты биоинформатики и искусственного интеллекта. MATLAB 6.5 SP1/7/7 SP1/7 SP2+Simulink 5/6. – М.: Солон-Пресс, 2005. – 454 с.

  4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: Учебное пособие. – М: Физматлит, 2006. – 320 с.

  5. Аллилуева Н.В., Руденко Э.М. Методика решения оптимизационных задач по выбору замкнутых маршрутов на графах на основе генетического алгоритма // Известия института инженерной физики. 2017. № 2 (44). С. 63 – 69.

  6. Лебедев Г.Н., Ефимов А.В., Михайлин Д.А. Оценка вектора состояния беспилотного летательного аппарата при наличии в объекте управления нелинейных элементов // Вестник Московского авиационного института. 2012. Т.19. № 1. С. 12 – 16.

  7. Лебедев Г.Н., Гончаренко В.И., Румакина А.В. Модификация метода ветвей и границ для двумерной маршрутизации координированного полета группы летательных аппаратов // Мехатроника, автоматизация, управление. 2016. Т. 17, № 11. С. 783 –791.

  8. Лебедев Г.Н., Михайлин Д.А., Румакина А.В. Многоступенчатая идентификация неизмеряемых параметров полета при комплексировании сигналов бортовых измерительных средств // Труды МАИ. 2016. № 91. URL: http://trudymai.ru/published.php?ID=75637

  9. Антонов Д.А., Жарков М.В., Кузнецов И.М., Лунев Е.М., Пронькин А.Н. Определение навигационных параметров беспилотного летательного аппарата на базе фотоизображения и инерциальных измерений // Труды МАИ. 2016. № 91. URL: http://trudymai.ru/published.php?ID=75632

  10. Гусейнов А.Б., Маховых А.В. Структурно-параметрический синтез рационального бортового распознающего устройства в составе беспилотного летательного аппарата // Труды МАИ. 2016. № 90. URL: http://trudymai.ru/published.php?ID=74833

  11. Зенкевич С.Л., Хуа Чжу. Управление движением группы роботов в строю типа «конвой» // Мехатроника, автоматизация, управление. 2017. Т. 18. № 1. С. 30 – 34.

  12. Гоголев А.А. Полунатурное моделирование беспилотных летательных аппаратов типа мультикоптер // Труды МАИ. 2017. № 92. URL: http://trudymai.ru/published.php?ID=77238

  13. Новак К.В., Олешко В.С., Старикова И.О., Тофоров М.С. Анализ комплексов с беспилотными летательными аппаратами, применяемых силами специальных операций Соединенных Штатов Америки // Труды МАИ. 2017. № 94. URL: http://trudymai.ru/published.php?ID=80936

  14. Rohde S. Link quality dependent mobility strategies for distributed aerial sensor networks // GLOBECOM Workshops (GC Wkshps), Dortmund, Germany, 2010 IEEE, pp. 1783 –1787.

  15. Sahingoz O.K. Networking Models in Flying Ad-Hoc Networks (FANETs): Concepts and Challenges // Journal of Intelligent & Robotic Systems. 2014. Vol. 74, no. 1–2, pp. 513 – 527.

  16. Зенкевич С.Л., Болотин Е.И. О планировании в мультиагентных системах, использующих методы искусственного интеллекта. // Мехатроника, автоматизация, управление. 2014. № 11. С. 21 – 27.

  17. Зенкевич С.Л., Галустян Н.К. Децентрализованное управление группой квадрокоптеров // Мехатроника, автоматизация, управление. 2016. Т. 17. № 11. C. 774 –782.

  18. Kothari M., Postlethwaite I., Gu D., Multi-UAV path planning in obstacle rich environments using rapidly-exploring random trees // Proc. Of the combined 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, December 16-18, 2009, Shanghai P.R. China, pp. 3069 – 3074.

  19. He P., Dai S. Stealth Real-time Paths Planning for Heterogeneous UAV Formation Based on Parallel Niche Genetic Algorithm // Journal of Computational Information Systems, 2014, pp. 6731–6740.

  20. Hassanzadeh R., Mahdavi I., Mahdavi-Amiri N., Tajdin A. A genetic algorithm for solving fuzzy shortest path problems with mixed fuzzy arc lengths // Mathematical and Computer Modelling. 2013. no. 7 (1), pp. 84–99.

  21. Sharma Y., Saini S.C., Bhandhari M. Comparison of Dijkstra’s Shortest Path Algorithm with Genetic Algorithm for Static and Dynamic Routing Network // International Journal of Electronics and Computer Science Engineering, ISSN-2277-1956/V1N2. 2012, pp. 416-425.

  22. Zhu X., Luo W., Zhu T. An Improved Genetic Algorithm for Dynamic Shortest Path Problems // IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp 2093-2100.

  23. Wagner M., Neumann F. Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING // IEEE Congress on Evolutionary Computation (CEC). Beijing. China. 2014. pp. 125-133.

  24. Kim J.W., Kim S.K. Fitness switching genetic algorithm for solving combinatorial optimization problems with rare feasible solutions // The Journal of Supercomputing. September 2016. Vol. 72. Issue 9, pp. 3549–3571.

  25. Иглин С.П. Математические расчеты на базе MATLAB. – СПб.: БХВ-Петербург, 2005. – 640 с.

  26. Лиго Т., Фомичев А.В. Планирование пространственного маршрута полета беспилотного летательного аппарата с использованием методов частично целочисленного линейного программирования // Вестник МГТУ им. Н.Э. Баумана. Серия: Приборостроение. 2016. № 2. С. 53-66.

  27. Моисеев Д.В., Чинь Ван Минь Вычислительные аспекты и прикладное программное обеспечение оптимальной маршрутизации полета легкого беспилотного летательного аппарата в поле постоянного ветра // Интернет-журнал Науковедение. 2017. Т. 9. № 3. URL: http://naukovedenie.ru/PDF/102TVN317.pdf

  28. Zadeh S.M., Powers D., Sammut K. Optimal Route Planning with Prioritized Task Scheduling for AUV Missions Article, University, Adelaide, SA 5042, Australia, 2016. pp. 1–8. URL: https://www.researchgate.net/publication/301816813. pdf


Скачать статью

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2024

 Вход