智能体规划算法（Planning）原理拆解：从符号推理到深度强化学习的全链路探索

引言

背景介绍

在人工智能（AI）的宏大版图中，规划（Planning） 是连接“感知世界（Perception）”与“执行动作（Action）”的核心桥梁——它解决的是“为了达成目标，应该做什么、按什么顺序做”的决策问题。从1956年达特茅斯会议上纽厄尔、肖和西蒙的“逻辑理论家（Logic Theorist）”首次尝试自动推理决策，到AlphaGo的蒙特卡洛树搜索（MCTS）结合深度神经网络横扫人类围棋界，再到如今ChatGPT、AutoGPT等大模型驱动的通用智能体（General AI Agent）尝试自主完成复杂任务，规划算法的演进贯穿了AI发展的70余年。

如今，规划算法的应用场景早已超越了传统的游戏AI、机器人路径规划：在自动驾驶中，它需要规划车辆从A到B的宏观导航路径、微观车道变换时序甚至紧急制动的毫秒级动作；在智能制造中，它要调度数百台机器人的协作顺序、优化流水线的生产节拍；在电商供应链中，它得平衡库存、物流与需求预测，制定补货、促销与配送的长期短期策略；在金融量化交易中，它甚至要在毫秒级的市场波动中规划买卖时机与仓位调整——规划能力的强弱，直接决定了智能体的“自主性”与“实用性”。

核心问题

尽管规划算法的应用千差万别，但所有规划问题本质上都可以抽象为同一类核心逻辑：

给定一个初始状态（Initial State）、一组可执行动作（Actions）及其状态转换规则（State Transition Rules）、一个目标条件（Goal Condition），寻找一条动作序列（Action Sequence/Plan），使得从初始状态出发，按该序列依次执行动作后，最终状态能够满足目标条件（如果存在这样的序列的话）；如果存在多条序列，则需要根据代价函数（Cost Function） 或效用函数（Utility Function） 找到“最优”或“近似最优”的序列。

围绕这一核心逻辑，规划算法领域产生了无数令人兴奋的分支与成果，但也面临着三个永恒的、相互制约的核心挑战：

1. 状态空间爆炸（State Space Explosion）：现实世界的状态维度极高（例如自动驾驶需要考虑的状态包括车辆位置、速度、加速度、周围车辆行人的状态、道路状况、天气等），传统的“枚举式”规划（如广度优先搜索BFS、深度优先搜索DFS）根本无法处理；
2. 不确定性（Uncertainty）：现实世界的感知结果、动作执行效果往往是不完全确定的（例如机器人可能会因为地面打滑而走偏，股票价格的预测可能会出错），传统的“确定性规划（Classical Planning）”假设完全不适用；
3. 实时性（Real-time）：很多应用场景（如自动驾驶、量化交易）要求规划算法在毫秒级甚至微秒级内给出决策，而复杂的最优规划算法（如A*的改进版本、马尔可夫决策过程的动态规划解法）往往计算量巨大。

本文将围绕这三大核心挑战，系统性地拆解智能体规划算法的演进脉络、核心原理、数学模型、实现细节以及实际应用。

文章脉络

为了让读者能够循序渐进地理解规划算法，本文将按照以下结构展开：

1. 基础概念：先明确规划问题的形式化定义、关键术语、经典的Benchmark问题，为后续的算法讲解打好基础；
2. 确定性规划算法：从最经典的“状态空间搜索”（BFS/DFS/Dijkstra/A*）讲起，再过渡到更高效的“规划空间搜索”（即STRIPS/ADL等经典规划语言驱动的规划算法，如Graphplan、FF规划器）；
3. 不确定性规划算法：引入马尔可夫决策过程（MDP）作为不确定性规划的数学模型，讲解动态规划（DP）、蒙特卡洛方法（MC）、时序差分学习（TD）、Q学习（Q-Learning）等经典解法，再过渡到部分可观测马尔可夫决策过程（POMDP）；
4. 现代智能体规划算法：讲解结合深度学习的规划算法，包括深度强化学习（DRL）驱动的规划（如DQN、PPO的规划变体）、大语言模型（LLM）驱动的规划（如ReAct、Tree-of-Thoughts、AutoGPT的规划模块）；
5. 实际场景应用：以自动驾驶宏观路径规划、微观行为规划、机器人任务规划为例，详细讲解规划算法在现实世界中的落地；
6. 行业发展与未来趋势：梳理规划算法从1950年代到2020年代的演变历史，分析当前的研究热点与未来的发展方向；
7. 总结与展望：回顾本文的核心内容，总结规划算法的核心思想，展望规划算法在通用人工智能（AGI）中的作用。

基础概念

核心概念

在深入讲解规划算法之前，我们需要先明确规划问题的形式化定义以及一系列关键术语——这是所有规划算法的共同语言。

