Survey of Robot 3D Path Planning Algorithms <s> Name of each sub-PRM <s> A number of seemingly unrelated problems involving the proximity of N points in the plane are studied, such as finding a Euclidean minimum spanning tree, the smallest circle enclosing the set, k nearest and farthest neighbors, the two closest points, and a proper straight-line triangulation. For most of the problems considered a lower bound of O(N log N) is shown. For all of them the best currently-known upper bound is O(N2) or worse. The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space. The Voronoi diagram is used to obtain O(N log N) algorithms for all of the problems. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Name of each sub-PRM <s> We present a novel algorithm for motion planning of multiple robots amongst dynamic obstacles. Our approach is based on a new roadmap representation that uses deformable links and dynamically retracts to capture the connectivity of the free space. We use Newtonian physics and Hooke's Law to update the position of the milestones and deform the links in response to the motion of other robots and the obstacles. Based on this roadmap representation, we describe our planning algorithms that can compute collision-free paths for tens of robots in complex dynamic environments. <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Name of each sub-PRM <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> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Name of each sub-PRM <s> United States. Air Force Office of Scientific Research (Michigan/AFRL Collaborative Center in Control Science Grant FA 8650-07-2-3744) <s> BIB004
Criteria of corresponding algorithm -PRM Meaning each step choose nearest neighbors to be the states which are under consideration. -PRM The expected states are to be chosen within a ball (or circle) region, for all states included in the radius will be chosen to connect to the vertex. --PRM A combination of above two, where for a given radius the upper bound of the vertices to be chosen is . work gave a great thought of random sampling in bounding box array. Reference BIB003 introduced PRM * to guarantee asymptotical optimality. Authors in BIB002 concentrated on the problem that typical PRM cannot tackle dynamic threats; they imported the idea of potential to avoid this, which is called Reactive Deformation Road Maps (RDR). PRM has the bottleneck of not being able to determine an efficient near vertex choosing and connection principle. Based on the difference of vertex chosen criteria, this paper combines the idea of  BIB004 and divides PRM into three parts in Table 1 . Although -PRM has the advantage of adopting enough samples to ensure smoothness by adjusting parameter , the extension will be biased if a fixed direction tends to be much more dense. -PRM can keep out the shortcoming of -PRM, but an unreasonable radius may result in an excessive computational burden. --PRM likes an adaptable -PRM; it can guarantee all direction connection and also limit the computational burden to a certain degree. BIB001 introduced the Voronoi diagram into the field of computational geometry; it is firstly Steer( , ) returns a point closer to but within the reach of by a certain value; Near( , rand , | |) return all vertices in a ball center at new and radius is ; Freeobsta( , ) means no obstacle between , ; (1)