Keywords

1 Introduction

As the technology of unmanned aerial vehicle (UAV) becomes more and more mature, UAVs are gradually used to solve problems that many traditional methods cannot effectively solve, such as target monitoring and tracking, airspace situational awareness interaction, unmanned aerial vehicle automatic collision avoidance, and empty sea-land cooperation. It has played a vital role in the emergency assistance and urban emergency [1]. UAVs have the advantages of flexibility, low cost, small size, low environmental requirements, and high flying height, and can adapt to more complex and dynamic uncertain environments [2]. UAV’s low-altitude autonomous flight is a research hotspot, and the core technology in the path planning for autonomous flight are the automatic obstacle avoidance technology during flight. Traditional UAV obstacle avoidance planning algorithms include gradient method, spline interpolation method, nonlinear programming method, optimal control method, A* algorithm, neural network method, simulated annealing method, genetic algorithm, ant colony algorithm, dynamic programming algorithm, etc. [3,4,5,6,7,8,9], but the above methods treat the UAV as a particle, without considering its own flight performance and the influence of the minimum turning radius on the establishment of the obstacle avoidance model. Dubins [10] considered the influence of the turning radius on the UAV motion and first discussed the shortest curve problem between the initial state and the end state of the motion using the geometric method. The concept of the Dubins path was first proposed. Based on the Dubins path, the researchers discussed how to choose the optimal path from many Dubins paths on the premise of multiple obstacles, and designed a large number of intelligent algorithms to solve. However, most of the traditional Dubins path-based methods do not consider the dynamic task environment, especially where the obstacle position, shape, and size are unknown. Although some real-time path planning algorithms can also respond well to the dynamic environment with uncertain obstacles, they usually require stronger, higher-cost sensors as auxiliary support. For low-cost UAVs, how to achieve dynamic obstacle avoidance during autonomous flight is an important issue that needs urgent solution.

This paper makes full use of Dubins path planning method and uses a simple forward detection sensor to implement a UAV dynamic obstacle avoidance planning algorithm based on the Dubins path through obstacle estimation and the real-time iterative planning. The remainder of the paper is organized as follows: Sect. 2 describes the related works. Section 3 briefly reviews the basic process of Dubins path planning. Section 4 conducts problem modeling and dynamic obstacle avoidance planning algorithm design. Section 5 presents a simulation experiment to discuss the advantages and disadvantages of different obstacle avoidance schemes. Section 6 summarizes the full text.

2 Related Works

At present, the research on the obstacle avoidance methods of UAVs mainly focuses on three aspects.

  1. (1)

    Based on image recognition. Such methods generally install cameras and vision processors on UAVs. The position of the obstacle is calculated from the image acquired by the camera. The reactive collision-avoidance algorithm based on the closest point of approach (CPA) using a single vision sensor for UAVs is proposed [11]. It can avoid a collision with an intruder while overcoming the loss-of-depth problem of the single vision sensor. However, when the shape of the obstacle is irregular, the calculation of the algorithm is more complicated. The method for design a controller of autonomous collision avoidance based on EKF-OSA was proposed [12]. However, this method only applies to static obstacle scenes. In [13], it introduces an efficient approach for sky segmentation in a cluttered environment that is considered as a vital step for UAV autonomous obstacle avoidance. In order to ensure the safety of UAVs flying at low altitude, the grayscale is adjusted according to the captured image to achieve segmentation of the sky, so that obstacles are identified. Through this method, the accuracy of obstacle recognition can be improved.

  2. (2)

    Based on searching. The A* algorithm performs route planning by constructing the cost function. In theory, the UAVs can achieve the shortest path by using A*. It is verified that the planned track satisfies all kinds of flight requirements for hypersonic vehicles and can avoid various threats. For two-dimensional obstacles, obstacle regions is wrapped using elliptical geometry. For three-dimensional obstacles, obstacle regions is wrapped using ellipsoids [14]. However, at present, this method is only aimed at static obstacles. A method of obstacle avoidance for UAV based on Dubins path planning is proposed [15]. This method takes into account the factors of the minimum turning radius of the drone. The path planning is solved by using genetic algorithms under the condition that the obstacle has prior knowledge. In [16], Dubins paths were applied for both static and moving ground obstacle avoidance by using a variation of the Rapidly-exploding Random Tree (RRT) planner. In [17], Search-and-avoid algorithms for Dubins paths can be developed by using several different techniques.

  3. (3)

    Based on potential field. The artificial potential field method is used to plan the targets and obstacles for UAVs. The gravitational function of artificial potential field method is improved, and a sufficient smooth flight path is obtained by several iterations and curvature checking [18]. It is a static path planning method. The geometric constraints of the artificial potential field are added to the kinematics equation, and the collision detection angle is calculated to determine the shortest avoidance path for UAVs [19, 20]. The method can be used to solve the collision avoidance problem during the UAV flight from the initial position to the destination point in a static and dynamic environment. Based on the traditional artificial potential field method, the velocity vectors of the target and the obstacle are respectively introduced into the functions of the gravitational field and the repulsive field in the relative position. The method can meet the safety, real-time and reachability of the path planning of drones under dynamic change of targets and obstacles, and improve the speed of tracking and obstacle avoidance of drones in dynamic environment.

