自动驾驶规划算法工程师面试实战题库 - 第4节

面试问题：请说明A*算法的基本原理，以及你在自动驾驶项目中对它做了哪些改进？

面试官考察点：对启发式搜索的理解深度、工程落地能力、改进创新意识。

回答框架：① 一句话定义A* -> ② 三个核心因素：开放列表/关闭列表、f=g+h、启发式函数 -> ③ 在项目中至少给出2项改进（如双向搜索、JPS、跳点剪枝、动态权重等）。

示例回答：A*是结合Dijkstra和贪心搜索的图搜索算法，通过f=g+h评估节点。我在项目中做了三个改进：① 采用Jump Point Search(JPS)加速，只保留关键转角点，搜索节点减少约70%；② 增加双向搜索，缩短搜索时间50%；③ 引入动态权重，高速场景h权重更大，提高实时性。

可能追问：双向搜索如何保证相遇点最优？启发式函数为何选择曼哈顿距离而非欧氏距离？JPS在什么场景下失效？

避坑提醒：不要只背原理，一定要结合具体业务场景（如城市道路vs高速）；避免说“我用了A*但没有改进”，面试官期待看到工程优化。

面试问题：RRT算法在高维规划中有什么优势？RRT*相比标准RRT改进了什么？

面试官考察点：采样与搜索空间平衡、渐进最优性概念、路径质量判断。

回答框架：① 优势：概率完备、适合非完整约束 -> ② 核心步骤：随机采样 -> 最近邻 -> 扩展 -> 碰撞检测 -> ③ RRT*增加了重选父节点和重布线，渐进最优。

示例回答：RRT通过均匀采样在高维空间快速构建树，适合带有运动学约束的规划。RRT*相比标准RRT增加了两步：每次新节点生成后，以半径r内节点重新选择父节点使代价最小，再对邻近节点重布线，保证渐近最优性。我曾在泊车场景中采用RRT*，路径代价降低约20%。

可能追问：RRT*的收敛速度如何优化？如何设置采样偏向区域？在动态环境下如何处理？

避坑提醒：RRT*虽优但收敛慢，不要只说理论；要说明实际工程中采用了“目标偏向采样” + “自适应步长”来加速；避免说“RRT路径振荡”，而应补充平滑后处理。

面试问题：请解释Lattice Planner的采样思路，与A*/RRT相比适用于什么场景？

面试官考察点：Frenet坐标系理解、采样密度与实时性权衡、场景匹配。

回答框架：① Lattice基于Frenet坐标系，沿着道路中心线做横向纵向采样，形成轨迹簇 -> ② 通过代价函数选最优 -> ③ 优势：生成轨迹自然平滑，适合结构化道路；劣势：依赖高精度地图和速度曲线。

示例回答：Lattice Planner在Frenet坐标系下，沿s方向等间隔采样终点状态，用五次多项式生成轨迹簇；再通过cost函数（加速度、曲率、与参考线距离）排序选择。相比A*适合高速路平稳变道，相比RRT更适合有明确车道线的场景，我曾在城区车道保持项目中使用，实时性达到20ms。

可能追问：如何处理横向采样与纵向采样的耦合？在障碍物突然切入时怎么做重规划？五次多项式与三次样条的区别？

避坑提醒：不要只答“采样-选优”四个字；必须讲清楚采样空间（s,d）和轨迹表示（如五次多项式）以及代价函数的设计思路；避免说“Lattice比A*好”，应结合场景客观对比。