都市低空 UAV ルート計画: 高密度 CBD シナリオにおける理論とアルゴリズム

何百ものドローンが高層ビルの間を同時に往復する場合、ルート計画はもはや「地点 A から地点 B まで飛行する」という単純な問題ではなく、3 次元の空間、時間、エネルギー、安全性のバランスを追求する 高次元の制約付き最適化問題 となります。

はじめに: CBD はなぜそれほど難しいのでしょうか?

都市低空域は通常、地上から 0 ～ 300 m (AGL) の飛行範囲として定義されます。この高さレベルは、UAV の物流、検査、緊急対応、その他の用途の主戦場となります。 CBD (Central Business District) は、次の 3 つの理由から最も複雑なサブシナリオです。

1.密集した建物が形成する「都市の峡谷」

高層ビルにより飛行可能な通路は非常に狭くなり、視線が遮られるためGPSの精度が低下します。建物の端でも強い乱気流が発生します。 50 メートル未満の低高度では、これらの乱気流により、小型マルチローターが完全に制御を失う可能性があります。

2.高密度の UAV は激しい衝突を引き起こす

郊外のシーンでは、同時に飛行しているドローンは数台しかない可能性があります。一方、成熟した都市航空交通管理 (UTM) システムの下では、CBD 上空のドローンの数は 1 分間に 40 機以上に達する可能性があります。これは、競合検出と解決 (CD&R) が周辺機能ではなくシステムの中核的なボトルネックになることを意味します。

3.動的障害物と多重拘束結合

建物に加えて、ドローンは一時的な飛行禁止区域、有人航空機のルート、リアルタイムの風況変化、地上の群衆密度による安全リスクにも対処しなければなりません。これらすべてが連携して機能するため、単一の経路計画アルゴリズムだけで対処することが困難になります。

1. 問題のモデリング: 飛行の問題を数学的な問題に変換する

1.1 3D 占有グリッド

都市空間をボクセルグリッドに離散化し、各ボクセルがその占有ステータスを記録します。

障 害 物 飛 行 禁 止 区 域 飛 行 可 能

ボクセル解像度は通常 1 ～ 5 m で、CBD コア領域は 0.5 m まで調整できます。建物の高さデータは GIS (地理情報システム) データベースから取得され、リアルタイムセンサーと組み合わせて動的に更新されます。

1.2 4D 軌道の数学的定義

単一の UAV の飛行軌道は、時間に関してパラメータ化された空間曲線です。$$ \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]

You can't use 'macro parameter character #' in math mode ここで、$d_{sep}$ は安全な最小距離であり、通常の値は 5 ～ 30 m (飛行速度と GPS 精度によって異なります) です。 ### 1.3 多目的最適化問題の一般形式 ルート計画は本質的に、制約付きの多目的最適化問題です。

\min_{\boldsymbol{\xi}}; J(\boldsymbol{\xi}) = w_1 J_{長さ} + w_2 J_{時間} + w_3 J_{エネルギー} + w_4 J_{リスク}

You can't use 'macro parameter character #' in math mode 各サブ項目の意味は次のとおりです。 |内訳 |意味 |代表的な対策 | |------|------|----------| | $J_{len}$ |パスの長さ | $\int_{t_0}^{t_f}\|\dot{\boldsymbol{\xi}}\|\,\mathrm{d}t$ | | $J_{時間}$ |飛行時間 | $t_f - t_0$ | | $J_{エネルギー}$ |エネルギー消費 | $\int P(v)\,\mathrm{d}t$ | | $J_{リスク}$ |地盤リスク |人口密集地上空を飛行する際のポイント | 制約 (すべて必須):- **アクセシビリティ**: $O(\boldsymbol{\xi}(t)) = 0,\;\forall t$ - **運動学**: $\dot{\mathbf{x}} = f(\mathbf{x}, \mathbf{u})$ (UAV 運動学/力学モデル) - **安全な分離**: $\|\boldsymbol{\xi}_i(t)-\boldsymbol{\xi}_j(t)\| \geq d_{sep},\;\forall i\neq j$ - **境界条件**: $\boldsymbol{\xi}(t_0)=\mathbf{p}_{start},\;\boldsymbol{\xi}(t_f)=\mathbf{p}_{goal}$ - **速度制限**: $v_{min} \leq \|\dot{\boldsymbol{\xi}}(t)\| \leq v_{max}$ --- ## 2. 単一マシンのパス計画アルゴリズム 複数マシンのコラボレーションに取り組む前に、まず単一マシンのシナリオにおけるコア アルゴリズムを理解してください。 ### 2.1 A* アルゴリズム: グラフ検索の基礎 A* は、離散化された空間グラフ (ウェイポイント グラフまたは可視性グラフ) 上の最短パスを検索します。各ノード $n$ の評価値は次のとおりです。

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

