Survey of Robot 3D Path Planning Algorithms <s> Multifusion Based Algorithms <s> Close formation flight is one of the most complicated problems on multi-uninhabited aerial vehicles (UAVs) coordinated control. Based on the nonlinear model of multi-UAVs close formation, a novel type of control strategy of using hybrid receding horizon control (RHC) and differential evolution algorithm is proposed. The issue of multi-UAVs close formation is transformed into several on-line optimization problems at a series of receding horizons, while the differential evolution algorithm is adopted to optimize control sequences at each receding horizon. Then, based on the Markov chain model, the convergence of differential evolution is proved. The working process of RHC controller is presented in detail, and the stability of close formation controller is also analyzed. Finally, three simulation experiments are performed, and the simulation results show the feasibility and validity of our proposed control algorithm. <s> BIB001 </s> Survey of Robot 3D Path Planning Algorithms <s> Multifusion Based Algorithms <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> BIB002 </s> Survey of Robot 3D Path Planning Algorithms <s> Multifusion Based Algorithms <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> BIB003 </s> Survey of Robot 3D Path Planning Algorithms <s> Multifusion Based Algorithms <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> BIB004
Multifusion based algorithms manage with problems where usually a single approach proposed cannot work to find an optimal path individually. When faced with unknown environments, with whether dynamic threat or static threat, not all traditional single planning approaches can fulfill the task of obtaining cost minimum or fast convergence or computational efficiency. For example, PRM cannot generate an optimal path itself, which is the same as Voronoi. Potential field methods often jump into local minimum; node based optimal algorithms need preknown environmental skeleton information. Mathematic model based algorithms tend to be time consuming and unable to solve NP-hard problem with varying environments; bioinspired algorithms vary their performance with the model diagram and have heavy time complexity. Thus researchers try to introduce a combination of different approaches to form a fast searching and global optimal algorithm. Yan et al. BIB004 used 3D grid to represent the environment and 3D PRM to form a road map in obstacle free space; at last A * optimal search algorithm combined to achieve an optimal path. Masehian and Amin-Naseri  introduced a visibility graph, Voronoi diagram, and potential field (VVP) integrated algorithm. If the extension of VVP algorithm to 3D space is investigated, it shows effective tradeoff between the shortest and safest path. Schøler et al. BIB003 combined visibility graph and Dijkstra's algorithm (or Geodesics) to find an optimal solution for path planning problem in 3D. Jaishankar and Pralhad BIB002 planned outdoor environment path by citing GIS-MCDA approach which first synthesizes a variety of information to generate a "combined gray level image"; then an optimal searching algorithm as A * , D * , or EA is used to achieve an optimal path. A hybrid of mathematic model based algorithms with EA BIB001 is proposed to solve NP-hard problem, where general EA tend to be premature. A lot of works adopt this idea; this paper gives a pioneering work of coming up with a taxonomy of this kind of methods. Based on the principle of each algorithm, this paper classifies all of these multifusion based algorithms into two categories: (a) Embedded Multifusion Algorithms (EMA) and (b) Ranked Multifusion Algorithms (RMA). EMA combines several algorithms' advantages together; these algorithms work in simultaneous model, thus ensuring a tightly coupled approach to achieve better performance. RMA means each algorithm works in separate level, where they work rankly. Table 6 illustrates several typical algorithms of each category.