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

该论文提出了 STRUCTUREDAGENT 框架，通过结合基于动态 AND/OR 树的在线分层规划器与结构化记忆模块，有效解决了现有 Web 智能体在长程任务中因记忆受限、规划能力弱及贪婪行为导致的性能瓶颈，显著提升了复杂网页浏览任务的成功率与可解释性。

要点

这篇论文介绍了一种名为 STRUCTUREDAGENT 的新型人工智能系统，专门用来解决那些极其复杂、步骤繁多的网页浏览任务。

想象一下，如果你让一个普通的 AI 去网上帮你买一套复杂的装备（比如：找三个不同品牌的、价格在 300 元以下的、带特定功能的机械键盘），普通的 AI 可能会像个迷路的新手：它可能刚找到第一个键盘就兴奋地把任务结束了，或者在遇到一个坏链接时就彻底放弃，甚至忘了之前看过的信息。

而 STRUCTUREDAGENT 则像是一位经验丰富的老练侦探或精明的项目经理。它之所以能成功，主要靠两样“法宝”：

1. 动态的“决策树” (AND/OR 树) —— 像下棋一样思考

普通的 AI 走一步看一步，而 STRUCTUREDAGENT 手里有一张动态生成的“作战地图”，也就是论文里说的 AND/OR 树。

• AND 节点（必须全部完成）： 就像做一道菜，你必须同时准备好“鸡蛋”、“面粉”和“糖”，缺一不可。在任务中，这意味着“搜索商品”、“筛选价格”和“确认库存”这三个步骤必须全部成功，任务才算推进。
• OR 节点（二选一）： 就像去超市买牛奶，你可以走“东门”进去，也可以走“西门”进去。只要其中一条路通了，任务就能继续。

最厉害的地方在于“后悔药”机制：
如果 AI 发现刚才选的那条路（比如点击了一个错误的链接）走不通了，普通的 AI 可能会死胡同里撞墙。但 STRUCTUREDAGENT 会立刻在“地图”上把这条死路剪掉（Prune），然后迅速回溯，尝试“地图”上标记的另一条备选路线（OR 节点）。它不会盲目地重复错误，而是像下棋一样，不断推演“如果这一步错了，我下一步该走哪里”。

2. 结构化的“记忆本” (Structured Memory) —— 像 Excel 表格一样记笔记

在复杂的购物或搜索任务中，AI 需要记住很多细节：这个商品多少钱？那个商品有没有货？哪个品牌符合我的要求？

普通的 AI 就像是在嘈杂的菜市场里大声喊话，记性不好，容易把刚才看到的商品和现在的搞混，或者忘了之前已经排除掉的选项。

STRUCTUREDAGENT 则有一个结构化的“记忆本”（就像一张动态的 Excel 表格）：

• 它会把找到的每一个候选商品（比如“投影仪 A"、“投影仪 B"）都填进表格里。
• 表格里有专门的列记录：价格、亮度、是否带屏幕、是否满足所有条件。
• 当它发现“投影仪 A"太贵了，它不会只是口头说“太贵了”，而是直接在表格里把这一行标记为“淘汰”，并更新状态。
• 这样，无论任务多长，它都能清晰地知道：“哦，我已经试过了 A 和 B，现在只剩下 C 和 D 了，我要继续检查它们。”

总结：它是怎么工作的？

你可以把 STRUCTUREDAGENT 想象成一位带着地图和记事本的探险家：

1. 接到任务（比如：找 3 个符合特定条件的投影仪）。
2. 画出地图：它先不急着行动，而是先在脑子里（或屏幕上）画出任务的大纲：先搜索，再筛选，再对比。
3. 执行与记录：它开始行动，每走一步，就把看到的商品信息填进“记忆本”的表格里。
4. 遇到障碍：如果某个商品不符合条件，它不会崩溃，而是立刻在“地图”上把这条路标红（剪掉），然后从“记忆本”里拿出下一个候选者，或者尝试另一条搜索策略（比如换个关键词）。
5. 最终交付：当它遍历了所有可能的路径，或者找到了满足所有条件的完美组合时，它会整理好“记忆本”里的信息，给你一个清晰、准确的答案。