は 、 開 始 点 か ら ノ ー ド ま で の 実 際 の 累 積 コ ス ト で す 。

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

は 、 か ら タ ー ゲ ッ ト ま で の 許 容 可 能 な ヒ ュ ー リ ス テ ィ ッ ク 関 数 で す 実 際 の コ ス ト を 過 大 評 価 し な い で く だ さ い 。 都 市 空 間 で 一 般 的 に 使 用 さ れ る ユ ー ク リ ッ ド 距 離 ヒ ュ ー リ ス テ ィ ッ ク

h(n) = |\mathbf{p}n - \mathbf{p}{目標}|_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) $$このうち、はコリドーセグメントの長さ、はコリドーの地盤リスクスコア (人口密度、建物の種類、事故の影響などの要因を組み合わせたもの)、はリスク重み係数です。このため、A* は、たとえ多少遠回りであっても、リスクの低い場所 (例: 川、公園) の上を飛行する経路を選択する傾向があります。

A* の限界: 空域図の質が理解の質を決定します。高密度 CBD では、グラフ内のノードの数が数十万に達する可能性があり、グラフの構築自体が課題となります。

2.2 RRT* アルゴリズム: 確率的に完全な漸近的最適計画

RRT* (Rapidly-exploring Random Tree Star) は、連続空間でランダムにサンプリングすることによって実現可能なパスを探索します。これは、高次元で複雑な障害物シーンに特に適しています。

最近傍クエリ - ツリー内のランダムサンプリングポイントに最も近いノードを検索します。

最 も 近 い

ステップ拡張 - ステップサイズをから方向に拡張します。

新 し い 最 も 近 い ラ ン ド 最 も 近 い ラ ン ド 最 も 近 い

RRT の主な改善点 - 再配線:* を中心、半径を持つ球内のすべての隣接ノードを検索します。

ここで、は現在のツリーのノード数、は空間次元 (3D シーン )、は空き領域の体積に関連する定数です。この半径は、サンプリングポイントが増加するにつれて縮小し、漸近的な最適性が確保されます。

コストの更新:

新 し い 近 い 近 い 新 し い

のコストがによって削減できる場合、再接続が実行されます。$$ \text{If } c(x_{near}) > c(x_{new}) + d(x_{new},, x_{near}),\text{ の場合、 } x_{near} \text{ の親ノードを } x_{new} に変更します

サ ン プ リ ン グ 数 が 無 限 に 近 づ く に つ れ て 、 は 確 率 で 最 適 解 に 収 束 す る こ と が 保 証 さ れ ま す 。

\lim_{n\to\infty} c(\xi_n^) = c^ \quad \text{(ほぼ間違いなく)}

You can't use 'macro parameter character #' in math mode ### 2.3 人工ポテンシャル場法 (APF): リアルタイムの王様 APF はターゲットを重力場として、障害物を斥力場として構築し、UAV は合力の作用を受けて移動します。 **重力ポテンシャル** (二次ポテンシャル井戸、ターゲットに向かって引っ張る):

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

は 、 か ら 最 も 近 い 障 害 物 ま で の ク リ ア ラ ン ス 距 離 で す 。 合 力 全 ポ テ ン シ ャ ル 場 の 負 の 勾 配

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

明 示 的 な グ ラ デ ー シ ョ ン コ ン ポ ー ネ ン ト

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

