Real-Time Trajectory Planning for Fixed-Wing UAVs Based on Exact Convex Relaxation

In this paper, we propose a real-time trajectory planning method for fixed-wing UAVs based on exact convex relaxation. The proposed method consists of two steps: path planning and velocity optimization. In the first step, we design a flight path that avoids obstacles while respecting the dynamic constraints of the fixed-wing UAV. In the second step, we compute the velocity and control profiles along the obstacle-avoidance path. By leveraging Dubins paths for path generation and exact convex relaxation for velocity optimization, our method achieves high computational efficiency and reliability. The mathematical foundations, numerical simulations, and comparative analysis are presented in detail below.

1. Problem Formulation for Fixed-Wing UAV Trajectory Planning

We consider a fixed-wing UAV flying in the horizontal plane. The state variables include position coordinates \((x, y)\), velocity magnitude \(v\), and heading angle \(\psi\). The control variables are thrust \(T\), lift coefficient \(C_L\), and bank angle \(\sigma\). The dynamics are governed by the following equations:

$$ L \cos \sigma = mg $$
$$ L \sin \sigma = m \frac{v^2}{r} $$
$$ \frac{dv}{dt} = \frac{T – D}{m} $$

Here, \(L = 0.5 \rho v^2 S C_L\) is the lift, \(D = 0.5 \rho v^2 S (c_0 + c_1 C_L^2)\) is the drag, \(\rho\) is air density, \(S\) is the reference area, \(m\) is mass, and \(g\) is gravitational acceleration. The turning radius \(r\) is related to the path curvature \(k = 1/r\).

The constraints include bounds on control variables:

$$ T_{\min} \le T \le T_{\max} $$
$$ 0 \le C_L \le C_{L,\max} $$
$$ |\sigma| \le \sigma_{\max} $$

Speed constraints:

$$ v_{\min} \le v \le v_{\max} $$

Obstacle avoidance constraints for circular obstacles with center \((x_{O_i}, y_{O_i})\) and radius \(r_{O_i}\):

$$ (x – x_{O_i})^2 + (y – y_{O_i})^2 \ge r_{O_i}^2 $$

The objective is to minimize the total flight time from a given initial state \((x_0, y_0, v_0, \psi_0)\) to a desired terminal state \((x_f, y_f, v_f, \psi_f)\) while satisfying all constraints. We decompose the problem into two decoupled subproblems: path planning (geometry) and velocity optimization (kinematics and controls).

2. Obstacle-Avoidance Path Planning Using Dubins Paths

2.1 Dubins Paths with Flight Performance Constraints

For a fixed-wing UAV, the minimum turning radius at a given speed \(v\) is derived from the maximum available lateral force. The maximum lateral force is limited by both the lift coefficient and the bank angle:

$$ (L \sin \sigma)_{\max} = \min\left\{ \sqrt{L_{\max}^2 – (mg)^2}, \; mg \tan \sigma_{\max} \right\} $$

with \(L_{\max} = C_{L,\max} \cdot 0.5 \rho v^2 S\). Therefore, the instantaneous minimum turn radius is:

$$ r_{\min}(v) = \frac{m v^2}{(L \sin \sigma)_{\max}(v)} $$

For a Dubins path (CSC type), we define the start and end turning radii as:

$$ r_0 = \frac{m v_0^2}{(L \sin \sigma)_{\max}(v_0)}, \quad r_f = \frac{m v_f^2}{(L \sin \sigma)_{\max}(v_f)} $$

Given the start and end parameters \((x_0, y_0, \psi_0, r_0)\) and \((x_f, y_f, \psi_f, r_f)\), we can generate a Dubins path consisting of two circular arcs and a straight line segment using analytic geometry.

2.2 Single Obstacle Avoidance

When a Dubins path intersects an obstacle, we select an intermediate waypoint on the boundary of the obstacle. The waypoint’s heading is aligned with the original straight segment, and its coordinates are computed as:

