A global path-planning algorithm based on critical point diffusion binary tree for a planar mobile robot

• Autorzy: Yang Zhiyong , Wang Lipeng , Cao Zejun , Zhang Zhi , Xu Zhuang

Identyfikatory

DOI

10.24425/bpasts.2024.148834

• Języki publikacji: EN

Abstrakty

EN

A global path-planning algorithm for robots is proposed based on the critical-node diffusion binary tree (CDBT), which solves the problems of large memory consumption, long computing time, and many path inflection points of the traditional methods. First of all, the concept of Quad-connected, Tri-connected, Bi-connected nodes, and critical nodes are defined, and the mathematical models of diverse types of nodes are established. Second, the CDBT algorithm is proposed, in which different planning directions are determined due to the critical node as the diffusion object. Furthermore, the optimization indices of several types of nodes are evaluated in real-time. Third, a path optimization algorithm based on reverse searching is designed, in which the redundant nodes are eliminated, and the constraints of the robot are considered to provide the final optimized path. Finally, on one hand, the proposed algorithm is compared with the A* and RRT methods in the ROS system, in which four types of indicators in the eight maps are analysed. On the other hand, an experiment with an actual robot is conducted based on the proposed algorithm. The simulation and experiment verify that the new method can reduce the number of nodes in the path and the planning time and is suitable for the motion constraints of an actual robot.

Słowa kluczowe

EN

robot; global path; rapid planning; critical point; reverse optimization

PL

robot; punkt krytyczny; optymalizacja odwrotna; ściezka globalna; planowanie szybkie

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2024
• Tom: Vol. 72, nr 2
• Strony: art. no. e148834
• Opis fizyczny: Bibliogr 26 poz., rys., tab.

Twórcy

autor

Yang Zhiyong

• College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin, 150001, China

• https://orcid.org/0000-0003-4399-5557

autor

Wang Lipeng

• College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin, 150001, China

• https://orcid.org/0000-0002-7987-5947

autor

Cao Zejun

• College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin, 150001, China

autor

Zhang Zhi

• College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin, 150001, China

autor

Xu Zhuang

• College of Intelligent Systems Science and Engineering, Harbin Engineering University, Harbin, 150001, China

Bibliografia

