机器人如何自主决策？自动驾驶、人形机器人这些热门方向背后，都绕不开同一个核心问题——规划（Planning）。本次分享带大家走进 LaValle 的经典著作《Planning Algorithms》，从第一章入手，拆解规划问题的七大基本要素，建立对规划算法领域的整体认知。读完你会明白：为什么状态空间、动作、转移函数这些抽象概念，是设计任何智能系统的起点。

书名：Planning Algorithms

作者：Steven M. LaValle

链接：https://lavalle.pl/planning/

阅读章节：Chapter 1 - Introductory Material

第1章为整本书描绘了宏大的蓝图。它明确了“规划”的核心问题，展示了其广泛的应用前景，并清晰地介绍了全书的主题结构、各部分的依赖关系以及核心的抽象概念（如状态、动作、计划、策略、不确定性）。借助本章，我们可以快速定位自己感兴趣的主题，建立起对规划算法领域的整体认知。

---

书籍简介

《Planning Algorithms》由 Steven M. LaValle 撰写、剑桥大学出版社于 2006 年出版，在业内享有极高地位，被广泛誉为“运动规划圣经”。作为机器人规划算法中理论描述最为清晰、全面且基础性的专业参考文献，建议 SLAM / V-SLAM / Path Planning 等方向的同学将其作为入门必读。多位国际知名学者（如乌得勒支大学 Mark Overmars 教授、比萨大学 Antonio Bicchi 教授）都高度评价该书，认为它成功整合了多个领域的算法，是对当前运动规划研究现状的极佳概述，是研究人员案头必备的经典。

这本书的核心价值在于：它提供了一个清晰、连贯的数学框架，把机器人学、人工智能、控制理论以及算法等多个相对独立的学科巧妙地结合在一起。书中系统介绍了规划领域的基础知识，包括离散规划、连续状态空间中的运动规划、决策论规划（如马尔可夫决策过程）以及微分约束下的规划等。这些底层数学概念、拓扑学基础以及经典算法原理具有极强的普适性和长远的生命力。

值得一提的是，从学术界的最新动态来看，LaValle 教授及其团队至今仍保持着极高的学术活跃度，持续在机器人运动规划、反馈规划、虚拟现实与遥操作等前沿领域发表高水平论文。这说明该书所奠定的理论体系在当下依然适用，并且仍在不断指导并推动着前沿研究。因此，无论作为高年级本科生和研究生的教科书，还是科研人员的案头参考书，它今天依然具有极高的学习与参考价值。

1. 核心主题：三大领域的融合

LaValle 在序言和第一章中反复强调，本书的背景是 机器人学（Robotics）、人工智能（AI） 和 控制理论（Control Theory） 三者的交汇。理解这一点，就抓住了全书的灵魂。

① 历史视角

· Robotics：早期关注几何路径规划（如“移动钢琴问题”），后来引入了不确定性和多体系统。

· AI：早期关注离散逻辑搜索（如国际象棋），后来引入了概率决策（MDPs）和博弈论。

· Control Theory：早期关注稳定性，后来扩展到为非线性系统计算可行轨迹。

② 本书的定义

作者把“规划”定义为一种决策过程。他特意指出，书中不区分“规划”和“控制”的高低层级，也不强调“高”或“低”的概念——两者都指代某种形式的决策。这一统一视角，正是后续展开的基础。

2. 规划问题的七大基本要素（Basic Ingredients）

这是第一章最核心的干货。作者将任何规划问题——无论是下棋还是开车——都抽象为以下七个数学要素。理解这些概念，对阅读后续章节至关重要。