$$ x_A = x_O + r_O \cos(\psi_A + \pi/2), \quad y_A = y_O + r_O \sin(\psi_A + \pi/2) $$

where \(\psi_A\) is the azimuth of the straight segment. The turning radius at the waypoint is set to:

$$ r_A = \max\left\{ r_O, \; \frac{m v_c^2}{(L \sin \sigma)_{\max}(v_c)} \right\} $$

If the turning radius is too large to avoid the obstacle, we iteratively decrease the reference speed \(v_c\) from \(v_{\max}\) until a feasible Dubins path is obtained. This search guarantees that the path can pass through narrow gaps between obstacles.

2.3 Multi-Obstacle Environment

We extend the single-obstacle method to multiple obstacles via a sequential procedure:

  1. Connect start and end points with a Dubins path.
  2. Check safety of each segment. For any unsafe segment, identify the closest obstacle to its start point.
  3. Insert a waypoint around that obstacle and reconnect the segments.
  4. Repeat until all segments are safe.

This algorithm requires only simple geometric computations and logical checks, ensuring low computational complexity and high speed. The result is a flyable path consisting of circular arcs and straight lines that fully respects the fixed-wing UAV’s maneuverability limits.

3. Exact Convex Relaxation for Velocity Optimization

3.1 Velocity Optimization Problem

Given the geometric path (position \(x(s), y(s)\), curvature \(k(s)\), and heading \(\psi(s)\) as functions of path length \(s\)), we need to find the optimal speed profile \(v(s)\) and controls \(T(s), C_L(s), \sigma(s)\) that minimize flight time while satisfying dynamics and constraints. We use \(v = v^2\) as a state variable to simplify the dynamics. Using \(d/dt = v \, d/ds\), the speed dynamics become:

$$ \frac{d v}{d s} = \frac{2T}{m} – \frac{c_0 \rho S}{m} v – \frac{4 c_1}{m \rho S} \cdot \frac{L^2}{v} $$

The path-tracking constraints require that the lift components balance gravity and provide the necessary centripetal acceleration:

$$ L \cos \sigma = mg, \quad L \sin \sigma = k m v $$

We define new control variables to linearize the dynamics:

$$ u_1 \triangleq L \cos \sigma, \quad u_2 \triangleq L \sin \sigma, \quad u_3 \triangleq \frac{L^2}{v} $$

Then the dynamics become linear:

$$ \frac{d v}{d s} = \frac{2T}{m} – \frac{c_0 \rho S}{m} v – \frac{4 c_1}{m \rho S} u_3 $$

and the path-tracking constraints become linear equalities:

$$ u_1 = mg, \quad u_2 = k m v $$

The definitions introduce a nonconvex equality constraint:

$$ u_1^2 + u_2^2 = u_3 v $$

We relax this to a convex inequality:

$$ u_1^2 + u_2^2 \le u_3 v $$

To ensure the relaxation is exact (i.e., holds with equality at the optimum), we modify the objective function. The original time-minimizing objective \(J_1 = t_f = \int_{s_0}^{s_f} \frac{1}{\sqrt{v}} ds\) can be replaced by \(J_2 = -\int_{s_0}^{s_f} v \, ds\) (see Theorem 1 in the original paper). However, we further add a regularization term to guarantee tightness of the constraint:

$$ J_3 = -\int_{s_0}^{s_f} v \, ds + c_r \int_{s_0}^{s_f} u_3 \, ds $$

where \(c_r\) is a small positive constant. The resulting convex optimization problem (Problem P2) is:

Problem P2:
\[
\begin{aligned}
\min_{v, T, u_3} \quad & -\int_{s_0}^{s_f} v \, ds + c_r \int_{s_0}^{s_f} u_3 \, ds \\
\text{s.t.} \quad & \frac{d v}{d s} = \frac{2T}{m} – \frac{c_0 \rho S}{m} v – \frac{4 c_1}{m \rho S} u_3, \\
& v(s_0) = v_0^2, \quad v(s_f) = v_f^2, \\
& v_{\min}^2 \le v \le v_{\max}^2, \\
& T_{\min} \le T \le T_{\max}, \\
& u_1^2 + u_2^2 \le u_3 v, \quad u_1 = mg, \quad u_2 = k m v.
\end{aligned}
\]

3.2 Theoretical Proof of Exactness

Under the assumption that the speed bounds and thrust bounds do not become active simultaneously (which is typical for fixed-wing UAVs), we prove via optimal control theory that the relaxed constraint is active almost everywhere. The Hamiltonian and Lagrangian are constructed, and the first-order optimality conditions lead to a contradiction if the constraint is slack on a finite interval. The details follow the approach in the original paper. The key result is:

Theorem 2. Let \(\{v^*(s), T^*(s), u_1^*(s), u_2^*(s), u_3^*(s)\}\) be an optimal solution of Problem P2. Under the assumption that the speed and thrust constraints do not simultaneously become active, we have:

$$ [u_1^*(s)]^2 + [u_2^*(s)]^2 = u_3^*(s) v^*(s) \quad \text{almost everywhere on } [s_0, s_f]. $$

Thus the relaxation is exact, and the solution of Problem P2 is also a solution of the original nonconvex problem (up to the small regularization term).

3.3 Discretization and Solution

We discretize the path into \(N\) intervals (e.g., \(N=100\)) using a uniform grid in \(s\). The linear dynamics are approximated by the forward Euler method. The resulting problem is a second-order cone program (SOCP) that can be solved efficiently by solvers like ECOS. No iteration is required, guaranteeing convergence in one single solve. The flight time is then computed as:

$$ t = \int_{s_0}^{s_f} \frac{1}{\sqrt{v}} ds $$

and the original controls are recovered as:

$$ C_L = \frac{\sqrt{u_1^2 + u_2^2}}{0.5 \rho v^2 S}, \quad \sigma = \arctan\left(\frac{u_2}{u_1}\right) $$

4. The Complete Real-Time Trajectory Planning Framework

Our real-time trajectory planning method for fixed-wing UAVs is summarized in the following steps:

Step Description Computational Cost
1 Input UAV parameters, start/end states, obstacle data. Negligible
2 Generate obstacle-avoidance path using Dubins path method (Sec. 2). Milliseconds (geometry only)
3 Formulate convex velocity optimization problem (Problem P2) with exact convex relaxation (Sec. 3). Problem setup: negligible
4 Discretize and solve the SOCP using ECOS. ~10–20 ms
5 Recover velocity, thrust, lift coefficient, bank angle, and flight time. Negligible
6 Output the complete trajectory (path + control profiles). Total < 30 ms

Because the path planning stage is purely geometric and the velocity optimization is a single convex solve, the entire process requires no iterative trial-and-error. This makes the method suitable for real-time onboard implementation, especially in unknown or dynamic environments where replanning is needed.

5. Simulation Results and Validation

5.1 Multi-Obstacle Environment

We test our method in a scenario with two circular obstacles. The fixed-wing UAV parameters are given in Table 1.

Table 1: Fixed-Wing UAV Parameters
Parameter Value Unit
Mass \(m\) 11.5 kg
Wing area \(S\) 0.84 m²
Zero-lift drag coefficient \(c_0\) 0.0339 –
Induced drag coefficient \(c_1\) 0.1834 –
Max lift coefficient \(C_{L,\max}\) 0.6083 –
Max bank angle \(\sigma_{\max}\) 60 deg
Max speed \(v_{\max}\) 40 m/s
Min speed \(v_{\min}\) 25 m/s
Max thrust \(T_{\max}\) 100 N
Min thrust \(T_{\min}\) 10 N