You can't use 'macro parameter character #' in math mode\nabla U_{rep} = k_{rep}\!\left(\frac{1}{\rho}-\frac{1}{\rho_0}\right)\!\frac{1}{\rho^2}\,\nabla\rho \qquad (\rho\leq\rho_0) $$ APF のオンライン更新は通常軽量で、リアルタイムの障害物回避に適しています。ただし、前述の定義に従って最も近い障害物の距離が $\rho(\mathbf{p})=\min_{obs}\|\mathbf{p}-\mathbf{p}_{obs}\|$ で直接計算される場合、単純な実装では通常、少なくとも各ステップで設定された障害物を横断する必要があり、これは約 $O(n_{obs})$ です。距離フィールド、ESDF、またはラスター クエリが事前計算されている場合、シングルステップ クエリは約 $O(1)$) のみになります。しかし、CBD キャニオンには依然としてアキレス腱があります。 **局所最小値** - 重力と反発力が正確にバランスしている場合、UAV は目標以外の点で立ち往生し、前に進むことができなくなります。改善には、ランダム摂動、調和ポテンシャル場、または RRT と組み合わせた PF-RRT アルゴリズムが含まれます。 ### 2.4 ファストトラベリングスクエア法 (FM²): 波面伝播の優雅さ FM² (Fast Marching Square) は、Eikonal 方程式を解くことによって滑らかな軌道を生成します。これは、4D 競合回避に特に適しています。 **アイコーナル方程式** - 波面到達時間を記述する偏微分方程式 $T(\mathbf{x})$: $$ |\nabla T(\mathbf{x})|^2 \cdot v^2(\mathbf{x}) = 1 $$ ここで、$v(\mathbf{x})$ は空間内の伝播速度です。 **クリアランス距離に基づく速度マップ**を構築して、波面が障害物の近くで自然に減速するようにします。 $$ v(\mathbf{x}) = c\cdot\rho(\mathbf{x}) = c\cdot\min_{obs}\|\mathbf{x}-\mathbf{x}_{obs}\| $$ $T(\mathbf{x})$ を解いた後、$T$ フィールドの勾配降下法によってパスが抽出されます。 $$ \dot{\boldsymbol{\xi}}(s) = -\frac{\nabla T\bigl(\boldsymbol{\xi}(s)\bigr)}{\left|\nabla T\bigl(\boldsymbol{\xi}(s)\bigr)\right|} $$**4D 競合回避に拡張:** 時間変化する速度マップを導入し、他の UAV が既に占有している時空領域で $v\to 0$ を許可します。 $$ v(\mathbf{x},t) = v_0(\mathbf{x})\cdot\phi_{競合}(\mathbf{x},t) $$ $\phi_{conflict}\to 0$ の場合、波面は時空衝突ボリュームを自然にバイパスし、衝突のない 4D パスを実現します。 FM² によって生成されたパスは自然に滑らか ($C^\infty$ 連続) であり、追加の平滑化後処理は必要ありません。 --- ## 3. 高密度シーンの中核問題: 競合の検出と解決 (CD&R) 高密度 UAV シナリオにおける基本的な課題は、経路を見つけることではなく、すべての経路が同時に安全であることを確認することです。 ### 3.1 競合の検出 UAV $i$ と $j$ の間の相対位置ベクトルを定義します。 $$ \Delta\mathbf{p}_{ij}(t) = \mathbf{p}_i(t) - \mathbf{p}_j(t) $$ **競合判定条件** (水平 ** と ** 垂直分離が同時に違反されている): $$ \text{競合}_{ij} \iff \|\Delta\mathbf{p}_{ij}(t)\|_{xy} < d_h \;\wedge\; |\デルタ z_{ij}(t)| < d_v $$ NASA UTM CONOPS の一般的なパラメータを参照してください: 水平分離標準 $d_h=30\,\text{m}$、垂直分離標準 $d_v=10\,\text{m}$。 実際には、システムは競合が発生するのを待って対応するのではなく、飛行前に競合を予測する必要があります。 UAV が先読みウィンドウ $[0, T_h]$ 内で一定の速度で飛行すると仮定します。 $$ \mathbf{p}_i(t) = \mathbf{p}_i^0 + \mathbf{v}_i t、\quad \mathbf{p}_j(t) = \mathbf{p}_j^0 + \mathbf{v}_j t $$ **最近接ポイント (CPA、最近接ポイント) 時間:**$$ t_{CPA} = -\frac{\Delta\mathbf{p}_{ij}^0 \cdot \Delta\mathbf{v}_{ij}}{\|\Delta\mathbf{v}_{ij}\|^2}, \qquad \Delta\mathbf{v}_{ij} = \mathbf{v}_i - \mathbf{v}_j $$ CPA での最小間隔: $$ d_{min} = \|\Delta\mathbf{p}_{ij}(t_{CPA})\| $$ $d_{min} < d_{sep}$ かつ $t_{CPA}\in[0, T_h]$ の場合、**予測の競合**があると判断され、解放メカニズムを直ちにトリガーする必要があります。 ### 3.2 競合の解決 武装解除戦略は 3 つのカテゴリに分類され、個別にまたは組み合わせて使用できます。 **戦略 1: 速度調整** 速度スケーリング係数 $\alpha$ を UAV $i$ に適用し、ダイナミクスの許容範囲内で減速または加速します。 $$ \mathbf{v}_i^{new} = \alpha\,\mathbf{v}_i, \quad \alpha\in\!\left[\frac{v_{min}}{v_i},\;\frac{v_{max}}{v_i}\right] $$ 最適な $\alpha$ は、分離制約を満たしながら、元の計画からの逸脱を最小限に抑えます。 $$ \alpha^* = \arg\min_\alpha\;|\alpha-1| \quad \text{s.t. } d_{min}^{new}(\alpha)\geq d_{sep} $$ **戦略 2: 見出しの変更** UAV $i$ の飛行方向を水平面内で $\delta\psi$ だけ回転します。 $$ \mathbf{v}_i^{new} = v_i\begin{pmatrix}\cos(\psi_i+\delta\psi)\\\sin(\psi_i+\delta\psi)\\0\end{pmatrix}

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