为什么这很重要？

以前的 AI 在长任务中容易“断片”或“贪心”（稍微有点进展就以为结束了）。这篇论文提出的方法，让 AI 变得更有条理、更抗造、更聪明。

• 更可靠：即使网页变了、链接坏了，它也能自己调整路线，不会轻易放弃。
• 更透明：因为它有“地图”和“表格”，人类可以清楚地看到它是怎么思考的，哪里出错了，甚至可以在它犯错时人工介入修正（就像在地图上帮它指个路）。
• 更擅长复杂任务：在需要同时满足多个条件（如价格、品牌、功能、评分）的购物或研究任务中，它的表现远超现有的其他 AI 系统。

简单来说，STRUCTUREDAGENT 就是把 AI 从一个“凭直觉乱撞的莽夫”，变成了一个“有规划、有记忆、会复盘的资深专家”。

技术摘要

论文技术总结：STRUCTUREDAGENT——面向长程网络任务的 AND/OR 树规划

1. 研究背景与问题 (Problem)

随着大语言模型（LLM）的发展，智能体（Agent）在顺序决策任务中展现出巨大潜力。然而，现有的 Web 智能体在处理复杂、长程（Long-Horizon）的网页浏览任务时仍面临严峻挑战，主要存在以下四个核心问题：

1. 上下文记忆受限 (Limited In-Context Memory)：网页内容庞大（单页常超过 20k token），现有智能体通常只能关注当前页面和有限的动作历史，难以在跨多页面的复杂任务中追踪替代解决方案路径。
2. 长程规划能力弱 (Weak Long-Horizon Planning)：难以构建和执行跨越多个时间步的复杂计划，缺乏对任务结构的分解能力。
3. 缺乏鲁棒的错误处理 (Lack of Robust Error Handling)：一旦执行失败，往往无法有效恢复或探索替代方案，导致任务过早终止。
4. 贪婪决策 (Greedy Behaviors)：智能体倾向于采取短视的贪婪策略，在未满足所有用户约束的情况下提前终止任务。

现有的解决方案（如基于 A* 的树搜索或增量树构建）往往在动作级别操作，缺乏对任务组合结构的利用，或者完全依赖 LLM 进行规划，导致计划简单且错误恢复能力差。

2. 方法论 (Methodology)

为了解决上述问题，作者提出了 STRUCTUREDAGENT，这是一个分层规划框架，其核心在于将规划与执行交织，利用动态构建的 AND/OR 树 来指导智能体行为。该框架包含两个核心组件：

2.1 动态 AND/OR 树规划器 (Online Hierarchical Planner)

该规划器将复杂任务递归分解为不同抽象层级的子目标，构建显式的 AND/OR 树结构：

• 节点类型：
  • AND 节点：表示合取子目标，所有子节点必须成功，父节点才算成功。
  • OR 节点：表示析取策略，只要有一个子节点成功，父节点即成功。
  • ACTION 节点：叶子节点，对应具体的浏览器操作（如点击、输入、滚动、记录笔记）。
• 执行机制：
  • 采用改进的贪婪深度优先搜索 (Modified Greedy DFS) 进行树的扩展和遍历。
  • 状态管理：引入三种节点状态（ENTERING, EXITING, FAILED）和六种状态值，支持节点的重访、修复和剪枝。
  • 动态修正：当执行失败时，框架支持错误反向传播 (Error Back-propagation)。对于失败节点，系统会尝试修复（添加/修改子节点）或剪枝（移除无效分支），并向上层传播失败信号以触发高层级的重新规划。
  • LLM 的角色：LLM 仅作为高层控制器，负责特定的局部树操作（如节点扩展、修复、完成性检查），而非生成整个计划。这提高了推理的可解释性和鲁棒性。

2.2 结构化记忆模块 (Structured Memory)

针对信息检索类任务（如购物、研究），传统的非结构化笔记容易丢失关键信息。STRUCTUREDAGENT 引入了结构化记忆模块：