关键术语

1. 状态（State）：状态是对智能体所处环境的完整或部分描述。在确定性规划中，状态通常是“完全可观测（Fully Observable）”的；在不确定性规划中，状态可能是“部分可观测（Partially Observable）”或“不可观测（Unobservable）”的。
   • 离散状态（Discrete State）：状态的取值是有限的或可数无限的（例如棋盘的棋子位置、机器人在网格中的坐标）；
   • 连续状态（Continuous State）：状态的取值是不可数无限的（例如车辆的速度、加速度、股票的价格）。
2. 初始状态（Initial State, $S_0$）：智能体开始规划时所处的状态。
3. 目标条件（Goal Condition, $G$）：智能体希望达成的状态集合——即规划的终点。目标条件可以是“单一目标状态（Single Goal State）”，也可以是“多个目标状态（Multiple Goal States）”，甚至是“满足某些属性的状态集合（Goal Specification）”。
4. 动作（Action, $a$）：智能体可以执行的操作。动作可以分为“离散动作（Discrete Action）”（例如机器人的“向前走一步”、“向左转90度”）和“连续动作（Continuous Action）”（例如车辆的“油门开度”、“方向盘转角”）。
   • 可执行动作集合（Applicable Actions, $A(s)$）：在状态 $s$ 下，智能体可以执行的所有动作的集合。
5. 状态转换函数（State Transition Function, $T$）：状态转换函数描述了执行动作后环境状态的变化规律。
   • 确定性状态转换函数（Deterministic Transition Function, $T:S\times A\to S$）：在状态 $s$ 下执行动作 $a$，一定会得到唯一的下一个状态 $s^{\prime }=T(s,a)$——这是经典规划的核心假设；
   • 不确定性状态转换函数（Stochastic Transition Function, $T:S\times A\times S^{\prime }\to [0,1]$）：在状态 $s$ 下执行动作 $a$，得到下一个状态 $s^{\prime }$ 的概率是 $T(s,a,s^{\prime })$，且满足 ${\sum }_{s^{\prime }\in S}T(s,a,s^{\prime })=1$——这是不确定性规划的核心假设。
6. 代价函数（Cost Function, $C$）：代价函数描述了执行动作所需要付出的“成本”。
   • 确定性代价函数（Deterministic Cost Function, $C:S\times A\to {\mathbb{R}}^{+}$）：在状态 $s$ 下执行动作 $a$，一定会付出固定的成本 $C(s,a)$；
   • 不确定性代价函数（Stochastic Cost Function, $C:S\times A\times S^{\prime }\to {\mathbb{R}}^{+}$）：在状态 $s$ 下执行动作 $a$ 并转移到状态 $s^{\prime }$，付出的成本是 $C(s,a,s^{\prime })$。
7. 效用函数（Utility Function, $U$）：效用函数描述了智能体对某条动作序列的“偏好程度”——通常是代价函数的相反数（即代价越小，效用越大），或者是长期回报的折扣和（在强化学习中常用）。
8. 动作序列（Action Sequence/Plan, $\pi$）：动作序列是一个有序的动作列表 $\pi =[a_0,a_1,...,a_{n-1}]$，对应的状态序列是 $s_0\to s_1\to ...\to s_n$，其中 $s_{i+1}=T(s_i,a_i)$（确定性规划）或 $s_{i+1}\sim T(s_i,a_i,\cdot )$（不确定性规划）。
   • 可行计划（Feasible Plan）：如果从初始状态 $s_0$ 出发，按动作序列 $\pi$ 执行后，最终状态 $s_n$ 满足目标条件 $G$，则称 $\pi$ 是一条可行计划；
   • 最优计划（Optimal Plan）：在所有可行计划中，效用最大（或代价最小）的计划称为最优计划。

规划问题的形式化定义

基于上述关键术语，我们可以将经典确定性规划问题（Classical Planning Problem） 形式化定义为一个五元组：
$${\mathcal{P}}_{\text{classical}}=(S,A,T,s_0,G)$$
其中：

1. $S$ 是一个有限的离散状态集合；
2. $A$ 是一个有限的离散动作集合；
3. $T:S\times A\to S$ 是一个确定性状态转换函数；
4. $s_0\in S$ 是初始状态；
5. $G\subseteq S$ 是目标状态集合。

经典确定性规划问题的目标是：寻找一条可行计划 $\pi =[a_0,a_1,...,a_{n-1}]$，使得 $s_n=T(s_{n-1},a_{n-1})\in G$。如果需要最优计划，则需要引入代价函数 $C:S\times A\to {\mathbb{R}}^{+}$，并寻找代价最小的可行计划：
$${\pi }^{\ast }=\arg \underset{\pi \in {\Pi }_{\text{feasible}}}{\min }\sum _{i=0}^{n-1}C(s_i,a_i)$$
其中 ${\Pi }_{\text{feasible}}$ 是所有可行计划的集合。

