# RJ-RRT: Improved RRT for Path Planning in Narrow Passages
## 1 Introduction  
With the rising use of applications such as unmanned aerial vehicles (UAV), autonomous driving, and mobile robots, path planning as an essential part of their technology have long been a research hotspot of scholars [1, 2]. The main task of path planning is to find an optimal or sub-optimal path from the initial configuration to the goal configuration in the configuration space according to specific performance criteria, such as path length, planning time, and whether the vehicle kinematics are satisfied. Among many types of algorithms, the graph-based search method represented by A* [3] and [PERSON]'s algorithm [4] divides the configuration space mapped from the real environment into multiple grids according to the size of the resolution and then uses the graph search method to find feasible paths. The resolution size has a decisive impact on this type of algorithm's performance. An overly complex and sizeable real environment often causes an exponential increase in computing time and memory usage [5]. As another important class of planning algorithms, sampling-based planning algorithms, represented by RRT [6] and Probabilistic Road Map (PRM) [7], simplify the configuration space by random sampling. Therefore, they do not require complex geometric modelling and perform better in high dimensions or large environments. Probabilistic completeness guarantees that if at least one feasible path exists, the probability of this class of methods finding the path will be 1 [8, 9]. Although sampling-based methods have many advantages for path planning, the performance of such algorithms still has challenges when the configuration space contains multiple narrow passages [10, 11]. As a single-query, RRT plans a path by constructing a random tree extending from the initial configuration to the goal configuration by continuousrandom sampling. As a multi-query, the PRM needs to generate several random sampling points at the preprocess stage and then connect these points to each other to form a connectivity graph, thus capturing the configuration space's connectivity. Due to the special property of random sampling, both RRT and PRM are affected by the volume limitation of free space in the random sampling process. Specifically, the branches generated when RRT constructs a random tree are almost impossible to expand in narrow passages, and PRM is difficult to generate random sampling points in the collision-free configuration space with small volumes, thus affecting the construction of connected graphs. To solve the problem that the sample-based algorithm has insufficient planning ability for narrow passages, scholars have given many solutions. For PRM, in [12], the author proposes an extended-retract map that makes the sampling points all fall on the central axis of free space. In [13], the author proposed a strategy based on Gaussian sampling. This strategy will increase the sampling points located at the boundary between the obstacle and the free space and eventually generate many sampling points around the obstacle. However, it is not considered that the sampling point is around the obstacle but not necessarily inside the narrow passage. In [14], the author proposes a bridge connection test method to detect narrow passages. In this method, a bridge is built by sampling points located on two different obstacles. If the midpoint of the bridge is in free space, it means that it has passed the bridge test. Obviously, narrow passages make it easier to build such bridges. In [15], the author uses an artificial potential field to make the sampling point located on the obstacle move to free space under the action of repulsive force. In [16], the authors coordinately map both the obstacle space and the free space at the same time, increasing the connectivity of the graph inversely through failed connections. For RRT, since RRT is more goal-oriented than PRM, it is planning a path while constructing a tree, which makes the improvement of RRT have greater potential.