PB-STDG: A Prediction-Based Short-Term Decentralized Greedy Guidance Algorithm for a Drone Road System

Zhouyu Qu; Andreas Willig; Xiaobing Wu

cs.ROOct 4, 2026

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

Abstract

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 4 : Road division into equal-length blocks for more accurate prediction

Symbol	Description
$(i,j)$	Lane identifier
${\mathcal{N}(i,j)}$	One-hop neighbor lanes of $(i,j)$ (excluding $(i,j)$ )
${\mathcal{C}(i,j)}$	Candidate lanes from $(i,j)$ ( ${\mathcal{N}(i,j)}\cup(i,j)$ )
${\Delta(i,j)}$	Set of drones on lane $(i,j)$ known to the current drone
${\Delta(\mathcal{L})}$	Union of ${\Delta(i,j)}$ for all $(i,j)\in\mathcal{L}$
${\left[(i,j),(i^{\prime},j^{\prime})\right]_{1}}$	Hop distance between two parallel lanes $(i,j)$ and $(i^{\prime},j^{\prime})$

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	$\kappa_{1}$	1
Collision Cost Coefficient	$\kappa_{2}$	10000
Distance Threshold for Searching Neighboring Drones	$\epsilon_{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

	$\kappa_{1}$	$\kappa_{2}$	$\epsilon_{1}$	Max. Collision Rate	Avg. Speed (m/s)	Arrival Count
STDG	1	10000	15	0.057%	10.2842	2.74
Prediction-Based	1	10000	15	0.00%	12.1829	3.62
STDG	100	1	5	1.27%	12.3005	3.73
Prediction-Based	100	1	5	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	$\kappa_{1}$	$\kappa_{2}$	$\epsilon_{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
$R^{2}$ value (%)	99.1394	94.5068	99.9791
Regression coefficients
Cost parameter $\kappa_{1}$ (Coefficient $\alpha_{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

Explore similar work

Dynamic-TD3: A Novel Algorithm for UAV Path Planning with Dynamic Obstacle Trajectory Prediction
Apr 30, 2026Wentao Chen, Jingtang Chen, Mingjian Fu +4Unmanned Aerial Vehicle Trajectories Collision Avoidance
FlockDiffusion: Assignment-Conditioned Diffusion for Multi-Drone Task Allocation and Completion
Sep 20, 2026Iana Zhura, Satenik Akopyan, Roohan Ahmed Khan +3Multi-Drone Coordination Diffusion Planning
Skolkovo Institute of Science and Technology, Moscow, Russia
Diffusion-based 4D Trajectory Prediction and Distributed Control for UAV Swarms
Jun 30, 2026Tianshun Li, Hongliang Lu, Haoang Li +1Unmanned Aerial Vehicle Swarms Model Predictive Control
The Hong Kong University of Science and Technology (Guangzhou), China · Southern University of Science and Technology, China and MoSense Technologies, China

Apr 30, 2026, cs.ROJ/K move · Enter open · S save

Dynamic-TD3: A Novel Algorithm for UAV Path Planning with Dynamic Obstacle Trajectory Prediction

Wentao Chen, Jingtang Chen, Mingjian Fu, Tiantian Li+3

Unmanned Aerial Vehicle Trajectories Collision Avoidance

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Dynamic-TD3: A Novel Algorithm for UAV Path Planning with Dynamic Obstacle Trajectory Prediction

FlockDiffusion: Assignment-Conditioned Diffusion for Multi-Drone Task Allocation and Completion

Diffusion-based 4D Trajectory Prediction and Distributed Control for UAV Swarms