# Progress in Construction Robot Path-Planning Algorithms: Review
## 3 Global Path-Planning Algorithms
### RRT Algorithm  
Rapidly Exploring Random Tree (RRT) is a sampling-based global algorithm with powerful global search capabilities. It explores space through random sampling and gradually builds a tree to find a path from the start to the goal. This method is particularly suitable for dealing with non-convex and high-dimensional search spaces. For example, RRT can help construction robots with robotic arms or humanoid robots quickly find a path to a target point. The algorithm starts by initializing a tree that includes the start point. It then randomly generates a target point within the search space. Next, it finds the node in the tree that is closest to the target point and attempts to connect it to the target point, thereby extending the tree towards this point. During the extension process, the algorithm checks whether the path from the current node to the target point intersects with obstacles. If an intersection is detected, resampling is performed. If the connection is successful, the target point is added to the tree. This cycle repeats until the goal is reached. See Figure 6.  
The RRT algorithm is characterized by its ability to quickly find a feasible path but not necessarily the optimal path [35]. [PERSON] and [PERSON] introduced a heuristic function to guide the selection of sampling points, reducing invalid sampling and thus improving search efficiency [36; 37]. [PERSON] implemented a two-way RRT method, where the algorithm draws samples from both the starting and ending points simultaneously, aiming to link the two trees  
Figure 6: Schematic diagram of the RRT algorithm. together in the center. This bidirectional extension significantly improves search coverage and speed, especially in high-dimensional spaces [38]. [PERSON] developed a modified version of the Rapidly Exploring Random Tree Star (RRT*) algorithm to establish an initial path and create a state tree structure. Furthermore, he introduced a rapid optimization technique for this initial path. This modified algorithm stands out from other static planning methods due to its ability to produce higher-quality initial paths, enhancing the effectiveness of path planning in various applications [39]. In a parallel effort, [PERSON] proposed a data-driven approach known as UPPHE, which incorporates the Feedback Rapidly Exploring Random Tree Star algorithm (FRRT*). This innovative method features a risk network with feedback modules, allowing it to leverage information derived from case data. By utilizing this data, FRRT* effectively constrains the expansion of the random tree and makes adjustments skewed towards optimizing planning efficiency, significantly enhancing the traditional RRT* approach [40]. [PERSON] recognized the unpredictable nature of tree growth in the original RRT* algorithm and sought to improve its performance by integrating the Attractive Potential Field (APF) method with RRT*. This combination refines the targeting of the sampling process, making it more focused. Additionally, in scenarios where RRT* encounters narrow channels or dense environments, [PERSON]'s approach employs adaptive step size adjustments facilitated by fuzzy control mechanisms, enhancing search efficiency in challenging areas [41]. [PERSON] introduced a refined sampling and tree growth mechanism that concentrates on the forward area near the target point during the sampling and growth phases. By restricting the sampling and tree development to this region, the method significantly accelerates the path-planning process, offering a more efficient solution to navigation problems in complex environments [42]. [PERSON] introduced an enhanced RRT-Connect algorithm for mobile robot path-planning, generating a third node within the space to allow for the algorithm to greedily expand with a quadtree [43]. [PERSON] proposed a sparse sampling mechanism to improve global search efficiency by reducing redundant sampling. Additionally, [PERSON] proposed a dynamic target bias strategy that provides directional guidance for the expansion of the random tree [44].