面试

主管面

学习

一定要理解为 “你如何快速学习不熟悉的知识”。

成就

  • 一定要强调 Summer Research Scholarship 是 成绩够好 才行
    • (还要强调其实竞争很激烈，不是人人都可以进入的。成绩是硬要求)。
  • 在校时期学习成绩优异，获得荣誉学位。
  • 毕业设计 “导师评价很高”，得了 89 分 （尬吹）。

小项目

学习时间紧，没有亲手去实践。做学校里的项目呀。

你最大的优势和劣势是什么

  • 优势：做事情有主动性，不拖沓，有责任心。
    • 举个例子：在做论文课题的时候，几乎都是我自己找老师汇报进度和找老师讨论问题，很少有被老师催的时候。
    • 每一次跟老师讨论之后都会将讨论的内容和老师提出的意见进行详细记录。在中软杯的比赛中，主动承担答辩ppt的制作，并且每次排练之后都迅速对ppt的修改意见进行落实修改，前前后后改了十几版。
  • 劣势：有时候做事情比较急躁，容易导致粗心。

注意点 - 语速合理

自我介绍和项目介绍的时候，语速要合理。

还要随时关注面试官的反应，要给他合理的时间消化你说的话。蔚来2面教训，我完全忽略了面试官的反应，自顾自地在说话。

项目介绍

停车场车位分配算法

IT行业各类工程师面试自我介绍 https://zhuanlan.zhihu.com/p/20948480

我最近做过的项目是关于停车场的车位分配策略，主要涉及到 路径规划 和 C++编程的知识。

  • Abstract
    • 设计一个去中心化的车位分配算法。
    • 在考虑路径规划和避障的情况下，评估停车位分配算法 (停车时间)。
  • Introduction:
    • 就目前而言，自主泊车主要有两种方案，
    • 一种是汽车不与停车场做任何交流，用 SLAM (Simultaneous Location and Mapping) 建图， 用传感器融合之类的检测车位， 然后自主泊车。
      • 第一种想法的缺点是，当很多智能汽车都聚在一起的时候，很有可能就是大家都停下来，等待别的车让路。这样就会卡着不动了。
    • 第二种就是停车场本身有传感器，会把可用的停车位发给
      • 第二种想法是， 停车场控制和观察整个停车场，给智能汽车合理的指示。这样的话，就是很简单的时空路径规划，这样的论文很多。如果涉及人类驾驶员和智能汽车的混合交通场景， 停车场也可以通过预测人类驾驶员的行为，来实现局部避障。
  • Problem Setup
    • 一个单层平面停车场
    • 汽车从同一个入口进入 (不排队)
    • 停车场负责分配停车位，并生成一条参考路径 (汽车不需要绕圈圈 wandering 去 search slots)
    • 汽车会执行路径。但每辆车都会有本地避障功能去避让。
    • 到达停车位附近就会启动泊车算法
  • Method
    • 目前这个项目还处于比较初级的阶段， 我会假设所有车辆在随机位置开始，然后停车场会基于距离分配停车位。
      • 一种基于优先级 ， 和 Multi-agent Path Finding 是完全一样的。 优先级更高的车可以优先选择停车位。
        • Multi-agent Path Finding 可以用 Conflict Based Search， 还有 Prioritized 方法。
      • 一种是从停车位的角度出发，由停车位来选择最近的车， 有点像贪心算法。
    • 停车场用 Motion Planning 用的是 RRT* 和 Reeds Shepp 曲线计算泊车路径
    • 汽车可能会有局部冲突
      • 在冲突的车里随机选一辆重新规划起路径， 其他车辆会等待一个随机时长 (类似计算机网络处理冲突)
      • 缺点就是
  • Simulation Results
    • 开发了一套验证停车位分配算法的框架
    • 提出了两种简单停车分配算法 (距离和优先级)
  • 讨论 (可能的改进)
    • 基于距离和优先级的车位分配算法 (成本函数)
      • 求解多智能体路径规划 (比如 Multi-agent Path Finding, CBS 算法)
      • 求解优化规划问题 (比如 MinMax 等等的数学优化问题, 数学建模)
      • 抽象成 network flow 问题
      • 决策问题 - 强化学习理论
      • 车位占用率的问题： 实时占用率和预测占用率。高峰提醒、允许预定。
      • 尽量无碰撞、所以要控制拥塞程度。车道拥塞，不能让太多车一下子进入。
      • 是否考虑停车场的通道是否拥塞。
      • 在考虑通道是否拥塞的情况下，能否控制进场汽车数量。
      • 考虑加入更多的 Heuristic 去改进停车位的分配算法， 比如旁边是否有车，停车的时间等等
    • 路径规划 (motion planner)
    • 局部避障 (local obastacle avoidance)
      • 路径追踪/循迹 ， 纯追踪 (Pure Pursuit)， MPC 模型， LQR， PID
      • 百度停车算法, RRT*, 或者 Hybrid A* 算法。
    • 在混合交通 (人车) 的情况下，如何分配车位 ?
      • 动态环境， 例如车辆能够自由进出， 能否动态地分配车位？
      • 考虑如何智能汽车对人类驾驶员的会车策略， 如何预测人类驾驶员的行为。
        • 在决策的时候，考虑其他车辆、行人的行为。
        • 停下来？ 往左？往右？慢慢地往前走？
        • 可以预测其他车辆的行为，预测行人的行为。比如神经网络、各种滤波器。
      • 拓展到真实的停车场景。 就是汽车能自由进出，在有汽车进入停车场的同时，也有汽车驶出停车场。
        • 这样的话， 就可以动态地分配车位。可以很好地限流或者更快地找到车位。
    • 汽车排队的问题。
    • 路径规划是否满足交通规则。
      • 停车场固定路线行驶(循迹)

