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

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

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

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

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

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

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

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

Еще

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

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

IDR: 147243212   |   УДК: 007.52:629.3.05   |   DOI: 10.14529/mmph240203

Simulation of swarm algorithms for path planning in a two-dimensional non-mapped environment

This paper examines the effectiveness of swarm path planning algorithms in a two-dimensional unmapped environment. The efficiency criteria are the number of iterations in the path finding process and an assessment of the probability of successfully achieving the goal. During the study, the maximum speed of movement of the swarm and the maximum number of iterations during which it is allowed that the distance to the target does not decrease are changed. It is assumed that each particle can determine the state of the environment in a certain local region. By determining the state we mean determining the presence of an obstacle in a cell of the environment. To solve the problem of local minima, it is proposed to introduce a virtual obstacle at the local minimum point. This approach is generally known. The novelty of this approach lies in the fact that it solves the problem of detecting a local minimum by a swarm of particles. With a single movement, detecting a local minimum is trivial and comes down to checking the movement to previously visited cells. In the group case, a new solution to the problem of detecting a local minimum is required. This article provides a review and analysis of the path planning problem, problem formulation, problem statement, mathematical description of global swarm path planning algorithms with proposed modifications, pseudo-codes of planning algorithms and the results of a numerical study. In the course of numerical studies, the paper presents the criteria for the efficiency of path planning in an environment of 100 100 cells with randomly placed obstacles.

Еще

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

  • Казаков, К.А. Обзор современных методов планирования движения / К.А. Казаков, В.А. Семенов // Труды ИСП РАН. – 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