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

Abstract

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.