計画ドメイン定義言語

計画ドメイン定義言語( PDDL ) は、人工知能 (AI) 計画言語を標準化する試みです。^{[1]これは、1998 年に}Drew McDermott 氏とその同僚によって最初に開発され、主に 1998/2000国際計画コンペティション(IPC) を可能にするために使用され、その後、各コンペティションで進化しました。PDDL によって提供される標準化には、ドメイン固有のシステムと比較して表現力が多少犠牲になりますが、研究の再利用性と比較が容易になるという利点があります。^[2]

PDDL は、自動計画の問題のための人間が読める形式であり、世界の可能な状態の説明、可能なアクションのセットの説明、世界の特定の初期状態、および望ましい目標の特定のセットを提供します。アクションの説明には、アクションの前提条件とアクションの効果が含まれます。PDDL は、計画問題のモデルを 2 つの主要部分に分割します。(1) 問題ドメインのすべての問題に存在する要素のドメインの説明、および (2) 特定の計画問題を決定する問題の説明です。問題の説明には、初期状態と達成すべき目標が含まれます。次の例は、2 つのグリッパ アームを備えたロボットの自動計画のドメイン定義と問題の説明のインスタンスを示しています。

PDDL は、通常、ドメインに依存しない人工知能 (AI) プランナーであるプランナー ソフトウェアへの入力になります。PDDL はプランナー ソフトウェアの出力を記述しませんが、出力は通常、完全にまたは部分的に順序付けられたプランであり、これは一連のアクションであり、その一部は並列​​に実行される場合があります。

PDDL 言語は、スタンフォード研究所問題解決ツール(STRIPS) やアクション記述言語(ADL) などからヒントを得ました。PDDL 言語は、オントロジーの作成に使用される知識表現言語の原理を採用しています。例としては、Web オントロジー言語(OWL) があります。オントロジーは、分類法や分類ネットワークを記述する正式な方法であり、基本的にさまざまなドメインの知識の構造を定義します。名詞はオブジェクトのクラスを表し、動詞はオブジェクト間の関係を表します。

PDDLの最新バージョンは、 PDDL 3.1のBNF（バッカス・ナウア記法）構文定義で説明されています。^[3] PDDLの使い方については、いくつかのオンラインリソースが利用可能であり、^{[1] [4] [5] [6] [7]}書籍もあります。^[8]

これは、1998 年の第 1 回 IPC と 2000 年の第 2 回 IPC の公式言語でした。^[9] これは、計画問題のモデルを(1) ドメイン記述と(2)関連する問題記述の 2 つの主要部分に分離しました。このようなモデルの分割により、(1)問題ドメインのあらゆる特定の問題に存在する要素 (これらの要素はドメイン記述に含まれています) と、(2)特定の計画問題を決定する要素 (これらの要素は問題記述に含まれています) を直感的に分離できます。したがって、複数の問題記述が同じドメイン記述に接続される場合があります (たとえば、 OOP (オブジェクト指向プログラミング)またはOWL (Web オントロジー言語)のクラスの複数のインスタンスが存在する場合と同様です)。このように、ドメインとそれに関連する問題記述によって計画問題の PDDL モデルが形成され、最終的にこれがプランナー (通常はドメインに依存しない AI プランナー) ソフトウェアの入力となり、適切な計画アルゴリズムを使用して特定の計画問題を解決します。プランナーの出力はPDDL によって指定されませんが、通常は完全にまたは部分的に順序付けられたプラン(アクションのシーケンス。その一部は並列​​で実行される場合もあります) になります。では、PDDL1.2 ドメインと問題記述の一般的な内容を見てみましょう...
(1)ドメイン記述は、ドメイン名の定義、要件の定義(PDDL モデルが実際に使用しているモデル要素をプランナーに宣言するため)、オブジェクト タイプ階層の定義 ( OOPのクラス階層と同様)、定数オブジェクトの定義(ドメイン内のすべての問題に存在する)、述語の定義(論理的事実のテンプレート)、および可能なアクションの定義(実行中にグラウンディング/インスタンス化されるパラメーター付きの演算子スキーマ) で構成されます。アクションには、パラメーター(オブジェクトでインスタンス化できる変数)、前提条件、および効果があります。アクションの効果は条件付き (when-effects) になることもあります。
(2)問題記述は、問題名の定義、関連するドメイン名の定義、すべての可能なオブジェクト(論理ユニバース内のアトム) の定義、初期条件で構成されます。(計画環境の初期状態、真/偽の事実の結合)、および目標状態の定義(計画環境の目標状態で真/偽であるべき事実の論理式)。このようにして、最終的に PDDL1.2 は、決定論的な単一エージェントの離散的かつ完全にアクセス可能な計画環境の「物理」を捉えました。

