路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2

简介: 路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-2

路径规划最全综述+代码+可视化绘图(Dijkstra算法+A*算法+RRT算法等)-1

https://developer.aliyun.com/article/1446465


基于采样的规划则是利用随机采样的方法来生成路径

其中最常见的算法是

  • RRT、
  • RRT-Connect、
  • Extended-RRT、
  • Dynamic-RRT、
  • RRT*、
  • Informed RRT*、
  • RRT* Smart、
  • Anytime RRT*、
  • Closed-Loop RRT*、
  • Spline-RRT*、
  • Fast Marching Trees (FMT*) 和
  • Batch Informed Trees (BIT*)


等算法。这些算法适用于复杂环境中的路径规划,如机器人导航、无人驾驶和物流配送等领域。

优缺点
  1. RRT (Rapidly-Exploring Random Trees)
    优点:适用于高维空间;能够有效处理复杂环境;运算速度较快。


缺点:无法保证找到最优解;生成的路径可能不是最短路径。

  1. RRT-Connect
    优点:可以保证找到可行路径;适用于多机器人路径规划问题。

缺点:路径质量可能较差;可能收敛速度较慢。

  1. Extended-RRT
    优点:能够处理非完整动力学系统;适用于多机器人协同规划。


缺点:路径质量可能较差;运算速度较慢。

  1. Dynamic-RRT
    优点:能够处理动态环境中的路径规划问题;适用于移动机器人和无人机等领域。


缺点:运算速度较慢;路径质量可能较差。


5.RRT* (Rapidly-Exploring Random Trees Star)

优点:能够找到最优路径;路径质量较高。

缺点:运算速度较慢;可能需要大量的存储空间。


6.Informed RRT*

优点:结合了启发式信息,能够加速搜索过程;能够找到近似最优解。


缺点:运算速度较慢;路径质量可能较差。

  1. RRT* Smart
    优点:通过智能采样策略提高搜索效率;能够找到最优路径。

缺点:运算速度较慢;路径质量可能较差。

  1. Anytime RRT*
    优点:可以在任何时候停止搜索并返回当前的最佳路径;能够找到近似最优解。

缺点:路径质量可能较差;需要进行实时计算。


9.Closed-Loop RRT*

优点:能够处理非完整动力学系统和约束条件;路径质量较高。

缺点:运算速度较慢;可能需要大量的存储空间。

# --------Visualization specialized for dynamic RRT
    def visualization(self):
        if self.ind % 100 == 0 or self.done:
            V = np.array(self.V)
            Path = np.array(self.Path)
            start = self.env.start
            goal = self.env.goal
            # edges = []
            # for i in self.Parent:
            #     edges.append([i, self.Parent[i]])
            edges = np.array([list(i) for i in self.Edge])
            ax = plt.subplot(111, projection='3d')
            # ax.view_init(elev=0.+ 0.03*initparams.ind/(2*np.pi), azim=90 + 0.03*initparams.ind/(2*np.pi))
            # ax.view_init(elev=0., azim=90.)
            ax.view_init(elev=90., azim=0.)
            ax.clear()
            # drawing objects
            draw_Spheres(ax, self.env.balls)
            draw_block_list(ax, self.env.blocks)
            if self.env.OBB is not None:
                draw_obb(ax, self.env.OBB)
            draw_block_list(ax, np.array([self.env.boundary]), alpha=0)
            draw_line(ax, edges, visibility=0.75, color='g')
            draw_line(ax, Path, color='r')
            # if len(V) > 0:
            #     ax.scatter3D(V[:, 0], V[:, 1], V[:, 2], s=2, color='g', )
            ax.plot(start[0:1], start[1:2], start[2:], 'go', markersize=7, markeredgecolor='k')
            ax.plot(goal[0:1], goal[1:2], goal[2:], 'ro', markersize=7, markeredgecolor='k')
            # adjust the aspect ratio
            set_axes_equal(ax)
            make_transparent(ax)
            # plt.xlabel('s')
            # plt.ylabel('y')
            ax.set_axis_off()
            plt.pause(0.0001)


if __name__ == '__main__':
    rrt = dynamic_rrt_3D()
    rrt.Main()


  1. Spline-RRT*
    优点:通过样条插值提高路径质量;能够找到平滑的路径。

缺点:运算速度较慢;可能需要大量的存储空间。

  1. Fast Marching Trees (FMT*)
    优点:运算速度快;能够找到最短路径。


