アクション記述言語

人工知能において、アクション記述言語（ADL）は、特にロボットのための自動化された計画およびスケジュールシステムであり、 STRIPSの発展形と考えられています。エドウィン・ペドノー（データ抽象化およびモデリングの分野の専門家であり、1996年からIBMの研究員としてデータ抽象化研究グループに所属）が1987年にこの言語を提案しました^。これはアクション言語の一例です。

ペドノーは、 STRIPS の表現力は、演算子の効果を条件付きにすることで改善できると指摘しました。これが ADL-A の主要アイデアです。ADL-A は、ペドノーが提案した ADL の命題部分とほぼ同等であり、^[2] ADL-B は ADL-A の拡張です。ADL-B の拡張では、新しい種類の命題「静的法則」を導入することで、間接的な効果を伴うアクションを記述できます。ADL の 3 番目のバリエーションは ADL-C です。ADL-C は、命題を静的法則と動的法則に分類できる点で ADL-B に似ていますが、より特殊性があります。^[3]

プランニング言語の意味は、環境内の特定の条件を表現し、それに基づいて、目的の目標につながる一連のアクションを自動的に生成することです。目標とは、部分的に指定された特定の条件です。アクションを実行する前に、その前提条件を満たす必要があります。実行後、アクションは効果を生み出し、それによって環境が変化します。環境は、満たされるか満たされないかのいずれかになる特定の述語によって記述されます。

STRIPS とは対照的に、オープン ワールドの原則はADL に適用されます。つまり、条件に含まれないものはすべて未知です (偽であると想定されるのではなく)。さらに、STRIPS では肯定的なリテラルと接続詞のみが許可されますが、ADL では否定的なリテラルと論理和も許可されます。

ADL スキーマは、アクション名、オプションのパラメーター リスト、および Precond、Add、Delete、Update というラベルの付いた 4 つのオプションの句グループで構成されます。

Precond グループは、アクションを実行するための前提条件を定義する数式のリストです。セットが空の場合、値「TRUE」がグループに挿入され、前提条件は常に保持条件として評価されます。

追加条件と削除条件は、それぞれ追加グループと削除グループによって指定されます。各グループは、図 1 の左側の列に示されている形式の節のセットで構成されます。

1. Rは関係記号を表す
2. τ ₁ , ..., τ _{n は}項を表す
3. ψは式を表す
4. シーケンスz ₁、...、z _kは、項τ ₁、...、τ _nに現れる変数シンボルであるが、アクションスキーマのパラメータリストには現れない。
5. x ₁、...、x _{n は}変数z ₁、...、z _nとは異なる変数シンボルであり、 τ ₁、...、τ _n、ψ、またはアクションスキーマのパラメータリストには現れない。

更新グループは、関数シンボルの値を変更するための更新条件を指定するために使用されます。更新グループは、図 2 の左の列に示す形式の節のセットで構成されます。

ADL の正式な意味は 4 つの制約によって定義されます。

⇒ アクションは、世界に存在するオブジェクトのセットを変更しない可能性があります。これは、すべてのアクション α とすべての現在の状態/次の状態のペア( s、t ) ∈ aについて、 t の定義域がsの定義域と等しくなければならないことを意味します。

⇒ ADLにおけるアクションは決定論的である必要があります。( s , t ₁ )と( s , t ₂ )がアクション∃の現在の状態/次の状態のペアである場合、t ₁ = t ₂である必要があります。

⇒ 上で紹介した関数は、一階の式として表現可能でなければなりません。すべてのn項関係記号Rに対して、自由変数x ₂、...、x _nを持つ式Φ ^a _R ( x ₁、...、x _n )が存在し、 f ^a _R ( s )は次のように与えられます。

${\displaystyle t(R)=f_{R}^{a}(s)=(d_{1},\ldots ,d_{n})\in \operatorname {Dom} (s)^{n}\mid s[d_{1}/x_{1},\ldots ,d_{n}/x_{n}\models \Phi _{R}^{a}(x_{1},\ldots ,x_{n})]}$

したがって、アクション |= を実行した後、 F ( n ₁ , ..., x _n ) = yが真になるのは、Φ ^a _R ( x ₁ , ..., x _n , y )が事前に真だった場合のみです。この表現可能性の要件は、最初の制約 ( fのドメインはsのドメインと等しくなければならない) に依存していることに注意してください。

⇒ アクションが実行可能な状態の集合も、式として表現可能でなければならない。ADLで表現できるすべてのアクションαに対して、 ( s、t ) ∈αとなる状態tが存在する場合のみ、s |= Π _a^という性質を持つ式Πaが存在しなければならない（つまり、アクションαは状態sで実行可能である）。

計算効率の点では、ADLはSTRIPSと状況計算の間に位置づけられます。^[4] ADLの問題はすべてSTRIPSインスタンスに変換できますが、既存のコンパイル手法は最悪のケースでは指数関数的です。^[5]この最悪のケースは、プランの長さを多項式で保存する場合には改善できません。^[6]そのため、ADLは厳密にはSTRIPSよりも簡潔です。

