Städtische UAV-Routenplanung in geringer Höhe: Theorie und Algorithmus in CBD-Szenarien mit hoher Dichte

Wenn Hunderte von Drohnen gleichzeitig zwischen Wolkenkratzern pendeln, ist die Routenplanung nicht länger ein einfaches Problem des „Fliegens von Punkt A nach Punkt B“ – es ist ein hochdimensionales eingeschränktes Optimierungsproblem, das ein Gleichgewicht zwischen dreidimensionalem Raum, Zeit, Energie und Sicherheit anstrebt.

---

Einleitung: Warum ist CBD so schwierig?

Der städtische Luftraum in geringer Höhe wird normalerweise als Flugreichweite 0–300 m (AGL) über dem Boden definiert. Dieses Höhenniveau ist zufällig das Hauptschlachtfeld für UAV-Logistik, Inspektion, Notfallmaßnahmen und andere Anwendungen. Das CBD (Central Business District) ist aus drei Gründen das komplexeste Teilszenario:

1. Dichte Bebauung bildet einen „Urban Canyon“

Durch Hochhäuser sind die verfügbaren Flugkorridore extrem eng und die Sichtlinie ist blockiert, was die Genauigkeit des GPS verringert. Auch die Kanten der Gebäude erzeugen starke Turbulenzen. In geringen Höhen unter 50 Metern können diese Turbulenzen dazu führen, dass ein kleiner Multirotor völlig die Kontrolle verliert.

2. UAVs mit hoher Dichte verursachen intensive Konflikte

In einer Vorstadtszene fliegen möglicherweise nur wenige Drohnen gleichzeitig. Während bei einem ausgereiften UTM-System (Urban Air Traffic Management) die Anzahl der Drohnen über dem CBD mehr als 40 Drohnen pro Minute erreichen kann. Das bedeutet, dass die Konflikterkennung und -lösung (Conflict Detection & Resolution, CD&R) zum zentralen Engpass des Systems und nicht mehr zu einer Randfunktion wird.

3. Dynamisches Hindernis und Multi-Constraint-Kopplung

Neben Gebäuden müssen Drohnen auch mit temporären Flugverbotszonen, bemannten Flugrouten, Windfeldänderungen in Echtzeit und Sicherheitsrisiken aufgrund der Menschenansammlung am Boden umgehen – all diese Faktoren machen es für einen einzelnen Flugplanungsalgorithmus schwierig, allein damit umzugehen.

---

1. Problemmodellierung: Flugprobleme in mathematische Probleme umwandeln

1.1 3D-Belegungsraster

Diskretisieren Sie den städtischen Raum in einem Voxelgitter, und jedes Voxel zeichnet seinen Belegungsstatus auf:

Die Voxelauflösung beträgt typischerweise 1–5 m und die CBD-Kernregion kann auf 0,5 m verfeinert werden. Die Gebäudehöhendaten stammen aus einer GIS-Datenbank (Geographic Information System) und werden in Kombination mit Echtzeitsensoren dynamisch aktualisiert.

1.2 Mathematische Definition der 4D-Flugbahn

Die Flugbahn eines einzelnen UAV ist eine zeitlich parametrisierte Raumkurve:$$ \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_{Zeit} + w_3 J_{Energie} + w_4 J_{Risiko}

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

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

h(n) = |\mathbf{p}n - \mathbf{p}{Ziel}|_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) $$Darunter ist die Länge des Korridorsegments, ist der Bodenrisikowert des Korridors (kombiniert Faktoren wie Bevölkerungsdichte, Gebäudetyp, Unfallfolgen usw.) und ist der Risikogewichtskoeffizient. Dies führt dazu, dass A* dazu tendiert, Routen zu wählen, die über Gebiete mit geringem Risiko (z. B. Flüsse, Parks) fliegen, auch wenn diese über leichte Umwege führen.

Einschränkungen von A*: Die Qualität der Luftraumkarte bestimmt die Qualität des Verständnisses. Bei CBD mit hoher Dichte kann die Anzahl der Knoten im Diagramm Hunderttausende erreichen, und die Erstellung des Diagramms selbst ist eine Herausforderung.

2.2 RRT*-Algorithmus: Wahrscheinlichkeitsvollständige asymptotische Optimalplanung

RRT* (Rapidly-exploring Random Tree Star) erkundet mögliche Pfade durch zufällige Stichproben im kontinuierlichen Raum, was sich besonders für hochdimensionale und komplexe Hindernisszenen eignet.

Nächste-Nachbarn-Abfrage – Finden Sie den Knoten, der dem zufälligen Stichprobenpunkt im Baum am nächsten liegt:

Schritterweiterung – Erweitern Sie die Schrittgröße von der Richtung zur Richtung :

