Planning Algorithms 学习站 LaValle · Planning Algorithms(2006)

学习主页

Planning Algorithms 中文互动教程

跟着 Steven M. LaValle 的《Planning Algorithms》(中文常译《规划算法》)一章一章读下去:每章有中文讲解(关键术语保留英文)、嵌在正文里的互动图,以及可以运行的参考代码。

Part I · 入门材料(已完成)

第 1 章

引言 Introduction

机器人学、控制论、AI 眼中的「规划」;1.2 节的应用示例;规划的六个基本要素;算法、规划器与计划的关系;全书结构。

应用示例筛选六要素对照表机器 / 环境边界全书路线图
第 2 章

离散规划 Discrete Planning

状态空间与状态转移图;BFS、DFS、Dijkstra、A*、Best-first、迭代加深、双向搜索;值迭代与 Dijkstra 的关系;STRIPS、部分计划、规划图、SAT。

搜索实验室值迭代实验室手电筒 STRIPS规划图互斥SAT 编码

配套代码:part1/code/ch2_discrete_planning.py(运行后会打印书中图 2.9、2.12、2.14、2.15 的表)。原书 PDF:Part I ↗ ·作者主页 ↗

Part II · 运动规划(已完成)

第 3 章

几何表示与变换 Geometric Representations and Transformations

世界 W、障碍 O 与机器人 A 的几何建模(半平面、半代数原语、谓词);2D/3D 刚体变换与齐次矩阵;运动链与 DH 参数(PUMA 560、辛烷);运动树的分叉约束与闭环;非刚体变换。

半平面交姜饼人脸齐次矩阵Yaw-Pitch-RollDH 参数PUMA 560闭环求解
第 4 章

配置空间 The Configuration Space

开集、同胚、流形与粘合、同伦与基本群;SE(2) = ℝ²×S¹,SE(3) = ℝ³×ℝP³ 与四元数;C-space 障碍、Minkowski 差与星形算法、钢琴搬运工问题;闭链的代数簇与 Grübler 公式。

内点/边界点拓扑检查器流形检测粘合正方形同伦与基本群O(2) 两个圆柱面规划四元数Minkowski 差星形算法机械臂 C-space两/三连杆簇连杆图
第 5 章

基于采样的运动规划 Sampling-Based Motion Planning

度量、Haar 测度与均匀随机旋转;van der Corput、Sukharev、Halton 与分散度 / 差异;层次与增量碰撞检测、路径段检查;网格搜索与随机势场;RRT/RDT、Kd 树与双向 RRT;PRM、可见性路线图与采样启发式。

Lp 度量SO(2) 距离位移度量球面 / SO(3) 采样van der Corput采样方法对比维数灾难包围体层次特征 Voronoi路径段检查连杆 Lipschitz网格 A*随机势场RDT 探索Kd 树RRT 规划器PRM可见性路线图采样启发式
第 6 章

组合运动规划 Combinatorial Motion Planning

完备算法与路线图的两个条件;双向边表、垂直单元分解与平面扫描、最大间隙路线图(广义 Voronoi 图)、最短路路线图(简化可见性图);单纯复形与奇异复形、三角剖分与柱形分解、线段机器人的临界曲线;Tarski 语句、柱形代数分解与 Canny 路线图;PSPACE 下界与 Davenport–Schinzel 序列。

路线图两条件双向边表图 6.2 四种情形平面扫描垂直分解 / 三角剖分 / 柱形分解等距曲线最大间隙路线图最短路路线图双切线测试单纯复形三维垂直分解雷达图与临界曲线Nicomedes 蚌线Tarski 语句符号分配一维分解柱形代数分解Canny 路线图双重 vs 单指数DS 序列与下包络
第 7 章

基本运动规划的扩展 Extensions of Basic Motion Planning

时变问题:X = C × T、伪度量与速度锥、速度调节;多机器人:优先级规划、固定路径 / 路线图协调与立方复形;混合系统与操作规划(transit / transfer、操作图);闭运动链的切平面步进与主动–被动分解;纸箱、结、药物与蛋白质折叠;牛耕式与生成树覆盖;近似最优规划与 Pareto 最优。

