前面十篇224-233讲了运动规划的各种算法——Reed-Shepp曲线、混合A*、轨迹优化、B样条、TOPP、碰撞检测、CHOMP/TrajOpt。今天做一个总结把面试官最爱问的15个运动规划问题整理在一起每个问题给出精炼的回答要点。面试运动规划岗自动驾驶规划、机器人运动规划、无人机轨迹规划这些问题出现的频率极高。我面了十几家公司的规划岗这些问题被问了不下50遍。一、基础概念类5题Q1路径规划和轨迹规划有什么区别路径规划找空间曲线从A到B走哪条路不考虑时间。轨迹规划在路径上加时间参数化什么时候走到哪个点。路径是几何的轨迹是时空的。轨迹可以求导得到速度/加速度路径不行。Q2完整约束和非完整约束有什么区别完整约束只限制位形比如关节限位-π ≤ q ≤ π。非完整约束限制速度比如车辆不能横向移动ẋ·sin(θ) - ẏ·cos(θ) 0。非完整约束不能积分成位形约束——它减少的是可控自由度而不是可动自由度。典型非完整系统阿克曼转向车辆、差速驱动机器人。完整系统的例子全向轮机器人omniwheel、机械臂每个关节独立可控。非完整约束对规划的影响不能直接用直线连接两个状态——必须用满足约束的曲线Dubins/Reed-Shepp曲线。Q3P问题、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题Q6A*和Dijkstra的区别是什么Dijkstra是A的特例启发函数h0。A用启发函数h(n)引导搜索方向比Dijkstra快很多。A的最优性条件是启发函数可容许admissible——h(n)不超过真实代价h(n)。A*的时间复杂度取决于启发函数质量——好的启发函数能让搜索从O(b^d)降到接近O(d)。Q7RRT和RRT*的核心区别RRT找到第一条路径就返回快速但不最优。RRT在每次添加新节点后做rewire——检查新节点附近的现有节点看通过新节点连接是否能减少代价。Rewire让RRT渐进逼近最优路径。代价是RRT比RRT慢2-5倍。Informed RRT在找到第一条路径后限制采样区域为椭球进一步加速优化。Q8DWA和TEB的区别DWADynamic Window Approach在速度空间中采样选取消耗函数最小的速度指令。TEBTimed Elastic Band在轨迹空间中优化用图优化方法同时优化轨迹形状和时间分配。DWA更快1ms但只能处理简单场景。TEB更慢5-20ms但能处理复杂约束运动学、动力学。ROS中导航栈默认DWAmove_base_flex支持TEB。说白了DWA是贪心策略——每一步选当前最优速度TEB是全局视野——看整条轨迹一起优化。Q9混合A*为什么在泊车场景中效果好三个原因。一是搜索空间包含朝向θ路径满足阿克曼转向模型——车一定能开过去。二是支持前进后退切换用Reed-Shepp曲线做解析扩展——泊车必须倒车。三是代价函数可以惩罚换向次数——用户不喜欢反复揉库。混合A的路径质量比RRT稳定确定性强比纯A可行考虑了运动学。Q10CHOMP和TrajOpt哪个更好看场景。CHOMP用软约束梯度下降实现简单适合障碍物简单的场景。TrajOpt用硬约束信赖域约束满足严格适合窄通道和复杂障碍物。两者都需要好的初始解通常由RRT提供。实际项目中经常组合使用——CHOMP粗优化TrajOpt精优化。三、工程实践类5题Q11运动规划模块的输入输出是什么输入当前位姿、目标位姿、地图栅格/点云/语义地图、运动学约束。输出一条可执行的轨迹时空点序列位置速度时间戳。有些系统输出路径速度曲线分开。Q12规划的频率一般多少全局路径规划1-10Hz每100ms-1s更新一次场景变化不大时可以降频。局部轨迹规划10-50Hz每20-100ms更新一次需要实时响应动态障碍物。时间参数化TOPP和路径规划同频路径变了就重算。频率选择的原则规划频率必须高于控制频率的一半以上。如果控制器200Hz5ms规划至少50Hz20ms。原因规划输出的轨迹需要在两个规划周期之间被控制器跟踪——规划频率太低会导致轨迹过期控制器跟踪误差大。Q13规划失败怎么处理分级处理。第一级放宽约束重试比如增大安全距离到障碍物距离的容差。第二级换算法重试RRT失败换PRMCHOMP失败换TrajOpt。第三级报告上层系统无法到达目标触发任务重规划比如换一个停车目标。工程上设置最大重试次数通常3-5次超过就放弃。还有一个常见的失败原因规划超时。RRT在复杂场景中可能需要几秒才能找到路径但规划超时设置通常500ms。解决方案用RRT-Connect双向搜索收敛更快或者混合A*有启发函数引导搜索更快。Q14怎么评估一条轨迹的质量五个指标路径长度越短越好、执行时间越短越好、最大jerk越小越舒适、离障碍物最小距离越大越安全、跟踪误差实际轨迹和规划轨迹的偏差。实际项目中给每个指标设阈值全过才算合格。更细致的评估把轨迹分段评估——起步段、巡航段、终点段分别看速度/加速度是否合理。起步段如果加速度突变说明jerk约束没处理好巡航段如果速度波动大说明轨迹不够平滑终点段如果停车时有余震overshoot说明末端速度/加速度边界条件没设好。Q15你在项目中用过哪些规划算法踩过什么坑这是开放式问题准备一个真实案例比如做AGV导航用的A全局规划DWA局部规划。踩过的坑A在窄通道中搜索时间长500ms解决方案是用visibility graph预处理减少搜索空间。DWA在动态障碍物场景中反应慢5Hz不够解决方案是把局部规划频率提到20Hz。小结15个高频问题覆盖了基础概念路径vs轨迹、约束类型、复杂度、算法原理A、RRT、DWA、混合A、CHOMP/TrajOpt、工程实践输入输出、频率、失败处理。准备面试时不要死记硬背答案——面试官追问两三个问题就能看出来你是真懂还是背书。核心是理解每个算法的适用场景和局限性能用自己项目中的案例来说明。下一篇是运动规划系列的收官篇——A*/RRT*/DWA/TEB的性能实测对比。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第233篇 多约束轨迹优化——CHOMP和TrajOpt框架下一篇预告第235篇 运动规划算法实测对比——A*/RRT*/DWA/TEB的性能数据有任何问题欢迎评论区留言我会尽量回复。