ステップバック・セルオートマトンを用いた航空交通シミュレーションAir Traffic Simulation by Step Back Cellular Automaton

81

hp160268 ポスト「京」研究開発枠（萌芽的課題 2） R&D category for post K computer (Exploratory Challenges 2)

ステップバック・セルオートマトンを用いた航空交通シミュレーション

Air Traffic Simulation by Step Back Cellular Automaton

長岡慎介，立川智章，藤井孝藏

Shinsuke NAGAOKA, Tomoki TATSUKAWA, Kozo FUJII 東京理科大学 工学部

Faculty of Engineering, Tokyo University of Science 要旨 近年，航空機数の急激な増加に伴い，アジア太平洋地域を中心に世界中で航空機の遅延が発生 している．本研究では，航空機の渋滞を緩和するためのシミュレーションツールの開発を目指す． ここでは複雑な数式を使用せず，複雑な航空交通シミュレーションが可能なセルオートマトンを ベースとしたステップバック・セルオートマトンを提案する．一般的なセルオートマトンの計算 コストは大きくないが，各航空機の機体特性を厳密に考慮した際に計算コストが非常に高くなる こと，対象とする航空機数が非常に多いことから詳細な航空機モデルへの拡張を考えると大規模 並列化は必要不可欠である．そこで本稿では，予備調査としてセルオートマトンによる航空交通 シミュレーションの並列化手法の検証を実施した． キーワード：セルオートマトン，ステップバック・セルオートマトン，航空機渋滞モデル， 航空交通シミュレーション，並列解析，並列化効率 Abstract

In recent years, transport aircraft arrival delays occur worldwide, especially in the Asia-Pacific region, due to rapid increase of the number of flights. The objective of this study is to develop a simulation tool to mitigate the traffic congestion of aircraft . Here, we propose Step Back Cellular Automaton (SBCA) model based on Cellular Automaton (CA) that does not use complex mathematical formulas and can perform complex air traffic simulations. Although the calculation cost of a general cellular automaton is not large, the calculation cost becomes very high when the aircraft characteristics of each aircraft are strictly considered. Moreover because the number of target aircraft is very large, large-scale parallelization is indispensable. In this paper, therefore, we verified the parallel method of air traffic simulation using CA as a preliminary study.

Keywords：Cellular Automaton, Step Back Cellular Automaton, Air Traffic Model,

Air Traffic Management Simulation, Air Traffic Model, Parallelization Method, Parallel Efficiency © 2019 Research Organization for Information Science and Technology All rights reserved.

Received: 30 March 2018 Accepted: 21 October 2019 Available online: 30 October 2019

81 1. 研究の背景と目的 近年の新興国の経済成長や格安航空会社(LLC)の普及などを背景に，航空旅客機数は急速に増 加している．それに伴い，航空機の需要も大幅に増加し，今後のさらなる需要拡大が見込まれて いる．航空機が着陸する際，空港の着陸可能容量を超える数が飛行してきた場合には，全ての航 空機に着陸許可を出すことはできない．着陸許可を得られなかった航空機は，決められた航路を 遠回りしたり（ベクタリング），一定のポイントで旋回し続けたり（ホールディング）することで 間隔調整を行う．図1 は 2013 年 3 月 10 日における東京国際空港へ南側から流入する全ての着 陸機の軌跡である．東京国際空港周辺では，各航空機が様々な軌跡を描いている．これは，空港 周辺で，間隔調整が頻発していることを意味している．この間隔調整により，航空機の到着時間 の遅延や燃料消費量の増加という社会経済的な問題を併発させる．加えて今後の航空機の更なる 増加は，管制官の能力の限界を超えると言われており，安全面の問題も懸念されている． そこで，本研究では，航空機 の挙動をモデル化し，東京国際 空港周辺のみならず，上流部分 から予め間隔調整を実施する ことで，空港周辺の渋滞の緩和 にどの程度の影響を与えるか を図る．実際の航空機の交通流 は，個々の航空機の相互作用に より挙動が変化する非常に複 雑な現象であるが，解析手法と して複雑な現象のモデル化を簡素なルール設定のみで行うことが出来るセルオートマトン (Cellular Automaton : CA)[1]をベースとしたステップバック・セルオートマトン(Step Back Cellular Automaton : SBCA)[2]を用いて，東京国際空港周辺で生じる航空機の緩和の一助とな ることを目指したシミュレーションツールの構築を目指す．

本稿では初期的検討として，本手法の簡易的な適用例と，将来の日本全体を対象とした詳細な 航空機渋滞モデルへの拡張をする際に使用する本手法の並列化手法についての検証結果を示す．