3 Overview of Dubins Path Planning

Assume that the UAV’s initial coordinate is \( < x_{s} ,y_{s} > \), the initial velocity is \( v_{s} \), the endpoint coordinate is \( < x_{f} ,y_{f} > \), and the endpoint velocity \( v_{f} \). As shown in Fig. 1, two directed starting circles and two directed target circles are generated with the minimum turning radius of the UAV. There must be a directed common tangent between any starting circle and the target circle so that the UAV reaches the target position and state from the initial position and state through a starting circular arc, a common tangent line, and a target circular arc (specifically, the common tangent between the two circles with the same orientation is the tangent of the grandfather, and the common tangent between the two circles with the opposite directions is the tangent of the male tangent). This path from the initial position and status to the target position and status is called the Dubins path. Obviously, there are four such combinations. That is, there must be four Dubins paths. The shortest Dubins path is the shortest path from the starting position and state to the target position and state.

Fig. 1.
figure 1

Dubins path between the start position and final position.

Full size image

When there is an obstacle in the path, the shortest Dubins path is found between the start circle, the obstacle circle, and the target circle. As shown in Fig. 2, there are two Dubins paths <SO-1, OF-1> and <SO-2, OF-2> between the start circle, the obstacle circle, and the target circle. Different start circles and target circles exist. There are also different Dubins paths. The shortest of all Dubins paths is the shortest path from the start position and state to the target position and state. In particular, when there are more obstacles, the more Dubins paths are available, the more complex the algorithm for choosing the shortest Dubins path from them.

Fig. 2.
figure 2

Dubins path when obstacle exists.

Full size image

4 Problem Description and Algorithm Design

4.1 Problem Description and Conditional Assumptions

Taking Fig. 3 as an example, assume that the UAV’s initial coordinate is \( < x_{s} ,y_{s} > \), the initial velocity is \( v_{s} \), the endpoint coordinate is \( < x_{f} ,y_{f} > \), and the endpoint velocity \( v_{f} \). A clockwise starting circle generated with the UAV minimum turning radius is the counterclockwise target circle generated with the UAV minimum turning radius. When the obstacle is not considered, the shortest path between the UAV from the starting position to the target position is the Dubins path. Assume that UAVs perform tasks in unknown areas, only knowing the position and status of the initial point and target point. There are obstacles with uncertain quantities, shapes, and sizes randomly in the task area. The problem to be solved at this time is how to minimize the UAV. The distance from the starting position to the target position.

Fig. 3.
figure 3

Figure of problem description.

Full size image

Other assumptions are as follows:

Assumption 1:

UAV’s flight altitude and flight speed remain the same;