而不确定性规划问题（Stochastic Planning Problem） 通常被形式化定义为一个马尔可夫决策过程（Markov Decision Process, MDP），即一个六元组：
$${\mathcal{P}}_{\text{stochastic}}=(S,A,T,R,\gamma ,s_0)$$
其中：

1. $S$ 是一个状态集合（可以是离散的，也可以是连续的）；
2. $A$ 是一个动作集合（可以是离散的，也可以是连续的）；
3. $T:S\times A\times S^{\prime }\to [0,1]$ 是一个不确定性状态转换函数（即转移概率分布），满足 ${\sum }_{s^{\prime }\in S}T(s,a,s^{\prime })=1$；
4. $R:S\times A\times S^{\prime }\to \mathbb{R}$ 是一个奖励函数（Reward Function）（即效用函数的基础单位），描述了在状态 $s$ 下执行动作 $a$ 并转移到状态 $s^{\prime }$ 后获得的即时奖励；
5. $\gamma \in [0,1]$ 是一个折扣因子（Discount Factor），用于描述未来奖励的“现值”——$\gamma$ 越接近1，智能体越看重未来的长期奖励；$\gamma$ 越接近0，智能体越看重当前的即时奖励；
6. $s_0\in S$ 是初始状态（在更一般的MDP中，初始状态可以是一个概率分布 $P_0(s)$）。

