EHCを少し改変したLeast Bad Search を紹介します。あんまり面白くなかった・・・
Least Bad Search は、イギリス王立大学 (King's College of London) のAmanda/Andrew Coles 教授夫妻(教授同士で結婚かよ…) のMarvinというプランニングソルバに載っている探索アルゴリズムです。
Coles, Andrew, and Amanda Smith. "Marvin: A Heuristic Search Planner with Online Macro-Action Learning." J. Artif. Intell. Res.(JAIR) 28 (2007): 119-156.
Search Plateau (プラトー)
最適化や探索の専門ではない人であっても、Plateau という言葉を聞いたことがある人は多いと思います。今日の話の主題はこのプラトーです。
プラトーとは、探索空間のうち、どっちに行っても $h$ 値、ゴールまでの推定距離が改善しないような場所のことです。自分のいまいる周囲しか見ることの出来ない局所探索アルゴリズム、たとえば山登り法やEHCは、このような場所では立ち往生 (stack) してしまいます。どの方向に行ってもなかなか自分よりもよい $h$ 値のノードが見つからないからです。
このような時、の局所探索の挙動をHCとEHC、そして今回紹介するLeast Bad Searchで比べてみましょう。
- HC --- 探索を諦める。
- EHC --- プラトーでは幅優先探索に移行、よいノードが見つかったらHCに戻る
- least bad search --- プラトーではBFS に移行、よいノードが見つかったらHCに戻る
これだけの違いです。正直、なんで名前を変えたの?って感じですが、JAIR論文になっているので紹介しました。(Least Bad Search の内容はJAIR論文の内容のほんの一部なので、論文自体の価値はべつに低くないと思います)
LBSは、EHCと比べてプラトーでの挙動を改善します。LBSがプラトーで用いるBFSは $h$ 値の小さいものから順に探索を行うため、調べるノードの数が少なくてすみ、かつ見つかる Plateau Exit の質がよくなるというものです。Plateau Exit とは、Plateau の開始地点 (Plateau Entrance) よりも $h$ 値の改善される始めての探索ノードを指します。(図は (Coles '04) より。)
まとめ
あんまり内容がありませんが、Least Bad Search について解説しました。