Urban low-altitude UAV route planning: theory and algorithm in high-density CBD scenarios

When hundreds of drones shuttle between skyscrapers at the same time, route planning is no longer a simple problem of “flying from point A to point B” - it is a high-dimensional constrained optimization problem that seeks a balance between three-dimensional space, time, energy, and safety.

---

Introduction: Why is CBD so difficult?

Urban low-altitude airspace is usually defined as the flight range 0–300 m (AGL) above the ground. This height level happens to be the main battlefield for UAV logistics, inspection, emergency response and other applications. The CBD (Central Business District) is the most complex sub-scenario for three reasons:

1. Dense buildings form an “urban canyon”

High-rise buildings make the available flight corridors extremely narrow, and the line of sight is blocked, which reduces the accuracy of GPS. The edges of the buildings also generate strong turbulence. At low altitudes below 50 meters, these turbulences can completely cause a small multi-rotor to lose control.

2. High-density UAVs cause intensive conflicts

In a suburban scene, there may be only a few drones flying at the same time; while under a mature urban air traffic management (UTM) system, the number of drones over the CBD may reach more than 40 drones per minute. This means that Conflict Detection & Resolution (CD&R) becomes the core bottleneck of the system rather than a peripheral function.

3. Dynamic obstacle and multi-constraint coupling

In addition to buildings, drones also have to deal with temporary no-fly zones, manned aircraft routes, real-time wind field changes, and safety risks from crowd density on the ground - all of which work together to make it difficult for any single path planning algorithm to deal with alone.

---

1. Problem modeling: turning flight problems into mathematical problems

1.1 3D Occupancy Grid

Discretize urban space into a voxel grid, and each voxel records its occupancy status:

Voxel resolution is typically 1–5 m and the CBD core region can be refined to 0.5 m. Building height data comes from a GIS (Geographic Information System) database and is dynamically updated combined with real-time sensors.

1.2 Mathematical definition of 4D trajectory

The flight trajectory of a single UAV is a space curve parameterized with respect to time:$$ \boldsymbol{\xi}(t) = \bigl(x(t),; y(t),; z(t)\bigr), \quad t \in [t_0,, t_f]

|\boldsymbol{\xi}_i(t) - \boldsymbol{\xi}_j(t)|2 \geq d{sep}, \quad \forall, i \neq j,; \forall, t \in [t_0, t_f]

\min_{\boldsymbol{\xi}}; J(\boldsymbol{\xi}) = w_1 J_{len} + w_2 J_{time} + w_3 J_{energy} + w_4 J_{risk}

f(n) = g(n) + h(n)

g(n) = g(\text{parent}) + d(\text{parent},, n)

h(n) = |\mathbf{p}n - \mathbf{p}{goal}|_2 = \sqrt{(x_n-x_g)^2+(y_n-y_g)^2+(z_n-z_g)^2}

d(u,v) = \ell_{uv}\cdot\bigl(1 + \beta\cdot\mathcal{R}_{uv}\bigr) $$Among them, is the corridor segment length, is the ground risk score of the corridor (combining factors such as population density, building type, accident consequences, etc.), and is the risk weight coefficient. This makes A* tend to choose paths that fly over low-risk areas (e.g. rivers, parks), even if they are slightly detoured.

Limitations of A*: The quality of the airspace map determines the quality of the understanding. In high-density CBD, the number of nodes in the graph can reach hundreds of thousands, and the construction of the graph itself is a challenge.

2.2 RRT* algorithm: probabilistically complete asymptotic optimal planning

RRT* (Rapidly-exploring Random Tree Star) explores feasible paths by randomly sampling in continuous space, which is particularly suitable for high-dimensional and complex obstacle scenes.

Nearest neighbor query - Find the node closest to the random sampling point in the tree :

Step expansion - Extend step size from to direction:

The core improvement of RRT - Rewire:* Find all neighboring nodes in the sphere with as the center and radius :

Where is the number of nodes of the current tree, is the space dimension (3D scene ), and is a constant related to the free space volume. This radius shrinks as the sampling points increase, ensuring asymptotic optimality.

Cost update:

If the cost of can be reduced through , reconnection is performed:$$ \text{If } c(x_{near}) > c(x_{new}) + d(x_{new},, x_{near}),\text{ then change the parent node of } x_{near} \text{ to } x_{new}

\lim_{n\to\infty} c(\xi_n^) = c^ \quad \text{(almost certainly)}

U_{att}(\mathbf{p}) = \frac{1}{2}k_{att}|\mathbf{p} - \mathbf{p}_{goal}|^2

U_{rep}(\mathbf{p}) = \begin{cases} \dfrac{1}{2}k_{rep}!\left(\dfrac{1}{\rho(\mathbf{p})}-\dfrac{1}{\rho_0}\right)^{!2} & \rho(\mathbf{p}) \leq \rho_0 \[8pt] 0 & \rho(\mathbf{p}) > \rho_0 \end{cases}

\mathbf{F}(\mathbf{p}) = -\nabla U_{att}(\mathbf{p}) - \nabla U_{rep}(\mathbf{p})

\nabla U_{att} = k_{att},(\mathbf{p}-\mathbf{p}_{goal})

\delta\psi^* = \arg\min_{|\delta\psi|};\delta\psi \quad \text{s.t. } d_{min}(\delta\psi)\geq d_{sep}

z_{layer}(k) = z_{base} + k\cdot\Delta z_{layer}, \quad k\in{0,1,\ldots,N_{layer}-1}

VO_{ij}^\tau = \left{\mathbf{v}_i ;\middle|; \exists, t\in[0,\tau],; \mathbf{p}_i+\mathbf{v}_i t ;\in; \mathbf{p}_j+\mathbf{v}j t \oplus \mathcal{D}(d{sep})\right}

where is the size of the minimum velocity change, and points to the normal direction of the boundary.

The set of feasible velocities for agent (intersect all neighbor constraints and then intersect with dynamic constraints):

Among them, encodes dynamic constraints such as maximum velocity and acceleration. ORCA has achieved a 100% success rate in density scenarios of more than 40 frames/minute, with a computational complexity of , making it suitable for real-time deployment.

---

4. Graph theory modeling: urban airspace network

4.1 Construction of route network diagram

Urban airspace is modeled as a weighted directed graph:

• Node : above road intersections, tops of buildings, key transfer points
• Edge : Legal flight corridor between two nodes (needs to pass collision detection verification)
• Edge weight : multi-objective scalar weighting

Corridor capacity constraints (the number of UAVs passing at the same time does not exceed the upper limit):

The occupancy status of the entire airspace can be described by a four-dimensional tensor ( is the voxel grid, is the number of time slots):$$ \mathbf{A} \in {0,1}^{N_x\times N_y\times N_z\times N_t}, \quad A_{x,y,z,t} = 1 \iff \exists\text{ UAV occupied voxel}(x,y,z)\text{ in time slot }t

P_{hover} = \sqrt{\frac{(mg)^3}{2,\rho_{air}, A_r}}

P(v) = \underbrace{P_0!\left(1+\frac{3v^2}{U_{tip}^2}\right)}{\text{Blade resistance}} + \underbrace{P_i!\left(\sqrt{1+\frac{v^4}{4v_0^4}}-\frac{v^2}{2v_0^2}\right)^{!\frac{1}{2}}}{\text{Induction power}} + \underbrace{\frac{1}{2},d_0,\rho_{air},s,A,v^3}_{\text{Body resistance}}

\mathcal{E}{ij} = \frac{\ell{ij}}{v}\cdot P(v)

v^* = \arg\min_v \frac{P(v)}{v}

f(v_w;, k,, \lambda) = \frac{k}{\lambda}!\left(\frac{v_w}{\lambda}\right)^{k-1}!\exp!\left[-!\left(\frac{v_w}{\lambda}\right)^k\right]

\bar{u}(z) = \frac{u^*}{\kappa}\ln!\left(\frac{z - d_0}{z_0}\right), \quad \kappa = 0.41 \text{(von Kármán constant)}

t_{ij} = \frac{d_{ij}}{v_{air} + v_w\cos\theta_w}