82 2. 計算モデル 2・1 ステップバック・セルオートマトンの基本的な考え方 本手法は，一般的な CA モデル に時間間隔調整アルゴリズムとし てステップバックを加えた手法で ある．航空機は，道路のようにあ る程度一定に定められてた航路を 通って目的の空港に向かう．その 際，基本的には前方の航空機を追 従する形になる．自動車や鉄道との最大の違いは，渋滞が生じた際にその場に留まることができ ない点である．また，上下前後左右の航空機との安全間隔が厳密に定められており，その距離を 厳守する必要もある． 図 2 は，SBCA の時空図である．SBCA は，一次元 CA を用いて各航路をセルで分割し，その 航路を粒子（航空機）が移動していくことを考え，それぞれの粒子に速度 s（1 ステップに s セル 進めるか）を割り振る．その上で，前方間隔 d，加算距離 BD を設定し，前方間隔の条件に従っ て各粒子の総移動距離を加算していくモデルとなる．このモデルは，前方 d 個のセル全てが粒子 に占領されていない場合は割り振られた速度分進み，どれか一つでも占領されているセルがある 場合は BD セル後ろに戻ることで総移動距離を加算していく．なお，粒子が戻る際，途中に他の 粒子が存在する場合は戻ることも出来ずに，その場に留まるものとする．このようにすることで， 複雑な数式を用いることなく，実際の航空機がベクタリングやホールディングにより，ある一定 の安全間隔を厳守する振る舞いを 1 次元セル上で表現する．またセルで分割された同一航路上を 移動しつつも，混雑状況に応じて，間隔調整を実施した際に生じる，総燃料消費量に違いを持た せることが出来る． 2・2 解析例 本研究で対象とするのは，東京国際空港へ進入す る全ての国内線である．現時点では各ルートを簡略 化し，全ての航空機は一直線に出発空港から東京国 際空港に向かうものと仮定した． なお，航路は各出発空港から東京進入管制区まで のローカルエリア，東京進入管制区から Final Approach Fix(FAF)と呼ばれる航空機の間隔調整を終 えるべき地点までの東京進入管制区エリア，そして FAF から東京国際空港までの FAF エリアの 3 種類に 分類した．東京進入管制区エリアおよび FAF エリア に関しては，東京国際空港からある一定距離の同心円のエリアと仮定した．また，ローカルエリ Fig. 2 Time space distribution of SBCA

(BD=3 , d=8, s=5)

Fig. 3 An image of flight routes of SBCA

83 アは，日本全体を 8 つのエリアに分割し，それぞれのエリアを出発する航空機は東京進入管制区 エリアにて出発エリア毎に合流をするものとした．合流は FAF エリアにおいても北側進入機と南 側進入機に分類をして行われる．具体的な模式図を図 3 に示す．上述のモデル化を基に東京国際 空港のホームページ内に掲載されるデータ[3]を参考とした 2016 年 3 月 22 日の時刻表を作成し， この時刻表に則り実施した解析結果を以下に示す． 図 4 に SBCA の解析結果を示す．図では出発空港のエリア毎の遅延機の状況を示している．こ こで遅延機とは，時刻表に記載されていた到着時間と比較して，解析によって得られた到着時間 が遅れているものを指す，図より航空機数が多い西日本側の遅延機の割合が東日本と比べて高い 傾向があることがわかる．特に「九州・沖縄」エリアの遅延機の割合が最も高く，平均遅延時間 は約 6 分程度となっている．

図 5 に CARATS Open Data[4]を用いたデータ解析の結果を示す．CARATS Open Data は国土交 通省により公開されている航空機位置・時刻情報に関するオープンデータである．本研究では 2012 年度のデータを解析に用いた．対象となる期間は 2012 年 5 月 7 日～13 日，7 月 7 日～13 日， 9 月 7 日～13 日，11 月 7 日～13 日，2013 年 1 月 7 日～13 日，3 月 7 日～13 日の計 42 日分であ り，図では対象期間における出発空港のエリア毎の平均値を示している．図より，CARATS Open Data においても西日本エリアの遅延率が高く，「九州・沖縄」エリアの遅延率が最も高い傾向が あることがわかる．SBCA 解析結果では，東京進入管制区に近づくにつれて西日本エリアの航空 機について多くの間隔調整が行われているが，実際に日常的な実運用においても同様の傾向がみ られることから定性的な傾向を再現できていると考えられる．一方，中部以北のエリアでは SBCA

