@yuichirominato 2018.12.22更新 183views

【自動車】量子コンピュータ(アニーラ)で車間距離最適化

QAOA QUBO 量子アニーリング 量子コンピュータ

はじめに

前回自動車の軌跡の最適化をイジングを使って行ってみました。時系列のデータはQUBOmatrixを使うことで木構造で実装ができました。

Optimal Douglas–Peucker Algorithm | 量子コンピュータによる自動運転のための自動車軌跡データ最適化
https://blog.mdrft.com/post/335

しばらく自動車関連データで量子コンピュータがどのように使えるかどうかを実際に使えるアルゴリズムとしていくつか実装を進めてみて自動車における量子コンピュータの活用を探ってみたいと思います。

今回は自動車の車間距離を最適化してみます。よく動画とかで渋滞などで非効率な自動車の走行を見かけて、動いたり止まったりを繰り返していたら燃費が悪くなりそうだなと思った単純なきっかけです。車間距離を最適化してスムーズな交通を心がけることで無駄な操作が減って事故も減り、燃費も良くなるのではと考えました。

1車線の車列をイジングで作ってみる

今回モデルはものすごくシンプルなものを採用しました。ある一定区間の最適化をします。右から自動車がきて、左へ抜けていきます。道路の区間を一定間隔でイジング対応させます。下の図の白いところが道路で、黒いのが自動車があるところです。

これを最適化してみます。色の黒いところが自動車のあるエリアで、q3とq4は車間距離が十分でないようです。逆にq1,q2やq5,q6などは空いてますので、混雑をこういうところに分散させられれば良さそうです。

実際にQUBOでこの問題を解いてみます。まずは制約条件です。各自動車は前に進むかその場で止まるかを考えてみます。その際にそれぞれの量子ビットの取りうるマス目は、各自動車について下記のような可能性があります。q0はその場に止まるか、q1へすすむ。q3はq3に止まるかq4にすすむ。q4はq4にとどまるか、q5へ進む。q7はその場に止まるか、q8に進むです。図示してみると、

薄いオレンジ色の部分がそれぞれの自動車の進みうる選択肢になります。区間内で自動車が進行しうるマス目の制約条件と、今回の区間内の自動車の数が変わらないという制約条件から、制約条件のコスト関数は、

E1 = (q0+q1-1)**2+(q3+q4-1)**2+(q4+q5-1)**2+(q7+q8-1)**2

E2 = (q0+q1+q2+q3+q4+q5+q6+q7+q8+q9-4)**2

こちらをちょっとWildqatにいれてみます。


from wildqat import *
a = opt()
a1 = np.array([
[-1,2,0,0,0,0,0,0,0,0],
[0,-1,0,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0,0],
[0,0,0,-1,2,0,0,0,0,0], 
[0,0,0,0,-2,2,0,0,0,0],
[0,0,0,0,0,-1,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,-1,2,0],
[0,0,0,0,0,0,0,0,-1,0],
[0,0,0,0,0,0,0,0,0,1]])

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

a.qubo = a1+a2
a.sa()

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

こちらは下記のようになります。

区間内の自動車の数を変えずに自動車の進行方向に関して提案ができました、見た目車間距離も解消されているように見えます。さまざまな制約条件を区分けていけばもちょい色々できそう。

サイズを大きくしたい場合には、a1は要素に合わせて多少変えて、a2は全体の区間内の車列に合わせてJijが大きく変わります。

このようにちょっとした問題でもイジングに直してみることでどうのように社会問題の中で最適化を入れればいいのかという練習になります。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方