これは2002年の第3回IPCの公式言語でした。 [ ^10]数値流暢性（燃料レベル、時間、エネルギー、距離、重量などの非バイナリリソースをモデル化するためなど）、計画メトリック（計画の定量評価を可能にし、目標駆動型だけでなく、ユーティリティ駆動型の計画、つまり最適化、メトリックの最小化/最大化を可能にする）、および持続的/継続的なアクション（可変で非離散的な長さ、条件、および効果を持つことができる）が導入されました。最終的にPDDL2.1では、元のバージョンの言語よりも多くの現実の問題の表現と解決が可能になりました。

これは、2004 年の第 4 回 IPC の決定論的トラックの公式言語でした。^[11]導出述語(特定の事実と他の事実の依存関係をモデル化します。たとえば、A が B から到達可能で、B が C から到達可能な場合、A は C から到達可能です (推移性))、および 時間指定初期リテラル(プラン実行とは無関係に特定の時間に発生する外生イベントをモデル化します) が導入されました。最終的に、PDDL2.2 はいくつかの重要な要素を追加して言語を拡張しましたが、PDDL1.2 以降の PDDL2.1 と比較して劇的な進化ではありませんでした。

これは、2006 年の第 5 回 IPC の決定論的トラックの公式言語でした。^{[12] [13] [14]}状態軌道制約(様相論理表現形式のハード制約。計画の実行中に生成される状態軌道に当てはまる必要があり、計画の問題の解決策となる) と 設定(論理表現形式のソフト制約。ハード制約に似ているが、必ずしも満たす必要はないが、満たされる設定の数を最大化するため、または計画の品質を測定するためだけに、計画メトリックに組み込むことができる) を導入し、設定ベースの計画を可能にしました。最終的に、PDDL3.0 では、計画における最近の重要な開発に対応できるように、言語の表現力が更新されました。

これは、2008年と2011年にそれぞれ開催された第6回IPCと第7回IPCの決定論的トラックの公式言語でした。^{[15] [16] [17]}オブジェクトフルエント（つまり、関数の範囲は数値（整数または実数）だけでなく、任意のオブジェクト型も可能）を導入しました。したがって、PDDL3.1は、構文的には小さいように見えますが、意味的には非常に重要な表現力の変更により、言語を現代の期待にさらに適合させました。

この言語の最新バージョンは PDDL3.1 です。PDDL3.1のBNF (Backus-Naur Form)構文定義は、IPC-2011 ホームページまたは IPC-2014 ホームページのリソース内にあります。

2002年から2006年頃のPDDL2.1のこの拡張は、自律的なプロセスとイベントの使用を通じて、継続的な変化のより柔軟なモデルを提供します。^{[2] [18]} この拡張が提供する鍵は、エージェントの行動とエージェントの環境によって開始される変化との間の相互作用をモデル化する機能です。プロセスは時間の経過とともに実行され、数値に継続的な影響を及ぼします。それらは、エージェントの直接アクションによって、または環境でトリガーされたイベントによって開始および終了します。この3つの部分からなる構造は、開始-プロセス-停止モデルと呼ばれます。論理状態と数値状態は区別されます。論理状態間の遷移は瞬間的であると見なされますが、特定の論理状態の占有は時間の経過に伴って持続する場合があります。したがって、PDDL +では、継続的な更新表現はプロセス効果でのみ発生するように制限されます。瞬間的なアクションとイベントは、離散的な変化の表現に制限されます。これは、前述の連続変化期間の 3 部構成のモデリングを導入します。(1)アクションまたはイベントが、プロセスによって表現される数値変数の連続変化期間を開始します。(2)プロセスが数値変数の連続変化を実現します。(3)アクションまたはイベントが最終的にプロセスの実行を停止し、数値変数への影響を終了します。コメント: アクティブなプロセスが停止される前に、計画の目標が達成される可能性があります。

NDDL（New Domain Definition Language ）は、2002年頃からNASAがPDDLに応えて作ったものです。 [ 19 ] [ ^{20 ]} その表現はPDDLとはいくつかの点で異なります。1)命題論理や一階述語論理ではなく、変数/値表現（タイムライン/アクティビティ）を使用する、2) 状態やアクションの概念がなく、間隔（アクティビティ）とそれらのアクティビティ間の制約のみがある、などです。この点で、NDDLのモデルは、PDDLモデルというよりも、計画問題のSATエンコードのスキーマに似ています。前述の違いにより、NDDLを使用すると計画の計画と実行（たとえば、重要な宇宙ミッション中）がより堅牢になる可能性がありますが、PDDL以外の標準的な計画問題表現との対応は、PDDLの場合よりもはるかに直感的ではない可能性があります。

