Kinematic Constrained RRT Algorithm with Post Waypoint Shift for the Shortest Path Planning of Wheeled Mobile Robots

Abstract

This paper presents a rapidly exploring random tree (RRT) algorithm with an effective post waypoint shift, which is suitable for the path planning of a wheeled mobile robot under kinematic constraints. In the growth of the exploring tree, the nearest node that satisfies the kinematic constraints is selected as the parent node. Once the distance between the new node and the target is within a certain threshold, the tree growth stops and a target connection based on minimum turning radius arc is proposed to generate an initial complete random path. The most significant difference from traditional RRT-based methods is that the proposed method optimizes the path based on Dubins curves through a post waypoint shift after a random path is generated, rather than through parent node selection and rewiring during the exploring tree growth. Then, it is proved that the method can obtain an optimal path in terms of the shortest length. The optimized path has good convergence and almost does not depend on the state of the initial random path. The comparative test results show that the proposed method has significant advantages over traditional RRT-based methods in terms of the sampling point number, the tree node number, and the path node number. Subsequently, an efficient method is further proposed to avoid unknown obstacles, which utilizes the original path information and thus effectively improves the new path planning efficiency. Simulations and real-world tests are carried out to demonstrate the effectiveness of this method.

Keywords

• rapidly exploring random tree
• kinematic constraints
• wheeled mobile robots
• post waypoint shift
• shortest path planning