Trajectory Planning Algorithms in Two-Dimensional Environment with Obstacles
Keywords:
mobile robots, motion planning, path planning, motion control, robot motionAbstract
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.
References
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. А.Г. Сухарев, “Оптимальные стратегии поиска экстремума,” СССР. Вычислительная математика и математическая Computational физика, Т. 11(4), с. 910-924, 1971.
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. В.Х. Пшихопов, М.Ю. Медведев. “Групповое управление движением мобильных роботов в неопределенной среде с использованием неустойчивых режимов,” Труды СПИИРАН. 2018. Вып. 60. C. 39-63.
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.
Published
How to Cite
Section
Copyright (c) Михаил Юрьевич Медведев, Пшихопов Вячеслав Хасанович
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).