MAPL (マルチエージェントプランニング言語、「メイプル」と発音)は、2003 年頃からの PDDL2.1 の拡張です。 ^[21] これは、元の言語のかなり重大な変更です。非命題状態変数 (n 項: true、false、unknown、またはその他の任意の値) が導入されています。また、様相演算子 (before、after など) で与えられる時間モデルが導入されています。しかし、PDDL3.0 では、元の PDDL 構文とも互換性のある、より徹底した時間モデルが与えられました (オプションの追加機能にすぎません)。MAPL では、実行時に期間が決定されるアクションと、エージェント間の音声行為に基づく通信によって実現される明示的なプラン同期も導入されています。同時実行プランを実行するエージェントは、マルチエージェント環境で機能できるように必ずしも通信する必要はないため、この仮定は不自然である可能性があります。最後に、MAPL では、アクションの同時実行性を処理するためにイベント (内生的および外生的)が導入されています。したがって、イベントは明示的に計画の一部となり、計画の一部でもある 制御機能によってエージェントに割り当てられます。

OPT（多形性型オントロジー）は、2003年から2005年頃にドリュー・マクダーモットによってPDDL2.1の大幅な拡張版として考案されました（PDDL+といくつかの類似点があります）。 ^[22] これは、計画アプリケーションが推論する計画ドメインの形式化された概念フレームワークとして定義されたオントロジーを作成するための汎用表記法を作成する試みでした。その構文は PDDL に基づいていましたが、はるかに複雑な型システムがあり、ユーザーは明示的なλ 式などの高階構造を使用して効率的な型推論を行うことができました (つまり、ドメイン オブジェクトに型 (レベル 0 の型)があるだけでなく、これらのオブジェクトの上に定義された関数/関数にも任意のマッピングの形式の型 (レベル 1 の型) があり、これはジェネリックにすることができるので、そのパラメーター (ジェネリック マッピングのドメインと範囲) を変数で定義でき、さらに高いレベルの型 (レベル 2 の型) を持つことができます。言うまでもなく、マッピングは任意であり、つまり、関数 (述語、数値関数など) のドメインまたは範囲は、任意のレベル 0/1/2 の型にすることができます。たとえば、関数は任意の関数から任意の関数にマッピングできます...)。 OPT は基本的に、PDDL2.1 と (ほぼ) 上位互換性を持つことが意図されていました。プロセスと持続アクションの表記法は主に PDDL+ と PDDL2.1 から借用されましたが、それ以外にも OPT は多くの重要な拡張機能を提供しました (例:データ構造、非ブール型のフルーエント、アクションの戻り値、アクション間のリンク、階層的なアクション拡張、ドメイン定義の階層、セマンティック ウェブとの互換性のための名前空間の使用)。

PPDDL（確率的PDDL）1.0は、2004年と第5回IPCの確率トラックの公式言語で、それぞれ2006年と2007年に開催されました。^[23] PPDDL2.1を、確率的効果（アクションの可能な効果に関する離散的な一般確率分布）、報酬フルーエント（アクションの効果で計画の総報酬を増減させる）、目標報酬（少なくとも1つの目標状態を組み込んだ状態軌道に報酬を与える）、目標達成フルーエント（状態軌道に少なくとも1つの目標状態が組み込まれている場合に真となる）で拡張しました。最終的にこれらの変更により、PPDDL1.0は、状態遷移に不確実性がある可能性があるが、環境はプランナー/エージェントにとって完全に観測可能なマルコフ決定プロセス（MDP）計画を実現できるようになりました。

APPL (抽象計画計画言語) は、2006 年に登場した NDDL の新しい変種で、 PDDL や NDDL などの既存のほとんどの計画言語よりも抽象度が高くなっています。^[24] この言語の目的は、将来の有人宇宙船の電力管理や自動ランデブーなど、安全性が重視されるアプリケーションを対象とした計画問題の形式分析と仕様指定を簡素化することでした。APPL は、アクションの拡張とその他の概念を含め、NDDL と同じ概念を使用していますが、表現力は PDDL よりもはるかに劣っています (堅牢性と形式検証可能性を維持するため)。

