Planification d’itinéraires urbains de drones à basse altitude : théorie et algorithme dans des scénarios CBD à haute densité

Lorsque des centaines de drones font la navette entre les gratte-ciel en même temps, la planification d’itinéraire n’est plus un simple problème de « voler d’un point A à un point B » : il s’agit d’un problème d’optimisation contraint de haute dimension qui recherche un équilibre entre l’espace tridimensionnel, le temps, l’énergie et la sécurité.

---

Introduction : Pourquoi le CBD est-il si difficile ?

L’espace aérien urbain à basse altitude est généralement défini comme la plage de vol 0–300 m (AGL) au-dessus du sol. Ce niveau de hauteur constitue le principal champ de bataille pour la logistique, l’inspection, les interventions d’urgence et d’autres applications des drones. Le CBD (Central Business District) est le sous-scénario le plus complexe pour trois raisons :

1. Des bâtiments denses forment un « canyon urbain »

Les immeubles de grande hauteur rendent les couloirs de vol disponibles extrêmement étroits et la ligne de vue est bloquée, ce qui réduit la précision du GPS. Les bords des bâtiments génèrent également de fortes turbulences. À basse altitude, en dessous de 50 mètres, ces turbulences peuvent complètement faire perdre le contrôle à un petit multirotor.

2. Les drones à haute densité provoquent des conflits intenses

Dans une scène de banlieue, seuls quelques drones peuvent voler en même temps ; tandis que dans le cadre d’un système de gestion du trafic aérien urbain (UTM) mature, le nombre de drones au-dessus du CBD peut atteindre plus de 40 drones par minute. Cela signifie que la détection et la résolution des conflits (CD&R) deviennent le principal goulot d’étranglement du système plutôt qu’une fonction périphérique.

3. Couplage obstacle dynamique et multi-contraintes

En plus des bâtiments, les drones doivent également faire face à des zones d’exclusion aérienne temporaires, à des itinéraires d’avions habités, à des changements de champ de vent en temps réel et à des risques pour la sécurité liés à la densité de la foule au sol - tous ces éléments travaillant ensemble pour rendre difficile la gestion par un algorithme de planification de trajectoire unique.

---

1. Modélisation de problèmes : transformer des problèmes de vol en problèmes mathématiques

1.1 Grille d’occupation 3D

Discrétisez l’espace urbain dans une grille de voxels, et chaque voxel enregistre son statut d’occupation :

La résolution du voxel est généralement de 1 à 5 m et la région centrale du CBD peut être affinée à 0,5 m. Les données de hauteur des bâtiments proviennent d’une base de données SIG (Système d’information géographique) et sont mises à jour dynamiquement en combinaison avec des capteurs en temps réel.

1.2 Définition mathématique de la trajectoire 4D

La trajectoire de vol d’un seul drone est une courbe spatiale paramétrée par rapport au temps :$$ \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,; \pour tous, t \in [t_0, t_f]

\min_{\boldsymbol{\xi}}; J(\boldsymbol{\xi}) = w_1 J_{len} + w_2 J_{time} + w_3 J_{énergie} + w_4 J_{risque}

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

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

h(n) = |\mathbf{p}n - \mathbf{p}{objectif}|_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) $$Parmi eux, est la longueur du segment du corridor, est le score de risque au sol du corridor (combinant des facteurs tels que la densité de population, le type de bâtiment, les conséquences des accidents, etc.) et est le coefficient de pondération des risques. Cela amène A* à choisir des itinéraires qui survolent des zones à faible risque (par exemple des rivières, des parcs), même s’ils sont légèrement détournés.

Limites de A* : La qualité de la carte de l’espace aérien détermine la qualité de la compréhension. Dans le CBD haute densité, le nombre de nœuds dans le graphe peut atteindre des centaines de milliers, et la construction du graphe lui-même est un défi.

2.2 Algorithme RRT* : planification optimale asymptotique complète de manière probabiliste

RRT* (Rapidly-exploring Random Tree Star) explore les chemins réalisables en échantillonnant aléatoirement dans un espace continu, ce qui est particulièrement adapté aux scènes d’obstacles complexes et de grande dimension.