\mathcal{E}{ij}^{wind} = \int_0^{t{ij}} P!\left(|\mathbf{v}_{UAV}(t) - \mathbf{v}_w(t)|\right)\mathrm{d}t

TI = \frac{\sigma_u}{\bar{u}}, \qquad \sigma_u = \sqrt{\overline{u’^2}}

d_{safe}(h) = d_{base} + \frac{k\cdot H_{bld}}{h - H_{bld} + \epsilon}

\rho\bigl(\mathbf{p}(t)\bigr) \geq d_{safe}\bigl(z(t)\bigr), \quad \forall, t \in [t_0, t_f]

\min;\sum_{k=1}^{N}!\left(w_1, T_k + w_2,\mathcal{E}_k\right)

\sum_{j:(i,j)\in E}x_{ij}^k - \sum_{j:(j,i)\in E}x_{ji}^k = b_i^k, \quad \forall, i\in V,;\forall, k

\sum_{k=1}^{N} x_{ij}^k \leq C_{ij}, \quad \forall,(i,j)\in E

t_j^k \geq t_i^k + \frac{d_{ij}}{v_{max}}\cdot x_{ij}^k, \quad \forall,(i,j)\in E,;\forall, k

t_i^k - t_i^l \geq \Delta t_{sep} - M(1 - z_{kl}^i)

t_i^l - t_i^k \geq \Delta t_{sep} - M, z_{kl}^i

\min_{x,, t,, v};\sum_k\sum_{(i,j)} x_{ij}^k\cdot\frac{d_{ij}}{v_{ij}^k}\cdot P(v_{ij}^k), \quad v_{min}\leq v_{ij}^k\leq v_{max}

r_i^t = r_{arrive}\cdot\mathbf{1}[goal] - c_{step} - c_{conflict}\cdot\mathbf{1}[conflict] - c_{detour}\cdot|\mathbf{p}i^t - \mathbf{p}{direct}| $$The meaning of each item: is the positive reward for reaching the target; is the time penalty for each flight step; is the penalty when a conflict occurs; is the detour penalty for deviating from the straight line.

7.2 Double-DQN update (discrete action space)

The online network selects actions, and the target network evaluates values, decoupling selection and evaluation to reduce overestimation bias.

7.3 Attention Mechanism: Modeling Neighbor Influence

The decision-making of each drone in the CBD requires sensing the status of its surrounding neighbors. The attention mechanism allows agent to dynamically weight the influence of neighbors :

The attention weight reflects the relevance of the neighbor to the decision-making of the agent . Neighbors with close distances and large speed conflicts naturally receive higher weights.

7.4 PPO policy gradient (continuous/mixed action space)$$

\mathcal{L}^{CLIP}(\theta) = \mathbb{E}_t!\left[\min!\left(r_t(\theta)\hat{A}_t,;\mathrm{clip}!\left(r_t(\theta),,1-\varepsilon,,1+\varepsilon\right)\hat{A}_t\right)\right]

r_t(\theta) = \frac{\pi_\theta(a_t\mid s_t)}{\pi_{\theta_{old}}(a_t\mid s_t)}

\boldsymbol{\xi}(u) = \sum_{i=0}^{n}\binom{n}{i}(1-u)^{n-i}u^i,\mathbf{P}_i, \quad u \in [0,1]

\dot{\boldsymbol{\xi}}(u) = n\sum_{i=0}^{n-1}\binom{n-1}{i}(1-u)^{n-1-i}u^i,(\mathbf{P}_{i+1}-\mathbf{P}_i)

\kappa = \frac{|\dot{\boldsymbol{\xi}}\times\ddot{\boldsymbol{\xi}}|}{|\dot{\boldsymbol{\xi}}|^3} \leq \frac{a_{max}}{v^2}

\min;\int_{t_0}^{t_f}!\left|\frac{d^4\boldsymbol{\xi}}{dt^4}\right|^2!\mathrm{d}t

\min_{\mathbf{c}};\mathbf{c}^\top\mathbf{Q}\mathbf{c} \quad \text{s.t. }\mathbf{A}{eq}\mathbf{c} = \mathbf{b}{eq}