Алгоритмы планирования траекторий в двумерной среде с препятствиями
Ключевые слова:
мобильный робот, планирование движения, управление движением, движение робота, планирование путиАннотация
В данной статье предложены алгоритмы планирования и управления движением мобильного робота в двухмерной стационарной среде с препятствиями. Задача состоит в том, чтобы сократить длину запланированного пути, учесть динамические ограничения робота и получить плавную траекторию. Для учета динамических ограничений мобильного робота на карту добавляются виртуальные препятствия, перекрывающие невыполнимые участки движения. Такой способ учета динамических ограничений позволяет использовать картографические методы без увеличения их сложности. В качестве алгоритма глобального планирования используется модифицированная версия алгоритма быстрого исследования случайных деревьев (Multi parent nodes RRT – MPN-RRT). В этом алгоритме, в отличие от оригинальной версии, используется несколько родительских узлов, что уменьшает длину запланированной траектории по сравнению с исходной версией RRT с одним узлом. Кратчайший путь на построенном графе находится с помощью алгоритма оптимизации муравьиной колонии. Методами численного моделирования показано, что использование двух родительских узлов позволяет уменьшить среднюю длину пути для городской среды с низкой плотностью застройки. Для решения проблемы медленной сходимости алгоритмов, основанных на случайном поиске и сглаживании путей, алгоритм RRT дополнен алгоритмом локальной оптимизации. Алгоритм RRT ищет глобальный путь, который сглаживается и оптимизируется итеративным локальным алгоритмом. Алгоритмы управления нижнего уровня, разработанные в этой статье, автоматически уменьшают скорость робота при приближении к препятствиям или повороте. Общая эффективность разработанных алгоритмов продемонстрирована методами численного моделирования с использованием большого количества экспериментов.
Литература
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.
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.
Опубликован
2022-05-30
Как цитировать
Пшихопов, В. Х., Медведев, М. Ю., Костюков, В. А., Хуссейн, Ф., & Кадим, А. (2022). Алгоритмы планирования траекторий в двумерной среде с препятствиями. Информатика и автоматизация, 21(3), 459-492. https://doi.org/10.15622/ia.21.3.1
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) Михаил Юрьевич Медведев, Пшихопов Вячеслав Хасанович
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).