量子アニーリングを用いた信号制御の最適化

この記事の概要

前回の記事に続いて, 今回も量子アニーリングを用いた交通最適化の論文を紹介します.
前回はこちら
jijtech.hatenablog.com

信号制御による交通最適化の目標は一貫して, 車の流れを良くすることです.
今回の論文でも, 最終的な目標は車の流れを良くすることになります.

この目標に対して, 今回の論文では交通量の多い道路の車が優先的に交差点を通れるようなモデルを作るアプローチを取っています.

そして, 最適化計算とシミュレーションの両方行い, 逐次的に一連の時間の信号制御を求めています.
結果（得られた解）の良し悪しもシミュレーション上で評価を行います.

本記事の具体的な説明の流れは以下のようになります.

1. 問題設定の説明：どういう交差点の状況を考えるのか
2. 具体的な目的の説明：車のフローを良くするために, 具体的にどのような評価指標を採用するのか
3. モデル化：1,2を数式で表すとどうなるか
4. 実験：3のモデルを用いて具体的な数値実験を行う
5. 結論

この記事の概要
今回紹介する論文
問題設定
モデル化
シミュレーション
実験
- 解の評価
- 結果
結言
参考文献
文責

今回紹介する論文

今回紹介する論文がこちらになります.
Optimal Control of Traffic Signals using Quantum Annealing.

問題設定

今回考える問題設定を説明します.

今回の問題は, ある時刻において, 与えられた交差点において信号のパターンを決定することによって車の流れを良くすることが目的です.

これに対しまず, 与えられる道路はどういうものかとそれに対し何を決定するのかについて説明します.

そして, 車のフローを良くするために, どういう評価指標を用いるのか（目的関数）について説明します.

考える道路状況

考える道路の状況は, 以下の図のような格子状の交差点の集合とします（[1]より引用）.

f:id:Jijinc_Shinohara:20200707174518p:plain — Fig1:格子状の交差点

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

車の振る舞い

今回車は, 直進 or 右折するとします（左折は考えません）.

信号機のパラメーター

今回は信号機の割当にただ単に青 or 赤だけでなく, 左折信号なども含めます（下図に例）.
f:id:Jijinc_Shinohara:20200708161111p:plain

１つの信号機に対して, 割当てる信号のパラメーターは以下の6つがあるとします.
f:id:Jijinc_Shinohara:20200707175132p:plain

論文ではこれをモードと呼んでいます.

以上より今回は, それぞれの時刻のそれぞれの交差点で, 信号機にどのモードを割当てるか, を決定します.

目的

大きな目標は, 道路の車の流れを良くする（最大化）することです.
この車の流れを良くするために, この論文では以下のアプローチを取っています.

1. 一番交通量の多い道路の車が優先的に交差点を進めるようにモードを決定する.
2. 車が通る連続した交差点において, 連続的に車が通れるようにする.

1は混雑している道路を解消し, 交通の流れを良くする意味合いがありそうです.
2の着想は, 赤信号で止まっていた車が, 青信号に変わり出発した後に通る次の交差点で, 再び赤信号で止まることの無いように,
というところから来ています.

道路の交通状況は時間と共に常に変化するので, 目的1&2ともに, 時間とともに変化します.
今回の論文では, 時間に対してある程度の時間間隔を含みながら, 逐次的に解を求めていきます.

モデル化

上で述べた問題を、数式でモデル化していきます.

変数定義

まずは, 変数の定義を行います.
決定することは, それぞれの交差点の信号に対して, 6つのどのモードを割当てです.

よって, 以下の0-1の決定変数を用います.
$\displaystyle{ x_{ij} = \begin{cases} +1 & (交差点iにモードjを割当てるとき) \\ 0 & (otherwise) \end{cases} \tag{1} }$

目的1

式(1)を用いれば, 目的1「交通量の多い道路の車を優先的に流す」は以下のようにかくことができます.

$\displaystyle{ Q_1 = -\lambda_1 \sum^n_{i=1} \sum^6_{j=1} C_{ij} x_{ij} \tag{2} }$

