路径规划最全综述+代码+可视化绘图(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. 路径规划的挑战与未来发展

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


结语

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

相关文章
|
24天前
|
机器学习/深度学习 算法 PyTorch
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
RPN(Region Proposal Networks)候选区域网络算法解析(附PyTorch代码)
180 1
|
1月前
|
算法 安全 C语言
使用C语言实现DES算法代码
使用C语言实现DES算法代码
|
2月前
|
传感器 算法 自动驾驶
混合A*运动规划算法:路径规划和路径跟踪-MPC-LQR-PID算法
混合A*运动规划算法:路径规划和路径跟踪-MPC-LQR-PID算法
67 0
混合A*运动规划算法:路径规划和路径跟踪-MPC-LQR-PID算法
|
15天前
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
1月前
|
机器学习/深度学习 算法 Python
傅里叶变换算法和Python代码实现
傅立叶变换是物理学家、数学家、工程师和计算机科学家常用的最有用的工具之一。本篇文章我们将使用Python来实现一个连续函数的傅立叶变换。
29 8
|
22天前
|
存储 算法 搜索推荐
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
|
25天前
|
存储 机器学习/深度学习 算法
C语言代码实现数据结构与算法
以上代码中,哈希表使用链表解决哈希冲突,每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值,insert函数用于向哈希表中插入一个键值对,若当前位置为空,则直接插入;否则,将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值,若存在则返回其值,否则返回-1。
32 1
|
1月前
|
算法
关于Dijkstra算法
关于Dijkstra算法
|
1月前
|
机器学习/深度学习 算法 生物认证
基于深度学习的人员指纹身份识别算法matlab仿真
基于深度学习的人员指纹身份识别算法matlab仿真
|
25天前
|
传感器 算法 计算机视觉
基于肤色模型和中值滤波的手部检测算法FPGA实现,包括tb测试文件和MATLAB辅助验证
该内容是关于一个基于肤色模型和中值滤波的手部检测算法的描述,包括算法的运行效果图和所使用的软件版本(matlab2022a, vivado2019.2)。算法分为肤色分割和中值滤波两步,其中肤色模型在YCbCr色彩空间定义,中值滤波用于去除噪声。提供了一段核心程序代码,用于处理图像数据并在FPGA上实现。最终,检测结果输出到"hand.txt"文件。