RDDL（リレーショナル・ダイナミック・インフルエンス・ダイアグラム言語）は、2011年の第7回IPCの不確実性トラックの公式言語でした。^[25] 概念的にはPPDDL1.0とPDDL3.0に基づいていますが、実際には構文的にも意味的にも完全に異なる言語です。部分観測の導入は、PPDDL1.0と比較したRDDLの最も重要な変更点の1つです。これにより、すべて（状態流暢性、観測、アクションなど）を変数で表すことで、マルコフ決定プロセス（MDP）と部分観測マルコフ決定プロセス（POMDP）を効率的に記述できます。このように、RDDLはPDDLから大きく離れています。グラウンデッドRDDLは、PPDDL1.0と同様に動的ベイジアンネットワーク（DBN）に対応しますが、RDDLはPPDDL1.0よりも表現力に優れています。

MA-PDDL （マルチエージェントPDDL）は、2012年に導入されたPDDL3.1の最小限のモジュール式拡張であり（つまり、新しい要件）、複数のエージェントによる、複数のエージェントのための計画を可能にします。[ 26 ^]この追加はPDDL3.1のすべての機能と互換性があり、MAPLの問題のほとんどに対処しています。異なるエージェントの異なる可能性のあるアクション（つまり、異なる機能）を区別する可能性が追加されました。同様に、異なるエージェントは異なる目標や測定基準を持つことができます。アクションの前提条件は、同時アクション（たとえば、他のエージェントのアクション）を直接参照できるようになったため、相互作用する効果を持つアクションを一般的で柔軟な方法で表現できます（たとえば、重いテーブルを空中に持ち上げるアクションを実行するには少なくとも2つのエージェントが必要であるとします。そうしないと、テーブルは地面に残ります（これは建設的な相乗効果の例ですが、破壊的な相乗効果もMA-PDDLで簡単に表現できます）。さらに、構文糖の一種として、アクション、目標、およびメトリックの継承と多態性のための単純なメカニズムも MA-PDDL に導入されました (が宣言されていると仮定)。PDDL3.1 では環境が決定論的で完全に観測可能であると仮定しているため、MA-PDDL でも同じことが当てはまります。つまり、すべてのエージェントは、すべての時点におけるすべての状態流暢性の値にアクセスでき、各エージェントの以前に実行されたすべてのアクションを観測でき、エージェントの同時アクションによって環境の次の状態が明確に決定されます。これは、部分観測性と確率的効果 (これも、それぞれ と という 2 つの新しいモジュール要件の形で、後者は PPDDL1.0 に触発され、 を含む言語の以前のすべての機能と互換性があります) の追加によって後に改善されました。^[27]:multi-agentlift:typing:partial-observability:probabilistic-effects:multi-agent

これは、2つのグリッパアームを備えたロボットの自動計画のためのSTRIPSインスタンスのドメイン定義です。 ^[28]

( define ( domain gripper-strips ) ( :predicates ( room ?r ) ( ball ?b ) ( gripper ?g ) ( at-robby ?r ) ( at ?b ?r ) ( free ?g ) ( carry ?o ?g )) ( :action move :parameters ( ?from ?to ) :precondition ( and ( room ?from ) ( room ?to ) ( at-robby ?from )) :effect ( and ( at-robby ?to ) ( not ( at-robby ?from )))) ( :action pick :parameters ( ?obj ?room ?gripper ) :precondition ( and ( ball ?obj ) ( room ?room ) ( gripper ?gripper ) ( at ?obj ?room ) ( at-robby ?room ) ( free ?gripper )) :effect ( and ( carry ?obj ?gripper ) ( not ( at ?obj ?room )) ( not ( free ?gripper )))) ( :action drop :parameters ( ?obj ?room ?gripper ) :precondition ( and ( ball ?obj ) ( room ?room ) ( gripper ?gripper ) ( carry ?obj ?gripper ) ( at-robby ?room )) :effect ( and ( at ?obj ?room ) ( free ?gripper ) ( not ( carry ?obj  
          
                      
   
     
      
                       
                       
      
                  
   
      
      
                       
                       
                        
                       
                       
       
                   
                  
   
      
      
                       
                       
                        
                       
       
                 
                   ?グリッパー)))))

これは、2 つの部屋と 2 つのボールがある具体的な環境で、前のドメイン定義をインスタンス化する問題定義です。

( define ( problem strips-gripper2 ) ( :domain gripper-strips ) ( :objects rooma roomb ball1 ball2 left right ) ( :init ( room rooma ) ( room roomb ) ( ball ball1 ) ( ball ball2 ) ( gripper left ) ( gripper right ) ( at-robby rooma ) ( free left ) ( free right ) ( at ball1 rooma ) ( at ball2 rooma )) ( :goal ( at ball1 roomb )))