Survey of Robot 3D Path Planning Algorithms <s> RRT-Star ( <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> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> RRT-Star ( <s> Engine malfunctions during helicopter flight poses a large risk to pilot and crew. Without a quick and coordinated reaction, such situations lead to a complete loss of control. An autonomous landing system could react quicker to regain control, however current emergency landing methods only generate dynamically feasible trajectories without considering obstacles. We address the problem of autonomously landing a helicopter while considering a realistic context: multiple potential landing zones, geographical terrain, sensor limitations and pilot contextual knowledge. We designed a planning system to generate alternate routes (AR) that respect these factors till touchdown exploiting the human-in-loop to make a choice. This paper presents an algorithm, RRT*-AR, building upon the optimal sampling-based algorithm RRT* to generate AR in realtime and examines its performance for simulated failures occurring in mountainous terrain, while maintaining optimality guarantees. After over 4500 trials, RRT*-AR outperformed RRT* by providing the human 280% more options 67% faster on average. As a result, it provides a much wider safety margin for unaccounted disturbances, and a more secure environment for a pilot. Using AR, the focus can now shift on delivering safety guarantees and handling uncertainties in these situations. <s> BIB002
* ). RRT * BIB001 is the tree version of RRG which also preserves the asymptotic optimal property as RRG; it is proposed to tackle differential constraints. RRT * removes probable bad connection which works in a refining way; thus it optimizes the solutions to be less expensive than they used to be. Here a cost-function cost( ) is defined to represent the cost of the unique path from init to an arbitrary state ∈ and gives the cost( init ) equal to zero initially. RRT * differs RRG in postprocessing process, compared to Algorithm 2; RRT * pseudocode is given in Algorithm 3 with intuitive illustration Figure 10 . Let us take the same example case as illustrated in Figure 9 (a). RRT * first finds the nearest state as well as the neighbor states near and then adds the nearest state to the tree as well as the minimal cost connection if it exists (from line 4 to line 12). Further, RRT * tries to eliminate the connections which have a larger cost by connection via new state (from line 14 to line 21). Because of the pruning and reconnecting, the tree turns to be more compact and dense as illustrated in Figure 10 (b). Consequently the overall minimal cost can be obtained. However, the whole time consumption increases, and also it cannot work to generate multipath. Choudhury et al. BIB002 assumed that if the nearest parent already has children nearby; then the second best parent will be chosen. This method solves the problem of general RRT and RRT * by supporting an on-line fast replanning method.