💻 computer science

Learning Lifted Action Models from Traces with Minimal Information About Actions and States

本論文は、動作および状態に関する部分的な情報を含むトレースから STRIPS+ 動作ドメインを学習するためのアルゴリズムと完全性結果を提示し、状態の完全な観測性から特定の状態述語の完全または局所的な観測性まで、あるいは状態の観測性が全くない状況に至るまでのシナリオを考慮することで、以前の限界に対処するものである。

原著者： Jonas Gösgens, Niklas Jansen, Hector Geffner

公開日 2026-05-19

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Jonas Gösgens, Niklas Jansen, Hector Geffner

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

複雑なボードゲーム、例えばチェスやスライドパズルのルールを推測しようとしていると想像してください。しかし、非常に奇妙な問題に直面しています。ボードが見えないのです。

見ることができるのは、プレイヤーが行う動きだけです。ある駒が「A」から「B」へ移動する様子や、プレイヤーがトークンを手に取る様子が見えます。しかし、どの駒が移動したのか、どこから始まったのか、移動の前後でボードがどうなっていたのかは分かりません。一連の行動を観察するだけで、ゲームのルールブックをリバースエンジニアリングしようとしているのです。

これが、論文**「Learning Lifted Action Models from Traces with Minimal Information（最小限の情報からのトレースによるリフトされた行動モデルの学習）」**で扱われている核心的な課題です。

以下に、著者たちが何を行ったかを、簡単な比喩を用いて解説します。

課題：「情報過多」の罠

過去、コンピュータ科学者たちは AI にこれらのルールを学習させようと試みました。彼らは主に 2 つのアプローチを取りましたが、どちらも欠点がありました。

「完全なボード」アプローチ：AI にはボードの全状態（すべての駒の位置）と、その移動が与えられました。
- 欠点：現実世界では、ボード全体を見ることはめったにありません。また、ルール自体があまりにも詳細を要求することがあります。例えば、パズルでタイルを動かす際、古いルールではタイルの現在の場所、新しい場所、そして空いている場所をすべて指定する必要がありました。しかし、移動を決定するためには、「左へ移動」という情報だけで十分です。追加の詳細は、意思決定者にとって単なるノイズに過ぎません。
「行動のみ」アプローチ：AI には行動のリストのみ（例：「左へ移動」、「持ち上げる」）が与えられました。
- 欠点：ボードが見えないため、AI は何を移動させたのかを特定できませんでした。「左へ移動」がロボットを動かすのか、車を動かすのか、箱を動かすのかさえ分かりませんでした。

解決策：新しい言語（STRIPS+）

著者たちは、**STRIPS+**と呼ばれる中間的なアプローチを導入しました。これは、ルールを記述するより賢い方法だと考えてください。

古い方法（STRIPS）では、ルールは厳格なフォームのように見えました。

Move(Robot, CurrentCell, NextCell)

新しい方法（STRIPS+）では、ルールはなぞなぞのように見えます。

Move()

このルールは、「もしセルの中にロボットがいて、右側にセルがあれば、移動できる」と述べています。コンピュータは、どのロボットとどのセルがこの記述に当てはまるかを推測する必要があります。これは、容疑者が「ジョン・スミス」と名指しされるのではなく、「赤い帽子をかぶった人物」という説明だけで特定される、探偵が事件を解決するようなものです。

新しいアルゴリズム：SIFT+ と SYNTH+

この論文では、情報が欠落している場合の謎を解くための 2 つの新しい「探偵」（アルゴリズム）が紹介されています。

1. SIFT+（「行動のみ」の探偵）

何をするか：ボードを一切見ることなく、行動のリストを見るだけでルールを学習します。
仕組み：**「排他的特徴（Mutex Features）」**と呼ばれるトリックを使用します。
- 比喩：プレイヤーがカップを手に取るのを見たが、カップ自体は見えないと想像してください。しかし、プレイヤーは一度に1 つのカップしか持てないことは分かっています。もしプレイヤーがカップを手に取ったなら、持っていたカップを置いたに違いありません。
- SIFT+ は、これらの「排他的」なパターンを探します。「ああ、この行動が起こるたびに、持っている物体について何かが真でなければならない」と気づくのです。そして、欠落している隙間を埋めるために、新しい「述語（is_holding のような概念）」を考案します。
結果：行動名からほとんどすべての詳細が剥ぎ取られていても、完全なルールブックを学習することができます。

2. SYNTH+（「部分的な視点」の探偵）

何をするか：ボードの一部は見えますが、すべては見えない状況でルールを学習します。
仕組み：新しい STRIPS+ 言語の「なぞなぞ解決」と、SIFT+ の「考案」のスキルを組み合わせます。
- 比喩：配達ドライバーを見ていると想像してください。ドライバーの位置（「完全に観測可能な」部分）は見えますが、トラックの中の荷物は見えません。しかし、ドライバーは一度に 1 つの荷物しか持てないことは分かっています。
- SYNTH+ は、見える位置情報を使って見えない荷物を推測します。「ドライバーがドアにいて、何かを『降ろした』としたら、彼の手には何があったに違いない？」と問いかけます。
転換点：この論文では**「局所観測性（Local Observability）」という概念を導入しています。これは、ボード全体**を見る必要はないことを意味します。現在の行動に関連する部分だけを見ればよいのです。
- 例：ロボットが「左」へ移動する場合、その左隣のセルを見るだけで十分です。マップの反対側のセルを見る必要はありません。これにより、学習ははるかに現実的なものになります。

