Hybird A*算法
操作步骤：小结
路径规划做为机器人导航中的一个重要的技术，一个好的路径规划可以极大地提高后续跟踪控制的效果，对机器人的运行好坏程度有非常直观的表现。从最初搜索一条有效路径（如Dijkstra、A*、RRT等），到现如今通过前端搜索，后端优化的方式得到一条考虑机器人运动学、动力学，安全性的高质量路径，众多学者、工程师提出了非常有效的路径规划方法。
Hybird A* 算法只需通过搜索就可以得到一条平滑的高质量路径，在计算效率上有一定的优势（特别是在宽阔的位置）。本文需要有一定的路径规划基础，如掌握A*算法。
具体算法可以参考：
Hybire A* 算法源程序 （需要安装ROS及相应依赖包）
操作步骤：
将初始位置节点放入列表openlist和列表closelist中；如果openlist为空，没有有效路径，结束程序，否则，从openlist中选出启发值最小的节点
N
o
d
e
m
i
n
Node_{min}
Nodemin并移除出openlist；根据规则生成连接节点
N
o
d
e
m
i
n
Node_{min}
Nodemin 和目标点
N
o
d
e
g
o
a
l
Node_{goal}
Nodegoal 的曲线，如果曲线有效，则成功完成路径搜索，否则，根据机器人运动学模型以
N
o
d
e
m
i
n
Node_{min}
Nodemin 为起点扩展新的节点
N
o
d
e
n
e
w
Node_{new}
Nodenew，并计算相应的距离、启发值等；如果节点
N
o
d
e
n
e
w
Node_{new}
Nodenew 不在closelist中，则将节点
N
o
d
e
n
e
w
Node_{new}
Nodenew加入到closelist和openlist中，否则，以节点到起点的距离为判断标准更新openlist和closelist中与节点
N
o
d
e
n
e
w
Node_{new}
Nodenew对应的节点；如果目标节点
N
o
d
e
g
o
a
l
Node_{goal}
Nodegoal 在closelist中，则成功完成路径搜索，否则继续从步骤2开始运行； 以上Hybird A* 算法与基础A*算法的主要区别是在步骤3的“根据规则生成连接节点
N
o
d
e
m
i
n
Node_{min}
Nodemin 和目标点
N
o
d
e
g
o
a
l
Node_{goal}
Nodegoal 的曲线”。这里的“规则”非常丰富，无人驾驶上用得比较多的是Reeds-shepp，以及Dubins、高次曲线、贝塞尔曲线等，也可以根据自己的需求定义曲线。以下为曲线示意图。
图1
图2
图3
图4
小结
Hybird A* 算法以较低的成本生成一条比较光滑的路径，但不是最优；可以用不同方法生成多条曲线，选择其中一条最优的做为最终路径，如路径最短、曲率变化平缓等；当步骤3的扩展步长较大时或曲线生成的条件过严，在地形狭窄的地方有可能无法搜索出路径；同一个栅格只能存在一个节点；
图1
图2
图3
图4
