プランニング領域定義言語 - 百科事典

計画領域定義言語（PDDL）は、人工知能（AI）の計画言語を標準化しようとする試みです。1998年にDrew McDermottとその同僚たちによって初めて開発され、主に1998年/2000年国際計画競争（IPC）を可能にすることを目的としていました。そして、各競争ごとに進化してきました。PDDLが提供する標準化は、研究をより再利用可能で簡単に比較可能にする利点がありますが、領域固有のシステムに対して若干の表現能力の犠牲が必要です。

概要
PDDLは、自動計画の問題に対する人間が読みやすい形式で、世界の可能な状態の説明、可能なアクションのセットの説明、世界の特定の初期状態、特定の目標のセットを提供します。アクションの説明には、アクションの前提条件と効果が含まれます。PDDLは計画問題のモデルを2つの主要な部分に分離します：問題の説明には初期状態と達成すべき目標が含まれます。以下の例では、2本のグリッパーを持つロボットの自動計画のための領域定義と問題の説明インスタンスが示されています。PDDLは計画ソフトウェアの入力となりますが、通常は領域独立のAI計画ソフトウェアです。PDDLは計画ソフトウェアの出力を説明しませんが、出力は通常、完全または部分的に順序付けられた計画であり、それがアクションのシーケンスで、その一部が並列に実行されることがあります。

PDDL言語は、スタンフォード研究所問題解決者（STRIPS）やアクション説明言語（ADL）などの他のものにインスパイアされています。PDDL言語は、オントロジーを作成するために使用される知識表現言語の原理を使用しており、例えばウェブオントロジー言語（OWL）があります。オントロジーは、分類と分類ネットワークを形式化する形式的方法であり、本質的に、さまざまな領域の知識の構造を定義します：オブジェクトのクラスを表す名詞と、オブジェクト間の関係を表す動詞です。PDDL言語はまた、オブジェクト指向プログラミング（OOP）の原理を使用しており、領域の説明には比較的固定されたオブジェクトタイプの階層がありますが、問題の説明は計画問題ごとに異なります。つまり、オブジェクトのインスタンスのデータのように、問題の説明は異なります。

最新バージョンのPDDLは、PDDL 3.1のBNF（Backus-Naur形式）構文定義で説明されています。PDDLを使用する方法に関するオンラインリソースがいくつかあります。また、本もあります。

PDDLの実際の公式バージョン
= PDDL1.2 =
1998年と2000年の1回目と2回目のIPCの公式言語でした。計画問題のモデルを2つの主要な部分に分離しました：このモデルの分割により、以下の要素が直感的に分離できます。（1）問題領域の特定の問題に常に存在する要素（これらの要素は領域説明に含まれます）、および（2）特定の計画問題を決定する要素（これらの要素は問題説明に含まれます）。したがって、同じ領域説明に複数の問題説明が関連できます（例えば、OOP（オブジェクト指向プログラミング）やOWL（ウェブオントロジー言語）のクラスに複数のインスタンスが存在するのと同じです）。したがって、領域と接続された問題説明が計画問題のPDDLモデルを形成し、最終的にはこれが計画ソフトウェア（通常は領域独立のAI計画ソフトウェア）の入力となります。このソフトウェアは、適切な計画アルゴリズムを使用して、与えられた計画問題を解決することを目指しています。計画の出力はPDDLによって指定されませんが、通常、完全または部分的に順序付けられた計画（アクションのシーケンス）で、その一部が時には並列に実行されることがあります。

= PDDL2.1 =
2002年の第3回IPCの公式言語でした。数値フロント（例えば、燃料レベル、時間、エネルギー、距離、重量などの非二値リソースをモデル化するために使用されます）、計画メトリクス（計画の定量評価を許可し、ただゴール駆動だけでなく、ユーティリティ駆動の計画、つまり最適化、メトリック最小化/最大化も許可します）、そして持続的/連続的なアクション（変数、非断片的な長さ、条件、効果を持つ可能性があります）を導入しました。最終的には、PDDL2.1は言語の元のバージョンよりも多くの実際の問題を表現および解決可能にしました。

= PDDL2.2 =
2004年の第4回IPCの確定性トラックの公式言語でした。導出された述語（例えば、AがBから達成可能で、BがCから達成可能である場合、AはCから達成可能である（伝達性）とするための他の事実からの依存関係をモデル化するために使用されます）と時刻初期リテラル（計画実行から独立して特定の時間に発生する外生的なイベントをモデル化するために使用されます）を導入しました。最終的には、PDDL2.2は数少ない重要な要素を言語に追加しましたが、PDDL1.2からPDDL2.1への進化に比べて革命的な進化ではありませんでした。

