Численное моделирование роевого алгоритма планирования пути в двухмерной некартографированной среде

Численное моделирование роевого алгоритма планирования пути в двухмерной некартографированной среде

Автор: Костюков Владимир Александрович, Медведев Илья Михайлович, Медведев Михаил Юрьевич, Пшихопов Вячеслав Хасанович

Журнал: Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика @vestnik-susu-mmph

Рубрика: Математика

Статья в выпуске: 2 т.16, 2024 года.

Бесплатный доступ

Исследуется эффективность роевых алгоритмов планирования пути в двумерной некартографированной среде. В качестве критериев эффективности используется число итераций в процессе поиска пути и оценка вероятности успешного достижения цели. В ходе исследования изменяется максимальная скорость перемещения роя и максимальное число итераций, в течение которых допускается отсутствие уменьшения расстояния до цели. Предполагается, что каждая частица может определять состояние среды в некоторой локальной области. Под определением состояния имеется в виду определение наличия препятствия в ячейке среды. Для решения проблемы локальных минимумов предлагается вводить виртуальное препятствие в точке локального минимума. Данный подход в целом известен. Новизна этого подхода заключается в том, что решается задача обнаружения локального минимума роем частиц. При одиночном движении обнаружение локального минимума тривиально и сводится к проверке движения к ранее посещенным ячейкам. В групповом случае требуется новое решение задачи обнаружения локального минимума. В данной статье приводится обзор и анализ задачи планирования пути, формулировка проблемы, постановка задачи, математическое описание алгоритмов глобального роевого планирования пути с предложенными модификациями, псевдокоды алгоритмов планирования и результаты численного исследования. В ходе численных исследований определены критерии эффективности планирования пути в среде размером 100 100 ячеек со случайно размещаемыми препятствиями.

Еще

Роевые алгоритмы, двумерная среда, локальный минимум, виртуальные препятствия, локальный поиск, виртуальное препятствие

Короткий адрес: https://sciup.org/147243212

IDR: 147243212   |   DOI: 10.14529/mmph240203