You can't use 'macro parameter character #' in math mode 一般的な構成: 東行き $\to z_1$、西行き $\to z_2$、北行き $\to z_3$、南行き $\to z_4$、レイヤー間隔 $\Delta z_{layer}=10\,\text{m}$。これにより、3 次元の衝突問題の次元が 2 次元の問題に削減され、システムの複雑さが大幅に軽減されます。 ### 3.3 分散型調整: 速度制限と ORCA 集中型 UTM はグローバルな最適解を得ることができますが、UAV の数 $N$ に応じて通信オーバーヘッドが $O(N^2)$ 増加し、超高密度シナリオではボトルネックに直面します。分散型ソリューションの中で、**Velocity Obstacle (VO)** とその改良版 **ORCA** は最も成熟したフレームワークです。 **スピード バリア** 定義 - UAV $i$ UAV $j$ の存在により禁止される一連の速度 (時間枠 $\tau$ 内で衝突を引き起こすすべての速度):

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}

こ こ で 、 は 半 径 の 円 盤 球 、 は ミ ン コ フ ス キ ー 和 で す 。 最 適 な 相 互 衝 突 回 避 各 エ ー ジ ェ ン ト は 、 過 度 に 保 守 的 に な る こ と を 避 け る た め 、 回 避 責 任 の 「 半 分 」 の み を 負 い ま す 。 は 、 に 対 す る エ ー ジ ェ ン ト の ハ ー フ ス ペ ー ス 制 約 を 定 義 し ま す 。

ここで、は最小速度変化のサイズ、は境界の法線方向を指します。

エージェントの実行可能な速度のセット (すべての近隣制約と交差し、その後動的制約と交差):

このうち、は、最大速度や加速度などの動的制約をエンコードします。 ORCA は、の計算量で 40 フレーム/分を超える密度シナリオで 100% の成功率を達成しており、リアルタイム展開に適しています。

4. グラフ理論モデリング: 都市空域ネットワーク

4.1 路線網図の構築

都市空域は重み付き有向グラフとしてモデル化されます。

