RBFS, Recursive Best First Search を紹介します。

(Korf, R.E. 1993. Linear-space best-first search. Artificial Intelligence. 62(1):41–78.)

IDA* + inconsistent heuristics

IDA* は、ノードを$f\leq F$の範囲で探索し、各イテレーションごとに$F$を増やしていきます。IDA*は $f$ が単調増加することを仮定しているので、F以下のノードについて特に展開順序は定めていません。しかし、$f$ が単調増加しない場合、$f=F$ のノードの子孫に $f<F$ なゴールノードが来る場合があります。

このことにより、IDAにinconsistent heuristicsを組み合わせると、IDAの 最良優先(Best-first order)の要素が失われます。端的に言えば、IDA*は下のような単純なグラフに対してさえ、コストの高い$v'_g$ を返す可能性があるのです。

_{ん? ちょっとまって、上のグラフの$h$って許容的じゃなくない? そう思ったあなた、正解です。許容的な探索では、$f$値は真の最適コスト$f^＊=1$ を上回らないんでしたよね。最良優先の要素が重要なのは、主に非最適探索設定です。しかし、非最適探索においても、線形のメモリで探索を行えるIDA*の魅力は大きいですし、なるべくコストの低いゴールを探したいという要求は変わりません。順番が逆になりましたが、このことは三日後の山登り法の時に書きます。}

これは、$f\leq F$ のノードについて、子がどのような順で選ばれるかを指定していないことから起こります。

Recursive Best First Search (R. E. Korf, 1993)

そこでRBFSの出番です。RBFSは、単調増加しない $f$ に対しても最良優先な探索を行う、そしてIDA*と同じく線形のメモリしか用いないアルゴリズムです。

RBFSは、わかればエレガントですが、わかりにくいアルゴリズムとして非常に評判が高い(低い??)です。 人気がないのか、英語版ウィキペディアにも情報がありません。理解すれば面白いアルゴリズムです。ここで、 SoCS-2011 に出たとある論文を見てみましょう。(Ariel Felner, Position Paper: The Collapse Macro in Best-First Search Algorithms and an Iterative Variant of RBFS, SoCS 2015)

なんか不穏な雰囲気。引用数が少ないって??

Ruml先生はUniversity of New Hampshire の准教授です。とてもよい司会者

RBFSむっちゃ難しいって!!!

うーんどうなんだろう。実装できない/理解できないわけではないと思うんですが、動作をイメージできないという人が多いみたいです。と、とりあえずコードを見てみましょうか。ここには(Korf 1993) を少し改変したものを載せます。

Algorithm RBFS (node: $n=v_0$, value: $F(n)=0$, bound: $B=0$):

パート1 : Corner Case & Termination
- If $f(n)>B$, return $f(n)$
- If $n$ is a goal, exit algorithm ( $n$ から後ろ向けにパスをたどれば経路 )
- If $n$ has no children, return $\infty$
パート2 : Initial Scoring
- Let $Q$ be a priority queue
- For each child $n_i \in children(n)$, do
  - If $f(n)<F(n)$
    - $push(Q, n_i, F(n_i)=\max(F(n),f(n_i)))$
  - Else
    - $push(Q, n_i, F(n_i)=f(n_i))$
