リバースアニーリングによるAGV経路最適化

Table of Contents

文献情報

タイトル：Travel time optimization on multi-AGV routing by reverse annealing
著者：Renichiro Haba, Masayuki Ohzeki & Kazuyuki Tanaka
書誌情報：https://doi.org/10.1038/s41598-022-22704-0

概要

量子アニーリングは、組合せ最適化問題を解くための高速なヒューリスティック手法として研究が進められています。実世界への応用例の1つに、工場や倉庫で用いられる無人搬送車（AGV: Automated Guided Vehicle）群の経路制御があります。複数のAGVを同時に動かす場合、経路の選び方によっては衝突やデッドロックが発生するため、安全性を保ちながら搬送時間を短縮する経路計画が重要です。

本論文では、複数AGVの走行時間を短縮するため、目的地までの残り距離を最小化するQUBO定式化を提案しました。従来の定式化[1]では、衝突を避ける経路を高速に求められる一方で、全体の迂回距離を十分に考慮しないため、AGVが不要に遠回りする可能性がありました。これに対して、本論文で提案する定式化では、各AGVがより目的地に近づく経路を選ぶように目的関数を設計することで、搬送効率の向上を目指しました。

さらに本論文では、D-Waveの量子アニーリングマシンの機能であるリバースアニーリング（RA）を用いています。RAは、あらかじめ得られた古典的な解を初期状態として与え、その近傍でより良い解を探索します。シミュレーションの結果、RAはフォワードアニーリング（FA）よりも良い性能を示し、20台のAGV制御ではGurobiとほぼ同等の搬送性能を示しました。また、小さい問題サイズでは、RAがGurobiよりも短い時間で最適解を得られる場合があることも確認されました。

背景

無人搬送車（AGV）

無人搬送車（AGV）は、工場、倉庫、コンテナターミナルなどで資材や荷物を運ぶために用いられています。AGVは床に設置されたマーカーやワイヤーに沿って移動し、これらの経路はネットワークとして表すことができます。図1に、AGVが走行する経路ネットワークの例を示します。図中の丸は交差点や中間点を表すノード、矢印は2つのノード間を結ぶ有向エッジ、四角は荷物の出発地点または目的地点となるノードを表しています。

複数のAGVが同じネットワーク上を同時に走行する場合、同じエッジや交差点を同時に利用しようとすることがあります。その結果、衝突やデッドロックが発生する可能性があります。AGVの経路計画では、このような衝突を避けることに加えて、搬送時間を短縮するためにできるだけ短い経路を選ぶことが求められます。

量子アニーリング

量子アニーリングは、二値変数を用いた組合せ最適化問題を解くヒューリスティックアルゴリズムです。量子揺らぎを利用して解空間を探索する点が特徴であり、QUBO（Quadratic Unconstrained Binary Optimization）問題と呼ばれる形式の最適化問題を解くために用いられます。

QUBO問題は、二値変数ベクトル$\boldsymbol{q} \in \{0,1\}^N$と行列$Q$を用いて、次のように表されます。

$$
\tag{1}
f_{QUBO}(\boldsymbol{q}) = \boldsymbol{q}^\mathsf{T} Q\boldsymbol{q} + \text{Const.}
$$

この QUBO問題は、イジングモデルのエネルギー最小化問題に変換できます。イジングモデルのハミルトニアンは、スピン変数$\sigma_i \in \{-1,1\}$を用いて次のように表されます。

$$
\tag{2}
H_0(\sigma) = -\sum_i h_i \sigma_i – \sum_{i < j} J_{ij} \sigma_i \sigma_j $$ QUBO問題とイジングモデルについて、詳しくはこちらの記事をご覧ください。

D-Waveの量子アニーリングマシンでは、横磁場を含むハミルトニアンを時間とともに変化させることで、最適解に近い状態を探索します。この時のハミルトニアンは次のように表されます。

$$
\tag{3}
\hat{H}(s) = -A(s) \sum_i \hat{\sigma}_i^x + B(s)\hat{H}_0
$$

