跳转至

基于搜索的路径规划

两个基本任务

  • Exploration 探索
  • Exploitation 利用

1. 找可行解的算法

1.1 PRM(Probabilistic Road Map)

  1. Learning phase

    alt text

    • 在地图中随机撒点
    • 对每个点进行碰撞检测，如果碰撞，则删除该点
    • 找到每个点的邻居，连线，如果连线碰撞，则删除该线

  2. Query phase

    • 使用图搜索算法（Dijkstra, A*, JPS）在PRM图上寻找从起点到终点的路径

1.2 RRT(Rapidly-exploring Random Tree)

2. 找最优解的算法

2.1 RRT(Rapidly-exploring Random Tree)

工程实现

  1. Bias Sampling: 有一定概率采样到目标点
  2. Sample Rejection: 如果 g + h > c*，则拒绝该采样点
  3. Branch-and-bound: 剪枝，也需要 Trade-off，影响最优性
  4. Graph Sparsify: 稀疏化，影响最优性
  5. Neighbor Query: K近邻或半径查询
  6. Delay Collision Check: 延迟碰撞检测
  7. Bi-directional Search: 双向搜索
  8. Conditional Rewire: 找到第一个解后，进行Rewire

3. 加速收敛速度的算法

3.1 RRT

从利用角度：有些节点没有必要被利用，有些节点可以被利用得更充分

3.2 Informed RRT*

从探索角度：只有在Informed set内采样才有用