STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

本論文は、長期にわたる複雑な Web タスクにおける既存の Web エージェントの限界を克服するため、動的な AND/OR 木を用いた階層的計画と構造化された記憶モジュールを組み合わせた「STRUCTUREDAGENT」を提案し、その有効性を複数のベンチマークで実証したものである。

要約

この論文は、**「複雑なウェブ上のタスクを、人間のように賢く計画して実行する新しい AI アシスタント」**について書かれています。

タイトルは『STRUCTUREDAGENT』。これを日本語で「構造化エージェント」とでも呼びましょうか。

この AI がなぜ特別なのか、そして何が問題だったのかを、**「大規模な図書館での宝物探し」**という物語に例えて説明します。

---

📚 物語：巨大な図書館での宝物探し

想像してください。あなたは**「1980 年と 1991 年のスーパーボウル優勝チームの出身地を調べ、その 2 都市間のルートと所要時間を教えて」**というミッションを任されました。

これは、巨大で複雑な図書館（インターネット）で、特定の本（情報）を探し出し、それを組み合わせて答えを出す作業です。

❌ 従来の AI の失敗：「衝動的な探検家」

これまでの AI（従来のエージェント）は、**「衝動的な探検家」**のようなものでした。

• すぐに走り出す: 指示を聞くと、すぐに「ピッツバーグに行こう！」と走り出します。
• 記憶が弱い: 10 歩歩くと、さっき見た本の内容を忘れ、「あ、あの本も探さなきゃ」とまた戻ったり、同じ場所を何度も往復したりします。
• あきらめやすい: 道に迷ったり、本が見つからなかったりすると、「もうダメだ」とすぐに諦めて「答えはわかりません」と言って帰ってしまいます。
• 計画がない: 「まず A を調べ、次に B を調べて、C を比較して…」という大まかな地図を持っていません。目の前のページだけを見て、その場しのぎで動いています。

その結果、複雑なミッション（例：Amazon で「3 つの異なる条件を満たす製品」を見つける）では、失敗することが多かったです。

✅ 新 AI「STRUCTUREDAGENT」の活躍：「慎重な作戦会議」

そこで登場するのが、この論文のSTRUCTUREDAGENTです。これは**「作戦会議をしながら動く探検家」**です。

彼が使うのは、**「AND/OR ツリー（論理の木）」**という特別な地図です。

1. 木（ツリー）を描く:

   • AND ノード（「かつ」の木）: 「A 条件かつB 条件かつC 条件」をすべて満たす必要がある場合、木は枝分かれして、すべての枝を完成させなければなりません。
   • OR ノード（「または」の木）: 「A 方法またはB 方法」でいい場合、木は複数の道を用意し、一番成功しそうな道を選びます。もしその道が失敗したら、すぐに別の道に切り替えます。

2. メモ帳（構造化メモリ）:

   • 従来の AI は「メモ」をただの落書きのように書いていましたが、この AI は**「整理された表」**を使います。
   • 「候補 A：価格〇〇、条件〇〇を満たす」「候補 B：条件〇〇を満たさない（却下）」のように、見つけた情報をきれいに整理して、後で忘れずに振り返ることができます。

3. 失敗からの回復（リカバリー）:

   • もし「ピッツバーグに行こう」という道が失敗したら、AI は「あ、失敗したな。じゃあ、この枝は切り捨てて、別の候補（例：ワシントン DC）を試そう」と冷静に判断します。
   • 従来の AI が「失敗＝終了」だったのに対し、この AI は**「失敗＝別の道を探すチャンス」**と捉えます。

🎯 なぜこれがすごいのか？（3 つのポイント）

1. 人間のように「分解」できる:
   大きなタスクを「まず情報を集める」「次に比較する」「最後に選ぶ」というように、小さなステップに分解して実行します。これにより、長い道のりでも迷子になりません。

2. 失敗しても諦めない:
   一つの道がダメでも、木構造（ツリー）の中に「別の道（OR ノード）」が用意されているため、すぐに切り替えて再挑戦できます。

