锦州 做网站,网站每年需要续费吗,六安亿联网络科技有限公司,黄山旅游攻略景点必去目录
案例一——Hybrid A*#xff08;基于正向运动学#xff09;
1、基本思想
2、 实现流程 3、启发函数设计
4、分析扩张#xff08;Analytic Expansions#xff09;
5、分级规划#xff08;Hierarchical planning#xff09;
案例二——State Lattice Planning基于正向运动学
1、基本思想
2、 实现流程 3、启发函数设计
4、分析扩张Analytic Expansions
5、分级规划Hierarchical planning
案例二——State Lattice Planning基于逆向运动学
1、基本思想
2、Conformal Lattice
3、目标状态实例
4、生成路径集合
5、代价值评估与路径选择
案例比较 案例一——Hybrid A*基于正向运动学
1、基本思想 Hybrid A*是A*算法的一种扩展本质也是一种图搜索算法Hybrid A*有以下特点
通过在控制空间中实时构件状态图 整体思想是在控制空间中采样利用前向积分的方式生成多条运动基元作为状态图的边。以自行车模型为例输入量有两个分别是运动速度v和前轮转角φ为了简化过程可以假设速度恒定此时只需要考虑φ一个变量可以假设φ∈[-umax, umax]对其做等距的离散采样上图采样了三份实际应用当中会分成跟多份取得的三个控制量分别为-umax0和umax然后对这三个控制量进行前向仿真/积分给定初始状态量给定时间△t通过积分得到新的状态
在网格地图中修剪一些节点减少图的大小剪枝 若在采样时状态空间取的足够密采样等距距离足够小那么会导致图中的节点和边过多极大地消耗计算资源因此为了保证整体算法的实时性Hybrid A*采用剪枝的操作将状态空间进行离散得到网格若多个state落入同一个网格中那么就选择最优的一个state(cost最小)保留
使用与A*算法相同的方法在状态图上搜索路径 A*算法与Hybrid A*算法的比较 A*将代价值与网格中心联系并且只访问与网格中心相对应的状态Hybrid A*为每一个网格赋予了连续的状态通过在模型的控制空间中采样并积分得到每一个网格对应的分数是其关联的连续状态下的代价值。
2、 实现流程
下面用伪代码的方式对Hybrid A*算法的实现流程进行简要描述
Algorithm Astar(G, start):let open_list be priority queue;g[start] : 0;f[start] : g[start] h[start];open_list.push(start,f[start]);while (open_list is not empty):current : open_list.pop();mark current as visitedif current is the goal:return current;// 通过从控制空间采样和前向仿真来扩展邻居节点for all unvisited neighbours next of current in Graph G:next_cost : g[current] cost(current,next);if next is not in open_list:open_list.push(next,next_cost h[next]) // 合并在离散空间中占用相同单元的连续坐标状态else:if g[next] next_cost:g[next] : next_cost;f[next] : next_cost h[next]; 对于Hybrid A*算法g(n)不单单表示路径距离上的代价值还包括一些其他方面的代价比如方向改变包括前后和左右的惩罚项 而对于启发式函数h(n)的设置可以用经典的欧几里得距离或和曼哈顿距离也可以用一些其它的方式使整体的搜索效率更高这方面会在下面讲解 3、启发函数设计 在Practical search techniques in path planning for autonomous driving. 论文中作者给出了两种启发函数的设计分别是
Non-holonomic-without-obstacles 这种启发式函数的估计是基于Reeds Sheep Path的方法此方法考虑了车辆本身的特性却忽略了环境
Holonomic-with-obstacles 这种启发式函数的估计是基于目标节点和当前正在扩展的顶点之间的最短距离此方法忽略了车辆本身的特性只考虑了障碍物。 原论文中给出了两个特定场景下使用不同的启发式函数取得的效果如下图所示 (a)使用最简单的欧几里得距离作为启发式函数 (b)使用non-holonomic-without-obstacles作为启发式函数 (c)使用non-holonomic-without-obstacles作为启发式函数 (d)non-holonomic-without-obstacles和Holonomic-with-obstacles组合使用 通过(a)图和(b)图的比较可以得到相比与简单使用欧几里得距离使用non-holonomic-without-obstacles作为启发式函数使树节点缩小了接近十倍效率有显著的提升 (c)(d)图中是一个更为复杂的场景(c)图表示在复杂场景下单纯使用non-holonomic-without-obstacles作为启发式函数会导致树的规模很大因为没有考虑环境障碍物的因素需要把环境探索完全才能得到可行的路径 而将non-holonomic-without-obstacles和Holonomic-with-obstacles组合进行使用就能得到(d)图所示的路径有前面的学习可知通过一次完整的迪杰斯特拉算法可以实现图中某个节点到其他所有节点啊之间的距离利用这个性质在做Hybrid A*算法前先从终点反向的进行一次迪杰斯特拉算法对整个图进行遍历我们可以得到图中任意节点到终点的最短路劲考虑障碍物将节点距离记录在表格中前期的离线收集过程。然后在Hybrid A*算法实时的搜索时直接根据当前位置从表格中获取对应的离终点考虑障碍物的最短路径。
4、分析扩张Analytic Expansions 论文指出离散搜索前向积分永远无法达到精确的连续目标状态整体的精度还取决于A*网格的分辨率因此文章中使用Reeds Shepp Path解析地连接当前节点和目标节点利用这种方法可以大大提高障碍物在稀疏环境下的搜索速度。
5、分级规划Hierarchical planning 在一个复杂的状态空间下想要一次性找到两点之间的最优轨迹是比较困难的分级规划的思想就是利用分布的思路先利用某种方式上图是利用Hybrid A*获得一条初解全局最优解再基于初解做局部的平滑得到局部最优解。 由Hybrid A*得到的路径通常是次优的主要有两个原因一是在剪枝的过程中每一个栅格内都只保留一个state这种操作会导致在某种层面上不是最优的二是在控制空间采样时不管是对前轮转角方向盘转角或者是转角变化率进行采样都无法实现严格意义上的连续最终的结果可能并不是很平滑。因此需要进一步改善。 论文中通过采用共轭梯度下降法对Hybrid A*路径进行光滑处理。
案例二——State Lattice Planning基于逆向运动学
1、基本思想 在状态空间中采用获得终点状态一系列离散的点 可以在Frenet坐标系下采样也可以在Cartesian坐标系下采样再通过求解边界值BVP问题来获得运动基元通过计算每条路径的成本选择最佳路径。
2、Conformal Lattice conformal lattice指的是在结构化道路上定义的一种采样规则大致是在在横向上获取目标状态沿道路目标点横向偏移采样在纵向上沿着车道中心线行驶能够在避开障碍的同时加快规划过程。
3、目标状态实例 目标状态从目标点沿道路横向偏移采样具体的采样规则需要根据当前速度和其他因素进行调整。比如在纵向上生成的路径的长度弧长往往需要和车速关联在低速时往往希望弧长短一些因为在低速时弧长过长会使车辆运动对应位置时失去时效性而在高速时往往希望弧长长一些弧长过短不利于下一时间对环境事物的判断。 另一方面在侧向方向上的采样也有特定的策略比如在拥堵场景下采样距离过大可能会导致无解。
4、生成路径集合 在采样结束后要进行边界值问题BVP处理在Frenet坐标系中可以用五次多项式进行处理在Cartesian坐标系中可以用三次螺旋线进行处理。
5、代价值评估与路径选择 代价函数的设计往往要考虑多个方面为了简化问题可以简单考虑安全性、平滑性和对中心线的贴合度三个方面的代价函数考虑
安全性 平滑性 中心线贴合度 将这三个因素进行不同的权重进行组合计算总的代价函数 得到了代价函数后就可以评估生成的各曲线的代价值进而获得最优路径。
案例比较 案例一是基于正向运动学的方法案例二则是基于逆向运动学的方法下面介绍这两种运动学方法以及它们的对比。 正向运动学方法对应上图中的在控制空间采样在知道控制量v、u以及给定时间t通过前向积分的方式得到一系列的轨迹而逆向运动学对应上图中在状态空间中采样此时的输入量是起始和终点的状态量通过起点和终点的状态量反推中间的状态量和输入量。
正向运动学控制空间采样 优点只要给定初始状态和控制变量通过运动学/动力学模型进行前向积分的方式即可得到 整个状态轨迹 缺点缺少对目标点的引导单纯依靠启发式函数来引导搜索过程。
逆向运动学状态空间采样 优点具有较强的任务引导性直接生成朝着目标的采样状态 缺点BVP问题较难处理 并且采样的规则需要精心计算。
