車の流れから街全体の信号機の状態を最適化するのは可能か　量子アニーリングマシンにおける“適応的制御”の研究

自己紹介と豊田中央研究所の研究について

井上大輔氏（以下、井上）：株式会社豊田中央研究所の井上です。本日は「量子アニーリングマシンを用いた大規模都市での信号制御」の紹介をします。なお、この研究は、東京大学の合原先生らとの共同研究として実施したものになります。

はじめに弊社、豊田中央研究所について簡単に紹介します。豊田中研は1960年にトヨタグループの共同出資によって設立されました。現在の従業員数はおよそ900名で、うち8割が研究職として働いています。トヨタグループ各社にも研究部門は存在しますが、スライドの「理念」が示すとおり、弊社では対象を自動車に限らない、比較的ロングスパンの研究にも取り組んでいます。

本拠点は愛知県の長久手市ですが、最近、東京の飯田橋に新しいオフィスである東京キャンパスを設立し、外部連携の拠点としての役割を担い始めています。私自身もこちらに勤務しているので、興味のある方は遊びに来てください。

少しだけ弊社の代表的な研究について紹介します。例えば、QRコード、可視光応答型光触媒、あるいは人工光合成などが挙げられます。このうち、QRコードはデンソーの発明と考えている方が多いと思いますが、実はデンソーから弊社に受託研究の依頼があり、共同で実施したものです。

「量子アニーリングマシン」で注目している問題

本題に入ります。「量子アニーリングマシン」は、量子コンピューターの一足早い実用化として、カナダのD-Wave社から提供されている計算機環境です。メリットとしてしばしば謳われているのが、最適性と省エネ性です。例えばスパコンと比べて1億倍早く問題が解ける、1000分の1の消費電力で問題が解けるなどです。

もちろんこれらの研究は、ある程度量子アニーリングマシンに有利な状況で検証されたものなので、量子アニーリングマシンがすぐさま既存の計算環境にとって変わることはないと思っていますが、弊社でも高速性と省エネ性に着目した研究を進めているところです。

特に注目しているのが、我々が“逐次的最適化”と呼んでいる問題です。これは、最適化を行った結果、システムの状態がある程度変化して、その変化したシステムに対してもう一度最適化を行うという、サイクルを繰り返すような最適化問題のことです。繰り返し解くことになるので、高速性や省エネ性が特に重要になると考え、我々の研究チームではこちらの対象の研究を進めています。

これまで複数のテーマについて研究してきましたが、本日はスライドの一番下の交通量制御についてのみ紹介します。信号を用いて都市全体の交通量を制御しようという内容です。

信号の研究のねらい

信号の研究のねらいについて述べます。従来の「古典的な信号機」と呼ばれる信号機は、その状態が時間で管理されていました。例えば、1分経ったら青の表示を赤に切り替える、という具合です。これは計算量がごく小さく済みますが、何らかの意味で「系」の状態を最適化しているとは思いづらい手法です。

これに対して近年導入されているのが“適応的制御”と呼ばれるもので、これは信号機の周辺状況を観測し、それをフィードバックして何らかの意味で最適化を行う手法です。

（スライドを指して）例えば、交差点に設置されている信号機の状態を考えると、左右に流れている車の数がある程度滞ってきたら、そちらを流すように信号の状態を切り替える、というイメージです。古典的な信号機に比べると、系の状態をフィードバックしているという意味では何らかの最適性が保証できると思えますが、交差点同士は全く連携していないので、街全体の最適性を担保するには不十分だと言えます。

我々が目指しているのはまさにその点で、街全体の車の流れの情報から、街全体の信号機の情報を決める制御が行えないかと考えています。これが実施できれば、もちろん系全体のグローバル最適を達成できますが、その場合、交差点の数が増えるにつれて、必要な計算量が指数的に大きくなってしまいます。したがって、既存のコンピューターではアプローチが難しい。そこで、量子アニーリングマシンのパワーを活かせないかと考えました。

本研究における3つの貢献

「本研究の貢献」としては、そのような具体的な手続きを構築した点です。具体的に1つ目は、信号機群の待機的な最適制御問題が、D-Waveをはじめとするイジングマシンが解けるかたちに変形できることを示しました。

2つ目は、実際にその操作を行った結果をD-Waveマシンによって制御させてみたところ、既存の局所的な適応制御よりも高性能であることを数値実験で示しました。

3つ目は、得られた信号制御の結果をどの程度定量的に分析できるか。例えば、ある信号がどの程度遠くの距離の信号と協調すべきかなどを解析できました。本日は、1つ目と2つ目を簡単に紹介します。

説明の都合上、数式が出てきますがご了承ください。（スライドを指して）今考えているのが、このように2次元の格子が東西南北に並ぶ道路網です。各道路上を走る車はそれぞれの交差点で、「一定確率a」で右折か左折するものとします。信号機がすべての交差点に設置されていますが、それらの信号は「状態σ」を用い、状態σが＋ならばその信号機は南北に車の進行を許可し、−1であれば東西に進行を許可するという具合に動いているとします。

このような問題で、すべての交差点に設置されてる信号の状態を何らかの意味で最適化しようとすると、例えば道路網が50×50であるとき、信号は22500通りの組み合わせになってしまい、最適化によってσ全体を決めることは困難であると予期されます。