Список литературы Численное моделирование роевого алгоритма планирования пути в двухмерной некартографированной среде

  • Казаков, К.А. Обзор современных методов планирования движения / К.А. Казаков, В.А. Семенов // Труды ИСП РАН. – 2016. – Т. 28, № 4. – С. 241–294.
  • Generalized Sampling-Based Motion Planners / S. Chakravorty, S. Kumar // IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). – 2011. – Vol. 41, no. 3. – P. 855–866.
  • Групповое управление подвижными объектами в неопределенных средах / Д.А. Белоглазов, А.Р. Гайдук, Е.Ю. Косенко. – М.: ФИЗМАТЛИТ, 2015. – 305 с.
  • Reynolds, C. Flocks, Herds, and Schools: A Distributed Behavioral Model / C. Reynolds // ACM SIGGRAPH Computer Graphics. – Vol. 21, Iss. 4. – P. 25–34.
  • Dorigo, M. Ant System: Optimization by a Colony of Cooperating Agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man, and Cybernetics-Part B. – 1996. – Vol. 26, no. 1. – P. 29–41.
  • Karaboga, D. An Idea Based On Honey Bee Swarm for Numerical Optimization. Technical Re-port-TR06 / D. Karaboga. – Erciyes University, Engineering Faculty, Computer Engineering Depart-ment, 2005.
  • Pomerleau, D.A. ALVINN: An Autonomous Land Vehicle in a Neural Network / D.A. Pomerleau // NeurIPS Proceedings. – 1988. – P. 305–313.
  • Гладков, Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. – М.: Физматлит, 2010. – 365 с.
  • Архитектура САПР распределенного искусственного интеллекта на основе самоорганизующихся нейрокогнитивных архитектур / З.В. Нагоев, З.А. Сундуков, И.А. Пшенокова, В.А. Де-нисенко // Известия Кабардино-Балкарского научного центра РАН. – 2020. – № 2(94). – С. 40–47.
  • Автономный синтез пространственных онтологий в системе принятия решений мобильного робота на основе самоорганизации мультиагентной нейрокогнитивной архитектуры / З.В. Нагоев, К.Ч. Бжихатлов, И.А. Пшенокова и др. // Известия Кабардино-Балкарского научного центра РАН. – 2020. – № 6 (98). – С. 68–79.
  • Разработка интеллектуальной интегрированной системы «умное поле» / З.В. Нагоев, В.М. Шуганов, А.У. Заммоев и др. // Известия ЮФУ. Технические науки. – 2022. – № 1 (225). – С. 81–91.
  • Классификация и условия применения алгоритмов автоматической онтологизации пространства состояний агента общего искусственного интеллекта под управлением нейрокогнитивной архитектуры / З.В. Нагоев, И.А. Пшенокова, М.И. Анчёков и др. // Известия Кабардино-Балкарского научного центра РАН. – 2023. – № 6 (116). – С. 210–225.
  • Формальная модель генома агента общего искусственного интеллекта на основе мультиа-гентных нейрокогнитивных архитектур / М.И. Анчёков, А.З. Апшев, К.Ч. Бжихатлов и др. // Известия Кабардино-Балкарского научного центра РАН. – 2023. – № 5 (115). – С. 11–24.
  • Нейросетевая система управления группой роботов в неопределенной двумерной среде / А.Р. Гайдук, О.В. Мартьянов, М.Ю. Медведев и др. // Мехатроника, автоматизация, управление. – 2020. – Т. 21, № 8. – С. 470–479.
  • End to End Learning for Self-Driving Cars / M. Bojarski, D.D. Testa, D. Dworakowski et al. // arXiv:1604.07316v1.
  • Off-Road Obstacle Avoidance through End-to-End Learning / Y. LeCun, U. Muller, J. Ben et al. // Part of Advances in Neural Information Processing Systems 18 (NIPS 2005). – P. 739–746.
  • Urban Driving with Conditional Imitation Learning / J. Hawke, R. Shen, C. Gurau et al. // 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France. – 2020. – P. 251–257.
  • Панкратов, И.А. Генетический алгоритм оптимизации затрат энергии на переориентацию плоскости орбиты космического аппарата / И.А. Панкратов // Мехатроника, Автоматизация, Управление. – 2022. – Т. 23, no. 5. – С. 256–262.
  • Elshamli, A. Genetic Algorithm for Dynamic Path Planning / A. Elshamli, H.A. Abdullah, S. Areibi // Canadian Conference on Electrical and Computer Engineering 2004 (IEEE Cat. No.04CH37513). Niagara Falls, ON, Canada. – 2004. – Vol. 2. – P. 677–680.
  • Планирование маршрутов полета БПЛА в задачах группового патрулирования протяженных территорий / А.Б. Филимонов, Н.Б. Филимонов, Т.К. Нгуен, К.Ф. Фам // Мехатроника, авто-матизация, управление. – 2023. – Т. 24, № 7. – С. 374–381.
  • Родзин, С.И. Современное состояние биоэвристик: классификация, бенчмаркинг, области применения / С.И. Родзин // Известия ЮФУ. Технические науки. – 2023. – № 2. – С. 280–298.
  • Masehian, E. A Multi-Objective PSO-based Algorithm for Robot Path Planning / E. Masehian, D. Sedighizadeh // 2010 IEEE International Conference on Industrial Technology, Via del Mar, Chile. – 2010. – P. 465–470.
  • Костюков, В.А. Алгоритм планирования пути в двухмерной среде с полигональными препятствиями на классе кусочно-ломаных траекторий / В.А. Костюков, М.Ю. Медведев, В.Х. Пшихопов // Известия ЮФУ. Технические науки. – 2023. – № 5(235). – С. 34–48.
  • Алгоритмы планирования траекторий в двумерной среде с препятствиями / В.Х. Пшихо-пов, М.Ю. Медведев, В.А. Костюков и др. // Информатика и автоматизация. – 2022. – Вып. 21(3). – С. 459–492.
  • Nandanwar, M. Implementation and Comparison between PSO and BAT Algorithms for Path Planning with Unknown Environment / M. Nandanwar, A. Nandanwar // International Journal of Latest Technology in Engineering, Management & Applied Science (IJLTEMAS). – 2017. – Vol. 6, Iss. 8S. – P. 67–72.
  • Shortest Path Planning Algorithm – A Particle Swarm Optimization (PSO) Approach / P.I. Adamu, J.T. Jegede, H.I. Okagbue, P.E. Oguntunde // Proceedings of the World Congress on Engi-neering 2018 Vol I, WCE 2018, July 4–6, 2018. – P. 19–24.
  • Nandanwar, M.K. Path Planning through BAT Algorithm in Complex Environments / M.K. Nandanwar, A.S. Zadagaonkar, D.A. Shukla // International Journal of Computer Science Trends and Technology (IJCST). – 2016. – Vol. 4, Iss. 1. – P. 79–86.
  • An Improved PSO-GWO Algorithm With Chaos and Adaptive Inertial Weight for Robot Path Planning / X. Cheng, J. Li, C. Zheng et al. // Front. Neurorobot. – 2021. – Vol. 15. – 770361.
  • Qu, Y. A Global Path Planning Algorithm for Fixed-wing UAVs / Y. Qu, Y. Zhang, Y. Zhang // J. Intell. Robot. Syst. – 2018. – Vol. 91. – P. 691–707.
  • Автономный подводный аппарат «Скат» для решения задач поиска и обнаружения заиленных объектов / В.Х. Пшихопов, С.Я. Суконкин, Д.Ш. Нагучев и др. // Известия ЮФУ. Технические науки. – 2010. – № 3(104). – С. 153–163.
  • Position-Trajectory Control System for Unmanned Robotic Airship / V.Kh. Pshikhopov, M.Yu. Medvedev, A.R Gaiduk. et al. // IFAC Proceedings Volumes. – 2014. – Vol. 47, Iss. 3. – P. 8953–8958.
  • A Real-Time Path Planning Algorithm for AUV in Unknown Underwater Environment Based on Combining PSO and Waypoint Guidance / Z. Yan, J. Li, Y. Wu, G. Zhang // Sensors. – 2018. – Vol. 19, Iss. 1. – P. 20.
  • Shin, J.J. UAV Path Planning under Dynamic Threats Using an Improved PSO Algorithm / J.J. Shin, H. Bang // International Journal of Aerospace Engineering. – 2020. – Article ID 8820284 (17 pages).
  • A 3D Path Planning Algorithm Based on PSO for Autonomous UAVs Navigation / A. Mirshamsi, S. Godio, A. Nobakhti // Bioinspired Optimization Methods and Their Applications. BIOMA 2020. Lecture Notes in Computer Science, Vol. 12438. – Springer, Cham, 2020.
  • Phung, M.D. Safety-Enhanced UAV Path Planning with Spherical Vector-Based Particle Swarm Optimization / M.D. Phung, Q.P. Ha // Applied Soft Computing. – 2021. – Vol. 107. – Article ID 107376.
  • Скобцов, Ю.А. Эволюционные вычисления / Ю.А. Скобцов, Д.В. Cперанский. – М.: Национальный Открытый Университет «ИНТУИТ», 2016. – Текст: электронный // ЭБС «Консультант студента»: [сайт]. – URL : https://www.studentlibrary.ru/book/intuit_406.html (дата обращения: 29.01.2024).
  • Костюков, В.А. Алгоритмы планирования сглаженных индивидуальных траекторий движения наземных роботов / В.А. Костюков, М.Ю. Медведев, В.Х. Пшихопов // Мехатроника, автоматизация, управление. – 2022. – Т. 23, № 11. – С. 585–595.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp