AI要約
3台のプラレールが同一コースを走行する中、QUBOアニーリングを用いてポイント切り替えを制御し、衝突を回避するシミュレーションに挑戦。問題をQUBOで定式化し、ポイントの最適な切り替えを探索しました。
やること
前回、Pythonでプラレールのシミュレータを作りました。
これでいろいろな制御を試すことができそうです。このコースに3台の電車を走らせて、できるだけ衝突しないように量子アニーリング(QUBO)でポイント切り替えを制御してみましょう。コードは複雑になってしまうので割愛します。ご了承を。
TYTANについて
オンライン講義のアーカイブはこちらから見れます。
discordコミュニティもあるので気軽に質問できます。
定式化
いろいろな方法が考えられるとは思いますし、というかそもそも未来をシミュレーションしてかっちり制御すればなんてことない問題なのですが、わざわざ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台のスピードを素数にすることで特定の周期的パターンに入ることを避けています(周期に入ると永久に続けられるみたいです)。
おわりに
次回はもう少しだけ修正して大きなコースでシミュレーションしてみます。