Trajectory Planning Algorithms in Two-Dimensional Environment with Obstacles

Мұқаба

Дәйексөз келтіру

Толық мәтін

Аннотация

This article proposes algorithms for planning and controlling the movement of a mobile robot in a two-dimensional stationary environment with obstacles. The task is to reduce the length of the planned path, take into account the dynamic constraints of the robot and obtain a smooth trajectory. To take into account the dynamic constraints of the mobile robot, virtual obstacles are added to the map to cover the unfeasible sectors of the movement. This way of accounting for dynamic constraints allows the use of map-oriented methods without increasing their complexity. An improved version of the rapidly exploring random tree algorithm (multi-parent nodes RRT – MPN-RRT) is proposed as a global planning algorithm. Several parent nodes decrease the length of the planned path in comprise with the original one-node version of RRT. The shortest path on the constructed graph is found using the ant colony optimization algorithm. It is shown that the use of two-parent nodes can reduce the average path length for an urban environment with a low building density. To solve the problem of slow convergence of algorithms based on random search and path smoothing, the RRT algorithm is supplemented with a local optimization algorithm. The RRT algorithm searches for a global path, which is smoothed and optimized by an iterative local algorithm. The lower-level control algorithms developed in this article automatically decrease the robot’s velocity when approaching obstacles or turning. The overall efficiency of the developed algorithms is demonstrated by numerical simulation methods using a large number of experiments.

Авторлар туралы

V. Pshikhopov

Southern Federal University (SFedU)

Хат алмасуға жауапты Автор.
Email: pshichop@rambler.ru
Shevchenko St. 2

M. Medvedev

Southern Federal University (SFedU)

Email: medvmihal@gmail.com
Shevchenko St. 2

V. Kostjukov

Southern Federal University (SFedU)

Email: wkost-einheit@yandex.ru
Shevchenko St. 2

F. Houssein

Southern Federal University (SFedU)

Email: info@sfedu.ru
Shevchenko St. 2

A. Kadhim

Technical Institute of Nasiriyah

Email: info@nust.edu.iq
Baghdad St. 26