ADL計画は依然としてPSPACE完全問題である。前提条件と効果が複雑な式であっても、アルゴリズムのほとんどは多項式空間である。^[7]

従来の計画に対する最も優れたアプローチのほとんどは、内部的に STRIPS のような表現を利用しています。実際、ほとんどのプランナー (FF、LPG、Fast-Downward、SGPLAN5、LAMA) は、まず ADL インスタンスを本質的に STRIPS インスタンス (条件付きまたは定量化された効果や目標なし) に変換します。

1. STRIPS 言語では、状態には肯定的なリテラルのみが許可されますが、ADL では肯定と否定の両方のリテラルがサポートされます。たとえば、STRIPS で有効な文は Rich ∧ Beautiful です。同じ文は、ADL では ¬Poor ∧ ¬Ugly と表現できます。
2. STRIPS では、言及されていないリテラルは偽です。これは、閉世界仮定と呼ばれます。ADL では、言及されていないリテラルは未知です。これは、開世界仮定として知られています。
3. STRIPSでは、目標にはグラウンドリテラルしか見つかりません。たとえば、Rich ∧ Beautifulです。ADLでは、目標に量化された変数が見つかります。たとえば、∃ x At (P1, x ) ∧ At(P2, x )は、ブロックの例でP1とP2を同じ場所にするという目標です。
4. STRIPS では、目標は接続詞です (例: (Rich ∧ Beautiful))。ADL では、目標には接続詞と選言 (Rich ∧ (Beautiful ∨ Smart)) が含まれる場合があります。
5. STRIPSでは効果は接続詞ですが、ADLでは条件付き効果が認められています。P : Eは、 Pが満たされる場合にのみEが効果であることを意味します。
6. STRIPS 言語は等価性をサポートしていません。ADL には等価性述語 ( x = y ) が組み込まれています。
7. STRIPS では型はサポートされていませんが、ADL ではサポートされています (たとえば、変数p  : Person)。

STRIPS 言語の表現力は、言語で記述できる数式セットの変換の種類によって制限されます。STRIPS 演算子を使用した数式セットの変換は、変換するセットからいくつかの数式を削除し、新しい数式を追加することによって行われます。特定の STRIPS 演算子では、追加および削除する数式は、変換するすべての数式セットで固定されています。その結果、STRIPS 演算子は、実行される状況によって結果が変わるアクションを適切にモデル化することはできません。一定時間発射されるロケットを考えてみましょう。軌道は、燃焼時間だけでなく、ロケットの速度、質量、方向によっても変化する可能性があります。追加および削除する必要がある数式は、変換する数式セットによって異なるため、STRIPS 演算子を使用してモデル化することはできません。^[8]

STRIPS言語を使用すると効率的な推論が可能になりますが、STRIPSの表現力は多くの現実世界のアプリケーションにおける動作のモデル化には適していないことが一般的に認識されています。この不十分さがADL言語の開発の動機となりました。^{[9] [10]} ADLの表現力と複雑さは、STRIPS言語と状況計算の中間にあります。その表現力は、上記のロケットの例を表現するのに十分ですが、同時に、効率的な推論アルゴリズムを開発できるほど制限されています。

ブロックの世界のより複雑なバージョンの例: ブロック A はブロック B と C の 2 倍の大きさである可能性があり、アクション xMoveOnto(B,A) は、On(A,C) がすでに true の場合に Clear(A) を否定する効果のみを持つか、ブロックのサイズに応じて条件付き効果を作成する可能性があります。このような条件付き効果は、条件付き効果なしで STRIPS 表記で表現することは困難です。

航空貨物輸送の問題を考えてみましょう。航空貨物輸送では、特定の商品を飛行機で空港から別の空港に輸送する必要があり、飛行機に荷物を積み込んだり降ろしたりする必要があります。

必要なアクションは、積み込み、積み下ろし、飛行です。記述子を使用して、貨物cが飛行機pにあるかどうか、オブジェクトx が空港AIn(c, p)にあるかどうかを表現できます。 At(x, A)

アクションは次のように定義できます。

アクション(  負荷( c : 貨物、 p: 飛行機、 A: 空港)  前提条件: At ( c 、 A) ^ At ( p 、 A)  効果: ¬At ( c 、 A) ^ In ( c 、 p) ) 
 




アクション(  荷降ろし( c : 貨物、 p: 飛行機、 A: 空港)  前提条件: In ( c 、 p) ^ At ( p 、 A)  効果: At ( c 、 A) ^ ¬In ( c 、 p) ) 
 
 



アクション( ( p :  飛行機、出発地: 空港、目的地: 空港) を飛行する  前提条件: At ( p 、 from)  効果: ¬At ( p 、 from) ^ At ( p 、 to) ) 
 

• アクション言語
• アクションの選択
• 階層型タスクネットワーク
• 計画ドメイン定義言語(PDDL)