The Research On Route Planning Algorithm Based On A* Algorithm And Dubins Path

The development of drone technology has greatly promoted the application of drones in various fields.The way that people control drone flight in real time on the ground is no longer suitable for the increasingly rich application scenarios of drone.Autonomous flight is an inevitable trend for the development of autonomous control technology for drones.Due to the small size and the limited carrying capacity of the UAV,its flight duration in the air is limited.Therefore,the flight path specified when the UAV is performing its mission should be the shortest.At the same time,sometimes approaching or moving away from the target from a specific direction can provide a better view or occlusion for the drone.Therefore,it is meaningful to explore how to find the shortest path between the start position with direction(starting pose position)and the end position with direction(ending pose position).The Dubins path is the shortest path between two pose points,and it conforms to the flight characteristics of the drone.Applying the Dubins path to the drone path planning can greatly improve the efficiency of the drone path planning.Aiming at the above situations,an airline planning algorithm based on A * algorithm and Dubins path is proposed.The main content of the paper is as follows:(1)Solving Dubins path.Two methods for solving the two-dimensional Dubins path between two pose points are summarized and proposed,including a solution method based on analytic geometry and a solution method based on differential geometry,and these two methods are extended to a three-dimensional plane.By simulation verification,these two methods can accurately plan the 2D and 3D Dubins path between the two pose points.(2)Path planning based on A* algorithm.The cost function of the A* algorithm and the implementation process of searching for obstacle avoidance paths are introduced,and the results of the A* algorithm searching for 2D and 3D obstacle avoidance paths are verified by simulation.(3)Combining A* algorithm with Dubins path.First,using the A* algorithm to obtain an obstacle avoidance path between two specified points.Then,using a straight line to compress the obstacle avoidance path to obtain an initial set of obstacle avoidance waypoints.Secondary,using the Dubins path to perform secondary compression on the initial set of waypoints to obtain the final set of obstacle avoidance waypoints.Finally,connecting the adjacent waypoints with Dubins path to form the final obstacle avoidance Dubins path.By simulation verification,the combining algorithm can successfully calculate the 2D and 3D obstacle avoidance Dubins path between the specified two pose points.The A* algorithm is compared with the RRT algorithm and PRM algorithm.The results prove that the A* algorithm is the relatively best choice for searching obstacle avoidance paths.Proved by experiments,the combining algorithm can successfully plan the obstacle avoidance Dubins path between two pose points in an environment with known static obstacles.The obtained path meets the flight constraints of the UAV and is short.