"); //-->
本文参考论文:
https://ai.stanford.edu/~ddolgov/papers/dolgov_gpp_stair08.pdf
1 hybrid A* 算法创新点
1.1 搜索方式
A*算法:在二维网格中进行搜索,本质上就是把车辆简化为质点,并且移动方向是固定的八个方向(或四个方向),移动距离也是确定的。但这不符合实际的车辆运动学模型。
hybrid A*算法:引入航向角,将搜索变成在
三个维度的空间中进行。符合车辆运动学模型。
1.2 车辆运动学模型
为了便于计算,hybrid A*采用车辆二自由度运动学模型(见上图),但是忽略了车辆加速度与前轮转角速度,于是经过简化的运动学模型如下
1.3 reeds-shepp曲线的引入
但是reeds-shepp曲线完全未考虑避障因素,但是由于reeds-shepp曲线比较简单易计算,所以构造速度非常快,使得先构造再检验是否碰撞成为可能,这里的碰撞指的是整条轨迹是否会与障碍物有交集。
因此不像传统A*不考虑中间过程,所以需要均匀采样整段时间,进行碰撞检验。假如该段轨迹无碰撞则加入搜索树中,作为候选轨迹,如下图
图a:假如每次搜索都用reeds-shepp,由下图a可见这个搜索轨迹构成的树规模很庞大,节点很多将会造成极大的计算量。
图b:但间歇性得用reeds-shepp和传统A*去搜索,在每N个节点中选取一个计算Reed-Shepp曲线(这里的N随启发函数递减而减少,即越发靠近终点时,N越小)。由下图b可见搜索树规模小,节点少。
但是在利用reeds-shepp曲线搜索时,若出现48种reeds-shepp曲线都会碰撞,也需要重新进行经典的A*搜索,这种混合的搜索使得搜索速度提升。
1.4 G的定义更丰富
在传统A*算法中,G是从起点到当前节点的路径消耗,由于一段直线前进的轨迹肯定优于反复前进倒退或扭曲的轨迹,因此我们对频繁切换速度 和前轮转向角 两个控制量的值这种行为进行惩罚,这样就能使得最后的轨迹更加合理。
还有很多为了轨迹合理可以惩罚的地方,这其实就是一个评价函数的设计,具体可以参考;
https://blog.csdn.net/weixin_65089713/article/details/123835309
但需要说明的是,如果是极端狭窄的泊车场景中,我们不得不采用复杂扭曲的轨迹。如下图
1.5 H的定义更丰富
按理来说,H函数应该是从当前节点位姿到终点节点位姿,同时满足避障以及车辆运动学约束的最短路径长度,这是真实路径,但这很难在还没采样搜索剩下的位置环境时就知道真实路径。
所以hybrid A* 设计两个H的子函数,H1代表符合车辆运动学约束但忽略碰撞因素的最短路径,H2代表满足避障约束但是忽略车辆运动学约束的最短路径,H定义为H1与H2的最大值。
H1:当前节点离终点较近时,更应该关注车辆运动学约束,忽略障碍物的情况下,路径不依赖于任何在线场景信息,可以通过离线的方式采样枚举所有reeds-shepp曲线可能,提前将路径长度记录出来,在线调用该函数时只需索引、插值即可返回函数值。同时,这项启发函数的主要目的是为修剪传统A*搜索树的分支,保证最后能精准衔接终止位姿。如下图
H2:当前节点离终点较远时,更应该关注避障行驶,防止陷入死胡同,利用传统A*的H进行计算。如下图
可见这样对启发函数的设计有利于提高搜索速度。
1.6 Voronoi势场函数
生成的路径必须与障碍物保持一定的距离,这也是最优轨迹的要求,由于传统的人工势场法的缺点是在狭窄路段构造了高势场,使得机器人或车辆无法通过,因此,构造Voronoi势场函数。首先,介绍一下Voronoi图。
Voronoi图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。每个点有一个它的最近邻区域。
每个Cell中包含的都是距离当前Cell距离最近的所有点,因此Cell的边界就是距离种子点最远的点的集合。利用这个特性,将采样障碍物的边界当做种子点,那么Cell的边界就是远离所有障碍物的可行驶路径。效果见下图
当然不可能就照着cell的边界去运动,因为设计的出发点是为了通过较窄的地方。在路较宽时,没有必要,所以我们需要构建一个势场,能够让车辆或机器人趋于cell的边界去运动。势场函数如下
*博客内容为网友个人发布,仅代表博主个人观点,如有侵权请联系工作人员删除。