実時間ヒューリスティック探索のロボット制御への応用

点击翻译按钮获取中文摘要

今年度は,実時間探索法の実問題適用に向けた検証をテーマに研究を行った.実問題においては,問題が大規模とならざるを得ない,という観点から,前年度作成したライブラリを用い,通常実時間探索法の学習性能測定に用いられる問題に比べ,より大規模な問題に適用し各種実時間探索法の性能評価を行った.特筆すべきは,筆者らの提案した,上界値を用いた実時間探索法(Upper-bounded LRTA*)の15パズルに対する効果で,比較対照としたLRTA*,FALCONSが40万節点展開後も1題も最適解を発見できなかったのに対し,Upper-bounded LRTA*は,32題の最適解を発見した.公正を期すために,LRTA*(FALCONS, Upper-bounded LRTA*に比べ,1節点あたり半分の記憶領域しか必要としない)については,80万節点展開するまで実験を続けたが,やはり1題も解くことはできなかった.実時間探索で15パズルの最適解を得た,という報告はこれまでない.また,あわせて,重みつき実時間探索においては,最適解の1.2倍の準最適解を17題で得ることができ,1.4倍まで許容すると51題,1.6倍では87題を解くことが可能であった.Upper-bounded LRTA*においては,上界値の伝播方法が問題になるが,これをオンラインに行う手法を新たに考案した.以上の,Upper-bounded LRTA*アルゴリズムに関する結果と,重みつき実時間探索に関する結果とをあわせて論文とし,Artificial Intelligence誌に採録が決定した.