书名Planning Algorithms作者Steven M. LaValle链接https://lavalle.pl/planning/阅读章节Chapter 2 - Discrete Planning导读机器人导航、游戏 AI 寻路、魔方自动复原——这些看似毫无关联的问题本质上都在回答同一件事如何在一个庞大的状态空间中高效找到从起点到目标的路径这个问题之所以值得关注是因为它是所有“智能决策”系统的算法基石至今仍是工业界路径规划的标配方案。读完这篇分享你将建立起“统一图搜索”的思维框架并真正搞懂 BFS、DFS、Dijkstra、A* 这些经典算法各自的适用场景与权衡取舍。我们先建立一个整体认知。第2章“离散规划”是全书算法部分的基石主要探讨如何在离散状态空间中通过搜索算法解决规划问题。它的核心思路是把规划问题抽象为在一个有向图状态转移图中寻找从初始状态到目标的路径。围绕这条主线本章依次展开三层内容第一层是基础的搜索策略包括广度优先搜索BFS、深度优先搜索DFS以及 Dijkstra 算法第二层进阶到基于动态规划的值迭代方法前向与后向迭代和引入启发式信息的 A* 算法用来解决最优规划问题第三层则面向大规模状态空间介绍 STRIPS 模型和规划图Planning Graph这种隐式表示方法。抓住这三层就抓住了整章的脉络。1. 核心主题从物理世界到状态空间理解整章的钥匙只有一个词——“离散化”。虽然现实世界通常是连续的但我们很快会发现许多规划问题可以甚至必须被建模为离散状态空间中的搜索问题。•物理到抽象的映射无论是下国际象棋离散状态还是移动机器人连续状态都可以统一抽象为在一个巨大的图中寻找一条从初始状态节点到目标状态节点的路径。•图搜索的本质规划算法的本质就是图搜索Graph Search。本章要回答的核心问题就是两个如何构建这个图状态转移图以及如何高效地遍历它。2. 规划问题的四大要素在动手搜索之前我们得先把问题“形式化”。作者在 2.1 节给出了离散规划问题的标准定义Formulation 2.1这是后续所有算法的公用语言务必先记住这四样东西要素描述状态空间 (X)所有可能情况的集合。可以是有限的如魔方状态或无限的如网格世界。动作空间 (U(x))在状态 x 下可以执行的所有动作集合。动作会改变系统的状态。状态转移函数 (f)定义了动作的效果x f(x, u)。即在状态 x 执行动作 u 后系统会转移到什么状态。初始与目标状态x_I起点和 X_G终点集合。规划的任务就是从 x_I 出发通过一系列动作到达 X_G 中的任意状态。3. 核心算法搜索策略有了形式化定义接下来进入正题——搜索。本章的算法可以清晰地分成两大类可行规划Finding Any Path只要找到一条路就行和最优规划Finding The Best Path必须找到成本最低的路。①可行规划目标是找到任意一条从起点到终点的路径。·广度优先搜索 (BFS)逐层扩展像涟漪一样向外扩散。它最大的优点是保证能找到最短路径步数最少代价是内存消耗大。·深度优先搜索 (DFS)一条路走到黑碰壁再回溯。内存消耗小但代价是不一定能找到最短路径甚至在无限图中可能直接迷失。·Dijkstra 算法这是从“可行搜索”跨向“最优搜索”的桥梁。它通过维护一个优先队列Priority Queue总是优先扩展“当前成本最低”的节点从而保证找到的路径是成本最优的。•最优规划目标升级了要找到一条累积成本最小的路径。②动态规划 (Dynamic Programming, DP)这是本章的重头戏作者重点介绍了值迭代Value Iteration方法。▪思想这里要用一点逆向思维——从目标状态开始反向计算每一个状态到目标的“最优代价”Cost-to-Go, G*。▪Bellman 方程整个方法的核心递推公式一句话概括就是——当前状态的最优代价 min{当前动作代价 下一状态的最优代价}。▪前向 vs 后向算法可以从初始状态正向推演Forward也可以从目标状态反向推演Backward两种视角殊途同归。③**A\* 算法可以把它理解为 Dijkstra 算法的“增强版”。关键改进是引入了启发式函数**Heuristic Function, h(x)用来估算当前点到目标的剩余成本。这一点点“方向感”能大大减少搜索的节点数。▪关键点这里有个非常重要的结论——如果启发函数 h(x) 是一致的Consistent且可采纳的Admissible即不过高估计真实代价A\* 算法就能像光速一样直达目标同时保证最优性。4. 高级表示逻辑与规划前面讲的所有算法都默认我们能“看见”整张图。但当状态空间巨大时比如机械臂的所有关节组合显式地把所有状态列出来根本不现实。这时候就需要一个更进阶的思路——隐式表示Implicit Representation。①STRIPS 模型这是一种非常经典的逻辑表示法。◦状态由一组谓词Predicates的真值构成例如On(A, Table) 为真。◦动作由前提条件Preconditions和效果Effects定义。只有当所有前提条件都满足时动作才能执行。◦优势核心思想是“按需展开”——不需要显式构建整个图而是在搜索过程中通过逻辑推演动态“生成”图的局部结构。②规划图 (Planning Graph)由 Blum 和 Furst 提出是一种更紧凑的数据结构专门用来表示状态和动作之间的依赖关系。◦分层结构图由交替的“文字层”Literals和“动作层”Operators组成。◦互斥关系 (Mutex)这里有个巧妙的设计——规划图不仅记录了什么可能发生还记录了什么不可能同时发生互斥。这些互斥信息为后续搜索提供了强大的剪枝依据。5. 关键要点回顾三个核心结论◦统一视角无论问题是简单的迷宫寻路Example 2.1还是复杂的魔方复原Example 2.2在数学上它们都是同一个问题——在图中找路径。◦算法权衡没有银弹。BFS 内存大但最优针对步数DFS 内存小但不一定最优Dijkstra/A\* 能处理带权图成本最优但依赖一个好的启发函数。◦维度灾难这里也要泼一盆冷水——离散规划有其本质局限那就是状态空间爆炸。当变量很多时如机械臂的多个关节状态数会呈指数级增长NP-hard。这也是后续章节必须引入连续空间与采样方法的根本动因。6. 技术启示与应用前景回过头看整章其实只讲了一件事把规划问题统一抽象为图搜索。从这个统一视角出发我们看清了各算法在内存消耗、最优性、完备性之间的权衡也触碰到了离散方法的天花板——维度灾难。这套理论至今生命力旺盛。在确定性、已知环境的规划场景中A\* 和 Dijkstra 因其完备性Completeness与最优性Optimality仍是游戏寻路 AI、机器人栅格导航、物流路径优化的工业标配STRIPS 模型则是现代任务规划与符号 AI 的源头。更重要的是本章建立的“状态—动作—转移—代价”框架正是后续连续空间规划、采样式规划RRT/PRM乃至现代强化学习MDP、Bellman 方程、值迭代的共同语言。掌握它就拿到了通往整个规划算法领域的钥匙。