Survey of Robot 3D Path Planning Algorithms <s> Rapidly Exploring Random Graph (RRG). <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> Rapidly Exploring Random Graph (RRG). <s> Rapidly exploring random trees (RRT) and probabilistic roadmaps (PRM) are sampling-based techniques being extensively used for robot path planning. In this paper, the tree structure of the RRT is generalized to a graph structure which enables a greater exploration. Exploration takes place simultaneously from multiple points in the map, all explorations fusing at multiple points producing well-connected graph architecture. Initially, in a typical RRT manner, the search algorithm attempts to reach the goal by expansions, and thereafter furtherer areas are explored. With some additional computation cost, as compared to RRT with a single robot, the results can be significantly improved. The so-formed graph is similar to roadmap produced by PRM. However as compared to PRM, the proposed algorithm has a more judicious search strategy and is adaptable to the number of nodes as a parameter. Experimental results are shown with multiple robots planned using prioritization scheme. Results show the betterment of the p... <s> BIB002
RRT performs well in practice and can guarantee completeness, but it pays almost no attention to the quality of the results, and it is proved that RRT algorithms are not asymptotically optimal BIB001 . To ensure asymptotic optimality, authors in BIB001 introduced rapidly exploring random graph (RRG). The work used a structure = ( , 0 , , ) to represent the performance of the system, where is the set of states, 0 ⊆ is the initial states sets, ⊆ × is the transition relation, and is the labeling function which is used to map each state to the set of atomic propositions. It is illustrated in Figure 9 , where "current new node" denotes the new nodes generated at current steps. Unlike RRT, RRG tries to extend to every state returned by Near() (line 7 of Algorithm 2), which is illustrated in Figure 9 . In Figure 9 (a), | | is the radius stated to choose the neighbor states around the center of "current new node"; then new connects all these nodes to form a graph as illustrated in Figure 9 (b) if the connection is collision-free (in Algorithm 2, from line 7 to line 12). The pseudocode is given in Algorithms 1 and 2. Line 7 shows the main difference between RRT and RRG, where RRG also connects to satisfaction vertices which lie in the circle region; thus it forms a graph. RRG holds the advantage of extending all the vertices returned by the Near() process and then connects them to present a more complex map. Although it seems to be more complex in some way, it almost surely can converge to an optimal path. Reference BIB002 showed experimental results of RRG, and the comparison to PRM proves the advantage of RRG. Also, the conclusion suggested that RRG enables navigating multiple robots simultaneously. However, it generates a complex network like PRM and thus cannot find the optimal path by itself.