卡地亚手表官方网站查询,理发美发培训学校,wordpress时间相差8小时,百度搜到网站#x1f4e2;本篇文章是博主人工智能#xff08;AI#xff09;领域学习时#xff0c;用于个人学习、研究或者欣赏使用#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记#xff0c;若有不当和侵权之处#xff0c;指出后将会立即改正#xff0c;还望谅… 本篇文章是博主人工智能AI领域学习时用于个人学习、研究或者欣赏使用并基于博主对相关等领域的一些理解而记录的学习摘录和笔记若有不当和侵权之处指出后将会立即改正还望谅解。文章分类在启发式算法专栏 【启发式算法】8---《RRT算法详细介绍Python》 【启发式算法】RRT算法详细介绍Python
目录 一、RRT算法的核心思想 二、基本流程 三、RRT算法伪代码
[Python] RRT算法实现
[Results] 运行结果
[Notice] 注意事项
四、RRT的特点
五、改进版本RRT*
六、应用场景 RRTRapidly-exploring Random Tree快速扩展随机树是一种采样式路径规划算法广泛应用于机器人运动规划、自动驾驶、无人机路径设计等领域。它特别适用于高维空间中的路径规划问题。下面是对RRT算法的详细介绍 一、RRT算法的核心思想 RRT的核心思想是通过在空间中随机采样点并逐步构建一棵树形结构搜索树来快速探索空间并找到从起点到终点的可行路径。 RRT偏向于快速探索未被探索的空间区域从而快速覆盖整个搜索空间。 二、基本流程
输入
起点 q_start终点 q_goal空间约束如障碍物、边界等最大迭代次数 步长 Δq
步骤
初始化一棵树 T树的根节点为起点 q_start。对于每次迭代 随机采样一个点 q_rand可以是完全随机也可以有一定概率采样为 q_goal称为“目标偏向”。在树中找到距离 q_rand 最近的节点 q_nearest。从 q_nearest 向 q_rand 移动一个固定步长 Δq得到新的节点 q_new。如果 q_new 不在障碍物中则将其加入树中并将其父节点设为 q_nearest。如果 q_new 距离 q_goal 很近可以认为找到了可行路径。 如果找到路径沿父节点回溯得到路径否则直到达到最大迭代次数。 三、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, parentq_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 np
import matplotlib.pyplot as plt
import randomclass Node:def __init__(self, x, y):self.x xself.y yself.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_length5.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_nodereturn new_nodedef is_collision(node):# 简化处理假设无障碍物return Falsedef rrt(start, goal, max_iter500, goal_sample_rate0.05):nodes [start]for _ in range(max_iter):rnd get_random_node(goal_sample_rate, goal)nearest min(nodes, keylambda 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_nodenodes.append(goal)breakreturn nodesdef draw_path(last_node):path []node last_nodewhile node:path.append((node.x, node.y))node node.parentpath 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, labelStart)
plt.plot(goal.x, goal.y, gs, labelGoal)
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.5
torch 2.1.0
torchvision 0.16.0
gym 0.26.2 由于博文主要为了介绍相关算法的原理和应用的方法缺乏对于实际效果的关注 四、RRT的特点 优点
非常适合高维空间的路径规划。易于实现。对复杂环境有良好的适应能力。 缺点
路径不最优常常是“锯齿状”路径。随机性强规划时间不稳定。在障碍物密集区域效果不佳。 五、改进版本RRT*
RRT*RRT Star下一篇文章介绍是RRT的优化版本加入了“路径优化”的机制
在每次加入新节点时不仅连接最近点还会尝试重新连接周围节点以获得更短路径。理论上可以得到渐近最优解。 六、应用场景
机器人路径规划无人机自主导航自动驾驶车辆的避障与路径生成多自由度机械臂的运动规划 更多启发式算法文章请前往【启发式算法】专栏 博客都是给自己看的笔记如有误导深表抱歉。文章若有不当和不正确之处还望理解与指出。由于部分文字、图片等来源于互联网无法核实真实出处如涉及相关争议请联系博主删除。如有错误、疑问和侵权欢迎评论留言联系作者或者添加VXRainbook_2联系作者。✨
