アクション記述言語
ロボットプログラミング言語

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

起源

ペドノーは、 STRIPSの表現力は、演算子の効果を条件付きにすることで向上する可能性があると指摘した。これはADL-Aの中心的なアイデアであり、ペドノーが提案したADLの命題的断片に近いものであり[2] 、 ADL-BはAの拡張である。ADL-Bの拡張では、新しい種類の命題、「静的法則」を導入することで、間接的な効果を伴う動作を記述することができる。ADLの3番目のバリエーションであるADL-Cは、命題を静的法則と動的法則に分類できる点でADL-Bに似ているが、より特殊な点がある[3] 。

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

STRIPSとは異なり、ADLではオープンワールドの原理が適用されます。つまり、条件に含まれないすべてのものは未知です（偽とみなされるのではなく）。さらに、STRIPSでは肯定的なリテラルと接続詞のみが許容されるのに対し、ADLでは否定的なリテラルと選言も許容されます。

ADLの構文

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

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

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

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

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

ADLの意味論

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

⇒アクションは、世界に存在するオブジェクトのセットを変更することはできません。これは、すべてのアクション α とすべての現在の状態/次の状態のペア( s、t ) ∈ aについて、 t のドメインがsのドメインと等しくなければならないことを意味します。

⇒ ADLにおける行動は決定論的でなければならない。( s , t 1 )と( s , t 2 )が行動∃の現在の状態と次の状態のペアである場合、t 1 = t 2でなければならない。

⇒ 上記で導入された関数は、一階述語論理式として表現可能でなければならない。任意のn項関係記号Rに対して、自由変数x 2 , ..., x nを持つ論理式Φ a R ( x 1 , ..., x n )が存在し、 f a R ( s )は次のように与えられる。

t （ R ） ＝ f R 1つの （ s ） ＝ （ d 1 、 … 、 d n ） ∈ ドム ⁡ （ s ） n ∣ s [ d 1 / × 1 、 … 、 d n / × n ⊨ Φ R 1つの （ × 1 、 … 、 × n ） ] {\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 1 , ..., x n ) = y が真となるのは、Φ a R ( x 1 , ..., x n , y )が事前に真であった場合のみである。この表現可能性の要件は、最初の制約（fの定義域はsの定義域と等しくなければならない）に依存している点に注意する必要がある。

⇒ アクションが実行可能な状態の集合も、式として表現可能でなければならない。ADLで表現可能なすべてのアクションαに対して、 ( s , t )∈αとなる状態tが存在する場合（すなわち、アクションαが状態sで実行可能である場合） に限り、 s |= Π aを満たす式Π aが存在する必要がある。

計画の複雑さ

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

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

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

STRIPSとADLの比較

  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)が既に真である場合にのみ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) )

参照

参考文献

  1. ^ Edwin Pednault. 「IBM Research Website: Pednault」 . 2013年3月29日閲覧。l
  2. ^ ペドノー「古典的計画枠組みにおけるマルチエージェント動的世界問題の定式化」マイケル・ジョージフとエイミー・ランスキー編『行動と計画についての推論』47-82ページ。モーガン・カウフマン、サンマテオ、カリフォルニア州、1987年。
  3. ^ Michael Gelfond、Vladimir Lifschitz (1998)「アクション言語 Archived September 2, 2011, at the Wayback Machine」、Linköping Electronic Articles in Computer and Information Science、vol 3、nr 16。
  4. ^ Edwin PD Pednault. ADL. 「STRIPSと状況計算の中間点を探る」KR -89紀要、324–332ページ。
  5. ^ Gazen, BCとKnoblock, CA、「UCPOPの表現力とGraphplanの効率性を組み合わせる」ECP9 7, pp. 221-233. トゥールーズ、フランス、1997年
  6. ^ Nebel, B., 「命題計画形式のコンパイル可能性と表現力について」人工知能研究ジャーナル、12、271315、2000年
  7. ^ Jorge A. Baier.、「再定式化による非古典的な計画のための効果的な探索技術」博士論文、トロント大学、2003年。
  8. ^ エドウィン・PD・ペドノー著「ADLと行動の状態遷移モデル」
  9. ^ HJ Levesque、RJ Brachman. 知識表現と推論における根本的なトレードオフ. 『知識表現の読み物』HJ Levesque、RJ Brachman編、pp. 42–70. Morgan Kaufmann、サンマテオ、カリフォルニア州、1985年。
  10. ^ ウラジミール・リフシッツとアルカディ・ラビノフ. 行為の形式理論における奇跡.人工知能, 626(3):89–116. 1986
「https://en.wikipedia.org/w/index.php?title=Action_description_language&oldid=1309967133」より取得