|
DOI: 10.14489/vkit.2019.02.pp.003-012
Лебедев Г. Н., Гончаренко В. И., Царева О. Ю., Михайлин Д. А.
ВЫБОР МНОЖЕСТВА ПРИОРИТЕТНЫХ НАЗЕМНЫХ ОБЪЕКТОВ НАБЛЮДЕНИЯ С ПОМОЩЬЮ БЕСПИЛОТНЫХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ И МАРШРУТИЗАЦИЯ ИХ ПОЛЕТА
(c. 3-12)
Аннотация. Решена первоначальная задача выбора множества наиболее важных наземных объектов наблюдения, которые должны попасть в план полета беспилотных летательных аппаратов. Приведен метод формирования множества приоритетных тов наблюдения с помощью динамического программирования, учитывающий переменную важность объектов наблюдения и время отсутствия контроля над объектами наблюдения. Получена формула вычисления динамического приоритета. На этапе планирования сформировано несколько субоптимальных маршрутов с использованием частных двухпараметрических критериев, образующих «элиту». Выполнены операции скрещивания и мутации рассматриваемых маршрутов. Приведены результаты исследований работы генетических алгоритмов при решении задачи маршрутизации полета летательного аппарата с учетом заданных ограничений в первую очередь при наличии главного требования о соблюдении заданного графика наблюдения мобильных объектов в нужном месте. Рассмотрены случаи одно- и многокритериальной реализаций генетического алгоритма. Показано, что благодаря высокой производительности современных бортовых вычислительных машин, реализация сложных алгоритмов маршрутизации при наблюдении наземных объектов с учетом заданного графика полета не вызывает трудностей. На основании результатов моделирования работы алгоритмов проведен сравнительный анализ эффективности их работы.
Ключевые слова: объекты наблюдения; беспилотные летательные аппараты; генетические алгоритмы; многокритериальная оптимизация.
Lebedev G. N., Goncharenko V. I., Tsareva O. Yu., Mikhailin D. A.
CHOOSING A VARIETY OF PRIORITY SURFACE OBSERVATION OBJECTS WITH THE HELP OF UNMANNED AERIAL VEHICLES AND ROUTING THEIR FLIGHT
(pp. 3-12)
Abstract. The work solves the initial selection task of plurality of the most important ground objects observed, which should be included in flight plan of an unmanned aerial vehicles. A method for generating a set of priority observing objects using dynamic programming is given, taking into account the variable importance of observation objects and the time when there is no control over objects of observation. The formula for calculating the dynamic priority is obtained. Then, at the beginning of the subsequent planning stage several of suboptimal routs with using particular two-parameter criterions, forming “elite”, is formed. And then the “crossing” and “mutation” operations of these routes are used. There are quoted the researches results of genetic algorithms work in the task routing solution of flight an aerial vehicle with an allowance for predetermined constraints. Primarily, the presence of the main requirement of predetermined schedule adherence of mobile objects observation in the right spot are taken into consideration. Onecriterion and multicriterion realization of genetic algorithm cases are regarded. The work demonstrates that realization of complicate algorithms of routing in the observation of ground objects adjusted for defined flight schedule does not cause difficulties through high performances of modern airborne computers. Based on the simulation results of the algorithms work, a benchmark analysis of their work efficiency is carried out.
Keywords: Observed objects; Unmanned aerial vehicles; Genetic algorithms; Multi-criterion optimization.
Г. Н. Лебедев, В. И. Гончаренко, О. Ю. Царева (Московский авиационный институт (национальный исследовательский университет), Москва, Россия)
Д. А. Михайлин (Московский авиационный институт (национальный исследовательский университет); ФГБУ «Главный научно-исследовательский испытательный центр робототехники» Министерства обороны РФ, Москва, Россия) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
G. N. Lebedev, V. I. Goncharenko, O. Yu. Tsareva (Moscow Aviation Institute (National Research University), Moscow, Russia)
D. A. Mikhailin (Моscow Aviation Institute (National Research University); Central Research Institute of Robotic of the Ministry of Defence of the Russian Federation, Moscow, Russia) E-mail:
Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript
1. Лебедев Г. Н., Ефимов А. В., Мирзоян Л. А. Метод маршрутизации облета неподвижных объектов при мониторинге наземной обстановки на основе динамического программирования // Мехатроника, автоматизация, управление. 2012. № 1. С. 63 – 70.
2. Лебедев Г. Н, Гончаренко В. И., Румакина А. В. Модификация метода ветвей и границ для двумерной маршрутизации координированного полета группы летательных аппаратов // Мехатроника, автоматизация, управление. 2016. Т. 17, № 11. С. 783 – 791. doi:10.17584/mau.17.783-791.
3. Левитин А. В. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы. Введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. М.: Вильямс, 2006. С. 189 – 195.
4. Нейросетевое планирование групповых действий ЛА при наблюдении заданной группы подвижных объектов / Г. Н. Лебедев и др. // Мехатроника, автоматизация, управление. 2009. № 11. С. 60 – 65.
5. Tsourdos A., White B. A., Shanmugavel M. Cooperative Path Planning of Unmanned Aerial Vehicles. John Wiley & Sons, 2011. 212 р. URL: http://bookre.org/ reader?file=1273237&pg=8 (дата обращения: 02.12.2018).
6. Aircraft Group Coordinated Flight Route Optimization Using Branch-and-Bound Procedure in Resolving the Problem of Environmental Monitoring / G. Lebedev et al. // ITM Web of Conf. 2017. V. 10, No. 01003. P. 1 – 3. doi: 10.1051/itmconf/20171001003
7. Царев Ф. Н. Совместное применение генетического программирования, конечных автоматов и искусственных нейронных сетей для построения системы управления беспилотным летательным аппаратом // Научно-технический вестник информационных технологий, механики и оптики. Автоматное программирование. 2008. № 53. С. 42 – 60.
8. Лебедев Г. Н., Малыгин В. Б., Михайлин Д. А. Постановка и решение задачи оперативной коррекции потоков прилета и вылета воздушных судов в районе аэродрома с помощью генетического алгоритма // Научный вестник Московского гос. техн. университета гражданской авиации. 2017. Т. 20, № 4. С. 8 – 17.
9. Аллилуева Н. В., Руденко Э. М. Математический метод расчета целевой функции на графах и решение задачи маршрутизации [Электронный ресурс] // Труды МАИ. 2017. Вып. № 96. URL: https://elibrary.ru/download/elibrary_30744421_17721688.pdf (дата обращения: 02.12.2018).
10. Optimal Route Planning with Prioritized Task Scheduling for AUV Missions / S. Mahmoudzadeh et al. University, Adelaide, SA 5042, Australia, 2016. P. 1 – 8. URL: https://www.researchgate.net/publication/301816813_ Optimal_Route_Planning_with_Prioritized_Task_Schedu-ling_for_AUV_Missions (дата обращения: 25.08.2018).
11. Darrah, M. A., Niland W. M., Stolarik B. M. Increasing UAV Task Assignment Performance Through Parallelized Genetic Algorithms // Proc. of AIAA Infotech@Aerospace 2007 Conference and Exhibit, Rohnert Park, CA, 2007. P. 1 – 10. URL: https://arc.aiaa.org/doi/ abs/10.2514/6.2007-2815 (дата обращения: 02.12.2018).
12. Wang F., Man Y., Man L. Intelligent Optimization Approach for the k Shortest Paths Problem Based on Genetic Algorithm // 10th Intern. Conf. on Natural Computation. 19 – 21 August, 2014, Xiamen, China, 2014. doi: 10.1109/ICNC.2014.6975838
13. Wagner M., Neumann F. Single- and MultiObjective Genetic Programming: New Runtime Results for SORTING / IEEE Congress on Evolutionary Computation (CEC). Beijing, China, 2014. P. 125 – 133.
14. Kim J. W., Kim S. K. Fitness Switching Genetic Algorithm for Solving Combinatorial Optimization Prob-lems with Rare Feasible Solutions // The Journal of Supercomputing. September 2016. V. 72, Is. 9. P. 3549 – 3571.
1. Lebedev G. N., Efimov A. V., Mirzoyan L. A. (2012). The method of routing the fly-around of fixed objects when monitoring the ground situation based on dynamic programming. Mekhatronika, avtomatizatsiya, upravlenie, (1), pp. 63-70. [in Russian language]
2. Lebedev G. N., Goncharenko V. I., Rumakina A. V. (2016). Modification of the branch and bound method for two-dimensional routing of coordinated flight of a group of aircraft. Mekhatronika, avtomatizatsiya, upravlenie, 17(11), pp. 783-791. [in Russian language]
3. Levitin A. V. (2006). Chapter 9. Greedy Methods: Dijkstra's Algorithm. Algorithms. Introduction to the development and analysis of the Algorithms, pp. 189-195. Moscow: Vil'yams. [in Russian language]
4. Lebedev G. N. et al. (2009). Neural network planning of group actions of aircraft in the observation of a given group of moving objects. Mekhatronika, avtomatizatsiya, upravlenie, (11), pp. 60-65. [in Russian language]
5. Tsourdos A., White B. A., Shanmugavel M. (2011). Cooperative Path Planning of Unmanned Aerial Vehicles. John Wiley & Sons. Available at: http://bookre.org/ reader?file=1273237&pg=8 (Accessed: 02.12.2018).
6. Lebedev G. N. et al. (2017). Aircraft Group Coordinated Flight Route Optimization Using Branch-and-Bound Procedure in Resolving the Problem of Environmental Monitoring. ITM Web of Conference, 10(01003), pp. 1-3. doi: 10.1051/itmconf/20171001003
7. Tsarev F. N. (2008). The combined use of genetic programming, finite automata and artificial neural networks to build a control system for unmanned aerial vehicle. Nauchno-tekhnicheskiy vestnik informatsionnyh tekhnologiy, mekhaniki i optiki. Avtomatnoe programmirovanie, 53, pp. 42-60. [in Russian language]
8. Lebedev G. N., Malygin V. B., Mihaylin D. A. (2017). Statement and solution of the problem of operational correction of the flow of arrival and departure of aircraft in the vicinity of the aerodrome using genetic algorithm. Nauchnyy vestnik Moskovskogo gosudar-stvennogo tekhnicheskogo universiteta grazhdanskoy aviatsii, 20(4), pp. 8-17. [in Russian language]
9. Allilueva N. V., Rudenko E. M. (2017). Mathematical method for calculating the objective function on graphs and solving the routing problem. Trudy MAI, 96. Available at: https://elibrary.ru/download/elibrary_ 30744421_17721688.pdf (Accessed: 02.12.2018)
10. Mahmoudzadeh S. et al. (2016). Optimal Route Planning with Prioritized Task Scheduling for AUV Missions, pp. 1-8. University, Adelaide, SA 5042, Australia. Available at: https://www.researchgate.net/publication/ 301816813_ Optimal_Route_Planning_with_Prioritized _Task_Scheduling_for_AUV_Missions (Accessed: 25.08.2018).
11. Darrah, M. A., Niland W. M., Stolarik B. M. (2007). Increasing UAV Task Assignment Performance through Parallelized Genetic Algorithms. Proceedings of AIAA Infotech@Aerospace 2007 Conference and Exhibit, Rohnert Park, CA, pp. 1-10. Available at: https://arc.aiaa.org/doi/ abs/10.2514/6.2007-2815 (Accessed: 02.12.2018).
12. Wang F., Man Y., Man L. (2014). Intelligent Optimization Approach for the k Shortest Paths Problem Based on Genetic Algorithm. 10th International Confer-ence on Natural Computation. 19-21 August, Xiamen, China. doi: 10.1109/ICNC.2014.6975838
13. Wagner M., Neumann F. (2014). Single- and Multi-Objective Genetic Programming: New Runtime Results for SORTING. IEEE Congress on Evolutionary Computation (CEC), pp. 125-133. Beijing, China.
14. Kim J. W., Kim S. K. (2016). Fitness Switching Genetic Algorithm for Solving Combinatorial Optimiza-tion Problems with Rare Feasible Solutions. The Journal of Supercomputing, 72(9), pp. 3549=3571.
Статью можно приобрести в электронном виде (PDF формат).
Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.
После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.
Для заказа скопируйте doi статьи:
10.14489/vkit.2019.02.pp.003-012
и заполните форму
Отправляя форму вы даете согласие на обработку персональных данных.
.
This article is available in electronic format (PDF).
The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.
After depositing your payment on our bank account we send you file of the article by e-mail.
To order articles please copy the article doi:
10.14489/vkit.2019.02.pp.003-012
and fill out the form
.
|
Current Issue
Разработка концепции и создание сайта - ООО «Издательский дом «СПЕКТР»