「依存グラフ」（道案内図）

これらの探偵がループにはまってしまわないようにするため、著者たちは依存グラフと呼ばれるマップを作成しました。

これはフローチャートのようなものです。「ルール A」を学習するには、「事実 B」を知る必要があるかもしれません。「事実 B」を学習するには、「ルール C」が必要かもしれません。
この論文は、このフローチャートに循環ループ（A が B を必要とし、B が C を必要とし、C が A を必要とするような状態）が存在しない限り、アルゴリズムは見えるものから始めて、見えないものへと逆算しながら、ステップバイステップでルールを学習できることを証明しています。

結果：機能しましたか？

著者たちは、これらの探偵を、ブロックワールド（ブロックを積み上げる）、デリバリー（荷物を運ぶ）、ソカバン（箱を押し込む）などの古典的なパズルでテストしました。

テスト：アルゴリズムに、情報の 50% から 90% が隠されたトレースを与えました。
結果：
- SIFT+ は、行動リストのみからルールを正常に学習し、「どのブロックが上にあるか」といった欠落した詳細を、パターンに気づくだけで回復させました。
- SYNTH+ は、「ボード」の大部分が隠れていても、重要な要素（エージェントの位置など）が見えていれば、ルールを学習しました。
- ほぼすべてのテストにおいて、アルゴリズムは100% の精度を達成し、隠されたルールブックを正しく再構築しました。

まとめ

この論文は、非常に少ない情報を与えられたときに、コンピュータに「ゲームのルール」を学習させる方法について述べています。

古い方法：「ここがボード、ここが移動だ。ルールを学習せよ。」（情報が必要過多）
新しい方法：「ここは行動のリストだ。プレイヤーの位置は見えますが、物体は見えません。ルールを推測してください。」
画期的な点：より賢い言語（STRIPS+）を使用し、真でなければならない事実に基づいて欠落した事実を「考案」する巧妙な方法（排他的特徴）を用いることで、AI は世界の完全な視界を得ることなく、空白を埋め、ドメインの完全な論理を学習できることです。

この論文は、完璧でデータに富んだマニュアルを必要とするのではなく、人間が他者を見ることで学習するのと同様に、自然で不完全な観察から学習できる AI を実現するための大きな一歩であると主張しています。

技術的概要：最小限の情報を用いたトレースからのリフテッド行動モデルの学習

問題定義

近年の研究では、リフテッド STRIPS モデルが行動トレースのみから効率的に学習可能であることが示されており（SIFT アルゴリズム）、また、暗黙的な行動引数を許容する STRIPS+ モデルが、完全に観測可能な状態 - 行動トレースから学習可能であることも示されている（SYNTH アルゴリズム）。しかし、これらのアプローチは実用的な限界に直面している：

SIFT は、引数が明示的な完全な STRIPS 行動トレースを必要とする。これには、行動選択に不要なパラメータが含まれることが多い（例：スライディングタイルパズルにおいて、行動が「左へ移動」であっても、タイルの現在の位置が明示的に渡されなければならない）。
SYNTH は、すべての状態述語の完全な観測可能性を仮定しており、部分的に観測可能な環境で動作するエージェントにとっては非現実的である。

本論文は、行動引数と状態情報の両方が部分的に観測可能なトレースから STRIPS+ 行動ドメインを学習する問題に取り組む。具体的には、著者らは、トレースが最小限の情報（一部の行動引数が省略され、状態述語が完全に観測不可能、完全に観測可能、または局所的に観測可能（現在の状態に関連するオブジェクトのみ観測可能））を運ぶ場合、同等のドメインが学習可能となる条件を調査する。

手法

提案される解決策 SYNTH+ は、SIFT と SYNTH の能力を拡張・統合した統合アルゴリズムである。これは拡張されたトレース（行動と部分的な状態観測の系列）上で動作し、2 つの中核メカニズムに依存する：

1. ミュートクス特徴（SIFT の拡張）

状態の観測可能性なしに欠落した行動引数を処理するために、著者らはミュートクス特徴を導入する。