其他

Git

PID

从不懂到会用！PID从理论到实践~_哔哩哔哩_bilibili

  • PID 针对当前误差、历史累积误差、**未来误差变化率 **进行调整。
  • 如果只用 P 的话， 到了 Reference ，可能仍旧有误差。
    • 所以就引出了 “稳态误差” 。 利用线性系统的 叠加性， 再加其他项
  • 即使 P 项的输出不能改变误差 (误差一直不变)， 但误差因为积分的作用 (线性增加)，使得 I 项逐渐增大， 所以 I 项可以在稳态的状态下接近 Reference
    • 在接近 Reference 后， P 项为 0 。 但是 I 项跟过去的误差有关，所以现在 I 项是完全不变的(停止积累)， 这就达到了悬停作用。
    • 所以 P 项只能减小稳态误差， 而 I 项能完全去除稳态误差
  • 注意到， 在 P 项有作用的时候， I 项也在积累误差。这就很容易出现 “超调现象” 。
    • K 和 I 对 Rise Time 都有作用 ，这下知道为什么了吧（当然也会增加 Overshoot ）
    • 超调现象 叫 Overshoot ，就是超越了 Reference 线。
  • 可以对误差求微分， 这就是 D 项
    • 假设刚开始 e = 10, 过了一秒后， e = 5 了，这样太快了， 此时 $de = 5 - 10 = -5$
    • 如果对象接近 Reference 的速度太快， 那么 D 项就能开始瞬速压制输出， 避免 Overshoot
    • 用 P 项理解。 u = Kp * e + Kd * de 。 意思是，当 e 在 t 时刻的变化率太大时 (即未来的误差)， Kd 就开始起作用。
    • 显然，噪音会导致变化率不稳定(噪音不定)， 所以 D 项一般需要滤波器。
  • 谈一谈自动驾驶中的MPC控制 - 知乎 (zhihu.com)
    • PID 有很成熟的调参算法， 还有 Zeros 和 Poles 还有各种图可以分析效率
    • 如果弱智一点的话， 就是先调 P 项， 然后调 I 项 (PI 项通常是因为对响应时间有要求)， 最后调 D 项。
  • 特殊情况
    • 从不懂到会用！PID从理论到实践~_哔哩哔哩_bilibili
    • 积分限幅
      • 如果无人机被按住了，误差一直不变，那么积分项可能会非常大，因为我们要对积分项限制，即 $max(I, n)$
    • 积分分离
      • 如果误差突变 (比如 Reference 突变)， 误差大于一定值时，让积分项直接为 0 。
      • 主要原因是积分项会作为历史被记录下来，这样误差突变也会被保留下来， 这样会导致积分项特别大
      • 本来 I 项也应该在接近 Reference 才起作用。积分分离很合理。
    • 微分先行
      • 让 “实际高度” 的传感器值直接给 D 项 (D 项不再测量误差)
      • 避免 Reference 的频繁变化导致超调。
      • 如果 “实际高度” 的变化率太大， D 项也会起作用 (下降或上升)

