# Fast Path Planning of Autonomous Vehicles in 3D Environments
## 1 Introduction  
Recently, various autonomous vehicles (AV), such as unmanned aerial vehicles (UAV) or unmanned underwater vehicles (UUV), perform many missions, such as environment monitoring, target tracking, and UAV photogrammetry [1; 2; 3]. Three dimensional path planning is important for safe navigation of an AV, which operates in three dimensions [2; 4; 5; 6]. Once the 3D path is planned, the AV follows the path utilizing path following controls [7; 8; 9]. However, how to make the AV follow the planned path is not within the scope of our paper. Simple 2D path planning algorithms cannot handle complex 3D environments, where there exist a lot of structures constraints and uncertainties [10]. Therefore, 3D path planners for an AV are urgently required, especially in complicated 3D environments such as urban environments. It is desirable that a path planner searches for a safe path as fast as possible. Therefore, this paper proposes a novel 3D path planner that is fast in generating a sub-optimal path. In other words, our path planner considers both the computational load and the generated path length. Since our path planner runs fast, our planner is suitable for on-line path planning of an autonomous vehicle with cheap embedded systems. There are many papers on 3D path planner for an AV [10]. A-star planner, Theta-star planner, Dijkstra planner, and Voronoi diagram have been implemented as path planners of various AVs [11; 12; 13; 14; 15]. A-star planner achieves better performance than Dijkstra planner by utilizing heuristics for guiding its search towards its goal. A-star, Theta-star, or Dijkstra planners [11; 12; 13; 14; 15] require that the entire workspace is already covered by multiple node points (grid cells) completely. A-star, Theta-star, or Dijkstra planners then work to find a cost minimum path to the goal [10]. As one increases the volume of the entire workspace,the number of node points required to cover the workspace also increases. Therefore, calculating a path utilizing A-star, Theta-star, or Djkstra planners in a large 3D environment may be infeasible due to large computational load. Our paper considers a 3D workspace without node points. Considering a 2D workspace without node points, a Voronoi diagram has been utilized as a safe path for an AV [16; 17; 18; 19; 20; 21]. However, it is not trivial to generate a 3D path utilizing 3D Voronoi diagrams. Two 3D obstacles generate a 3D Voronoi surface that is equidistant from the two obstacles. However, it is not clear how to generate a 3D path on the 3D Voronoi surface. Considering a 3D workspace without node points, ref. [22] addressed a potential field based 3D path planner in cluttered environments. The path planners in [22] describes obstacles by simulated annealing neural networks. The computational load of the path planner in [22] increases as one increases the total number of planar surfaces of the obstacle. However, adding spheres and cylinders, that are described with second order equations, increases the computational load of the path planner in [22]. The 3D path planner in our paper does not depend on obstacle shapes, which distinguishes our paper from [22]. In other words, our path planner works for obstacles with arbitrary shapes. Considering a workspace without node points, RRT planners in [23; 24; 25] utilized random sampling to generate a feasible path. RRT planners works for obstacles with arbitrary shapes. RRT planners have been utilized in complex environments due to their ability to search high-dimensional input spaces, in order to navigate among static and dynamic obstacles [26]. In RRT planners, sample points are randomly generated in the obstacle-free space. The authors of [24] showed that the path generated by RRT-star converges to the optimum path asymptotically when infinite time is consumed. But, one cannot wait for unspecified time in practice. In other words, it may take too much time until randomly generated sample points cover the entire obstacle-free space.