Bidirectional A* -- 双方向探索に決着がついた日

本日学振DC2の採択通知が来た浅井です。クリスマスプレゼントかな。_{罰ゲームかも}

今日は双方向探索の話をします。Aがある程度知られていたのと同様、双方向探索もあるていど知られていると思います。結論としては、双方向探索は ブルートフォースかそれとほとんど変わらない弱いヒューリスティクスを用いた時ぐらいしか使えない ということを示します。強力なヒューリスティクスがある場合には、Aのほうがよいです。

双方向探索

双方向探索 という手法があります(Pohl 1971)。スタートとゴールから交互に逆向きに探索を始め、どちらかが出会ったところで探索が終了するというものです。双方向探索を$A^＊$に用いたものを、Bidirectional A* と呼びます。

http://www.massey.ac.nz/~mjjohnso/notes/59302/l03.html より。

1つの見方としては、これはとても優れた手法の はず です。A*の探索に必要なノードの数は、解までの深さ$d$, Branching factor $b$ として $O(b^d)$ でした。必要となる探索が深くなればなるほど、必要なメモリ量が指数的に増大します。一方双方向$A^＊$は、うまく行けば$A^＊$の半分の深さで探索を終えることが出来ます。 これは、必要となる探索空間のサイズが $O(b^{d/2})$ になることを意味します。

ですが 別の見方 からすると、これは酷いアイディアでもあります。これはたとえば、渋谷と本郷にいる二人の学生A,Bが、「新宿のあたりで合流ね♪」とか言って勝手に歩き出すようなもんです。絶対迷います。実際、アルゴリズム的にも、探索の先端 (Search Frontier) が重なったか否かを見るために、多対多の比較をしなくてはなりません。これは、多対一の比較だけが必要な一方向探索よりも作業が多そうです。

用語:

• Search Frontier: OPEN にあるノードのうちで、最小の$f$ 値を $f_{min}$ としたとき、 $f=f_{min}$ であるようなノードを集めたもののこと。探索フロンティア。
• Forward Search: スタートからゴールに向けてノードを探索するタイプの一方向探索。前方探索。
• Backward / Regression Search: ゴールからスタートに向けて探索するタイプの一方向探索。後方探索。

それだけではありません。双方向探索では、Frontier が $d/2$ ぐらいのところで出会うことを期待していますが、2つのFrontierを持つということは、同じ$f_{min}$ まで探索した時点で使うメモリの量は A* のおおよそ 2倍 必要です。これは、深さが$f^＊/2$ に達する前にメモリで死ぬかもしれないことを意味します。(どちらも新宿まで辿り着かず野垂れ死ぬような感じ…)

Bidirectional A*

双方向A*にも、様々なサブタイプがあります。

• Front-To-End Bidirectional $A^＊$ : ノード$s$ の見積もり値が、前方探索部分では ゴールノードに対して、後方探索部分では初期ノードに対して計算されるタイプの双方向A*。 学生Aは現在位置から本郷までの距離の見積もり値を用い、学生Bは現在位置から渋谷までの見積もり値を用いる、というような感じ。
• Front-To-Front Bidirectional $A^＊$ : 前方探索と後方探索が、お互いのFrontierを考慮して見積もりを行うタイプの双方向A*。 学生の例では、渋谷~Aの実際の距離、A~Bの推定値、B~本郷の実際の距離、の3つの和を最小化するように探索する。

今日扱うのは Front-To-End A*です。

Algorithm Bidirectional $A^＊$

• Initialize A* from $v_0$ (Forward OPEN : $OPEN_f$)
• Initialize A* from $v_g$ (Backward OPEN : $OPEN_b$)
• while :
  • Expand 1 node in $OPEN_f$
  • If Frontier が衝突したか?
    • $ProveOptimality($現在のSolution Path$)$
  • Expand 1 node in $OPEN_b$
  • If Frontier が衝突したか?
    • $ProveOptimality($現在のSolution Path$)$

Frontier が衝突しただけでは、これが最適解であるとは限りません。そこで、次の条件が満たされるまで探索を続行します。

Subroutine $ProveOptimality(p)$

• $c \leftarrow cost(p)$
• Continue searching until
  • $c < f_{min}(OPEN_f),$ or
  • $c < f_{min}(OPEN_b),$ or
  • $c < g_{min}(OPEN_f) + g_{min}(OPEN_b)$