ここで、$\hat{\sigma}_i^x$は$i$番目の量子ビットの状態を変化させる働きを持つパウリ行列です。また、$\hat{H}_0$は求めたい最適化問題を表したハミルトニアンです。式(2)ではスピン変数を用いて問題を表しましたが、量子アニーリングマシン上ではそれをパウリ行列の$z$成分に置き換えて表します。さらに、$s \in [0,1]$は時間に依存して変化するパラメータであり、アニーリングスケジュールによって制御されます。アニーリングの初期段階、すなわち$s=0$の状態では$A(s) \gg B(s)$であり、横磁場の影響が大きいため、量子ビットは様々な状態を取りやすくなります。時間が進むにつれて徐々に$A(s)$は小さく、$B(s)$は大きくなります。最終的に$s=1$では$A(s) \ll B(s)$となり、最適化問題を表す$\hat{H}_0$の影響が支配的になります。これにより、量子ビットの状態は少しずつエネルギーの低い状態、すなわち最適化問題の答えに近い状態へと変化していきます。

アニーリングの方法には、フォワードアニーリング（FA）とリバースアニーリング（RA）があります。図2に、それぞれのアニーリングスケジュールを示します。標準的な量子アニーリングであるFAは、上述の通り$s=0$、すなわちすべての状態が重ね合わされた状態から探索を開始し、時間とともに$s=1$へ近づけることで、古典的な状態を得る手法です。この方法では、広い解空間を探索できる一方で、制約条件を満たす実行可能解が必ず得られるとは限りません。

一方、RAは、あらかじめ与えられた古典的な初期解から探索を開始する手法です。まず$s=1$の古典的な状態から始め、そこから一度$s$を小さくすることで横磁場の効果を強めます。これにより、初期解の周辺にある別の解へ移りやすくなります。その後、再び$s=1$に戻すことで、初期解の近傍からよりエネルギーの低い解を探索します。つまり、RAは、すでに得られている解を初期解として、その近くにあるより良い解を探す局所探索的な方法です。

図2：FAとRAのアニーリングスケジュール
https://doi.org/10.1038/s41598-022-22704-0

本論文でRAを用いる主な理由は2つあります。第1に、貪欲アルゴリズムのような高速な古典アルゴリズムで得られた解を実行可能な初期解として使うことで、FA単独よりも良い解を得られる可能性があるためです。第2に、実行可能な初期解を用意しておくことで、量子アニーリングの出力が実行不可能な解になった場合でも、元の初期解を利用してシステムの停止を避けられるためです。

RAでは、反転距離$r$が重要なパラメータとなります。反転距離は、図2のアニーリングスケジュールに示すように、$s=1$からどの程度$s$を小さくするかを表す値であり、初期状態にどの程度量子揺らぎを与えるかを決めます。反転距離は、小さすぎる場合、量子揺らぎが弱く初期解からほとんど変化しないため、より良い解を探索する効果が小さくなります。一方で、反転距離が大きすぎる場合、量子揺らぎが強くなりすぎるため、初期解の近傍を探索するというRAの特徴が失われてしまいます。その結果、初期解の情報が十分に活かされず、FAに近い広域探索となってしまいます。

本論文では、反転距離を決定するために行った実験として、20台のAGV制御中に現れた10個のQUBO問題を用いて、反転距離を変えたときの解の変化を調べました。その結果を図3に示します。図3では、赤色の領域が初期解と同じ状態、緑色の領域がより良い基底状態、灰色の領域が基底状態ではない解を表しています。反転距離が小さい場合は、初期解にとどまりやすく、反転距離が大きすぎる場合は最適解を得にくくなります。図3より、最適解が得られる確率が高かった$r=0.45$を本論文における反転距離として採用しました。

図3：反転距離の調整結果
https://doi.org/10.1038/s41598-022-22704-0

手法

本論文では、各AGVに割り当てられた荷物と、その荷物の出発地点および目的地点が与えられている状況を考えます。このとき、荷物を出発地点から目的地点まで搬送する作業をタスクと呼びます。目標は、各AGVが衝突せずに走行しながら、一定時間内にできるだけ多くのタスクを完了できるような経路を決定することです。