时变 X = C × T柱体与传递性ρ_X 与速度锥速度调节装配规划优先级规划协调空间三机器人柱形障碍立方复形门卫室可重构机器人操作规划子集transit / transfer沿 C_clo 步进环生成器关节角的界纸箱折叠能量软障碍结的化简牛耕式分解生成树覆盖三种动作模型单位步长可达集加权区域Pareto 最优协调
第 8 章

反馈运动规划 Feedback Motion Planning

开环与反馈;离散反馈计划与导航函数、wavefront 与 Dial 算法、NF2 最大间隙;向量场、积分曲线与 Filippov 解,光滑流形与切空间;单元复形上的向量场、平面最优导航函数、加速度界、Rimon–Koditschek 与调和势函数;漏斗组合与带插值的值迭代。

开环 vs 反馈网格导航函数wavefront / DialNF2 最大间隙向量场与积分曲线Filippov 解坐标邻域S² 切空间势函数局部极小三角剖分向量场最优导航函数加速度控制Rimon–Koditschek调和势函数SE(2) 无碰球漏斗与覆盖插值带插值的值迭代

Part III · 决策论规划(已完成)

第 9 章

基本决策论 Basic Decision Theory

单步决策:优化与 Pareto 最优、概率回顾、随机化策略;与自然对弈的最坏情况 / 期望 / 遗憾准则,观测、贝叶斯分类与参数估计;零和博弈的鞍点与随机化鞍点(线性规划);Nash 均衡;效用理论与对决策论的审视。

Pareto 最优骰子事件实验室贝叶斯马赛克随机化与猜硬币先验单纯形决策准则实验室噪声传感器OCR 分类器参数估计矩阵博弈实验室上 / 下包络双矩阵 Nash三人博弈效用与彩票偏好三角形频率学派风险无信息先验重复囚徒困境
第 10 章

序贯决策论 Sequential Decision Theory

与自然的序贯博弈(MDP);前向投影与弱 / 强反向投影;反馈计划与最坏 / 期望代价;值迭代、策略迭代、反向投影算法与非确定 Dijkstra;折扣与平均代价的无限时域问题;TD(λ) 与 Q-learning;博弈树、安全计划、alpha-beta 与三种信息模型;连续空间里与自然对抗的运动规划。

网格上的自然数轴前向投影弱 / 强反向投影计划与 G_π循环与渐近收敛值迭代实验室策略迭代非确定 Dijkstra折扣因子机器保养 MDPMC / TD(λ)Q-learning博弈树与 alpha-beta三种信息模型走廊追逐有自然的博弈与自然对抗的运动规划会开关的门
第 11 章

传感器与信息空间 Sensors and Information Spaces

状态未知时,把「知道什么」当成状态:传感器与原像、历史 I-空间;I-map 与充分性、不确定 / 概率 I-空间与有限记忆;L 形走廊、NFA 与 POMDP;连续空间的保守近似与矩近似、传感器目录、只看投影的例子、无传感器的托盘倾斜;卡尔曼滤波、网格法与粒子滤波;博弈中的信息模型与战舰。

传感器与原像三状态 I-stateI-map 充分性检验信念单纯形整数线与目标可识别性L 形走廊NFA 与子集构造保守近似传感器目录正弦曲线图上的点圆盘上方还是下方托盘倾斜卡尔曼滤波网格 / 粒子 / 矩近似博弈信息模型战舰
第 12 章

感知不确定下的规划 Planning Under Sensing Uncertainty

在 I-空间里规划:把 I_ndet / I_prob 当作大状态空间做值迭代(POMDP);离散网格、连续多边形与概率定位(卡尔曼 / 粒子滤波);地图未知时判定环境、迷宫搜索、D*、Bug 算法与竞争比、间隙导航树、EM 建图;基于可见性的追逃;原像规划、顺应运动与无传感器的零件挤压。

I_ndet 值迭代POMDP α-向量被动定位主动定位计划树可见性定位概率网格定位蒙特卡洛定位判定环境迷宫搜索D*Bug1 / Bug2迷路的牛间隙导航树EM 建图可见性追逃摩擦锥反向投影挤压零件

Part IV · 微分约束下的规划(已完成)

第 13 章

微分模型 Differential Models

