衝突回避のための最適な航空経路選択への応用 "Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management" by Tobias Stollenwerk et al. (2017).

Table of Contents

文献情報

タイトル Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
著者 Tobias Stollenwerk, Bryan O’Gorman, Davide Venturelli, Salvatore Mandra, Olga Rodionova, Hok K. Ng, Banavar Sridhar, Eleanor G. Rieffel, and Rupak Biswas
arXiv:1711.04889 [quant-ph]

概要

大西洋横断飛行において、風に対する最適な軌道を採用することで生じるフライト間の衝突を、フライトの遅延によって回避するという問題がある。これをD-Wave 2XおよびD-Wave 2000Qを用いて解いた。

問題

航空における交通量は年々増加しており、使用可能な空域が限られてきている。大西洋に存在するジェット気流の影響を受ける大西洋横断飛行(NAT)において風に対する最適な軌道が採用されると、潜在的な衝突が発生する。

大西洋の気流の様子(http://www.surfline.com/surfdata/chart_viewer/?chart=natlwind&id=2142)

スケジューリング問題として捉えると、潜在的な衝突を回避するために以下の対処方法が考えられる。

フライトの出発時間を遅らせる
フライトの軌道を局所的に変更する

今回は簡単のために出発時間の遅延のみを考慮し、全てのフライトにおける遅延の総和と全ての衝突の総和を最小化する。

最適化問題の定式化

組合せ最適化問題の種類: スケジューリング問題
変数: $d_{i,l} \in \{0,1\}$ (出発時の遅延 $d_i (= 0,1,2 …, d_{\mathrm{max}})$ が$l$の場合$1$, そうでなければ$0$)
目的関数:

$$ f = f_{\mathrm{encoding}} + f_{\mathrm{delay}} + f_{\mathrm{conflict}} $$

ただし、$\Delta_d$を遅延の分解能、$N_d$を遅延の総数、$N_f$をフライトの総数とする。

1つのフライトの遅延を、1つに制限する:

$$ f_{\mathrm{encoding}} = \lambda_{\mathrm{encoding}}\sum_{i=1}^{N_f}(\sum_{l=0}^{N_d}d_{i,l}-1)^2 $$

全てのフライトにおける遅延の総和:

$$ f_{\mathrm{delay}} = \Delta_d\sum_{i=1}^{N_f}\sum_{l=0}^{N_d}ld_{i,l} $$

全ての衝突の総和:

$$ f_{\mathrm{conflict}} = \lambda_{\mathrm{conflict}} \sum_{k} \sum_{l,l’|\Delta_d (l-l’) \in D_k, i,j \in I_k | i<j} d_{i,l} d_{j,l} $$

衝突グラフ: 頂点を各フライト、辺を衝突(少なくとも1つ衝突が存在するフライト間を結ぶ)とするグラフ。最大許容遅延時間$d_{\mathrm{max}}$が大きいほど、結合コンポーネント(接続された頂点のまとまり)は高密度となり、その数は小さくなる。また、$d_{\mathrm{max}}$に対して、経験則の指数$\alpha$の依存性が存在する。問題設定が困難な場合は衝突グラフを木分解し、遅延を伝播することによって最適値を容易に見つけることができる。

設定空間の離散化: 遅延時間を細かく離散化するほど、必要となる量子ビットの数は大きくなる。離散化の粒度および最大遅延許容時間が、最適解の質に与える影響を考えることは、量子アニーリングを有効に利用する上で重要である。$d_{\mathrm{max}}=3$の場合を除いて、$d_{\mathrm{max}}$をさらに増加させても、最小遅延の総和は減少しないため、より大きな問題のインスタンスであっても、ある程度大きい$d_{\mathrm{max}}$で十分である。一方、遅延離散化$\Delta_d$は、高品質の解を得るためにはできるだけ細かいものでなければならない。

用いたデータセット

2012年7月29日大西洋横断飛行(NAT)における984のフライトに関して、事前に計算された風に対する最適な軌道(巡航高度と一定の速度を含む)

D-Waveマシン実装上の工夫

ハイパーパラメータの設定: 最大7回の飛行と9回の衝突を伴うすべての変数において、$(\lambda_{\mathrm{conflict}},\lambda_{\mathrm{encoding}})$が妥当(両方が制約を満たす)である場合とそうでない場合の境界はボックス状になり、両者の妥当性が独立している。

埋め込み: D-Wave 2Xでは、最大$N_f = 50$、$N_c = 104$、D-Wave 2000Qでは$N_f = 64$、$N_c = 261$までの変数を埋め込むために、D-Waveのヒューリスティック埋め込みアルゴリズムを使用した。

結果

D-Wave 2Xおよび D-Wave 2000Qから得られた結果を、正確な最適解が求まるMax-SATソルバーの結果と比較した。各QUBO変数について、アニーリング処理を104〜106回実行した。細かな離散化とより大きな問題変数の場合に、以下の式で表される成功確率99%の解時間$T_{99}$は増大し、成功確率が減少することが分かった。

$$ T_{99}=\frac{\ln (1-0.99)}{\ln (1-p)}T_{\mathrm{Anneal}} $$

成功確率の原因として考えられるD-Wave上の仕様の精度を表す尺度として、最大係数比$C_{\mathrm{max}}$が用いられる。

$$ C_{\mathrm{max}} = \max\left[\frac{\max|h_i|}{\min|h_i|},\frac{\max|J_{ij}|}{\min|J_{ij}|}\right] $$

成功確率は、強磁性内部論理量子ビット結合$J_F$の選択に依存する。すべての埋め込み可能な変数に対する$J_{\mathrm{max}}$を用いた場合、精度の高い$C_{\mathrm{max}}$が増加するほど、最大成功確率が大きく低下する。成功確率は$C_{\mathrm{max}} \approx 30$付近で消滅するため、D-Wave 2000Qの精度が約1/30に相当することが分かる。一般に$C_{\mathrm{max}}$は、問題の大きさや細かな離散化とともに増加するため、大きな問題変数と細かな離散化に対する最適化に長い時間を要する。

本記事の担当者

丸山尚貴

Post Views: 424

T-QARD Harbor

衝突回避のための最適な航空経路選択への応用 “Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management” by Tobias Stollenwerk et al. (2017).

文献情報

概要

問題

最適化問題の定式化

用いたデータセット

D-Waveマシン実装上の工夫

結果

本記事の担当者