[人工智能]无人驾驶-规划-混合A*

一、混合A*算法变更了连通图结构。

与A算法在网格上搜索相比，混合A算法额外考虑了θ这一维度，从而将连续的三维(x, y, θ)状态空间网格化。且混合A*使用车辆后轴中心点坐标，使用θ代表车辆位姿。

二、混合A*更改了节点拓展方式。

假设当前节点Nodecurrent中具体记录着车辆位姿(x, y, θ)，混合A算法要求在v, Φ在单位时间1.0秒内采样为某常值，是的车辆以初始状态在单位时间内1.0秒内按照v, Φ行驶，通过前向模拟获得一段始于起点位姿的符合车辆运动学的行车路径，且路径末端位姿落入的三位网格对应子节点Nodechild。其中，保证v∈{-vmax， vmax}， Φ∈{-Φmax，0，Φmax}条件下至少可拓展6个子节点。在前向模拟过程中，混合A忽略车辆加速度以及前轮转角速度，仅考虑最基础的自行车模型，如下：

在1.0秒内，设置v恒为vmax，Φ恒为Φmax，则可以确定t∈[0, 1]时间内车辆的运动轨迹。

θ(t) = θ(0) + [vmax * tan(-Φmax) / Lw] * t

x(t) = x(0) + ∫ v(τ)* cos(θ) dτ;

y(t) = y(0) + ∫ v(τ)* sin(θ) dτ; v∈[0, 1]

[x(t), y(t), θ(t)]对应车辆在t∈[0, 1]区间上的运动轨迹，这条完整轨迹连通其末端位姿都记录着子节点Node中。

v∈{-vmax， vmax}， Φ∈{-Φmax，0，Φmax}。一共六种组合，可以生成六种轨迹

三、混合A*丰富了每一个节点所需记录的字段类别。

除记录f, g, h, parent_idx等之外，每一个节点还记录详细的位姿数值。

另外，每一个子节点必须准确专门开辟traj字段记录从其父节点拓展而来的1.0行车记录，用等时间间隔的密集有序散点集表示。

四、混合A*算法丰富了遍历搜索策略。

引入了Reeds-Sheep曲线生成机制，任意始末位姿信息之间的最短路径归纳为48种情况，可以通过圆弧段和直线段的各种排列组合方式。

但Reeds-Sheep曲线并没有考虑避障因素，使用Reeds-Sheep的构造速度。如果检测到碰撞，则抛弃Reeds-Sheep曲线，重新使用A*搜索。

五、混合A*完善了节点碰撞检验方式。

混合A*在拓展子节点时，除检验子节点对应的车辆位姿是否与障碍物相撞外，也会检验整条前向模拟的轨迹是否与障碍物有重叠。可以通过精细、均匀采样，检测避障情况。

六、混合A*算法丰富了函数g的定义。

当前节点到子节点的真实里程值即车辆在单位时间1.0秒内的运动距离，可直接由v*1.0s算出。

七、混合A*算法完善了启发函数h的定义。

h函数表示从当前节点位姿到终点位姿的，同时满足避障条件及车辆运动学约束条件的最短路径长度。

八、泊车场景下，对调始末位姿有助解决起点宽敞而终点狭窄的泊车决策任务。