企业官网建设流程全解析

360安全网站怎么做号码认证,深圳市企业网站seo,网站制作域名是免费的吗,网站内链符号提升在复杂环境中使用RRT算法族解决路径规划问题的实践能力。9.1 RRT算法介绍快速扩展随机树(Rapidly-exploring Random Trees#xff0c;RRT)是一种用于路径规划的算法#xff0c;特别适用于机器人、自动驾驶车辆和其他自主系统的运动规划问题。该算法通过在自由空间中随机…提升在复杂环境中使用RRT算法族解决路径规划问题的实践能力。9.1 RRT算法介绍快速扩展随机树(Rapidly-exploring Random TreesRRT)是一种用于路径规划的算法特别适用于机器人、自动驾驶车辆和其他自主系统的运动规划问题。该算法通过在自由空间中随机采样并迭代地构建一棵树来寻找从起点到目标点的可行路径。RRT是近十几年得到广泛发展与应用的基于采样的运动规划算法它由美国爱荷华州立大学的 Steven M. LaValle 教授在1998 年提出。RRT 算法是一种在多维空间中有效率的规划方法。原始的 RRT 算法是通过一个初始点作为根节点通过随机采样增加叶子节点的方式生成一个随机扩展树当随机树中的叶子节点包含了目标点或进入了目标区域便可以在随机树中找到一条由树节点组成的从初始点到目标点的路径。RRT 算法的主要优点之一是它的随机性和快速性。通过随机采样并迭代地扩展树RRT 能够有效地探索大型自由空间并在有限时间内找到可行路径。此外RRT 算法对于高维空间中的运动规划问题也很有效因为它不需要显式地构建整个空间的表示而是在需要时根据采样点来动态扩展搜索树。注意RRT算法也有一些局限性例如在某些情况下可能会找到次优路径以及对于高度动态的环境或需要考虑更多因素的问题可能不够灵活。因此有时候需要结合其他算法或改进来解决特定的路径规划问题。9.2 RRT算法的定义与实现RRT算法通过随机采样和树结构迭代地探索搜索空间直到找到连接起点和目标点的路径。算法不断生成新节点并将其连接到最近邻节点直到达到最大迭代次数或找到路径。最终从树中提取路径作为解。9.2.1 RRT算法的实现步骤实现RRT算法的基本步骤如下所示。1初始化将起点添加到搜索树中作为唯一节点。2循环在搜索树中不断迭代直到找到目标点或达到最大迭代次数。采样在自由空间中随机采样一个点作为新的探索点。最近邻搜索在搜索树中找到与新采样点最近的节点。扩展从最近邻节点向采样点之间的直线路径上进行一步扩展并检查是否碰撞了障碍物。连接如果扩展路径是无碰撞的则将新的节点添加到搜索树中并将连接它的边添加到树中。目标检测检查新添加的节点是否足够接近目标点如果是则算法终止。3路径提取当算法终止时从搜索树中提取从起点到目标点的路径。9.2.2 原始的RRT算法在介绍 RRT 算法之前先说明一下路径的表示方法。我们用一个有向图来表示路径G(V,E)那么一条可行的路径就是一个顶点的序列(v1​,v2​,v3​,…,vn​)v1qinitvnqgoal。同时为了使该序列构成一条有效路径要求每一对相邻顶点( , 1) 都是图中的一条有向边即满足(vi,vi1)∈E其中1≤i≤n-1表示边。这样路径规划问题就转化为如何利用采样得到的节点不断扩展图 G以找到一条从初始节点通往目标节点的路径。“原始的 RRT 算法”指的是最初提出的、最基本版本的 RRTRapidly-exploring Random Tree算法。这个版本是由 Steven M. LaValle 在他的论文 Rapidly-exploring Random Trees: A New Tool for Path Planning 中提出的。原始的 RRT 算法是用于路径规划的一种基本方法其核心思想是通过随机采样和树结构迭代地探索搜索空间直到找到连接起点和目标点的路径。在算法的每次迭代中随机生成一个点并通过扩展树来探索新的空间区域以此逐步构建一棵树。通过这种方式RRT 算法能够在自由空间中快速生成路径并且在有限时间内收敛到一条可行路径。例如下面的例子实现了基本的RRT算法在这个例子中主要的RRT算法实现在 main 函数的for 循环中。在每次迭代中都会随机采样一个点 q_rand然后找到树中最接近该点的节点 q_nearest并使用 extend 函数将该随机点扩展到树中。最后将扩展后的节点加入树中。实例9-1使用原始的RRT算法寻找路径codes/9/yuan.py实例文件yuan.py的具体实现代码如下所示。import math import random import matplotlib.pyplot as plt # 定义节点类 class Node: def __init__(self, x, y): self.x x self.y y # 计算两个节点之间的距离 def distance(n1, n2): return math.sqrt((n1.x - n2.x)**2 (n1.y - n2.y)**2) # 扩展函数 def extend(nearest, rand, max_distance): d distance(nearest, rand) if d max_distance: return rand else: theta math.atan2(rand.y - nearest.y, rand.x - nearest.x) x nearest.x max_distance * math.cos(theta) y nearest.y max_distance * math.sin(theta) return Node(x, y) # 主函数 def main(): q_init Node(0, 0) # 起始点 q_goal Node(10, 10) # 目标点 V [q_init] # 存储节点的集合 iterations 100 # 迭代次数 max_distance 1.0 # 最大扩展距离 for i in range(iterations): # 采样随机点 q_rand Node(random.uniform(0, 100), random.uniform(0, 100)) # 找到距离随机点最近的节点 q_nearest V[0] for node in V: if distance(node, q_rand) distance(q_nearest, q_rand): q_nearest node # 扩展树 q_new extend(q_nearest, q_rand, max_distance) V.append(q_new) # 输出节点集合 print(Nodes:) for node in V: print((, node.x, ,, node.y, ), end ) print() # 绘制节点和路径 plt.figure(figsize(8, 8)) plt.plot([node.x for node in V], [node.y for node in V], bo, markersize3) # 绘制节点 plt.plot([q_init.x, q_goal.x], [q_init.y, q_goal.y], r-) # 绘制起点和终点之间的路径 plt.plot(q_init.x, q_init.y, go, labelStart) # 绘制起点 plt.plot(q_goal.x, q_goal.y, ro, labelGoal) # 绘制终点 plt.xlabel(X) plt.ylabel(Y) plt.title(RRT Algorithm Visualization) plt.legend() plt.grid(True) plt.show() if __name__ __main__: main()上述代码实现了基本的RRTRapidly-exploring Random Tree算法具体实现流程如下所示。1首先定义类Node用于表示二维空间中的节点每个节点有 x 和 y 坐标。2然后定义了一个计算两个节点之间距离的函数 distance以及一个扩展节点的函数 extend。distance 函数使用欧几里得距离公式计算两个节点之间的距离extend 函数用于在当前最近节点和随机生成的节点之间进行扩展保证扩展距离不超过最大距离。3接着在主函数main中定义了起始节点 q_init 和目标节点 q_goal并创建了一个存储节点的集合 V将起始节点加入集合。4在迭代过程中程序将执行如下所示的操作采样随机点生成一个随机的二维坐标点作为新的随机点 q_rand。找到距离随机点最近的节点遍历节点集合 V找到与随机点 q_rand 最近的节点 q_nearest。扩展树使用 extend 函数将最近节点 q_nearest 和随机点 q_rand 之间的距离进行扩展生成一个新的节点 q_new并将其加入节点集合 V 中。以上过程会持续进行指定的迭代次数。5最后将生成的节点和起点到终点之间的路径进行可视化展示如图9-1所示。使用 matplotlib 库绘制了生成的节点和路径节点用蓝色圆圈表示起点用绿色圆圈表示终点用红色圆圈表示路径用红色线段表示。展示了算法在迭代过程中生成的节点分布情况以及起点到终点的路径。图9-1 节点和路径的可视化9.2.3 基于概率P的RRT算法基于概率 P 的 RRTProbabilistic Roadmap Planning是一种路径规划算法是 RRT 算法的一种变体。与传统的 RRT 算法不同基于概率 P 的 RRT 引入了概率因素来指导树的生长以提高路径搜索的效率。在传统的 RRT 算法中随机采样点的选择是均匀随机的而在基于概率 P 的 RRT 中采样点的选择是依据一定的概率分布进行的。这个概率分布通常会考虑到环境的特性比如障碍物的分布情况、起点和终点的位置等。通过合理选择概率分布可以使得采样点更有可能出现在搜索空间中有意义的区域从而加速路径搜索的过程。基于概率 P 的 RRT 算法仍然遵循 RRT 的基本思想即通过不断生长树来探索搜索空间并最终找到起点到目标点的可行路径。但是通过引入概率因素该算法能够更加智能地选择扩展方向从而更快地收敛到解。这种方法通常可以提高算法的效率并且在某些情况下能够更好地应对复杂的环境和任务需求。例如下面是一个基于概率P的RRT算法的完整例子包括了节点结构的定义、距离计算函数、扩展函数以及主函数实现。实例9-2使用基于概率P的RRT算法codes/9/prrt.py实例文件prrt.py的具体实现代码如下所示。import random import math import matplotlib.pyplot as plt # 定义节点结构 class Node: def __init__(self, x, y): self.x x self.y y # 计算两个节点之间的距离 def distance(n1, n2): return math.sqrt((n1.x - n2.x) ** 2 (n1.y - n2.y) ** 2) # 根据概率P选择目标点 def chose_target(qrand, qgoal, P): if random.random() P: return qgoal else: return qrand # 找到距离目标点最近的节点 def nearest(V, q): nearest_node V[0] min_dist distance(nearest_node, q) for node in V: dist distance(node, q) if dist min_dist: nearest_node node min_dist dist return nearest_node # 在节点qnearest和目标点q之间进行局部扩展得到新节点 def steer(qnearest, q): theta math.atan2(q.y - qnearest.y, q.x - qnearest.x) x qnearest.x math.cos(theta) y qnearest.y math.sin(theta) return Node(x, y) # 判断从节点qnearest到节点qnew的路径是否避开障碍物 def obstacle_free(qnearest, qnew): # 在这里假设路径是始终可行的 return True # Extend函数实现基于概率P的RRT算法的扩展操作 def extend(V, qrand, qgoal, P): q chose_target(qrand, qgoal, P) qnearest nearest(V, q) qnew steer(qnearest, q) if obstacle_free(qnearest, qnew): V.append(qnew) return V # 可视化函数绘制节点集合和边集合 def visualize(V, E, q_init, q_goal): fig, ax plt.subplots() for node in V: ax.plot(node.x, node.y, bo) for edge in E: ax.plot([edge[0].x, edge[1].x], [edge[0].y, edge[1].y], k-) ax.plot(q_init.x, q_init.y, go) # 起始点 ax.plot(q_goal.x, q_goal.y, ro) # 目标点 ax.set_xlabel(X) ax.set_ylabel(Y) ax.set_title(Probabilistic RRT Visualization) plt.show() # 主函数 def main(): random.seed() # 初始化随机种子 q_init Node(0, 0) # 起始点 q_goal Node(10, 10) # 目标点 V [q_init] # 存储节点的集合 E [] # 存储边的集合 iterations 50 # 迭代次数 P 0.9 # 概率P for _ in range(iterations): # 采样随机点 q_rand Node(random.randint(0, 100), random.randint(0, 100)) # 扩展树 q_nearest nearest(V, q_rand) q_new steer(q_nearest, q_rand) if obstacle_free(q_nearest, q_new): V.append(q_new) E.append((q_nearest, q_new)) # 输出节点集合和边集合 print(Nodes:, end ) for node in V: print(f({node.x}, {node.y}), end ) print() # 可视化 visualize(V, E, q_init, q_goal) if __name__ __main__: main()上述代码的实现流程如下所示1首先定义了节点结构 Node包含节点的 x 和 y 坐标并实现了一些基本的几何计算函数如计算两个节点之间的距离、选择目标点、找到距离目标点最近的节点等。2然后在主函数main中初始化了起始点和目标点并创建了节点集合 V 和边集合 E。通过随机选择节点进行迭代每次迭代根据概率 P 选择目标点在当前树中找到距离目标点最近的节点然后在这个最近节点和目标点之间进行局部扩展生成新的节点。如果新节点的路径不与障碍物相交就将新节点添加到节点集合中并将扩展过程中的边添加到边集合中。3接着利用 matplotlib 库实现了可视化功能将节点集合和边集合绘制在二维坐标系中并标记了起始点和目标点。这样可以直观地观察到基于概率 P 的 RRT 算法在搜索空间中的探索过程和生成的路径。1最后打印输出了生成的节点集合并绘制了路径信息的可视化图如图9-2所示。这样可以通过输出结果和可视化图形了解算法的执行情况和生成的路径信息。图9-2 路径信息的可视化图