Әдебиет тізімі

  1. K.A. Kazakov, V.A. Semenov, “Reviwes of moderm path planing methods,” Proceedings of ISP RAS, v. 28(4), 2016, pp. 241-294.
  2. Sánchez-Ibáñez, J.R.; Pérez-del-Pulgar, C.J.; García-Cerezo, A. Path Planning for Autonomous Mobile Robots: A Review. Sensors 2021, 21, 7898. https://doi.org/10.3390/s21237898
  3. L.E. Kavraki; P. Svestka; J.-C. Latombe; M.H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation, v. 12 (4), pp. 566-580, 1996.
  4. A.G. Sukharev, “Optimal strategies of the search for an extremum,” U.S.S.R. Computational Mathematics and Mathematical Physics, v. 11(4), pp. 910-924, 1971. Translated from Russian, Journal Vychisl. Mat. i Mat. Fiz.
  5. F. Samaniego, J. Sanchis, S. García-Nieto, R. Simarro. “Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs,” Electronics, v. 8 (3), 306, 2019.
  6. R. Toodesh, and S. Verhagen. "Adaptive, variable resolution grids for bathymetric applications using a quadtree approach," Journal of Applied Geodesy, v. 12(4), 2018, pp. 311-322.
  7. P.E. Hart, N.J. Nilsson, B.A. Raphael, “Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, v. 2, pp. 100 – 107, 1968.
  8. A. Stentz, “Optimal and efficient path planning for partially known environments,” In Intelligent Unmanned Ground Vehicles, Springer, Boston, MA, USA, 1997, pp. 203–220.
  9. Q. Wang, Y. Hao, F. Chen. “Deepening the IDA* algorithm for knowledge graph reasoning through neural network architecture,” Neurocomputing, v. 429, 2021, pp. 101-109.
  10. R. Zhou, E.A. Hansen, “Memory-Bounded {A*} Graph Search,” The Florida AI Research Society Conference - FLAIRS, pp. 203–209, 2002.
  11. R. Holte, M. Perez, R. Zimmer, A. MacDonald, “Hierarchical A*: Searching abstraction hierarchies efficiently,” Proceedings of the thirteenth national conference on Artificial intelligence, v. 1, pp. 530–535, 1996.
  12. B. Liu, X. Xiao and P. Stone, "A Lifelong Learning Approach to Mobile Robot Navigation," in IEEE Robotics and Automation Letters, v. 6(2), 2021, pp. 1090-1096.
  13. B.Y. Chen, X.-W. Chen, H.-P. Chen, W.H.K. Lam, “Efficient algorithm for finding k shortest paths based on re-optimization technique,” Transportation Research Part E: Logistics and Transportation Review, V. 133, 2020, Article number 101819.
  14. X. Zhang, B. Wylie, C. Oscar, C.A. Moore, “Time-Optimal and Collision-Free Path Planning for Dual-Manipulator 3D Printer,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020-October, 9283493, pp. 2389-2396.
  15. O. Khatib, “Real-Time Obstacles Avoidance for Manipulators and Mobile Robots,” International Journal of Robotics Research, vol. 5(2), pp. 90–98, 1986.
  16. V.Kh. Pshikhopov (Ed.), D. Beloglazov, V. Finaev, V. Guzik, E. Kosenko, V. Krukhmalev, M. Medvedev, V. Pereverzev, A. Pyavchenko, R. Saprykin, I. Shapovalov, V. Soloviev. Path Planning for Vehicles Operating in Uncertain 2D Environments, Elsevier, Butterworth-Heinemann, 2017. 312 p, ISBN: 9780128123058.
  17. S.S. Ge, Y.J. Cui, “New potential functions for mobile robot path planning,” IEEE Transactions on Robotics and Automation. v. 16 (5), pp. 615 – 620, 2000.
  18. A.C. Woods, H.M. La, “A Novel Potential Field Controller for Use on Aerial Robots,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, 49 (4), 7932539, pp. 665-676, 2019.
  19. Y. Koren, J. Borenstein, “Potential field methods and their inherent limitations for mobile robot navigation,” International Conference on Robotics and Automation v.2, pp. 1398 – 1404, 1991.
  20. V. Pshikhopov, M. Medvedev, “Group control of autonomous robots motion in uncertain environment via unstable modes,” SPIIRAS Proceedings. v. 60(5), pp. 39-63, 2018.
  21. Zhou, C., Huang, B. & Fränti, P. A review of motion planning algorithms for intelligent robots. Journal of Intelligent Manufacturing, 2021. https://doi.org/10.1007/s10845-021-01867-z.
  22. S. Chakravorty, S. Kumar, “Generalized Sampling-Based Motion Planners,” IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, vol. 41(3), 2011.
  23. A. Ravankar, Ab. Ravankar, T. Emaru, Y. Kobayashi, “HPPRM: Hybrid Potential Based Probabilistic Roadmap Algorithm for Improved Dynamic Path Planning of Mobile Robots,” IEEE Acsess, vol. 8, pp. 221743 – 221766, 2020.
  24. S.M. LaValle, J. Kuffner, “Randomized kinodynamic planning,” Int. Journal of Robotics Research, vol. 20(5), pp. 378–400, 2001.
  25. S.M. LaValle, J.J. Kuffner, “Rapidly-exploring random trees: Progress and prospects,” 2000 Workshop on the Algorithmic Foundations of Robotics, pp. 293–308, 2000.
  26. X. Wang, X. Li, Y. Guan, J. Song, R. Wang, “Bidirectional Potential Guided RRT* for Motion Planning,” IEEE Acsess, vol. 7, pp. 95046 – 95057, 2019.
  27. A. Qureshi, Y. Ayaz, “Potential functions based sampling heuristic for optimal path planning,” Autonomous Robot, vol. 40, pp 1079–1093, 2016.
  28. S. Karaman, E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” The International Journal of Robotics Research, 30(7), pp. 846–894, 2011.
  29. L. Chen, Y. Shan, W. Tian, B. Li, and D. Cao, “A Fast and Efficient Double-Tree RRT∗-Like Sampling-Based Planner Applying on Mobile Robotic Systems,” IEEE/ASME Transactions on Mechatronics, vol. 23(6), pp. 2568 – 2578, 2018.
  30. J. Wang, M.Q.-H. Meng, O. Khatib, “EB-RRT: Optimal Motion Planning for Mobile Robots,” IEEE Transactions on Automation Science and Engineering, v. 17(4), pp. 2063-2073, 2020.
  31. J. Janos, V. Vonasek, R. Penicka, “Multi-Goal Path Planning Using Multiple Random Trees,” IEEE Robotics and Automation Letter. v. 6(2), 2021, pp. 4201-4208.
  32. S.N. Spitz and A.A.G. Requicha, “Multiple-goals path planning for coordinate measuring machines,” in Proc. IEEE Int. Conf. Robot. Automat., vol. 3, 2000, pp. 2322–2327.
  33. D. Devaurs, T. Siméon, and J. Cortés, “A multi-tree extension of the transition-based RRT: Application to ordering-and-pathfinding problems in continuous cost spaces,” in Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst., 2014, pp. 2991–2996.
  34. V. Vonásek and R. Pˇeniˇcka, “Space-filling forest for multi-goal path planning,” inProc. 24th IEEE Int. Conf. Emerg. Technol. Factory Automat., 2019, pp. 1587–1590.
  35. R. Wang, X. Zhang, Y. Fang, B. Li, “Virtual-Goal-Guided RRT for Visual Servoing of Mobile Robots With FOV Constraint,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021.
  36. V. Kostjukov, V. Pshikhopov, M. Medvedev, “Optimization of mobile robot movement on a plane with finite number of repeller sources,” SPIIRAS Proceedings. v. 19(1), pp. 43-78, 2020.
  37. V. Kostjukov, M. Medvedev, V. Pshikhopov, “Method for Optimizing of Mobile Robot Trajectory in Repeller Sources Field,” Informatics and Automation. v. 20(3), pp. 690-726, 2021.
  38. V. Pshikhopov, M. Medvedev, “Multi-Loop Adaptive Control of Mobile Objects in Solving Trajectory Tracking Tasks,” Automation and Remote Control, v. 81(11), pp. 2078–2093, 2020.
  39. B.A. Güvenç, L. Güvenç, S. Karaman, “Robust Yaw Stability Controller Design and Hardware-in-the-Loop Testing for a Road Vehicle,” IEEE Transactions on Vehicular Technology, v. 58(2), pp. 555-571, 2009.
  40. M. Dorigo, L.M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, v. 1(1), pp. 53-66, 1997.
  41. J. H. Wilkinson, “The algebraic Eigenvalue Problem,” Oxford, Clarendon Press, 1965.
  42. W. Chen and J. Zhang, “An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS Requirements," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), v. 39(1), pp. 29-43, 2009.
  43. A.R. Gaiduk, O.V. Martjanov, M.Yu. Medvedev, V.Kh. Pshikhopov, N. Hamdan, A. Farhood, “Neural network based control system for robots group operating in 2-d uncertain environment,” Mekhatronika, Avtomatizatsiya, Upravlenie. v. 21(8), pp. 470 – 479, 2020.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».