の解析結果と CARATS Open Data の傾向に違いが見られる．東京進入管制区の北側から進入して くる航空機には東日本エリアからの国内線だけでなく国際線が多数存在する．今回の SBCA の解 析は国内線のみを対象としていたため，国内線が早着することになり全体として遅延機数が少な く評価されたと考えられる．その中で，関東，東北の羽田到着便には遅延が生じ，特に遅延率グ ラフに大きな違いが見られる．これらの地域については，遅延時間は大きくないものの，便数自 体がそれぞれ一日 3 便(八丈島)，26 便と少ないため遅延率（遅延機数／便数）に大きな影響が出 てしまったと考えられる．以上から，国内線の影響が大きな西日本エリアからの航空機の遅延状 況の傾向は SBCA モデルで定性的に再現できていることと考えられる．簡略化した解析条件の厳 密化，特に各航空機の固有データを詳細に計算し，海外からの進入なども考慮することで，SBCA 解析による遅延状況の再現性を高めることが期待できる．

84 3. 並列計算の方法と効果（性能） 前述の SBCA を用いた将来的な日本全国の航空機を対象とした詳細なシミュレーションの実 施に向け，一般的な CA による簡単な交通流モデルを用いて，並列化方針を検討する． 初めに，並列のループをエージェント（以下，粒子と呼ぶ）ベースで廻すか，セルベースで廻 すかであるが，実距離をベースに個別セルを想定することを前提とすると，当該研究が対象とす る領域の広さに比べてエージェントの数は少ない．具体的には，日本国内の１日のフライト数は 6,000 機程度である．この観点から，セルベースでループを廻すと無駄が多く，エージェントをベ ースにループを廻すことが効率的であると判断した．並列化指針の検討に用いるモデルは，一般 の交通流解析でよく利用されるルール 184 に則った一次元セルオートマトンによる簡単なモデル とし，前方に粒子が無い場合のみ粒子は前方に移動できる．従って，粒子間の通信で必要となる のは，基本的には自身の粒子の前方粒子の位置データのみである． 3・1 検証方法 並列化手法の重要な要素として，ノー ド間通信の考え方を評価した．逐次的な 一対一通信と一定の段階でまとめて集団 通信を実施する 2 種類の方法を利用して 計算速度の比較を行った．なお，領域分 割は各ノードが担当する粒子が一定にな る様に粒子ベースの領域分割を行う． 一対一通信では図 6 に示すように，各 ノードの最後方の粒子位置情報を一つ手前のノードに送信するのみなので，各ノードの通信は 1 Fig. 4 Simulation result of SBCA

Fig. 6 Example of one-to-one communication

