この記事の概要
いくつかの交差点の集合における車の流れを良くすることが最終的な目標です.
これに対し, 信号機に割り当てられた信号パターンと, それによる車の量の関係性を元に最適化問題に定式化します.
そして, その最適化問題を量子アニーリング(D-Wave)を用いて解くことにより, 最終的にある時刻における交差点の車の流れを良くするような信号パターンの割当を決定します.
基本的な量子アニーリングの解説(解ける問題のクラスなど)は省略します.
量子アニーリングの基礎的な内容などはここが参考になります[1].
本記事の具体的な説明の流れは以下のようになります.
1. 問題設定の説明:どういう交差点の状況を考えるのか
2. 具体的な目的の説明:車のフローを良くするために, 具体的にどのような評価指標を採用するのか
3. モデル化:1,2を数式で表すとどうなるか
4. 実験:3のモデルを用いて具体的な数値実験を行う
5. 結論
今回紹介する論文
本記事のメインで紹介する論文です. 豊田中央研究所×東大がpublishした論文です.
Traffic Signal Optimization on a Square Lattice using the D-Wave Quantum Annealer
上の論文の元になったモノです.
Chaotic Ising-like dynamics in traffic signals
問題設定
今回考える問題設定を説明します.
今回の問題は, ある時刻において, 与えられた交差点において信号のパターンを決定することによって車の流れを良くすることが目的です.
これに対しまず, 与えられる道路はどういうものかとそれに対し何を決定するのかについて説明します.
そして, 車のフローを良くするために, どういう評価指標を用いるのか(目的関数)について説明します.
考える道路状況
今回の問題では, 正方格子状の交差点の集まりを対象に考えます.
具体的に言うと以下の図のようになります([2]より引用).
すなわち, ある交差点は4つの交差点と繋がっており, 格子上に交差点(信号機)が存在します.
車の振る舞い
今回車の振る舞いは, 交差点で 直進 or 左折 or 右折 するとします(図1 (b) ).
このとき, 車が直進する割合を, とします.
そして, 左右に曲がる割合は等しく, それぞれ とします.
これにより, ある道路に存在する車の量は, 水平 or 垂直方向の信号機の色によって異なり, それぞれ図1(b)の左と右のようになります.
信号機のパラメーター(決定するもの)
今回決定する信号機のパラーメーターは, ある時刻における信号機の色とします.
もう少し具体的に説明すると, ある時刻において信号機の垂直方向を青にするか(図1bの左) or 水平方向を青にするかを決定します.
交差点の信号機の青赤のパラメーターをとし,
のとき, 垂直方向の信号機が青, のとき, 水平方向の信号機が青 が割当られているとします.
今回この垂直方向を青にするか or 水平方向を青にするかを決定します.
目的
今回の最終的な目標は, 考える交差点の集まりにおいて, 車の流れを良くすることです.
この目標の達成に対し具体的には, 交差点で待っている車の量を均一にすることを目標とします.
ある交差点に接している道路のうち, 待っている車の方が多い方向の信号機を青に割り当てます.
すなわち, 交差点において, 垂直方向の道路の車量が, 垂直方向の道路の車量よりも多い場合, を割当, 垂直方向の道路の車の量を減らします.
逆も同様です.
このように, 道路に存在する車の量を均等に保つことによって, 道路全体の流れを良くすることを目指します.
もちろん, ある時刻ある道路における車の量は, 前の時刻の隣接する交差点の信号の割当によって変化します.
なので, 次の節ではそれらを定式化し, 具体的な数式モデルを作っていきます.
モデル化
ここでは, 実際に今回の問題を数式にモデル化していきます.
ある時刻における信号機の割当と車の進行方向の割合を元に,
次の時刻における道路の車の量を表します.
そしてある交差点に隣接する道路で待っている車の量を均等にするような信号機のパターンを決定する最適化問題を構築していきます.
車の量
時刻における交差点から交差点への道路の車の量を ( )とします.
また, 時刻での, 交差点との信号機のパラメーターをそれぞれ, とします.
すると, 時刻での道路の車の量は以下のようになります.
ここで, は道路の方向パラメーターで, 道路が垂直方向なら, 道路が水平方向ならです.
また, です.
道路の方向で車量が変わるのは, 車の進行する割合が異なるためです.
次に, 交差点で待つ車の量の平均値をを元に求めます.
このとき, 最終的に車の量を均一することを考えて, 垂直方向の量をプラス, 水平方向の量をマイナスで考えます.
が0に近いほどある交差点に接する道路の車の量は均一ということになります.
1つの方向に対して, 2つの道路から車が来るので, しています.
式(1), (2)より, 時刻での交差点に接する道路の車量は以下のようになります.
これで, 交差点での信号機の色と, 車の量の関係式ができました.
単純に考えると, のときは, 垂直方向の車の量が多いので, 垂直方向を青にすれば良さそうです.
逆になら, 水平方向を青に割り当てれば良さそうです.
これを全ての交差点に対して行列形式で書き直すと, 次のようになります.
目的関数
今回の目的は, ある交差点において水平方向と垂直方向で待っている車を均等にすることです.
すなわち, を0に近づけるような信号の割当 を決定することです.
よって, 目的関数は以下のように設定すれば良さそうです.
二乗の形にすることで, 0が最小値となります.
実験
50 × 50 の交差点に対して, 今回のモデルを用いて信号の割当を決定します.
今回は以下の3つの手法を比較します.
1. (3)式を計算して, ならば, , ならば, を割当てる, ルールベースの割当(以下局所探索)
2. (8)式を, D-WaveのライブラリのSimulated Annealingを用いて解く(以下SA).
3. (8)式を, D-Waveの量子アニーリング(Quantum Annealing)を用いて解く(以下QA).
実験方法
まず, の初期状態として, 各交差点のを, [-5.0, 5.0]の間でランダムに決定します.
も {-1,1}のどちらかをランダムに割り当てます.
その後, 次の時刻の信号の割当を上の3つの手法で求めます.
そして決定した信号の割当を元に, を式(3)より計算します.
これらを元に次の時刻の信号の割当を求める, を求める,.......
というのを繰り返します.
結果
パラメーターを, とし, 時刻で実験を行った結果が以下の図2左aになります.
QAを用いた結果が, 一番良い値を一番多く出しており, QAの優位性がわかります.
また, (車が直進する割合に関する量)を変化させて実験を行った図が, 図2右bになります.
こちらは, 全ての時間に対してハミルトニアン(8式)の平均値で比較しています.
が0.7あたりから, ハッキリとSAよりもQAの方が良い結果を得られていることがわかります.
が1に近づくにつれて, QAでの結果がよくなる考察が本論文では考察されています.
考察
が1に近づくにつれて, それぞれの手法の差が明確にあらわれています.
特に, QAが優位となるのはが1に近い領域となります.
論文では, (8)式の係数行列が, が1に近づくほど, スパースになることを示しています.
スパースな行列とは, 行列の要素に0が多い行列のことを言います.
先行研究では, 係数行列がスパースになるほど, D-Waveでの成功確率が高くなることがあると実験的に言われています[4].
これは, D-Waveのグラフ自体がスパースであるため, スパースな問題はD-Wave上に埋め込みやすいということが理由にあると思われます.
結言
今回は, 交通道路のフローを良くするために, 信号の割当とそれによる車の量の変化を定式化し,
それを用いて信号を待つ車の量を均等にするような最適化問題を作成しD-Waveを用いて解いた論文を紹介しました.
交通系の最適化問題は, 問題の構造から量子アニーリングと相性が良さそうです.
しかしながら, 何を最適化すれば良いかなどモデル化の仕方がとても工夫が必要なようにも思えます.
今回の論文では, 交通道路のフローに関係するであろう, 「信号で待っている車の量」を信号機の割当と関連付けて上手くモデル化出来ており感服です.
弊社でも, 今回紹介した論文とは異なるアプローチを用いて, 量子アニーリングを用いた交通最適化を研究開発しています.
pc.watch.impress.co.jp
参考文献
- [1] 物理のいらない量子アニーリング入門
- [2] Traffic Signal Optimization on a Square Lattice using the D-Wave Quantum Annealer, Daisuke Inoue et al, 2020
- [3] TChaotic Ising-like dynamics in traffic signals, Hideyuki Suzuki et al, 2012
- [4] Experimental Investigation of Performance Differences Between Coherent Ising Machines and Quantum Annealer, Harmerly, R. et al, 2019
文責
篠原 秀人、株式会社 Jij
Hideto Shinohara, Jij Inc.
※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。