このような最適化問題を実際に定式化するために、我々は車のダイナミクスと信号のよさを決める“評価関数”というものをモデル化しました。先ほど考えた格子状の都市と左右、右左折の確率が一定であるという仮定を用いて式変形を行うと、交差点iと交差点jの間に存在する車両台数qijの変数の時間発展が（スライドを指して）この式で表されることが示されます。

この式は、現在時刻の車両台数が、その付近の交差点の信号の状態σiとσjによって次の時刻にどう時間発展するかを表しています。ここでいうSijとは、その道路が縦か横かを表す定数です。

次に、交差点の交通状態の評価関数を用意します。Hがそれに当たりますが、このHは第1項目と第2項目に分けられ、1項目は車の流れの偏りを減らす効果、2項目は信号の頻繁な切り替えを防ぐ効果を持ちます。新しく登場したxという記号は、車の車両台数qijを重みづけ平均したもので、その交差点における流れの偏りの変数を表す値です。もしxが小さければ偏りは少なく、大きければ偏りは大きいので、これを小さくしたいというわけです。

詳細は割愛しますが、先ほどの動特性と流れの偏りの定義を評価関数に代入して、うまく変形すると、先ほど導入した評価関数が（スライドを指して）このようなかたちになることが示せます。

この式は変数であるσについて二次の項までを含んでいて、σ自体は＋1か－1の2値、そして制約を含まないため、“イジングモデル”と呼ばれるかたちになっています。これこそが、D-Waveマシンをはじめとするイジングマシンが唯一解ける最適化問題のクラスであり、これらのマシンと今回扱う交通流制御の問題の相性がよいことがわかりました。

（スライドを指して）今見せているのが、D-Waveマシンを用いて数値計算を行った結果です。手続きとしては、交通流モデルを1ステップ時間発展させたものを用いてD-Waveで最適化を行い、再び交通流モデルを時間発展させるというサイクルを繰り返す逐次的最適化です。

このアニメーションの各ドットは交差点のIDを表し、ドットが赤色であれば南北方向に進行を許可、青色であれば東西方向に進行を許可しています。隣接した信号同士が何かしら協調しながら制御を行っている様子が見てとれます。

ここで気になるのが、この手法の性能です。我々は既存の局所制御の典型的な手法として、交差点の流れの偏りがある閾値θを超えたら、信号の表示を逆転させるという局所制御を実施しました。（スライドを指して）その様子が左のアニメーションです。これを見ると、先ほどお見せした（右側にお見せしている）D-Waveを用いた制御とはやや様子が異なり、連携はできていないことがわかります。

肝心の評価関数の値をプロットしたのが真ん中の図で、こちらは評価関数Hを時間平均してプロットしたものです。下に行けば行くほどいいわけですが、局所制御と比べて待機制御の性能が10%近くよいことがわかりました。

イジングマシンは信号機群の最適制御問題と相性がよく、既存の適用制御以上の性能を示す

井上：本研究のまとめです。まず、D-Waveマシンをはじめとするイジングマシンが信号機群の最適制御問題と相性がいいことを、式変形によって示しました。次に実際にD-Waveマシンを用いて、そういった制御実験を行った結果、既存の適用制御よりもよい性能を示すことがわかりました。本日は割愛しましたが、先ほどの縞のようなものが、どういった意味合いを持つのかを定量的に解析しました。

（スライドを指して）詳しくはこれらの論文に書かれているので、興味のある方は読んでください。今回扱った系のフューチャーワークとして、より現実に近い交通流の制御ができるかについて考えるために、現在、東京大学の合原先生らと共同研究を行っているところです。また結果が出ましたら報告します。以上です。

質疑応答

司会者：質疑応答を行います。まずは「流れの偏りが大きいということは、周りの道よりも車が多いという認識でよろしいのですか」という質問です。

井上：今回用いている系に関してすごくナイーブな質問で、必ずしもそうではないけれども、少なくとも流れの偏りが大きいときはその可能性が大きい。完全に一致はしないけれど、相関するような現象になっています。

司会：次に「量子アニーリングでは全体最適を目指すように解の探索が行われるとのことですが、例えば信号の最適化において出力される結果の最適性は、どのように検証しますか」。

井上：これも非常に大事な質問です。そもそも今回量子アニーリングマシンに解かせている問題というのは、系の規模が大きくなってくると、誰にも最適性が保証できない。最適解を求めるのが難しい問題なので、複数の最適化手法で解いてみて、一番評価関数を小さくしたものが最もいいと結論づけるしかありません。

あえてそういったことにアプローチしようとすると、例えばより規模の小さい系でマシンを動かしてみると厳密解が求まるケースが多いので、それらのケースを考えて比べるということが考えられます。

司会：続いて「将来的には緊急車両の緊急度も組み込めますか」。

井上：まさに今、そういう系の捉える現象を現実に近づける努力を日々行っています。やはり、QUBO（Quadratic Unconstrained Binary Optimization）イジングモデルに落とし込むことが肝になるので、それ次第です。まだこちらの環境ではできていませんが、取り組むべき課題だと感じています。

司会：これで終了します。ありがとうございました。