Jij Tech Blog

Jij inc.の開発日記です

D-Waveを用いた正方格子状の交差点群における信号制御最適化

この記事の概要

いくつかの交差点の集合における車の流れを良くすることが最終的な目標です.
これに対し, 信号機に割り当てられた信号パターンと, それによる車の量の関係性を元に最適化問題に定式化します.

そして, その最適化問題量子アニーリング(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]より引用).

f:id:Jijinc_Shinohara:20200707121142p:plain
図1:考える交差点の状況

すなわち, ある交差点は4つの交差点と繋がっており, 格子上に交差点(信号機)が存在します.

車の振る舞い

今回車の振る舞いは, 交差点で 直進 or 左折 or 右折 するとします(図1 (b) ).

このとき, 車が直進する割合を,  aとします.
そして, 左右に曲がる割合は等しく, それぞれ  (1-a)/2とします.

これにより, ある道路に存在する車の量は, 水平 or 垂直方向の信号機の色によって異なり, それぞれ図1(b)の左と右のようになります.

信号機のパラメーター(決定するもの)

今回決定する信号機のパラーメーターは, ある時刻における信号機の色とします.
もう少し具体的に説明すると, ある時刻において信号機の垂直方向を青にするか(図1bの左) or 水平方向を青にするかを決定します.

交差点 iの信号機の青赤のパラメーターを \sigma_iとし,
 \sigma_i = + 1のとき, 垂直方向の信号機が青,  \sigma_i = - 1のとき, 水平方向の信号機が青 が割当られているとします.

今回この垂直方向を青にするか or 水平方向を青にするかを決定します.


 \displaystyle{
\sigma_i = \begin{cases}
    +1 & (垂直方向の信号機が青) \\
    -1 & (水平方向の信号機が青)
  \end{cases}
}

目的

今回の最終的な目標は, 考える交差点の集まりにおいて, 車の流れを良くすることです.

この目標の達成に対し具体的には, 交差点で待っている車の量を均一にすることを目標とします.
ある交差点に接している道路のうち, 待っている車の方が多い方向の信号機を青に割り当てます.

すなわち, 交差点 iにおいて, 垂直方向の道路の車量が, 垂直方向の道路の車量よりも多い場合,  \sigma_i = +1を割当, 垂直方向の道路の車の量を減らします.
逆も同様です.

このように, 道路に存在する車の量を均等に保つことによって, 道路全体の流れを良くすることを目指します.

もちろん, ある時刻ある道路における車の量は, 前の時刻の隣接する交差点の信号の割当によって変化します.
なので, 次の節ではそれらを定式化し, 具体的な数式モデルを作っていきます.

モデル化

ここでは, 実際に今回の問題を数式にモデル化していきます.
ある時刻における信号機の割当 \sigmaと車の進行方向の割合 aを元に,
次の時刻における道路の車の量を表します.

そしてある交差点に隣接する道路で待っている車の量を均等にするような信号機のパターン\sigmaを決定する最適化問題を構築していきます.

車の量q_{ij}, x_{i}

時刻tにおける交差点jから交差点iへの道路の車の量をq_{ij}(t) \neq q_{ji} )とします.
また, 時刻tでの, 交差点ijの信号機のパラメーターをそれぞれ\sigma_i (t), \sigma_j (t)とします.

すると, 時刻t+1での道路j \rightarrow iの車の量q_{ij}(t+1)は以下のようになります.
 \displaystyle{
q_{ij} (t+1) = q_{ij} + \frac{s_{ij}}{2} ( - \sigma_i (t) + \alpha \sigma_j (t)  )
\tag{1}
}

ここで, s_{ij}は道路の方向パラメーターで, 道路j \rightarrow iが垂直方向なら s_{ij} = +1, 道路j \rightarrow iが水平方向なら s_{ij} = -1です.
また, \alpha = 2a -1 です.
道路の方向で車量が変わるのは, 車の進行する割合が異なるためです.


次に, 交差点iで待つ車の量の平均値x_iq_{ij}を元に求めます.
このとき, 最終的に車の量を均一することを考えて, 垂直方向の量をプラス, 水平方向の量をマイナスで考えます.
 \displaystyle{
x_{i} (t) =  \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t)
\tag{2}
}
x_iが0に近いほどある交差点に接する道路の車の量は均一ということになります.
1つの方向に対して, 2つの道路から車が来るので,  ÷2 しています.

式(1), (2)より, 時刻t+1での交差点iに接する道路の車量x_i (t+1)は以下のようになります.
 \displaystyle{
x_{i} (t+1) =  \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} (t+1) \\
= \frac{1}{2} \sum_{j \in N(i)} s_{ij} \cdot q_{ij} + \frac{1}{2} ( - \sigma_i (t) + \alpha \sigma_j (t)  ) \\
= x_i (t) + \frac{1}{4} \sum_{j \in N(i)} ( - \sigma_i (t) + \alpha \sigma_j (t) )
\tag{3}
}

これで, 交差点での信号機の色と, 車の量の関係式ができました.
単純に考えると,  x_i (t+1) >0のときは, 垂直方向の車の量が多いので, 垂直方向を青にすれば良さそうです.
逆に x_i (t+1) <0なら, 水平方向を青に割り当てれば良さそうです.

これを全ての交差点に対して行列形式で書き直すと, 次のようになります.
 \displaystyle{
\boldsymbol{x} (t+1) = \boldsymbol{x} (t) + (- \boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A} ) \boldsymbol{\sigma} (t)
\tag{4}
}

目的関数

