面灵AI→

地平线规划控制算法一面:A*、混合 A* 与 MPC

轮次
一面
结果
挂了
时间
2026-11
来源
牛客网

《面试题目》

  1. 讲一下你的项目和实习经历。
  2. A* 和混合 A*(Hybrid A*)有什么区别?
  3. 自行车模型是什么?
  4. C++ 常用容器有哪些,底层是怎么实现的?
  5. PID、LQR、MPC 的概念和各自的优劣?
  6. 车辆模型如何建立?
  7. coding:无向图最短路径的思路(Dijkstra)。

《参考解析》

A 与混合 A。** A* 在离散栅格上搜,代价 f = g + h,h 必须可采纳(不能高估),栅格地图常用欧氏距离或对角距离;它的问题是把车当成质点,路径是一串折线,既没有考虑最小转弯半径,也没考虑朝向,规划完还得做平滑和可行性检查。混合 A* 把状态扩到连续空间的 (x, y, θ),扩展时不再走栅格邻居,而是用一组运动基元(固定转角步长、前进/后退、不同速度)积分出可行轨迹,天然满足车辆运动学约束;启发式一般取「忽略障碍的非完整距离」,也就是 Reeds-Shepp 曲线(允许倒车)或 Dubins 曲线(只允许前进)的长度,再叠一张 2D 栅格 Dijkstra 的启发式来引导搜索方向。代价函数里会加转向角变化、换挡、倒车的惩罚,让路径更舒服。工程上它节点数量大,需要栅格哈希去重、优先队列开集,常用于泊车位姿搜索这类小范围高精度场景;开放道路更常见的是 lattice/采样加 QP 优化。

自行车模型与车辆建模。 运动学自行车模型把前后轮用轴距 L 连成刚体,只考虑几何关系:ẋ = v·cosθ、ẏ = v·sinθ、θ̇ = v·tanδ / L,状态是 (x, y, θ, v),控制是 (v, δ),曲率 κ = tanδ / L。它假设轮胎不侧滑、车速低,泊车和低速循迹够用,高速会失真。动力学模型要加质量、转动惯量、前后轴侧偏刚度,用单轨(bicycle)或双轨模型,轮胎力用线性模型或魔术公式,状态里多出侧偏角、横摆角速度。建模的完整步骤是:定坐标系和状态/控制量、写动力学方程、选轮胎模型、辨识参数(轴距、质心到前后轴距离、侧偏刚度、转向传动比)、再用阶跃转向和正弦转向的实车数据验证。面试里能说清「低速用运动学、高速和极限工况必须上动力学」这条分界线,比背公式得分高。

PID、LQR、MPC 的取舍。 PID 不依赖模型,靠误差反馈,调参直观,单入单出场景够用;问题是它处理不了约束,大延迟下容易振荡,多变量耦合时调参变成玄学。LQR 用状态空间模型最小化二次型代价 ∫(xᵀQx + uᵀRu),解 Riccati 方程得到线性状态反馈 u = -Kx,Q/R 调「跟踪精度 vs 控制量」的权衡;它理论漂亮、在线计算量小,但约束无法显式表达,非线性系统要做 LTV 或 LQI。MPC 在滚动时域里求解带约束的最优控制,能把转角限幅、转角速率、加速度、障碍物都写成约束,预测未来若干步,效果最好;代价是每步要解一个 QP,实时性靠短时域、热启动、显式 MPC 或离线查表。实际栈里常见组合:横向用纯跟踪或 Stanley 起步,要求高了换 LQR,再往上(高速、需要约束)用 MPC。

Dijkstra 的口述要点。 邻接表建图,dist 数组初始化为无穷,源点 0,用最小堆每次取当前最近的未定型点,松弛它的出边;复杂度 O((V+E)logV)。三个细节会被追问:堆里会有过期条目,弹出时用 if d > dist[u]: continue 做懒删除;只求单点到单点可以提前终止;负权边不能用 Dijkstra,要换 Bellman-Ford 或 SPFA。它和 A* 的关系一句话说清:把启发式取 0,A* 就退化成 Dijkstra。

C++ 容器底层。 vector 连续内存、扩容按 1.5 或 2 倍并搬迁,所以扩容后迭代器、引用全部失效;deque 是分段连续,头尾插入 O(1);list 是双向链表,插入删除不失效但缓存不友好;map/set 红黑树,unordered_map/set 哈希桶加链地址(或红黑树),要能说出负载因子、rehash 导致迭代器失效、以及 reserve 的用处。