3. 人間が介入できる:
   もし AI が間違った方向に進みそうになったら、人間が「ちょっと待て、その木（計画）は間違っている。こっちの枝に変えて」と手助けできます。AI の思考過程が「木」の形で見えるため、どこが間違っているか一目でわかります。

🍳 料理の例えでまとめると

• 従来の AI: 冷蔵庫の中をただ見て、「卵があるから卵料理を作ろう」と思いつき、材料が足りなくても「もう無理」と言って料理を中断する。
• STRUCTUREDAGENT:
  1. まず**レシピ（計画）**を書く。「卵、牛乳、パンが必要（AND 条件）」と決める。
  2. 冷蔵庫を見て材料を探す。
  3. もし「牛乳」がなかったら、**「豆乳でも代用できるかも（OR 条件）」**という選択肢を即座に検討する。
  4. 見つかった材料を**「メモ帳（表）」**に記録して、忘れずに管理する。
  5. 最終的に、完璧なオムレツ（タスク完了）を完成させる。

🌟 結論

この論文は、**「AI に『衝動的に動く』だけでなく、『計画を立てて、失敗しても冷静に切り替え、情報を整理して』実行させる仕組み」**を作ったことを報告しています。

これにより、複雑なショッピングや情報収集のような、長く難しいウェブ上のタスクでも、AI は人間よりもはるかに賢く、頼もしいパートナーになれるようになりました。

技術概要

StructuredAgent: 長期視野の Web タスクのための AND/OR 木を用いた計画手法

技術的サマリー（日本語）

本論文は、大規模言語モデル（LLM）を基盤とした自律エージェントが、複雑で長期にわたる Web ブラウジングタスク（情報収集、フォーム入力、取引など）を遂行する際に直面する課題を解決するための新しいフレームワーク**「STRUCTUREDAGENT」**を提案するものです。

1. 問題定義

既存の Web エージェントは、以下の 4 つの主要な限界により、複雑な長期タスクにおいて失敗しやすい傾向があります。

1. 限られたコンテキストメモリ: 20,000 トークンを超える dense な Web ページや、多数のページにわたる履歴を保持・追跡する能力が不足している。
2. 計画能力の欠如: 長期の視野にわたって複雑な計画を構築・実行する能力が弱い。
3. エラー処理の脆弱性: 失敗からの回復や、代替解決策の探索が不十分である。
4. 貪欲な意思決定: 全ての制約を満たす前にタスクを早期に終了してしまう傾向がある。

これらの課題は、人間の問題解決（手段・目的分析とヒューリスティック探索）の特性を模倣できていないことに起因しています。

2. 提案手法：STRUCTUREDAGENT

STRUCTUREDAGENT は、計画と実行を交互に行う階層的な計画フレームワークであり、以下の 2 つの中核コンポーネントと、解釈可能性の高い階層的計画の生成を特徴としています。

A. オンライン階層プランナー（動的 AND/OR 木）

エージェントは、タスク実行中に動的に構築・維持されるAND/OR 木を用いて計画します。

• ノードの種類:
  • AND ノード: 親ノードの成功には、すべての子ノード（部分目標）の成功が必要（論理積）。
  • OR ノード: 親ノードの成功には、いずれか一つの子ノード（代替戦略）の成功で十分（論理和）。
  • ACTION ノード: ブラウザ操作（クリック、入力、スクロールなど）またはメモ記録に対応する葉ノード。
• 探索アルゴリズム: 標準的な DFS（深さ優先探索）を改良した貪欲な反復 DFSを採用しています。
  • 状態管理: ノードに ENTERING（処理中）、EXITING（完了確認）、FAILED（失敗）の 3 つの状態を割り当て、動的な木の変化や失敗の伝播を管理します。
  • 動的修正: 実行中に失敗が発生した場合、LLM を用いた**ノード修復（Node Repair）や剪定（Pruning）**を行い、計画をリアルタイムで修正します。
  • LLM の役割: 木全体の構築を LLM に任せるのではなく、フレームワークが木を管理し、LLM にはノードの展開、修復、完了確認など、局所的で定義されたタスクのみを委譲します。これにより、推論の解釈可能性と堅牢性が向上します。

