@yuichirominato 2018.12.18更新 704views

Optimal Douglas–Peucker Algorithm | 量子コンピュータによる自動運転のための自動車軌跡データ最適化

QUBO イジング 自動運転 量子アニーリング 量子コンピュータ

はじめに

イジングマシンや量子アニーラは実用段階に入っており、かつ社会問題の適用が課題となっています。社会問題の発展のために少しずつアルゴリズムを考えて出していこうと思います。今回は来るべき自動運転の時代に向けて自動車の軌跡データを最適化するアルゴリズムを作ってみたので紹介します。これを利用することで、自動車の軌跡をはじめとして様々なビッグデータへの最適化問題の適用が考えられ、イジングマシンの使い道がとても広がるものと思います。

自動車の軌跡データを最適化する重要性について

来るべき自動運転時代に向けて1つ重要な技術としてコネクティッドカーがあります。コネクティッドカーはインターネットへの常時接続機能を有し、データの格納と分析を通じて交通や自動車の動きを最適化し、様々なサービスの幅を広げることができます。自動車は移動体ですから、その走行データをインターネットを通じて保存する必要が出てきます。この走行データは位置データだけでなく、速度・加速度をはじめとしてさまざまな車内制御用のCANデータなどを含みます。

データ量は単体の自動車で月間データで数GBにものぼります。これらの膨大な走行データをさらにすべての自動車において保存するのはとても困難がつきまといます。また、データを保存するだけでなくリアルタイムに近い形で処理をした上でそれを利用者に対してサービスの形で返す必要があります。このように自動車のデータ処理を適切な形で行うことはサーバー運用上のコストやサービス提供の利便性の加点からとても重要です。

今回は特に走行データをコネクティッドカーがインターネットを通じてサーバーに保存し、その履歴からサービスを最適化するという観点に基づいて走行データを量子アニーラや量子コンピュータを利用してどのように最適化していけば良いかという参考になればと思います。

提案するOptimal Douglas–Peucker Algorithmについて

自動車の走行データを最適化するアルゴリズムとして今回はDouglas-Peuckerアルゴリズムを使います。こちらは有名な軌跡の最適化アルゴリズムです。

参考:Ramer–Douglas–Peucker algorithm
wikipedia:https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

始点と終点を最初に結び、そこから少しずつ閾値以下に設定された近似点を選んで計算を進めていきます。最終的に無理なく近似された点を結んだ軌跡が間引きされてとりだされます。今回は古典アルゴリズムのRamer–Douglas–Peucker algorithmからOptimal Douglas–Peucker Algorithmを提案します。

使用するツール

今回は弊社の提供している無料のツールWildqatとBlueqatを利用し実行してみます。もちろん工夫すればD-Waveにものりますが、今回は提案段階なので実機実装は次回やってみます。

量子コンピュータSDK / Blueqat
https://github.com/mdrft/Blueqat

量子アニーラ向けQUBOSDK / Wildqat
https://github.com/mdrft/Wildqat

上記は異なるマシン向けのツールですが、今回は量子コンピュータ・量子アニーラ両方においてソリューションを提供したいと思います。

アルゴリズムとイジングモデル接続数

量子コンピュータや量子アニーラで最適化を行う際に、特にD-Waveマシンなどはキメラグラフという特殊な結合方法を持っています。イジングモデルと呼ばれる物理モデルを利用して計算をする場合、キメラグラフなどは1量子ビットに対しての接続数が限られており、それらの接続数を効率的に利用するには、空間的・時間的な特性を理解した上でアルゴリズムを作る必要があります。

参考:http://blog.mdrft.com/post/6

今回提案するOptimal Douglas-Peuckerアルゴリズムはこの空間特性、時間特性をうまくキメラグラフや限られた接続数に実装するための工夫がされています。また、量子アニーラや量子コンピュータで社会問題を実装する際には、既存計算機での前処理も必要となります。今回は簡単な前処理を挟みながら連続的に計算を進めたいと思います。

現在出回っているマシンには接続数が多い全結合などのマシンもあります。そのようなマシンでは今回のアルゴリズムの大枠は変わりませんが、より広い空間接続、より長い時間での最適化計算を行うことができ、効率化を行うことができます。

Optimal Douglas–Peucker Algorithmの全体概要

このアルゴリズムを構築するには、まず自動車の時系列の位置情報を取得していきます。今回はあるモデルの道路を走る自動車を想定して例を挙げて考えてみます。下記のような道路を進行することを想定します。

次に自動車の走行軌跡を時間ごとに分割してみます。時系列での分割なのでカーブが多かったりする部分では走行距離はそこまで稼げないかもしれません。

実際に走行軌跡から得られた軌跡は道路へのGPSのマップのマッチングや各種調整が必要となります。ここでは、この得られた点をどれくらい間引きできるのかを考えてみます。現在の例では、点の数は6つあります。

全体のフロー