パート3 : Recursive Call
- $F(m) \leftarrow nextmin(Q)$ /* 最小の sort key */
- $m \leftarrow popmin(Q)$
- While $F(m) \leq B \land F(m) < \infty$
  - $push(Q, m, RBFS(n_1, F(m), \min(B, nextmin(Q)))$
- return $F(m)$ (= smallest $F(m)$ larger than $B$)

むっちゃわからん! 次章でもう少し解説をしますので、すこしお付き合いください。

これでも、オリジナルのアルゴリズムを意味単位に3つのパートに分けて書きました。再帰的定義はオリジナルと同じです。再帰的であるにも関わらず、再帰の各段階内部で優先度付きキューを用いる点が Recursive Best First Search の名前を物語っています。

RBFS の動作

RBFSの動作を一言で言い表すと、こうです。「f(n)が制限Bを超えるぎりぎりの所まであっちこっち少しずつ手を出しては、到達したf(n)の最大値F(n)だけ記録して手を引っ込め、Bの値を更新して別の方向にまた手を出す」。全然一言じゃないですね。

これを説明するために、ポケモンに縛りを付けたものを考えましょう。ソフトは、WikipediaによればポケモンX・Yが最新作らしいので、このソフトだとします。

問題は、初代金銀までしか遊んでいない世代である私には、どのポケモンがどの経験値でレベルが上がるか、そしてレベル何で進化するか全くわからないということです。そこで試しに次のような課題をたて、グラフ探索問題として解いてみましょう。

どの手持ちポケモン $p$ が最も低い経験値 $f(p)$ で進化するのかを、他のどのポケモンもその経験値以上に育てること無く知りたい

仮定として、私があわせて5匹のポケモンを持っているとし、それらはどれもlv.1で、かつどこかのレベルで進化するとしましょう。例えば、ポケモン $p_i (0\leq i < 5)$ が経験値 $(200, 300, 400, 500, 600)$ で、$p_4$ が経験値600で進化するような状況がゴールです。

さて、IDA*はこの問題を以下のように解きます。

Loop for L from 1 to $\infty$
- For each $p$ in Pokemons ; do
  - $p$ をレベル$L$まで育てて進化しなかったらリセット

となります。毎回1つのポケモンのみを育て、究極にえこひいきするような戦略です。アルゴリズムの終了時の手持ちポケモンの経験値は、例えば $(0,0,0,0,600)$ となります。

しかし、 すばらしいポケモントレーナーになるためには 、なるべくえこひいきせず、全てのポケモンを均等に成長させなくてはいけません。RBFSはこのような用途に向いています。ここでまず、ポケモン $p$ の2つの経験値、$f(p)$と$F(p)$について説明しましょう。

$f(p)$は、セーブされている「有効な」経験値です。
- 「ほかのどのポケモンも超えない」という制限が当てはまるのはこの経験値です。
$F(p)$は、セーブされていない過去を含めた 中で、そのポケモンが経験した最大の経験値です。

RBFSは以上のf,Fを用いて以下のようにポケモンを育てます...

セーブします。
$F$ の最も小さいポケモン $p$ をどんどん育てます。
- このとき、次に小さい$F$ 値を持つポケモンを$p'$ とします。
- $p$ のレベルアップ時に、$p$ の経験値が $nextmin(Q)=F(p')$ を超えてしまっていたら、
  - リセットして一つ前のセーブまで戻ります。
  - このとき、リセット直前の経験値を$F(p)$に記録します。
ポケモンを$F$に従ってソートし直します。以下ループ。
- 今度は $p'$ が最小のFを持っているはずです。

なんとかお分かりいただけたでしょうか。このようにRBFSは、様々な子ノードを公平に、言い換えれば 移り気に 展開するアルゴリズムです。理解できるとこの説明でしっくりいくんですが… (ちなみにこのポケモンの例は、スタートから5本分岐してあとは直線になっているような木として捉えられます)

RBFSは、$F(n)$による優先度付きキュー $Q$ がソート機能を持つので、はじめに見せた非単調な$f$ を用いるグラフでも、最良優先な展開順序を保ちます。

ILBFS

上で一瞬述べた (Felner 2015) で提案されたのがILBFS (Iterative Linear Best First Search) です。Felner はこの論文で、Collapse & Restore という操作を用いて A*, IDA*, EPEA*, SMA*, LA* そしてRBFSを統一的に説明する手法を提案しました。 ILBFSは、Collapse&Restoreを用いてRBFSを捉え直し、わかりやすく書きなおしたアルゴリズムです。

_{それだけで論文になるのかよって感じはありますが、SoCSの採択率は厳しくない(3rd Tierぐらいか?)ので、驚くことではないです。IROS,ICAPS,IJCAI,AAAIの常連が集まる場所なので、間違った内容はそんなに投稿されませんが、感覚的に重要度が低いのが多い。}

Collapse 操作と Restore 操作は以下のような操作です。

$Collapse(n, b)$
- ノード $n$ の子孫(subtree)を $T(r)$ とする。
- $T(r) \cap OPEN$ で最小の $f$ を $F(n)$ とする。
- $T(r)$ を OPEN,CLOSEから取り除く。
- $n$ を $F(n)$ を用いてOPENに入れる。
$Restore(n)$
- $n$ の子孫をどうにか再生成する (アルゴリズム依存)。このとき、何らかの手法で$F(n)$ をboundとして探索する。

ちなみにAはCollapseしない手法, IDAは常に開始ノードでcollapseする手法として捉えられています。

まとめ

RBFSを紹介しました。

明日明後日は優しい研究室メンバが二日間も書いてくれます。いずれも並列探索に関するものです。感謝。