= PDDL3.0 =
2006年の第5回IPCの確定性トラックの公式言語でした。状態軌道制約（計画の実行中に生成される状態軌道に対して真であるべきモダル論理表現の形で表されるハード制約）と好み（論理表現の形で表されるソフト制約、ハード制約と同様に、その満足度は必要ではありませんが、例えば満足度の高い計画の質を測るために計画メトリックに組み込むことができます）を導入しました。これにより、好みに基づく計画を可能にしました。最終的には、PDDL3.0は言語の表現能力を更新し、計画における最近の重要な進展に対応することができます。

= PDDL3.1 =
2008年と2011年の第6回と第7回IPCの確定性トラックの公式言語でした。オブジェクトフロント（つまり、関数の範囲は数値（整数または実数）だけでなく、任意のオブジェクトタイプでもなることがあります）を導入しました。これにより、PDDL3.1は文法的に小さなが意味的には非常に重要な表現能力の変更を通じて、現代の期待に応えました。

現在の状況
最新バージョンの言語はPDDL3.1です。PDDL3.1のBNF（Backus-Naur形式）構文定義は、IPC-2011ホームページやIPC-2014ホームページのリソースの中に見つけることができます。

PDDLの後継者/バリエーション/拡張
= PDDL+ =
PDDL2.1のこの拡張は、約2002年から2006年に提供され、自律プロセスとイベントの使用を通じて連続的な変化のモデルをより柔軟にしました。この拡張が提供する鍵は、エージェントの行動とエージェントの環境によって引き起こされる変化との相互作用をモデル化する能力です。プロセスは時間を通じて実行され、数値の連続的な効果を持ちます。プロセスはエージェントの直接的な行動によって開始および終了されるか、環境で引き起こされるイベントによって開始および終了されます。この3つの構造は「開始プロセス停止モデル」と呼ばれます。論理的および数値の状態の区別がなされます：論理的状態間の遷移は瞬間的であると仮定され、特定の論理的状態の占領は時間を通じて持続することができます。したがって、連続的な更新式はプロセス効果の中でのみ発生することが制限されます。瞬間的なアクションとイベントは、断片的な変化の表現に制限されます。これにより、以下に示す連続的な変化の期間の3つの構造が導入されます：コメント：計画の目標は、活動プロセスが停止される前に達成される可能性があります。

= NDDL =
NDDL（New Domain Definition Language）は、約2002年にNASAがPDDLに対して作成しました。その表現はPDDLとはいくつかの点で異なります：この点で、NDDLのモデルはPDDLモデルよりもSATエンコーディングの計画問題のスキーマに似ています。このような違いにより、NDDLを使用すると計画と計画の実行（例えば、重要な宇宙船ミッション中）がより堅牢になることがありますが、PDDL以外の標準的な計画問題の表現に対する対応は、PDDLよりもずっと直感的ではありません。

= MAPL =
MAPL（Multi-Agent Planning Language、マップルと発音）は、約2003年にPDDL2.1から拡張されました。これは元の言語の相当な修正です。非宣言的状態変数（例えば、n-aryである可能性があります：true、false、unknown、または他のもの）を導入し、モダル演算子（before、afterなど）で与えられた時空モデルを導入しました。PDDL3.0では、もっと徹底的な時空モデルが与えられ、元のPDDL構文（ただし、オプションの追加として）と互換性があります。MAPLは、実行時で決定されるアクションの持続時間と明示的な計画同期を導入しました。これらの仮定は人工的である可能性があり、同時計画を実行するエージェントがコミュニケーションを取る必要がないと仮定されています。最後に、MAPLはアクション（内生的および外生的）を導入し、アクションの並列性を処理するために使用されます。これにより、イベントは計画の一部として明示的に成り立ち、制御関数によってエージェントに割り当てられます。これは計画の一部でもあります。

