【DL輪読会】"ROBOTOUILLE: AN ASYNCHRONOUS PLANNING BENCHMARK FOR LLM AGENTS"

ROBOTOUILLE: AN ASYNCHRONOUS PLANNING BENCHMARK FOR LLM AGENTS Presenter: M1 Sayaka Yamashita 1

書誌情報 • 論文名 – ROBOTOUILLE: AN ASYNCHRONOUS PLANNING BENCHMARK FOR LLM AGENTS • 著者 – Gonzalo Gonzalez-Pumariega, Leong Su Yean, Neha Sunkara, Sanjiban Choudhury • 発表学会 – ICRL 2026 Conference Paper • リンク – https://arxiv.org/abs/2502.05227 – https://proceedings.iclr.cc/paper_files/paper/2025/file/d033407a1a4b7a75cd5f9 e4575ad9fb5-Paper-Conference.pdf – 2

• https://aclanthology.org/2025.findings-acl.856/

概要 LLMエージェントの計画能力、特に非同期計画（Asynchronous Planning）能力を評価す る新しいベンチマーク環境「ROBOTOUILLE」を提案。 逐次的タスクや時間遅延のない環境に焦点を当てる既存のベンチマークと比較し、本研究 では、料理シミュレーター環境を通じて、LLMエージェントが多様な長期的タスクや時間遅 延、複数エージェントの調整をどのように処理できるかをテストした。 実験の結果、GPT-4oを用いたReActエージェントであっても、同期的なタスクでは47%の 成功率を示したのに対し、非同期タスクでは11%にまで低下することが明らかとなった。失 敗要因の分析からは、LLMエージェントが環境のルール違反や目標の誤解から回復する 能力に乏しく、長期的視野でのフィードバックの取り込みや自己監査が必要であることが示 唆された。 3

研究の課題意識・目的 現実世界を見据えるとLLMエージェントの非同期計画能力は重要 1. 時間遅延： パスタを茹でるなど、完了までに時間がかかるタスクがある場合、効率的 なエージェントはその待ち時間に別の作業を行うべきである 2. 長期的タスク： 複数の目的を満たすために依存関係を考慮した長い手順が必要 3. マルチエージェント協調： 複数のエージェントでタスクを分担する能力 →これらを解決するために必要なのが非同期計画（Asynchronous Planning）。これは既 存のベンチマーク（ALFWorldやPlanBenchなど）は「時間遅延」を考慮しておらず、この能 力を評価できていなかった 4

ROBOTOUILLE ◎環境の仕組み: • タスクは、時間遅延効果を含むMDP（マ ルコフ決定過程）として定式化 • JSON形式でドメイン（状態や行動の定 義）と問題（初期状態とゴール）を記述し、 手続き型生成によって多様な環境を作成 可能 • PDDL（Planning Domain Definition Language）に触発された形式を採用し、 行動には「即時効果」だけでなく、遅延後 に状態が変わる「特別効果（例：調理完 了）」も定義 5

ROBOTOUILLE • 数理モデル：時間遅延付きMDP (1) 状態 (State) S 状態 s∈S は、物理的な状況と、時間の進行状況の2つペアで表現される (観測可能な状態): S^t：現在の環境の物理的な事実を表す「述語（Predicates）」の集合。 例: iscut(lettuce1)（レタスは切られている）、on(lettuce1, table2)（レタスはテーブル2にある）など • Ht(タイマー変数集合): 現在進行中の待ち時間を管理する変数セット。 各 h∈Htはカウントダウン関数を持つ h(x)=d−(x−i) ・d: 遅延定数（例：肉が焼けるのに必要な3ステップ） ・ i: タイマーが作動した（肉を焼き始めた）ステップ ・ x: 現在のステップ この h(x) が 0 になると、アクションが完了したとみなされる (2) 行動 (Action) A エージェントが実行可能な具体的な行動。 例: move(robot1, table1, table2) アクションは「前提条件（Preconditions）」を持ち、満たされていない場合（例：手に何か持っているのに物を拾おう とする）は無効になる • 一部のアクション（焼く、茹でるなど）は、実行すると新たなタイマー h を Htに追加する。 6

