【启发式算法】RRT算法详细介绍（Python）_rrt避障算法 python

        📢本篇文章是博主人工智能（AI）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等地方的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉启发式算法专栏：

       【启发式算法】（8）---《RRT算法详细介绍（Python）》

【启发式算法】RRT算法详细介绍（Python）

目录

 一、RRT算法的核心思想

 二、基本流程

 三、RRT算法伪代码

[Python] RRT算法实现

[Results] 运行结果

[Notice]  注意事项

四、RRT的特点

五、改进版本：RRT*

六、应用场景

        RRT（Rapidly-exploring Random Tree）快速扩展随机树是一种采样式路径规划算法，广泛应用于机器人运动规划、自动驾驶、无人机路径设计等地方。它特别适用于高维空间中的路径规划问题。下面是对RRT算法的详细介绍：

 一、RRT算法的核心思想

        RRT的核心思想是通过在空间中随机采样点并逐步构建一棵树形结构（搜索树），来快速探索空间并找到从起点到终点的可行路径。

        RRT偏向于快速探索未被探索的空间区域，从而快速覆盖整个搜索空间。

二、基本流程

输入：

• 起点 q_start
• 终点 q_goal
• 空间约束（如障碍物、边界等）
• 最大迭代次数 
• 步长 Δq

步骤：

1. 初始化一棵树 T，树的根节点为起点 q_start。
2. 对于每次迭代：
   • 随机采样一个点 q_rand（可以是完全随机，也可以有一定概率采样为 q_goal，称为“目标偏向”）。
   • 在树中找到距离 q_rand 最近的节点 q_nearest。
   • 从 q_nearest 向 q_rand 移动一个固定步长 Δq，得到新的节点 q_new。
   • 如果 q_new 不在障碍物中，则将其加入树中，并将其父节点设为 q_nearest。
   • 如果 q_new 距离 q_goal 很近，可以认为找到了可行路径。
3. 如果找到路径，沿父节点回溯得到路径；否则直到达到最大迭代次数。

 三、RRT算法伪代码

def RRT(q_start, q_goal, N, Δq): T = Tree(q_start) for i in range(N): q_rand = random_sample() q_nearest = nearest_node(T, q_rand) q_new = steer(q_nearest, q_rand, Δq) if is_valid(q_nearest, q_new): T.add_node(q_new, parent=q_nearest) if distance(q_new, q_goal) < threshold: return extract_path(T, q_new) return failure

[Python] RRT算法实现

下面提供了一个简化版的 Python 实现示例，并配合图示说明RRT的执行过程。

 项目代码我已经放入GitCode里面，可以通过下面链接跳转：🔥

【启发式算法】--- RRT算法

若是下面代码复现困难或者有问题，也欢迎评论区留言。

\"\"\"《RRT算法》 时间：2025.06.16 作者：不去幼儿园\"\"\"import numpy as npimport matplotlib.pyplot as pltimport randomclass Node: def __init__(self, x, y): self.x = x self.y = y self.parent = Nonedef distance(n1, n2): return np.hypot(n1.x - n2.x, n1.y - n2.y)def get_random_node(goal_sample_rate, goal): if random.random() < goal_sample_rate: return Node(goal.x, goal.y) return Node(random.uniform(0, 100), random.uniform(0, 100))def steer(from_node, to_node, extend_length=5.0): dist = distance(from_node, to_node) theta = np.arctan2(to_node.y - from_node.y, to_node.x - from_node.x) new_x = from_node.x + extend_length * np.cos(theta) new_y = from_node.y + extend_length * np.sin(theta) new_node = Node(new_x, new_y) new_node.parent = from_node return new_nodedef is_collision(node): # 简化处理：假设无障碍物 return Falsedef rrt(start, goal, max_iter=500, goal_sample_rate=0.05): nodes = [start] for _ in range(max_iter): rnd = get_random_node(goal_sample_rate, goal) nearest = min(nodes, key=lambda n: distance(n, rnd)) new_node = steer(nearest, rnd) if not is_collision(new_node): nodes.append(new_node) if distance(new_node, goal) < 5.0: goal.parent = new_node nodes.append(goal) break return nodesdef draw_path(last_node): path = [] node = last_node while node: path.append((node.x, node.y)) node = node.parent path = path[::-1] plt.plot([x for x, y in path], [y for x, y in path], \'-r\')def draw_tree(nodes): for node in nodes: if node.parent: plt.plot([node.x, node.parent.x], [node.y, node.parent.y], \'-g\')start = Node(10, 10)goal = Node(90, 90)nodes = rrt(start, goal)draw_tree(nodes)draw_path(goal)plt.plot(start.x, start.y, \"bs\", label=\"Start\")plt.plot(goal.x, goal.y, \"gs\", label=\"Goal\")plt.legend()plt.grid(True)plt.axis([0, 100, 0, 100])plt.title(\"RRT Path Planning (No Obstacles)\")plt.show()

  有博主给出了更好更完整的RRT算法，在下面的github库中：RRT算法 

[Results] 运行结果

图示说明：

运行上面代码后会出现如下图所示效果：

• 🌲 绿色的线表示RRT生成的搜索树结构。
• 🔴 红色路径表示最终从起点到终点的规划路径。
• 🔵 起点，🟢 终点。

[Notice]  注意事项

• 每一步都从树中最近节点往随机点延伸。
• 最终形成一条从起点连到终点的路径。
• 可在is_collision()中添加障碍物检测逻辑以模拟真实环境。

​# 环境配置Python  3.11.5torch  2.1.0torchvision 0.16.0gym  0.26.2

        由于博文主要为了介绍相关算法的原理和应用的方法，缺乏对于实际效果的关注

四、RRT的特点

 优点：

• 非常适合高维空间的路径规划。
• 易于实现。
• 对复杂环境有良好的适应能力。

 缺点：

• 路径不最优，常常是“锯齿状”路径。
• 随机性强，规划时间不稳定。
• 在障碍物密集区域效果不佳。

五、改进版本：RRT*

RRT*（RRT Star）（下一篇文章介绍）是RRT的优化版本，加入了“路径优化”的机制：

• 在每次加入新节点时，不仅连接最近点，还会尝试重新连接周围节点，以获得更短路径。
• 理论上可以得到渐近最优解。

六、应用场景

• 机器人路径规划
• 无人机自主导航
• 自动驾驶车辆的避障与路径生成
• 多自由度机械臂的运动规划

 更多启发式算法文章，请前往：【启发式算法】专栏

        博客都是给自己看的笔记，如有误导深表抱歉。文章若有不当和不正确之处，还望理解与指出。由于部分文字、图片等来源于互联网，无法核实真实出处，如涉及相关争议，请联系博主删除。如有错误、疑问和侵权，欢迎评论留言联系作者，或者添加VX：Rainbook_2，联系作者。✨