6Q-8
貪欲的でない最良優先探索の提案と解析
○今井達也，岸本章宏（東工大）
人工知能エージェントの古典的プランニング問題は
グラフ上の経路探索問題に帰着して解くことができる．
近年では，ヒューリスティック関数によって探索ノードから
ゴールまでの距離を見積もり，見積の小さい順にノードを展開していく
貪欲最良優先探索アルゴリズムがよく用いられている．
本研究は，不正確な見積を元にした貪欲的な探索が
非効率なノード展開を生じさせうることを明らかにした．
また，この問題を回避する貪欲的でない最良優先探索アルゴリズムを提案し，
実験的な性能評価を行った．