📚 课程目录第4章路径规划与轨迹生成

路径规划与轨迹生成：A*、RRT、Dijkstra 等算法面试问答

章节导入：路径规划与轨迹生成是自动驾驶决策规划层的核心模块。面试中算法类问题常考察对图搜索、采样规划、最优控制等范式的理解深度。本章用 3 个问答卡片 + 1 个真实项目案例，帮你快速掌握回答框架与高频追问。

常规问答卡片 1：A* 算法的启发式函数如何设计？

面试问题	请详细解释 A* 算法中启发式函数的设计原则，并举例说明在自动驾驶场景中如何选择。
考察点	对 A* 最优性、可采纳性、一致性的理解；能否将理论映射到实际（如欧氏距离 vs 曼哈顿距离的选择）；是否考虑过不一致启发式的影响。
回答框架	① 定义启发式函数 h(n)：估计从节点 n 到目标的最小代价；② 可采纳性：h(n) ≤ 实际代价（保证最优解）；③ 一致性（单调性）：h(n) ≤ c(n,m) + h(m)；④ 自动驾驶常用：欧氏距离（2D/3D 无向图）、复现曼哈顿距离（城市网格）；⑤ 实际工程可选对角线距离或 Dubins 曲线距离（考虑车辆运动学）。
简短示例回答	“A* 的启发式必须可采纳以保证最优解。在结构化道路上我选用欧氏距离，因为简单且可采纳。而在泊车场景，我会用 Reeds-Shepp 曲线距离作为启发式，虽然计算稍重，但能有效减少扩展节点数，提升实时性。”
可能追问	“如果启发式不一致怎么办？”（可能需重新开放节点，效率下降）；“哪些场景下启发式不会显著加速？”（自由空间大、障碍物稀疏时）；“你如何检验启发式的可采纳性？”。
避坑提醒	注意：面试官很可能让你手写 A* 伪码并指出哪些行体现了启发式。不要只说理论，要能写出 Open Set / Closed Set 逻辑。

常规问答卡片 2：RRT 与 RRT* 的区别及应用场景

面试问题	对比 RRT 和 RRT* 的核心差异，说明各自适用于哪些自动驾驶规划任务。
考察点	对采样算法的理解深度；是否能区分“可行解”与“最优解”；对变种（如 RRT-Connect、Informed RRT*）的了解。
回答框架	① RRT：概率完备但非最优，快速随机树生长；② RRT：在 RRT 基础上增加重布线（rewire）和父节点重选，渐近最优；③ 应用场景：RRT 适合高维、实时性要求高的场景（如非结构化停车场、避障路径生成）；RRT 适合离线路径规划或低维状态空间（如全局路径参考线）。
简短示例回答	“RRT 能快速找到可行解，但路径不光滑且非最优。RRT* 通过每次插入新节点时重连邻近节点，保证渐近最优。在低速泊车场景，我用 RRT* 生成初始轨迹，再交给优化器平滑；而高速避障时选 RRT 快速规划。”
可能追问	“RRT* 的收敛速度如何改进？”（Informed RRT* 通过椭圆采样剪枝）；“如何保证 RRT 生成的路径满足车辆动力学？”（使用 Dubins 或 Reeds-Shepp 连接采样点）；“重连半径如何选择？”。
避坑提醒	不要只背诵定义。强调工程权衡：RRT 的扩展步长、Collision Checking 策略、以及如何与后端的轨迹平滑模块配合。

常规问答卡片 3：Dijkstra 算法在规划中的定位与优化

面试问题	Dijkstra 算法是最短路径基础算法，在自动驾驶中为何很少直接使用？请指出其局限性及改进方向。
考察点	对 Dijkstra 与 A* 的对比理解；计算复杂度意识；是否了解分层规划（如先 Dijkstra 粗粒度搜索再 A* 细化）。
回答框架	① Dijkstra 无启发式，遍历所有方向，在稠密网格中效率低；② 自动驾驶环境动态场景需要重规划，Dijkstra 全图更新代价高；③ 改进：通过分层地图（如 Lane Graph 上 Dijkstra 寻路，再局部 A）；④ 与 D Lite 或 LPA* 作比较（增量式搜索更适合动态环境）。
简短示例回答	“Dijkstra 在静态小地图上依然可用。实际工程中我会先在车道级别拓扑图中用 Dijkstra 找全局参考线，再切换到局部规划器。但全量栅格地图直接 Dijkstra 会因 O(N²) 复杂度无法满足 100ms 的实时要求，必须用 A* 或 Hybrid A*。”
可能追问	“Dijkstra 是否保证最优？”（是，但只保证不带启发式的图最优）；“如果地图有负权边怎么办？”（不能用，需 Bellman-Ford）；“你如何评估 Dijkstra 在矢量地图上的计算时间？”。
避坑提醒	不要简单说“Dijkstra 不如 A*”。面试官想听你分析“为什么不用”以及“在什么子问题中仍然可以用”。可举车道级寻路作为例子。

项目案例：基于混合A* + 二次规划的泊车路径规划系统

项目名称	自动代客泊车（AVP）路径规划模块
业务背景	支持 L4 级别地下车库/地面停车场，车辆自主从入口行驶至目标车位并完成泊入。需同时处理静态障碍（柱子、车辆）和动态障碍（行人、前车）。
规模指标	规划周期 ≤ 40ms；路径成功率 ≥ 99.5%；泊入精度 ≤ 20cm；支持 5 层大型车库（区域大小 300m × 200m）。
技术栈	混合A（Non-holonomic A）、Reeds-Shepp 曲线、二次规划（OSQP）、B样条平滑；C++ / ROS2 / 仿真平台 CARLA。
核心难点	① 离散搜索步长与连续性矛盾：混合A* 需在连续状态空间离散化加速，但可能导致死锁；② 优化与硬约束冲突：二次规划极易因避障约束过强导致无解；③ 重规划实时性：动态障碍更新时需增量式搜索。
面试高频追问	“混合A* 中如何做节点扩展？为什么不用传统A*？” “二次规划的目标函数如何设计？权重系数如何调参？” “如何保证泊入终点朝向误差 < 0.5°？” “碰撞检测用什么方法？如何剪枝？”
可迁移回答话术	“对于结构化场景的路径规划，我倾向于采用‘前端启发式搜索 + 后端优化’范式。前端用混合A* 快速得到无碰撞的粗糙路径，利用车辆运动学模型替代欧几里得距离作为启发式；后端使用二次规划在满足曲率、加速度等约束下最小化长度和平滑度，通过软硬约束结合提高求解成功率。这种组合既能保证实时性，又能输出满足动力学的最优轨迹。”

  📌 面试加分提示： 在回答项目经验时，主动提及“遇到过多少个 failed case”“如何调参平衡最优性和安全性”“对其他变种（如 A*-Connect、RRT*-Smart）的对比实验”，能让面试官觉得你不仅有落地经验，还有深入思考。

💡 本章小结： 路径规划算法面试应避免只背概念，要围绕“算法分类 → 原理 → 优缺点 → 工程落地 → 变种拓展”五步骤展开。结合项目案例中的真实指标（如 40ms、99.5%成功率）会更有说服力。