📚 课程目录第4章技术基础

第4章技术基础：路径规划算法（A*、Dijkstra、RRT等）

  核心认知：路径规划是自动驾驶决策的底层引擎。面试中需要清晰说出每种算法的优化目标、假设条件、计算开销及工程妥协。重点不是手写代码，而是选型理由与已知局限的应对方案。

作答口诀：先分类、后对比、再工程取舍。回答时先说“我针对XX场景选择了XX算法，因为……”，然后补充“若遇到动态障碍物，我会引入RRT*或Hybrid A*”。

面试问题	请解释A*算法和Dijkstra算法的区别，以及你在项目中如何选择？
面试官考察点	对启发式搜索的理解；能否根据场景约束做合理选型。
回答框架	1）算法本质：Dijkstra无启发式，保证最短路径；A引入启发函数（如欧氏距离），加速收敛但不保证最优（若启发函数>=实际代价则降级为Dijkstra）。2）选型依据：低维、小地图优先A；需要最优或代价函数复杂时用Dijkstra。
示例回答	“A通过启发函数（如曼哈顿距离）减少搜索节点，在结构化道路的栅格地图中比Dijkstra快3-5倍。但若地图存在强约束（如非均质代价场），我会改用Dijkstra以确保全局最优性。在高速场景，我偏好Hybrid A结合运动学约束。”
可能追问	1）启发函数如何设计？如何保证admissibility？2）如果启发函数过估计会怎样？3）A的变种（如Weighted A）你了解哪些？
避坑提醒	不要只说“A*比Dijkstra快”就完事。面试官会追问“快多少？什么场景下快？慢的场景是什么？”

面试问题	RRT算法在自动驾驶中有什么缺陷？你如何改进？
面试官考察点	对随机采样类算法的理解；是否了解RRT*、Informed RRT等改进。
回答框架	1）原版RRT问题：路径曲折、非最优、搜索效率浪费。2）改进方向：RRT*（rewire保证渐进最优）、Informed RRT（缩小采样范围）、Bi-RRT（双向搜索速度提升）。3）工程落地：结合运动学模型做节点扩展，避免不可执行路径。
示例回答	“我在停车场场景使用RRT*，采样时限制在椭圆区域内加速收敛，并对每条边做Reeds-Shepp曲线连接，确保路径符合车辆最小转弯半径。经过1000次仿真测试，成功率从78%提升至95%。”
可能追问	1）RRT的渐进最优性证明要点？2）为什么不直接用A？3）如何处理狭窄通道（narrow passage）问题？
避坑提醒	避免只说“RRT慢”而不提出量化对比。给出具体场景（如狭窄停车场、非结构化园区）和对应改进方法。

面试问题	Hybrid A和传统A的主要区别是什么？在泊车场景中如何应用？
面试官考察点	是否理解运动学约束下的路径搜索；能否解释连续状态空间离散化的方法。
回答框架	1）传统A在离散栅格上搜索，不保证运动学可行性；Hybrid A在连续状态空间（x,y,θ）中搜索，使用Reeds-Shepp曲线或Dubins曲线作为预连接。2）工程实现：剪枝策略（只保留每个栅格中代价最小的状态节点）、启发函数取max(非完整约束代价，无障碍距离)。
示例回答	“我们采用Hybrid A*生成泊车粗轨迹，再用非线性优化平滑。具体做法：每个栅格只保留一个节点（计算代价最小），通过Reeds-Shepp曲线连接两节点，后续用梯度下降优化曲率和障碍物距离。实测在垂直泊车位成功率99%。”
可能追问	1）如何解决Hybrid A*的局部最优问题？2）网格分辨率如何设定？3）与MPC结合的接口设计？
避坑提醒	不要混淆A和Hybrid A。强调“连续状态空间”和“运动学约束”是Hybrid A*的核心。如果没项目经验，可以讲公开数据集（如nuScenes）上的实验。

高频雷区：很多面试者只背定义，缺乏定量对比。面试前准备好一组数据（如“A*搜索1000节点耗5ms，RRT*耗12ms但路径质量高20%”），能显著加分。

业务背景	为某自动驾驶出租车车队提供高鲁棒性规划模块，要求在城市复杂路口、人行横道、无保护左转等场景下稳定运行。
规模指标	覆盖200+路口，每日运营里程5000km，平均规划耗时≤15ms，成功绕障率99.2%。
技术栈	C++ / ROS2 / Hybrid A* + Lattice Planner / 基于梯度优化的QP平滑器 / 代价场设计（障碍物+车道线+舒适性）
核心难点	1）多模态预测导致规划时间不足；2）狭窄缺口处Hybrid A*易陷入局部最优；3）实时性要求下剪枝策略调优。
面试高频追问	1）Hybrid A*的启发函数具体怎么算？2）QP平滑器如何处理硬约束（如曲率限制）？3）如果传感器延迟50ms你怎么补偿？4）如何在线调整代价权重？
可迁移回答话术	“针对实时性瓶颈，我在Hybrid A*中引入‘自适应分辨率’——直行路段粗网格（1m），转弯区域细网格（0.2m），搜索节点数降低40%同时保持轨迹精度。同时，采用‘先跟踪后采样’策略：当接近预测路径时减少采样密度。”

  面试加分点：在说明算法选择时，主动补充“如果遇到XX情况（如阻塞），我会切换为……”，展示工程边界意识。用数字（耗时、成功率、网格尺寸）让回答更有说服力。

第4章 技术基础：路径规划算法（A*、Dijkstra、RRT等）