第234篇运动规划面试高频题——面试官最爱问的15个规划问题-开发者社区

前面十篇（224-233）讲了运动规划的各种算法——Reed-Shepp曲线、混合A*、轨迹优化、B样条、TOPP、碰撞检测、CHOMP/TrajOpt。今天做一个总结：把面试官最爱问的15个运动规划问题整理在一起，每个问题给出精炼的回答要点。

面试运动规划岗（自动驾驶规划、机器人运动规划、无人机轨迹规划），这些问题出现的频率极高。我面了十几家公司的规划岗，这些问题被问了不下50遍。

一、基础概念类（5题）

Q1：路径规划和轨迹规划有什么区别？路径规划找空间曲线（从A到B走哪条路），不考虑时间。轨迹规划在路径上加时间参数化（什么时候走到哪个点）。路径是几何的，轨迹是时空的。轨迹可以求导得到速度/加速度，路径不行。

Q2：完整约束和非完整约束有什么区别？完整约束只限制位形（比如关节限位：-π ≤ q ≤ π）。非完整约束限制速度（比如车辆不能横向移动：ẋ·sin(θ) - ẏ·cos(θ) = 0）。非完整约束不能积分成位形约束——它减少的是可控自由度而不是可动自由度。典型非完整系统：阿克曼转向车辆、差速驱动机器人。完整系统的例子：全向轮机器人（omniwheel）、机械臂（每个关节独立可控）。非完整约束对规划的影响：不能直接用直线连接两个状态——必须用满足约束的曲线（Dubins/Reed-Shepp曲线）。

Q3：P问题、NP问题、NP-hard和运动规划有什么关系？在有障碍物的环境中找最优路径是NP-hard问题（可以归约为TSP）。所以实际算法都是近似或启发式的——A用启发函数加速、RRT渐进逼近最优、PRM是概率完备的。面试时如果被问这个，能说出"最优路径规划是NP-hard"就够了，不用展开证明。

Q4：概率完备性和渐进最优性是什么意思？概率完备性：如果解存在，算法在无限时间内以概率1找到解（RRT是概率完备的）。渐进最优性：随着采样数增加，解的质量以概率1趋近于最优（RRT是渐进最优的，RRT不是）。面试时说清楚RRT和RRT的区别就够了。

Q5：全局规划和局部规划的区别？全局规划：基于完整地图信息，规划从起点到终点的全局路径（A、RRT、混合A）。局部规划：基于局部感知信息，在短视距内规划避障轨迹（DWA、TEB、人工势场）。实际系统两者结合——全局规划给大方向，局部规划做实时避障。

补充一个工程细节：全局规划和局部规划的地图通常不是同一张。全局规划用离线构建的全局地图（精度高、更新慢），局部规划用实时感知生成的局部地图（精度低、更新快）。百度Apollo的系统里全局地图每10秒更新一次，局部地图每50ms更新一次。

二、算法原理类（5题）

Q6：A*和Dijkstra的区别是什么？Dijkstra是A的特例（启发函数h=0）。A用启发函数h(n)引导搜索方向，比Dijkstra快很多。A的最优性条件是启发函数可容许（admissible）——h(n)不超过真实代价h(n)。A*的时间复杂度取决于启发函数质量——好的启发函数能让搜索从O(b^d)降到接近O(d)。

Q7：RRT和RRT*的核心区别？RRT找到第一条路径就返回（快速但不最优）。RRT在每次添加新节点后做rewire——检查新节点附近的现有节点，看通过新节点连接是否能减少代价。Rewire让RRT渐进逼近最优路径。代价是RRT比RRT慢2-5倍。Informed RRT在找到第一条路径后限制采样区域为椭球，进一步加速优化。

Q8：DWA和TEB的区别？DWA（Dynamic Window Approach）在速度空间中采样，选取消耗函数最小的速度指令。TEB（Timed Elastic Band）在轨迹空间中优化，用图优化方法同时优化轨迹形状和时间分配。DWA更快（<1ms）但只能处理简单场景。TEB更慢（5-20ms）但能处理复杂约束（运动学、动力学）。ROS中导航栈默认DWA，move_base_flex支持TEB。说白了，DWA是"贪心策略"——每一步选当前最优速度，TEB是"全局视野"——看整条轨迹一起优化。

Q9：混合A*为什么在泊车场景中效果好？三个原因。一是搜索空间包含朝向θ，路径满足阿克曼转向模型——车一定能开过去。二是支持前进后退切换（用Reed-Shepp曲线做解析扩展）——泊车必须倒车。三是代价函数可以惩罚换向次数——用户不喜欢反复揉库。混合A的路径质量比RRT稳定（确定性强），比纯A可行（考虑了运动学）。

Q10：CHOMP和TrajOpt哪个更好？看场景。CHOMP用软约束+梯度下降，实现简单，适合障碍物简单的场景。TrajOpt用硬约束+信赖域，约束满足严格，适合窄通道和复杂障碍物。两者都需要好的初始解（通常由RRT提供）。实际项目中经常组合使用——CHOMP粗优化+TrajOpt精优化。

三、工程实践类（5题）

Q11：运动规划模块的输入输出是什么？输入：当前位姿、目标位姿、地图（栅格/点云/语义地图）、运动学约束。输出：一条可执行的轨迹（时空点序列：位置+速度+时间戳）。有些系统输出路径+速度曲线分开。

Q12：规划的频率一般多少？全局路径规划：1-10Hz（每100ms-1s更新一次，场景变化不大时可以降频）。局部轨迹规划：10-50Hz（每20-100ms更新一次，需要实时响应动态障碍物）。时间参数化（TOPP）：和路径规划同频，路径变了就重算。

频率选择的原则：规划频率必须高于控制频率的一半以上。如果控制器200Hz（5ms），规划至少50Hz（20ms）。原因：规划输出的轨迹需要在两个规划周期之间被控制器跟踪——规划频率太低会导致轨迹过期，控制器跟踪误差大。

Q13：规划失败怎么处理？分级处理。第一级：放宽约束重试（比如增大安全距离到障碍物距离的容差）。第二级：换算法重试（RRT失败换PRM，CHOMP失败换TrajOpt）。第三级：报告上层系统"无法到达目标"，触发任务重规划（比如换一个停车目标）。工程上设置最大重试次数（通常3-5次），超过就放弃。

还有一个常见的失败原因：规划超时。RRT在复杂场景中可能需要几秒才能找到路径，但规划超时设置通常500ms。解决方案：用RRT-Connect（双向搜索，收敛更快）或者混合A*（有启发函数引导，搜索更快）。

Q14：怎么评估一条轨迹的质量？五个指标：路径长度（越短越好）、执行时间（越短越好）、最大jerk（越小越舒适）、离障碍物最小距离（越大越安全）、跟踪误差（实际轨迹和规划轨迹的偏差）。实际项目中给每个指标设阈值，全过才算合格。

更细致的评估：把轨迹分段评估——起步段、巡航段、终点段分别看速度/加速度是否合理。起步段如果加速度突变说明jerk约束没处理好，巡航段如果速度波动大说明轨迹不够平滑，终点段如果停车时有余震（overshoot）说明末端速度/加速度边界条件没设好。

Q15：你在项目中用过哪些规划算法？踩过什么坑？（这是开放式问题，准备一个真实案例）比如：做AGV导航用的A全局规划+DWA局部规划。踩过的坑：A在窄通道中搜索时间长（500ms+），解决方案是用visibility graph预处理减少搜索空间。DWA在动态障碍物场景中反应慢（5Hz不够），解决方案是把局部规划频率提到20Hz。