路径规划做为机器人导航中的一个重要的技术，一个好的路径规划可以极大地提高后续跟踪控制的效果，对机器人的运行好坏程度有非常直观的表现。从最初搜索一条有效路径（如Dijkstra、A*、RRT等），到现如今通过前端搜索，后端优化的方式得到一条考虑机器人运动学、动力学，安全性的高质量路径，众多学者、工程师提出了非常有效的路径规划方法。
  Hybird A* 算法只需通过搜索就可以得到一条平滑的高质量路径，在计算效率上有一定的优势（特别是在宽阔的位置）。本文需要有一定的路径规划基础，如掌握A*算法。
   具体算法可以参考：

Hybire A* 算法源程序 （需要安装ROS及相应依赖包）

操作步骤：

  1. 将初始位置节点放入列表openlist和列表closelist中；
  2. 如果openlist为空，没有有效路径，结束程序，否则，从openlist中选出启发值最小的节点Node min 并移除出openlist；
  3. 根据规则生成连接节点 Node min和目标点 Node goal 的曲线，如果曲线有效，则成功完成路径搜索，否则，根据机器人运动学模型以Node min为起点扩展新的节点 Node new ，并计算相应的距离、启发值等；
  4. 如果节点Node new不在closelist中，则将节点 Node new加入到closelist和openlist中，否则，以节点到起点的距离为判断标准更新openlist和closelist中与节点Node new对应的节点；
  5. 如果目标节点Node goal在closelist中，则成功完成路径搜索，否则继续从步骤2开始运行；以上Hybird A* 算法与基础A*算法的主要区别是在步骤3的“根据规则生成连接节点Node min和目标点Node goal  的曲线”。这里的“规则”非常丰富，无人驾驶上用得比较多的是Reeds-shepp，以及Dubins、高次曲线、贝塞尔曲线等，也可以根据自己的需求定义曲线。以下为曲线示意图。
图1
图2
图3
图4

小结

  1. Hybird A* 算法以较低的成本生成一条比较光滑的路径，但不是最优；
  2. 可以用不同方法生成多条曲线，选择其中一条最优的做为最终路径，如路径最短、曲率变化平缓等；
  3. 当步骤3的扩展步长较大时或曲线生成的条件过严，在地形狭窄的地方有可能无法搜索出路径；
  4. 同一个栅格只能存在一个节点；
图1
图2
图3
图4