現在6つある点に対してすべてを結合してみます。全体の古典計算機(量子計算機との比較で既存計算機をこう呼ぶ)と量子アニーラの処理に関してのフローは、

1、点同士をつなぐ直線から点までの距離eを求める(古典計算機)
2、一定閾値以上の距離eの直線を残し、それ以外は除外する(古典計算機)
3、残された直線の数がもっとも少なくなり、かつ始点と終点を結ぶ組み合わせを計算する(量子計算機)
4、出てきた組み合わせが答えになる。

1、点同士をつなぐ直線から点までの距離eを求める(古典計算機)

まずは点同士をつなぎ、各直線から点までの距離を求めます。下記のようになります。

2、一定閾値以上の距離eの直線を残し、それ以外は除外する(古典計算機)

求めた距離において閾値以上のものを除外します。今回は閾値を適当に決めて下記のようになりました。

3、残された直線の数がもっとも少なくなり、かつ始点と終点を結ぶ組み合わせを計算する(量子計算機)

そして残された直線からもっとも選ぶ直線の数が小さくなるように組合せ最適化問題を量子アニーラで解いてみます。このような組合せ最適化問題は直線を選ぶエッジベースか分割点を選ぶノードベースかになりますが、今回はノードベースで解いてみます。使用する点をAからFまで名前をつけます。


次に回る順番を列に、頂点を行にして行列を作ります。今回はした三角行列でつくり、それぞれに量子ビットをあてがいます。必要な量子ビット数はN(N-1)/2+1です。今回はN=6なので、全部で16量子ビット使います。今回は色々都合で削っていって11量子ビットでやります。

上記で閾値を設定して選択された直線が残りました。列は0から5番目までに選択される量子ビットの順番、AからFまでは量子ビットの名前で、量子ビットは通るノードとその順番に対応しています。例えば、q7はEという量子ビットを3番目に採用するという意味です。

次にこれをQUBOmatrixになおします。制約条件は、1つの順番には1量子ビットだけ選ばれる、1つのノードは1回だけ通るです。また、今回のコスト関数は採用される量子ビットの数です。上記の量子ビットは事前に直線と点の距離を計算してありますので、通れないパスは除外されています。今回は通れるパスのみを残して、少ない手順でFまで行ければ圧縮率が高まります。

早速計算してみます。最初に接続されているノード同士の接続を取ります。QUBOmatrixは下記の通りです。

次に制約条件を考えます。制約条件は1つの順位に出現するノードは1つ。1つのノードは1回しか出現しないです。行と列にそれぞれ制約をつけます。まずは行方向に制約をつけました。

次に列方向に制約ですが、いちばん下の行が変則的な制約条件になるので、q9-q11あたりが変則的なQUBOmatrixになります。

最後にコスト関数で少ないノード数の方が選ばれるようにします。出来上がったQUBOmatrix同士をハイパーパラメータで接続し、コスト関数としてアニーリングにかけます。


from wildqat import *
a = opt()

a1 = np.array([ 
[0,-1,-1,0,0,0,0,0,0,0,0,0], 
[0,0,0,-1,-1,-1,0,0,0,0,0,0], 
[0,0,0,0,-1,-1,0,0,0,0,0,0], 
[0,0,0,0,0,0,-1,-1,-1,0,0,0], 
[0,0,0,0,0,0,0,-1,-1,0,0,0], 
[0,0,0,0,0,0,0,0,-1,0,0,0], 
[0,0,0,0,0,0,0,0,0,-1,-1,0], 
[0,0,0,0,0,0,0,0,0,0,-1,0], 
[0,0,0,0,0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,0,0,0,0,-1], 
[0,0,0,0,0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,0,0,0,0,0]]) 

a2 = np.array([
[-1,0,0,0,0,0,0,0,0,0,0,0],
[0,-1,0,0,0,0,0,0,0,0,0,0],
[0,0,-1,2,0,0,0,0,0,0,0,0],
[0,0,0,-1,0,0,0,0,0,0,0,0],
[0,0,0,0,-1,0,2,0,0,0,0,0],
[0,0,0,0,0,-1,0,2,0,2,0,0],
[0,0,0,0,0,0,-1,0,0,0,0,0],
[0,0,0,0,0,0,0,-1,0,2,0,0],
[0,0,0,0,0,0,0,0,-1,0,2,2],
[0,0,0,0,0,0,0,0,0,-1,0,0],
[0,0,0,0,0,0,0,0,0,0,-1,2],
[0,0,0,0,0,0,0,0,0,0,0,-1]])

a3 = np.array([
[-1,0,0,0,0,0,0,0,0,0,0,0],
[0,-1,2,0,0,0,0,0,0,0,0,0],
[0,0,-1,0,0,0,0,0,0,0,0,0],
[0,0,0,-1,2,2,0,0,0,0,0,0],
[0,0,0,0,-1,2,0,0,0,0,0,0],
[0,0,0,0,0,-1,0,0,0,0,0,0],
[0,0,0,0,0,0,-1,2,2,0,0,0],
[0,0,0,0,0,0,0,-1,2,0,0,0],
[0,0,0,0,0,0,0,0,-1,0,0,0],
[0,0,0,0,0,0,0,0,0,0,2,0],
[0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0]])

