プランニングの基本的な考え方はすでに理解されていると思います。hMax 、hAdd、およびhFFアルゴリズムは、現在占有されている状態を基準にして、計画グラフ上の特定の状態のヒューリスティック値を計算するために使用されます。
3 つのアルゴリズムはすべて、問題の緩和されたバージョンを考慮することで機能します。具体的には、該当する各アクションの削除リストを削除することで緩和されたバージョンです。この効果は、アトムが達成される (true になる) と、達成されたままになると要約できます。
hMaxとhAddは非常によく似た方法で機能します。2 つのアルゴリズムは、計画グラフの状態を考慮し、該当するすべてのアクションを使用してその状態のすべてのアトムを真にすることで機能します。すべてのアトムを真にするために必要なアクションのコストは、それらが生成するヒューリスティック値の基礎です。
hAddの場合、特定の状態のヒューリスティックは、その状態のすべてのアトムを達成するための合計コストです。
hMaxの場合、特定の状態のヒューリスティックは、その状態で最も高価なアトムのコストです。
どちらのアルゴリズムも実際には緩和された問題を解決しないことに注意してください。現在の状態と比較して、特定の状態を達成するのがどれほど難しいかを推定するだけです。
hMax は許容されますが、 hAdd は許容されません。
hFFは、緩和された問題を実際に解決するため、異なります。最適な解決策 (以下の † を参照) を見つけようとするのではなく、合理的な解決策を見つけようとします。
与えられた状態 ( sと呼びましょう) のヒューリスティックを決定するために、hFFは現在の状態から与えられた状態への解を緩和された計画(π(s)と呼ばれることが多い) で見つけます。その解が見つかると、状態sに与えられるヒューリスティック値は、緩和された解のアクションの数になります。これは次のように記述できます。
h(s) = |π(s)|
hFFは、緩和計画 hと呼ばれることもあります。認められませんが、参考にはなります。
緩和された計画で解を見つけるために使用される方法は、hFFアルゴリズムの実装によって異なります。
† hFFは最適解を見つけようとはしません。元の問題を計画するよりも簡単ですが、最適解を計算することは、状態ごとに計算する必要があるため、ヒューリスティックとして使用するには依然として難しすぎるためです。代わりに、計算コストがはるかに低い合理的な計画を見つけようとします。
これがお役に立てば幸いです。これ以上混乱させないようお願いいたします。
私はまた、自分が正しいことを心から望んでいます - 私は自分が正しいと比較的自信を持っていますが、修正されることに対して完全にオープンです.これをAI講師に確認してもらい、これが正しいと確信しました。