ROBOTOUILLE (3) 遷移関数 (Transition Function) T 現在の状態 s と行動 a から、次の状態 s′を決定する関数 T:S×A→S • 無効な行動の場合 : 状態は変化し（s′=s）。これが実験で「Repeated Transitions（繰り返された遷移）」としてカウ ントされる挙動 • 有効な行動の場合 : 次の状態 は以下のように更新される 1. 物理状態の更新 : アクションの直接的な効果を適用 2. タイマーの更新 : ▪ 期限切れ（h(t)=0）になったタイマーを削除し、その結果（例：iscooked）を物理状態に追加 ▪ 新しいアクションによって発生した遅延をタイマーセットに追加 (4) 報酬関数 (Reward Function) R 非常にシンプルで、ゴール状態 sgに到達したかどうかで判定される R:S→{0,1} • ゴールに到達すれば 1、それ以外は 0 7

ROBOTOUILLE 計算複雑性の数式 通常の計画問題（同期的）とROBOTOUILLE（非同期）の計算量の違いは以下のように定式化 • 同期的（遅延なし , d=0）: 計算量は状態数と行動数に比例 O(∣S∣+∣A∣) • 非同期（遅延あり , d>0）: タイマー変数 n 個と、それぞれの遅延時間 d によって、状態空間が指数 関数的に爆発する O(∣S∣×(d+1)^n+∣A∣) プランナー（LLM含む）が「肉が焼けるまであと3秒」「あと2秒」「あと1秒」...というそれぞれの瞬間を別の 状態として考慮し、その間に他の作業（野菜を切るなど）をどう組み合わせるかを計算しなければならな いからであり、LLMが非同期タスクで失敗する理論的な背景である。 8

データセット ◎3つのデータセット 10種類、⑩パターンでそれぞれ100問ある 1. 同期的（Synchronous）： a. 待ち時間のない、標準的な料理タスク（サンドイッチ作りなど）。 2. 非同期（Asynchronous）： a. 「肉を焼く」「お湯を沸かす」といった待ち時間が発生するタスク。この待ち時 間の間に他の作業（野菜を切るなど）を行うことが効率化の鍵である。 3. マルチエージェント（Multi-agent）： a. 複数エージェントでの協調タスク（本論文では実験の将来課題とされるが データセット自体は提供される）。 9

実験設定 使用されたモデル • 主要モデル: GPT-4o (OpenAI) • 比較用モデル: GPT-4o-mini, Gemini-1.5-Flash, Claude-3-Haiku • オープンソースモデル: Llama-3.1 (70B, 8B), Qwen2 (72B, 32B), Gemma-2 (27B, 9B) • 設定: 温度パラメータ（Temperature）は 0.7 ベースライン手法 (Baselines) エージェントの動作モードとして、以下の3種類（＋拡張版）が比較 1. I/O (Input/Output): a. 現在の初期状態（有効なアクションとゴールを含む）を入力とし、計画全体を一括で出力。環境から のフィードバックを受け取らない「開ループ（Open-loop）」制御 2. I/O CoT (Chain of Thought): a. I/Oと同様だが、アクションの前に「思考の連鎖（CoT）」を出力させ、次の状態を予測させながら計 画を立てる。開ループ。 3. ReAct (Reasoning + Acting): a. 「思考（Reasoning）」と「行動（Action）」を交互に行い、1ステップごとに環境からの新しい状態 （Observation）を受け取る「閉ループ（Closed-loop）」制御。 10

