However, constrained by the size of the target area and the maneuverability of fixed-wing UAVs themselves, in practical applications, UAV formations often encounter scenarios where they must fly around dense distributions of target points. This requires UAVs to perform extensive curved maneuvers to reach the target point coordinates, significantly reducing the efficiency of the UAV formation’s search and increasing the search time. Therefore, we recommend determining the sequence of target points and the heading angle for each UAV towards every target point before path planning to optimize the UAV formation’s path planning.
2.1. Dubins Path
The trajectory of fixed-wing unmanned aerial vehicles is a linear variation, delineating its trajectory as a curve [
19].
This paper focuses solely on the motion of unmanned aerial vehicles in a two-dimensional environment, where x and y represent the Cartesian coordinates of the drone’s position, and θ represents the angle of the UAV relative to the X-axis, which is the heading angle of the drone.
Assuming a model where the UAV’s velocity is set at 1 and the maximum curvature is 1/γ, the kinematic equations can be expressed as follows:
In this context, , and the constant u is the control variable that varies with time for the drone, with an absolute value of .
In mathematical modeling, the simulation of an unmanned aerial vehicle’s curved motion with curvature 1/γ is typically achieved through the utilization of Dubins curves [
20]. J-D. Boissonnat et al. had a detailed account of the specific derivations for various scenarios involving Dubins curves [
21]. Dubins curves are commonly divided into two major families: the CCC family, which includes RLR and LRL, and the CSC family, which includes RSR, LSL, RSL, and LSR [
22]. C represents an arc with curvature not exceeding 1/γ, S represents a straight line, L represents a counterclockwise curve, and R represents a clockwise curve. The Dubins curve is depicted by drawing the maximum curvature radius circle tangent to the initial state, followed by the delineation of two tangent lines connecting the circles. Through defined coordinate positions and heading angles, the shortest path can be determined [
23].
The Dubins shortest-path problem belongs to the realm of solving minimization problems in traditional optimal control theory. In this problem, the initial and final states of the UAV are uncertain, and the control vector is a continuous function, making it amenable to solution using variational methods. In the UAV motion model presented in this paper, the UAV’s velocity is set to 1. The performance functional for the shortest path of Dubins curves can be represented by an integral, as shown in Equation (5).
In Equation (5),
and
represent the initial and terminal times of the UAV. We set
,
,
as parameters for the shortest path. Combining Equations (2)–(4), which represent the UAV’s kinematic equations, with Equation (5), which represents the performance functional, we construct the Hamiltonian function based on the theorems of optimal control theory. Therefore, the Hamiltonian function for the UAV’s shortest path is given as
According to the Pontryagin maximum principle, we can obtain the necessary conditions for the shortest path of the Dubins curve [
24].
The above equation indicates that
and
are piecewise constant within the UAV’s motion cycle [
,
]. Due to the linearity of the Hamiltonian in the control function u, there are two distinct types of optimal control [
25]. In the situation that
, u takes on the value of
. Conversely, when
, u ∈ [−1, 1]. The former condition corresponds to the maximum curvature arc with a radius of r, while the latter aligns with the trajectory of a straight line where the direction is given by
.
Sussmann and his colleagues, in their seminal paper in 1991, established the existence of a solution to the Dubins path problem, wherein the optimal trajectories manifest as either C
αC
βC
δ or C
αS
dC
β, where 0 ≤ α, δ < 2π, π < β < 2π, and d ≥ 0 [
26]. Given the inherent non-uniqueness of solutions to the Dubins path, generally, multiple trajectories can converge to the minimal value [
27]. As discerned from Equation (7), the shortest path of the Dubins curve is intricately linked to the heading angle. The choice of distinct heading angles results in divergent selections within the path details. Consequently, determining the heading angles in the Dubins curve emerges as a pivotal factor in ascertaining the unmanned aerial vehicle’s shortest path [
28]. In
Section 2.2, we introduce a heading angle model that exhibits a notable enhancement when compared to existing algorithms. The specific data comparisons are presented in
Section 4.
2.2. Compensatory Look-Ahead Algorithm
In
Section 2.1, the necessary conditions for the shortest path and the existence of the optimal solution are demonstrated. It is also shown that the shortest path of Dubins curves is closely related to the heading angle. Determining the heading angle in Dubins curves is crucial for determining the shortest path for unmanned aerial vehicles. Compared to path planning between two waypoints, smooth curve optimization between three waypoints better meets practical requirements and yields superior planning results. Ma et al. introduced a midpoint
between the initial point
and the terminal point
of the Dubins curve. Referring to the analysis in [
26], they obtained the boundary relationships of the midpoint, as shown below.
In Equation (8), and are constants. Combined with Equation (7), it becomes evident that and exhibit a discontinuous jump at and are not continuous.
Figure 2 presents a schematic diagram of the optimal path. The red trajectory represents the Dubins optimal path, which passes through the initial point, midpoint, and terminal point.
is the heading angle (relative to the X-axis) of the initial point
.
and
are the angles of the line where they are located (relative to the X-axis).
represents the heading angle of the midpoint
. Ma et al. reached the conclusion that a line drawn from the midpoint
to the point of intersection A
of the two line segments bisects the angle of intersection, which is shown by the blue line segment in
Figure 2. On the optimal path,
and
. Substituting these values into Equation (8) allows the system of simultaneous equations to be solved. The results can then be utilized in Equation (9).
From Equation (9), we can derive that
. The Hamiltonian function is continuous along the optimal trajectory at point (
). Therefore, it can be represented as follows:
From the above equation, it can be deduced that
From Equations (7) and (9), Equation (10) can be obtained.
By Equation (10), the midpoint heading angle of the shortest path can be obtained, and the solution to the coupled trigonometric equations can be found. While this can be accomplished numerically, it is challenging to describe using a general formula. In their paper, Ma et al. did not provide a complete equation that could represent all possible geometric configurations of three path points and initial direction, thus uniquely determining the optimal trajectory for any problem. Solving the coupled trigonometric equations can be performed numerically but is difficult to describe with a general formula. Therefore, based on the horizon backtracking principle, we propose a four-point optimization-based algorithm for calculating the heading angle (Algorithm 1) and provide a general formula for computing the heading angle size at the target point.
First, let us consider the scenario where the distances between the initial, intermediate, and terminal waypoints are relatively long.
Figure 3 illustrates the path planning between the initial, intermediate, and terminal waypoints, where the solid red lines represent Dubins trajectories. Point F (
) and point D (
) denote the tangent points of two circular trajectories. While the midpoint heading angle
can be solved using Equation (10), when the distances between the initial and intermediate points are considerable, the error between the angle
(relative to the X-axis) of the line segment connecting point F (
) and point D (
) and the angle
(relative to the X-axis) of the line segment connecting the initial point B (
) and the tangent point D (
) (red dashed line segment) can be neglected. Solving for the coordinates of tangent point F (
) is difficult, so the direction angle
(relative to the X-axis) of the intermediate point can be directly solved using the coordinates of the initial point B (
) substituted into Equation (12).
From
Figure 3, the total range L between the three points after task planning can be obtained, as shown below:
From Equation (13), it can be seen that the value of L is related to α, β, as shown in Equation (14):
It is discernible from the equation that as the sum of α and β decreases, reaching equality (α = β), the value of Equation (14) attains its minimum. Illustrated graphically, when the center O of the circle lies on the angle bisector of angle A, the total course length L achieves its minimum value, denoted as . The heading angle at the midpoint is given by .
Next, let us consider the scenario where the distances between the initial, intermediate, and terminal waypoints are relatively close.
Figure 3 depicts the path planning between the initial, intermediate, and terminal waypoints, where the solid red lines represent Dubins trajectories. However, when the distances between the initial and intermediate points are close, the error between the angle
(relative to the X-axis) of the line segment connecting point F (
) and point D (
) and the angle
(relative to the X-axis) of the line segment connecting the initial point B (
) and the tangent point D (
) (red dashed line segment) cannot be neglected. Therefore, we cannot directly substitute the coordinates of the initial point B (
) into Equation (12) to solve for the direction angle
(relative to the X-axis) of the intermediate point. In this scenario, the heading angles of the initial and terminal points will affect the values of
and
.
From
Figure 3, it can be observed that when the waypoints are close to each other, the actual
can significantly differ from the original
. In such cases, continuing to use
for calculations would lead to significant errors. It is challenging to obtain a solution for the fully coupled trigonometric equations. To address this issue, we propose a four-point optimization algorithm for calculating the heading angles, aiming to minimize the deviation caused by error terms.
In the scenario where the initial point (
) is close to the midpoint, the heading angle at the initial point will affect the heading angle at the midpoint. In this paper, we introduce an adjacent point (
) to the initial point (
). We preprocess the target point (
) using the optimization algorithm for the scenario where the initial point is far from the midpoint, as described in
Figure 3, to obtain a tangent point
Q1 (
). Then, we use this tangent point
Q1 (
) instead of the initial point (
) as the new target point. We repeat the previous step for the midpoint (
). This process allows us to obtain a compensated heading angle
for the midpoint. As shown in
Figure 4,
represents the angle of the line segment connecting tangent points
Q1 (
) and
Q2 (
), and
represents the angle of the line segment connecting tangent point
Q3 (
) and the terminal point C. O
1 and O
2 are the centers of the two circular trajectories. The solid black line represents the process of solving for the substitute point
Q1, and the dashed black line represents the process of using the substitute point
Q1 instead of the initial point B to solve for the direction angle
of the midpoint.
Algorithm 1. Compensation look-ahead algorithm |
Input: B Output: compensation heading angle 1: Center of circle 2: Distance from point to tangent point 3: Acquiring tangent point 4: Center of circle 5: Distance from point to tangent point 6: Distance from point to tangent point 7: Acquiring tangent point 8: Acquiring tangent point 9: Obtain compensation heading angle 10: end |