Start state: \((0, 0, 30\,\text{m/s}, 0^\circ)\); terminal state: \((500, 100, 36\,\text{m/s}, 0^\circ)\). Obstacles: O1 center (180,90) radius 100 m; O2 center (330,20) radius 60 m.

The path planning process generates a three-segment Dubins path I-A-B-F. During the planning of segment A-B, the initial reference speed \(v_c = v_{\max}\) leads to an infeasible turn (circles intersect). By reducing \(v_c\) with step 0.2 m/s, we find a feasible path at \(v_c = 37.2\) m/s with turn radius 81.44 m. The velocity optimization (solved using ECOS with 101 discretization points) yields the speed and control profiles shown in the following table summary.

Table 2: Velocity Optimization Results (Selected Points)
Waypoint Speed (m/s) Thrust (N) Lift coefficient Bank angle (°)
Start I 30.0 100.0 0.320 0.0
After arc 1 32.5 100.0 0.421 15.3
Mid-straight 36.0 85.2 0.300 0.0
Before arc 2 37.2 78.4 0.398 12.8
End F 36.0 50.2 0.310 0.0

All constraints are strictly satisfied. The velocity and thrust show a matching pattern: acceleration uses max thrust, deceleration uses min thrust, and cruising uses intermediate thrust. Importantly, the speed and thrust bounds never become active simultaneously, confirming the assumption for Theorem 2. The relaxed constraint \(u_1^2+u_2^2 \le u_3 v\) is active for the entire trajectory when the regularized objective \(J_3\) is used, whereas using only \(J_2\) leads to slackness. This numerically validates the exactness of the convex relaxation.

5.2 Unknown Obstacle Environment

We simulate a scenario where obstacles are unknown initially. The UAV starts at (0,50) with speed 30 m/s, heading 0°, and aims to reach (800,200) with speed 36 m/s, heading 0°. Two obstacles (O1: radius 140 m at (280,160); O2: radius 90 m at (600,120)) are not known a priori. The UAV has a detection range of 100 m.

At the start, the UAV flies a nominal Dubins path. When it detects the first obstacle at point A, it replans the trajectory online. After reaching point B, it detects the second obstacle and replans again. The final collision-free path is achieved. The computation times for the initial plan, the first replan, and the second replan are 12.18 ms, 11.79 ms, and 11.89 ms, respectively. This demonstrates that the method can safely handle unknown environments with only tens of milliseconds for each update.

5.3 Adaptability and Real-Time Performance Comparison

We perform 101 different mission scenarios with varying start positions (arranged along a rectangular perimeter) and four fixed obstacles. Our method successfully plans a feasible trajectory for all cases. We compare our method against two standard approaches: nonlinear programming (NLP) using pseudospectral discretization and SNOPT, and successive convex optimization (SCP) using iterative linearization. The average computation times and iteration counts are summarized in Table 3.

Table 3: Computational Efficiency Comparison (Average over 101 Cases)
Method Average Iterations Average Computation Time (ms)
Nonlinear Programming (NLP) 11.53 2541.52
Successive Convex Optimization (SCP) 6.62 435.48
Proposed Method (Ours) 1 (single solve) 12.60

The proposed method is over 30 times faster than SCP and over 200 times faster than NLP. The main reasons are: (1) path planning uses only geometry, (2) velocity optimization is cast as one single convex problem with no iterations, and (3) the exact convex relaxation avoids linearization errors or convergence issues.

6. Conclusion

We have presented a real-time trajectory planning method for fixed-wing UAVs that combines Dubins path planning with exact convex relaxation for velocity optimization. By incorporating flight performance constraints directly into the path design and by using a regularized convex reformulation that is provably exact, our method achieves both reliability and efficiency. The numerical simulations confirm that the proposed method can generate safe, dynamically feasible trajectories in multi-obstacle and unknown environments within tens of milliseconds. This makes it highly suitable for onboard real-time applications such as surveillance, reconnaissance, and combat missions. Future work will extend the framework to three-dimensional environments and consider moving obstacles.

Scroll to Top