缺点:路径质量可能较差;在高维空间中效果可能不理想。

  1. Batch Informed Trees (BIT*)
    优点:通过批量采样提高搜索效率;能够找到最优路径。

缺点:运算速度较慢;可能需要大量的存储空间。

2. 常见的路径规划算法

2.1 Dijkstra算法

Dijkstra算法是一种用于图中寻找最短路径的算法,它可以应用于有向图或无向图。该算法通过不断更新起点到各个顶点的最短路径来找到最终的最短路径。Dijkstra算法的时间复杂度为O(V^2),其中V为顶点数,但可以通过优先队列实现最小堆来优化时间复杂度。

2.2 A*算法

A算法是一种启发式搜索算法,它结合了Dijkstra算法和贪婪最佳优先搜索算法的优点。A算法通过估计从当前节点到目标节点的代价来动态调整搜索方向,从而更快地找到最佳路径。A*算法在很多实际应用中表现出色,并且具有较高的效率和准确性。

2.3 RRT算法

RRT(Rapidly-exploring Random Tree)算法是一种适用于高维空间的路径规划算法,它通过随机采样和不断扩展树形结构来搜索路径。RRT算法适用于具有复杂空间结构的环境,并且在机器人导航和运动规划中有着广泛的应用。


3. 路径规划在无人驾驶中的应用

无人驾驶技术作为当今人工智能领域的热点之一,路径规划在其中扮演着至关重要的角色。无人驾驶车辆需要通过传感器获取周围环境信息,并利用路径规划算法来决定车辆的行驶路线,以确保安全和高效地到达目的地。由于道路交通环境的复杂性,路径规划算法需要考虑到实时交通状况、障碍物避让、交通规则等因素,因此对路径规划算法的要求也更加严格。


4. 路径规划在物流配送中的应用

随着电商行业的快速发展,物流配送成为了一个备受关注的领域。路径规划在物流配送中的应用不仅可以提高配送效率,还可以降低成本。通过合理的路径规划,配送车辆可以在最短的时间内覆盖更多的配送点,从而提高送货效率。同时,路径规划算法还需要考虑到配送点的时效性、交通拥堵情况等因素,以提供最优的配送方案。


0f11dd35d696452b8429164bb4304859.gif


5. 路径规划的挑战与未来发展

随着人工智能和计算机技术的不断发展,路径规划领域也面临着一些挑战。例如,在复杂的城市环境中,路径规划需要考虑到人行道、交通信号灯、行人车辆等多种因素,这对算法的精度和实时性提出了更高的要求。未来,路径规划技术可能会结合更多的传感器数据和深度学习技术,以提高路径规划的效率和准确性。


结语

路径规划作为人工智能领域中的重要应用之一,对于实现智能化的交通系统和物流配送具有重要意义。随着技术的不断进步,路径规划算法将会在更多的领域发挥作用,为人们的生活带来便利和安全。

相关文章
|
17天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
50 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
1天前
|
算法 测试技术 开发者
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗
在Python开发中,性能优化和代码审查至关重要。性能优化通过改进代码结构和算法提高程序运行速度,减少资源消耗;代码审查通过检查源代码发现潜在问题,提高代码质量和团队协作效率。本文介绍了一些实用的技巧和工具,帮助开发者提升开发效率。
7 3
|
13天前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?
|
14天前
|
搜索推荐
插入排序算法的讲解和代码
【10月更文挑战第12天】插入排序是一种基础的排序算法,理解和掌握它对于学习其他排序算法以及数据结构都具有重要意义。你可以通过实际操作和分析,进一步深入了解插入排序的特点和应用场景,以便在实际编程中更好地运用它。
|
24天前
|
算法 数据可视化 新制造
Threejs路径规划_基于A*算法案例完整版
这篇文章详细介绍了如何在Three.js中完整实现基于A*算法的路径规划案例,包括网格构建、路径寻找算法的实现以及路径可视化展示等方面的内容。
49 0
Threejs路径规划_基于A*算法案例完整版
|
6天前
|
缓存 分布式计算 监控
优化算法和代码需要注意什么
【10月更文挑战第20天】优化算法和代码需要注意什么
13 0
|
24天前
|
存储 算法 机器人
Threejs路径规划_基于A*算法案例V2
这篇文章详细介绍了如何在Three.js中使用A*算法进行高效的路径规划,并通过三维物理电路的实例演示了路径计算和优化的过程。
45 0
|
27天前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
8天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
5天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。