斯坦福大学AA274A课程：机器人自主性原理（2019年秋季）——运动规划图搜索方法

（原标题：Stanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Motion Planning Graph Search Methods）

🎓 课程背景与运动规划定义

• 本课程前两周内容难度最高，重点涉及轨迹优化及复杂数学概念，后续章节难度将保持平稳或略有下降。
• 运动规划的核心目标是计算一系列动作序列，使机器人从初始状态安全到达终端状态，同时避开障碍物并满足特定的运动约束条件。
• 该领域在20世纪70年代首次被提出，80年代出现了精确算法，但在高维空间下扩展性较差；90年代研究重心转向近似算法，以平衡实时性与规划质量。
• 标准运动规划通常基于静态、完全已知的地图输入，这与处理未知环境的“遮挡下规划”（Planning under Occlusions）有本质区别。

📚 算法分类与核心参考文献

• 主要参考书籍包括 Steve LaValle 的《Planning Algorithms》（2006版）以及 Dimitri Bertsekas 关于动态规划与最优控制的著作，这些文献构成了课程的理论基础。
• 运动规划算法主要分为四大类：势场法、基于网格的方法、组合规划及采样规划，每类方法在适用场景和计算复杂度上各有优劣。
• 势场法通过人工势能引导机器人移动，其计算速度极快，但容易陷入局部最小值导致无法到达目标；组合规划虽然保留了连续信息，但计算复杂度高且难以扩展到高维空间。
• 采样基于算法因避免了显式映射难题，成为处理高维运动规划问题的更优选择，特别是在机器人具有旋转或多关节自由度的情况下。

📐 网格搜索与标签校正机制

• 网格方法将连续环境离散化为图结构，其中节点代表位置，边代表邻域连接（如4邻居或8邻居），从而将路径规划转化为图搜索问题。
• 分辨率选择存在显著权衡：高分辨率能提升解的质量但大幅增加计算量；低分辨率可能导致路径偏差较大，无法精确贴合障碍物边界。
• “标签校正”算法（Label Correcting）通过维护优先队列（Frontier Queue）迭代更新节点成本 $C(q)$，即从起点到该节点的最优已知路径成本。
• 初始化时所有非起点节点成本设为无穷大，算法通过比较经由当前节点到达邻居的成本来逐步修正路径，直至找到全局最优解或收敛至稳定状态。

🧠 搜索策略对比与 A* 算法机制

• 深度优先搜索采用后进先出策略，内存占用低但可能遍历整个空间；广度优先搜索对应 Bellman-Ford 算法，按层级均匀扩展节点。
• Dijkstra 算法选取最低到达成本节点进行扩展，保证每个节点仅入队一次，但缺乏目标导向性导致各向同性扩展，效率较低。
• A* 算法通过排序函数 $C_q + H_q$（到达成本+启发式估计）优先探索靠近目标的节点，显著减少无效探索区域并提升计算效率。
• 为确保最优性，A* 算法要求启发式函数 $H_q$ 必须是实际成本的严格下界，例如使用欧几里得距离作为近似值。

📊 配置空间与维度灾难挑战

• 运动规划实质是在高维配置空间中为“点机器人”寻找路径，需通过膨胀障碍物来体现真实几何约束，避免碰撞。
• 将工作空间中的障碍物显式映射到配置空间在数学上极其复杂，尤其是当机器人具有旋转或多关节自由度时，障碍物会形成复杂的非刚性形状。
• 网格法顶点数量随维度呈指数级增长，即“维度灾难”，导致其在三维以上高维空间（如机械臂关节角）中难以直接应用显式障碍物表示。
• 组合规划算法虽然理论上完备且能提供更强的运行时间保证，但由于几何构造的实现难度和高维扩展性差，在实际应用中并不实用。

🎯 课程重点、考试范围与实践建议

• A* 算法将作为本季度后续内容的参考规划器，学生需在作业中实现该变体，这是掌握网格规划的核心工具。
• 期中考试将涵盖网格方法（如 A* 与 Dijkstra 的区别）及采样算法概念；组合规划仅作为补充知识，不纳入详细考核范围。
• 鉴于组合算法在高自由度问题上的局限性，实际工程应优先采用采样基于方法，除非特定低维几何场景需要严格最优性保证。
• 有效的离散路线图需满足“可访问性”（任意初始/目标点能连接至图节点）和“连通性”（若连续空间存在路径，图中必存在对应路径）。

🛠️ 关键细节、工具与实现注意事项

• 机器人通常被简化为点模型，障碍物需根据机器人尺寸（如外接圆半径）进行膨胀处理；邻域定义需谨慎，仅连接正交邻居会导致路径长度偏差。
• 梯形分解法通过从障碍物顶点发射射线将环境划分为凸单元格，确保连通性，但几何计算实现繁琐，可借助 CGAL 库辅助完成复杂构造。
• 本片段聚焦于几何设置下的路径长度最小化，暂不涉及动力学约束或不确定性处理，为后续引入更复杂的规划模型奠定基础。