Speed of Performance of a Group of Controlled Objects

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

The problem of the speed of performance (speed, performance) of a group of controlled objects is considered, the initial state of each of which is given, and the final state is selected from a fixed set of possible terminal states (targets). For each object, it is required to assign a target and find the control that ensures that the group simultaneously reaches all the selected targets in the shortest time. Since the speed-optimal controls of individual objects do not solve the problem of group speed, the so-called minimally delayed trajectories are used. A technique for solving the problem is developed, which includes an algorithm for solving the minimax assignment problem and a procedure for using the optimal and minimally delayed trajectories. The problem of the speed of a group of objects, whose planar motion is represented by Markov–Dubins trajectories, is solved.

About the authors

A. S. Bortakovskii

Moscow Aviation Institute (National Research University), 125080, Moscow, Russia; National University of Science and Technology (MISiS), 119049, Moscow, Russia

Author for correspondence.
Email: asbortakov@mail.ru
Россия, Москва; Россия, Москва

References

  1. Каляев И.А., Гайдук А.Р., Капустян С.Г. Модели и алгоритмы коллективного управления в группах роботов. М.: Физматлит, 2009.
  2. Куржанский А.Б. Задача управления групповым движением. Общие соотношения // Докл. РАН. 2009. Т. 426. № 1. С. 20–25.
  3. Габасов Р., Дмитрук Н.М., Кириллова Ф.М. Оптимальное децентрализованное управление группой динамических объектов // ЖВМ и МФ. 2008. Т. 48. № 4. С. 593–600.
  4. Евдокименков В.Н., Красильщиков М.Н., Оркин С.Д. Управление смешанными группами пилотируемых и беспилотных летательных аппаратов в условиях единого информационно-управляющего поля. М.: Изд-во МАИ, 2015.
  5. Гончаренко В.И., Желтов С.Ю., Князь В.А., Лебедевa Г.Н., Михайлинa Д.А., Царева О.Ю. Интеллектуальная система планирования групповых действий беспилотных летательных аппаратов при наблюдении наземных мобильных объектов на заданной территории // Изв. РАН. ТиСУ. 2021. № 3. С. 39–56.
  6. Tsourdos A., White B., Shanmugavel M. Cooperative Path Planning of Unmanned Aerial Vehicles. N. Y.: Wiley&Sons, 2011.
  7. Jia Zeng, Xiaoke Yang, Lingyu Yang, Gongzhang Shen. Modeling for UAV Resource Scheduling Under Mission Synchronization // J. Systems Engineering and Electronics. 2010. V. 21. № 5. P. 821–826.
  8. Babel L. Coordinated Target Assignment and UAV Path Planning with Timing Constraints // J. Intelligent & Robotic Systems. 2019. V. 94 (3–4). P. 857–869.
  9. Бортаковский А.С., Щелчков К.А. Задачи группового быстродействия летательных аппаратов // Тр. МАИ. 2018. № 99. http://mai.ru//upload/iblock/33c/Bortakovskiy_ SHCHelchkov_rus.pdf.
  10. Poudel S., Moh S. Task Assignment Algorithms for Unmanned Aerial Vehicle Networks: A Comprehensive Survey // Vehicular Communications. 2022. V. 35. P. 100469.
  11. Бузиков М.Э., Галяев А.А. Перехват подвижной цели машиной Дубинса за кратчайшее время // АиТ. 2021. № 5. С. 3–19.
  12. Галяев А.А., Рубинович Е.Я. Планирование движения подвижных объектов в конфликтной среде // Аналитическая механика, устойчивость и управление: Тр. XI Междунар. Четаевской конф. (пленарные доклады). Казань: Изд-во КНИТУ-КАИ, 2017. С. 71–90.
  13. Mohsan S.A.H., Othman N.Q.H., Li Y. et al. Unmanned Aerial Vehicles (UAVs): Practical Aspects, Fpplications, Open Challenges, Security Issues, and Future Trends. Intel Serv Robotics. 2023. V. 16. P. 109–137.
  14. Марков А.А. Несколько примеров решения особого рода задач о наибольших и наименьших величинах // Сообщения Харьк. мат. общества. Сер. 2. Т. I. 1889. С. 250–276.
  15. Dubins L.E. On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents // American. Mathematics. 1957. V. 79. № 3. P. 497–516.
  16. Isaacs R. Games of Pursuit // Scientific Report of the RAND Corporation. Santa Monica, 1951.
  17. Бортаковский А.С. Оптимальные по быстродействию траектории плоского движения с неограниченной кривизной // Изв. РАН. ТиСУ. 2022. № 4. С. 38–48.
  18. Пацко В.С., Федотов А.А. Трехмерное множество достижимости для машины Дубинса: сведение общего случая ограничений на повороты к каноническому // Изв. РАН. ТиСУ. 2023. № 4. С. 25–49.
  19. Диниц Е.А. О решении двух задач о назначении // Исследования по дискретной оптимизации. М.: Наука, 1976. С. 333–348.
  20. Глебов Н.И. Об одном обобщении минимаксной задачи о назначениях // Дискретн. анализ и исслед. операций. 2004. Т. 11. Вып. 4. С. 36–43.
  21. Серая О.В. Минимаксная задача назначения // Восточно-Европейский журнал передовых технологий. 2009. Т. 3. № 3(39). С. 8–11.
  22. Fulkerson D.R., Glicksberg I., Gross O. A Production Line Assignment Problem. Tech. Rep. RM-1102, The Rand Corporation. Santa Monica. CA, 1953.
  23. Burkard R., Dell’Amico M., Martello S. Assignment Problems: Revised Reprint. Siam, 2012. T. 125.
  24. Gottlieb Y.; Shima T. UAVs Task and Motion Planning in the Presence of Obstacles and Prioritized Targets // Sensors. 2015. V. 15. P. 29734–29764. https://doi.org/10.3390/s151129734
  25. Zhu X., Peng R. Optimal Routing, Aborting and Hitting Strategies of UAVs Executing Hitting the Targets Considering the Defense Range of Targets // Reliability Engineering and System Safety. 2021. V. 215. P. 107811.
  26. Кофман А., Анри-Лабордер А. Методы и модели исследования оптимизации. Целочисленное программирование. М.: Мир, 1976.
  27. Garfinkel R. An Improved Algorithm for the Bottleneck Assignment Problem // Oper. Res. 1971. V. 19. P. 1747–1751.
  28. Derigs U., Zimmermann U. An Augmenting Path Method for Solving Linear Bottleneck Assignment Problems // Computing. 1978. V. 19. P. 285–295.
  29. Федоренко Р.П. Приближенное решение задач оптимального управления. М.: Наука, 1978.
  30. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002.
  31. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. М.: Физматгиз, 1961.
  32. Грачев Н.И., Евтушенко Ю.Г. Библиотека программ для решения задач оптимального управления // ЖВМ и МФ. 1979. Т.10. № 2. С. 367−387.
  33. Cockayne E.J., Hall G.W.C. Plane Motion of a Particle Subject to Curvature Constraints // SIAM J. Control and Optimization. 1975. V. 13. № 1. P. 197−220.
  34. Ли Э.Б., Маркус Л. Основы теории оптимального управления. М.: Наука, 1972.
  35. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.: Наука, 1974.
  36. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
  37. Кларк Ф. Оптимизация и негладкий анализ. М.: Наука, 1988.

Supplementary files


Copyright (c) 2023 А.С. Бортаковский