a4 = diag([1,1,1,1,1,1,1,1,1,1,1,1])

a.qubo = ここに係数*a1+a2+a3+ここに係数*a4
a.sa()

#array([1., 1., 0., 0., 0., 1., 0., 0., 1., 0., 0., 0.])

答えは、q0,q1,q5,q8が選ばれました。これはグラフでは下記のようなパスになっています。

今回は説明のために少し恣意的な選択になりましたが、こちらのアルゴリズムを使うことで、少ないノードで始点と終点を繋ぐ最短の経路ができました。

こちらのアルゴリズムは接続数を調整しながら結合数の許す限り拡張して調整することができますので、応用は楽だと思います。6頂点を合理的に4頂点に減らすことができ、データ量を4/6=0.67で約33%の節約です。今回のアルゴリズムは常に最大の圧縮率を選ぶので、便利だと思います。

ゲートモデルでも計算してみる

WildqatのデータをBlueqatに自動変換すると量子ゲートモデルでもイジング問題が解けます。アルゴリズムはQAOA+VQEというものを使います。


from wildqat import *
from blueqat import vqe

qubo = a.qubo
step = 8 
result = vqe.Vqe(vqe.QaoaAnsatz(qubo,step)).run() 
print(result.most_common(5))                                                                                                                                                  


#=>(((1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0), 0.08664815124265286), ((1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0), 0.04122331490845978), ((1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0), 0.03741982333002039), ((1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0), 0.0292301775045698), ((1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0), 0.02554785814976286))

今回はステップ数は多めの8にしました。そして計算してしばらく待ったのち、出た答えは、0>2>5>8とか、0>1>5>8など最短をとるものがでてきました。量子ゲートでも計算ができています。

時系列と接続数を考える

つぎにアルゴリズムの展開を考えるために空間的、時系列的な考察をしてみます。今回のOptimal Douglas–Peucker Algorithmはイジングモデルで実装を行いました。これは接続数が限られている状態でも活用できるように、空間的、時系列的な自動車の軌跡を効率的に考えて実装されている。自動車の軌跡のポイントは空間的に断続的でかつ、近いところから少しずつ軌跡ができて遠くの方の軌跡に繋がっていきます。

たとえば高速道路のようなカーブが緩やかで速度が一定の道路では、この間引きが起きやすくなると思われます。変化が少なく、すべての経路が閾値以下になりやすいです。また、カーブの多いところでは、閾値を越えることが多く、間引き率が少なくなります。

また、時系列で考えた際に、時系列と空間的な対応が対応しており、軌跡の繋がり方は空間的に時系列的に対応しています。このように空間と時間の制限のある社会モデルでは、接続数の限られたイジングマシンで実装が容易になるということがわかりそうです。

時系列で実装を考える

次に時系列で実装を考えてみます。自動車が少しずつ進みながら軌跡を描くときにどのように計算が行われるかを確認してみます。まず自動車が始点にいます。

1つ、2つ進むと接続ができます。3つ進むと接続がさらに増えます。

4つくらい進むと5つの点で接続ができます。それぞれ進んだステップに対して接続した直線と点との距離が求まります。このように時系列で少しずつ計算を進めていくことで計算量を調整しながら計算ができます。

また、接続数に関しても最大で点の接続数を調整することで、量子計算機の計算量を調整することができます。接続数が少ないときには時系列で採用する点の数を最大接続数に応じて調整ができます。

多数の自動車におけるアルゴリズム

古典的なアルゴリズムとの違いは組合せ最適化問題に落とし込むことで間引きの組み合わせを実現できます。従来アルゴリズムでは始点から終点までをつないで逐一処理で行うために複数の間引きのパターンを組み合わせるなどは考えられていませんので、より圧縮率の高いデータ圧縮の組み合わせを探索できます。

また、複数の多数の自動車の軌跡を同時に最適化することで、多くのデータを圧縮し、節約することができます。1台に限ったアルゴリズムではないので、多々圧縮してしまいましょう。

閾値について

閾値の設定は任意です。行いたいデータ圧縮量に応じてなど、調整をする感じになりますが、こちらのパラメータを取り除いたNon Parametric Optimal Douglas–Peucker Algorithmを考えてみたいと思います。こちらは今後の展開としたいと思います。

まとめ

今回は自動車の走行軌跡のデータを圧縮するためにDouglas-PeukerアルゴリズムをベースにOptimal Douglas-Peukerを作ってみました。イジングモデルの新しい利用方法は多数あります。身の回りのアルゴリズムをイジングに落としてみましょう。

Recommended


Wikiへ移動