• Update $p$ if new path $p'$ has $cost(p') <c$

双方向 A* の効果 (Kaindl and Kainz, 1997. JAIR 7:283–317)

双方向探索を実用で使うためには、それが実際どういう時にうまくいって、それがなぜなのか、悪くなる時はそれがナゼなのか、これらをよく理解しておく必要があります。これを詳しく検証したのが題に載せた論文です。

この記事ではじめに双方向探索を紹介した時、「AとBが新宿で待ち合わせをするようなもので、はぐれるに決まってる」という説明をしました。実は、Kaindl and Kainz によれば、これは双方向$A^＊$+ consistent heuristics では起こりません。双方向探索が1971年に提唱されてからこの論文まで実に26年間、研究者らは「前方探索と後方探索がはぐれるから双方向探索は失敗するのだ」と なんとなく 思っていたのですが、実はそんなことはなかった、と定説をひっくり返したのがこの論文です。

_{もちろんそれだけでもかなりびっくりする内容ですが、「すごい発見とすごい改善と両方やらなくっちゃあいけないところがトップジャーナルの辛い所だな・・・」。論文はこれらの知見に基づいたさらなる提案手法を示し、性能向上を示しています。Kaindl and Kainz はその後も、探索の途中で双方向探索から一方向探索に切り替える手法など、いろいろ研究を行っていたみたいです。(IJCAI, 1999)}

Kaindl and Kainz のJAIR論文は、こんどは「双方向探索が失敗するのは$ProveOptimality$に時間がかかるからだ」と結論づけました。が、(Korf, AAAI 2015) はこれもまた違うということを示しました。真実はこうです。

$ProveOptimality$に時間がかかるのはヒューリスティックが弱い時である。

Korf, AAAI 2015

弱い ヒューリスティクスとはどのようなものをさすのでしょうか。と、そのまえに、ヒューリスティック関数の特性についておさらいしておきましょう。一般に、 $\forall n ; h_1(n) < h_2(n)$ であるような場合、 $h_2$ は　$h_1$を dominate しているとよび、 $h_2$ を用いて探索すると、必要な探索ノード数が減るのでした。

ここでBidirectional Searchの分析で重要なのは 深さ毎の展開数 です。なぜなら、Bidirectional Search では 深さがちょうど $f^＊/2$ ぐらいのところでFrontierが衝突することが期待されているからです。

下の図は、前方探索において、ブルートフォース(Dijkstra, $h=0$)からだんだんヒューリスティック関数の質を上げていった場合の、深さ毎の展開ノード数の推移です(左端が初期ノード)。質の低い下界関数であるほど、探索ノード数がゴール側に偏っていることがわかります。 _{Additional info: この図で用いた問題インスタンスは、解ける程度に簡単なハノイの塔インスタンスです。用いたヒューリスティクス関数はパターンデータベース(PDB)。}

また、濃い灰色はブルートフォースで双方向探索を行った時の展開ノード数です。このような状況で双方向探索を行うと、ノード数が爆発的に多くなる深いところのノードを探索しなくて良くなることがわかります。

しかし、1997年の時点では発見されていなかったようなより高性能なヒューリスティック関数を用いると、グラフの見た目はガラリと変わります。下の図の薄い灰色がその図です。質の高い下界関数では、探索ノード数がスタート側に偏ることがわかります。もちろん、全体の探索ノード数は質の悪い関数より二桁以上少なくなっています。

もしこのような関数を用いている時に双方向探索をおこなったらどうなるでしょう。それを見るために、後方探索をプロットしたのが濃い灰色のグラフです。前方と後方を同時に行うと、前方探索だけの時よりも多くのメモリを使用してしまうことがわかるでしょうか。 もしも使えるメモリ量がもっと制限されていたら、あるいはもっと難しい問題だったら、Solution Midpoint に到達する前にメモリ不足で探索に失敗してしまうかもしれません。

まとめ

二つ目の図のように、あるヒューリスティック関数を用いて半分以上のノードがmidpoint以前に展開されるような場合、その関数を 強い ヒューリスティック関数と呼ぶことにすれば、大雑把な結論として、強いヒューリスティック関数を用いる場合には双方向探索は避けるべき と言うことができます。逆に、ヒューリスティクスが全然わからない場合には、双方向探索は使える可能性があります。

というわけで、今日は双方向探索とその使いドコロを示しました。

_{老人の国から早く脱出しないと・・・}