不确定性规划问题的目标是：寻找一个策略（Policy, $\pi$）——策略是一个从状态到动作的映射（确定性策略 $\pi :S\to A$）或概率分布（随机策略 $\pi :S\times A\to [0,1]$）——使得长期回报的期望最大。长期回报（Return, $G_t$）的定义为：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$
其中 $R_{t+k+1}$ 是在时间步 $t+k+1$ 获得的即时奖励。策略 $\pi$ 对应的状态值函数（State Value Function, $V^{\pi }(s)$） 定义为：从状态 $s$ 出发，遵循策略 $\pi$ 执行动作后，长期回报的期望：
$$V^{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$
策略 $\pi$ 对应的动作值函数（Action Value Function, $Q^{\pi }(s,a)$） 定义为：从状态 $s$ 出发，先执行动作 $a$，再遵循策略 $\pi$ 执行动作后，长期回报的期望：
$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$$
不确定性规划问题的最优策略 ${\pi }^{\ast }$ 满足：对于所有的状态 $s\in S$，$V^{{\pi }^{\ast }}(s)={\max }_{\pi }{V}^{\pi }(s)$（最优状态值函数 $V^{\ast }(s)$），且对于所有的状态 $s\in S$ 和动作 $a\in A$，$Q^{{\pi }^{\ast }}(s,a)={\max }_{\pi }{Q}^{\pi }(s,a)$（最优动作值函数 $Q^{\ast }(s,a)$）。

关于MDP的更多细节，我们将在不确定性规划算法章节详细讲解。

经典Benchmark问题

为了方便研究和比较不同的规划算法，学术界提出了一系列经典的Benchmark问题。这些问题通常具有明确的状态空间、动作空间、状态转换规则和目标条件，且难度可以通过调整参数（如网格大小、障碍物数量、棋子数量等）灵活控制。

1. 网格世界（Grid World）

网格世界是最经典、最常用的规划Benchmark问题之一——它是一个二维的离散网格，其中：

• 状态：网格中的每个单元格 $(x,y)$ 都是一个状态；
• 动作：通常包括“上（Up）、下（Down）、左（Left）、右（Right）”四个离散动作（有些版本也会加入“停留（Stay）”动作）；
• 状态转换规则：
  • 在确定性网格世界中，执行动作 $a$ 后，智能体一定会移动到对应的相邻单元格（如果相邻单元格是“可通行的（Free）”）；如果相邻单元格是“障碍物（Obstacle）”或“边界（Boundary）”，则智能体停留在当前单元格；
  • 在不确定性网格世界中，执行动作 $a$ 后，智能体有 $p$ 的概率移动到对应的相邻单元格，有 $1-p$ 的概率移动到其他相邻单元格（例如 $p=0.8$，$0.1$ 的概率向左，$0.1$ 的概率向右，当执行“向上”动作时）；
• 目标条件：通常是到达某个或某些“目标单元格（Goal Cell）”；
• 代价函数/奖励函数：
  • 通常每移动一步的代价是 $1$（或奖励是 $-1$），到达目标单元格的代价是 $0$（或奖励是 $+100$），撞到障碍物的代价是 $+10$（或奖励是 $-100$）。

网格世界的优点是：状态空间和动作空间非常简单，容易可视化和理解；难度可以通过调整网格大小、障碍物数量、不确定性概率等参数灵活控制；既可以用于测试确定性规划算法，也可以用于测试不确定性规划算法。

2. 积木世界（Blocks World）

积木世界是经典规划领域（符号推理）最常用的Benchmark问题之一——它模拟了一个用积木搭建城堡的场景，其中：

• 状态：状态是对所有积木位置的描述——每个积木要么放在“桌子（Table）”上，要么放在另一个积木的“顶部（Top）”；且每个积木的顶部最多只能有一个积木（即积木是“堆叠（Stacked）”的，不能“交叉（Crossed）”）；
• 动作：通常包括两个基本动作（有些版本会拆分成四个更细的动作）：
  • Stack(x, y)：将积木 $x$ 放在积木 $y$ 的顶部——前提条件（Precondition）是：积木 $x$ 的顶部是空的（Clear(x)）、积木 $y$ 的顶部是空的（Clear(y)）、积木 $x$ 不在桌子上（On(x, Table) 为假）；效果（Effect）是：积木 $x$ 在积木 $y$ 的顶部（On(x, y)）、积木 $y$ 的顶部不再是空的（¬Clear(y)）、积木 $x$ 不再在原来的位置（¬On(x, z)，其中 $z$ 是原来的支撑物）、原来的支撑物 $z$ 的顶部变为空的（Clear(z)）；
  • Unstack(x, y)：将积木 $x$ 从积木 $y$ 的顶部拿起来——前提条件是：积木 $x$ 的顶部是空的（Clear(x)）、积木 $x$ 在积木 $y$ 的顶部（On(x, y)）；效果是：积木 $x$ 不在积木 $y$ 的顶部（¬On(x, y)）、积木 $y$ 的顶部变为空的（Clear(y)）、积木 $x$ 被拿在手里（Holding(x)）；
  • Putdown(x)：将手里的积木 $x$ 放在桌子上——前提条件是：手里拿着积木 $x$（Holding(x)）；效果是：手里不再拿着积木 $x$（¬Holding(x)）、积木 $x$ 在桌子上（On(x, Table)）、积木 $x$ 的顶部是空的（Clear(x)）；
  • Pickup(x)：将桌子上的积木 $x$ 拿起来——前提条件是：积木 $x$ 的顶部是空的（Clear(x)）、积木 $x$ 在桌子上（On(x, Table)）、手里没有拿任何积木（¬Holding(y) 对所有 $y$）；效果是：积木 $x$ 不在桌子上（¬On(x, Table)）、手里拿着积木 $x$（Holding(x)）；
• 状态转换规则：确定性的——执行某个动作后，状态会根据动作的“前提条件”和“效果”发生变化：如果前提条件满足，则状态变为效果描述的状态；如果前提条件不满足，则动作不可执行；
• 目标条件：通常是让积木处于某个特定的堆叠状态（例如“积木A在积木B的顶部，积木B在积木C的顶部，积木C在桌子上”）；
• 代价函数：通常每执行一个动作的代价是 $1$，最优计划是动作数量最少的可行计划。

积木世界的优点是：它是一个典型的“符号推理”问题，非常适合测试经典规划语言（如STRIPS、ADL、PDDL）驱动的规划算法；难度可以通过调整积木的数量灵活控制（积木数量越多，状态空间爆炸越严重）。

3. 旅行商问题（Traveling Salesman Problem, TSP）

旅行商问题是组合优化领域最经典的问题之一，也可以被看作是一个特殊的规划问题——其中：

• 状态：状态是对当前位置和已访问城市集合的描述——例如 $s=(current\_city,visited\_cities)$；
• 动作：动作是从当前位置移动到一个未访问的城市；
• 状态转换规则：确定性的——执行动作 $a$（移动到城市 $c$）后，当前位置变为 $c$，已访问城市集合加入 $c$；
• 目标条件：已访问所有城市，且当前位置回到起点；
• 代价函数：移动的总距离（或总时间、总费用），最优计划是总代价最小的可行计划。

旅行商问题的优点是：它是一个典型的“NP-hard”问题（即不存在多项式时间的最优算法，除非P=NP），非常适合测试近似规划算法（如贪心算法、模拟退火算法、遗传算法、蚁群算法等）。

4. 俄罗斯方块（Tetris）

俄罗斯方块是一个经典的视频游戏，也可以被看作是一个不确定性规划问题——其中：

• 状态：状态是对当前游戏板（Board）的布局、当前下落的方块（Piece）的类型和位置、下一个方块的类型的描述；
• 动作：动作是对当前下落方块的操作——包括“左移（Left）、右移（Right）、旋转（Rotate）、加速下落（Soft Drop）、直接下落（Hard Drop）”；
• 状态转换规则：部分不确定性的——下一个方块的类型是随机的（服从某种概率分布）；
• 目标条件：尽可能地消除更多的行，获得更高的分数；
• 奖励函数：每消除一行获得一定的奖励（例如消除1行得100分，消除2行得300分，消除3行得500分，消除4行得800分），游戏结束（方块堆到顶部）获得巨大的惩罚（例如-10000分）。

俄罗斯方块的优点是：它是一个典型的“高维状态空间、部分不确定性、实时性要求高”的规划问题，非常适合测试深度强化学习驱动的规划算法。

问题背景：规划算法的起源与分类

起源

规划算法的起源可以追溯到1950年代的人工智能符号主义（Symbolism） 学派——符号主义学派认为，人工智能的核心是“知识表示（Knowledge Representation）”和“自动推理（Automated Reasoning）”，而规划就是“自动推理”的一个重要应用。

1956年，纽厄尔、肖和西蒙在达特茅斯会议上展示了“逻辑理论家（Logic Theorist）”——这是世界上第一个能够自动证明数学定理的程序，也是第一个尝试自动推理决策的程序。1959年，他们又开发了“通用问题求解器（General Problem Solver, GPS）”——这是世界上第一个通用的规划程序，它使用“手段-目的分析（Means-Ends Analysis, MEA）”的方法来解决问题：即先比较当前状态和目标状态的差异，然后选择一个能够减少差异的动作，重复这个过程直到当前状态等于目标状态。

尽管GPS的通用性很强，但它的效率很低，只能解决一些非常简单的问题（如汉诺塔问题）。为了提高规划算法的效率，1971年，斯坦福大学的菲克斯（Fikes）和尼尔森（Nilsson）开发了“斯坦福研究所问题求解器（Stanford Research Institute Problem Solver, STRIPS）”——这是世界上第一个专门用于规划的程序，它提出了一套经典规划语言（STRIPS语言） 来表示规划问题的状态、动作、前提条件和效果，并使用“状态空间搜索”和“规划空间搜索”相结合的方法来求解规划问题。STRIPS的出现标志着经典规划领域（Classical Planning） 的正式诞生。

分类

根据不同的分类标准，规划算法可以分为不同的类型：

1. 根据状态和动作的确定性分类：
   • 确定性规划算法（Classical Planning Algorithms）：假设状态是完全可观测的，动作执行效果是完全确定的——例如BFS、DFS、Dijkstra、A*、Graphplan、FF规划器；
   • 不确定性规划算法（Stochastic Planning Algorithms）：假设状态是部分可观测的或不可观测的，动作执行效果是不确定的——例如MDP的动态规划解法、蒙特卡洛方法、时序差分学习、Q学习、POMDP的解法；
2. 根据搜索空间的分类：
   • 状态空间搜索算法（State-Space Search Algorithms）：在“状态空间”中搜索——即从初始状态出发，不断执行动作，生成新的状态，直到找到目标状态——例如BFS、DFS、Dijkstra、A*；
   • 规划空间搜索算法（Plan-Space Search Algorithms）：在“规划空间”中搜索——即从一个“空规划”或“部分规划”出发，不断添加、删除或修改动作，直到找到一个可行规划——例如STRIPS的原始算法、NOAH规划器、Nonlin规划器；
   • 规划图搜索算法（Planning-Graph Search Algorithms）：先构建一个“规划图（Planning Graph）”——规划图是一个分层的图，包含“状态层（State Levels）”和“动作层（Action Levels）”交替出现的结构——然后在规划图中搜索可行规划——例如Graphplan、IPP规划器；
3. 根据是否需要先验知识分类：
   • 基于模型的规划算法（Model-Based Planning Algorithms）：需要知道环境的“模型”——即状态转换函数 $T$ 和奖励函数 $R$——例如动态规划解法、Dijkstra、A*；
   • 无模型的规划算法（Model-Free Planning Algorithms）：不需要知道环境的模型，只需要通过与环境的交互来学习——例如蒙特卡洛方法、时序差分学习、Q学习；
4. 根据是否结合机器学习分类：
   • 传统规划算法（Traditional Planning Algorithms）：不结合机器学习，完全基于符号推理或搜索——例如BFS、DFS、Dijkstra、A*、Graphplan、FF规划器；
   • 现代规划算法（Modern Planning Algorithms）：结合机器学习（尤其是深度学习）——例如深度强化学习驱动的规划、大语言模型驱动的规划。

确定性规划算法

确定性规划算法是规划算法领域的基础——它假设状态是完全可观测的，动作执行效果是完全确定的，因此规划问题的形式化定义相对简单，求解方法也相对成熟。

本节将按照“搜索空间的分类”，依次讲解状态空间搜索算法、规划空间搜索算法和规划图搜索算法。

状态空间搜索算法

状态空间搜索算法是最直观、最容易理解的规划算法——它将规划问题转化为一个“图搜索问题”：

• 图的节点（Node） 对应规划问题的状态；
• 图的边（Edge） 对应规划问题的动作；
• 边的权重（Weight） 对应动作的代价；
• 规划问题的初始状态对应图的起始节点；
• 规划问题的目标状态集合对应图的目标节点集合；
• 规划问题的可行计划对应图中从起始节点到目标节点的路径；
• 规划问题的最优计划对应图中从起始节点到目标节点的最短路径（权重之和最小的路径）。

因此，所有经典的图搜索算法（如BFS、DFS、Dijkstra、A*）都可以直接用于求解确定性规划问题。

1. 无信息搜索算法（Uninformed Search Algorithms）

无信息搜索算法（也称为“盲目搜索算法（Blind Search Algorithms）”）——它们不需要任何关于目标状态的“先验信息（Heuristic Information）”，只按照固定的顺序遍历状态空间。

（1）广度优先搜索（Breadth-First Search, BFS）

广度优先搜索是一种“层优先”的搜索算法——它从起始节点出发，先遍历所有距离起始节点“1步”的节点，再遍历所有距离起始节点“2步”的节点，依此类推，直到找到目标节点。

算法流程

BFS的算法流程可以用以下的伪代码描述：

输入：起始节点 s0，目标节点集合 G，可执行动作函数 A(s)，状态转换函数 T(s, a)
输出：从 s0 到 G 中某个节点的最短路径（动作序列），如果不存在则返回 None

1. 初始化：
   a. 创建一个空的队列 queue（FIFO，先进先出）
   b. 将起始节点 s0 加入队列 queue
   c. 创建一个空的字典 visited，用于记录已访问的节点及其父节点和动作：visited[s0] = (None, None)
2. 循环：
   a. 如果队列 queue 为空，则返回 None（没有找到可行计划）
   b. 从队列 queue 中取出队首节点 s（出队）
   c. 如果 s 属于目标节点集合 G，则回溯 visited 字典，生成动作序列并返回
   d. 遍历 s 的所有可执行动作 a ∈ A(s)：
      i. 计算下一个状态 s' = T(s, a)
      ii. 如果 s' 不在 visited 字典中：
          - 将 s' 加入 visited 字典：visited[s'] = (s, a)
          - 将 s' 加入队列 queue（入队）