AGVの経路制御は、一定時間$T$ごとに次の処理を繰り返す動的アルゴリズムとして行われます。図4に、処理1から3までの流れを示します。

各AGVについて、現在位置から目的地までの複数の候補経路を生成
候補経路を、時間$T$内に到達可能な長さに短縮
AGVが途中で停止できるように、候補経路を複数の部分経路に分割
すべてのAGVについて、目的関数を最小化する経路の組み合わせを選択
選択された経路に従って、AGVを時間$T$だけ移動

図4の例における最終的な候補経路の数は、図に示された6本の経路とその場に停止し続ける操作を合わせて7つとなります。

また、上に示した動的アルゴリズムのうち、本論文の中心となるのは4番目の最適化です。各AGVがどの候補経路を選ぶかを二値変数で表し、衝突を避けながら目的地までの残り距離を小さくするように目的関数を定義します。

$i$番目のAGVが$j$番目の候補経路を選択する場合に$q_{ij}=1$、選択しない場合に$q_{ij}=0$とします。また、$d_{ij}^*$を、$i$番目のAGVが$j$番目の候補経路を進んだ後の終端ノードから目的地までの最短距離とします。このとき、目的関数は次のように定義されます。

$$
\tag{4}
f_{obj}(\boldsymbol{q}) = \sum_{i=1}^{N} \sum_{j=1}^{M_i} d_{i,j}^* \, q_{i,j}
$$

ここで、$N$はAGVの台数、$M_i$は$i$番目のAGVに対する候補経路の数を表します。この目的関数を最小化することで、各AGVの目的地までの残り距離の合計が小さくなる経路を選択できます。

制約条件は2つあります。1つ目は、以下に示すように各AGVが候補経路の中から必ず1つの経路を選択するという制約です。

$$
\tag{5}
\sum_{j=1}^{M_i} q_{i,j} = 1, \quad \forall i \in \{1, 2, \ldots, N\}
$$

2つ目は、同じ時間に同じエッジを複数のAGVが占有しないようにする衝突回避制約です。$F_{i,j,t,e}$を、時刻$t$において$i$番目のAGVの$j$番目の候補経路がエッジ$e$を占有する場合に1、そうでない場合に0をとるとすると、制約は次のように表されます。

$$
\tag{6}
\sum_{i=1}^{N} \sum_{j=1}^{M_i} F_{i,j,t,e} \, q_{i,j} \leq 1, \quad \forall e \in E, \quad \forall t \in \{1, 2, \ldots, T\}
$$

ここで、$E$はネットワーク上のすべてのエッジの集合です。この制約により、各エッジを同時に占有できるAGVの台数を1台以下に制限します。なお、あるAGVがノードに進入する場合、そのノードに接続するほかのエッジも占有されているものとして扱うことで、交差点での衝突も防ぎます。

量子アニーリングで解くために、これらの制約をペナルティ項として目的関数に加え、QUBO形式に変換します。

$$
\tag{7}
f_{QUBO}(\boldsymbol{q})
= \sum_{i=1}^{N} \sum_{j=1}^{M_i} d_{i,j}^* \, q_{i,j}
+ a \sum_{i=1}^{N} \left( \sum_{j=1}^{M_i} q_{i,j} – 1 \right)^2
+ b \sum_{t=1}^{T} \sum_{e \in E} \left( \sum_{i=1}^{N} \sum_{j=1}^{M_i} F_{i,j,t,e} \, q_{i,j} – \frac{1}{2} \right)^2
$$

第1項は各AGVの目的地までの残り距離の合計を表し、第2項は各AGVが1つの経路を選ぶための制約、第3項は衝突回避制約に対応します。第3項では、同じ時刻$t$に同じエッジ$e$を占有するAGVの台数が0台または1台の場合は許容し、2台以上となる場合にペナルティが加わるように、$\frac{1}{2}$を用いています。これにより、エッジが使用されていない場合と1台のAGVのみが使用している場合を同程度に扱いつつ、複数のAGVによる同時占有を避けることができます。$a$と$b$は、制約違反に対するペナルティの重みを表すハイパーパラメータです。