要素	英文术语	详细解析
状态空间	State Space (X)	所有可能情况的集合。可以是离散的（如魔方的每一种组合）或连续的（如机器人在平面上的坐标 (x,y)）。规划算法通常处理的是隐式定义的空间，而非显式列出所有点。
时间	Time	决策必须随时间序列执行。时间可以是显式的（如“第5秒”）或隐式的（如“第5步”），可以是离散的（t=1,2...）或连续的。
动作	Actions (U)	改变状态的操作。在 AI 中叫操作符，在控制理论中叫输入。动作可以由决策者选择，也可以由“Nature”（自然/环境）选择（代表不确定性）。
初始与目标	Initial & Goal	规划的起点 (x_I) 和终点 (X_G)。目标可以是一个具体的点，也可以是一组状态。
准则	Criterion	评价标准，分为两类：1. 可行性（Feasibility）：能否到达目标？2. 最优性（Optimality）：如何以最小成本/最短时间到达？
状态转移函数	Transition Function	描述动作如何改变状态的规则，即 x' = f(x, u)。这是模型的核心动力学。
规划/计划	Plan (π)	具体的策略。可以是动作序列，也可以是状态反馈函数（如：看到墙就右转）。

3. 算法、规划器与计划（Algorithms, Planners, and Plans）

这一节作者探讨了“算法”的本质，特别是图灵机模型在物理世界中的局限性。这部分内容提醒我们：理论与现实之间，存在一道必须跨越的鸿沟。

① 图灵机的局限（The Church-Turing Thesis）

· 传统算法（图灵机）假设输入是一条静态的磁带。但在物理世界中，机器（Machine）和环境（Environment）是紧密耦合的（如图 1.16 所示）。

· 问题：如果环境在算法运行时发生了变化（如有人移动了障碍物），图灵机模型很难处理这种实时交互。

② 在线算法（On-line Algorithms）

为了解决上述问题，引入了在线算法模型。机器通过传感器（Sensing） 获取环境信息，通过执行器（Actuation） 改变环境。

③ 规划的三种用途

· 执行（Execution）：机器自主执行预设计划。

· 精化（Refinement）：计划作为子程序被优化（例如：先规划几何路径，再优化速度曲线）。

· 分层包含（Hierarchical Inclusion）：将一个计划打包成一个动作，用于更高层的计划（例如：把“走路”封装成一个动作，用于“去厨房”这个高层任务）。

4. 本书的结构与阅读路线图

第一章末尾提供了全书的结构概览，对于制定学习计划非常有帮助。建议大家在正式深入之前，先对照这张“地图”找到自己的兴趣点。

• Part I（第1-2章）：入门与离散规划。这是理解后续内容的基石。

• Part II（第3-8章）：运动规划（Motion Planning）。这是本书的重头戏，涵盖机器人学中最核心的几何路径规划、位形空间（C-Space）理论。

• Part III（第9-12章）：规划与不确定性。涉及决策理论、部分可观测马尔可夫决策过程（POMDPs）。

• Part IV（第13-15章）：约束系统。涉及非完整约束（如汽车停车）和动力学系统。

5. 总结与思考

第一章虽然名为“引言”，但它确立了全书的计算主义视角：把物理世界的运动和决策，转化为数学空间中的搜索问题。

① 核心收获

· 通用性：规划不仅仅是让机器人走路，更是处理状态空间（State Space）中的复杂性，它涵盖了从下棋到自动驾驶的所有决策过程。

· 抽象化：理解 状态空间（State Space） 的概念是关键。无论问题多复杂，只要能定义出状态和动作，就能套用书中的算法。

· 模型的局限：处理物理世界问题时，单纯的离散算法（图灵机）是不够的，必须考虑“感知—行动”的循环。

② 个人感悟

在 2026 年的今天回顾 LaValle 的经典著作，可以看到书中提到的“采样-based 方法”（如 RRT）和“混合离散/连续空间”规划，依然是解决复杂机器人任务（如人形机器人导航、自动驾驶）的核心基础。理解这些基本要素（如状态空间和动作模型），是设计任何智能系统的第一步。

写在最后：回到核心——规划的本质，是把物理世界的运动与决策，抽象为状态空间中的搜索问题。无论是下棋、机器人导航还是自动驾驶，只要能定义状态和动作，就能套用这套统一框架。在 2026 年的今天，采样方法与混合规划依然是具身智能的底座。掌握这些基础，就等于拿到了打开智能系统设计大门的钥匙，这正是这本经典历久弥新的价值所在。