0 Lattice Graph
考虑机器人运动模型下的路径规划中说道,不管是离散控制空间还是状态空间,生成的图形都是Lattice Graph。
但是,加入在离散的过程当中,发现因为当时份数选择的更多,就会导致离散时候彼此连接的很近,所以可以进行剪枝的操作。
那如何进行剪枝?最有效的是使用栅格地图直接网上套,即可完成,栅格地图的代表就是A Star算法。所以,所谓的混合A Star算法就是将A*与Lattice Graph相关联。
1 Hybrid A Star
之后,在搜索的过程当中选取不同的Control Input往前驱动我的系统向前积分(就是会有很多feasible motion connections,例如图上的弯弯的线,从中找出最优的),积分出来的这个State,我保持在栅格地图的这个节点方格里都只记录一个机器人的State。
因为现在是保持在栅格地图当中,每个节点方格只记录一个机器人的State,如上图所示,现在进入到同一个栅格中有两条线,所以要不要把原来的那个节点进行更新呢?看Cost,不过这里的Cost不是我们狭义理解的线段的长度,而是一种广义的Cost,比如上次说过的BVP问题当中,Cost可以是时间、消耗的能量、路径的长度、终端状态惩罚项的累加等等。如果新的节点比老节点的Cost要少,就进行更新。
综上,永远保证一个网格当中只有一个节点。
2 Hybrid A Star伪代码
关于A*的伪代码详解
Hybrid A Star
A*算法当中最重要的一点就是找它的邻居(neighbors),其实就是上下左右斜对角。
在找邻居的过程当中,如果发现栅格原先没有被记录,那么就进行一个记录,如果在找邻居发现栅格已经被记录,则看Cost,之后对比决定是否进行更新。
3 启发式函数选择
启发式函数的选择与普通的A*可以是不一样的。
看是否设计动力学模型(&是否考虑障碍物)。
4 One Shot
这种方法就是HA*扩散到一定的程度的时候,直接在某一点计算与终点的理论距离,如果得出来的路径上没有障碍物且符合运动学约束的话那就直接走(因为这就是最优的路径了),可以设置扩散到第几个节点(N = ?)的时候去做一下这个One Shot,相当于买彩票一样的,在无人机的路径规划上还是挺有用的。
5 Application
文章来源:https://www.toymoban.com/news/detail-412767.html
6 总结
混合A算法产生的路径并非最优的,需要进行两个阶段进行优化:文章来源地址https://www.toymoban.com/news/detail-412767.html
- 对轨迹上的顶点进行非线性优化,以改善解的长度和平滑度。
- 执行非参数插值。
到了这里,关于混合A*算法---Hybrid A Star的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!