ẋ = f(x, u):C-space 上的速度约束(隐式 / 参数、Pfaffian、完整与非完整);简单车、Dubins 与 Reeds–Shepp、差速驱动、拖车、推箱子、滚球;相空间与漂移、线性与控制仿射系统、加积分器;Newton–Euler 力学、刚体转动、轮胎侧滑;Lagrange 与 Hamilton 力学、两连杆机械臂;自然干扰与追逃微分对策。

速度约束画廊q̇ = f(q,u) 两种解读Pfaffian 平面族简单车与平行泊车差速驱动 / 独轮车拖车与折刀推箱子飞机螺旋线滚球困在圆上相平面与摆非完整积分器加积分器月球着陆器刚体转动平面推进器轮胎侧滑变分两连杆机械臂球面上的质点Hamilton 相流自然干扰追逃微分对策
第 14 章

微分约束下的采样规划 Sampling-Based Planning Under Differential Constraints

Formulation 14.1;非完整 / 动力学 / 轨迹规划、漂移、欠驱动、对称;相空间障碍与不可避免碰撞区;可达集、离散时间模型、可达图与分辨率完备、运动基元;系统模拟器(Euler、RK4、反向积分)与 BVP;双积分器格点与近似算法、单元剪枝搜索、RDT;带插值的值迭代;先规划再变换、路径约束相平面与 bang-bang;打靶法。

速度集与系统性质不可避免碰撞区简单约束可达集简单车可达集可达树 / 可达图圆上稠密的顶点Δt 减半的分辨率完备交错探索机动自动机理想距离 vs 加权欧氏Euler vs RK4双积分器格点可达锥平面点质量格点搜索U′(q, q̇)单元剪枝搜索微分约束下的 RDT带插值的值迭代先规划再变换路径上的允许加速度路径约束相平面 / bang-bang打靶法与局部极小
第 15 章

系统理论与解析方法 System Theory and Analytical Techniques

Lyapunov 稳定性与 Lyapunov 函数、能控性与 STLC;HJB 方程、线性二次调节器、Pontryagin 最小值原理;Dubins、Reeds–Shepp、Balkcom–Mason 最优曲线;控制仿射系统、分布与 Lie 括号、Frobenius 与 Chow–Rashevskii 定理、P. Hall 基;CFS 方程、正弦转向、链式系统与微分平坦。

稳定性定义吸引域与极限环线性特征值Lyapunov 函数Kalman 秩条件小时间可达集STLC 递归细分值迭代 → HJBHJB 逐点LQR / Riccati双积分器 bang-bangDubins 曲线单元与度量Reeds–SheppBalkcom–Mason分布 3D换位运动P. Hall 基Lie 括号计算器CFS 转向正弦转向链式与平行泊车微分平坦

全书路线图 & 我的进度

这个仓库的组织方式

lavalle-planning-algorithms-zh/ # github.com/xpengzxp/lavalle-planning-algorithms-zh ├── index.html # 你在这里:学习主页 ├── README.md # 仓库说明(怎么阅读、目录、章节列表) ├── CLAUDE.md # 编写约定与「新增一章」流程 ├── docs/COORDINATION.md # 第 6–15 章的协调记录 ├── assets/ # 所有页面共用的样式和脚本 │ ├── style.css │ ├── common.js # 深色模式、目录高亮、公式渲染、小工具 │ └── roadmap.js # 全书路线图(章节登记表也在这里) ├── part1/ # Part I:第 1–2 章 │ ├── ch1-introduction.html │ ├── ch2-discrete-planning.html │ ├── js/ # 本部分的互动组件 chK-*.js │ └── code/ # 可运行的参考实现 chK_*.py ├── part2/ # Part II:第 3–8 章 ├── part3/ # Part III:第 9–12 章 └── part4/ # Part IV:第 13–15 章

全站是纯静态网页,可以直接托管在 GitHub Pages 上,也可以 clone 仓库后在根目录运行 python3 -m http.server 阅读。公式渲染需要联网加载 KaTeX。原书 PDF 不在仓库里,页面中的原书链接都指向 lavalle.pl/planning。

「我已读完」的勾选只保存在你当前的浏览器里(localStorage),每个人、每个浏览器的进度各自独立,不会上传,也不会写进仓库;换浏览器或清除浏览器数据后会从零开始。