Fig. 7 Example of group communication Fig. 5 Analysis result of CARATS Open Data (Period: One week every two months from May

85 つの粒子位置のみとなる．次に，集団通信のイメージを図 7 に示す．同図は，ノード 1 に全ての 粒子位置データを送信している様子を表している．同様に全てのノードはこのプロセスを経て全 ての粒 子情報を把握するので，モデルの増大に伴って通信量が大幅に増加する．当該研究で対 象とする 航空交通の問題では，特定の空港の着陸機の動きが，移動中の他の航空機や別の空港 を離陸する 航空機の出発時刻などに影響を与える．各粒子の情報が他のほとんどの粒子に影響 することにな り，逐次通信の場合も他のノード内の全ての粒子との通信が発生すると考えられ る．その場合， このような集団通信のメリットが出てくる可能性があると考え，比較検討を行っ た． 3・2 並列化効率の検証 前述の 2 つの通信方法を用いて実施した，ストロング・スケーリングによる並列化効率の検 証結果を示す．解析条件は，1 日分のフライトを想定し，時間刻み幅 1 秒で 86,400 ステップと した． また，ポスト「京」時代に向けて，対象となる航空機数はさらに増加し，航空機の他に 鉄道や人 の流れなどを考慮すると，粒子数は大幅に増加することが予想されるが，「京」利用 の段階では， 日本上空の 1 日のフライトを想定し，6,000 粒子とした． 検証は，集団通信と一対一通信で各々6 ケース（1PE，50PE，100PE，150PE，200PE， 250PE）計 12 ケース実施した．粒子の機体特性を考慮する際には，Eurocontrol により提供され る Base of Aircraft Data(BADA)[5]を用いて，目的関数として速度，抗力，高度，推力，燃料消費

量や質量などを考慮する予定であるが，本稿で述べるプレリミナリ―な検証では各粒子の機体 特性は速度のみとした．しかしながら，将来的な航空機の厳密な機体特性の導入時の計算負荷 の増加を視野に入れ，速度以外の目的関数として，抗力，高度，推力，燃料消費量，質量の算 出やそれに伴う計算を考慮した際の計算量の増加を現状の 10 倍程と推定して，仮想的な計算負 荷を与え，解析全体における通信量の割合を意図的に減少させた． 4. 研究成果 得られた高速化率の推移を図 8 に示す．並列解析を実施しなかった場合の 1 ケース当たりの 解析時間は約 1335 秒であった．この計算を集団通信及び一対一通信で 250 並列解析を実施した 所， 計算時間は共に 16 秒まで短縮された．高速化率（スピードアップ）では集団通信が 78 倍，一対一通信が 80 倍である．この時，解析時間全体における通信時間が占める割合は 45%程 度になる． これを並列化効率で表すと，集団通信が約 32%であるのに対して，一対一通信が約 31.2%である． 通信コストが小さい一対一通信の方が，若干ではあるが，高い並列化効率を得 られるものの大きな差はない．これは，並列化手法の違いが及ぼす影響は現在送受信する情報 が位置情報のみであり，現時点で想定している計算条件下ではそれほど大きくはないためであ ると考えられる．送受信する情報や通信方法を含む並列化アルゴリズムのさらなる検討は必須 と考えられるが，いずれも 1 ケース当たりの計算時間という観点では大幅な削減が可能とな

86 る．また今後，機体モデルやルールを高度化するに伴い各機体の計算コストが増大するため， 並列化効率は向上すると考えられる． 本研究で目指すのは，現在の航空交通流を再現 した上で各航空機のパラメータを調整し，上流側 からの安全間隔の調整を実施し，様々な問題を解 消するツールとすることである．そのためには， このような計算を何万ケースも実施する最適化 計算が必要になるため，並列計算による各ケース の計算時間の削減は必要不可欠である．また，本 研究で対象とするのは，各航空機の機体特性を考 慮するような個別粒子の計算コストが高くなる だけでなく，本例で示したような前方航空機との位置関係のみならず，前後上下左右の航空機に 加えて，さらに広域の航空機との位置関係が必要になる問題である．必要最低限のデータのみを 取得する一対一通信を用いると解析コード実装が複雑になると共に，通信量もケース毎にまばら になり，同期待ちのための並列化効率の低下も懸念される．故に，本研究で用いる手法としては， 集団通信により，全ての航空機の位置データを取得し，柔軟な設定でシミュレーションを実施す る方が，対応は容易であり，適していると考えられる． 5. まとめと今後の課題 本論文では，今後のますますの航空機数の増加に伴い，航空機の空での渋滞が最も懸念され る東京国際空港を対象とした航空機渋滞モデルの構築を行い，SBCA による解析がある程度現 状の航空交通流の様子を再現出来ることを示し，併せて，本手法を用いた並列解析を実施する 際に重要となる並列化手法の検証を実施した．現在の航空管制では，管制官が全体の情報を見 ながら管制を行っているものの，局所的な間隔調整が行われている．そのため，現在の運行を 模擬する場合であれば前後の機体との一対一通信で再現できると考えられるが，より多くの機 体情報を活用した航空管制の検討を行うためには各航空機が全体の情報にアクセスできるよう な仕組みにしておくことが望ましい．また，各航空機の機体特性を厳密に考慮するための計算 コストが通信量と比較して高くなるような問題であることから並列化手法として集団通信を用 いる方が適していると考えられる．ただし，共有する情報についてはさらなる検討が必要であ る．今後は，SBCA の航空機の移動に関する計算を BADA を用いて実施し，現状の航空交通流 の再現を目指す．また，ケースごとのノード割り当てによる並列化についても検討する．ルー ルの高度化に伴い機体当たりのコストが増大していくとともに，レジリエンスやロバスト性を 考慮した最適化を行っていくことから「京」のような大規模マシンでの実施が有効であると考 えられる．

87 謝辞 本研究は，ポスト「京」で重点的に取り組むべき社会的・科学的課題に関するアプリケーション 開発・研究開発，萌芽的課題 2 の成果によるものです (課題番号 : hp160268) ． 参考文献 [1] 西成活裕. 図解よくわかる渋滞学. ナツメ出版企画株式会社, pp34-43, 2009. [2] 立川智章，安齋洸也，藤井孝藏: 1 次元セルオートマトンを用いた羽田空港周辺の航空機渋滞 モデル．第 22 回計算工学講演論文集(CD-ROM), B-06-3, 埼玉, 2017 年 5 月 [3] フライト情報．羽田空港 国際線旅客ターミナル ホームページ, https://www.tokyo-airport-bldg.co.jp/flight/ [4] 将来の航空交通システムに関する研究会：将来の航 空交通システムに関する長期ビジョン-戦略的な航空交通システムへの改革，国土交通省，2010 年 URL: http://www.mlit.go.jp/common/000123890.pdf