先睹为快!Hybrid A*如何助力“停车自由”
2022-10-26

周末时光,携全家人到商场购物的你,驾车来到购物中心,下车潇洒关上车门,用手机发送泊车指令让车辆自主完成行驶、避障、找寻车位、泊入车位;结束愉快的一天,再用手机给车辆发送定位,车辆重复上述整套动作,自主泊出车位,并前往上车地点迎接。

 

自动泊车的终极理想状态,莫过于此。

 

这让人不禁想起《魔兽争霸》里的“寻路指引”机制。该功能解决了“从起点到目标地点最佳路径”问题——即成功避开障碍物、敌人,并以更低的成本(装备、时间、金钱等)到达目的地。

 

可见,路径优化算法在生活中应用广泛。从虚拟世界到现实场景,普遍都能找到自动寻路功能的衍生。

 

 

自动泊车,如何“寻路”

 

自动泊车作为常用的智驾功能,主要涉及模块有感知、定位、规划、控制等。其中,路径规划这一环节至关重要,其结合感知和定位,计算出合理的车辆行驶轨迹。若想让目标对象在规定范围内的区域,找到一条从起点到终点的无碰撞安全路径,其背后离不开高效的代码运算。

 

常规的路径规划算法有Dijkstra、A*等。

 

Dijkstra算法主要是通过“贪心原则”,解决从一个节点到另一个节点的最短路径问题。主要特点是每次迭代时选择的下一个节点是当前节点最近的子节点,所以每一次迭代行进的路径是最短的。但是Dijkstra算法的搜索没有方向性,会产生大量冗余的搜索操作。

 

在Dijkstra的启示下,A*算法加上了一些启发性的信息,引导搜索算法快速搜索到目标,在已知终点位置下,借助一个启发函数来引导搜索的过程:

 

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

 

其中:

f(n) 是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。

g(n) 是节点n距离起点的代价。

h(n) 是节点n距离终点的预计代价,这也就是A*算法的启发函数。

 

 

A*算法类似于计算预估代价过程中网格化空间,节点只能沿着节点周边8个方向进行遍历。既不会考虑运动物体的方向,也不考虑物体的运动实迹,并且假定物体总能转移到邻近格点中。

 

事实上这并不符合车辆的运动轨迹。因此A*不完全适用于车辆,考虑到车辆的运动学特性,Hybrid A*算法应运而生。

 

 

Hybrid A*算法,是一种图搜索算法,改进于A*算法,是目前主流的路径规划算法。它主要分为如下阶段:

 

1、先应用A*算法,生成costmap地图,此地图表示每个栅格到终点栅格的heuristic cost值,用于Hybrid A*中,指引扩展点的搜索方向,往cost小的方向扩展。

 

2、对当前节点扩展并生成最短RS曲线。命中终点后,通过碰撞检测检查RS路径有无碰撞障碍物,如果没有碰撞,则搜索成功并回溯路径,若碰撞则继续搜索下一节点。

 

Hybrid A*,提升自动泊车体验

 

Hybrid A*算法与普通A*算法最大的不同,是在后者的基础上加上了对车辆运动学约束的考虑。该算法目前的应用场景有车辆掉头,泊车等对方向盘控制要求较高的场景。而自动泊车的路径规划相对复杂,涉及障碍物和车辆的轨迹预测、可行驶区域选择、局部轨迹规划和车辆控制等内容。

 

作为寅家科技泊车路径规划算法之一,基于Hybrid A*的规划方法,可协同控制模块对检测到的车位实现直接泊车,无需手动调整至特定位置。同时对Hybrid A*出来的路径进行平滑优化,并对其搜索路径规划和基于几何规则的路径规划这两阶段泊车策略做好衔接,能更好地解决自动泊车场景中出现的难点痛点,从而提升驾驶员泊车效率和舒适度,实现更顺畅的泊车体验。

 

针对特殊需求,迭代进行时。目前实际量产的自动泊车方案中,依旧存在若干技术难点,例如:对于死胡同底部车位,还不能实现车头入库,或重新退出倒车进胡同。寅家科技自动泊车解决方案利用Hybrid A*算法能够实现包括死胡同车位在内的绝大多数泊车应用场景,即各个角度的车位均可实现车头车尾入库。

 

寅家科技自动泊车系统具备优秀的软硬件一体化能力,未来还将持续深化核心算法的独特优势,在不增加硬件成本的情况下,不断打磨优化泊车体验,为更多合作伙伴提供性能领先、快捷落地的产品解决方案。