4/15(火)~17(木) 第5回量子コンピューティングEXPO春(東京ビッグサイト)に共同出展します☆彡
量子アニーリング

New!! 量子アニーリング(QUBO)でプラレールを衝突回避させてみた①

AI要約

3台のプラレールが同一コースを走行する中、QUBOアニーリングを用いてポイント切り替えを制御し、衝突を回避するシミュレーションに挑戦。問題をQUBOで定式化し、ポイントの最適な切り替えを探索しました。

やること

前回、Pythonでプラレールのシミュレータを作りました。

これでいろいろな制御を試すことができそうです。このコースに3台の電車を走らせて、できるだけ衝突しないように量子アニーリング(QUBO)でポイント切り替えを制御してみましょう。コードは複雑になってしまうので割愛します。ご了承を。

TYTANについて

「TYTAN」はOSSの疑似量子アニーリングパッケージです。

GitHub - tytansdk/tytan: Python SDK for large QUBO problems
Python SDK for large QUBO problems. Contribute to tytansdk/tytan development by creating an account ...

チュートリアル教材はこちらの「第3世代基礎コースと認定試験問題」から。

GitHub - tytansdk/tytan_tutorial
Contribute to tytansdk/tytan_tutorial development by creating an account on GitHub.

オンライン講義のアーカイブはこちらから見れます。

discordコミュニティもあるので気軽に質問できます。

https://discord.gg/qT5etstPW8

定式化

いろいろな方法が考えられるとは思いますし、というかそもそも未来をシミュレーションしてかっちり制御すればなんてことない問題なのですが、わざわざQUBOで定式化して最適化してみようという取り組みをしているわけです。はい

まずポイント切り替えが2箇所あるので、直進(0)と曲がる(1)の全組み合わせで4通りを考えます。これを「パターン」と呼ぶことにします。

次に、各電車、各パターンで未来50フレームくらいまでシミュレーションをします。

マス目に書き込んでいるのはレール番号です。どのレールにいるかですね。

ここから定式化です。

量子ビットを「電車の数×パターン数」用意します。各電車はいずれかのパターンを必ず一つ採用することとします(ワンホット制約、強い条件)。

ある未来のフレームにおいて、同じレールを複数の世界線が踏んでいるとき、2つ以上の世界線が同時に実現しないようにペナルティをかけます(弱い条件)。上の図で言うと、5フレーム後にレール6を踏む世界線が6つあります。これらの世界線のうち2つ以上が同時に実現してはいけません。それは2台以上の電車が同じレールに乗っていることになるので。同時に実現して良いのは0個か1個だけです。0個でも大丈夫であることに注意。(参照:量子アニーリングのQUBOで設定可能な条件式まとめ(保存版)

ちなみに、5フレーム後の世界でレール1にもこのペナルティを適用する必要があるでしょうか?実のところ必要ないです。電車0の世界線でしか重複していないので、そもそも電車0のパターンをワンホットしていることを考慮すると両立するものではありません。しかしコーディングが面倒なので機械的に「0個または1個」を適用することにします。適用しても問題はない(実質無効)。

あとは強い条件(制約)と弱い条件(コスト)の重みですが、制約の方を100倍くらいにしておきましょう。とはいえ、衝突したらダメなのでコストも一切妥協できません。アニーリングさんには理論上の最小エネルギーを出してもらいます。

それから、何フレーム先までシミュレーションするかも調整してください。長すぎると重複を避けられなくなるし、短すぎるとどん詰まり(どうやっても衝突不可避な状況)に陥るリスクが出てきます。だいたいコースを0.8周するくらいのフレーム数で良いと思います。とはいえ電車によってスピードが違うため、早い電車が0.8周というと遅い電車は0.2周とかでどん詰まりリスクが出てきます。

ではどうすればいいか。遅い電車に合わせてある程度長い時間(100フレームくらい?)シミュレーションすることにして、nフレーム後のコストに (1/n^2) の重みをかけることで「近未来の衝突を優先的に避ける」解を出すようにします。重複が避けられないのは確実ですが、近未来の重複を避けることを優先してくれます。そして少し走ってから再度アニーリングするときには(速い電車の)未来が変わっていて、そのときはまた良い解が出てくるだろうと。

うーん、いや、まあ、自分もかなり疑いながら書いてます()

結果

定式化は以上ですが、その後のポイント切り替え制御も修正する必要があります。各電車にそれぞれのパターンが決まるので、電車がポイントに来たときに自分の分岐状態を呼び起こして適用します。現実ではやや手前で切り替える必要があるのですが、シミュレータではオンザレール瞬間切り替えです。

前回と同じ3台の電車で、毎フレームQUBOアニーリングしては進めるを繰り返してみました。手元のPCではアニーリング含めて3fpsくらいの計算速度でした(ショット数にもよりますが)。

365フレーム目で衝突しました。ここまでよく耐えていると思います。ちなみに3台のスピードを素数にすることで特定の周期的パターンに入ることを避けています(周期に入ると永久に続けられるみたいです)。

おわりに

次回はもう少しだけ修正して大きなコースでシミュレーションしてみます。

リアクションのお願い

「参考になった!」「刺激された!」と思ったらぜひリアクションをしましょう。エンジニアの世界はGive and Takeによって成り立っています。これからも無料で良質な情報にアクセスできるよう、Giveする人への感謝をリアクションで示しましょう!

この記事をシェアする

自身のブログ等で使用する場合は引用を忘れずに!

また、寄付も受け付けています。コーヒー1杯でとても喜びます(*˘︶˘*)

 Amazonでギフト券(アマギフ)を贈る

こちらのリンク から金額を指定してお贈りください。(デフォルトで10000円になっているのでご変更ください)

配送:Eメール
受取人:staffあっとvigne-cla.com
贈り主:あなたのお名前やニックネーム
メッセージ:◯◯の記事が参考になりました。など

のようにご入力ください。見返りはありませんのでご了承ください。

 Amazonで食事券(すかいらーく優待券)を贈る

500円 1000円 2000円 5000円 からお贈りください。

配送:Eメール
受取人:staffあっとvigne-cla.com
贈り主:あなたのお名前やニックネーム
メッセージ:◯◯の記事が参考になりました。など

のようにご入力ください。見返りはありませんのでご了承ください。

 その他、ギフト券やクーポン券をメールで贈る

デジタルのギフト券/クーポン券はメールアドレス(staffあっとvigne-cla.com)までお送りください。受領の返信をいたします。
紙のギフト券/クーポン券は 「郵便物はこちらへ」の住所 まで送付してください。名刺やメールアドレスを同封していただければ受領の連絡をいたします。
余った株主優待券等の処理におすすめです。
いずれも見返りはありませんのでご了承ください。

不明点はSNSでお気軽にご連絡ください

ビネクラのTwitter・Youtubeでコメントをください!


Slack・Discordの場合はこちらの公開グループに参加してShoya YasudaまでDMをください!


※当ブログに関することは何でもご相談・ご依頼可能です。

この記事を書いた人
Yasuda

博士(理学)。専門は免疫細胞、数理モデル、シミュレーション。米国、中国で研究に携わった。遺伝的アルゴリズム信者。物価上昇のため半額弁当とともに絶滅寸前。

タイトルとURLをコピーしました