プランニンググラフとヒューリスティクス

プランニンググラフとドメイン非依存ヒューリスティクスは、到達可能性をコンパクトに分析し、状態から目標までの距離を自動的に推定することで、古典的プランニングを高速化した技術です。

Definition

プランニンググラフは、到達可能性を近似するために、命題レベルとアクションレベルをmutex制約と交互に配置した階層構造です。プランニングヒューリスティクスは、しばしばこのような構造や削除緩和された問題から計算される関数であり、ある状態から目標に到達するまでのコストを推定します。

Scope

このトピックでは、Graphplanによって導入されたプランニンググラフのデータ構造について説明します。これには、命題とアクションのレベル、およびどの事実とアクションが共起できないかを捉える相互排他（mutex）関係が含まれます。また、現代のヒューリスティック探索プランナーを駆動する、緩和された問題（特に削除効果を無視する）から導出されるドメイン非依存ヒューリスティクスのファミリーについても扱います。到達可能性情報がどのように計算され、探索の指針としてどのように使用されるかについて述べます。基礎となる古典的プランニングモデルは、関連トピックで扱われます。

Core questions

• プランニンググラフは、到達可能な命題とアクションをレベルごとにどのように表現しますか？
• mutex関係とは何ですか、またそれらは事実とアクション間の非互換性をどのように捉えますか？
• 削除緩和は、許容可能または情報量の多いプランニングヒューリスティクスを導出するためにどのように使用されますか？
• これらのヒューリスティクスは、プランニングを効率的なヒューリスティック探索にどのように変えますか？

Key concepts

• プランニンググラフ
• 命題とアクションのレベル
• 相互排他（mutex）
• Graphplan
• 削除緩和
• h-maxおよびh-addヒューリスティクス
• FFヒューリスティックと緩和計画
• ヒューリスティック順方向探索

Key theories

プランニンググラフとGraphplan

Graphplanは、各レベルでどの命題とアクションが到達可能か、どのペアが相互排他的であるかをコンパクトに符号化するプランニンググラフを構築し、この構造を逆方向に探索することで計画を抽出し、プランニングを劇的に高速化します。

削除緩和ヒューリスティクス

アクションの削除効果を無視すると、はるかに簡単に解決できる緩和されたプランニング問題が得られます。この緩和の解決コストは、順方向探索を導く情報量の多い、しばしば許容可能なヒューリスティクス（h-max、h-add、FFヒューリスティクスなど）を提供します。

ヒューリスティック探索プランニング

最先端の古典的プランナーは、自動的に導出されたヒューリスティクスと最良優先探索または貪欲探索、および優先オペレータなどの強化を組み合わせることで、多様なドメインで強力な汎用性能を達成しています。

Clinical relevance

プランニンググラフと削除緩和ヒューリスティクスは、ロボット工学、ロジスティクス、自律制御で使用される競技会で優勝したプランナーの中核技術であり、ドメイン非依存プランナーが手作業による探索ガイダンスなしに大規模な問題を迅速に解決することを可能にします。

History

BlumとFurstのGraphplan（1995年、ジャーナル版1997年）はプランニンググラフを導入し、プランニング速度に革命をもたらしました。1990年代後半から2000年代にかけて、削除緩和ヒューリスティクスが台頭し、FFプランナー（HoffmannとNebel、2001年）、そして後のFast Downward（Helmert、2006年）が、ヒューリスティック順方向探索を支配的なアプローチとして確立しました。

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

プランニンググラフにおけるmutexとは何ですか？

mutex（相互排他）関係は、両方が同じレベルで成立または適用できない2つの命題または2つのアクションをマークします。例えば、あるアクションが別のアクションの前提条件を削除する場合などです。Mutexは、プランニンググラフを真の到達可能性のより厳密な近似にします。

削除効果を無視することが有用なヒューリスティックを与えるのはなぜですか？

削除効果がない場合、ある目標を達成しても別の目標が元に戻ることはないため、緩和された問題ははるかに解決しやすく、元の問題よりも難しくなることはありません。したがって、緩和された計画のコストは、実際のコストの下限または情報に基づいた推定値となり、探索を導く効果的なヒューリスティックとなります。