Requête du voisin le plus proche - Recherchez le nœud le plus proche du point d’échantillonnage aléatoire dans l’arborescence  :

Expansion de l’étape - Étendre la taille du pas de la direction à la direction  :

L’amélioration principale de RRT - Rewire :* Recherchez tous les nœuds voisins de la sphère avec comme centre et rayon  :

Où est le nombre de nœuds de l’arbre actuel, est la dimension de l’espace (scène 3D ) et est une constante liée au volume d’espace libre. Ce rayon diminue à mesure que les points d’échantillonnage augmentent, garantissant une optimalité asymptotique.

Mise à jour des coûts :

Si le coût de peut être réduit via , la reconnexion est effectuée :$$ \text{Si } c(x_{near}) > c(x_{new}) + d(x_{new},, x_{near}),\text{ puis changez le nœud parent de } x_{near} \text{ en } x_{new}

\lim_{n\to\infty} c(\xi_n^) = c^ \quad \text{(presque certainement)}

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

où est la taille du changement de vitesse minimum et pointe vers la direction normale de la limite .

L’ensemble des vitesses réalisables pour l’agent (coupe toutes les contraintes voisines puis coupe les contraintes dynamiques) :

Parmi eux, code des contraintes dynamiques telles que la vitesse et l’accélération maximales. ORCA a atteint un taux de réussite de 100 % dans des scénarios de densité supérieure à 40 images/minute, avec une complexité de calcul de , ce qui le rend adapté au déploiement en temps réel.

---

4. Modélisation de la théorie des graphes : réseau d’espace aérien urbain

4.1 Construction du schéma du réseau routier

L’espace aérien urbain est modélisé sous la forme d’un graphe orienté pondéré :

• Nœud  : au-dessus des intersections routières, des sommets des bâtiments, des points de transfert clés
• Edge  : couloir de vol légal entre deux nœuds (doit réussir la vérification de détection de collision)
• Edge Weight : pondération scalaire multi-objectifs

Contraintes de capacité du couloir (le nombre de drones passant en même temps ne dépasse pas la limite supérieure) :

L’état d’occupation de l’ensemble de l’espace aérien peut être décrit par un tenseur à quatre dimensions ( est la grille de voxels, est le nombre de créneaux horaires) :$$ \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{ voxel occupé par le drone}(x,y,z)\text{ dans la tranche horaire }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{Résistance de la lame}} + \underbrace{P_i!\left(\sqrt{1+\frac{v^4}{4v_0^4}}-\frac{v^2}{2v_0^2}\right)^{!\frac{1}{2}}}{\text{Puissance d’induction}} + \underbrace{\frac{1}{2},d_0,\rho_{air},s,A,v^3}_{\text{Résistance corporelle}}

\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{(constante de von Kármán)}

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

\mathcal{E}{ij}^{vent} = \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_{arriver}\cdot\mathbf{1}[objectif] - c_{étape} - c_{conflit}\cdot\mathbf{1}[conflit] - c_{détour}\cdot|\mathbf{p}i^t - \mathbf{p}{direct}| $$La signification de chaque élément : est la récompense positive pour avoir atteint l’objectif ; est la pénalité de temps pour chaque étape de vol ; est la pénalité lorsqu’un conflit survient ; est la pénalité de détour pour s’écarter de la ligne droite.

7.2 Mise à jour Double-DQN (espace d’action discret)

Le réseau en ligne sélectionne les actions et le réseau cible évalue les valeurs, dissociant la sélection et l’évaluation pour réduire les biais de surestimation.

7.3 Mécanisme d’attention : modélisation de l’influence du voisin

La prise de décision de chaque drone dans le CBD nécessite de détecter le statut de ses voisins environnants. Le mécanisme d’attention permet à l’agent de pondérer dynamiquement l’influence des voisins  :

Le poids d’attention reflète la pertinence du voisin dans la prise de décision de l’agent . Les voisins proches et en conflit de vitesse important reçoivent naturellement des pondérations plus élevées.

7.4 Dégradé de politique PPO (espace d’action continu/mixte)$$

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