ノード : 道路交差点、建物の屋上、主要な乗り換えポイントの上
エッジ : 2 つのノード間の合法的な飛行コリドー (衝突検出検証に合格する必要があります)
エッジの重み : 多目的スカラー重み付け

回廊の収容力の制約 (同時に通過する UAV の数が上限を超えない):

空域全体の占有状況は 4 次元テンソルで記述できます ( はボクセルグリッド、はタイムスロットの数です)。$$ \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 占有ボクセル}(x,y,z)\text{ タイムスロット }t

You can't use 'macro parameter character #' in math mode ### 4.2 ローター UAV エネルギー消費モデル エネルギー消費はルート計画の重要な最適化目標であり、正確なモデリングが必要です。 **ホバーパワー** (葉要素の運動量理論から導出):

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

こ こ で 、 は ド ロ ー ン の 質 量 、 は 重 力 加 速 度 、 は 空 気 密 度 、 は ロ ー タ ー デ ィ ス ク の 面 積 で す 。 前 方 飛 行 パ ワ ー モ デ ル 、 つ の 物 理 コ ン ポ ー ネ ン ト

P(v) = \underbrace{P_0!\left(1+\frac{3v^2}{U_{tip}^2}\right)}{\text{刃の抵抗}} + \underbrace{P_i!\left(\sqrt{1+\frac{v^4}{4v_0^4}}-\frac{v^2}{2v_0^2}\right)^{!\frac{1}{2}}}{\text{誘導電力}} + \underbrace{\frac{1}{2},d_0,\rho_{air},s,A,v^3}_{\text{身体抵抗}}

パ ラ メ ー タ の 意 味 は ホ バ リ ン グ ブ レ ー ド タ イ プ の 抵 抗 力 、 は ホ バ リ ン グ 誘 導 電 力 、 は ロ ー タ ー 先 端 速 度 、 は ホ バ リ ン グ 誘 導 速 度 、 は 胴 体 の 抗 力 係 数 、 は ロ ー タ ー の 剛 性 、 は ロ ー タ ー の デ ィ ス ク 面 積 で す 。 フ ラ イ バ イ セ グ メ ン ト の エ ネ ル ギ ー 消 費 量 長 さ 、 速 度

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

最 適 巡 航 速 度 単 位 距 離 あ た り の 最 小 エ ネ ル ギ ー 消 費 量

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

You can't use 'macro parameter character #' in math mode 一般的な小型マルチコプター ($m\about 1\,\text{kg}$) の場合、$v^*$ は通常 8 ～ 12 m/s です。 ---＃＃５ 風力場と都市の峡谷効果 ### 5.1 都市風力場のモデリング 都市部の峡谷の風速分布は田舎に比べてはるかに複雑で、ワイブル分布は統計モデリングで広く使用されています。

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{(フォン・カルマン定数)}

こ こ で 、 は 摩 擦 速 度 、 は ゼ ロ 面 変 位 高 さ 、 は 粗 さ の 長 さ で す 。 風 力 発 電 所 が ル ー ト 計 画 に 及 ぼ す 定 量 的 な 影 響 風 補 正 後 の 移 動 時 間 コ リ ド ー 方 向 成 分 に 沿 っ た

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

You can't use 'macro parameter character #' in math mode $TI > 0.3$ のコリドーは通常、高リスクとしてマークされ、プランナーはこのセグメントのエッジの重みを積極的に回避するか、増加させます。 ### 5.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]

You can't use 'macro parameter character #' in math mode --- ## 6. マルチマシン協調最適化: MILP グローバル モデリング $N$ ドローンの共同パスとタイムスロット割り当て問題については、**混合整数線形計画法 (MILP)** モデルを確立して、小規模から中規模 ($N\leq 50$) でグローバルな最適解を取得できます。 **目的関数** (すべてのドローンの合計完了時間とエネルギー消費を最小限に抑える):

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