B. 構造化メモリモジュール（Structured Memory）

情報探索タスクにおいて、候補となるエンティティ（商品や記事など）とその制約の充足状況を追跡するためのモジュールです。

• 動的テーブル: 発見された候補を構造化されたテーブル（行：候補、列：制約・属性）として管理します。
• 制約追跡: タスクの制約（価格、仕様、評価など）を明示的に追跡し、候補の追加、更新、削除を LLM に指示します。
• 効果: 探索中の候補を見失ったり、重複したりするのを防ぎ、複数の候補を同時に比較・評価することを可能にします。

3. 主要な貢献

1. 順序付き AND/OR 木による推論時計画: 構成的推論、動的計画修正、エラーの逆伝播を可能にする階層的計画フレームワークの導入。これにより、エラーの局所化と人間の介入が容易になります。
2. 構造化メモリモジュールの開発: Web ベースの情報探索タスクにおいて、候補エンティティと制約の充足状況を追跡し、計画・実行中の制約充足率を向上させる仕組みの提案。
3. 広範なベンチマークでの有効性実証: WebVoyager、WebArena、および独自に設計した複雑なショッピングタスクにおける高い性能の実証。

4. 実験結果

複数のベンチマークとモデルファミリー（Claude 3.5/3.7, Kimi-k2, Gemini, GPT-4.1）を用いた評価において、STRUCTUREDAGENT は既存の強力なベースライン（AgentOccam, SteP, BasicClaudeAction など）を上回る性能を示しました。

• Amazon ショッピングタスク（複雑な長期タスク）:
  • Amazon Easy: 平均成功率 83.3%（AgentOccam より 14% 上）。
  • Amazon Hard: 人間評価で 37.8%（AgentOccam より 7% 以上上）。構造化メモリ（StructuredAgentMem）を併用することで、さらに 5% 向上しました。
  • 複雑な制約（価格、仕様、複数アイテムの組み合わせなど）を満たす能力が顕著に向上しました。
• WebArena:
  • 全体スコア 52.6%（AgentOccam より約 6% 上）。特にショッピング（52.8%）と Reddit（72.6%）タスクで高い性能を発揮しました。
• WebVoyager:
  • 比較的単純なタスクではベースラインと同等かやや低い結果となりましたが、これは本フレームワークが最も恩恵を受ける複雑な多段階計画が必要なタスクにおいて顕著な差が出るためです。
• 効率性と軌跡:
  • 難易度の高いタスクでは、より多くのブラウザ操作（探索）を行いますが、これは失敗からの回復や代替戦略の探索に起因しており、結果として成功率が向上しています。

5. 意義と結論

STRUCTUREDAGENT は、LLM エージェントが Web 環境において直面する「長期視野」「不確実性」「エラー回復」という課題に対し、明示的な階層計画（AND/OR 木）と構造化された状態管理を組み合わせることで、人間のような適応的な問題解決を可能にしました。

• 解釈可能性: 計画の過程が木構造として可視化されるため、どこで失敗したか、なぜその判断を下したかを人間が理解・介入しやすくなっています。
• 汎用性: 基盤モデル（Claude, Kimi など）を問わず効果的であり、LLM の能力向上のみならず、アーキテクチャ的な工夫がエージェントの性能向上に寄与することを示しました。
• 将来展望: このアプローチは、単なる Web ブラウジングだけでなく、複雑な意思決定を必要とするあらゆる自律エージェントシステムへの応用が期待されます。

本論文は、LLM エージェントの「推論」と「実行」を統合し、より信頼性が高く、人間と協調可能なシステムを構築するための重要なステップを示しています。