# Path Planning of a Mobile Robot Based on the Improved RRT Algorithm
## 3 Methods
### APS-RRT Planner
#### 3.1.2 Adjustable Sampling Area Strategy  
The RRT algorithm draws samples using the uniform sampling strategy. This process is random and inefficient, leading the algorithm to sample in some useless areas. Moreover, the states in these areas have no effect on the final path, so this sampling strategy not only wastes time but also increases memory usage. To avoid such situations, it is hoped that the sampling nodes are distributed in the promising region where the solutions may exist as much as possible, which means that feasible solutions can be found more quickly. Considering that the RRT algorithm is a single-query incremental method, the configuration space is divided into three level areas, the _StartingArea_, the _MiddleArea_, and the _TargetArea_, according to the positions of the initial state and the target state. For brevity and clarity, _StartingArea_, _MiddleArea_, and _TargetArea_ are denoted as \(S\), \(M\) and \(T\), respectively. These areas are calculated using Equations (3)-(5), and each area can be treated as a state set, where \(\tau_{i}\) (\(i=\) 1, 2, 3, 4) are hyperparameters that represent the boundary of each set. It should be noted that \(T\subset M\subset S\). \[\textit{StartingArea}=\{x|x(x,y)\in Map\} \tag{3}\]  
\[\textit{MiddleArea}=\{x|\tau_{1}\leq x(x,y)\leq\tau_{2}\} \tag{4}\]\[TargetArea=\{x|\tau_{3}\leq x(x,y)\leq\tau_{4}\} \tag{5}\]  
Area \(S\) equals the global space, where the planner samples the whole space, similarly to the basic RRT algorithm, in the area \(S\). The new state \(x_{new}\) is used to check the growth status of the search tree. When \(x_{new}\in S\backslash M\), the search tree is currently in area \(S\) (line 1-2 in Algorithm 5). When the search tree arrives at area \(M\), where \(x_{new}\in M\backslash T\), the sampling area is reduced from \(S\) to \(M\). At this time, the planner only draws samples in area \(M\). In other words, the samples are not generated from area \(S\backslash M\) (line 3-4 in Algorithm 5). When the search tree reaches area \(T\), where \(x_{new}\in T\), the sampling area is reduced from \(M\) to \(T\), and the tree searches for the target state in area \(T\) (line 5-7 in Algorithm 5). _flag_ is a query variable that has three possible values, 0, 1, and 2, which are used to indicate that the search tree is currently in area \(S\), \(M\), or \(T\), respectively. When the value of _flag_ equals 2, the \(AS\) strategy will no longer be executed. By gradually reducing the sampling area, the planner can avoid undertaking unnecessary explorations in unimportant regions, thus improving the planner's speed. ```
Input: \(x_{new}\), Map Output: Map, flag
1: if\(x_{new}\in S\backslash M\) then
2: Map \(\gets S\), flag \(\gets 0\)
3: else if \(x_{new}\in M\backslash T\) then
4: Map \(\gets M\), flag \(\gets 1\)
5: else
6: Map \(\gets T\), flag \(\gets 2\)
7: end
```  
**Algorithm 5**\(AS\)  
To prevent the algorithm from failing to find a solution due to the limited sampling area strategy, the area's sampling times are set. If the random tree cannot enter the next area or find the target state within the specified times, the planner is considered to be stuck in a local minimum. At this time, the planner goes to the difference space between the current sampling area and the global sampling area and samples there several times using the FailSample function. The uniform sampling strategy is performed in the FailSample function (line 16-18 in Algorithm 3). It should be noted that, if the planner cannot meet the conditions in area \(S\), the FailSample function is conducted there. After that, the algorithm moves back to the current area to perform several samplings. If the conditions are still not met, the above operations are repeated until they are. Therefore, the improved algorithm can be guaranteed to achieve probabilistically completeness. An example is shown in Figure 3. When states \(x_{1}\) and \(x_{2}\) are added to the tree, this indicates that the search tree has reached areas \(M\) and \(T\), respectively.