実験設定② 評価指標と計算式 (Metrics & Formulas) 本研究では単なる成功/失敗の二元論ではなくステップ数を基準とした厳密な数式で評価が行われた。 A. 成功の定義 (Success Definition) タスクを完了しても、あまりに非効率な場合は「失敗」とみなす - 条件: エージェントがゴールに到達し、かつそのステップ数が「最適ステップ数の1.5倍以内」 - 判定ロジック : これを超えた時点でエピソードは強制終了され、失敗としてカウント B. 最適性率 (Optimality Rate) 成功したエージェントがどれだけ効率的に動けたかを測る指標 • 計算式: ∥τ^∥: エージェントが実際にかかったステップ数◦ ∥τ∗∥ : 初期状態からゴールまでの最適（最短）ステップ数 • 評価区分 : ◦ 1.0: 最適（Optimal）。最短手順でクリア。 ◦ 1.0 < x ≤ 1.5: 成功だが非効率（Suboptimal）。無駄な行動や待機が含まれる。 ◦ > 1.5: 失敗（Failure）。 11

実験設定③ C. 正規化された残りステップ数 (Normalized Steps to Go) 「失敗したケース」 **において、ゴールまであとどれくらいだったかを測る指標 • 計算式 : ∥τ^left∥ : エージェントが終了（失敗）した時点の状態から、ゴール到達に必要な残りの最適ステップ数。 ∥τ∗∥ : 初期状態からゴールまでの最適ステップ数。 • 評価区分 : ◦ 0 ～ 0.5: ゴールにかなり近づいていた（あと少しで完成）。 ◦ 0.5 ～ 1.0: ほとんど進捗していなかった（初期状態に近い）。 ◦ > 1.0: ゴールから遠ざかった（間違った行動をして状況を悪化させた）。 D. 繰り返された遷移 (Repeated Transitions) エージェントの「回復力（ Recovery）」を測るための指標。 • 定義: 同じ状態から同じ行動を繰り返し選択した回数。 • 背景: LLMは環境のルール（例：「コンロには 1つの鍋しか置けない」）に違反してエラーが返された際、学習せずに同じ無効な行動を繰り 返す傾向がある。この数値が高いほど、失敗からのリカバリーが苦手であることを示す。 12

主な結果①全体 性能の低下：最も高性能の「GPT-4o + ReAct」エージェントは同期的タスクでは47%の成功率 で、非同期タスクでは11%にまで低下 既存モデルの限界：GPT-4o以外のモデル（GPT-4o-mini, Claude-3-Haiku, Gemini-1.5-Flashなど）やオープンソース モデル（Llama-3.1-70b, Qwen2-72Bなど）は、非同期設定 においてほぼ0%に近い成功率。タスクの難易度が非常に高 いことが示さた。 13

主な結果②成功と効率性 • Finding 1: 閉ループベースラインは開ループよりも優れている – 環境からのフィードバックを受け取るかどうかが成功率に差を生む – 行動の結果を観察できる「ReAct（閉ループ）」手法は、観察できない「I/O」や「I/O CoT（開ループ）」手法より圧倒的に高いパフォーマンスを示した。 – GPT-4oを用いた場合、ReActは同期的タスクで47%、非同期タスクで11%の成功率 を記録したが、I/O手法はどちらも数%（1～4%）にとどまった。 – → 計画を一気に出力して実行するだけでは不十分であり、ステップごとに環境の状 態を確認し、修正しながら進める能力が不可欠。 14

主な結果③成功と効率性 • Finding 2:非同期タスクでの「成功」は同期的タスクより効率が悪い – たとえタスクをクリアできたとしても、非同期タスクでは無駄な動きが多く見られた。 – 同期的タスクの成功例では55.3%が「最適解（最短手順）」だが、非同期タスクでは 最適解だったのはわずか9.1% – 多くの成功例（63.6%）は「最適ではないが成功（Suboptimal）」に分類。エージェント が「待ち時間の間に他の作業（野菜を切るなど）を行わず、ただ待機している」といっ た非効率な行動をとったからである 15

