Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> 1 Introduction and Overview.- 2 Configuration Space of a Rigid Object.- 3 Obstacles in Configuration Space.- 4 Roadmap Methods.- 5 Exact Cell Decomposition.- 6 Approximate Cell Decomposition.- 7 Potential Field Methods.- 8 Multiple Moving Objects.- 9 Kinematic Constraints.- 10 Dealing with Uncertainty.- 11 Movable Objects.- Prospects.- Appendix A Basic Mathematics.- Appendix B Computational Complexity.- Appendix C Graph Searching.- Appendix D Sweep-Line Algorithm.- References. <s> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner. > <s> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> This paper addresses the problem of generating smooth trajectories between an initial and a final position and orientation in space. The main idea is to define a functional depending on velocity or its derivatives that measures smoothness of trajectories and find a trajectory that minimizes this functional. In order to ensure that the computed trajectories are independent of the parametrization of positions and orientations, we use the notions of Riemannian metric and covariant derivative from differential geometry and formulate the problem as a variational problem on the Lie group of spatial rigid body displacements. We show that by choosing an appropriate measure of smoothness, the trajectories can be made to satisfy boundary conditions on the velocities or higher order derivatives. Dynamically smooth trajectories can be obtained by incorporating the inertia of the system into the definition of the Riemannian metric. We state the necessary conditions for the shortest distance, minimum acceleration and minimum jerk trajectories. <s> BIB004 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds). <s> BIB005 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <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> BIB006 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> This is the second part of a series papers on modeling and path planning of the City-Climber robot. This paper presents a path planning method for the City-Climber robot using mixed integer linear programming (MILP) in 3D building environments that consist of objects with primitive geometrical shapes. In order to use MILP to solve obstacle avoidance problems, we first simplify and decouple the robot dynamic model by introducing a restricting admissible control. The decoupled model and obstacle can be rewritten as a linear program with mixed integer linear constraints that account for the collision avoidance. A key benefit of this approach is that the path optimization can be readily solved using the AMPL and CPLEX optimization software with a Matlab interface. Simulation results show that the framework of MILP is well suited for path planning and obstacle avoidance problems for the wall-climbing robot in 3D environments. <s> BIB007 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <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> BIB008 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> Abstract In this paper, optimal paths in environments with obstacles for underwater vehicles are computed using a numerical solution of the nonlinear optimal control problem (NOCP). The underwater vehicle is modeled with six-dimensional nonlinear and coupled equations of motion, controlled by DC motors in all degrees of freedom. An energy performance index combined with a time consumption index is used. Both fixed and free final times are considered. Solving NOCP leads to a two point boundary value problem (TPBVP). Five intelligent evolutionary algorithms (EAs), which include genetic algorithm, memetic algorithm, particle swarm optimization, ant colony optimization and shuffled frog leaping algorithm, are applied to solve the NOCP. For comparison, a conjugate gradient penalty method is also used to solve the TPBVP. The simulation results show that the trajectories obtained by the intelligent methods are better than those of conjugate gradient method. After analyzing a simple path planning problem, the time-energy-optimal path planning problem in energetic environments is propounded and solved by EAs. The problem of static obstacle collision avoidance in an energetic environment is also studied. <s> BIB009 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> This paper presents a real-time path planning algorithm for unmanned aerial vehicle (UAV) in complex 3D environments. In this study, the work space is represented by free voxels, which have enough space tolerance to satisfy the safety needs of the UVA. In order to obtain the connectivity of free voxels effectively, the environment is divided into bounding box array and the connectivity evaluation is carried out in each bounding box. A modified Probabilistic Roadmap Method (PRM) is introduced by random sampling in bounding box array to ensure a more evenly distribution of roadmap nodes in 3D space. Based on the voxel connectivity, the selected nodes compose a roadmap, which is applied for path searching by A∗ algorithm for feasible path. Experimental results show that the proposed path planning approach can significantly reduce the computation time than traditional PRM method. <s> BIB010 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> The majority of existing approaches to mobile robot mapping assumes that the world is static, which is generally not justified in real-world applications. However, in many navigation tasks including trajectory planning, surveillance, and coverage, accurate maps are essential for the effective behavior of the robot. In this paper we present a probabilistic grid-based approach for modeling changing environments. Our method represents both, the occupancy and its changes in the corresponding area where the dynamics are characterized by the state transition probabilities of a Hidden Markov Model. We apply an offline and an online technique to learn the parameters from observed data. The advantage of the online approach is that it can dynamically adapt the parameters and at the same time does not require storing the complete observation sequences. Experimental results obtained with data acquired by real robots demonstrate that our model is well-suited for representing changing environments. Further results show that our technique can be used to substantially improve the effectiveness of path planning procedures. <s> BIB011 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <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> BIB012 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> Coverage Path Planning (CPP) is the task of determining a path that passes over all points of an area or volume of interest while avoiding obstacles. This task is integral to many robotic applications, such as vacuum cleaning robots, painter robots, autonomous underwater vehicles creating image mosaics, demining robots, lawn mowers, automated harvesters, window cleaners and inspection of complex structures, just to name a few. A considerable body of research has addressed the CPP problem. However, no updated surveys on CPP reflecting recent advances in the field have been presented in the past ten years. In this paper, we present a review of the most successful CPP methods, focusing on the achievements made in the past decade. Furthermore, we discuss reported field applications of the described CPP methods. This work aims to become a starting point for researchers who are initiating their endeavors in CPP. Likewise, this work aims to present a comprehensive review of the recent breakthroughs in the field, providing links to the most interesting and successful works. <s> BIB013 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> An Unmanned Aerial Vehicle (UAV) has to possess three abilities to function autonomously. The three abilities are localization, mapping and path planning. Path planning guides the UAV to find a feasible path, meaning a path that meets safety, kinematic and optimization constrains. In order to intercept a moving target, dynamic path planning must be used due to target movement. To produce a feasible path, many approaches had been used in path planning algorithms. The current approach of path planning is divided into three kinds of algorithm. The first approach is an algorithm which is based on grid. Second approach is algorithm which is based on evolutionary algorithm. The last is algorithm which is based on curves. This paper presents short review of these algorithms and gives a critical analysis of each approach. The review used literature from book, conference and journal publication. The result shows that implementation of curved path planning in dynamic condition becomes a great opportunity in the UAV field. <s> BIB014 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> Motivated by the need for formal guarantees on the stability and safety of controllers for challenging robot control tasks, we present a control design procedure that explicitly seeks to maximize the size of an invariant “funnel” that leads to a predefined goal set. Our certificates of invariance are given in terms of sums of squares proofs of a set of appropriately defined Lyapunov inequalities. These certificates, together with our proposed polynomial controllers, can be efficiently obtained via semidefinite optimization. Our approach can handle time-varying dynamics resulting from tracking a given trajectory, input saturations (e.g. torque limits), and can be extended to deal with uncertainty in the dynamics and state. The resulting controllers can be used by space-filling feedback motion planning algorithms to fill up the space with significantly fewer trajectories. We demonstrate our approach on a severely torque limited underactuated double pendulum (Acrobot) and provide extensive simulation and hardware validation. <s> BIB015 </s> Survey of Robot 3D Path Planning Algorithms <s> Introduction <s> 3D path planning of unmanned aerial vehicle (UAV) targets at finding an optimal and collision free path in a 3D cluttered environment while taking into account the geometric, physical and temporal constraints. Although a lot of works have been done to solve UAV 3D path planning problem, there lacks a comprehensive survey on this topic, let alone the recently published works that focus on this field. This paper analyses the most successful UAV 3D path planning algorithms that developed in recent years. This paper classifies the UAV 3D path planning methods into five categories, sampling-based algorithms, node-based algorithms, mathematical model based algorithms, Bio-inspired algorithms, and multi-fusion based algorithms. For each category a critical analysis and comparison is given. Furthermore a comprehensive applicable analysis for each kind of method is presented after considering its working mechanism and time complexity. <s> BIB016
Advances in commercial grade technology and advanced research make it possible for robots to appear in everyday life. Modern robots of different varieties include industrial robots, service robots, have seen bright future. For robots, such as Google Self-Driving Car  and iRobot Vacuum Cleaning robot  , one of the most basic and important abilities is path planning, that is, autonomous routing. This requires both time efficiency to react to any emergency situation and safety consideration for implementation. Path planning targets for moving robots from their initial locations to the goal location by their own actuators and strategies, and during the process, robots must always be able to avoid obstacles to maintain safety. Robots such as underwater robots BIB006 BIB009 , wall-climbing robot BIB007 , and micro air vehicles BIB012 BIB008  have already been tested purposely with different kinds of methods. These methods can be basically perceived from   BIB002  , where algorithms were already detailed synthesized. These works contributes a lot; however they are analyzed in a general view without comparison and analyzed in specific perspectives as well as covering the latest works. Thus, we need to provide a comprehensive analysis on 3D path planning methods. By reviewing the latest works, it is not hard to see that most works concentrate only on two dimensions (2D), thus limiting the behaviors of the robots only to surface or each iteration considering the height as a constant to achieve a 2.5-dimensional (2.5D) method. Choset  summarized a lot of his own and others' works; however he mainly concentrates on 2D environment and therefore algorithms like bioinspired algorithms were paid no attention. LaValle et al.  focused mainly on sampling based algorithms. None of these researchers had analyzed all the algorithms in 3D planning area. Surveys such as BIB013 almost all analyze the path planning problems under 2D condition. Reference BIB014 only focuses on micro air vehicle's path planning problems, and algorithms like mathematic optimal algorithms were ignored. Lately, authors in BIB013 did a thorough survey on coverage path planning, which is classified by distinguishing decomposition methods. They provided a basic understanding of 3D path planning methods and then narrowed their discussion 2 Journal of Control Science and Engineering (a) Forest BIB010 (b) Urban  (c) Underwater  Figure 1: Examples of 3D complex environments. to sampling based algorithm to explain the 3D planning idea. Facing the more and more challenging environment that robots faced, where environments tend to be unstructured and full of uncertain factors, 3D path planning algorithms are urgently needed nowadays. Several typical kinds of 3D environments are presented in Figure 1 , including forest, urban, and underwater environments. When planning in these complex situations, a simple 2D algorithm will not be qualified; thus 3D path planning algorithms are needed. Path planning in 3D environment shows great prospect, but unlike 2D path planning, the difficulties increase exponentially with kinematic constraints. In order to plan a collision-free path through the cluster environment, the problem of how to model the environment while taking the kinematic constraints into consideration needs to be solved. From the optimization point of view, finding a 3D optimal path planning problem is NP-hard; thus there exist no common solutions. 3D path planning algorithms include visibility graph  which works by connecting visible vertexes of polyhedron, random-exploring algorithms such as rapidly exploring random tree  , Probabilistic Road Map BIB005 , optimal search algorithms (such as Dijkstra's algorithm  , A * BIB001 , and D * BIB003 ), and bioinspired planning algorithms. What must be emphasized is that this paper only pays attention to broadly applicable methods proposed. Algorithms such as manifold based algorithms BIB004 , which generate smooth path, have been ignored due to reason that it is only applicable to rigid body robots without aerodynamical or hydromechanical influences. Synthesizing all these methods, a two-step procedure of 3D path planning is summarized as follows. Step 1. The first step is environment perception and modeling, usually using a grid map BIB011 (with occupancy probability), or a convex or nonconvex region in combination of polynomial form BIB015 . Step 2. Then path planning algorithm is employed to find the best path according to the cost function, with the ability to achieve both time efficiency and cost minimum. Steps above are not absolute procedures we must obey, and Step 1 can be divided into two parts, or Step 2 integrates with Step 1. According to Step 2, this paper discusses the efficiency of each algorithm and particularly concentrates on time complexity and applicability. Path planning in 3D environments may face much more uncertainties; thus all this should be taken into consideration to achieve the best path. Local minimal and global optimal are two contradictive points; this paper will analyze these two properties of the algorithms. This paper mainly answered several important questions: (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? This paper is an extension of BIB016 , with more comprehensive explanation on each kind of algorithms. The main contributions of this paper are listed below. (1) The first contribution is proposing a taxonomy method for 3D path planning algorithms and puts forward a new category called multifusion based algorithms. (2) The second contribution of this paper is providing a comprehensive analysis of 3D path planning algorithm which contains almost all of the current most successful methods. The following sections are arranged as follows. Section 2 discusses some controversial points which need to be declared and gives definitions to these problems for further discussion. Section 3 explains the taxonomy of 3D path planning algorithms and gives a detailed analysis of the taxonomy's reason and also lists elements of each category. This section includes the basic concept of each kind of algorithms. A series of sampling based algorithms are discussed particularly, and each element is put forward by comparison in Section 4. Node based optimal algorithms' common properties are analyzed in Section 5, and this kind of algorithms shares the same merits. In Section 6, this paper discusses a special kind of planning algorithms, that is, mathematic model based algorithms, and confirms it to be path planning algorithm. Section 7 concentrates on the working mechanism of bioinspired algorithms, and three typical algorithms are analyzed elaborately. Multifusion based algorithms are discussed in Section 8, which are commonly ignored. Some typical researches are listed to prove this category. The last section outlines a conclusion and some directions for further research.