# CERRT: A Mobile Robot Path Planning Algorithm Based on RRT in Complex Environments
## 1 Introduction  
Path planning is a crucial research field in the robotics industry. Its purpose is to find a safe, collision-free path for a mobile robot to traverse from its starting position to its destination in a specified area that contains obstacles [1]. It has widespread applications in complex environments such as urban roads, factory production lines, and outdoor exploration. Currently, path planning mainly uses algorithms based on search, heuristics, and sampling. Among them, sampling-based path planning algorithms have become a research hotspot due to their wide applicability, ease of implementation, and lack of need to construct complex structures [2]. In the class of sampling-based algorithms, the rapidly-exploring random tree (RRT) algorithm, which is widely used, can avoid complex space constructions by implementing a collision check module, making it suitable for solving high-dimensional or multi-constraint planning problems [3]. However, the efficiency of the RRT algorithm is typically affected when it faces complex environments such as multiple obstacles, mazes, narrow passages, and concave traps. In recent years many researchers have proposed improved RRT algorithms to address these issues. For instance, [PERSON] et al. propose a straightforward and efficient bidirectional random tree algorithm, denoted as RRT-Connect [4], alternately expands two trees to improve the algorithm's efficiency. However, its performance still suffers in complex environments. [PERSON] et al. introduced a rapid exploration algorithm named Rapid Random Vine (RRV) [5] for efficient exploration. It determines the local environment type using principal component analysis (PCA), a dimensionality reduction technique that captures the most significant variations in the data. By analyzingthe relationships among environmental features, RRV selects an appropriate direction in which to expand, thereby solving the narrow passage problem well. However, its performance is poor in complex environments without passages. [PERSON] et al. [6] augmented the Rapidly-Exploring Random Tree (RRT) algorithm with a bridge-testing technique, which increased the sampling probability in narrow passages and decreased the sampling probability in non-interest regions, thereby addressing narrow passage issues. However, the unevenness of the sampling probability may cause the algorithm to ignore some feasible paths. [PERSON] et al. proposed the Fast-RRT [7] algorithm, which detects narrow passages by re-randomizing the expansion direction at collision points, but the algorithm's stability is poor. [PERSON] et al. combined RRV with bridge testing [8], enabling efficient identification and expansion in complex environments without the need for additional collision detection, greatly reducing computational intensity, but the algorithm can generate a large number of useless vertices in open areas. Building upon RRV and RRT-Connect, [PERSON] et al. proposed an adaptive random tree algorithm called ARRT-Connect [9], which effectively improves the algorithm's performance, but the algorithm may fall into concave traps. [PERSON] et al. [10] introduce a heuristic path-planning algorithm based on the Generalized Voronoi Diagram (GVD), which significantly improves the algorithm's performance in maze environments but requires preprocessing of the map and does not consider the narrow passage problem. [PERSON] et al. proposed a Fuzzy Greedy Rapidly Exploring Random Tree (FG-RRT) [11] algorithm, which significantly reduces computation time in maze, narrow passage, and convex obstacle environments, but the algorithm requires the setting of nine fuzzy rules, and the parameter settings are complex. To address the problem of low-quality generated paths, the RRT* algorithm was introduced by [PERSON] et al. [12], which introduced the ChooseParent and Rewire processes when adding new nodes to the tree, making the algorithm asymptotically optimal. As the number of iterations tends to infinity, the probability of finding the optimal solution approaches 100%.