规划控制

Fig.2 A* 与Hybrid-A* 节点拓展示意图

Hybrid-A*算法在规划路径时主要分为如下几个步骤：

搜索空间的离散化：将空间划分成小网格(grid)；

搜索树的扩展(Analytic Expansions)：利用RS/Dubins等曲线连接当前节点与目标节点，并对该轨迹进行碰撞检测，若无碰撞，则结束搜索，其规划轨迹为当前路径到目标节点的path1+当前节点回溯到起始节点的路径path2；若碰撞，则放弃该曲线，并从Open List中重新寻找节点，继续搜索；

路径优化：经过Hybrid-A*得出的路径往往不是最优的，通常存在不必要的转向，为了获得更好的预期驾驶行为，还需对轨迹进行进一步优化（如轨迹平滑/插值等）；

Fig.3 梯度下降法平滑轨迹

启发式的选择

启发式的选择

对于A* 算法而言，在某一结点n处的代价函数可以表示为：

f(n) = g(n) + h(n)

式中，g(n)为状态空间中从初始点到当前节点n的实际代价；

------h(n)为当前节点n到目标节点最佳路径的估计代价；

在代价函数的选择上，Hybrid-A*结合实际运行情况以及车辆当前的位姿，对车辆的航向、档位、曲率以及方向等施加惩罚，使其更符合实际运动场景。

在A* 算法中，启发式一般采用两个节点间的距离之和，而Hybrid-A*算法完善了启发式函数h的定义，主要采用了如下两种启发式以提高搜索效率。

non-holonomic-without-obstacles-heuristic：考虑车辆的运动约束但不考虑障碍物，一般使用RS曲线、Dubins曲线等；

holonomic-with-obstacles-heuristic：考虑障碍物，不考虑车辆的运动约束；

Fig.4 启发式对比

项目参考

项目参考

[1] karlkurzer/path_planner

该项目为karl kurzer的硕士课题，其论文及链接：Path Planning in Unstructured Environments: A Real-time Hybrid A* Implementation for Fast and Deterministic Path Generation for the KTH Research Concept Vehicle

Fig.5 规划轨迹

[2] HAStar_ParkingPlanner

该项目主要是基于Apollo开源项目中Hybrid A* 算法实现泊车的路径规划方法，分别进行了垂直和水平车位的测试，算是一个阉割版，效果有待提升。

Fig.6 垂直车位

[3] Matlab Hybrid_A*

该项目为Hybrid- A*的Matlab版本实现，对于理解其实现的原理比较有帮组。

Fig.7 泊车示意图

参考文献

参考文献

[1] Dolgov D , Thrun S , Montemerlo M , et al. Practical Search Techniques in Path Planning for Autonomous Driving[J]. ann arbor, 2008.

[2] Dolgov D , Thrun S , Montemerlo M , et al. Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments[J]. The International Journal of Robotics Research, 2010, 29(5):485-501.

[3]古月居_混合A*算法研究

[4] 自动驾驶运动规划-Hybird A*算法

[5] Gradient-Informed Path Smoothing for Wheeled Mobile Robots (GRIPS) (github.com)

学机器人SLAM/3D视觉，就上 cvlife.net ！

点击领取学习资料 → 机器人SLAM学习资料大礼包

独家重磅课程官网：cvlife.net

全国最大的机器人SLAM开发者社区

技术交流群

— 版权声明 —

本公众号原创内容版权属计算机视觉life所有；从公开渠道收集、整理及授权转载的非原创文字、图片和音视频资料，版权属原作者。如果侵权，请联系我们，会及时删除。返回搜狐，查看更多