You can't use 'macro parameter character #' in math mode MINLP は、実際に一般的に使用されるヒューリスティック アルゴリズム (ランダム フラクタル検索 SFS、チーター最適化 MCO など) によって近似的に解決される NP 困難問題です。 --- ## 7. 強化学習ソリューション: MARL と注意メカニズム UAV の規模が 100 を超えると、MILP の計算の複雑さは許容できなくなります。 **マルチエージェント強化学習 (MARL)** は、オフライン トレーニングと非常に高速な推論の代替手段を提供します。 ### 7.1 報酬関数の設計 タイムステップ $t$ で各ドローン $i$ が受け取る報酬:

r_i^t = r_{到着}\cdot\mathbf{1}[目標] - c_{ステップ} - c_{衝突}\cdot\mathbf{1}[衝突] - c_{迂回}\cdot|\mathbf{p}i^t - \mathbf{p}{直接}| $$各項目の意味: は目標に到達した場合のプラスの報酬です。は各飛行ステップの時間ペナルティです。は、競合が発生した場合のペナルティです。は、直線から逸脱した場合の迂回ペナルティです。

7.2 ダブル DQN 更新 (離散アクション空間)

オンラインネットワークがアクションを選択し、ターゲットネットワークが値を評価し、選択と評価を切り離して過大評価バイアスを軽減します。

7.3 注意メカニズム: 近隣の影響のモデル化

CBD 内の各ドローンの意思決定には、周囲の近隣のドローンのステータスを感知する必要があります。 アテンションメカニズム により、エージェントは隣接するエージェントの影響を動的に重み付けすることができます。

注意の重みは、エージェントの意思決定に対する隣接者の関連性を反映します。距離が近く、速度の衝突が大きい近隣ノードは、当然、より高い重みを受け取ります。

7.4 PPO ポリシーの勾配 (継続的/混合アクション空間)$$

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

You can't use 'macro parameter character #' in math mode Clip 操作は、過剰なポリシー更新によるトレーニングのクラッシュを防ぐために、更新ステップ サイズを $[1-\varepsilon,\, 1+\varepsilon]$ (通常は $\varepsilon=0.2$) の範囲に制限します。 **集中トレーニング、分散実行 (CTDE) パラダイム:** - **トレーニング フェーズ**: 評価ネットワーク $V(s^{global};\phi)$ はグローバル状態を使用し、すべてのエージェント情報を認識できます - **実行フェーズ**: ポリシー ネットワーク $\pi_\theta(a_i\mid o_i)$ はエージェント $i$ のローカル観測のみを使用し、通信は行いません --- ## 8. 軌道の平滑化: ベジェ曲線と最小スナップ 経路計画の出力は、多くの場合、一連の離散的なウェイポイントであり、これらのウェイポイントを直接追跡すると、実行不可能な急カーブが発生します。 **軌道平滑化**を通じて動的に実現可能な連続軌道を生成する必要があります。 ### 8.1 ベジェ曲線 次数 $n$ のベジェ曲線は、$n+1$ 制御点 $\{\mathbf{P}_i\}$ によって定義されます。

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

You can't use 'macro parameter character #' in math mode ### 8.2 最小スナップ: クアッドコプターの標準ソリューション クアッドコプター UAV の場合、スナップ (加速度の 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}

