グラフプラン

Graphplan は、 1995 年にAvrim Blumと Merrick Furstによって開発された自動計画アルゴリズムです。Graphplanは、 STRIPSで表現された計画問題を入力として受け取り、可能であれば、目標状態に到達するための一連の操作を生成します。

グラフプランという名前は、新しい計画グラフを使用することにより、状態空間グラフの単純な探索からソリューションを見つけるために必要な検索の量を削減することに由来しています。

状態空間グラフでは:

• ノードは可能な状態であり、
• エッジは特定のアクションによる到達可能性を示します。

一方、Graphplanの計画グラフでは次のようになります。

• ノードはアクションと原子事実であり、交互のレベルに配置されています。
• エッジには 2 種類あります。
  1. 原子的事実からそれが条件となる行動まで、
  2. 行為から、それが真か偽かを判断する原子的事実まで。

最初のレベルには、初期状態を識別する真の原子事実が含まれています。

同時に真になることができない互換性のない事実と、一緒に実行できない互換性のないアクションのリストも維持されます。

次に、アルゴリズムは計画グラフを反復的に拡張し、長さ l-1 のソリューションが存在しないことを証明してから、後方連鎖によって長さl の計画を探します。目標が真であると仮定すると、Graphplan は目標に到達できるアクションと以前の状態を探し、非互換性情報を利用して可能な限り多くを削除します。

計画に密接に関連するアプローチは、満足度としての計画 ( Satplan ) です。どちらも、自動計画の問題を軽減して、異なる固定期間の長さの計画を検索します。

• A. Blum および M. Furst (1997)。「プランニング グラフ分析による高速プランニング」。人工知能。90:281-300。

• Avrim Blum の Graphplan ホームページ
• PLPLAN: Java GraphPlan 実装
• NPlanner: .NET GraphPlan 実装 2013-12-31 にWayback Machineにアーカイブされました
• Emplan と JavaGP: Graphplan の C++ および Java 実装
• GraphPlan と計画グラフの作成に関する MIT OpenCourseWare 講義