3. 回溯动作序列的函数（backtrack(visited, s_goal)）：
   a. 初始化一个空的动作序列 plan
   b. 当前节点 current = s_goal
   c. 循环：
      i. 如果 current 的父节点是 None，则跳出循环
      ii. 将当前节点的动作 a 加入 plan 的开头（因为回溯是从目标节点到起始节点的）
      iii. 将当前节点 current 更新为其父节点
   d. 返回 plan

数学模型

BFS的搜索过程可以用队列的状态变化来描述——设 $Q_k$ 为第 $k$ 层遍历完成后队列的状态，$V_k$ 为第 $k$ 层遍历完成后已访问节点的集合，则：
{Q0={s0}V0={s0}Qk+1=⋃s∈Qk({T(s,a)∣a∈A(s),T(s,a)∉Vk})Vk+1=Vk∪Qk+1 \begin{cases} Q_0 = \{s_0\} \\ V_0 = \{s_0\} \\ Q_{k+1} = \bigcup_{s \in Q_k} \left( \{ T(s,a) | a \in A(s), T(s,a) \notin V_k \} \right) \\ V_{k+1} = V_k \cup Q_{k+1} \end{cases} ⎩⎨⎧​Q0​={s0​}V0​={s0​}Qk+1​=⋃s∈Qk​​({T(s,a)∣a∈A(s),T(s,a)∈/Vk​})Vk+1​=Vk​∪Qk+1​​
当 $Q_k\cap G\ne \varnothing$ 时，搜索终止，此时的 $k$ 就是最短路径的长度（动作数量）。

算法流程图

我们可以用Mermaid流程图来更直观地展示BFS的算法流程：

算法优缺点

BFS的优点是：

• 完备性（Completeness）：如果存在可行计划，BFS一定能找到它；
• 最优性（Optimality）：如果所有动作的代价都是相等的（即单位代价），BFS一定能找到最短的可行计划（动作数量最少的计划）。

BFS的缺点是：

• 时间复杂度高：设 $b$ 为状态空间的“分支因子（Branching Factor）”——即每个状态的平均可执行动作数量；$d$ 为最短可行计划的长度（动作数量）——则BFS的时间复杂度为 $O(b^d)$；
• 空间复杂度高：BFS需要同时存储所有已访问的节点和队列中的节点——而队列中的节点数量最多为 $b^d$（在最坏情况下，即最后一层才找到目标节点）——因此BFS的空间复杂度也为 $O(b^d)$。

由于时间复杂度和空间复杂度都是指数级的，BFS只能用于解决一些非常简单的规划问题（如网格大小为10x10、没有障碍物的网格世界）——对于稍微复杂一点的问题，BFS就会因为“状态空间爆炸”而无法处理。

（2）深度优先搜索（Depth-First Search, DFS）

深度优先搜索是一种“深度优先”的搜索算法——它从起始节点出发，沿着一条路径一直向下搜索，直到找到目标节点，或者遇到“死胡同（Dead End）”（即当前状态没有可执行的未访问动作），然后回溯到上一个节点，继续搜索其他路径。

算法流程

DFS的算法流程与BFS非常相似，唯一的区别是：BFS使用“队列（FIFO）”来存储待访问的节点，而DFS使用“栈（Stack，LIFO，后进先出）”来存储待访问的节点。

DFS的伪代码如下：

输入：起始节点 s0，目标节点集合 G，可执行动作函数 A(s)，状态转换函数 T(s, a)
输出：从 s0 到 G 中某个节点的路径（动作序列），如果不存在则返回 None

1. 初始化：
   a. 创建一个空的栈 stack（LIFO，后进先出）
   b. 将起始节点 s0 加入栈 stack
   c. 创建一个空的字典 visited，用于记录已访问的节点及其父节点和动作：visited[s0] = (None, None)
2. 循环：
   a. 如果栈 stack 为空，则返回 None（没有找到可行计划）
   b. 从栈 stack 中取出栈顶节点 s（出栈）
   c. 如果 s 属于目标节点集合 G，则回溯 visited 字典，生成动作序列并返回
   d. 遍历 s 的所有可执行动作 a ∈ A(s)：
      i. 计算下一个状态 s' = T(s, a)
      ii. 如果 s' 不在 visited 字典中：
          - 将 s' 加入 visited 字典：visited[s'] = (s, a)
          - 将 s' 加入栈 stack（入栈）