• 功能：动态维护一个候选实体表（Candidate Entities Table）。
• 机制：从任务描述中提取约束条件，在浏览过程中实时提取、更新或删除候选项及其属性（如价格、评分、规格）。
• 作用：在决策过程中（如节点扩展和修复），检索满足最多约束的前 K 个候选项，避免重复探索已拒绝的页面，显著提升多约束任务中的约束满足率。

2.3 可解释性与人工干预

框架生成的分层计划具有高度的可解释性。如图 13 所示，人类操作员可以检查 AND/OR 树，发现错误的子目标分解，并在执行前注入修正后的子目标（Human-in-the-loop），从而纠正智能体的幻觉或逻辑错误。

3. 主要贡献 (Key Contributions)

1. 分层规划框架：提出了基于有序 AND/OR 树的推理时规划框架，支持组合推理、动态计划修订和错误反向传播，生成了可解释的层级计划，便于错误定位和人工干预。
2. 结构化记忆模块：针对 Web 信息检索任务，开发了能够追踪候选实体及其满足约束的结构化记忆模块，显著提升了复杂约束下的任务完成质量。
3. 广泛的实证验证：在具有挑战性的 WebVoyager、WebArena 以及自定义的 复杂购物基准 (Custom Complex Shopping) 上进行了全面评估，证明了该方法在长程任务上的优越性。

4. 实验结果 (Results)

实验在多个基准测试中对比了 STRUCTUREDAGENT 与主流基线（如 AgentOccam, SteP, BasicClaudeAction 等），使用 Claude 3.5/3.7 和 Kimi-k2 等模型作为骨干。

• Amazon 购物任务 (长程、多约束)：
  • 在 Amazon Easy 任务中，STRUCTUREDAGENT 取得了 83.3% 的平均成功率，优于 AgentOccam (69.2%)。
  • 在更难的 Amazon Hard 任务中，人类评估显示 STRUCTUREDAGENT 比 AgentOccam 高出至少 7%，比 BasicClaudeAction 高出 23.4%。
  • 引入结构化记忆模块（StructuredAgentMem）后，在 Amazon Hard 任务上进一步提升了 5% 的成功率。
• WebArena 基准：
  • 在 Shopping 和 Reddit 类别中表现最佳，整体成功率达到 52.6%，显著优于 AgentOccam (46.4%) 和其他基线。
  • 在 Map 和 GitLab 任务上，虽然动作数量略多（因为进行了更彻底的探索），但成功率依然具有竞争力。
• 模型泛化性：
  • 使用更强的模型（Claude 3.7）时，STRUCTUREDAGENT 依然保持领先，且结构化记忆模块带来的增益减小（说明强模型能更好地利用树结构），证明了框架的通用性。
  • 在 Kimi-k2 模型上也取得了优于 AgentOccam 的整体表现。
• 效率分析：
  • 在困难任务上，STRUCTUREDAGENT 倾向于执行更多动作以探索多种策略，这反映了其“深思熟虑”的规划特性，而非盲目试错。

5. 意义与影响 (Significance)

STRUCTUREDAGENT 的研究具有重要的理论和实践意义：

1. 解决长程任务痛点：通过显式的 AND/OR 树结构和动态错误处理机制，有效解决了现有 LLM 智能体在长程、多步 Web 任务中容易迷失、无法恢复和过早终止的问题。
2. 提升可解释性与可控性：将黑盒的 LLM 决策过程转化为可视化的树状结构，不仅便于调试，还允许人类在关键节点进行干预，这对于高风险或高价值的应用场景至关重要。
3. 结构化记忆的新范式：证明了在长程任务中，将非结构化记忆转化为结构化表格能显著提升约束满足能力，为未来的智能体记忆机制设计提供了新思路。
4. 通用性：该框架不依赖特定模型，在不同大小的 LLM 上均表现出鲁棒性，为构建更可靠的自主 Web 智能体提供了通用的架构参考。

综上所述，STRUCTUREDAGENT 通过结合分层规划、动态树搜索和结构化记忆，显著提升了智能体在复杂 Web 环境中的任务完成能力，是迈向更可靠、可解释的自主智能体的重要一步。