Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> Given a set of n points in the Euclidean plane each of which is continuously moving along a given trajectory. At each instant of time, these points define a Voronoi diagram which also changes continuously, except for certain critical instances — so-called topological events. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> A path-planning algorithm for the classical mover's problem in three dimensions using a potential field representation of obstacles is presented. A potential function similar to the electrostatic potential is assigned to each obstacle, and the topological structure of the free space is derived in the form of minimum potential valleys. Path planning is done at two levels. First, a global planner selects a robot's path from the minimum potential valleys and its orientations along the path that minimize a heuristic estimate of the path length and the chance of collision. Then, a local planner modifies the path and orientations to derive the final collision-free path and orientations. If the local planner fails, a new path and orientations are selected by the global planner and subsequently examined by the local planner. This process is continued until a solution is found or there are no paths left to be examined. The algorithm solves a much wider class of problems than other heuristic algorithms and at the same time runs much faster than exact algorithms (typically 5 to 30 min on a Sun 3/260). > <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> The Voronoi network is known to be a useful tool for the structural description of voids in the packings of spheres produced by computer simulations. In this article we extend the Voronoi-Delaunay analysis to packings of nonspherical convex objects. Main properties of the Voronoi network, which are known for systems of spheres, are valid for systems of any convex objects. A general numerical algorithm for calculation of the Voronoi network in three dimensions is proposed. It is based on the calculation of the trajectory of the imaginary empty sphere of variable size, moving inside a system (the Delaunay empty sphere method). Analysis of voids is presented for an ensemble of random straight lines and for a molecular dynamics model of liquid crystal. The spatial distribution of voids and a simple percolation analysis are obtained. The distributions of the bottleneck radii and the radii of spheres inscribed in the voids are calculated. <s> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> Despite its many important applications in various disciplines in sciences and engineering, the Euclidean Voronoi diagram for spheres in 3D space has not been studied as much as it deserves. In this paper, we present an algorithm to compute a Euclidean Voronoi diagram for 3D spheres and show how the diagram can be used in the analysis of protein structures. <s> BIB004 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> The goal of adaptive sampling in the ocean is to predict the types and locations of additional ocean measurements that would be most useful to collect. Quantitatively, what is most useful is defined by an objective function and the goal is then to optimize this objective under the constraints of the available observing network. Examples of objectives are better oceanic understanding, to improve forecast quality, or to sample regions of high interest. This work provides a new path-planning scheme for the adaptive sampling problem. We define the path-planning problem in terms of an optimization framework and propose a method based on mixed integer linear programming (MILP). The mathematical goal is to find the vehicle path that maximizes the line integral of the uncertainty of field estimates along this path. Sampling this path can improve the accuracy of the field estimates the most. While achieving this objective, several constraints must be satisfied and are implemented. They relate to vehicle motion, intervehicle coordination, communication, collision avoidance, etc. The MILP formulation is quite powerful to handle different problem constraints and flexible enough to allow easy extensions of the problem. The formulation covers single- and multiple-vehicle cases as well as single- and multiple-day formulations. The need for a multiple-day formulation arises when the ocean sampling mission is optimized for several days ahead. We first introduce the details of the formulation, then elaborate on the objective function and constraints, and finally, present a varied set of examples to illustrate the applicability of the proposed method. <s> BIB005 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> Euclidean Voronoi diagram of spheres in 3-dimensional space has not been explored as much as it deserves even though it has significant potential impacts on diverse applications in both science and engineering. In addition, studies on the data structure for its topology have not been reported yet. Presented in this paper is the topological representation for Euclidean Voronoi diagram of spheres which is a typical non-manifold model. The proposed representation is a variation of radial edge data structure capable of dealing with the topological characteristics of Euclidean Voronoi diagram of spheres distinguished from those of a general non-manifold model and Euclidean Voronoi diagram of points. Various topological queries for the spatial reasoning on the representation are also presented as a sequence of adjacency relationships among topological entities. The time and storage complexities of the proposed representation are analyzed. <s> BIB006 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> the integration of terrain following, terrain avoidance, threat avoidance (TF/TA2) is the key technique for aircrafts to achieve low altitude penetration flight. Depending on this technique, survival ability, accuracy and diversity of aerial assault have been greatly improved. In this Paper, the optimal trajectory programming algorithm of TF/TA2 has been improved, and threat avoidance has been studied. <s> BIB007 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> This paper investigates the problem of covering an environment using a group of quadrotor Unmanned Aerial Vehicles (UAVs) based on locational optimization techniques to assign Voronoi regions to vehicles. In comparison with the standard coverage control problems for single integrator agents, we design a planar position controller for UAVs to spread out over an environment to provide coverage. The stability of entire system is guaranteed using LaSalle’s invariance principle, and numerical simulation is provided to show the effectiveness of the proposed method.Copyright © 2011 by ASME <s> BIB008 </s> Survey of Robot 3D Path Planning Algorithms <s> Voronoi. Shamos and Hoey <s> This paper presents a 3D path planning algorithm for an unmanned aerial vehicle (UAV) in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method (PRM) is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A* algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments. <s> BIB009
Algorithm 2: Explore RRG ( , ). Steer( , ), Near( , rand , | |), Freeobsta( , ) are the same as RRG; Parent( near ) returns the parent vertex of near ; (1) while all new ∈ near  if Freeobsta( new , near ) and  cost End; END; Algorithm 3: Explore RRT * ( , ). used for finite points in the Euclidean plane and now widely used with a series of improved forms in the field of path planning. Voronoi diagram generates topological connection; the distances from the edges to the nearby obstacles are the same. 3D Voronoi first selects an initial site; this site's coordinates hold the property that the minimal distance to the obstacles nearby is the same. Then it calculates new Voronoi sites based on calculation of the Voronoi channel BIB003 and defines the Voronoi net bounds. The whole process stops when all the sites are recorded and all the channels are obtained. The calculation of the Voronoi channel is used to choose a Voronoi site, and the equation of Voronoi channel for the triplet of objects { , , } is as follows: where ( ) is the minimal distance from a give point (or robot as a mass point with 3D coordinate) to the surface of th obstacle in 3D space. Equation (1) extends the characteristics of general Voronoi, if there exists a small shift V along the is the vertices set according to the node choose method claimed ahead; Freeobsta( rand , ) means no obstacle between rand and ; is the path vertex set, is the path edges set; (1) = ⊘; = ⊘; (2) for = 0 to BIB005 rand ← the th sample state in free (4) ← ( PRM or -ball or ∩ )\{ } (5) = ∪ rand BIB009 for each ∈ (7) if Freeobsta( rand , ) End; End; (10) End; Return = ( , ) Algorithm 4: Whole PRM. channel and the point = + V should satisfy the constraint equation, With respect to (1), linearization of this system should obey This ensures finding the direction of the displacement V; thus we can get a new point along the vector. An estimation function (4) is used to improve the computer-based accuracy, that is, controlling the deviation of the trajectory from the Voronoi channel: Let Φ = 0 ensure that the point is on the Voronoi channel. If Φ > 2 ( is desired value), then it returns to the Voronoi channel by applying gradient decay procedure. However, in order to ensure fast convergence, the preliminary sampling of each state is very important; thus this kind of algorithm is classified as sampling based (even though it introduced information adjustment feedback to correct the initial sampling). Voronoi generates a global graph or local graph, but almost the same as RRG and PRM; it also cannot generate the shortest path at the same time. Thus it seeks help from Dijkstra's algorithm, A * , D * , and so forth. This paper defines three steps to Voronoi path generation methods: (a) sampling the environment or just seeking help from other environment construction methods, (b) generating a 3D Voronoi graph, and (c) employing a search algorithm to find the minimal cost path globally. Luchnikov et al. BIB003 first proposed an elaborate 3D Voronoi diagram construction method, which solves 3D complex system path planning problem. Reference BIB006  BIB004 improved it to a further stage by proposing a radial edge like data structure which is capable of dealing with topological characteristics of Euclidean Voronoi diagram of spheres. The topological characteristics are region, face, edge, vertex, oop, and partial edge, which contain the geometric information and adjacency relationship. When implemented in reality, Lifeng and Shuqing BIB007 introduced the method that uses geographical information system to generate the environment nodes and combined with Dijkstra's algorithm to find the shortest path. Sharifi et al. BIB008 assigned Voronoi region to a group of UAV to solve the problem of coverage planning for an environment. Voronoi was combined with potential field method in  BIB002 which is efficient to guarantee fast convergence. Voronoi channel is built mainly based on static obstacles; authors in BIB001 tackle dynamic threats by adding a bound to the Voronoi channels, and the idea can be introduced to 3D environment.