学习主页
跟着 Steven M. LaValle 的《Planning Algorithms》(中文常译《规划算法》)一章一章读下去:每章有中文讲解(关键术语保留英文)、嵌在正文里的互动图,以及可以运行的参考代码。
机器人学、控制论、AI 眼中的「规划」;1.2 节的应用示例;规划的六个基本要素;算法、规划器与计划的关系;全书结构。
状态空间与状态转移图;BFS、DFS、Dijkstra、A*、Best-first、迭代加深、双向搜索;值迭代与 Dijkstra 的关系;STRIPS、部分计划、规划图、SAT。
配套代码:part1/code/ch2_discrete_planning.py(运行后会打印书中图 2.9、2.12、2.14、2.15 的表)。原书 PDF:Part I ↗ ·作者主页 ↗
世界 W、障碍 O 与机器人 A 的几何建模(半平面、半代数原语、谓词);2D/3D 刚体变换与齐次矩阵;运动链与 DH 参数(PUMA 560、辛烷);运动树的分叉约束与闭环;非刚体变换。
开集、同胚、流形与粘合、同伦与基本群;SE(2) = ℝ²×S¹,SE(3) = ℝ³×ℝP³ 与四元数;C-space 障碍、Minkowski 差与星形算法、钢琴搬运工问题;闭链的代数簇与 Grübler 公式。
度量、Haar 测度与均匀随机旋转;van der Corput、Sukharev、Halton 与分散度 / 差异;层次与增量碰撞检测、路径段检查;网格搜索与随机势场;RRT/RDT、Kd 树与双向 RRT;PRM、可见性路线图与采样启发式。
完备算法与路线图的两个条件;双向边表、垂直单元分解与平面扫描、最大间隙路线图(广义 Voronoi 图)、最短路路线图(简化可见性图);单纯复形与奇异复形、三角剖分与柱形分解、线段机器人的临界曲线;Tarski 语句、柱形代数分解与 Canny 路线图;PSPACE 下界与 Davenport–Schinzel 序列。
时变问题:X = C × T、伪度量与速度锥、速度调节;多机器人:优先级规划、固定路径 / 路线图协调与立方复形;混合系统与操作规划(transit / transfer、操作图);闭运动链的切平面步进与主动–被动分解;纸箱、结、药物与蛋白质折叠;牛耕式与生成树覆盖;近似最优规划与 Pareto 最优。
开环与反馈;离散反馈计划与导航函数、wavefront 与 Dial 算法、NF2 最大间隙;向量场、积分曲线与 Filippov 解,光滑流形与切空间;单元复形上的向量场、平面最优导航函数、加速度界、Rimon–Koditschek 与调和势函数;漏斗组合与带插值的值迭代。
单步决策:优化与 Pareto 最优、概率回顾、随机化策略;与自然对弈的最坏情况 / 期望 / 遗憾准则,观测、贝叶斯分类与参数估计;零和博弈的鞍点与随机化鞍点(线性规划);Nash 均衡;效用理论与对决策论的审视。
与自然的序贯博弈(MDP);前向投影与弱 / 强反向投影;反馈计划与最坏 / 期望代价;值迭代、策略迭代、反向投影算法与非确定 Dijkstra;折扣与平均代价的无限时域问题;TD(λ) 与 Q-learning;博弈树、安全计划、alpha-beta 与三种信息模型;连续空间里与自然对抗的运动规划。
状态未知时,把「知道什么」当成状态:传感器与原像、历史 I-空间;I-map 与充分性、不确定 / 概率 I-空间与有限记忆;L 形走廊、NFA 与 POMDP;连续空间的保守近似与矩近似、传感器目录、只看投影的例子、无传感器的托盘倾斜;卡尔曼滤波、网格法与粒子滤波;博弈中的信息模型与战舰。
在 I-空间里规划:把 I_ndet / I_prob 当作大状态空间做值迭代(POMDP);离散网格、连续多边形与概率定位(卡尔曼 / 粒子滤波);地图未知时判定环境、迷宫搜索、D*、Bug 算法与竞争比、间隙导航树、EM 建图;基于可见性的追逃;原像规划、顺应运动与无传感器的零件挤压。
ẋ = f(x, u):C-space 上的速度约束(隐式 / 参数、Pfaffian、完整与非完整);简单车、Dubins 与 Reeds–Shepp、差速驱动、拖车、推箱子、滚球;相空间与漂移、线性与控制仿射系统、加积分器;Newton–Euler 力学、刚体转动、轮胎侧滑;Lagrange 与 Hamilton 力学、两连杆机械臂;自然干扰与追逃微分对策。
Formulation 14.1;非完整 / 动力学 / 轨迹规划、漂移、欠驱动、对称;相空间障碍与不可避免碰撞区;可达集、离散时间模型、可达图与分辨率完备、运动基元;系统模拟器(Euler、RK4、反向积分)与 BVP;双积分器格点与近似算法、单元剪枝搜索、RDT;带插值的值迭代;先规划再变换、路径约束相平面与 bang-bang;打靶法。
Lyapunov 稳定性与 Lyapunov 函数、能控性与 STLC;HJB 方程、线性二次调节器、Pontryagin 最小值原理;Dubins、Reeds–Shepp、Balkcom–Mason 最优曲线;控制仿射系统、分布与 Lie 括号、Frobenius 与 Chow–Rashevskii 定理、P. Hall 基;CFS 方程、正弦转向、链式系统与微分平坦。
全站是纯静态网页,可以直接托管在 GitHub Pages 上,也可以 clone 仓库后在根目录运行 python3 -m http.server 阅读。公式渲染需要联网加载 KaTeX。原书 PDF 不在仓库里,页面中的原书链接都指向 lavalle.pl/planning。
「我已读完」的勾选只保存在你当前的浏览器里(localStorage),每个人、每个浏览器的进度各自独立,不会上传,也不会写进仓库;换浏览器或清除浏览器数据后会从零开始。