guihua算法问题

zt3ff3n

规划与控制岗

一.轨迹优化

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算法？用途是什么？分别解决了什么问题？
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？
参考答案（部分）

规划与控制岗

一.轨迹优化

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*搜索出的转角是不连续的，可能导致方向盘来回摆动，一般和需要再进行一次曲线光滑优化。
（参考深蓝课件）
Maintain a priority queue to store all the nodes to be expanded  
The priority queue is initialized with the start state XS
Assign g(XS  )=0, and g(n)=infinite for all other nodes in the graph
Loop
If the queue is empty, return FALSE; break;  
Remove the node “n” with the lowest g(n) from the priority queue  
Mark node “n” as expanded  
If the node “n” is the goal state, return TRUE; break;  
For all unexpanded neighbors “m” of node “n”  
If g(m) = infinite  
g(m)= g(n) + Cnm  
Push node “m” into the queue  
If g(m) > g(n) + Cnm  
g(m)= g(n) + Cnm  
end  
End Loop12.轨迹规划所使用的坐标系有哪些？它们的有什么不同？分别用于什么场景？
【参考回答】
一般有笛卡尔坐标系、Frenet坐标系2种，具有车道参考线的结构化道路一般可以使用Frenet坐标系，降低问题的数学复杂度，降低问题维度，提升求解效率。无参考线低速非结构化道路功能（如APA）一般使用笛卡尔坐标系。