• [1] W. Kowalczyk and K. Kozlowski, “Trajectory tracking and collision avoidance for the formation of two-wheeled mobile robots,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 67, no. 5, pp. 915–924, 2019.
• [2] U. Libal and J. Plaskonka, “Noise sensitivity of selected kinematic path following controllers for a unicycle,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 62, no. 1, pp. 3–13, 2014, doi: 10.2478/bpasts-2014-0001.
• [3] W. Chi, Z. Ding, and J. Wang, “A Generalized Voronoi Diagram-Based Efficient Heuristic Path Planning Method for RRTs in Mobile Robots,” IEEE Trans. Ind. Electron., vol. 69, no. 5, pp. 4926–4937, 2021, doi: 10.1109/TIE.2021.3078390.
• [4] J. Yang, C. Wang, and B. Jiang, “Visual perception enabled industry intelligence: state of the art, challenges and prospects,” IEEE Trans. Ind. Inform., vol. 17, no. 3, pp. 2204–2219, 2020, doi: 10.1109/TII.2020.2998818.
• [5] K. Shu, H. Yu, and X. Chen, “Autonomous driving at intersections: A behavior-oriented critical-turning-point approach for decision making,” IEEE-ASME Trans. Mechatron., vol. 27, no. 1, pp. 234–244, 2021, doi: 10.1109/TMECH.2021.3061772.
• [6] K. Wu, H. Wang, and M. A. Esfahani, “Achieving real-time path planning in unknown environments through deep neural networks,” IEEE Trans. Intell. Transp. Syst., vol. 23, no. 3, pp. 2093–2102, 2020, doi: 10.1109/TITS.2020.3031962.
• [7] Q. Wei, H. Li, and X.S. Yang, “Continuous-time distributed policy iteration for multicontroller nonlinear systems,” IEEE T. Cybern., vol. 51, no. 5, pp. 2372–2383, 2020, doi: 10.1109/TCYB.2020.2979614.
• [8] S. Zhao, L. Shi, and W. Zhang, “Global dynamic path-planning algorithm in gravity-aided inertial navigation system,” IET Signal Process., vol. 15, no. 80, pp. 510–520, 2021, doi: 10.1049/sil2.12056.
• [9] V. Venkatesan, J. Seymour, and D. J.Cappelleri, “Micro-assembly sequence and path planning using subassemblies,” J. Mech. Robot., vol. 10, no. 6, 2018, doi: 10.1115/1.4041333.
• [10] E. Çakır, Z. Ulukan, and T. Acarman, “Time-dependent Dijkstra’s algorithm under bipolar neutrosophic fuzzy environment,” J. Intell. Fuzzy Syst., vol. 42, no. 1, pp. 227–236, 2022, doi: 10.3233/JIFS-219188.
• [11] G. Dong, F. Yang, and K. L. Tsui, “Active Balancing of Lithium-Ion Batteries Using Graph Theory and A-Star Search Algorithm,” IEEE Trans. Ind. Inform., vol. 17, no. 4, pp. 2587–2599, 2021, doi: 10.1109/TII.2020.2997828.
• [12] P. Skačkauskas and E. Sokolovskij, “Analysis of the Hybrid Global Path Planning Algorithm for Different Environments,” Transp. Telecommun. J., vol. 20, no. 1, pp. 1–11, 2019, doi: 10.2478/ttj-2019-0001.
• [13] S. Kadry, G. Alferov, and V. Fedorov, “D-Star Algorithm Modification,” Int. J. Online Biomed. Eng., vol. 16, no. 8, pp. 108–113, 2020, doi: 10.3991/ijoe.v16i08.14243.
• [14] N. Ma, J. Wang, and J. Liu, “Conditional Generative Adversarial Networks for Optimal Path Planning,” IEEE Trans. Cogn. Dev. Syst., vol. 14, no. 2, pp. 662–671, 2022, doi: 10.1109/TCDS.2021.3063273.
• [15] X. Song, S. Gao, and C. B. Chen, “A New Hybrid Method in Global Dynamic Path Planning of Mobile Robot,” Int. J. Comput. Commun. Control, vol. 13, no. 6, pp. 1032–1046, 2022, doi: 10.15837/ijccc.2018.6.3153.
• [16] Y. Long, Z. Zuo, and Y. Su, “An A*-based bacterial foraging optimisation algorithm for global path planning of unmanned surface vehicles,” J. Navig., vol. 73, no. 6, pp. 1–16, 2020, doi: 10.1017/S0373463320000247.
• [17] I.S. Kim, W.K. Lee, and Y.D. Hong, “Simple global path planning algorithm using a ray-casting and tracking method,” J. Intell. Robot. Syst., vol. 90, no. 6, pp. 101–111, 2018, doi: 10.1007/s10846-017-0642-2.
• [18] K. Zhang, Y. Yang, andM. Fu, “Two-phase A*: A real-time global motion planning method for non-holonomic unmanned ground vehicles,” Proc. Inst. Mech. Eng. Part D-J. Automob. Eng., vol. 235, no. 4, pp. 1–16, 2021, doi: 10.1177/0954407020948397.
• [19] J. Zhang, Y. Xia, and G. Shen, “A novel learning-based global path planning algorithm for planetary rovers,” Neurocomputing, vol. 361, no. 1, pp. 69–76, 2019, doi: 10.1016/j.neucom.2019.05.075.
• [20] G. Xia, Z. Han, and B. Zhao, “Global path planning for unmanned surface vehicle based on improved quantum ant colony algorithm,” Math. Probl. Eng., vol. 7, pp. 1-10, 2019, doi: 10.1155/2019/2902170.
• [21] C. Huang and J. Fei, “UAV path planning based on particle swarm optimization with global best path competition,” Int. J. Pattern Recognit. Artif. Intell., vol. 32, no. 1, pp. 1–23, 2018, doi: 10.1142/S0218001418590085.
• [22] P.G. Luan, and N.T. Thinh, “Hybrid genetic algorithm based smooth global-path planning for a mobile robot,” Mech. Based Des. Struct. Mech., vol. 51, no. 3, pp. 1758–1774, 2023, doi: 10.1080/15397734.2021.1876569.
• [23] Z. Yu and L. Xiang, “NPQ-RRT: an improved RRT approach to hybrid path planning,” Complexity, vol. 2021, p. 6633878, 2021, doi: 10.1155/2021/6633878.
• [24] Q. Song, S. Li, and J. Yang, “Intelligent Optimization Algorithm-Based Path Planning for a Mobile Robot,” Comput. Intell. Neurosci., vol. 2021, p. 8025730, 2021, doi: 10.1155/2021/8025730.
• [25] J. Wang, Y. Luo, and X. Tan, “Path Planning for Automatic Guided Vehicles (AGVs) Fusing MH-RRT with Improved TEB,” Actuators, vol. 10, no. 12, p. 314, 2021, doi: 10.3390/act10120314.
• [26] D. Pazderski, ”Application of transverse functions to control differentially driven wheeled robots using velocity fields,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 64, no. 4, pp. 831–851, 2016, doi: 10.1515/bpasts-2016-0092.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).