跳转至

规划与推理综述

概述

规划与推理是智能体的核心认知能力。从 1960 年代的 STRIPS 规划器到 2020 年代的 LLM 推理模型，智能体"如何思考并制定行动方案"经历了根本性的范式转变。本文梳理这一演进历程，并建立理解后续各专题的框架。

1. 经典规划

1.1 STRIPS 表示

STRIPS（Stanford Research Institute Problem Solver, 1971）定义了经典规划的标准框架：

规划问题 \(\mathcal{P} = \langle S, A, s_0, G \rangle\)：

  • \(S\)：状态集合（命题集合的幂集）
  • \(A\)：动作集合
  • \(s_0 \in S\)：初始状态
  • \(G \subseteq s\)：目标条件

动作定义 \(a = \langle \text{Pre}(a), \text{Add}(a), \text{Del}(a) \rangle\)：

  • \(\text{Pre}(a)\)：前提条件（执行 \(a\) 需要满足的条件）
  • \(\text{Add}(a)\)：添加效果（执行后新增的事实）
  • \(\text{Del}(a)\)：删除效果（执行后移除的事实）

状态转移：

\[ \text{Result}(s, a) = (s \setminus \text{Del}(a)) \cup \text{Add}(a) \quad \text{if } \text{Pre}(a) \subseteq s \]

1.2 PDDL

PDDL（Planning Domain Definition Language）是 STRIPS 的标准化扩展，支持类型、量词、条件效果等：

(define (domain logistics)
  (:predicates (at ?obj ?loc) (in ?obj ?vehicle))
  (:action load
    :parameters (?obj ?vehicle ?loc)
    :precondition (and (at ?obj ?loc) (at ?vehicle ?loc))
    :effect (and (in ?obj ?vehicle) (not (at ?obj ?loc)))))

1.3 经典规划算法

算法 类型 复杂度 特点
前向搜索 状态空间 指数 从初始状态搜索到目标
后向搜索 状态空间 指数 从目标回推到初始状态
GraphPlan 图搜索 多项式构图 构建规划图再提取方案
SAT规划 编译方法 SAT复杂度 转化为布尔满足问题
FF 启发式搜索 启发式引导 放松问题作为启发函数
HTN 层级规划 依赖域 任务分解为子任务

2. 从经典到现代的范式转变

graph LR
    A[STRIPS/PDDL<br/>符号规划<br/>1970s-2000s] --> B[MDP/POMDP<br/>概率规划<br/>1990s-2010s]
    B --> C[深度RL<br/>学习规划<br/>2013-2020]
    C --> D[LLM推理<br/>语言规划<br/>2022-]
    D --> E[推理模型<br/>o1/R1<br/>2024-]

2.1 为什么 LLM 改变了一切？

维度 经典规划 LLM 规划
知识来源 人工编码领域模型 预训练语料中的世界知识
状态表示 形式化逻辑命题 自然语言描述
动作定义 PDDL 算子 自然语言指令 + 工具 API
目标表示 逻辑公式 自然语言任务描述
搜索算法 完备搜索 自回归生成 + 采样
泛化能力 域内完备 跨域但不可靠
失败模式 搜索超时 幻觉、遗漏、循环

LLM 的关键优势：不需要预定义领域模型，可以直接从自然语言任务描述生成行动方案。

LLM 的关键劣势：缺乏正确性保证，无法像经典规划器那样证明方案的最优性或完备性。

3. LLM 推理的核心方法

3.1 方法谱系

graph TD
    ROOT[LLM 推理方法] --> IO[直接输入-输出<br/>Standard Prompting]
    ROOT --> COT[思维链<br/>Chain-of-Thought]
    ROOT --> REACT[ReAct<br/>推理+行动]
    ROOT --> TOT[树搜索<br/>Tree of Thoughts]
    ROOT --> REF[反思<br/>Reflexion]
    ROOT --> PE[计划-执行<br/>Plan-and-Execute]
    ROOT --> RM[推理模型<br/>o1/R1]

    IO --> |添加中间步骤| COT
    COT --> |添加行动| REACT
    COT --> |添加搜索| TOT
    REACT --> |添加经验| REF
    REACT --> |分离规划| PE
    COT --> |内化推理| RM

3.2 方法对比

方法 推理深度 搜索宽度 学习能力 工具使用 计算成本
Standard 单步 1 无 无 低
CoT 多步链 1 无 无 低-中
Self-Consistency 多步链 K条路径 无 无 中
ReAct 多步链 1 无 有 中
ToT 树搜索 B分支 无 可选 高
Reflexion 多步链 1 语言经验 有 中-高
Plan-Execute 两阶段 1 可选 有 中-高
o1/R1 深度链 内部搜索 训练时 可选 高

4. 规划与推理的统一视角

从数学角度看，所有推理和规划方法都可以视为在某个搜索空间中寻找最优路径：

\[ \pi^* = \arg\max_{\pi \in \Pi} \sum_{t=0}^{T} R(s_t, a_t) \]
方法 搜索空间 路径 评估函数
经典规划 状态空间 动作序列 目标满足
MDP 状态-动作空间 策略 期望累积奖励
CoT Token 空间 推理链 输出正确性
ToT 思维节点树 分支路径 LLM 评估分数
MCTS 游戏树 最优走法 UCB + 价值估计

5. 本章内容导引

文件 主题 回答的核心问题
思维链与推理模式 CoT 及其变体 如何让 LLM 展示推理过程？
ReAct与工具推理 推理+行动 如何统一思考和工具使用？
树搜索与蒙特卡洛 搜索方法 如何系统地探索推理空间？
反思与自我改进 经验学习 如何从失败中学习改进？
规划执行框架 工程实现 如何将规划能力工程化？
推理前沿进展 最新进展 推理能力的极限在哪里？

参考文献

  1. Fikes, R.E. & Nilsson, N.J. (1971). STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 2(3-4), 189-208.
  2. Ghallab, M. et al. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  3. Wei, J. et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. NeurIPS 2022.
  4. Yao, S. et al. (2022). ReAct: Synergizing Reasoning and Acting in Language Models. ICLR 2023.
  5. Huang, W. et al. (2022). Language Models as Zero-Shot Planners. ICML 2022.

评论 #