主な結果④成功と効率性 • Finding 3: 非同期タスクでの「失敗」は、ゴールに向かってほとんど進捗し ていない – 非同期タスクの失敗は惜しい失敗ではなく何もできずに終わる失敗が多い – 失敗時の残りステップ数（Normalized Steps to Go）を分析した結果非同期タスクの 失敗の約58.6%はゴールまでの距離が初期状態とほぼ変わらない状態 – 一方で、同期的タスクの失敗は、ゴールから遠ざかってしまう（間違った行動をして 状況を悪化させる）ケースが多い（45.3%）。同期的タスクでは「ゴールの誤認」が起 きやすいからである。 16

結果の分析⑤失敗の要因 • Finding 4: 失敗の主因は「ルール違反」と「ゴールの誤認」 – 失敗の原因を分析すると、タスクの種類によって支配的な要因が異なるが根幹に は共通した弱点が見られた – 同期的タスクの失敗: 主に「ゴールの不確実性（64.1%）」が原因。複雑なレシピ や順序指定を誤解して、間違ったものを作ってしまうケース – 非同期タスクの失敗: 主に「遷移関数の不確実性（56.8%）」、つまり環境の物理 ルールの違反が原因 – 特に「1つのステーション（コンロなど）には1つのアイテムしか置けない」という ルールを破るケースが全失敗の53.4%を占めた。非同期タスクでは調理器具を 多く使うため、この管理ができずにパニックに陥る 17

結果の分析⑥失敗の要因 • Finding 5: 非同期設定では、失敗からの「回復（リカバリー）」が著しく下手 – 一度ミスをした後、そこから立ち直る能力において、非同期タスクは同期的タスク よりも困難であることが示された。 – エージェントが同じミス（無効な行動）を繰り返す回数を計測したところ、非同期タ スクでの失敗時は、同期的タスクに比べてこの回数が大幅に多いことがわかった – 非同期タスクで一度ルール違反などを犯すと、修正するために必要な手順が複 雑になり、エージェントは無駄なループ行動を繰り返してステップ数切れになりが ちである。 18

結果の分析⑥フォローアップ調査 • Finding 6:適切な「優先順位付け」がパフォーマンスを向上させる – 「待ち時間が発生するタスクを先にやる」という戦略を与えることが有効であること が確認された。 – プロンプトで「非同期サブタスク（例：お湯を沸かす）を優先せよ」と指示を与えた 場合（Prioritization）、成功率は指示なしの6%から16%へと向上 – LLM自体がタスクのスケジューリングを自律的に行うのは苦手だが、外部から優 先順位のヒントを与えれば、効率的な計画が可能になるとを示した 19

結果の分析⑦フォローアップ調査 • Finding 7: 事前のルール説明を強化すると特定の失敗は減るが別課題が生じる – 失敗主因「ルール違反」を防ぐためプロンプトでルール強調実験を行った – 「ReAct + Prior」手法でルールを詳しく説明してルール違反による失敗は38.1% から22.2%へとほぼ半減。しかし、全体の成功率は統計的に有意なほどには向 上せず（30%→40%程度の変化）。ルール違反が減った代わりに「状態の誤認」 が増えた（例：「肉をコンロに置けば、時間は関係なくすぐに焼けるはずだ」と思い 込むなど）。 – 単にルールを教え込むだけでは不十分で、状態変化（肉が焼けるまでのプロセス など）への理解も同時に深める必要があるとわかった。 20

議論と今後の展望 今後必要とされるもの： • フィードバックの取り込み – 長期的なタスクにおいて、過去のすべての履歴をコンテキストに入れるのはコストと精 度の面で限界がある。エージェントが相互作用を「事実」として要約し、不確実性を減ら すアプローチが有望。 • 自己監査（Self-Verification） – エージェントが自身の推論や計画を監査し、ルール違反や非効率な手順を事前に防ぐ 能力の向上が必要。 21

議論と今後の展望 まとめ： 本論文は「LLMは『手順通りに行う』ことには慣れてきたが、『待ち時間を計算して並行処理 する』ことはまだ非常に苦手である」ことを、新しいベンチマーク「ROBOTOUILLE」を通じて 実証し、その原因が「失敗からの回復力の低さ」や「ルールの不徹底」にあることを突き止め ている 22