Assumption 2:

UAV flight process always meets the constraints of the minimum turning radius;

Assumption 3:

The UAV only carries sensors that are detected in front of the flight, and can sense the distance from the UAV to the obstacle in the front; the maximum detection distance is \( D_{sens} \);

Assumption 4:

The safety distance between the UAV and the obstacle in front is \( D_{safe} \). If the distance between the UAV and the obstacle in front of the UAV is larger than \( D_{safe} \), the UAV may not make any adjustment. When the distance between the UAV and the obstacle in front of the obstacle is less than or equal to \( D_{safe} \), the UAV must bypass.

4.2 Dynamic Estimation of Obstacle Circle

Since only low-cost detection sensors can be used, the UAV constantly sends detection signals forward during flight and takes corresponding measures based on the distance from the obstacle in front. The Dubins path planning method must know the size and position of obstacles, and the obstacles must be circular. Therefore, when faced with unknown obstacles, it is necessary to first solve the problem of obstacle circle estimation.

As shown in Fig. 4, UAV first calculates the shortest Dubins path based on the initial position \( < x_{s} ,y_{s} > \), initial speed \( v_{s} \), and end point \( <x_{f} ,y_{f}>\). If it is detected that there is an obstacle entering the safety distance \( D_{safe} \) during the flight, it is estimated based on the detected obstacle point. A circle of obstacles and re-plan Dubins path. From Fig. 4, we can see that the accuracy of the obstacle circle estimation directly determines the length of the Dubins path and the number of replanning. When the obstruction circle is estimated to be too small (O1 in the figure), frequent replanning is prone to occur; and when the obstruction circle is estimated to be too large (O0 in the figure), although the number of replanning is reduced, it may bypass farther distance. Therefore, the first problem to be solved is the estimation of the size of the obstacle circle.

Fig. 4.
figure 4

Estimation of the obstacle circle.

Full size image

In order to reduce the number of plans and the distance of detours as much as possible, this paper designs a dynamic estimation method of obstacle circle, as follows:

  1. (1)

    Considering that obstacles are mostly continuous spatial geometries, a relatively small radius R1 is first used as the radius of the obstruction circle, and the obstruction circle is used for Dubins path planning.

  2. (2)

    Starting from the previous route planning, if there is an obstacle within the safe distance ahead of UAV Flight T, the obstacle is the same obstacle as the last estimated obstacle. At this time, combining the positions of the obstacles detected twice, the Dubins path planning is performed again using the radius R2 as a new obstacle circle (R2 > R1);

  3. (3)

    If no obstacle was detected during UAV flight T from the previous route planning, clear the historical information, and deal with new obstacles when obstacles are re-detected, as in step 1).

In particular, when the obstacle itself is a circle, according to the principle that a circle is determined by three points, the UAV can only achieve a short obstacle avoidance flight by only requiring dynamic programming three times during the flight. As shown in Fig. 5, when the obstacle itself is a circle, the third estimated obstacle circle is the shape of the obstacle itself.

Fig. 5.
figure 5

Estimation of the obstacle circle for special shape.

Full size image

4.3 Dynamic Obstacle Avoidance Planning Algorithm

figure a

Obviously, it is impossible to find the shortest Dubins path when the obstructions in the environment are completely unknown. Therefore, the goal of this algorithm is to find a Dubins path that can bypass the unknown obstacles from the starting point to the end point, and the Dubins path should be as short as possible. According to the dynamic estimation method of obstacle circle in Sect. 4.2, Dubins path planning method, the dynamic obstacle avoidance planning algorithm designed in this paper is as above.

Among them, the initial Dubins path is determined by the position and status of the starting point and the target point (line 1). If the UAV encounters an obstacle during the flight, it first determines whether the obstacle has connections with the previous obstacle (line 5–7). If it is unrelated, it directly estimates the obstacle circle based on the current obstacle point, and if it is relevant, the estimation of the obstacle circle based on historical information (line 8–16) will be conducted. Finally, a new Dubins path (line 17) is generated based on the estimated obstacle circle.

