Research On The Small UAV Online Path Planning Algorithms In Complex And Low-Altitude Environments

The problem of the path planning of a Small Unmanned Aerial Vehicle(SUAV) is to plan a valid path reaching the goal. The path is required to be feasible, flyable, safe, low-cost and low-collision probabilily. The feasibility of a path means the path must satisfy all the kinematic constraints of the SUAV. The flyablity requires that the path is easy to execute and the curvature of the path is contivuous. Meanwhile, the flyability processing of a path mainly considers the problems of redundant waypoints pruning and path smoothing. The safety of a path requires the threat amount on the path is low. The cost of a path considers the energy consumption of the flight of a SUAV and the control difficulty of the SUAV when executing the path, as well as the threat amount on the path. The low-collision probability means the collision probability of a SUAV is low when it flies on the path.The online path planning is a key problem of realizing the autonomously flying of a SUAV. It helps to improve the abilities of survival and handling the emergencies in complex low-altitute spaces. The key technologies of the online path planning include the problems of online path searching, online path optimizing and the path flyability processing. In this dissertation, the key technologies and problems of the SUVA online path planning mentioned above will be discussed.Aiming at solving the problem of fast searching for a secret path in obstacle dense environments, an accurate sampling space reduction based fast path searching algorithm and a K-dimensional tree(Kd) based fast path tree nodes storing and accessing method are researched and proposed. Details are as follows. Firstly, aiming at solving the problem of over-reducing the sampling space by the traditional method, a cost model of the sampling space is proposed, then, the sampling space is reducted accurately by comparing the costs of samples and their near path tree nodes. Secondly, the speed of stroring and accessing nodes of a Kd tree is slow when the Kd tree is huge. To solve this problem, a novel path tree nodes storing and accessing method based on sampling space division and multi Kd trees is proposed. The experimental results indicate that the methods proposed in the dissertation improve the secret SUAV path searching speed in obstacle dense environments.Aiming at solving the online safe path searching problem in threat environments, we propose an online path searching method based on the static threat modeling and the Dynamic Threat(DT) Reachable SUAV waypoints Set(RS) estimation. Details are as follows. Firstly, a static threat area model is proposed based on the An Intuitionstic Fuzzy Set(A-IFS) theory, to solve the problem of traditional models which do not take the real-time UAV motion into account. The new model expresses a threat area by the functions of membership, non-membership and hesitancy. The non-membership function is used to describe the influence of the UAV motion on the threat level that the UAV suffers. Secondly, the results of traditional methods are imprecise in estimating the reachability areas of a DT when the motion model of DT is unknown. To solve this problem, a wide RS estimation method is proposed where the DT avoidance problem is formulated by the zero-sum game theory, and the RS is estimated according to the DT intention to intercept the SUAV. Thirdly, aiming at solving the problem that the sub goals of traditional online planning searching methods are not heuristic enough, a new sub goal selection method is presented. The difficulty of searcing a path to a sub goal and the cost of the sub path reaching the sub goal are considered when selecting a sub goal. The experimental results indicate that our methods improve the reliability of the threat assessment and the speed of searching for a low threat path online.Aiming at searching for a low-collision probability path, an online path searching method and the RS estimation method based on the motion control error estimation are proposed. Firstly, the traditional motion control error handling methods are computationally complicated and the randomness of conventional heuristic path searching methods is strong. Thus a new online path searching method is proposed which estimates the motion control error distribution of the SUAV off-line and searches for the low-collision path online based on the sampling space reduction. Secondly, to improve the reliability of the static threat assessing, a new method is proposed to consider the motion control errors of the SUAV during modeling and assessing static threats. Thirdly, the environmental information usage of conventional methods is not sufficient enough when the motion model of DT is available but the constraints of DT are far from sufficient. Thus a wide RS estimation method is presented according to the intention of DT to intercept the SUAV and the motion estimation of DT. Finally, because the traditional path adjustment methods are computationally complex without consideration the motion of the SUAV, a new path adjustment method is presented according to the distributions of the SUAV motion control error and threat areas to rapidly decrease the threat amount on the path. The experimental results indicate that our methods promote the low collision probability path searching speed and the reliability of the threat assessment of the static threat and the dynamic threat.A sampling space reduction based online path optimizing method and an estimated lowest path cost based redundant waypoints pruning method are proposed. Firstly, traditional path optimizing methods converge slowly, and the conventional heuristic cost function based sampling space reduction methods are imprecise, and slow in adjusting the reduction of the sampling space as well as insufficient in using the environmental information. Thus, we propose a new sampling reduction method based on which an online path optimizing method is presented. Secondly, because the sequential redundant waypoints pruning method does not take the indicators of path cost into account comprhensively and the shortcut method converges slowly, an estimated lowest path cost based redundant waypoints pruning method is presented. In this method, the shortcut method is embedded into the sequential method to prune waypoints randomly and improve the diversity of the pruning. Meanwhile, the pruned probabilities of waypoints are computed by the costs of the estimated optimal paths through waypoints and the probabilities are adjusted adaptively in the random pruning process. The sequential method is used to control the scope of the random pruning. The experimental results demonstrate that our methods improve the efficiency of the path optimizing and promote the flyability of the resulting SUAV path.Above all, we provide a new thought and solution for the key technological problems of the online path searching in obstacle dense environment and the online path searching in threat environments, and the online path searching taking the motion control error of the SUAV into account, as well as the online path optimizing and path flyability processing.