面试相关
[[规划的一些感想]] [[时空规划]] [[刷题记录]] 优化问题 判断是否相交
Apollo¶
https://paul.pub/apollo-planning/ https://zhuanlan.zhihu.com/p/146367865
面经1¶
作者：cuke
链接：https://zhuanlan.zhihu.com/p/440844177
来源：知乎
一.轨迹优化¶
1.说明规划算法建模过程。（如何设计代价函数和约束）
2.说明轨迹规划和路径规划区别。
3.说明规划与控制的区别。（曲线）
4.说明DP和QP优化的时候考虑的约束及优化目标。
5.如何考虑障碍物？
6.说明Lattice和Em的基本思 路。
7.Lattice为什么使用五次多项式？多项式次数对于拟合曲线有什么影响？
8.什么是A、D、RRT？用途是什么？
9.说明Dijkstra和蚁群算法的特点。
10.搜索算法有哪些，用途是什么？
11.什么是轨迹生成算法？（曲线）
12.hybrid Astar算法流程及应用
二.控制算法¶
1.规划和控制的关系？如何相互配合影响的？
2.什么是运动控制？控制具体控制了什么，输入输出是什么？如何实现的？表现到车辆状态上又是怎样的？
3.什么是PID、LQR、MPC算法？用途是什么？分别解决了什么问题？
MPC 1）对于机器人而言，是位置和力。 X = X + dx * t + ½ (u/m) * t2，进而转换为 X’ = dx + (u/m) * t 。其中 u 指的是外部的作用力，目标是，尽量小的u，使得预测数值和观测数值之间的误差尽量小。这里面的一个问题是，如何确定在某个时间点需要达到的位置，这个位置应该是时间的函数。
约束：航向角 +- 25； 加速度 +- 1
优化项目：
1）期望的航向角以及加速度角度的变化尽量少，也就是油耗低或者用户的体验好；
2）时间越短越好
如何加上避动态障碍物 ？？
图 Udacity 车辆场景下规划出来的航向角
1) MPC 的预测轨迹点，在什么地方考虑了动态的障碍物。
2) 时间段约束在什么地方体现 ？
3) 可行性轨迹实际上是多条的曲线，在这些曲线中获取的最优解曲线。 曲线并且需要平滑处理
lattice : 位置的可行解空间
TEB和DWA都属于MPC family算法，与MPC一样，基于机器人的姿态和速度以及局部环境图的优化问题在特定时间范围内重复求解。在每个控制周期中，只有第一个时间步的控制变量（ 线速度，角速度）被发送到机器人。
最终转换为QP的二次求解器。
4.传统PID、LQR、MPC各自的优缺点有哪些？对于缺点有哪些解决方法？
5.PID超调如何解决，积分饱和如何解决？LQR如何建模，状态量有哪些，控制量有哪些？
6.如何设计MPC？
三.计算几何¶
1.如何求点在线上的投影？如何求点到直线距离？
2.如何求SL坐标系
3.两条直线的交点（向量）
4.碰撞检测方法
5.曲线（贝塞尔，b样条，正弦曲线，圆弧曲线，螺旋曲线等）
6.五次曲线、回旋线、三次样条曲线、B样条曲线的表示。
四.车辆动力学和运动学模型¶
1.车辆动力学和运动学模型不同，原因以及使用的情况
五.C++编程¶
1.C++函数指针有哪几类？函数指针、lambda、仿函数对象分别是什么？
2.如何利用谓词对给定容器进行自定义排序？
3.传递引用和传递值的区别？传递常引用和传递引用之间的区别？传递右值引用和传递引用之间的区别？
4.函数对象应该通过什么传递？
5.什么是万能引用？用途是什么？
6.什么是完美转发？用途是什么？
7.std::unorded_map和std::map之间的差异是什么？
8.虚函数、虚表的原理？
9.如何在c++中创建线程？如何在线程间同步？
10.互斥锁是什么？用途是什么？条件变量又是什么？为什么要用条件变量？
11.智能指针和祼指针之间的差异？为什么要用指针的引用计数？
12.智能指针分哪几种？std::unique_ptr，std::shared_ptr，std::weak_ptr各有何用途？
13.悬挂指针会导致什么问题？如何避免？
14.traits是什么？什么时候用traits？
6 参考答案（部分）¶
轨迹优化¶
1.说明规划算法建模过程。（如何设计代价函数和约束）
【参考回答】
代价函数：主流算法在frenet坐标系下进行规划，代价也表示在frenet坐标系下。
a) 代价函数：
横向路径维度：guidance+避障+光滑
guidance项：相对中心参考线的横向偏移距离
避障项：与障碍物的距离
光滑项：与参考线的heading夹角，曲率（对应轨迹半径、前轮转角大小），曲率变化率（对应前轮转向速率）
纵向维度：
guidance项：巡航速度偏差
舒适性：加速度，加加速度大小
避障：障碍物距离
b)约束：
横向路径：安全范围，保证不碰撞；heading，确保与参考线的夹角不过大；曲率：方向盘最大转角；曲率变化率：转向系统最大转向速率。
纵向：单调递增约束，保证不发生倒车；station上下限约束，保证不发生碰撞；最大车速约束，保证不超过设定目标速度；加速度边界约束；jerk上下限约束。
2.说明轨迹规划和路径规划区别。
【参考回答】
1).路径规划（Path/Motion Planning），是在不考虑临时或者移动的障碍物的前提下，对车辆在空间上的变化的规划；
2).轨迹规划（Trjectory Planning）一般轨迹规划包括横向规划和纵向规划，横向规划主要输出trajectory中的x, y, s，纵向规划主要填充轨迹上各点期望速度ds/dt。一般横纵解耦规划方案先规划横向，再规划纵向。
3.说明规划与控制的区别。（曲线）
【参考回答】
1).规划是基于环境信息给出一条需要被跟踪的轨迹（包括路径及路径上的速度信息），需要保证安全性、可行性、舒适性；
2).控制是对规划出轨迹进行横向、纵向的跟踪，使得车辆实际允许效果尽量贴近规划轨迹，同时也会再次进一步考虑舒适性、安全性等优化目标及约束。一般规划相对低频，控制更加高频。
4.说明DP和QP优化的时候考虑的约束及优化目标。
【参考回答】
此问题仅针对EM Planner架构，横向上DP主要考虑避障、参考线距离、舒适性，QP主要考虑对DP结果跟踪的精度、舒适性。
5.如何考虑障碍物？
【参考回答】
一般地，横向路径规划主要考虑oncoming障碍物以及静态障碍物；纵向针对动态障碍物进一步处理，确保安全。对于oncoming纵向结果会在横向上投影，下一帧基于新的速度规划结果规划路径。
6.说明Lattice和Em的基本思路。
【参考回答】
Lattice是网格化采样。路径规划采样：向前取若干个距离，每个距离采样不同横向距离，从而获得多排采样点，使用多项式连接不同排采样点获得候选路径；纵向规划采样：采样多各前方时间，每个时间采样不同距离形成一列候选距离，沿时间向前使用多项式连接各列候选距离形成候选距离随时间变化的纵向曲线。路径与纵向规划采样合并后得到候选轨迹，根据cost函数选取cost最低的最优轨迹输出；
EM Planner是在Lattice采样基础，针对采样结果再进行一次优化。采样可以更密集，直接使用直线连接，同时使用DP向前搜索提高效率；优化时考虑舒适性，并贴近DP选出的采样结果。
7.Lattice为什么使用五次多项式？多项式次数对于拟合曲线有什么影响？
【参考回答】
五次多项式有6个系数，起点和终点的0阶/1阶/2阶导约束正好是6个，形成满秩矩阵，唯一地确定多项式各个系数。
8.什么是A、D、RRT？用途是什么？
【参考回答】
A D是基于搜索的路径规划方法，RRT是基于概率采样的路径规划方法。
D 主要应用于动态环境下的路径优化，也能兼容静态环境，A 只能用于静态环境下的路径优化。D 的实现过程中有和Dijkstra、A 相似的思想，在初始路径规划的过程中，是一个反向Dijkstra算法，在遇障碍重新规划的过程中，可看做是一个启发式算法A*，只是起点是一些不固定的点，h()充当了启发函数的角色。
9.说明Dijkstra和蚁群算法的特点。
【参考回答】
是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
蚁群算法是用来寻找优化路径的概率型算法，具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。适用于大规模高复杂度的问题，只能保证结果是较优解，难以保证最优解。
10.搜索算法有哪些，用途是什么？
【参考回答】
Dijkstra、A、Lattice采样等。A是Dijkstra的升级版本，效率更高，Hybrid A在转向的采样空间内进行A搜索，主要用于非结构化道路场景如APA泊车；Lattice采样更多用于封闭结构化道路的规划。
11.Dijkstra算法demo
【参考回答】
Dijkstra是一种完备但低效的向周围均匀扩张的算法，采用贪心算法思想解决有权图最短路径问题，类似广度有限搜索；
A引入启发式函数牵引搜索的方向，提升搜索效率，但搜索结果无法保证满足运动学限制，Hybrid A是在向前搜索时在可行转角范围内采样不同转角，并使用该转角向前移动一定距离获得下一个位置。Hybrid A*搜索出的转角是不连续的，可能导致方向盘来回摆动，一般和需要再进行一次曲线光滑优化。
（参考深蓝课件）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
12.轨迹规划所使用的坐标系有哪些？它们的有什么不同？分别用于什么场景？
【参考回答】
一般有笛卡尔坐标系、Frenet坐标系2种，具有车道参考线的结构化道路一般可以使用Frenet坐标系，降低问题的数学复杂度，降低问题维度，提升求解效率。无参考线低速非结构化道路功能（如APA）一般使用笛卡尔坐标系。
面经3¶
作者：MrFive1001
链接：https://zhuanlan.zhihu.com/p/96008369
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
4. 滴滴(Offer)
滴滴总共四轮面试，一轮电话面、三轮现场面
一面（电话面）：
自我介绍、轨迹优化方法特点、了解的规划算法(10分钟)
Leetcode 跳跃游戏 (30分钟)
C++理论多态封装、智能指针、emback和pushback区别
现场面一共三面，每一轮流程是先手撕两个代码题，然后聊项目：
自我介绍、实习经历
速度规划流程及考虑因素、路径规划流程及代价
Lattice和Em基本思路、A星、Dijkstra和蚁群算法的特点
深度强化学习的特点及在无人驾驶中的应用
DP和QP优化的时候考虑的约束及优化目标
C++ 继承、多态、虚函数、emplace和push的区别、抽象类、智能指针、vector扩容、map底层、const的作用、指针引用数组的区别、public和private继承的特点
二叉树寻找所有最深叶节点的公共父节点
倒数第K大的数字
Dijkstra算法demo
利用random实现random
一个leetcode hard难度题
滴滴整体面试流程非常的高效、而且面试官都很专业，整体面试过程偏向于基础的代码能力(默默吐槽谈薪流程非常缓慢。)
5. 商汤(Offer)
加上hr面总共6面，持续了3个月左右，可以说从秋招开始到结束(捂脸)。
一面(系统组)：
自我介绍、实习经历
C++多态、继承、虚函数
青蛙走台阶的各种变形版
兔子生孩子，动态规划和公式计算两种方法
二叉树的分层打印
二面(系统组)：
代码：C++快排(1min)、二叉树变成数字、商汤笔试题目(N个数字M滑动窗口的最小值)、单调栈——还是没躲过笔试
C++多态、多种智能指针、vector扩容原理、C++的一些基础知识过了一遍
三面(规划组交叉面)：
本来简历是分到系统组的、结果交叉面的规划组才是我想去的组，所以后面加了一面
自我介绍、规划算法及如何考虑障碍物、规划算法的优缺点
FreeSpace的一些规划、RRT和A 星
强化学习的基本思路、DDPG的基本思路
四面(规划组)：
自我介绍
对无人驾驶公司的了解、想去的公司
算法题目（没印象了）
Lattice和Em planner特点、Lattice缺点的弥补
强化学习DDPG的更新方式、输入输出、Buffer size、学习率的影响
强化学习的Loss函数
总监面：
聊了半个多小时很宏观的东东
面经4¶
https://blog.csdn.net/weixin_42301220/article/details/129327035
面经5（大疆笔试）¶
- 第一块ROS，考察了ros的基本概念如roshandler，roslaunch，roscore等；
- 第二块Linux的使用，gdb调试，linux常用命令kill等；
- 第三块编程，代码题，看代码选答案。
- 第四块路径规划算法，A*，Dijkstra，插值，样条等；
- 第五块数学，几何，四元数，泛函，多项式，坐标变换，公式推导等。