PB-STDG: A Prediction-Based Short-Term Decentralized Greedy Guidance Algorithm for a Drone Road System
Authors: Zhouyu Qu, Andreas Willig, Xiaobing Wu
Organizations: Dept. of Computer Science and Software Engineering, University of Canterbury, Private Bag 4800, Christchurch, 8140, New Zealand · Wireless Research Centre, University of Canterbury, Private Bag 4800, Christchurch, 8140, New Zealand
In recent years, Unmanned Aerial Vehicles (UAVs) or drones have been increasingly adopted in urban environments for applications such as parcel delivery, infrastructure inspection, emergency response, and drone light shows. A non-negligible issue is how to manage the increasing number of drones operated by different entities, to enable them to cooperatively avoid potential collisions and determine conflict-free short-term flight paths in urban airspace. This paper presents a Prediction-Based Short-Term Decentralized Greedy (PB-STDG) guidance algorithm for a structured Drone Road System (DRS). PB-STDG extends the original STDG algorithm by introducing a prediction mechanism that enables drones to anticipate the decisions of neighboring drones using additional information shared in beacon packets, aiming to address the over-conservative behavior observed in the STDG algorithm. Several simulation scenarios are conducted to evaluate and compare the proposed algorithm with STDG. The results show that PB-STDG improves traffic efficiency while maintaining a safety level comparable to that of STDG.
Figures & tables
Figure 1 : Left: Simple lane arrangement example, identifier (0,0) is the central lane of the road. Right: Example of position-cost calculation.
Figure 2 : Beacon Content
Figure 3 : Workflow of PB-STDG
Figure 4 : Road division into equal-length blocks for more accurate prediction
Symbol
Description
(i,j)
Lane identifier
N(i,j)
One-hop neighbor lanes of (i,j) (excluding (i,j) )
C(i,j)
Candidate lanes from (i,j) ( N(i,j)∪(i,j) )
Δ(i,j)
Set of drones on lane (i,j) known to the current drone
Δ(L)
Union of Δ(i,j) for all (i,j)∈L
[(i,j),(i′,j′)]1
Hop distance between two parallel lanes (i,j) and (i′,j′)
Table 1 : Notation used in the coordination-free STDG algorithm
Figure 5 : The selection areas of drones in O(A) , D(i,j)A) , and P(i,j)A . Drones are assumed to receive complete information from at least the current block and blocks immediately ahead of and behind that.
Parameter
Value
Path Loss Exponent
2
Minimal Safety Distance
0.5 m
Lane Radius
10 m
Preferred Speed Interval
10–15 m/s
Preferred Speed Distribution
Uniform
Replication Number per Simulation
50
Table 2 : Fixed Simulation Parameters
Figure 6 : A simple DRS used to compare STDG and PB-STDG. The two roads are located at different altitude levels. The right-hand side shows the lane arrangement of both roads.
Parameter
Notation
Value
Position Cost Coefficient
κ1
1
Collision Cost Coefficient
κ2
10000
Distance Threshold for Searching Neighboring Drones
ϵ1
15 m
Table 3 : Key Algorithm Parameters in Initial Study
Figure 7 : Average speed for STDG and Prediction-Based algorithms in two-road two-ramp scenario, where the beaconing rate is 10 Hz and the transmit power is 2 mW.
Figure 8 : Arrival count for STDG and Prediction-Based algorithms in two-road two-ramp scenario, where the beaconing rate is 10 Hz and the transmit power is 2 mW.
Figure 9 : Lane Usage Distributions for STDG and Prediction-Based Algorithms in One Road One Ramp Scenario. In each hexagon, (i,j) denotes the lane identifier, and the percentage indicates the corresponding lane usage.
Figure 10 : Drone Road System used in the simulations
Figure 11 : Collision rate for different block lengths
Figure 12 : Average speed for different block lengths
κ1
κ2
ϵ1
Max. Collision Rate
Avg. Speed (m/s)
Arrival Count
STDG
1
10000
15
0.057%
10.2842
2.74
Prediction-Based
0.00%
12.1829
3.62
STDG
100
1
5
1.27%
12.3005
3.73
Prediction-Based
0.64%
12.3117
3.73
Ideal
0.00%
12.5
4.2
Table 4 : Simulation results for 50 replications in the complex road system for STDG and PB-STDG, where gr = 0.2
Generation Rate
κ1
κ2
ϵ1
Collision Rate (%)
Average Speed (m/s)
Arrival Count
0.2
1
10
15
0.0086 (1.3888)
12.32 (9.56)
3.73 (1.69)
0.2
1
10
5
0.4224 (1.41)
12.36 (12.01)
3.78 (3.79)
0.2
1
10000
15
0 (0.0026)
12.18 (10.28)
3.62 (2.74)
0.2
1
10000
5
0.4694 (1.164)
12.37 (11.72)
3.75 (3.57)
0.2
10
10
15
0.0022 (1.1604)
12.28 (11.89)
3.74 (3.64)
0.2
10
10
5
0.314 (1.726)
12.28 (11.93)
3.78 (3.57)
Table 5 : Simulation results from 50 independent simulation replications under various parameter combinations for PB-STDG and STDG (shown in parentheses).
Collision rate
Average speed (m/s)
Arrival count
Average of responses
1.2e-3
12.3837
2.8631
Minimum of responses
0.0
12.1829
1.97
Maximum of responses
4.69e-3
12.4952
3.81
R2 value (%)
99.1394
94.5068
99.9791
Regression coefficients
Cost parameter κ1 (Coefficient α1 )
-2.0e-4
-1.8e-2
1.1e-2
Table 6 : Regression analysis results and percentage contributions of parameters for PB-STDG.
Algorithm
Total Algorithm Executions
Lane-Switching Decisions
STDG
186288
2445
PB-STDG
142419
4790
Table 7 : Comparison of STDG and PB-STDG in Handling Concurrent Lane Switching
Deep reinforcement learning (DRL) finds extensive application in autonomous drone navigation within complex, high-risk environments. However, its practical deployment faces a safety-exploration dilemma: soft penalty mechanisms encourage risky trial-and-error, while most constraint-based methods suffer degraded performance under sensor noise and intent uncertainty. We propose Dynamic-TD3, a physically enhanced framework that enforces strict safety constraints while maintaining maneuverability by modeling navigation as a Constrained Markov Decision Process (CMDP). This framework integrates an Adaptive Trajectory Relational Evolution Mechanism (ATREM) to capture long-range intentions and employs a Physically Aware Gated Kalman Filter (PAG-KF) to mitigate non-stationary observation noise. The resulting state representation drives a dual-criterion policy that balances mission efficiency against hard safety constraints via Lagrangian relaxation. In experiments with aggressive dynamic threats, this approach demonstrates superior collision avoidance performance, reduced energy consumption, and smoother flight trajectories.
Autonomous multi-drone navigation requires fleets to service distributed objectives in cluttered environments under tight computational budgets. Efficient coordination depends on task bundling, where each drone visits multiple objectives along its route. Separate solvers for cost estimation, assignment, and execution incur redundant graph search and produce long, abrupt paths. We propose FlockDiffusion, a learned framework combining a scene graph encoder, an explicit allocation head, an assignment conditioned diffusion transformer, and a closed form trajectory decoder. An autoregressive teacher provides offline supervision for parallel fleet trajectory generation. PyBullet ablations show that bundling increases task completion from 50% to 100%, while our complete teacher further reduces route cost by 8.4% relative to MAGNNET with bundling. In the optimized scalability benchmark, evaluated on 100 scenes per density with ten drones, FlockDiffusion achieves 6.2 to 7.6 times faster inference and approximately 37% shorter routes than the classical pipeline. As nominal task counts increase from 20 to 40, latency rises from 7.8 to 11.1 ms, compared with 48.0 to 75.8 ms for the baseline. In a separate evaluation across five Gazebo environments, FlockDiffusion achieves 100% planner coverage and reduces planned route cost by 15.4% relative to the baseline with bundling. These results demonstrate efficient planning under increasing task density in configurations that are demanding to reproduce with physical drone fleets.
Iana Zhura, Satenik Akopyan, Roohan Ahmed Khan +3
Skolkovo Institute of Science and Technology, Moscow, Russia
Accurate 4D trajectory prediction and closed-loop tracking are essential for Unmanned Aerial Vehicle (UAV) swarms to achieve safe and efficient operations in complex low-altitude environments such as urban airspaces, industrial sites, and indoor facilities. However, this task remains challenging due to intrinsic nonlinearity of UAV swarm dynamics and strict real-time constraints of swarm formation control. To address these challenges, we propose a unified framework that couples coarse-to-fine trajectory forecasting with uncertainty-aware Distributed Nonlinear Model Predictive Control (DNMPC). Our approach features two key innovations: 1) a dimension-decoupled trajectory prediction module that reduces computational complexity by forecasting axis-wise motion, and 2) a diffusion-based residual dynamics refinement module that captures temporally correlated dynamic uncertainties. These refined predictions are then integrated into a DNMPC loop to ensure formation stability. We also introduce a synchronized multi-scenario 4D UAV swarm dataset spanning six representative airspace scenarios. The dataset contains over \textbf{7,900} frames of synchronized three-UAV trajectories with frame-level annotations of speed intention and target sector. Extensive experiments demonstrate that our approach outperforms state-of-the-art baselines, reducing trajectory tracking error by up to \textbf{10-15%} and achieving sub-\textbf{0.07,m} average tracking error in complex urban and industrial environments, while maintaining real-time inference speeds of 34 FPS (sub-30 ms latency) suitable for agile flight.
Tianshun Li, Hongliang Lu, Haoang Li +1
The Hong Kong University of Science and Technology (Guangzhou), China · Southern University of Science and Technology, China and MoSense Technologies, China