Urban air mobility is rapidly evolving, with low altitude drones playing a pivotal role in solving last-mile delivery inefficiencies. These low altitude UAVs operate in complex environments characterized by high-density dynamic traffic flows and structural obstacles. This paper addresses the collision avoidance problem for logistics low altitude drones navigating such challenging urban canyons.
Low altitude UAV operations face unique challenges: building occlusions limit perception ranges, narrow airspace corridors restrict maneuverability, and dynamic obstacles require real-time responses. Current approaches often fail to address the partial observability inherent to urban environments. We propose a 3D collision avoidance algorithm that expands solutions into three-dimensional space while maintaining robustness under sensor limitations.
Problem Formulation and Environmental Modeling
Urban low-altitude airspace typically follows layered operational structures (40-120m AGL) where low altitude drones maintain assigned flight levels unless collision avoidance necessitates vertical maneuvers. We model the environment as a continuous 3D space discretized into grids, incorporating static obstacles (buildings) and dynamic obstacles (“intruder” drones moving linearly). Safety thresholds follow aviation standards:
$$d_{\text{safe}} = 10 \text{ m}, \quad v_{\text{max}} = 25 \text{ m/s}, \quad \Delta h_{\text{max}} = 2 \text{ m/s}$$
The motion model for low altitude UAVs follows Dubins kinematics with performance constraints:
$$
\begin{bmatrix}
v_t \\
\theta \\
x_t \\
y_t \\
z_t
\end{bmatrix}
=
\begin{bmatrix}
v_0 + a \cdot \Delta t \\
\frac{g \tan \phi}{v_t} \\
x_0 + v \cos \theta \cdot \Delta t \\
y_0 + v \sin \theta \cdot \Delta t \\
z_0 + \Delta h \cdot \Delta t
\end{bmatrix}
$$
Where \(v_t\) = velocity at time \(t\), \(\theta\) = heading angle, \((x_t, y_t, z_t)\) = position, \(\phi\) = bank angle, and \(\Delta h\) = altitude change rate. Performance envelopes for low altitude UAVs are constrained as follows:
| Parameter | Range |
|---|---|
| Velocity (\(v\)) | [10, 25] m/s |
| Bank Angle (\(\phi\)) | [-25°, 25°] |
| Altitude Rate (\(\Delta h\)) | {-2, 0, 2} m/s |
Collision Avoidance as Markov Decision Process
We formulate the low altitude UAV collision avoidance problem as a Markov Decision Process (MDP) with the following components:
State Space (\(S_t\)): A \((7 + 6n)\)-dimensional vector incorporating the low altitude UAV’s position \((o_x, o_y, o_z)\), velocity (\(o_v\)), heading (\(o_\theta\)), \(n\) intruders’ states, and target position \((g_x, g_y, g_z)\):
$$S_t = \left( o_x, o_y, o_z, o_v, o_\theta, \ldots, i^{(k)}_x, i^{(k)}_y, i^{(k)}_z, i^{(k)}_v, i^{(k)}_\theta, \ldots, g_x, g_y, g_z \right)$$
Action Space (\(A\)): Discrete 3D maneuvers combining acceleration (\(A_a\)), bank angle (\(A_\phi\)), and altitude changes (\(A_h\)):
$$A = \left\{ A_a, A_\phi, A_h \right\} = \left\{ \{-5,0,5\} \text{m/s}^2, \{-5,0,5\}^\circ, \{-2,0,2\} \text{m/s} \right\}$$
Reward Function (\(R(s)\)): Modified to balance obstacle avoidance with altitude layer adherence:
$$R(s) =
\begin{cases}
1 & d_{\text{goal}} < 2 \text{m} \text{ and } |H_{\text{crt}} – H_0| = 0 \\
d(p) + \delta d(n) & d_{\text{goal}} \geq 2 \text{m} \text{ and } d_{\text{UAV}} > 10 \text{m} \\
0 & d_{\text{UAV}} \leq 10 \text{m}
\end{cases}$$
where:
$$d(p) = \frac{\max\{d_{\text{goal}}\} – d_{\text{goal}}}{\max\{d_{\text{goal}}\}}, \quad d(n) = -\left| \frac{H_{\text{crt}} – H_0}{H_{\text{max}}} \right|$$
Here, \(\delta\) = altitude influence factor (optimized at 0.02), \(d_{\text{goal}}\) = Euclidean distance to target, and \(H_{\text{crt}}\) = current altitude.
Algorithm Design: Monte Carlo Tree Search
We employ Monte Carlo Tree Search (MCTS) with Upper Confidence Bound for Trees (UCT) to solve the MDP:
$$\text{UCT} = \frac{Q(v’)}{N(v’)} + C \sqrt{\frac{2 \ln N(v)}{N(v’)}}$$
Where \(Q\) = node reward, \(N\) = visit count, \(C = 1/\sqrt{2}\) = exploration constant. This enables real-time computation of optimal actions for low altitude drones:
$$a_{\text{best}} \in \left\{ a_a, a_\phi, \Delta h \right\}$$
The MCTS process for low altitude UAV navigation involves:
- Selection: Traverse tree using UCT values
- Expansion: Add new child nodes
- Simulation: Rollout random policies to terminal state
- Backpropagation: Update node statistics with reward
Parameter Optimization
The altitude influence factor \(\delta\) critically balances horizontal vs. vertical avoidance for low altitude UAVs. Simulation results demonstrate its impact:
| \(\delta\) Value | Avg. Flight Time (s) | Max Altitude Deviation (m) |
|---|---|---|
| 0.01 | 264 | 120 |
| 0.02 | 258 | 100 |
| 0.04 | 267 | 90 |
| 0.08 | 286 | 80 |
| 0.10 | 322 | 75 |
Optimal performance occurs at \(\delta = 0.02\) where low altitude drones achieve minimal flight time while maintaining altitude stability. Higher values overly penalize essential vertical maneuvers, while lower values cause excessive layer deviations.
Simulation Results
3D Collision Avoidance Performance
Comparative simulations between horizontal-only and 3D avoidance strategies for low altitude UAVs show significant improvements:
| Strategy | Flight Time (s) | Path Length (km) | Avg. Velocity (m/s) |
|---|---|---|---|
| Horizontal Avoidance Only | 356 | 7.3 | 20.5 |
| 3D Avoidance (Proposed) | 269 | 4.87 | 18.1 |
The 3D strategy reduces flight time by 24.4% and path length by 33.2% for low altitude drones. Vertical maneuvers prove particularly effective against low-height obstacles where climbing is more efficient than circumnavigation.
Robustness Under Perception Constraints
Urban canyons create perception limitations for low altitude UAVs. We tested algorithm performance under restricted sensing radii:
| Perception Radius (m) | Conflict Probability (%) | Avg. Flight Time (s) | Min. Separation (m) |
|---|---|---|---|
| 500 | 0.0 | 258 | 68.4 |
| 300 | 0.0 | 261 | 56.2 |
| 200 | 0.5 | 267 | 38.1 |
| 150 | 1.5 | 284 | 29.7 |
| 120 | 3.5 | 322 | 17.3 |
| 100 | 7.5 | 350 | 12.1 |
The algorithm maintains safety (conflict probability < 2%) down to 150m perception range – crucial for low altitude UAVs operating in sensor-limited environments. Performance degradation is gradual rather than catastrophic.
Comparison with Dynamic-RRT
Benchmarking against state-of-the-art Dynamic-RRT demonstrates advantages for low altitude drone operations:
| Metric | Proposed Algorithm | Dynamic-RRT |
|---|---|---|
| Path Length (km) | 5.38 | 7.90 |
| Flight Time (s) | 278 | 439 |
| Conflict Probability (%) | 2.0 | 8.0 |
| Avg. Computation Time (ms) | 21 | 17 |
| Altitude Deviation (m) | 15.2 | 42.7 |
Our approach generates 28.7% shorter paths with 36.7% faster traversal for low altitude UAVs while better maintaining assigned flight levels (\(\Delta H\) reduced by 64.4%). The marginally longer computation time (21ms vs. 17ms) remains within real-time constraints for low altitude drone operations.
Conclusion
This paper presents a robust 3D collision avoidance algorithm for low altitude UAVs operating in urban environments with perception limitations. By formulating the problem as an MDP and solving it with optimized MCTS, we enable intelligent trade-offs between horizontal and vertical avoidance maneuvers. Key contributions include:
- A 3D action space expansion enabling both circumnavigation and obstacle-crossing strategies for low altitude drones
- A modified reward function with altitude influence factor (\(\delta = 0.02\)) balancing efficiency and airspace stability
- Demonstrated robustness maintaining < 2% conflict probability down to 150m perception range
Simulations confirm 24.4% flight time reduction and 33.2% path length reduction compared to horizontal-only avoidance. The algorithm outperforms Dynamic-RRT in path efficiency, conflict avoidance, and altitude stability – critical metrics for urban low altitude UAV operations. Future work will integrate wind dynamics and communication delays into the model for enhanced realism.