3. 回溯动作序列的函数（backtrack(visited, s_goal)）：
   与BFS的回溯函数完全相同

除了“栈”的实现方式，DFS还可以用“递归（Recursion）”来实现——递归的本质就是“系统栈（System Stack）”。递归实现的DFS伪代码如下：

输入：当前节点 s，目标节点集合 G，可执行动作函数 A(s)，状态转换函数 T(s, a)，已访问字典 visited
输出：从 s 到 G 中某个节点的路径（动作序列），如果不存在则返回 None

1. 如果 s 属于目标节点集合 G，则返回空列表 []（因为当前节点就是目标节点，不需要执行任何动作）
2. 遍历 s 的所有可执行动作 a ∈ A(s)：
   a. 计算下一个状态 s' = T(s, a)
   b. 如果 s' 不在 visited 字典中：
       i. 将 s' 加入 visited 字典：visited[s'] = (s, a)
       ii. 递归调用 dfs_recursive(s', G, A, T, visited)，得到子路径 sub_plan
       iii. 如果 sub_plan 不是 None，则将 a 加入 sub_plan 的开头，返回 [a] + sub_plan
3. 如果所有动作都遍历完了，仍然没有找到可行计划，则返回 None

需要注意的是：递归实现的DFS需要在调用前初始化visited字典，并将起始节点s0加入visited字典。

数学模型

递归实现的DFS的搜索过程可以用递归函数的调用栈来描述——设 $Call(s)$ 为对节点 $s$ 的递归调用，则：
$$Call(s)=\{\begin{array}{ll}[]& \text{if }s\in G\\ [a]+Call(T(s,a))& \text{if }\exists a\in A(s),T(s,a)\notin V,Call(T(s,a))\ne None\\ None& \text{otherwise}\end{array}$$
其中 $V$ 是已访问节点的集合。

算法流程图

我们可以用Mermaid流程图来展示递归实现的DFS的算法流程：

算法优缺点

DFS的优点是：

• 空间复杂度低：DFS只需要存储当前路径上的节点和已访问的节点——而当前路径上的节点数量最多为 $m$（$m$ 为状态空间的最大深度）——因此DFS的空间复杂度为 $O(bm)$（$b$ 为分支因子），远低于BFS的 $O(b^d)$；
• 实现简单：无论是用栈还是用递归，DFS的实现都非常简单。

DFS的缺点是：

• 不完备性（Incompleteness）：如果状态空间是“无限深度（Infinite Depth）”的（例如网格世界没有边界，智能体可以一直向右走），DFS可能会沿着一条无限的路径一直向下搜索，永远找不到目标节点；
• 不最优性（Suboptimality）：DFS找到的第一条可行计划不一定是最短的可行计划（单位代价下），也不一定是代价最小的可行计划（非单位代价下）；
• 可能会陷入“死循环（Infinite Loop）”：如果没有已访问节点的记录（visited字典），DFS可能会在一个环（Cycle）中反复搜索，永远无法跳出。

为了缓解DFS的不完备性和不最优性，学术界提出了一些改进的DFS算法，例如深度受限搜索（Depth-Limited Search, DLS）、迭代加深深度优先搜索（Iterative Deepening Depth-First Search, IDDFS）。

（3）深度受限搜索（Depth-Limited Search, DLS）

深度受限搜索是DFS的一个改进版本——它给DFS设置了一个“最大深度限制（Maximum Depth Limit, $l$）”：当搜索深度超过 $l$ 时，就停止沿着这条路径搜索，回溯到上一个节点。

DLS的伪代码与递归实现的DFS非常相似，唯一的区别是：它需要多传入一个“当前深度（Current Depth, $k$）”的参数，并在递归调用时检查当前深度是否超过最大深度限制 $l$。

DLS的伪代码如下：

输入：当前节点 s，当前深度 k，最大深度限制 l，目标节点集合 G，可执行动作函数 A(s)，状态转换函数 T(s, a)，已访问字典 visited
输出：从 s 到 G 中某个节点的路径（动作序列），如果不存在则返回 None

1. 如果 s 属于目标节点集合 G，则返回空列表 []
2. 如果 k >= l，则返回 None（超过最大深度限制）
3. 遍历 s 的所有可执行动作 a ∈ A(s)：
   a. 计算下一个状态 s' = T(s, a)
   b. 如果 s' 不在 visited 字典中：
       i. 将 s' 加入 visited 字典：visited[s'] = (s, a)
       ii. 递归调用 dls_recursive(s', k+1, l, G, A, T, visited)，得到子路径 sub_plan
       iii. 如果 sub_plan 不是 None，则将 a 加入 sub_plan 的开头，返回 [a] + sub_plan
4. 如果所有动作都遍历完了，仍然没有找到可行计划，则返回 None

需要注意的是：递归实现的DLS需要在调用前初始化visited字典，并将起始节点s0加入visited字典，当前深度k初始化为0。

算法优缺点

DLS的优点是：

• 避免了无限深度搜索：由于设置了最大深度限制 $l$，DLS不会沿着一条无限的路径一直向下搜索；
• 空间复杂度仍然很低：与DFS相同，DLS的空间复杂度为 $O(bl)$。

DLS的缺点是：

• 仍然不完备：如果最短可行计划的长度 $d>l$，则DLS无法找到可行计划；
• 仍然不最优：即使找到可行计划，也不一定是最短的或代价最小的；
• 需要预先知道最大深度限制 $l$：如果 $l$ 设置得太小，会找不到可行计划；如果 $l$ 设置得太大，又会浪费计算资源。

为了解决DLS需要预先知道最大深度限制的问题，学术界提出了迭代加深深度优先搜索（IDDFS）。

（4）迭代加深深度优先搜索（Iterative Deepening Depth-First Search, IDDFS）

迭代加深深度优先搜索是DFS和BFS的“结合体”——它从最大深度限制 $l=0$ 开始，不断调用DLS，每次将最大深度限制 $l$ 增加1，直到找到可行计划为止。

IDDFS的伪代码如下：

输入：起始节点 s0，目标节点集合 G，可执行动作函数 A(s)，状态转换函数 T(s, a)
输出：从 s0 到 G 中某个节点的最短路径（动作序列），如果不存在则返回 None

1. 初始化最大深度限制 l = 0
2. 循环：
   a. 初始化已访问字典 visited，将 s0 加入 visited：visited[s0] = (None, None)
   b. 调用 dls_recursive(s0, 0, l, G, A, T, visited)，得到计划 plan
   c. 如果 plan 不是 None，则返回 plan
   d. 如果 l 已经达到了“合理的最大深度”（例如状态空间的最大可能深度），则返回 None
   e. 将最大深度限制 l 增加 1：l = l + 1

算法优缺点

IDDFS的优点是：

• 完备性：与BFS相同，如果存在可行计划，IDDFS一定能找到它；
• 最优性：与BFS相同，如果所有动作的代价都是相等的（单位代价），IDDFS一定能找到最短的可行计划；
• 空间复杂度低：与DFS相同，IDDFS的空间复杂度为 $O(bd)$（$d$ 为最短可行计划的长度），远低于BFS的 $O(b^d)$。

IDDFS的缺点是：

• 会重复搜索之前的层：每次调用DLS时，都会重新搜索之前所有深度小于 $l$ 的层——例如当 $l=3$ 时，会搜索深度0、1、2、3的层；当 $l=4$ 时，又会重新搜索深度0、1、2、3、4的层——因此IDDFS的时间复杂度比BFS略高，但仍然是 $O(b^d)$（指数级的时间复杂度在实际应用中