You can't use 'macro parameter character #' in math mode 行列 $\mathbf{Q}$ はスナップ積分をエンコードし (解析的に計算できます)、等式制約 $\mathbf{A}_{eq}\mathbf{c}=\mathbf{b}_{eq}$ は、軌道がすべてのパス点を通過するように強制し、セグメント間の位置、速度、加速度の連続性を保証します。 --- ## 9. メソッドの水平比較|方法 |完全性 |最適性 |時間計算量 |リアルタイム |マルチマシンの拡張性 | |------|----------|----------|---------------|--------|-----------| | **A\*** |完了 |最適 (離散グラフ) | $O(b^d)$ |中 |悪い | | **RRT\*** |確率的に完全 |漸近的に最適 | $O(n\log n)$ |より良い |中 | | **APF** |不完全 |保証なし | $O(1)$/ステップ |素晴らしい |良い | | **FM²** |完了 |最適 (連続) | $O(N\log N)$ |中 |中 | | **MILP** |完了 |グローバル最適 | NPハード |悪い |中 ($N\leq50$) | | **オルカ** |確率的に完全 |局所最適 | $O(N^2)$ |素晴らしい |素晴らしい | | **マール+アットン** |完全な確率 |おおよそ |激しいトレーニング、高速な推論 |良い |素晴らしい | **選択の提案:** - **小規模、高度なセキュリティ要件** ($N\leq 20$) → MILP グローバル最適 - **中規模、リアルタイム重視** ($20 < N \leq 100$) → A\* / RRT\* + ORCA 競合解決 - **大規模、高密度** ($N > 100$) → MARL + アテンション メカニズム (推論遅延 $< 10\,\text{ms}$) --- ## 10. 概要と展望 都市部の低高度、特に CBD シナリオにおける高密度の UAV ルート計画は、学際的なシステム エンジニアリングの問題です。この記事では、**単一マシンのパス計画** (A\*、RRT\*、APF、FM²) から **複数マシンの競合解決** (CD&R、ORCA、MILP)、そして **学習メソッド** (MARL、PPO、attention) までの完全なメソッド チェーンを整理し、各コア リンクの正確な数式を示します。 **3 つの主要な未解決の課題:** 1. **リアルタイムのオンライン再計画**: 突然の飛行禁止区域やドローンの故障が発生した場合、システムは影響を受けるすべての軌道の再計画を 200 ミリ秒以内に完了する必要があります。現在、MILP はこの要件をはるかに下回っており、MARL が最も有望な候補です。2. **デジタル ツインと知覚融合**: 正確なリアルタイム 3 次元都市地図 (動的建物建設、仮囲い、気象情報を含む) は、ルート計画の品質の基礎となります。デジタルツイン技術は、センチメートルレベルおよびサブ秒レベルの空域状態の同期を実現すると期待されています。 3. **規制枠組みの技術的実装**: 中国民用航空局 (CAAC) の低高度管理規制、ヨーロッパの EASA U-Space、およびアメリカの FAA UTM CONOPS にはすべて、紛争解決時間、飛行計画の提出形式、緊急着陸手順などに関する明確な要件があり、アルゴリズムの設計は規制の境界と深く結び付く必要があります。 > 数学的な観点から見ると、都市部の低空航空路計画は、非凸、非線形、混合整数、マルチエージェント、リアルタイムの制約付き最適化問題です。 「ワンクリックで問題を解決」できる単一のフレームワークはありません。エンジニアリングの実践では、多くの場合、マルチレベルのハイブリッド アーキテクチャになります。地図計画は戦略層で使用され、ORCA は戦術層で使用され、APF は緊急層で使用され、これらが一体となって堅牢な航空交通管理システムを形成します。 --- **主な参考文献:**1. カラマン、S.、フラッツォーリ、E. (2011)。 *最適な動作計画のためのサンプリングベースのアルゴリズム* International Journal of Robotics Research、30(7)、846–894。 2. Van den Berg, J.、Guy, S.J.、Lin, M.、および Manocha, D. (2011)。 *相互 n 体衝突回避。* ロボティクス研究、3–19。 3. Zeng, Y.、Xu, J.、Zhang, R. (2019)。 *回転翼 UAV との無線通信のエネルギー最小化。* IEEE Transactions on Wireless Communications、18(4)、2329–2345。 4. ミューラー、M.W.、ヘーン、M.、ダンドレア、R. (2015)。 *クアドロコプターの軌道生成のための計算効率の高いモーション プリミティブ。* IEEE Transactions on Robotics、31(6)、1294–1310。 5. ブリテン、M.、ウェイ、P. (2019)。 *自律型航空管制官: 深いマルチエージェント強化学習アプローチ* arXiv:1905.01303。 6. Bertram, J.、Wei, P. (2020)。 *高密度都市エアモビリティのための分散型計算ガイダンス* AIAA 航空フォーラム。 7. ヴァラヴァニス、K.P.、ヴァハツエヴァノス、G.J. (編)。 （2015年）。 *無人航空機のハンドブック。* スプリンガー。 8. Augugliaro, F.、Schoellig, A.P.、D'Andrea, R. (2012)。 *クワドロコプター フリートの衝突のない軌道の生成。* IEEE/RSJ IROS、3977 ～ 3982。