Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <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> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> The potential field approach to path planning is computationally intensive but highly parallel. The authors propose a general neural network architecture called the wave expansion neural network (WENN), specifically designed to implement such potential field operations useful for path planning. The authors describe WENN-based neural network systems which implement certain types of artificial potential fields for path planning. The neural network takes the workspace which needs to be navigated as input and generates artificial potential fields which are then subsequently used to find a path. Neural network implementation results in greatly reduced computations. > <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> Due to the NP-hard complexity, the path planning problem may perhaps best be resolved by stochastically searching for an acceptable solution rather than using a complete search to find the guaranteed best solution. Most other evolutionary path planners tend to produce jagged paths consisting of a set of nodes connected by line segments. This paper presents a novel path planning approach based on AppART and Particle Swarm Optimization (PSO). AppART is a neural model multidimensional function approximator, while PSO is a promising evolutionary algorithm. This path planning approach combines neural and evolutionary computing in order to evolve smooth motion paths quickly. In our simulation experiments, some complicated path-planning environments were tested, the result show that the hybrid approach is an effective path planner which outperforms many existing methods. <s> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <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> BIB004 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> In this paper, a mixed-model assembly line (MMAL) sequencing problem is studied. This type of production system is used to manufacture multiple products along a single assembly line while maintaining the least possible inventories. With the growth in customers' demand diversification, mixed-model assembly lines have gained increasing importance in the field of management. Among the available criteria used to judge a sequence in MMAL, the following three are taken into account: the minimization of total utility work, total production rate variation, and total setup cost. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and bacteria optimization (BO) are deployed. The performance of the proposed hybrid algorithm is then compared with three well-known genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed hybrid algorithm outperforms the existing genetic algorithms, significantly in large-sized problems. <s> BIB005 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> The paper presents a genetic algorithm to find and optimize solutions for nonholonomic motion planning problems. Mainly focusing on mobile robots, the algorithm uses present randomized algorithms to come up with suboptimal paths and iteratively optimizes them according to a fitness function which includes domain specific knowledge. The major advantages of this method include being an any-time algorithm, and improving the quality of the solution throughout the evolutionary process. An extensive experimental analysis comparing our results with state of the art algorithms outline the effectiveness of the proposed methodology. <s> BIB006 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> Abstract Ant colony optimization (ACO) is successfully applied in optimization problems. Performance of the basic ACO for small problems with moderate dimension and searching space is satisfactory. As the searching space grows exponentially in the large-scale unit commitment problem, the basic ACO is not applicable for the vast size of pheromone matrix of ACO in practical time and physical computer-memory limit. However, memory-bounded methods prune the least-promising nodes to fit the system in computer memory. Therefore, the authors propose memory-bounded ant colony optimization (MACO) in this paper for the scalable (no restriction for system size) unit commitment problem. This MACO intelligently solves the limitation of computer memory, and does not permit the system to grow beyond a bound on memory. In the memory-bounded ACO implementation, A ∗ heuristic is introduced to increase local searching ability and probabilistic nearest neighbor method is applied to estimate pheromone intensity for the forgotten value. Finally, the benchmark data sets and existing methods are used to show the effectiveness of the proposed method. <s> BIB007 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> This paper presents a novel potential field based 3D path planning technique for differential drive mobile robots, moving in known environment. The path planners are based on description of the obstacles by simulated annealing neural networks. The generated paths are piecewise linear with changing directions at the corners of the obstacles. The proposed planner can be successfully applied to snake robots, flying robots, and control of Gantry cranes. Several simulation results show the effectiveness of the proposed algorithm. <s> BIB008 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> Abstract Three-dimension path planning of uninhabited combat air vehicle (UCAV) is a complicated optimal problem, which mainly focuses on optimizing the flight route considering the different types of constrains under complicated combating environments. A new hybrid meta-heuristic ant colony optimization (ACO) and differential evolution (DE) algorithm is proposed to solve the UCAV three-dimension path planning problem. DE is applied to optimize the pheromone trail of the improved ACO model during the process of ant pheromone updating. Then, the UCAV can find the safe path by connecting the chosen nodes of the three-dimensional mesh while avoiding the threats area and costing minimum fuel. This new approach can accelerate the global convergence speed while preserving the strong robustness of the basic ACO. The realization procedure for this hybrid meta-heuristic approach is also presented in detail. In order to make the optimized UCAV path more feasible, the к-trajectory is adopted for smoothing the path. Finally, series experimental comparison results demonstrate that this proposed hybrid meta-heuristic method is more effective and feasible in UCAV three-dimension path planning than the basic ACO model. <s> BIB009 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> Abstract Optimal Path Planning is a well-known problem and there are many approaches and techniques for solving this task, which are mostly based on graph or grid representation of the environment. Such a representation can be very difficult to construct in the real applications. This paper introduces the Distance Transform (DT) technique of image processing, which operates on the gray level image representation of the 3D environment and its capability of planning optimized paths. The 3D environment is modelled in the form of geo-located layered data, similar to the Geographic Information system (GIS). The spatial multicriteria decision analysis (MCDA) techniques combined with distance transform technique have been used to arrive at the gray level image representation of the environment and to generate the optimal path. <s> BIB010 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> We consider the challenge of planning a minimum length path from an initial position to a final position for a rotorcraft. The path is found in a 3-dimensional Euclidean space containing a geometric obstacle. We base our approach on visibility graphs which have been used extensively for roadmap based path planning in 2-dimensional Euclidean space. Generalizing to 3-dimensional space is not straightforward, unless a visibility graph is generated that, when searched, will only provide an approximate minimum length path. Our approach generates such a visibility graph that is composed by an obstacle graph and two supporting graphs. The obstacle graph is generated by approximating a mesh around the configuration space obstacle, which is build from the convex hull of its work space counterpart. The supporting graphs are generated by finding the supporting lines between the initial or final position and the mesh. An approximation to the optimal path can subsequently be found using an existing graph search algorithm. The presented approach is suitable for fully known environments with a single truly 3-dimensional (not merely "raised" 2-dimensional) obstacle. An example for generating a nearly minimum length path for a small-scale helicopter operating near a building is shown. <s> BIB011 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <s> Abstract A new optimization algorithm called multi-frequency vibrational genetic algorithm (mVGA) that can be used to solve the path planning problems of autonomous unmanned aerial vehicles (UAVs) is significantly improved. The algorithm emphasizes a new mutation application strategy and diversity variety such as the global random and the local random diversity. Clustering method and Voronoi diagram concepts are used within the initial population phase of mVGA process. The new algorithm and three additional GAs in the literature are applied to the path planning problem in two different three-dimensional (3D) environments such as sinusoidal and city type terrain models, and their results are compared. For both of the demonstration problems considered, remarkable reductions in the computational times have been accomplished. <s> BIB012 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis and Conclusion <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> BIB013
This paper analyzes a certain aspect of providing a comprehensive knowledge of 3D path planning, including canonical definition and basic knowledge of each kind of algorithms as well as applicable area. By analyzing all these algorithms which have already proved to be successful, this paper classifies all the approaches into five categories: sampling based algorithms, node based optimal algorithms, mathematic model based algorithms, bioinspired algorithms, and multifusion based algorithms. This paper first lists the elements of each category and then supports a critical discussion of each algorithm. During each discussion process, this paper answers four important questions, respectively: (a) what is the taxonomy of these 3D path planning algorithms? (b) How do these algorithms work in order to find the path? (c) Why is it suitable or not suitable for such environment? According to the analysis we supported, several conclusions can be drawn as illustrated in Table 7 , with the details of time complexity, static (S) or dynamic (D) environmental applicability, and real time applicability. (1) Sampling based algorithms all share the merits of using an initial guess; they differ in how to do postprocessing to ensure completeness or optimum. The random initial guess ensures escaping of local minimum, and this kind of algorithms does not rely much on environmental representation. This kind of algorithms can be further classified as active and passive, where active algorithm can find the optimal path by their own, but passive algorithms cannot. These approaches are appropriate for on-line implementation as they have a high time efficiency, with the ability to handle dynamic and static threats. BIB004 , VVP  , Voronoi potential field algorithms  BIB001 , neural network potential field algorithms BIB002 BIB008  , hybrid bioinspired BIB009 BIB007 BIB003 BIB005 , and so forth Ranked multifusion algorithms PRM node based optimal algorithms BIB013 , GIS-MCDA algorithms BIB010 , visibility graph node based optimal algorithms BIB011 , visibility graph geodesics algorithm BIB011 , sampling based EA BIB012 BIB006 , and so forth (2) Node based optimal algorithms are grid based exploring algorithms; they commonly tackle with node/arc information which can transform distance between nodes/arcs into weight. They originate from dynamic programming approaches and thus cannot further optimize the result beyond the decomposition of the environment. The results of this kind of algorithms rely much on the preconstructed graph and can be combined with other methods to achieve global optimal. (3) Mathematic model based algorithms aim to describe the whole workspace in a mathematic form, with the advantage of describing all constraints with differential equations. They can easily represent dynamic constraints and kinematic constraints. This kind of algorithms gives an overall consideration to safety, reliability, and efficiency and then bounds the cost function tightly. Although this kind of methods loads a heavy computational burden on computer, it can perform well enough with the improvement of computer technology. (4) Bioinspired algorithms import heuristic idea and can excellently deal with complex and dynamic unstructured constraints as well as NP-hard problem. This kind of algorithms optimizes the path by mutation (iterative optimization), but the process also brings problem simultaneously. The mutation process repeats until final goal is achieved; almost all bioinspired algorithms have the shortcoming of having a long dealing period. Thus this kind of algorithms is suggested to work off-line, even though they can handle dynamic threats. (5) Multifusion based algorithms synthesize several algorithms' advantages together to achieve global optimal and cost minimum. This kind of algorithms imports the idea of complementation, that is, merging the merits of several algorithms. These algorithms have ability to achieve several goal simultaneously; thus it often happens that sometimes several simple relative methods combine to form a rather well performed method. These methods are designed to work real time, with strong environmental adaption. 3D path planning approaches explode these years, but problems such as real time planning, complete information expressing, and complex environments modeling still have not been completely solved yet. According to Section 8, this paper recommends a fusion of multipath planning and environment modeling methods; this may become a key direction for 3D path planning under complex situations, and also control uncertainty is recommended to be included.