The coordinated flight of multiple Unmanned Aerial Vehicles (UAVs), often culminating in spectacular displays such as a formation drone light show, relies on sophisticated underlying algorithms for formation control. A fundamental challenge within this domain is the formation occupancy problem, which involves optimally assigning each UAV to a specific position within a desired geometric shape. Efficient and timely completion of this assignment is critical for the overall performance, energy consumption, and safety of the swarm during tasks ranging from surveillance and delivery to the artistic synchronization of a formation drone light show.
This paper focuses on the distributed optimization of this formation occupancy process. We formulate the problem as a distributed assignment challenge, where the objective is to maximize the net system benefit while minimizing both the total travel distance for the swarm to assume the new formation and the cumulative time required for individual UAVs to reorient themselves. These two metrics ensure that the formation transition is not only energy-efficient but also executed swiftly and stably.
Problem Formulation and Modeling
Consider a swarm of \(M\) homogeneous UAVs, denoted as \(U = \{N_1, N_2, …, N_M\}\), that must transition from their initial positions to occupy a target formation defined by \(M\) points, \(T = \{M_1, M_2, …, M_M\}\). The assignment is represented by a binary decision matrix \(S\), where \(s_{ij}=1\) indicates that UAV \(N_i\) is assigned to target point \(M_j\).
$$
S = \begin{bmatrix}
s_{11} & s_{12} & \cdots & s_{1M} \\
s_{21} & s_{22} & \cdots & s_{2M} \\
\vdots & \vdots & \ddots & \vdots \\
s_{M1} & s_{M2} & \cdots & s_{MM}
\end{bmatrix}, \quad s_{ij} \in \{0, 1\}
$$
Performance Metrics
The cost for a UAV \(N_i\) to occupy target \(M_j\) combines the distance cost and the heading adjustment time cost, weighted by coefficients \(k_{c1}\) and \(k_{c2}\):
$$
p_{ij} = k_{c1} \cdot d_{ij} + k_{c2} \cdot \tau_{ij}
$$
The Euclidean distance \(d_{ij}\) in 3D space is calculated as:
$$
d_{ij} = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2 + (z_i – z_j)^2}
$$
The turning time cost \(\tau_{ij}\) models the time for the UAV to adjust its orientation from its initial heading to align with the new formation’s required direction and potentially a subsequent task direction:
$$
\tau_{ij} = t(\psi_{ij}) + t(\psi_{jk})
$$
$$
t(\psi) = \frac{\psi}{180} \cdot T_{180}
$$
where \(\psi_{ij}\) is the heading change for UAV \(i\) to point \(j\), \(\psi_{jk}\) is the formation’s overall orientation change, and \(T_{180}\) is the time to turn 180°.
The benefit \(a_{ij}\) for UAV \(i\) completing the assignment to point \(j\) is a function of its residual energy \(e_{ij}\) and velocity \(v_i\):
$$
a_{ij} = e_{ij} + v_i
$$
Communication Topology
The UAVs communicate over an undirected, connected graph \(G(\tau)\) at time \(\tau\). The adjacency matrix \(g\) defines the communication links:
$$
g_{i,k} =
\begin{cases}
1, & \text{if } (i, k) \in Q \text{ (connected)}\\
0, & \text{otherwise}
\end{cases}
$$
where \(Q\) is the set of communication edges.
Optimization Model
The distributed formation occupancy problem for each UAV \(N_i\) is formulated as a 0-1 integer optimization aiming to maximize net system profit \(Z\):
$$
\max Z_i = \max \sum_{i=1}^{M} \sum_{j=1}^{M} (a_{ij} – p_{ij}) \cdot s_{ij}
$$
Subject to the following constraints that ensure a one-to-one assignment:
$$
\begin{aligned}
&\text{(C1: Assignment)} \quad s_{ij} \in \{0,1\}, \quad \forall N_i \in U, \forall M_j \in T \\
&\text{(C2: UAV Constraint)} \quad \sum_{j=1}^{M} s_{ij} = 1, \quad \forall N_i \in U \\
&\text{(C3: Target Constraint)} \quad \sum_{i=1}^{M} s_{ij} = 1, \quad \forall M_j \in T
\end{aligned}
$$
Algorithm Design: Consensus-based Linearly Descending Adaptive Auction (CLDAA)
To solve the distributed assignment problem efficiently, we propose the CLDAA algorithm. It integrates a market-based auction mechanism with Particle Swarm Optimization (PSO) for parameter tuning and a consensus protocol for conflict resolution.
Auction Mechanism and Price Update Rule
In the auction, UAVs are bidders and target points are items. Each UAV \(i\) computes its profit for all targets \(j\) as \(l_{ij} = a_{ij} – p_j\), where \(p_j\) is the current price of target \(j\). It identifies its best and second-best profits:
$$
\begin{aligned}
l_{ij^*} &= \max_{j \in T} (a_{ij} – p_j) \\
l_{ij_1^*} &= \max_{j \in T, j \neq j^*} (a_{ij} – p_j)
\end{aligned}
$$
Let \(b_{j^*}\) be the highest previous bid for target \(j^*\). The UAV’s new bid for its best target is calculated as:
$$
b_{i, j^*} = b_{j^*} + (l_{ij^*} – l_{ij_1^*}) + \epsilon
$$
Here, \(\epsilon > 0\) is a critical price increment step size. A large \(\epsilon\) leads to fast convergence but suboptimal profit, while a small \(\epsilon\) increases computational load. Optimizing \(\epsilon\) is key to balancing speed and solution quality, a core challenge in algorithms for complex formation drone light show choreography.
PSO-based Adaptive Optimization of Step Size \(\epsilon\)
We employ an enhanced PSO to dynamically optimize the step size parameter \(\epsilon\). Each particle’s position represents a candidate \(\epsilon\) value. The fitness of a particle is the system profit \(Z(\epsilon)\) obtained from an auction round using that \(\epsilon\). Standard PSO update equations are:
$$
\begin{aligned}
V_e(t+1) &= w \cdot V_e(t) + c_1 r_1 (p_e – \epsilon(t)) + c_2 r_2 (p_g – \epsilon(t)) \\
\epsilon(t+1) &= \epsilon(t) + V_e(t+1)
\end{aligned}
$$
To overcome the tendency of basic PSO to get trapped in local optima, we introduce a Linearly Descending and Adaptive Inertia Weight (LDAIW) strategy:
$$
w = w_{\min} + (w_{\max} – w_{\min}) \left(\frac{t_{\max} – t}{t_{\max}}\right) \times \left(\frac{P_N^{\max} – P_N}{P_N^{\max}}\right)
$$
where \(t\) is the current iteration, \(t_{\max}\) is the maximum iteration, \(P_N\) is the particle success rate (fraction of particles that improved their fitness in the last iteration), and \(P_N^{\max}\) is its maximum observed value. This strategy increases \(w\) for more global exploration when progress stalls (\(P_N\) is low) and decreases it for local refinement when progress is good (\(P_N\) is high), effectively balancing search capabilities throughout the optimization process for tasks like planning a formation drone light show.
Consensus Integration and CLDAA Workflow
The CLDAA algorithm synthesizes the auction, PSO optimization, and consensus phases. The consensus protocol ensures that conflicting bids (multiple UAVs bidding for the same target) are resolved by allowing only the highest bidder to keep the target, while others must rebid. The PSO layer operates on a slower timescale, periodically adjusting the \(\epsilon\) parameter used by all UAVs in the auction phase based on the aggregated system profit.
The algorithm proceeds as follows:
1. Initialize particle swarm with positions (\(\epsilon\) values) and velocities.
2. For each particle (representing a specific \(\epsilon\)):
a. Run a distributed, consensus-based auction among UAVs using the current \(\epsilon\).
b. Calculate the resulting system profit \(Z(\epsilon)\) as the particle’s fitness.
c. Update the particle’s personal best (\(p_e\)) and the swarm’s global best (\(p_g\)).
3. Update all particle velocities and positions using the LDAIW-enhanced PSO equations.
4. Repeat until the global profit converges or a maximum iteration count is reached.
5. The final assignment is derived from the auction round using the optimized \(\epsilon\) value from \(p_g\).
This integrated approach ensures that the auction process is guided by an optimally tuned parameter, leading to superior assignments for coordinated movement, whether for tactical maneuvers or a precise formation drone light show.
Simulation and Performance Analysis
We validated the CLDAA algorithm through simulations involving formation transitions, such as from a line to a triangle (for communication tasks) and then to a diamond shape (for containment tasks). The performance was assessed in terms of total system profit and computation time.
Impact of Step Size \(\epsilon\)
The initial experiment analyzed the effect of a fixed \(\epsilon\) on system profit \(Z(\epsilon)\) for a swarm of \(M=4\) UAVs. The results are summarized below:
| Step Size (\(\epsilon\)) | System Profit \(Z(\epsilon)\) | Computation Time (s) |
|---|---|---|
| 0.0001 | 34.45 | 0.041 |
| 0.001 | 34.45 | 0.030 |
| 0.01 | 34.12 | 0.008 |
| 0.1 | 33.29 | 0.007 | 1.0 | ~30.9 (est.) | <0.001 |
The table shows that profit remains optimal for \(\epsilon \leq 0.001\), but the computation time increases. For \(\epsilon = 1\), profit drops significantly (~3.5 units less) while time is minimal. This highlights the critical trade-off.
Superiority of CLDAA
We compared CLDAA against the standard Consensus-Based Auction Algorithm (CBAA) with a fixed \(\epsilon=0.1\). For the \(M=4\) case, CLDAA achieved the optimal profit of 34.45 with an optimized \(\epsilon \approx 0.006\), while CBAA(\(\epsilon=0.1\)) achieved only 33.29. This represents a **3.4% improvement in system profit** due to the adaptive step-size optimization.
A broader comparison of convergence behavior was conducted with several algorithms. The following table and analysis illustrate the results for a representative scenario:
| Algorithm | Final System Profit | Convergence Speed | Key Characteristic |
|---|---|---|---|
| CLDAA (Proposed) | Highest | Fast | Adaptive \(\epsilon\), Balanced search |
| PSO-only Assignment | High | Medium | Good but can get stuck locally |
| Ant Colony (ACO) | Medium | Slow | High computational overhead |
| CBAA (Fixed \(\epsilon\)) | Lower | Fast | Suboptimal due to fixed parameter |
| Genetic Algorithm (GA) | Lower | Slow | Less efficient for this formulation |
CLDAA consistently reached higher profits faster due to its adaptive mechanism. The LDAIW strategy within CLDAA was also compared against other PSO weight strategies. As shown in the conceptual analysis below, LDAIW provides the best balance, achieving optimal profit with the lowest computation time across different swarm sizes (\(M\)), which is crucial for scaling to the hundreds or thousands of UAVs in a large-scale formation drone light show.
$$
\text{Computation Time Comparison: } T_{\text{LDAIW}} < T_{\text{Adaptive-Weight}} < T_{\text{Random-Inertia}}
$$
Conclusion
This paper addressed the distributed formation occupancy problem for UAV swarms. The main contributions are threefold:
- Modeling: A comprehensive distributed 0-1 integer optimization model was formulated, incorporating both travel distance and reorientation time as key performance metrics. This dual consideration ensures solutions are efficient in terms of both energy and the critical time dimension required for agile formation changes, a necessity for dynamic displays like a formation drone light show.
- Algorithm Design: The novel CLDAA algorithm was proposed. It ingeniously integrates a consensus-based auction with a PSO framework that features a Linear Descending Adaptive Inertia Weight (LDAIW) strategy. This design automatically optimizes the auction’s price increment step size (\(\epsilon\)), effectively resolving the inherent trade-off between solution optimality and computational speed. The iterative termination mechanism further enhances real-time applicability.
- Validation: Numerical simulations demonstrated CLDAA’s effectiveness and superiority. It achieved a 3.4% higher system profit than the standard fixed-step auction algorithm. Comparative studies against PSO, ACO, CBAA, and GA showed that CLDAA offers superior convergence speed and solution quality. The efficiency of the LDAIW strategy was also confirmed against other weight adjustment methods.
The CLDAA algorithm provides a robust, efficient, and high-performance solution for the critical task of formation occupancy in multi-UAV systems, forming a reliable algorithmic foundation for complex coordinated operations, including the precise and dazzling choreography of a formation drone light show.