非決定プランニングでの探索手法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/16 01:19 UTC 版)
「自動計画」の記事における「非決定プランニングでの探索手法」の解説
非決定的プランニングに対する古典的な探索アルゴリズムの代表的なものに、Value IterationおよびAO*アルゴリズムがある。Value Iterationはヒューリスティクスを用いない知識なし探索であるため、ダイクストラ法の非決定的プランニングへの拡張と捉えることができる。この理解のもとでは、AO*はValue Iterationにヒューリスティクスを足した知識有り探索版であり、またA*を非決定的プランニングに拡張したものとも捉えられる。ダイクストラやA*と同様、AO*は、許容的ヒューリスティック関数(厳密な下界関数)を用いれば最適ポリシーを発見できる。これらのアルゴリズムは確率的プランニングにも同様に適用できる。 非決定的プランニングのうち、解ポリシーにループを含む必要がある場合(すなわち、ポリシーが非DAGとなる場合)AO*は適切な解を生成しない。この点を改善したのがLAO*である。 非決定的環境に対する確率的探索アルゴリズムの代表的なものとして、モンテカルロ木探索(MCTS)がある。確率的アルゴリズムであること(アルゴリズムが乱択に基づくこと)と、環境の振る舞い(アクション)が確率的であることは別の概念であることに注意したい。確率的アルゴリズムであるMCTSは、時間を無限大にとる極限では最適解に収束するが、実時間ではこれは保証されない。
※この「非決定プランニングでの探索手法」の解説は、「自動計画」の解説の一部です。
「非決定プランニングでの探索手法」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- 非決定プランニングでの探索手法のページへのリンク
