江苏龙网

  1. 主页 > 生活百科 > >

运动规划之搜索算法：前端规划、后端轨迹生成到状态求解( 六 )

算法

  • 用起始状态XS初始化优先队列
  • 设置g(XS)=0,对图中的其他节点设置g(n)=无穷
  • 循环:
  • 如果队列为空,返回FALSE并退出循环
  • 从队列中取出f(n)=g(n)+h(n)最小的节点“n”
  • 将节点“n”标记为已扩展
  • 如果节点“n”是目标状态,返回TRUE并退出循环
  • 对节点“n”的所有未扩展邻居节点“m”:
  • 如果g(m)=无穷
  • g(m)= g(n) + Cnm
  • 将节点“m”加入队列
  • 如果g(m)>g(n)+Cnm
  • g(m)= g(n) + Cnm
  • 结束对邻居节点循环
  • 结束主循环 ::: 通过对启发式函数的调节，可以达成控制A* 的行为：
  • 一种极端情况，如果h(n)是0 ， 则只有g(n)起作用，此时A* 演变成Dijkstra算法，这保证能找到最短路径 。
  • 如果h(n)经常都比从n移动到目标的实际代价?。ɑ蛘呦嗟龋??则A保证能找到一条最短路径 。h(n)越小，A扩展的结点越多 ， 运行就得越慢 。
  • 如果h(n)精确地等于从n移动到目标的代价，则A 将会仅仅寻找最佳路径而不扩展别的任何结点，这会运行得非常快 。尽管这不可能在所有情况下发生，但是你仍可以在一些特殊情况下让它们精确地相等 。只要提供完美的信息，A会运行得很完美 ， 认识这一点很好 。
  • 如果h(n)有时比从n移动到目标的实际代价高，则A* 不能保证找到一条最短路径，但它运行得更快 。
  • 另一种极端情况，如果h(n)比g(n)大很多，则只有h(n)起作用，A* 就演变成了BFS算法 。
    如果目标的引力太低，会得到最短路径，不过速度变慢了；如果目标引力太高，那就放弃了最短路径，但A运行得更快，所以最优路径和最快搜索在复杂情况下需要有一个取舍/平衡 。
    A的这个特性非常有用 。例如，你会发现在某些情况下 ， 你希望得到一条好的路径 ， 而不是一条完美的路径 ， 为了权衡g(n)和h(n) ， 你可以修改任意一个 。

    • 运动规划之搜索算法：前端规划、后端轨迹生成到状态求解

    文章插图
    如果alpha是0 ， 则改进后的代价函数的值总是1 。这种情况下 ， 地形代价被完全忽略，A工作变成简单地判断一个网格可否通过 。如果alpha是1，则最初的代价函数将起作用，然后你得到了A的所有优点 。你可以设置alpha的值为0到1的任意值 。
    可以考虑对启发式函数的返回值做选择：绝对最小代价或者期望最小代价 。例如，如果你的地图大部分地形代价为2，其它一些地方是代价为1的道路，那么你可以考虑让启发式函数不考虑道路，而只返回2距离 。
    速度和精确度之间的选择并不是全局固定对 。在地图上的某些区域，精确度是重要的，你可以基于此进行动态选择 。例如，假设我们可能在某点停止重新计算路径或者改变方向，则在接近当前位置的地方，选择一条好的路径则是更重要的，对于在地图上的一个安全区域，最短路径也许并不十分重要，但是当从一个危险区域脱离对时候，轨迹的精度是最重要的 。
    同样通过对g(n)或者f(n)的调节，也可以达成A具体动作的控制
    • 通过加上障碍物cost function到g(n)或者f(n)（这两个动作是一个意思） ， 可以实现规划路径在障碍物中间 。
    • 通过加上车辆几何或者轨迹kappa平滑度cost function的到g(n)或者f(n)，可以实现规划出来的路径是平滑变化的 。
    • 通过加上到way point的cost function的到g(n)或者f(n)，规划出来的路径则倾向于走way points的方向 。
    • 构造精确启发函数的一种方法是预先计算任意一对结点之间最短路径的长度 。有几种方法可以近似模拟这种启发函数：
    1.【降采样地图-预计算】在密集栅格图的基础上添加一个分辨率更大的稀疏栅格图 。预计算稀疏图中任意两个栅格的最短路径 。2.【waypoings-预计算】在密集栅格图上，预计算任意两个way points的的最短路径 。


    推荐阅读


    上一篇：TensorRT是如何做到架构更快的？

    下一篇：Java网络代理：探索代理服务器与虚拟网络技术