また、本論文ではRAの初期解を得るために貪欲アルゴリズムを用いています。貪欲アルゴリズムの流れは次の通りです。

各AGVに最短経路を割り当てる
衝突する2台のAGVについて、次の候補経路に変更した場合に衝突する台数の少ない方の経路を変更する
すべてのAGVが衝突しなくなるまで、候補経路の変更を繰り返す

この貪欲アルゴリズムは、衝突のない経路を高速に求めることを目的としています。一方で、経路の選択時に全体の迂回距離を十分に考慮しないため、不要な迂回が生じる可能性があります。

実験

実験設定

実験では、図5に示すような、すべてのエッジの長さが1mの仮想的な工場内の経路ネットワーク上で、20台のAGVを動作させるシミュレーションを行います。各AGVには順番に実行すべきタスクが与えられ、AGVは出発地点から目的地点まで荷物を運びます。各AGVの速度は$0.5\,\mathrm{m/s}$とし、1イテレーション当たりの時間間隔$T$は2秒に設定されています。シミュレーションは500イテレーション、すなわち合計1000秒行われます。

図5：AGVが走行する経路のネットワーク
https://doi.org/10.1038/s41598-022-22704-0

評価指標

Time-to-solution（TTS）は、一定の確率で最適解を得るまでに必要な時間を評価する指標であり、次の式で定義されます。

$$
\tag{8}
TTS(p) = t_c \frac{\log(1-p)}{\log(1-p_s)}
$$

ここで、$p$は少なくとも1回最適解が得られる確率、$p_s$は1回の試行で最適解が得られる確率、$t_c$は1回の試行にかかる計算時間です。たとえば、$TTS(0.99)$は、99%の確率で最適解を得るために必要な推定時間を表します。

残留エネルギーは、得られた解が最適解にどれだけ近いかを評価する指標であり、次の式で定義されます。

$$
\tag{9}
E_{res} = \frac{\langle E \rangle – E_{min}}{E_{min}}
$$

ここで、$\langle E \rangle$はサンプルの平均エネルギー、$E_{min}$は最適解のエネルギーです。ここでのエネルギーは、式(7)で示したQUBO形式の目的関数値、またはそれと等価なイジングモデルにおけるエネルギーに対応します。残留エネルギーが小さいほど、得られた解のエネルギーが最適解に近いことを表します。

結果

まず、完了タスク数と稼働率の比較結果を表1に示します。

表1：各手法における完了タスク数と稼働率の比較
https://doi.org/10.1038/s41598-022-22704-0

Gurobiは完了タスク数において最も高い値を示しました。一方で、貪欲アルゴリズムはGurobiよりも稼働率が高かったものの、完了タスク数は少なくなりました。これは、貪欲アルゴリズムではAGVが停止している時間が短く、高い稼働率を保つ一方で、不要な迂回が発生し、結果として搬送効率が低下したためです。このことから、高い稼働率は必ずしも搬送効率を高めるとは限らないことが分かります。FAは、完了タスク数と稼働率の両方で最も低い性能となりました。一方、RAはFAを上回り、Gurobiに近い完了タスク数と稼働率を示しました。この結果から、貪欲アルゴリズムで得た実行可能解を初期状態として用いるRAは、複数AGVの制御において有効であることが示されました。

次にTTSの比較結果を図6に示します。ここでは、10個のQUBO問題に対して$TTS(0.99)$を測定しています。横軸は問題サイズであり、各AGVの候補経路数の合計を表します。

図6：RAとGurobiのTTS比較（エラーバーは標準誤差）
https://doi.org/10.1038/s41598-022-22704-0

図6より、問題サイズが小さい場合、RAはGurobiより短い時間で最適解を得られることが確認できました。特に小さい問題サイズでは、最大で約10分の1の短い時間で最適解を得られる場合がありました。ただし、問題サイズが大きくなるとRAの性能は低下し、Gurobiのほうが短時間で最適解を得られるようになりました。また、問題サイズが100を超える場合には、RAで最適解を見つけられませんでした。