5 Simulation Results and Analysis

In order to verify the effectiveness of the proposed algorithm named UAV dynamic obstacle avoidance planning algorithm, experiments are carried out for different types of obstacles. In experiment, the location and state of UAV’s initial point and target point are known, and the location, shape and size of the obstacles are unknown, then set the speed of UAV to 2 m/s, the minimum turning radius to r, the safe distance to Ds.

Experiment 1:

Three experiments were carried out for non-circular obstacles, as shown in Figs. 6 and 7.

Fig. 6.
figure 6

(a) Path under different turning radius, (b) Path under different safe distances.

Full size image
Fig. 7.
figure 7

Path under multi obstacles.

Full size image

Under the condition that the safe distance is set to 15 m, the obstacle avoidance path of UAV under different turning radius is shown in Fig. 6(a). It can be seen that with the increase of the minimum turning radius, the detour distance increases when UAV meets obstacles. The reason for this phenomenon is that the smaller the turning radius of UAV is, the more flexible its motion is, and it can use the shorter route to bypass obstacles. Figure 6(b) shows the obstacle avoidance path of UAV at different safe distances under the condition that the minimum turning radius of UAV is set to 5 m. It can be found that with the increase of safety distance, the smaller the distance traveled by UAV when obstacles are encountered, the less likely it is to collide with obstacles. Because the greater the safety distance, UAV can detect obstacles ahead, and advance obstacle avoidance planning in advance. In particular, when the safety distance is too small, UAV may collide with obstacles due to failure to detect obstacles in time. Figure 7 shows the obstacles avoidance path of UAV when it encounters a number of obstacles. Moreover, it can be seen from the figure that when facing obstacles, UAV can provide a real-time path planning with the help of dynamic algorithm to avoid obstacles.

Experiment 2:

Comparison experiment between the proposed algorithm and the basic Dubins path planning algorithm.

Since the basic Dubins path planning method is mainly aimed at known circular obstacles, the circular obstacle is experimentally contrasted in this paper. When a plurality of circular obstacles exist, the path comparison between the dynamic obstacle avoidance planning algorithm and the basic Dubins planning algorithm is presented in Fig. 8(a). We can conclude from the Fig. 8(a) that the path generated by the two algorithms can successfully bypass the obstacles. Compared to the UAV optimal path as a red curve representation in Fig. 8(a) generated by the basic Dubins programming algorithm, the real-time path as a blue curve representation in Fig. 8(a) generated by the dynamic obstacle avoidance planning algorithm is slightly longer than the optimal path. However, the dynamic obstacle avoidance planning algorithm is carried out under the condition that the location, shape and size of obstacles are completely unknown, which is more consistent with the actual UAV task environment.

Fig. 8.
figure 8

(a) Comparison between Dynamic and Basic Dubins planning with round obstacle, (b) Path when the shape of obstacles are known. (Color figure online)

Full size image

Figure 8(b) shows the path of the dynamic algorithm in the case of the shape of circle obstacles is known, location and size are unknown. We can conclude from Fig. 8(b) that comparing with the situation of obstacles completely unknown, the path generated by dynamic algorithm for planning path to avoid obstacles is relatively close to the optimal path, as the shape of obstacles is known to us.

6 Conclusion

In most of the task scenarios, it is difficult to obtain the specific location, shape and size of an obstacle. This paper proposes a dynamic obstacle avoidance planning algorithm based on Dubins path planning. The UAV constantly transmits detection signals in the forward direction during flight, estimates the shape of the obstacles, and detects the distance from obstacles, ensuring that obstacle avoidance is achieved under the minimum turning radius. UAV can plan a better obstacle avoidance path in real time without knowing the shape, location and size of obstacles. Simulation results show that the algorithm is correct and can improve the efficiency of low-cost UAVs performing tasks in a dynamic environment.