ここで, $\lambda_1$ は後述する目的2との重みを調節するパラメーター, $n$ は考える交差点の数, $C_{ij}$ は交差点 $i$ にモード $j$ を割当てることによって減らせる車の量の最大値です.
すなわち, $C_{ij}$ は $x_{ij} = 1$ としたときに, 何台の車が交差点を通過することができるかの量になります.

$Q_1$ は, 交差点を通過する車の量が多くなればなるほど, 小さい値を取ることになります.
よって, $Q_1$ を最小となるような $x_{ij}$ を求めることによって, 目的1を達成することができます.

$C_{ij}$ の計算方法

$C_{ij}$ の計算方法を説明します.
そのため, 交差点 $i$ に接続する道路の交通量を以下のように定義します.
f:id:Jijinc_Shinohara:20200708113332p:plain

$\displaystyle{ a_i^k : 交差点iに接続するポジションkの道路で止まっている車の量 }$

車は, 直進したり右折したりします.
なので直進する割合を以下の図のように $f$ とします.
f:id:Jijinc_Shinohara:20200708113500p:plain

$\displaystyle{ f_i^k : 交差点iに接続するポジションkで直進する車の割合 }$

今定義した2つの量より, $C_{ij}$ を計算することができます.
具体的に以下のようになります.
$\displaystyle{ C_{i1} = f_i^1 a_i^1 + f_i^2 a_i^2 \tag{3} }$
$\displaystyle{ C_{i2} = a_i^2 \tag{4} }$
$\displaystyle{ C_{i3} = a_i^1 \tag{5} }$
$\displaystyle{ C_{i4} = f_i^3 a_i^3 + f_i^4 a_i^4 \tag{6} }$
$\displaystyle{ C_{i5} = a_i^4 \tag{7} }$
$\displaystyle{ C_{i6} = a_i^3 \tag{8} }$

$a,f$ は問題においては, 与えられるパラメーターとなります.
実際には, $f$ はシミューレーションを用いて逐次測定を行います.

そこから $C_{ij}$ を計算することになります.

目的2

目的2「車が通る連続した交差点において, 連続的に車が交差点を通れるようにする」を式でかくと以下のようになります.

