The proliferation of low-altitude economic activities, including private, commercial, and public services, has brought unmanned aerial vehicles (UAVs) to the forefront of modern aviation. The ability to autonomously plan safe and efficient flight paths is a fundamental requirement for UAV applications such as logistics delivery, emergency rescue, and urban inspection. However, path planning in complex environments is computationally intensive, especially when multiple constraints and real-time adaptability are required. This work focuses on designing lightweight optimization algorithms that balance computational complexity and solution quality for both single-UAV offline planning and multi-UAV real-time cooperative planning. By decomposing global optimization problems into local sub-problems and hybridizing different planning strategies, I propose methods that significantly reduce computational burden while maintaining near-optimal performance. This article presents the mathematical formulations, algorithmic details, and simulation results of the proposed lightweight approaches.
1. Introduction
Unmanned aerial vehicles (UAVs) are aircraft that operate without an onboard human pilot, offering high flexibility, stealth, and adaptability in complex and dangerous environments. The global UAV market has expanded rapidly, with registered civilian UAVs in China surpassing two million units. In military applications, UAVs perform reconnaissance, surveillance, and precision strike missions, substantially reducing risks to human personnel. In civilian sectors, UAVs enable aerial mapping, last-mile delivery, power line inspection, precision agriculture, and disaster response, greatly improving operational efficiency and reducing costs. The execution of these missions depends critically on flight path planning, which aims to generate collision-free paths from start poses to goal poses while satisfying flight dynamics, safety margins, and mission objectives.
Path planning algorithms can be broadly divided into offline and online approaches. Offline planning uses complete environmental information to compute an optimal or near-optimal path before takeoff, emphasizing global optimality over speed. Online planning, also known as real-time planning, relies on sensor feedback during flight to dynamically adjust the path, prioritizing rapid response and adaptability in partially known or unknown environments. Both scenarios require careful management of computational resources; heavy optimization algorithms often yield high-quality paths but suffer from high time complexity, which is unsuitable for real-time applications. Lightweight optimization, therefore, aims to achieve a trade-off between path quality and computational efficiency.
In this work, I investigate lightweight optimization algorithms from two perspectives. First, for single-UAV offline path planning, I propose a hybrid method combining RRT (Rapidly-exploring Random Tree), Dubins curves, and Particle Swarm Optimization (PSO) to generate smooth, dynamics-compliant paths with minimal length. This method decomposes the global path optimization into local sub-problems, using RRT to find a feasible initial route, greedy pruning to remove redundant waypoints, and PSO to fine-tune the parameters of continuous Dubins curves. The result is a path that approximates the global optimum with far lower computational cost than a full global optimization. Second, for multi-UAV real-time path planning, I propose a distributed-hybrid framework based on Model Predictive Control (MPC). The UAV swarm is dynamically clustered using K-means, with centralized planning inside each cluster and distributed coordination between clusters. This design balances global optimality and real-time responsiveness. Simulation results demonstrate the effectiveness of both methods in reducing path length and computational time compared to conventional approaches.
2. Problem Formulation
I first describe the common environment models and path planning constraints used throughout this work. The task space is defined as a two-dimensional plane, because most low-altitude missions maintain a constant altitude. Obstacles are modeled as circular regions with known or unknown centers and radii. For a given UAV, the state vector comprises its planar coordinates and heading angle:
$$
\mathbf{X}_k^i = \begin{bmatrix} x_k^i \\ y_k^i \\ \theta_k^i \end{bmatrix}
$$
The control input is composed of linear velocity and angular velocity:
$$
\mathbf{u}_k^i = \begin{bmatrix} v_k^i \\ \omega_k^i \end{bmatrix}
$$
The discrete-time kinematic model of the UAV is expressed as a nonlinear unicycle model:
$$
\mathbf{X}_{k+1}^i = \mathbf{X}_k^i + \Delta t \begin{bmatrix} v_k^i \cos(\theta_k^i + \omega_k^i \Delta t) \\ v_k^i \sin(\theta_k^i + \omega_k^i \Delta t) \\ \omega_k^i \end{bmatrix}
$$
where \(\Delta t\) is the time step. The minimum turning radius constraint must be respected:
$$
r_{\min} \le \frac{v}{g \tan \theta_{\max}}
$$
Here, \(v\) is the flight speed, \(g\) is gravitational acceleration, and \(\theta_{\max}\) is the maximum banking angle. The objective is to find a feasible path from start pose \(\mathbf{Q}_s\) to goal pose \(\mathbf{Q}_g\) while minimizing a selected cost function, such as total path length, and satisfying collision avoidance and dynamic constraints.
3. Lightweight Trajectory Optimization for Single UAV
3.1 Overview of the Proposed Approach
Conventional path planning methods, such as RRT, generate piecewise linear paths with sharp corners and discontinuous curvature. These paths violate the kinematic constraints of fixed-wing or even multirotor UAVs, causing unstable flight controls. To address this issue, I propose a three-stage method: first, the RRT algorithm is employed to obtain an initial collision-free path; second, a greedy pruning procedure removes redundant waypoints; finally, Dubins curves are used to connect the pruned waypoints smoothly, and the PSO algorithm optimizes the curve parameters to minimize path length. The key innovation is to convert a global complex optimization into a sequence of local optimizations, thus greatly reducing computational expense while preserving near-global optimality.
3.2 RRT and Greedy Pruning
The RRT algorithm builds a tree by randomly sampling configurations in the free space. Starting from the root \(\mathbf{q}_{start}\), the tree iteratively extends a new node \(\mathbf{q}_{new}\) toward a randomly sampled node \(\mathbf{q}_{rand}\) if the connecting edge is collision-free. This process repeats until the goal is reached within a tolerance. The output is a path composed of a sequence of \(N\) discrete waypoints:
$$
\mathcal{P} = \{ \mathbf{P}_1, \mathbf{P}_2, \dots, \mathbf{P}_N \}
$$
However, the RRT path contains many redundant waypoints. I apply a greedy pruning algorithm to remove unnecessary intermediate nodes. Starting from the first waypoint, the algorithm attempts to connect every subsequent waypoint directly; if the connection is collision-free, the intermediate waypoints are deleted. This reduces the number of waypoints to \(N’\) and shortens the total path length significantly. Table 1 shows an example of length reduction after pruning in a simulation environment of size \(1000 \times 1000\).
| Stage | Number of waypoints | Path length | Reduction |
|---|---|---|---|
| RRT generated | 31 | 1534 | – |
| After greedy pruning | 4 | 1278 | 16.7% |
3.3 Dubins Curve Smoothing
Each waypoint \(\mathbf{P}_i\) is augmented with a heading angle \(\theta_i\), forming a pose \(\mathbf{Q}_i = (\mathbf{P}_i, \theta_i)\). I connect consecutive poses with Dubins curves. A Dubins curve is the shortest path between two oriented points in the plane, under a minimum turning radius \(R\). It consists of three segments selected from left-turn (L), right-turn (R), and straight (S). In this work, I consider four types: LSL, LSR, RSL, and RSR. The total length of a Dubins curve can be computed as:
$$
L_{\mathrm{Dubins}}(\mathbf{Q}_s, \mathbf{Q}_g, R) = l_s + l_m + l_g
$$
where \(l_s\) and \(l_g\) are the arc lengths of the initial and terminal turns, and \(l_m\) is the straight segment length. The centers of the turning circles are given by:
$$
\begin{bmatrix} x_cs \\ y_cs \end{bmatrix} = \begin{bmatrix} x_s + R \xi_s \sin \theta_s \\ y_s – R \xi_s \cos \theta_s \end{bmatrix}
$$
$$
\begin{bmatrix} x_cg \\ y_cg \end{bmatrix} = \begin{bmatrix} x_g + R \xi_g \sin \theta_g \\ y_g – R \xi_g \cos \theta_g \end{bmatrix}
$$
where \(\xi_s, \xi_g \in \{-1, 1\}\) represent left or right turns. The angles of the arcs are computed using trigonometric relationships, and the total length depends on the turn directions and the circle distance \(l_c = \| \mathbf{C}_s – \mathbf{C}_g \|\).
For a path consisting of \(N’\) waypoints, I concatenate \(N’-1\) Dubins curves. The total path length is:
$$
L_{\mathrm{total}} = \sum_{i=1}^{N’-1} L_{\mathrm{Dubins}}(\mathbf{Q}_i, \mathbf{Q}_{i+1}, R_i)
$$
where \(R_i\) is the turning radius of the \(i\)-th curve, which must satisfy \(R_i \ge r_{\min}\).
3.4 PSO-Based Parameter Optimization
To minimize \(L_{\mathrm{total}}\), I use Particle Swarm Optimization to optimize three groups of variables: the intermediate poses \(\mathbf{Q}_i = (x_i, y_i, \theta_i)\) for \(i=2,\dots,N’-1\), the turn direction parameters \(\xi_{i,1}, \xi_{i,2}\), and the radii \(R_i\). The search space for the positions is a disc centered at the original waypoint with radius \(R_{p,i}\), and the heading angle is constrained to a range that aligns with the direction toward the next waypoint. The PSO velocity and position update equations are:
$$
v_{i,d}^{t+1} = \omega v_{i,d}^t + c_1 r_1 (p_{i,d}^t – x_{i,d}^t) + c_2 r_2 (g_d^t – x_{i,d}^t)
$$
$$
x_{i,d}^{t+1} = x_{i,d}^t + v_{i,d}^{t+1}
$$
where \(\omega\) is the inertia weight, \(c_1,c_2\) are acceleration coefficients, and \(r_1,r_2\) are uniform random numbers. The fitness function is simply \(L_{\mathrm{total}}\) provided the path remains collision-free. Table 2 lists the PSO parameters used in the simulations.
| Parameter | Value |
|---|---|
| Population size | 50 |
| Number of iterations | 100 |
| Cognitive coefficient \(c_1\) | 2 |
| Social coefficient \(c_2\) | 2 |
| Inertia weight \(\omega\) | 0.8 |
| Radius range \(R_i\) | \([r_{\min}, 4r_{\min}]\) |
| Safety distance \(d_{\min}\) | 5 |
3.5 Simulation Results and Comparisons
I conducted simulations in a \(1000 \times 1000\) task space with multiple circular obstacles. The start and goal poses were set as \((50,50,\pi/4)\) and \((950,950,\pi/6)\), respectively. Figure 1 illustrates the three stages of the proposed method: RRT path, pruned path, and Dubins-smoothed path. The path length after each stage is shown in Table 3.
| Stage | Path length |
|---|---|
| RRT | 1534 |
| Greedy pruning | 1278 |
| Dubins + PSO | 1237 |
I also investigated the influence of the safety distance \(d_{\min}\). Smaller safety distances enlarge the search space and allow shorter paths, but may reduce safety margins. Table 4 shows results for three different safety distances in a scenario with 10 obstacles.
| Safety distance \(d_{\min}\) | Path length |
|---|---|
| 15 | 1349 |
| 10 | 1325 |
| 5 | 1320 |
To further assess the performance of the Dubins-based smoothing, I compared it with B-spline smoothing and a recently published RRT*-based method. The average path lengths over ten independent runs for different obstacle counts are summarized in Table 5.
| Number of obstacles | Proposed Dubins method | B-spline | Literature method |
|---|---|---|---|
| 5 | 1234 | 1388 | 1403 |
| 10 | 1355 | 1497 | 1509 |
| 15 | 1046 | 1203 | 1235 |
The results indicate that the proposed method reduces the average path length by roughly 11.5% compared to B-spline and by a greater margin compared to the literature method. Importantly, the generated path satisfies the first-order smoothness and the minimum turning radius constraints, which are critical for fixed-wing UAVs.
4. Real-Time Multi-UAV Path Planning Based on MPC
4.1 Model and Problem Setup
For multi-UAV scenarios, I consider a swarm of \(N_{\mathrm{UAV}}\) unmanned aerial vehicles. Each vehicle \(i\) follows the same unicycle model described in Section 2. The environment is assumed unknown, but each UAV has a sensor with a circular detection range \(R_{\mathrm{sensor}}\). The UAV can only perceive obstacles inside this range. The objective is to plan a collision-free path from each UAV’s start pose to its goal pose, while ensuring inter-vehicle separation and obstacle avoidance.
4.2 Transition Pose Selection
Since the complete environment is not known, at each time step the UAV computes a transition (intermediate) pose that lies along the line from its current position to the final goal. The transition position is chosen to minimize the distance to the goal while avoiding detected obstacles. The heading angle of the transition pose is set to point toward the goal:
$$
\theta_{\mathrm{trans}} = \operatorname{atan2}(y_{\mathrm{goal}} – y_{\mathrm{trans}}, x_{\mathrm{goal}} – x_{\mathrm{trans}})
$$
The transition pose is then used as the temporary goal for the MPC optimization. As the UAV moves, its sensor detects new obstacle parts. If only a segment of an obstacle is visible, the UAV can estimate the full circular obstacle using least squares on the detected boundary points. The estimated center and radius are:
$$
(x_{\mathrm{obs}}, y_{\mathrm{obs}}) = \arg\min \sum_{i=1}^{n} \left[ (x_i – x_{\mathrm{obs}})^2 + (y_i – y_{\mathrm{obs}})^2 – r_{\mathrm{obs}}^2 \right]^2
$$
$$
r_{\mathrm{obs}} = \frac{1}{n} \sum_{i=1}^{n} \sqrt{(x_i – x_{\mathrm{obs}})^2 + (y_i – y_{\mathrm{obs}})^2}
$$
where \(n\) is the number of detected points on the obstacle boundary. This generates a set of obstacle information that is used by the MPC to formulate avoidance constraints.
4.3 MPC Formulation
Model Predictive Control is employed to compute the optimal control input sequence over a finite prediction horizon \(N_p\). At each time step, the following objective is minimized:
$$
J = w_1 \| \mathbf{X}_{N_p} – \mathbf{X}_{\mathrm{goal}} \| + w_2 \| \Delta v \| + w_3 \| \Delta \omega \| + w_4 \| \mathbf{u}_k – \mathbf{u}_{k-1} \|
$$
subject to dynamic and safety constraints:
$$
v_{\min} \le v_k \le v_{\max}, \quad \omega_{\min} \le \omega_k \le \omega_{\max}
$$
$$
\dot{v}_{\min} \le a_v \le \dot{v}_{\max}, \quad \dot{\omega}_{\min} \le a_\omega \le \dot{\omega}_{\max}
$$
$$
\| \mathbf{x}_k – \mathbf{x}_{\mathrm{obs},m} \| \ge r_{\mathrm{obs},m} + r_{\mathrm{safe}}, \quad \forall m
$$
$$
\| \mathbf{x}_k^i – \mathbf{x}_k^j \| \ge d_{\mathrm{safe}}, \quad \forall i \ne j
$$
The first two constraints bound the linear and angular velocities and their accelerations. The next constraint ensures the UAV maintains a safe distance from each obstacle. The last constraint enforces inter-UAV separation. The resulting nonlinear optimization problem is solved using the interior-point method. Only the first control input is applied, and the horizon is receded.
4.4 Hybrid Grouping Strategy
Distributed planning treats every UAV independently, which offers high real-time performance but often leads to suboptimal paths because the vehicles only coordinate locally. Centralized planning combines all UAVs into one optimization, which yields superior paths but becomes computationally prohibitive as the number of UAVs increases. To balance these extremes, I propose a hybrid strategy that dynamically partitions the swarm into several groups. Inside each group, centralized MPC is used; between groups, only inter-group distance constraints are imposed, resulting in distributed coordination.
The group count is determined from the spatial distribution of the UAVs. I compute the mean position vector and the covariance matrix:
$$
\bar{\mathbf{x}} = \frac{1}{n} \sum_{i=1}^{n} \mathbf{x}_i
$$
$$
\mathbf{A} = \frac{1}{n-1} \sum_{i=1}^{n} (\mathbf{x}_i – \bar{\mathbf{x}}) (\mathbf{x}_i – \bar{\mathbf{x}})^T
$$
Let \(\lambda_{\max}\) be the largest eigenvalue of \(\mathbf{A}\). The number of groups \(m\) is determined by:
$$
m = \begin{cases} n, & \lambda_{\max} > b – b_0 \\ 1, & \lambda_{\max} < a + b_0 \\ \operatorname{round}\left( 1 + (n-1) \frac{\lambda_{\max} – (a + b_0)}{(b – b_0) – (a + b_0)} \right), & \text{otherwise} \end{cases}
$$
Here \(a\), \(b\), and \(b_0\) are tunable parameters that reflect the desired granularity. After determining \(m\), the K-means clustering algorithm assigns each UAV to its nearest cluster center. The cluster centers are updated iteratively to minimize the intra-cluster squared distance:
$$
J_{\mathrm{cluster}} = \sum_{k=1}^{m} \sum_{i \in C_k} \| \mathbf{x}_i – \mathbf{c}_k \|^2
$$
where \(\mathbf{c}_k\) is the centroid of cluster \(C_k\).
Re-grouping is performed every fixed time interval \(T\). Let \(k\) be a positive integer, and the re-grouping times are \(t = kT\). This dynamic adaptation allows the system to respond to changing spatial relationships as the UAVs move.
4.5 Simulation Results
I simulated a swarm of four UAVs in a \(1000 \times 1000\) environment with ten circular obstacles. The start and goal poses of the UAVs were chosen to ensure crossing trajectories, which force the vehicles to interact with each other. The relevant parameters are shown in Table 6.
| Parameter | Value |
|---|---|
| Time step \(\Delta t\) | 0.1 s |
| Prediction horizon \(N_p\) | 15 |
| Obstacle safety distance | 5 |
| Inter-UAV safety distance \(d_{\mathrm{safe}}\) | 100 |
| Linear acceleration limits | \([-20, 20]\) |
| Angular acceleration limits | \([-0.3, 0.3]\) |
| Linear velocity range | \([10, 80]\) |
| Angular velocity range | \([-0.6, 0.6]\) |
I compared three strategies: fully distributed, fully centralized, and the proposed hybrid strategy. The algorithm runtime (i.e., computational time) and the average arrival time of all UAVs were recorded. Table 7 presents the results from three different scenarios.
| Scenario | Algorithm runtime (seconds) | Average arrival time (seconds) | ||||
|---|---|---|---|---|---|---|
| Distributed | Centralized | Hybrid | Distributed | Centralized | Hybrid | |
| 1 | 56.23 | 148.64 | 95.97 | 20.35 | 15.82 | 17.83 |
| 2 | 77.39 | 153.37 | 106.17 | 30.15 | 18.85 | 24.51 |
| 3 | 83.54 | 179.48 | 122.36 | 38.92 | 22.73 | 31.34 |
From the data, the hybrid method reduces the average arrival time by about 16.9% compared to the distributed method, while reducing the algorithm runtime by about 32.7% relative to the centralized method. This demonstrates that the hybrid strategy achieves a favorable compromise between computational efficiency and global path quality.
I also investigated the effect of the re-grouping interval \(T\). Different intervals (10, 20, 30, and 40 time steps) were tested in a fixed scenario. The resulting algorithm runtime and average arrival time are shown in Table 8.
| Grouping interval \(T\) | Algorithm runtime (s) | Average arrival time (s) |
|---|---|---|
| 10 | 85.13 | 17.88 |
| 20 | 86.88 | 18.05 |
| 30 | 89.10 | 18.10 |
| 40 | 90.46 | 18.25 |
These results suggest that smaller intervals provide more frequent re-grouping, which generally improves performance by allowing the system to adapt quickly to changing spatial layouts. However, in some obstacle configurations, the relationship is not monotonic, because a trade-off exists between regrouping overhead and the benefit of adaptation. The optimal interval depends on the specific distribution of UAVs and obstacles.
5. Conclusion
This article presents lightweight optimization algorithms for both single-UAV and multi-UAV path planning. For the single-UAV case, the proposed RRT-Dubins-PSO method converts a global path optimization into a sequence of local refinements, achieving a significant reduction in path length while satisfying the first-order smoothness and turning radius constraints. For the multi-UAV case, the hybrid MPC framework dynamically adjusts the balance between centralized and distributed planning through K-means-based grouping. Simulation results show that the hybrid approach outperforms distributed planning in arrival time and is much faster than centralized planning while retaining near-global optimality. These methods demonstrate that lightweight optimization is feasible by exploiting problem structure and combining complementary algorithms, providing a practical pathway for real-time UAV applications in complex environments.