最後に残留エネルギーの比較結果を図7に示します。残留エネルギーは、RA、FA、貪欲アルゴリズムの3つで比較しました。

図7：RA、FA、貪欲アルゴリズムの残留エネルギー比較（エラーバーは標準誤差）
https://doi.org/10.1038/s41598-022-22704-0

図7より、RAは多くの問題サイズでFAや貪欲アルゴリズムよりも低い残留エネルギーを示しました。これは、RAが貪欲アルゴリズムによる初期解を改善できたことを示唆します。ただし、問題サイズが250程度になると、FAのほうが低い残留エネルギーを示す場合もあり、大規模問題に対しては初期解の探索方法の改善が必要であると考えられます。

考察

実験結果から、提案されたQUBO定式化は、複数AGV制御における搬送時間の短縮に有効であると考えられます。表1に示したように、貪欲アルゴリズムは高い稼働率を実現できますが、迂回距離を十分に考慮しないため、必ずしも完了タスク数の増加にはつながりませんでした。これに対して、目的地までの残り距離を最小化する本手法では、AGVがより効率的に目的地へ近づくため、搬送効率が向上したと考えられます。

また、図6および図7の結果から、RAは、貪欲アルゴリズムで得られた実行可能解を初期解として、その近傍からより良い解を探索できる点で有効です。実際、FAが低エネルギー解を十分に見つけられなかったのに対し、RAは安定して性能を改善しました。このことから、古典アルゴリズムと量子アニーリングを組み合わせるハイブリッド手法には有用性があると言えます。

一方で、RAの性能は問題サイズに依存します。図6に示したように、問題サイズが大きくなると、RAよりGurobiの方が優位になります。また、図7からは、問題サイズが大きい場合にRAの残留エネルギーが増加する傾向も読み取れます。これは、貪欲アルゴリズムで得られる初期解の質が低下し、RAによる改善が十分に働かなくなるためだと考えられます。したがって、より大規模な問題に適用するためには、初期解を生成するアルゴリズムの改良や、問題サイズに応じた探索方法の切り替えが重要になると考えられます。

結論

本論文では、複数AGVの走行時間を短縮するため、目的地までの残り距離を最小化するQUBO定式化を提案しました。シミュレーションの結果、この定式化によって不要な迂回を抑え、時間効率の良い搬送経路を実現することが示されました。

また、貪欲アルゴリズムで得た実行可能解を初期状態として用いるRAは、FAより高い性能を示し、20台のAGV制御ではGurobiとほぼ同等の搬送性能を示しました。さらに、小さい問題サイズでは、Gurobiより短い時間で最適解を得られる場合がありました。一方で、問題サイズが大きくなるとGurobiが優位になるため、RAの性能向上には初期解の改善が重要であると考えられます。

参考文献

[1] Ohzeki, M., Miki, A., Miyama, M. J. & Terabe, M. Control of automated guided vehicles without collision by quantum annealer and digital devices. Front. Comput. Sci. 1, 9. https://doi.org/10.3389/fcomp.2019.00009 (2019).

あとがき

本論文ではシミュレーテッドアニーリング（SA）との比較は行われていませんでした。SAを用いた場合、量子アニーリングのような量子トンネル効果は利用できないものの、問題サイズや初期解によってはRAに近い性能を示す可能性もあると思います。そのため、今後はSAを含めた比較を行い、どの手法がどの条件で有利なのかを調べてみたいです。また、TTSの性能比較では、RAは貪欲アルゴリズムで得た初期解を用いている一方、Gurobiは最初から最適化を行っています。そのため、実用上の計算時間をより公平に比較するには、貪欲アルゴリズムによる初期解生成時間とRAの実行時間を合計し、Gurobiの実行時間と比較する必要があると感じました。この点を検証することで、RAが実際のAGV制御にどの程度有効かをより詳しく評価できると考えられます。

本記事の作成者

山田竜雅

Post Views: 16