Survey of Robot 3D Path Planning Algorithms <s> Analysis. <s> A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character's path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time. We introduce a new data structure, i.e. the Explicit Corridor Map, which allows creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the corresponding algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Analysis. <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> BIB002
Sampling based algorithms exploring depends much on initial guess, and this guess repeats every step. The algorithms may take advantage of nearby collision detection or potential adjustment. Although this leads to loss of completeness and inexplicit construction of the environment sometimes, this can somehow reduce the dependence on environment model and thus enable them to be implemented in various environments. We summarize all the advantage and weakness of this kind of algorithms and analyze each subcategory in detail as illustrated in Table 2 . Except for algorithms analyzed in Table 2 , algorithms such as visibility graphs  and corridor map BIB001 also belong to sampling based algorithms. Visibility graph method likes a simple version of obstacle-based PRM which is proposed by Amato et al.  . Corridor map method likes octree-structure PRM introduced by Yan et al. BIB002 . They both defined a cell decomposition method to construct the workspace. However, such as PRM and Voronoi, these methods need a node search algorithm to achieve the best path. 