一、基于采样（sampling）/搜索（search）的路径规划

1.1 基于采样的规划：

  • 工作原理：基于采样的规划方法通过在配置空间中随机或有规律地采样一些候选点，然后从这些点中选择合适的点来构建路径。典型的算法包括Rapidly Exploring Random Trees (RRT) 和Probabilistic Roadmaps (PRM)。

  • 优点：这些方法适用于高维配置空间，因为它们不需要在整个空间中搜索。它们通常能够以较少的计算成本找到可行路径。此外，它们可以处理复杂的环境，包括动态障碍物。

  • 缺点：基于采样的规划方法不能保证找到最优路径，因为它们通常是概率性的。此外，它们的性能可能受到采样密度和随机性的影响。

1.2 基于搜索的规划：

  • 工作原理：基于搜索的规划方法通过在配置空间中使用搜索算法来逐步探索可能的路径。典型的算法包括A*、Dijkstra、和深度优先搜索等。

  • 优点：这些方法能够找到最优路径，因为它们在搜索过程中考虑了路径的代价和距离。它们适用于小型配置空间，其中精确搜索是可行的。

  • 缺点：基于搜索的规划方法在高维配置空间中的性能通常较差，因为它们需要遍历整个配置空间或者维护大量的搜索状态。这可能导致计算成本非常高，特别是在复杂环境中。

二、RRT 快速探索随机树（Rapidly Exploring Random Trees）

快速探索随机树（Rapidly Exploring Random Trees，RRT）是一种在机器人学和计算机科学中广泛使用的路径规划算法，用于在高维配置空间中找到可行路径。RRT算法是由Steven M. LaValle于1998年提出的。RRT算法的基本思想是逐步构建一个随机样本的树，该树位于机器人或其他系统的配置空间中，其目标是连接起始和目标配置。

以下是RRT算法的工作方式的高级概述：

  • 初始化：

    • 从只包含初始配置的树开始，将其作为根节点。
  • 扩展：
    • 随机采样配置空间中的一个配置。
    • 找到现有树中与采样配置最近的节点。通常通过计算欧氏距离或其他距离度量来实现这一点。
    • 通过在采样配置或从最近节点到采样配置的路径上创建一个新节点来扩展树。这个新节点成为最近节点的子节点。
    • 确保从最近节点到新节点的路径是无碰撞的，即它不与环境中的障碍物相交。

  • 目标检查：

    • 检查新添加的节点是否足够接近目标配置。如果是，并且到目标的路径是无碰撞的，则算法成功终止。

  • 迭代：

    • 重复扩展步骤（步骤2），直到满足终止条件。这个条件可以是时间限制、最大迭代次数或其他标准。

  • 路径构建：

    • 一旦达到目标配置，就从目标节点向根节点追溯，以构建从初始配置到目标配置的路径。

RRT的关键特点和优点：

  • RRT是概率完备的，意味着当迭代次数趋于无穷时，如果存在可行路径，它将找到该路径。
  • 它非常适用于高维配置空间。
  • RRT通过朝着未探索区域的方向扩展来高效地探索空间。
  • 它可以通过包括碰撞检查来处理复杂和动态环境。

RRT有许多变种和扩展，包括RRT*（最优变种）、RRT-Connect（用于连接两棵树）等，它们以不同的方式改进了基本的RRT算法。

三、仿真

参考《motion planning for mobile robots》

3.1 伪代码

Input: Map, x_init, x_goal
Result: path_optimal from x_init to x_goal
path_optimal.init();
for i = 1 to iter do
    x_rand = Sample(Map);
    x_near = Find_Near(x_rand,path_optimal);
    x_new = Find_New(x_rand,x_near,StepSize);
    Edge_i = Make_Edge(x_new,x_near);
    if CheckCollision(Map,Edge_i) then
        path_optimal.addNode(x_new);
        path_optimal.addEdge(Edge_i);
    if x_new = x_goal then
        Success();

3.2 Matlab仿真

参考《motion planning for mobile robots》，如果想要源码的话，可以评论或私聊~