今回の目的は, ある交差点において水平方向と垂直方向で待っている車を均等にすることです.
すなわち,  \boldsymbol{x} (t+1) を0に近づけるような信号の割当\boldsymbol{\sigma} (t) を決定することです.

よって, 目的関数は以下のように設定すれば良さそうです.
 \displaystyle{
\min{ \boldsymbol{x} (t+1) ^T \boldsymbol{x} (t+1) }
\tag{5}
}

二乗の形にすることで, 0が最小値となります.

制約条件

変数やパラメータの定義のおかげで, 明確な制約条件は存在しません.
ただこの問題設定の上で困ることが一つあります.

それが, 信号の色がこまめに変わってしまうことです.
隣り合う異なる時刻で, 毎回信号が変わってしまうと車の流れを良くするという点であまり良くなさそうに思われます.

よって, 隣り合う時刻間で信号の色が変わるとペナルティーがかかるようにします.
以下の項を入れれば良さそうです.

 \displaystyle{
Penalty = \eta ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) ) ^T ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) )
\tag{6}
}
\etaは, 目的関数とペナルティーを調整する重みのパラメータです.

まとめ

まとめると, 今回の問題のハミルトニアン

 \displaystyle{
H = { \boldsymbol{x} (t+1) ^T \boldsymbol{x} (t+1) } +  \eta ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) ) ^T ( \boldsymbol{\sigma}(t) - \boldsymbol{\sigma}(t-1) )
\tag{7}
}

これを全て \boldsymbol{\sigma} (t) で書きくだすと,
 \displaystyle{
H(\boldsymbol{\sigma} (t) ) =  \boldsymbol{\sigma(t)} ^T J \boldsymbol{\sigma} (t) + h \boldsymbol{\sigma} (t) + c(t)
\tag{8}
}

 J, hは以下のようになります.  c(t)は定数項です.
 \displaystyle{
J = (-I + \frac{\alpha}{4} A) ^T (-I + \frac{\alpha}{4} A) + \eta I \\
h = 2x(t) ^T (-I + \frac{\alpha}{4} A) - 2\eta \sigma(t-1) ^T
\tag{9}
}

実験

50 × 50 の交差点に対して, 今回のモデルを用いて信号の割当を決定します.
今回は以下の3つの手法を比較します.

1. (3)式を計算して, x_i (t) \geq \thetaならば, \sigma_i (t)  = +1, x_i (t) \leq -\thetaならば, \sigma_i (t)  = -1 を割当てる, ルールベースの割当(以下局所探索)
2. (8)式を, D-WaveのライブラリのSimulated Annealingを用いて解く(以下SA).
3. (8)式を, D-Waveの量子アニーリング(Quantum Annealing)を用いて解く(以下QA).

実験方法

まず, t=0の初期状態として, 各交差点のx_i(0)を, [-5.0, 5.0]の間でランダムに決定します.
 \boldsymbol{\sigma} (0) も {-1,1}のどちらかをランダムに割り当てます.

その後, 次の時刻の信号の割当を上の3つの手法で求めます.
そして決定した信号の割当を元に,  \boldsymbol{x} (t)を式(3)より計算します.

これらを元に次の時刻の信号の割当を求める, \boldsymbol{x}を求める,.......
というのを繰り返します.

結果

パラメーターを,  \alpha = 0.8, \eta=1.0とし, 時刻t=0 \sim 200で実験を行った結果が以下の図2左aになります.

f:id:Jijinc_Shinohara:20200707154134p:plain
図2:結果

QAを用いた結果が, 一番良い値を一番多く出しており, QAの優位性がわかります.

また, \alpha(車が直進する割合に関する量)を変化させて実験を行った図が, 図2右bになります.
こちらは, 全ての時間に対してハミルトニアン(8式)の平均値で比較しています.

\alphaが0.7あたりから, ハッキリとSAよりもQAの方が良い結果を得られていることがわかります.
\alphaが1に近づくにつれて, QAでの結果がよくなる考察が本論文では考察されています.

考察

\alphaが1に近づくにつれて, それぞれの手法の差が明確にあらわれています.
特に, QAが優位となるのは\alphaが1に近い領域となります.

論文では, (8)式の係数行列 Jが, \alphaが1に近づくほど, スパースになることを示しています.
スパースな行列とは, 行列の要素に0が多い行列のことを言います.

先行研究では, 係数行列がスパースになるほど, D-Waveでの成功確率が高くなることがあると実験的に言われています[4].
これは, D-Waveのグラフ自体がスパースであるため, スパースな問題はD-Wave上に埋め込みやすいということが理由にあると思われます.

結言

今回は, 交通道路のフローを良くするために, 信号の割当とそれによる車の量の変化を定式化し,
それを用いて信号を待つ車の量を均等にするような最適化問題を作成しD-Waveを用いて解いた論文を紹介しました.

交通系最適化問題は, 問題の構造から量子アニーリングと相性が良さそうです.
しかしながら, 何を最適化すれば良いかなどモデル化の仕方がとても工夫が必要なようにも思えます.

今回の論文では, 交通道路のフローに関係するであろう, 「信号で待っている車の量」を信号機の割当と関連付けて上手くモデル化出来ており感服です.


弊社でも, 今回紹介した論文とは異なるアプローチを用いて, 量子アニーリングを用いた交通最適化を研究開発しています.
pc.watch.impress.co.jp

文責

篠原 秀人、株式会社 Jij
Hideto Shinohara, Jij Inc.


※ 疑問点や間違いなどございましたら、お気軽にブログ上でご質問ください。