运动规划问答 -路径规划

1、Dijstra算法，算法流程

关键
初始化：

算法是基于图搜索的思想，所以需要先构建一个图，图中不包含障碍物，读入起点和终点信息，设置一个以代价作为键值排序的multiMap，起点入队，并设置起点是被标记过的，

进入循环

起点出队，multiMap移除这点，判断当前节点是否是终点，如果为终点则跳出循环,以这点作为邻居节点的当前结点，获取图中当前结点的邻居节点，各自到当前结点的代价距离，然后对所有邻居节点进行遍历，如果是之前已经标记过的，那么判断到起点的代价距离是否比当前大，如果大，则更新，并把邻居节点的前置节点设为当前结点，如果未标记，将该点的前置节点设为当前结点，并加入multiMap，标记上，然后重复这个过程直到multiMap为空，然后反转得到路径

2、RRT算法流程；

keyword: 采样，迭代，树，两点之间是否联通

首先初始化，输入起点，终点，地图信息

设置迭代次数，开始迭代，在地图无障碍区域进行采样，获得采样点，然后寻找与采样树中最近的点，以一定的步长扩展新的节点，判断二者连接是否存在障碍物，无障碍物则扩展新的节点到树中，循环这个过程，直到终点被加入树中，当然这需要满足一定的阈值。反向查询，最后生成路径

初始化整个空间，定义初始点、终点、采样点数、点与点之间的步长t等信息 在空间中随机产生一个点xrand 在已知树的点集合中找到距离这个随机点最近的点xnear 在xnear到xrand的直线方向上从xnear以步长t截取点xnew 判断从xnear到xnew之间是否存在障碍物，若存在则舍弃该点 将new点加入到树集合中 循环2~6，循环结束条件：有一个new点在终点的设定邻域内

(225条消息) RRT与RRT_算法具体步骤与程序详解（python）问题很多de流星的博客-CSDN博客_rrt算法

3、你用过的路径规划算法原理及特点

路径规划五种算法简述及对比

启发式搜索是利用启发函数来对搜索进行指导，从而实现高效的搜索

A 算法是一种在静态地图中求解最短路径的直接搜索方法。_

4 说一下a*算法的流程

初始化open_set和close_set；

• 将起点加入open_set中，并设置优先级为0（优先级最高）；
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点，则：
  • 从终点开始逐步追踪parent节点，一直达到起点；
  • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点，则：
  • 将节点n从open_set中删除，并加入close_set中；
  • 遍历节点n所有的邻近节点：
  • 如果邻近节点m在close_set中，则：
  • 跳过，选取下一个邻近节点
  • 如果邻近节点m也不在open_set中，则：
  • 设置节点m的parent为节点n
  • 计算节点m的优先级
  • 将节点m加入open_set中

5、 A*算法中openlist和closelist的作用，节点如何更新？

openlist存放已经获取到的邻居节点,但是还未处理,

closelist 存放的是已经处理过的节点

对于不是openlist的节点,将其加入优先队列中, 已经在的话则需要根据代价判断是否更新;而对于closelist存放的不再处理

6、hybrid A*算法以及优化

混合A再A算法的基础上考虑了车辆的运动学模型，即满足车辆的最大曲率约束，计算代价时考虑进去。

与A*区别：

扩展方式
A扩展时是从当前栅格的中心点，扩展到周围八个栅格的中心点，路径是两两中心点的连线
HybridA扩展一共六个方向，左圆前进、倒车，直线前进、倒车，右圆前进、倒车，通过系统状态方程进行扩展
A到达新的栅格，位置必定是栅格中心，而HybridA到达的位置可以是路径上的任一点。

连通图结构
混合A* 除了考虑（x,y）维度外，还考虑量车辆姿态 θ
启发函数：
混合A表示从当前节点位姿到终点位姿的，同时满足避障条件及车辆运动学约束条件的最短路径长度，分为non-holonomic without-obstacle和 with obstacles AnalyticExpand(nc)两种类型启发函数，考虑障碍物与否区分
对于无障碍物采用Reeds-Sheep曲线生成，如果路径与障碍物发生重叠，采用动态规划或者A搜索路径；
接近目标点
混合A靠近目标点直接连接即可，因为采样不一定能刚好到目标点，同时也是为了提升效率
A则要求搜索的当前节点为目标点

7 、 蚁群算法和常见的搜索算法有什么不同

正反馈，信息素
用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

(1)采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。

(2)每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。

(3)搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。

(4)启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。 [4]

8、 基于图论的规划方法其缺点是什么

不适合于高维问题，需要事先建立图，

9.曼哈顿距离与欧式距离的优缺点，

欧氏距离

$$D(x,y)=\sqrt{\sum _{i=1}^n{\left(x_i-y_i\right)}^2}$$

曼哈顿距离:

$$D(x,y)=\sum _{i=1}^k\left|x_i-y_i\right|$$

对于向量之间的差异进行计算过程中，各个维度差异的权值不同

常见距离度量方法优缺点对比！_mob604756ea26ec的技术博客_51CTO博客

(186条消息) 欧式距离和曼哈顿距离的比较_AliceWanderAI的博客-CSDN博客_曼哈顿距离和欧式距离

9说说DP算法的过程

这个可以参考
算法题64. 最小路径和
思想：把多阶段的决策过程转化为一系列单阶段的最优化问题来解决
逆向寻优，正向求值
应用
百度apollo中的em_planner也有用到DP的思想进行局部路径的搜索，再用QP的方式进行轨迹平滑。