HTNプランニングでのヒューリスティック関数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/01/16 01:19 UTC 版)
「自動計画」の記事における「HTNプランニングでのヒューリスティック関数」の解説
HTNプランニングをSTRIPSプランニング問題に直接変換することは可能だが、その際には問題サイズが指数的に大きくなってしまい、非実用的である。ただし、HTNプランニングのうち末尾再帰的(Tail-Recursive)な問題は、多項式時間でSTRIPSに変換することができる。実応用に使われるHTNプランニング問題の多くは、全体が末尾再帰的ではないにしろ、一部に末尾再帰的な要素が含まれているため、この問題を末尾再帰的に緩和した問題はもとの問題のよい下界を返すことが期待される。これに基づいて、HTNプランニングのヒューリスティクス関数として、HTNプランニングをSTRIPSに緩和して解く手法がある(Hierarchy Relaxation)。緩和の結果得られたSTRIPS問題は、既存のSTRIPSソルバによって解かれる(これはさらに削除効果緩和やランドマークによる多項式時間緩和問題を解くことで探索する)。
※この「HTNプランニングでのヒューリスティック関数」の解説は、「自動計画」の解説の一部です。
「HTNプランニングでのヒューリスティック関数」を含む「自動計画」の記事については、「自動計画」の概要を参照ください。
- HTNプランニングでのヒューリスティック関数のページへのリンク