Intelligent path planning by an improved RRT algorithm with dual grid map

• Published in: Alexandria engineering journal 2024-02, Vol.88, p.91-104
• Main Authors: Zhang, Rui, Guo, He, Andriukaitis, Darius, Li, Yongbo, Królczyk, Grzegorz, Li, Zhixiong
• Format: Article
• Language: English
• Subjects: A-star algorithm; Bezier curve; Bidirectional RRT; Grid map; Obstacle avoidance algorithm
• ISSN: 1110-0168
• DOI: 10.1016/j.aej.2023.12.044

This research addresses the limitations of existing autonomous vehicle path planning algorithms, notably their slow processing speeds and suboptimal route efficiency. We introduce an innovative path planning algorithm that synergizes the A* algorithm with the Rapidly-exploring Random Tree (RRT) approach. This hybrid model significantly enhances route timeliness and reliability, particularly in obstacle avoidance scenarios for driverless vehicles. Our methodology employs a 'two-level map' approach, where a lower-resolution grid map is derived from a high-resolution map. Utilizing the A* algorithm on this framework, we ascertain a preliminary 'coarse path' for the navigation target. The RRT algorithm, modified to reduce the traditional redundancy associated with random uniform sampling, is then applied for probabilistic sampling within this defined area. ovel aspect of our approach is the simultaneous generation of two trees, originating from both the start and end points, guided by a target-biased strategy and dual-direction theory. This method probabilistically expands towards the node of the opposite tree, thereby enhancing both the generation speed and trajectory viability. Further refinements are made through a pruning process, optimizing the path, and employing Bezier curves for smoothing, ensuring compliance with the dynamic constraints of Ackerman chassis vehicles. Comparative analysis in complex environments demonstrates the superiority of our proposed algorithm. It outperforms traditional methods with a 400 % increase in planning speed relative to the RRT-Connect algorithm, and a 30 % reduction in average path length. Additionally, the mean curvature of routes generated by our algorithm is 19 % lower than traditional routes, underscoring significant advancements in both the timeliness and viability of the planned routes.