$\displaystyle{ Q_2 = -\lambda_2 \sum^n_{i=1} \sum^6_{j=1} C_{ij} x_{ij} [ \tau_{i,a'} \lambda_3 C_{a',a} x_{a',a} + \tau_{i, b'} \lambda_3 ' C_{b',b} x_{b',b} + \tau_{i,c} \lambda_3 C_{c',c} x_{c',c} + \tau_{i, d'} \lambda_3' C_{d',d} x_{d',d} ] \tag{9} }$

少し長くてわかりずらいので抜き出して考えてみます.
$\displaystyle{ -\lambda_2 \sum^n_{i=1} \sum^6_{j=1} C_{ij} x_{ij} [ \tau_{i,a'} \lambda_3 C_{a',a} x_{a',a} ] \tag{10} }$

ここで, 交差点 $i$ にモード $j$ が割り当てられて, それに伴い交差点 $i$ を通過した車について考えてみます.
f:id:Jijinc_Shinohara:20200708105619p:plain

この車が次に差し掛かる交差点を $a'$ とします.

式(10)は, これらの車が交差点 $a'$ で止まることなる, 連続して通過できるようなモード $a$ を選べば,
それによって移動できる車の台数 $C_{a`,a}$ に応じたコストが減少するような構成になっています.

もちろん, 交差点 $i$ から $a'$ に着くまでに時間がかかるので,
その時間に関する0-1のパラメーターが $\tau_{i,a`}$ です.

ある交差点に隣接する交差点は4つ存在するので, (9)式は4つの項からなっています.

交差点 $i$ でのモードの決定によって移動した車が, 次にどの交差点に着くか,
また, その交差点でどのモードを割り当てればコストが下がるのかを表したのが次の図です.
f:id:Jijinc_Shinohara:20200708110327p:plain

もちろん, 全ての車が連続して交差点を通過することは不可能なので,
連続して通過できる車の台数に応じてコストが減少するように, $C_{ij}, C_{a'a}$ が係数にかかっています.

$\lambda_3', \lambda_3$ はそれぞれ右折する車 or 直進する車, どちらに重点を置くかのパラメーターです.

時間に関するパラメーター $\tau$

今回, 連続した信号機では, なるべく連続して通れるように信号機のモードを割り当てたいわけですが,
連続する交差点を同期させるのは, そこには時間差が必要です.

その時間に関するパラメーターが $\tau_{i,i'}$ です（前述）.

今所与の値として, 以下のモノがわかっているとします.

交差点の道路の長さ
交差点間を走行する車の平均速度

するとこの２つから, 車の交差点間の走行にかかる平均的な時間がわかります.
それを $\Delta t_{ii'}$ とします.

また現在の時刻を $t$ としたときに, そこから $\Delta t_{i,i'}$ 時間たったときのみ, $\tau_{i,i'}$ が1となるように設定します.

数式でかくと,
$\displaystyle{ \tau_{i,i'} = \begin{cases} +1 & (t mod \Delta t_{i,i'} \sim 0) \\ 0 & (otherwise) \end{cases} \tag{11} }$

もし, $t < \Delta t_{i,i'}$ ならば, 以下のようにします.
$\displaystyle{ \tau_{i,i'} = \begin{cases} +1 & (\Delta t_{i,i'} - t \sim 0) \\ 0 & (otherwise) \end{cases} \tag{12} }$

これによって, ある車が差し掛かっている現在の交差点と, 次に差し掛かる交差点の信号の同期は, 交差点間を横断してからになります.

制約条件

今回の制約条件は, それぞれの交差点で割り当てられるモードはちょうど１つです.
なので, 制約式は以下のようになります.

$\displaystyle{ Q_3 = \lambda_4 \sum_{i=1}^n \{ 1 - \sum_{j=1}^6 x_{ij} \}^2 \tag{13} }$

問題のハミルトニアン

これらを踏まえると, 今回の問題のハミルトニアンは以下のようになります.

$\displaystyle{ H = Q_1 + Q_2 +Q_3 \\ = -\lambda_1 \sum_i, \sum_j C_{ij} x_{ij} - \lambda_2 \sum_{i} \sum_j C_{ij} x_{ij} [ \tau_{i,a'} \lambda_3 C_{a',a} x_{a',a} + \tau_{i, b'} \lambda_3 ' C_{b',b} x_{b',b} + \tau_{i,c} \lambda_3 C_{c',c} x_{c',c} + \tau_{i, d'} \lambda_3' C_{d',d} x_{d',d} ] +\lambda_4 \sum_{i} \{ 1 - \sum_{j} x_{ij} \}^2 \tag{14} }$

シミュレーション

今回の論文では, シミュレーションと最適化問題を交互に行います.
まず, 初期状態で最適化問題 $Q_1 + Q_2$ を解きます.

それを元に信号機の色を配置し, シミュレーション上で車を動かします.

そのシミュレーションの結果を元に, 次の最適化問題で用いるパラメーターを計算します（ $C_{ij}, \tau_{ii'}$ など).
車の混雑度などから, 交差点間の移動にかかる平均時間 $\Delta t_{ii'}$ を求め, 最適化問題を解く時間間隔 $t$ を元に同期させる信号を選びます（ $\tau_{ii'}$ の決定）.

そしてそれを元に次から全体の最適化問題である(14)式を解きます.

これを所定の回数繰り返します.

実験

以下の問題設定で, 実験を行ってみます.

交差点の数 : 6×6 = 36
車の台数 : 4320
道路の制限速度 : 11, 17, 22, 28（ランダムに割当てる）
道路の長さ : 1km
$f_i^k$ = 0.7
1回のシミュレーションで動かす時間 : 150s
$\lambda_1 = 1, \lambda_2 = 60, \lambda_3' = 0.7, \lambda_3 = 0.3, \lambda_4 = 60$
5秒ごとに最適化問題を解く.