Die Kernverbesserung von RRT – Rewire:* Finden Sie alle benachbarten Knoten in der Kugel mit als Mittelpunkt und dem Radius :

Dabei ist die Anzahl der Knoten des aktuellen Baums, die Raumdimension (3D-Szene ) und eine Konstante, die sich auf das freie Raumvolumen bezieht. Dieser Radius schrumpft mit zunehmender Anzahl von Abtastpunkten und gewährleistet so eine asymptotische Optimalität.

Kostenaktualisierung:

Wenn die Kosten von durch reduziert werden können, wird eine erneute Verbindung durchgeführt:$$ \text{Wenn } c(x_{near}) > c(x_{new}) + d(x_{new},, x_{near}),\text{ dann ändere den übergeordneten Knoten von } x_{near} \text{ in } x_{new}

\lim_{n\to\infty} c(\xi_n^) = c^ \quad \text{(fast sicher)}

U_{att}(\mathbf{p}) = \frac{1}{2}k_{att}|\mathbf{p} - \mathbf{p}_{Ziel}|^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}_{Ziel})

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

z_{Schicht}(k) = z_{Basis} + k\cdot\Delta z_{Schicht}, \quad k\in{0,1,\ldots,N_{Schicht}-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}

wobei die Größe der minimalen Geschwindigkeitsänderung ist und auf die Normalenrichtung der -Grenze zeigt.

Die Menge der zulässigen Geschwindigkeiten für den Agenten (schneidet alle Nachbarbeschränkungen und dann die dynamischen Beschränkungen):

Darunter kodiert dynamische Einschränkungen wie maximale Geschwindigkeit und Beschleunigung. ORCA hat in Dichteszenarien von mehr als 40 Bildern/Minute eine Erfolgsquote von 100 % erreicht, mit einer Rechenkomplexität von , was es für den Einsatz in Echtzeit geeignet macht.

---

4. Graphentheoretische Modellierung: städtisches Luftraumnetzwerk

4.1 Erstellung eines Streckennetzdiagramms

Der städtische Luftraum wird als gewichteter gerichteter Graph modelliert:

• Knoten : über Straßenkreuzungen, Gebäudedächern, wichtigen Übergabepunkten
• Kante : Legaler Flugkorridor zwischen zwei Knoten (muss die Überprüfung der Kollisionserkennung bestehen)
• Kantengewichtung : Skalare Gewichtung mit mehreren Zielen

Einschränkungen der Korridorkapazität (die Anzahl der gleichzeitig passierenden UAVs überschreitet nicht die Obergrenze):

Der Belegungsstatus des gesamten Luftraums kann durch einen vierdimensionalen Tensor beschrieben werden ( ist das Voxelgitter, ist die Anzahl der Zeitschlitze):$$ \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 besetztes Voxel}(x,y,z)\text{ im Zeitfenster }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{Klingenwiderstand}} + \underbrace{P_i!\left(\sqrt{1+\frac{v^4}{4v_0^4}}-\frac{v^2}{2v_0^2}\right)^{!\frac{1}{2}}}{\text{Induktionsleistung}} + \underbrace{\frac{1}{2},d_0,\rho_{Luft},s,A,v^3}_{\text{Körperwiderstand}}

\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-Konstante)}

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_{Ankunft}\cdot\mathbf{1}[Ziel] - c_{Schritt} - c_{Konflikt}\cdot\mathbf{1}[Konflikt] - c_{Umweg}\cdot|\mathbf{p}i^t - \mathbf{p}{direkt}| $$Die Bedeutung jedes Elements: ist die positive Belohnung für das Erreichen des Ziels; ist die Zeitstrafe für jeden Flugschritt; ist die Strafe, wenn ein Konflikt auftritt; ist die Umwegstrafe für das Abweichen von der Geraden.

7.2 Double-DQN-Update (diskreter Aktionsraum)

Das Online-Netzwerk wählt Aktionen aus und das Zielnetzwerk wertet Werte aus, wodurch Auswahl und Bewertung entkoppelt werden, um Überschätzungsfehler zu reduzieren.

7.3 Aufmerksamkeitsmechanismus: Nachbareinfluss modellieren

Die Entscheidungsfindung jeder Drohne im CBD erfordert die Erfassung des Status ihrer umliegenden Nachbarn. Der Aufmerksamkeitsmechanismus ermöglicht es dem Agenten , den Einfluss von Nachbarn dynamisch zu gewichten:

Das Aufmerksamkeitsgewicht spiegelt die Relevanz des Nachbarn für die Entscheidungsfindung des Agenten wider. Nachbarn mit geringen Abständen und großen Geschwindigkeitskonflikten erhalten naturgemäß höhere Gewichte.

7.4 PPO-Richtliniengradient (kontinuierlicher/gemischter Aktionsraum)$$

\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}