アニーリングマシンを活用した次世代自動配線ツールの開発

取り組んだ内容

2024年度の未踏ターゲット事業を通して、プリント基板設計における配線の自動化ツールの開発に取り組みました。大学のサークル活動でロケットやロボットの制御基板の設計を行っていましたが、基板の配線は、多くの制約条件のもとで複数の部品を結線する必要があり、人手による作業では膨大な時間がかかる上、設計の最適化が困難だという課題を抱えていました。特に複雑な基板では、配線の交差回避やビア数（層間の貫通穴の数）の削減、配線長の最小化など、様々な要素を同時に考慮する必要があります。これらの課題に対して、量子アニーリング・イジングマシンを活用し、最適な配線を自動作成するツールを開発しました。

組合せ最適化問題の概要

プリント基板上の各部品を接続する配線に対して複数の配線候補を用意して最適な組み合わせを選択する問題です。基板上では、複数の部品間を配線で結ぶ必要がありますが、配線は他の配線と交差しないように、かつできるだけ短く、ビア数も少なく抑えることが求められます。また、一定のスペース内に引ける配線本数の上限（密度制約）も存在します。今回は、各配線に対して複数の候補経路を用意し、それらを組み合わせて、交差・配線長・ビア数・密度制約を考慮しつつ、全体のコストが最小となるような配線パターンを導き出す組合せ最適化問題に取り組みました。

決定変数

配線 i が配線候補 j を選択するかどうかを表すバイナリ変数

目的関数

選択した配線の配線長及びビア数の最小化

制約条件

• 交差する2配線は同時に選択しないこと
• 狭い領域を通過する配線数が通過可能数以下であること
• 各接続に対して1本だけ選ばれること

苦労した点

苦労した点は大きく二つありました。一つ目は、問題設定と定式化です。6月のプロジェクト開始直後から3ヵ月程度かけて3〜4パターンの定式化を並行して検討しました。9月末の中間発表の際にいただいたPMの方からのフィードバックなどを踏まえて、最終的な定式化の方向性を決めました。「配線の最適化」という一つの問題に取り組んでいるわけですが、問題設定や定式化の方法次第で最適化問題としての解きやすさや将来の拡張性などに大きな違いが生まれるということを学びました。二つ目は、問題の大規模化です。まずは小規模な問題からはじめ、徐々に問題の規模を大きくしていきましたが、大規模な基板になると配線候補の組み合わせが膨大になり、アニーリングの決定変数の数も増え、最適化の計算が困難になっていきます。この課題に対して、試行錯誤を繰り返し行いました。この試行錯誤は、非常に泥臭く時間がかかる作業でした。最終的には、ある程度規模を絞った問題で最適化計算を何回か行い、その結果をもとに不要な経路候補を「捨て」、有望な経路候補を「追加する」というサイクルを回すことで、徐々に精度を高める工夫を考案し、納得のいく結果を得ることができるようになりました。

良かったこと・嬉しかったこと

今回の未踏ターゲット事業を通じて、アニーリング技術を初めて本格的に活用しましたが、その手軽さに驚きました。2次・非線形問題ということで、線形問題よりも複雑な問題であるにもかかわらず、線形ソルバーと同じような感覚で実装でき、学習コストが非常に低かったです。
また、自分たちが提案したアルゴリズムで、大規模な基板でも整然とした配線結果を得られたときは、とても嬉しかったです。特に、得られた解を可視化して、配線がきれいに通っているのを確認できたときは、問題設定・定式化・工夫・実装などを含めて「自分たちの手法が正しかった」と実感でき、何事にも代えがたい大きな達成感がありました。

今後の展望

今後は、現在取り組んでいる「配線の最適化」の改良に加え、基板上の「部品配置の最適化」にも取り組んでいきたいと思っています。部品配置の最適化は、配線の前に行う作業になりますが、こちらも量子アニーリング・イジングマシンを使えたら面白いんじゃないかなと思っています。明示的な定式化が困難な可能性もあるので、量子アニーリング・イジングマシンを活用したブラックボックス最適化（FMQA）を活用するかもしれません。最終的には、この部品配置と自動配線を組み合わせて、アプリケーション化することを目指しています。

見ている方に一言

量子アニーリングは、難しい問題をスマートに解くための大きな可能性を秘めた技術です。取り組みを開始した当初は「量子は万能」というイメージを持っていましたが、実際に取り組んでみると、うまくいかない場面も多く、正しい定式化や適切な使い方が非常に重要だと感じました。それでも、適切に活用すればこれまで手作業で行っていたような面倒な課題も解決できることを実感しました。また、一度取り組むと、身の回りの多くの課題が実は組合せ最適化問題として捉えることができると気付くと思います。ご興味のある方は、ぜひ一度試してみると良いと思います。

＊本記事の掲載内容は全て取材時の情報に基づいています