In recent years, drone shows and drone performances have gained immense popularity in various entertainment and exhibition settings. The demand for real-time interactivity and personalized audience experiences in drone performances has driven the need for efficient trajectory planning methods. Traditional approaches often struggle with computational complexity and scalability when dealing with large drone swarms. This paper addresses these challenges by proposing a novel distributed model predictive control (DMPC) framework for offline trajectory generation in drone swarms. Our method enables rapid formation changes while ensuring collision avoidance and optimal flight efficiency, making it ideal for interactive drone shows.
The core of our approach lies in modeling the drone formation change as a point-to-point transition problem. We consider a swarm of N drones operating in a 3D space, each modeled with double-integrator dynamics. The position $p_i[k]$, velocity $v_i[k]$, and acceleration $a_i[k]$ of drone i at time step k are governed by the discrete-time equations:
$$ p_i[k+1] = p_i[k] + h v_i[k] + \frac{h^2}{2} a_i[k] $$
$$ v_i[k+1] = v_i[k] + h a_i[k] $$
where h is the discrete time step duration. Physical constraints are imposed to reflect the drones’ capabilities:
$$ a_{\min} \leq a_i[k] \leq a_{\max} $$
$$ p_{\min} \leq p_i[k] \leq p_{\max} $$
Collision avoidance is critical in drone performances. We model the collision boundary as an ellipsoid using a scaling matrix $\Theta = \text{diag}(a, b, c)$ with $a = b = 1$ and $c > 1$. The constraint between drones i and j is:
$$ \| \Theta^{-1} (p_i[k] – p_j[k]) \|_n \geq r_{\min} $$
where $n = 2$ for the ellipsoid degree, and $r_{\min}$ is the minimum distance in the xy-plane. The vertical safety distance is $r_{z,\min} = c r_{\min}$.
Our DMPC algorithm operates in a distributed manner, where each drone independently solves an optimization problem while sharing predictions with neighbors. The synchronous algorithm involves the following steps at each time step $k_t$:
- Detect potential collisions using shared predictions from the previous step.
- Construct an optimization problem with state and input constraints, adding collision constraints only if risks are identified.
- Solve for the optimal control sequence and apply the first input to the drone model.
- Share the updated state predictions with the swarm.
The prediction model for each drone over a horizon K is linear. Let $\hat{x}_i[k|k_t]$ denote the predicted state at $k_t + k$. The dynamics are compactly represented as:
$$ \hat{x}_i[k+1|k_t] = A \hat{x}_i[k|k_t] + B \hat{u}_i[k|k_t] $$
where $A$ and $B$ are matrices derived from the discrete-time model. The position sequence $P_i$ is an affine function of the input sequence $U_i$:
$$ P_i = A_0 X_{0,i} + \Lambda U_i $$
Here, $A_0$ and $\Lambda$ are matrices that propagate the initial state $X_{0,i}$ and inputs, respectively.
The objective function $J_i(U_i)$ for each drone combines three penalties:
- Terminal gap penalty: Minimizes the difference between the predicted position and the target $p_{d,i}$ over the last $\kappa$ steps:
$$ J_{e,i} = U_i^T (\Lambda^T \tilde{Q} \Lambda) U_i – 2 (P_{d,i}^T \tilde{Q} \Lambda – (A_0 X_{0,i})^T \tilde{Q} \Lambda) U_i $$
where $\tilde{Q}$ is a positive definite block-diagonal matrix.
- Control cost penalty: Reduces control effort:
$$ J_{u,i} = U_i^T \tilde{R} U_i $$
with $\tilde{R}$ as a weighting matrix.
- Input change penalty: Ensures smooth acceleration profiles:
$$ J_{\delta,i} = U_i^T (\Delta^T \bar{S} \Delta) U_i – 2 (U_i^{*T} \bar{S} \Delta) U_i $$
where $\Delta$ is a matrix representing input differences, and $U_i^*$ includes the previous input.
The combined cost is:
$$ J_i(U_i) = J_{e,i} + J_{u,i} + J_{\delta,i} $$
Physical constraints are formulated as linear inequalities:
$$ A_{\text{in}} U_i \leq b_{\text{in}} $$
For collision avoidance, we introduce an on-demand strategy with soft constraints. If a collision is predicted with drone j at time $k_{c,i}$, the constraint becomes:
$$ \nu_{ij}^T \hat{p}_i[k_{c,i}|k_t] – \epsilon_{ij} \xi_{ij} \geq \rho_{ij} $$
where $\epsilon_{ij} \leq 0$ is a slack variable, and $\nu_{ij}$, $\xi_{ij}$, $\rho_{ij}$ are derived from linearization. The augmented problem includes slack penalties:
$$ J_{\text{aug},i}(\mathcal{U}_i) = J_i(U_i) + \mathcal{U}_i^T H_{\epsilon,i} \mathcal{U}_i – f_{\epsilon,i}^T \mathcal{U}_i $$
where $\mathcal{U}_i$ is the augmented decision vector. The optimization problem is solved subject to constraints on physical limits and collisions.
To enhance efficiency, we propose an intelligent target point allocation method for unlabeled drones. The relative position between drones i and j is $s_{i,j} = p_j – p_i$. We evaluate the dot product $u_{i,j}^T w_{i,j}$, where $u_{i,j}$ and $w_{i,j}$ are initial and target relative positions. If $u_{i,j}^T w_{i,j} < 0$, drones i and j swap target points to reduce trajectory crossings. This minimizes the total distance traveled and mitigates collision risks, crucial for dynamic drone performances.
We evaluated our method through simulations comparing it with sequential convex programming (SCP) approaches. The table below summarizes the success rates for trajectory generation across different swarm sizes, highlighting the effectiveness of our soft constraint strategy in drone shows:
| Swarm Size | Hard Constraints | Soft Constraints (Our Method) |
|---|---|---|
| 50 drones | 60% | 95% |
| 100 drones | 45% | 88% |
| 150 drones | 30% | 78% |
Another key metric is computation time. Our DMPC approach significantly reduces time compared to centralized SCP, as shown below:
| Method | Average Computation Time (s) |
|---|---|
| Centralized SCP | 12.5 |
| Decoupled SCP | 3.2 |
| Our DMPC | 0.5 |
Furthermore, we analyzed trajectory efficiency by measuring the total flight distance. With intelligent target allocation, our method reduces the aggregate distance by 26% compared to fixed assignments. This optimization is vital for energy-efficient drone performances in prolonged shows.
The convergence of the target allocation algorithm is ensured by minimizing $\sum_{i=1}^N \sum_{j \in \mathcal{N}_i} \| u_{i,j} – w_{i,j} \|^2$. The algorithm iterates until no beneficial swaps remain, typically requiring $O(N^2)$ checks. This process enhances the scalability of our approach for large-scale drone shows.
In terms of robustness, our method handles uncertainties in drone dynamics and environmental disturbances. The soft constraints allow minor violations to maintain feasibility, ensuring reliable operation in real-world drone performances. The tuning parameters, such as the horizon length K and cost weights, can be adjusted based on the specific requirements of a drone show, balancing aggression and safety.
To illustrate the practical application, consider a scenario where a drone swarm transitions from a random initial formation to a predefined pattern. Our DMPC algorithm generates trajectories that avoid collisions while minimizing time and energy. The distributed nature allows parallel computation, making it suitable for real-time interactive drone performances where audience inputs dynamically alter target formations.
In conclusion, our DMPC-based framework provides a scalable and efficient solution for drone swarm formation changes. It addresses the limitations of existing methods by combining distributed optimization, on-demand collision avoidance, and intelligent target allocation. This enables real-time interactivity in drone shows, meeting the growing demand for personalized and engaging drone performances. Future work will focus on incorporating wind disturbances and extending the approach to heterogeneous swarms for more complex drone shows.