= OPT =
OPT（Ontology with Polymorphic Types）は、約2003年から2005年にDrew McDermottによってPDDL2.1を拡張しました。これは計画領域に関する計画アプリケーションが推論するために定義される形式化された概念フレームワークを作成するための一般的な記号を作成する試みでした。その構文はPDDLに基づいていますが、もっと洗練された型システムが含まれており、ユーザーは高階構造（例えば、明示的なλ式を許可する効率的な型推論を可能にする）を使用することができます。例えば、オブジェクトが型（レベル0の型）を持つだけでなく、これらのオブジェクト上に定義された関数/フロントも型を持つことができます。これにより、OPTは基本的にはPDDL2.1とほぼ上互換で、プロセスや持続的なアクションの記号は主にPDDL+とPDDL2.1から借用されていますが、それ以外にも多くの重要な拡張（例えば、データ構造、非ボールルートフロント、アクションのリターン値、アクション間のリンク、階層的なアクション拡張、領域定義の階層、名前空間の使用など）が提供されます。

= PPDDL =
PPDDL（Probabilistic PDDL）1.0は、2004年と2006年の第4回と第5回IPCの確定性トラックの公式言語でした。確定性の効果（アクションの可能な効果に対する確率分布）、報酬フロント（計画の総報酬を増加または減少させるためにアクションの効果に含まれます）、目標報酬（少なくとも1つの目標状態を含む状態軌道を報酬するために使用されます）、そして目標達成フロント（状態軌道が少なくとも1つの目標状態を含む場合に真であるとする）をPDDL2.1に拡張しました。これにより、PPDDL1.0はMDP計画を実現しました。この場合、状態遷移には不確実性がありますが、環境は計画者/エージェントにとって完全に観察可能です。

= APPL =
APPL（Abstract Plan Preparation Language）は、2006年にNDDLの新しいバリエーションとして登場しました。これはPDDLやNDDLなどのほとんどの既存の計画言語よりも抽象的です。この言語の目的は、安全性の高いアプリケーション（例えば、パワーマネジメントや未来の有人宇宙船の自動接近）のための計画問題の形式的分析と特定を簡略化することです。APPLはNDDLと同じ概念を使用し、アクションの拡張や他のいくつかの概念を追加しましたが、それでもPDDLの表現能力よりもずっと低いです（堅牢性と形式確認を維持するために）。

= RDDL =
RDDL（Relational Dynamic influence Diagram Language）は、2011年第7回IPCの不確定性トラックの公式言語でした。概念的にはPPDDL1.0とPDDL3.0に基づいていますが、実際には文法的および意味的には完全に異なる言語です。部分観察性の導入は、PPDDL1.0に対するRDDLの最も重要な変更の一つです。すべてのもの（状態フロント、観察、アクション、...）を変数で表すことで、効率的にマルコフ決定過程（MDP）や部分観察マルコフ決定過程（POMDP）を記述することができます。この方法により、RDDLはPDDLから大きく逸脱します。基礎となるRDDLはPPDDL1.0と同様に動的ベイズネットワーク（DBN）に対応しますが、RDDLはPPDDL1.0よりも表現能力が高くなります。

= MA-PDDL =
MA-PDDL（Multi Agent PDDL）は、2012年に導入された最小限の、モジュール的なPDDL3.1の拡張であり、複数のエージェントによる計画を可能にします。この追加はPDDL3.1のすべての機能と互換性があり、MAPLのほとんどの問題を解決します。異なるエージェントの異なるアクション（つまり異なる能力）を区別する可能性を追加し、異なるエージェントが異なる目標と/またはメトリクスを持つ可能性も追加します。アクションの前提条件は、直接のアクション（例えば、他のエージェントのアクション）を直接参照することができます。したがって、相互作用効果を持つアクションを一般的で柔軟な方法で表現できます（例えば、少なくとも2つのエージェントが必要で、重いテーブルを空中に持ち上げるリフトアクションを実行しないとテーブルは地面に残る場合があります（これは構造的シンエラージーですが、破壊的シンエラージーも簡単に表現できます））。さらに、シンタックスの甘いメカニズムとして、アクション、目標、メトリクスの継承とポリモーフィズムの簡単なメカニズムもMA-PDDLに導入されました（:typingが宣言されている場合を仮定）。PDDL3.1は環境が確定性で完全に観察可能であると仮定しており、MA-PDDLも同じように、すべてのエージェントがすべての状態フロントの値にアクセスし、すべてのエージェントの以前に実行されたアクションを観察し、エージェントの並列アクションが環境の次の状態を明確に決定することを仮定しています。これは後に部分観察性と確率効果の追加（それぞれはPPDDL1.0にインスパイアされたものであり、言語のすべての前の機能と互換性があります）によって改善されました。

例
これは2本のグリッパーを持つロボットの自動計画のためのSTRIPSインスタンスの領域定義です。

そして、前述の領域定義を2つの部屋と2つのボールを持つ具体的な環境でインスタンス化する問題の定義です。

参考文献