Survey of Robot 3D Path Planning Algorithms <s> Rapidly Exploring Random Trees. <s> Sampling-based planners have solved difficult problems in many applications of motion planning in recent years. In particular, techniques based on the Rapidly-exploring Random Trees (RRTs) have generated highly successful single-query planners. Even though RRTs work well on many problems, they have weaknesses which cause them to explore slowly when the sampling domain is not well adapted to the problem. In this paper we characterize these issues and propose a general framework for minimizing their effect. We develop and implement a simple new planner which shows significant improvement over existing RRT-based planners. In the worst cases, the performance appears to be only slightly worse in comparison to the original RRT, and for many problems it performs orders of magnitude better. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Rapidly Exploring Random Trees. <s> Sampling-based algorithms such as the Rapidly-exploring Random Tree (RRT) have been recently proposed as an effective approach to computationally hard motion planning problem. However, while the RRT algorithm is known to be able to find a feasible solution quickly, there are no guarantees on the quality of such solution, e.g., with respect to a given cost functional. To address this limitation, the authors recently proposed a new algorithm, called RRT*, which ensures asymptotic optimality, i.e., almost sure convergence of the solution returned by the algorithm to an optimal solution, while maintaining the same properties of the standard RRT algorithm, both in terms of computation of feasible solutions, and of computational complexity. In this paper, the RRT* algorithm is extended to deal with differential constraints. A sufficient condition for asymptotic optimality is provided. It is shown that the RRT* algorithm equipped with any local steering procedure that satisfies this condition converges to an optimal solution almost surely. In particular, simple local steering procedures are provided for a Dubins' vehicle as well as a double integrator. Simulation examples are also provided for these systems comparing the RRT and the RRT* algorithms. <s> BIB002
Rapidly exploring random tree (RRT) method is first proposed by LaValle  . The method attempted to solve path planning problems under holonomic, nonholonomic, and kinodynamic constraints. RRT has the advantage of handling multi-DOF problems; thus it is widely used for PR2 and other robots [94] . Authors in BIB001 proposed a fast local escaping version called Dynamic Domain RRT, which will be analyzed below. Karaman and Frazzoli BIB002 solved nonoptimal results problem of RRT by introducing RRG and a heuristic method RRT * . RRT rapidly searches the configuration space to generate a path connecting the start node and the goal node. In each step a new node is sampled; if the extension from the sampled to the nearest node succeeds, a new node will be added. When this kind of method is applied to 3D environment, it normally assumes that there exists a 3D configuration space = . The configuration space consists of two parts, a fixed obstacle region, obs ⊂ , which must be avoided, and an obstacle free region, free ⊂ , where the robots must stay. Corresponding to the configuration space, a path state (or vertex) set includes all the sampling vertices which are generated by RRT exploration process. In order to implement the algorithm, the following steps should be obeyed (see in Figure 7 ). Step 1. First add the initial state init ∈ free in as the first vertex. Then randomly choose a state random in free , and Figure 7 illustrates two states which are random1 and random2 . Step 2. Select a nearest state near to the newly generated state random in based on a certain metric (mostly Euclidean metric) which is already designed; regard near as the parent state of random .