概念：ミュートクス特徴 $f = \langle k, A, D \rangle$ は、 $k$ 番目の引数が最初の $k-1$ 個の引数によって暗黙的に決定される $k$ 項の述語を表す。
メカニズム：標準的な特徴では追加パターンと削除パターンが同じ項数を持つが、ミュートクス特徴では削除パターンが $k-1$ 項を持つことを許容する。これにより、行動（例：drop()）がそのオブジェクトを明示的に名前付けずに、現在保持されているオブジェクトに基づいて述語（例：holding(o)）を削除するという制約を捉えることができる。
一貫性：トレースグラフ全体において、すべての基底原子 $f(o)$ が単一の真理値を受け取り、同じ状態内の任意の 2 つの真の原子 $f(o)$ と $f(o')$ について、最後の引数が異なる場合（ $o_k \neq o'_k$ ）、少なくとも 1 つの先行する引数も異なっていなければならない（ある $i < k$ に対して $o_i \neq o'_i$ ）とき、ミュートクス特徴は一貫しているという。

2. クエリ合成と統合（SYNTH の拡張）

SYNTH+ は、述語の「発明」（SIFT 経由）と暗黙的引数の推論（SYNTH 経由）を反復ループで統合する：

入力：拡張されたトレースのラベル付きグラフと、完全に観測可能な述語の集合 $P_\omega$ 。
反復：
- SIFT+ ステップ：明示的引数と現在既知の暗黙的引数にわたる行動パターンを用いて、新しいミュートクス特徴と単純特徴を発明する。これらの特徴は、新しい述語とその効果を表す。
- SYNTH ステップ：新たに発明された述語（および任意の観測可能な述語）を用いて、暗黙的変数 ( $z_i$ ) を状態内の一意のオブジェクトに束縛するクエリ（部分クエリ $Q_i$ ）を定義する。
- 更新：グラフを、新しい暗黙的引数とその定義クエリで更新する。
終了：過程は、固定点に達するか、最大深さ制限 ( $d_{max}$ ) を超えるまで継続する。

3. 局所観測可能性

この枠組みは、局所観測可能性を処理する LOCAL SYNTH+ に拡張される。この設定では、述語は「局所的」なオブジェクト（現在の行動の引数として現れるもの）に対してのみ観測可能である。アルゴリズムは、事前条件をテストする際に非局所原子を偽と仮定するように一貫性テスト手順 (TEST*) を修正し、観測されていない状態の部分が暗黙的引数の学習を無効化しないようにする。

主要な貢献

SYNTH+ アルゴリズム：行動と状態の両方の部分的観測可能性を伴うトレースから STRIPS+ ドメインを学習するための汎用アルゴリズム。これは、SIFT の述語発明と SYNTH の暗黙的引数解決を統合する。
ミュートクス特徴：最後の引数が他の引数に機能的に依存する述語の学習を可能にする新規形式。これにより、完全な状態観測なしに省略された行動引数を回復できる。
完全性結果：アルゴリズムが完全となるための理論的条件が確立されている：
- SIFT+（状態観測なし）：隠れた STRIPS+ ドメインが適切に形成され、強連結であり、依存グラフ（ノードは述語と暗黙的変数）において非循環的である必要がある。
- SYNTH+（部分的状態観測）：非観測可能な述語に制限された依存グラフが非循環的である必要がある。
- LOCAL SYNTH+：局所観測可能性の下で、完全観測可能な場合の事前条件における暗黙的引数のみを含む述語（主要述語）および他の述語が局所的に観測可能であれば、完全であることが証明されている。
一般化：この研究は、SIFT と SYNTH がそれぞれ $P_\omega = \emptyset$ および $P_\omega = P$ である場合の SYNTH+ の特殊ケースであることを示している。

実験結果

著者らは、隠れた STRIPS+ モデルから生成された拡張トレースを使用して、標準的な計画ドメイン（ブロック、配送、グリッド、ソコバン、物流など）の suite 上で SIFT+ と SYNTH+ を評価した。

SIFT+ の性能：すべてのテストドメインにおいて、行動トレースのみから正しいドメインを学習することに成功し（検証率 100%）、トレースから省略された行動引数の平均 55% を回復した。
SYNTH+ の性能：SYNTH よりもはるかに少ない観測可能な述語を用いて正しいドメインを学習した。
- 配送において、SYNTH+ はエージェントの位置 (at(x)) と静的な隣接関係のみを観測してドメインを学習したが、SYNTH はすべてのフルエント述語を必要とした。
- ソコバンおよび物流*において、SYNTH+ は静的述語のみを観測してドメインを学習した。これは、SYNTH も SIFT+ も成功できなかったシナリオである。
効率性：アルゴリズムは標準的なハードウェア上で効率的に実行され（数秒から数分）、数千のトレースステップを持つドメインにスケーリングした。

意義と主張

本論文は、SYNTH+ が「自然な」トレースから動的モデルを学習可能にすることで、モデルベース強化学習に対する実用的なリフテッド代替手段を提供すると主張している。これらのトレースは最小限の情報しか必要としない：

形式化された STRIPS エンコーディングが要求するすべての引数（例：積み重ねられたブロックの現在の位置など）を列挙する必要はない。
完全な状態観測性は必要ない。特定の述語の部分的または局所的な観測可能性で十分である。

著者らは、このアプローチが、完全な観測可能性をしばしば仮定する理論的モデル学習と、エージェントが限られた知覚を持つ実用的応用との間のギャップを埋めることを強調している。学習が可能となる正確な条件（依存グラフの非循環性）を特徴づけることで、この研究は部分的に観測可能な設定におけるリフテッド行動モデル学習の厳密な範囲を確立している。結果は、複雑なドメインが完全な状態記述ではなく、行動を選択するために必要な情報のみを伝達するトレースから再構築可能であることを示唆している。