In the domain of low-altitude defense, the rapid proliferation of unauthorized unmanned aerial vehicles (UAVs) has introduced severe security threats to critical infrastructure, military installations, and public safety. The inherent characteristics of these small, slow, and low-flying drones make them difficult to detect and engage using traditional air defense systems. As a response, deploying friendly drones to autonomously intercept intruding targets has emerged as a cost-effective and agile countermeasure. The core challenge lies in generating a feasible and time-optimal interception trajectory in a dynamic, obstacle-populated environment, while respecting the drone’s dynamics and real-time computational constraints. This paper presents a comprehensive planning framework that integrates a novel target-synergistic ripple spreading algorithm (TS-RSA) for path search, a minimum-snap trajectory optimization for kinematic feasibility, and a prediction error compensation mechanism to enhance robustness. The proposed method is validated through extensive simulations on the Gazebo platform, demonstrating high interception success rates and low latency.
The advancement of drone technology has enabled the deployment of autonomous interception systems that can operate in complex low-altitude airspace. However, the requirement for real-time decision-making under uncertainty remains a bottleneck. Our work addresses this by embedding the predicted target trajectory directly into the path search process, thereby avoiding the drawbacks of decoupled spatial and temporal planning. By leveraging the spatiotemporal synchronization property of a ripple spreading mechanism, we achieve efficient reachability computation for maneuvering targets. Furthermore, we design a trajectory generation and optimization module that ensures smooth, dynamically feasible flight, and a lightweight time-scaling strategy that compensates for prediction deviations without full trajectory replanning. This combination yields a robust, high-performance interception solution suitable for practical deployment.
Problem Formulation and Mathematical Model
We consider a scenario where an interceptor drone must capture a non-cooperative target drone that moves along a predicted trajectory $\mathbf{p}_{g}(t)$. At the current time $t_0$, the interceptor is at $\mathbf{p}_{i}(t_0)$ with velocity $\mathbf{v}_i(t_0)$ and acceleration $\mathbf{a}_i(t_0)$. The goal is to minimize the capture time $T$ subject to dynamic constraints and obstacle avoidance:
$$
\begin{aligned}
\min_{T} \quad & T \\
\text{s.t.} \quad & \mathbf{p}_i(T) = \mathbf{p}_g(T), \\
& \dot{\mathbf{p}}_i(t) = \mathbf{v}_i(t), \quad \ddot{\mathbf{p}}_i(t) = \mathbf{a}_i(t), \\
& \mathbf{p}_i(t) \in \Theta, \quad \mathbf{v}_i(t) \in \mathcal{V}, \quad \mathbf{a}_i(t) \in \mathcal{A},
\end{aligned}
$$
where $\Theta$ denotes the collision-free space, and $\mathcal{V}, \mathcal{A}$ are admissible velocity and acceleration sets. The challenge is to solve this problem in real-time while the target’s future motion is only approximately known.
Target-Synergistic Ripple Spreading Algorithm (TS-RSA)
Traditional path planning methods like A* or sampling-based planners require explicit handling of dynamic obstacles and time-dependent target positions, often leading to frequent replanning and suboptimal solutions. The Ripple Spreading Algorithm (RSA) offers a natural way to incorporate time evolution into the search process by simulating wavefront propagation from the start node. We extend this to the Target-Synergistic Ripple Spreading Algorithm (TS-RSA), where the destination itself moves according to predicted target positions.
Let the road network be represented as a graph $G(t) = (V(t), E)$ with $N$ nodes. Each node $v$ has a state $F(v) \in \{0,1,2,3\}$ (inactive, active, waiting, dead). The ripple propagation speed is set to the interceptor’s average cruise speed $v_{\text{ripple}}$, and the time step is $\Delta t = R_0 / v_{\text{ripple}}$, where $R_0$ is the minimum edge weight. The algorithm proceeds as follows:
- Initialization: Set all nodes inactive; activate the start node $P_0$; set $t=0$.
- Main loop: At each time step $t \leftarrow t + \Delta t$, update the graph $G(t)$ and the target node position $P_M(t)$. For each active node $m$, extend its ripple radius by $R_0$ and attempt to activate neighboring nodes if the ripple reaches them. If a neighboring node is blocked by an obstacle, it enters a waiting state; when the obstacle clears, it becomes active. The loop terminates when the target node $P_M(t)$ is activated.
- Backtracking: Trace the activation source chain from $P_M$ back to $P_0$ to obtain the shortest interception path and corresponding expected arrival times.
The key advantage of TS-RSA is that it implicitly performs a spatiotemporal reachability analysis. The activation boundary represents the set of nodes reachable at the current time, and the target trajectory intersects this boundary exactly at the optimal interception point. The algorithm is both complete and optimal under the point-mass assumption, as proven in the original RSA literature. The time complexity is $O( \bar{N} \cdot M )$, where $\bar{N}$ is the average node degree and $M$ is the number of propagation steps, which is typically much smaller than the product of nodes and time horizons in explicit time-expanded graphs.
Trajectory Generation and Optimization
The discrete path output by TS-RSA consists of a sequence of waypoints $\{P_0, P_1, \dots, P_M\}$ with associated time stamps $\{t_0, t_1, \dots, t_M\}$. To obtain a smooth, dynamically feasible trajectory, we first perform adaptive waypoint sampling based on path complexity, then solve a Quadratic Programming (QP) problem for minimum-snap polynomial trajectories.
Waypoint Sampling
We define a path complexity metric $k(M)$ that combines normalized arc length, curvature, and time deviation:
$$
d(M) = \sum_{i=0}^{M-1} \|P_{i+1} – P_i\|, \quad c(M) = \sum_{i=1}^{M-1} \frac{\arccos(\mathbf{v} \cdot \mathbf{w} / \|\mathbf{v}\|\|\mathbf{w}\|)}{\pi}, \quad t(M) = \sum_{i=0}^{M-1} \frac{|t_{i+1} – t_i – \bar{\Delta} |}{\bar{\Delta}},
$$
where $\bar{\Delta}$ is the average time interval. The number of sampled waypoints $N_{\text{samp}}$ is determined by a clamped rounding:
$$
N_{\text{samp}} = \text{clamp}\left( \text{round}\big(\alpha d(M) + \beta c(M) + \gamma t(M) \big), N_{\min}, N_{\max} \right).
$$
Each sampled waypoint $W_j$ is obtained by linear interpolation along the path with respect to the normalized complexity coordinate $k(W_j) = j \cdot k(M) / N_{\text{samp}}$.
Minimum-Snap Trajectory Optimization
Each segment between two consecutive waypoints $W_j$ and $W_{j+1}$ is represented as a 7th-order polynomial:
$$
p_j(t) = a_{j,0} + a_{j,1} t + a_{j,2} t^2 + \cdots + a_{j,7} t^7, \quad t \in [0, \Delta t_j],
$$
where $\Delta t_j$ is the allocated time derived from TS-RSA output. The objective is to minimize the integral of the squared snap (fourth derivative) over the whole trajectory:
$$
\min \; J = \sum_{j=0}^{N_{\text{samp}}-1} \int_{0}^{\Delta t_j} \left( \frac{\mathrm{d}^4 p_j(t)}{\mathrm{d}t^4} \right)^2 \mathrm{d}t.
$$
Constraints enforce position, velocity, and acceleration continuity at waypoints, as well as boundary conditions (initial state and final interception position). This forms a standard QP problem:
$$
\min \; \frac{1}{2} \mathbf{a}^T \mathbf{Q} \mathbf{a} \quad \text{s.t.} \quad \mathbf{A}_{\text{eq}} \mathbf{a} = \mathbf{b}_{\text{eq}},
$$
where $\mathbf{a}$ is the stacked coefficient vector, $\mathbf{Q}$ is a sparse Hessian matrix representing the snap energy, and $\mathbf{A}_{\text{eq}}, \mathbf{b}_{\text{eq}}$ encode the constraints. Solving this QP yields a trajectory that minimizes actuator effort while exactly passing through the desired waypoints at specified times. The computational overhead is typically 12–20 ms, well within real-time requirements.
Prediction Error Compensation
Trajectory predictions inevitably suffer from errors that accumulate over time. Rather than replanning the entire path frequently, we employ a time-scaling strategy that adjusts the execution speed of the existing trajectory to absorb discrepancies. At the current time $t_{\text{current}}$, the updated target prediction $\mathbf{p}_{g,\text{updated}}(t)$ may indicate a new interception point. We evaluate two error metrics:
- Spatial error: $\delta_{\text{spatial}} = \| \mathbf{p}_{g,\text{init}}(T) – \mathbf{p}_{g,\text{updated}}(T_{\text{updated}}) \|$,
- Temporal error: $\delta_{\text{temporal}} = | T_{\text{updated}} – T |$,
where $T$ is the originally planned interception time and $T_{\text{updated}}$ is the time at which the updated trajectory is closest to the original interception point. If the errors exceed dynamic thresholds $\epsilon_{\text{spatial}}(t_{\text{current}})$ and $\epsilon_{\text{temporal}}(t_{\text{current}})$, a full replanning with TS-RSA is triggered. Otherwise, we compute a time-scaling factor:
$$
s = \frac{T_{\text{updated}} – t_{\text{current}}}{T – t_{\text{current}}}.
$$
The existing polynomial trajectory $\mathbf{p}(\tau)$ for $\tau \in [0, T – t_{\text{current}}]$ is reparameterized as $\mathbf{q}(\tau) = \mathbf{p}(\tau / s)$, effectively speeding up or slowing down the motion. The new polynomial coefficients become:
$$
\tilde{a}_{j,k} = a_{j,k} \cdot s^{-k}, \quad k = 0,\dots,7.
$$
This method preserves the spatial shape of the trajectory, requires negligible computation (a few milliseconds), and significantly reduces the number of replanning events. The dynamic thresholds are linearly decreasing functions of remaining time, e.g.,
$$
\epsilon_{\text{spatial}}(t) = b_0 + k_0 (T – t), \quad \epsilon_{\text{temporal}}(t) = b_1 + k_1 (T – t),
$$
so that early stage tolerates larger errors, while later stage imposes tighter constraints for precise interception.
Experimental Evaluation
Road Network Comparison
To evaluate the path search efficiency of TS-RSA, we compared it against two classic interception planning strategies: Online Path Optimization (OPO) and Iterative Path Optimization (IPO) in random road networks of varying sizes (100 to 625 nodes). The interceptor’s maximum speed was 6.5 m/s, and the target’s speed was 3 m/s. The key metrics are path length (PL), computation time (CT), actual interception time (IT), and waiting time due to obstacles (WT). Each scenario was repeated 100 times. The results are summarized below.
| Scenario | Algorithm | PL (m) | CT (s) | IT (s) | WT (s) |
|---|---|---|---|---|---|
| Scene 1 (100 nodes) | TS-RSA | 58.2 | 0.082 | 12.4 | 0.0 |
| OPO | 72.5 | 0.045 | 14.7 | 0.0 | |
| IPO | 55.1 | 0.210 | 13.8 | 2.1 | |
| Scene 2 (225 nodes) | TS-RSA | 61.3 | 0.136 | 13.1 | 0.3 |
| OPO | 78.9 | 0.089 | 16.2 | 0.0 | |
| IPO | 57.8 | 0.618 | 15.5 | 3.4 | |
| Scene 3 (400 nodes) | TS-RSA | 65.7 | 0.204 | 14.0 | 0.5 |
| OPO | 85.2 | 0.132 | 17.8 | 0.0 | |
| IPO | 62.3 | 1.452 | 17.1 | 5.6 | |
| Scene 4 (625 nodes) | TS-RSA | 70.4 | 0.289 | 15.2 | 0.8 |
| OPO | 95.1 | 0.210 | 20.1 | 0.0 | |
| IPO | 68.9 | 3.870 | 19.4 | 6.8 |
TS-RSA consistently achieved the shortest interception time (IT) with negligible waiting time, while IPO suffered from high replanning costs and OPO exhibited longer path lengths due to its myopic pursuit behavior. The computational time of TS-RSA scaled gracefully with network size, never exceeding 0.3 s even in the largest graph. This demonstrates that TS-RSA is well-suited for real-time dynamic interception tasks.
Gazebo Simulation Experiments
We conducted comprehensive simulations in the Gazebo environment with a 200 m × 100 m × 5 m airspace, including dynamic obstacles (moving cubes of 5 m side length) and a target drone executing various maneuvering patterns (arc, zigzag, figure-eight, S-curve, and obstacle-dense path). The interceptor’s maximum speed was 2 m/s, and the target’s maximum speed was varied: 1 m/s (advantage), 2 m/s (equal), and 3 m/s (disadvantage). Three trajectory prediction models were employed: simple constant acceleration model, noise-injected model, and LSTM-based model. Interception success was defined as the distance between the two drones being less than 1 m at any time. A total of 486 scenario combinations were tested. The following table shows the average success rates for three different strategies: Strategy 1 (without prediction compensation), Strategy 2 (using line-of-sight navigation instead of polynomial trajectory), and Strategy 3 (full proposed method).
| Prediction Model | Strategy 1 | Strategy 2 | Strategy 3 |
|---|---|---|---|
| Simple motion | 0.351 | 0.426 | 0.704 |
| Noise-injected | 0.481 | 0.407 | 0.722 |
| LSTM network | 0.611 | 0.592 | 0.851 |
Strategy 3 achieved an average success rate of 75.9% across all experiments, outperforming Strategy 1 (48.1%) and Strategy 2 (47.5%) by a substantial margin. The improvement was especially pronounced when the target had a speed advantage or when prediction errors were large. Notably, the number of replanning events per mission dropped from an average of 7.86 (Strategy 1) and 5.24 (Strategy 2) to only 2.75 for Strategy 3, confirming the effectiveness of the time-scaling compensation mechanism.
Real-time performance was also measured. The average computation time for each module in Strategy 3 is shown below.
| Module | Time (ms) |
|---|---|
| TS-RSA path search | 13.27 |
| Waypoint sampling | 1.43 |
| Trajectory optimization (QP) | 16.85 |
| Total planning cycle | 31.55 |
The total planning cycle of about 31.55 ms easily supports a 20–50 Hz replanning rate, fulfilling the real-time requirement for onboard autonomous flight. The TS-RSA path search contributed the largest portion, yet remained under 14 ms even with dense graphs in the 3D space (discretized as a grid of nodes). These results validate the practical applicability of the proposed framework for low-altitude drone interception tasks.
Conclusion and Future Work
We have presented a complete autonomous drone interception planning method that integrates a target-synergistic ripple spreading algorithm, minimum-snap trajectory optimization, and a low-cost prediction error compensation strategy. The TS-RSA provides optimal spatiotemporal paths through dynamic obstacle fields, while the trajectory generation ensures smooth and dynamically feasible flight. The compensation mechanism significantly reduces the need for replanning, enhancing robustness against prediction uncertainties. Extensive simulations on the Gazebo platform demonstrated an average success rate of 75.9% across 486 diverse scenarios, with planning latencies well under 40 ms. This work contributes to the advancement of drone technology for low-altitude defense applications, enabling reliable and efficient counter-UAV operations.
Future research directions include extending the framework to handle adversarial targets with active evasion maneuvers via game-theoretic or reinforcement learning approaches, and scaling to multi-interceptor coordination for swarm defense. Additionally, integration with real sensor data and flight tests on actual hardware platforms will be pursued to validate the system’s performance under realistic conditions.