梯度下降

【机器人状态估计】2. 为什么引入李群流形 李代数 求导 微分 四元数_哔哩哔哩_bilibili

已知 $ r = f(x)$ 其中 $f$ 叫损失函数。可以逆向求解 $x^{*}$

注意到， 由于 $f(x)$ 关于 $x$ 的解可能有多个 (非凸问题)

  • 比较著名的是梯度下降，通过一个 guess 的解 $x’$ 在 $f(x’)$ 处的线性化(即求梯度)， 找到能够下降的梯度
  • (这样 损失函数 就能保证在下一个迭代中减小)。然后进入下一个迭代。
  • 自动驾驶路径规划-Voronoi Planner - 知乎 (zhihu.com)
  • 自动驾驶运动规划-Hybird A*算法(续) - 知乎 (zhihu.com) ，
    • 轨迹优化的入门，就是 cost function 的设计， 各种奇怪的 Term 。
    • 然后用梯度下降，假设原本的位置 $x$ ， 新的位置是 $y$ ， 那么 cost function 的变化就是 $f(y) - f(x)$
    • 要在原本的位置 $x$ 处求导， 然后往梯度的反方向走。 这样就可以得到新的 $y$ 使得 cost function 变小。
    • 可见必须有一个初始解，然后也就是在初始解附近游荡。

李群

Pure Pursuit

路径规划与轨迹跟踪系列算法学习_第10讲_纯跟踪法_哔哩哔哩_bilibili

F1TENTH Autonomous Racing: Pure Pursuit - YouTube

  • 假设车辆后轮能够到达某个参考点， 那么就有以下几何关系
  • 重点是 车辆后轮 到参考点的距离 $ld$ , 夹脚 $2\alpha$ , 转动半径 $R$
  • 然后根据几何关系确定前轮转角 $\delta$

点到直线距离

这道题经常考到 ， 用相似三角形即可

机器人路径规划、轨迹优化系列课程_哔哩哔哩_bilibili

image-20210723213851646

用下面的相似三角形关系， 就可以计算出 $o$ 的坐标。然后 $|op|$ 的坐标都知道了， 还不会求就…. \(\frac{|vw|^2}{\vec{vp}\cdot\vec{vw}} = \frac{|vw||vw|}{|vp||vw|\cos{\alpha}} = \frac{|vw||vw|}{|vo||vw|} = \frac{|vw|}{|vo|}\)

RRT*

  • 就是 Choose Parent 和 Rewire
    • Choose Parent : 新的随机节点 $x_{new}$ 选择树上 (范围内) 最好的一点作为 Parent
    • Rewire: 树上(范围内) 的其他节点是否可以把 $x_{new}$ 作为 Parent 以减少代价？这步会删除旧的 Edge ，所以叫 Rewire

  • 注意这个圆的半径是在变化的， 论文里用的是 $R \sqrt{\log(N) / N}$ ， 这样可以不遍历那么多的节点

  • Choose Parent 是为每个随机点选择更好的父节点 (普通 RRT 随机点的父节点就是 Neighest Neighbour)
  • Rewire 除了对新的随机点改进， 还可以为树上已有的节点选择更高的父节点
    • 新的随机点 $x_{new}$ 。如果 圆内的近邻节点 的父节点 改为 $x_{new}$ 可以减小路径代价， 则进行更改。
  • 以上过程都会删除旧的
  • 机器人路径规划、轨迹优化系列课程_哔哩哔哩_bilibili

Reeds Shepp

  • 圆弧和线段
  • 可以根据起点和终点计算出两个圆的圆心
  • 根据向量方法计算出两个圆的切点