目录

引言

重要代码

传统 A*算法

传统 A*算法缺点分析

越野环境下的 A*算法

子节点优化选择策略

(1)子节点选择方式

(2)优化子节点选择

代码部分

结果对比

越野环境路径规划对比

敏感度衡量对比

结论

全部代码可私信

正文

引言

近年来，随着智能时代的到来，路径规划技术飞快发展，已经形成了一套较为成熟的理论体系。其经典规划算法包括 Dijkstra 算法、A算法、D算法、Field D算法等，然而传统的路径规划算法在复杂的场景的表现并不如人意，例如复杂的越野环境。针对越野环境规划问题以及规划算法的优劣性，选择改进 A算法来进行越野环境路径规划

通过越野栅格环境建模、通行方向变化惩罚、局部区域复杂度惩罚和路径平滑的方法对传统 A*算法进行改进，以满足复杂越野环境下，不同类型的智能车辆和不同任务的安全行驶、高效通行综合要求。

重要代码

###############构造地图################
#宽高W，H。
class Array2D:
    #初始化
    def __init__(self,w,h):
        self.w=w
        self.h=h
        self.data=[]
        self.data=[[0.0 for y in range(h)] for x in range(w)]
    #显示地图
    def showArray2D(self):
        for y in range(self.h):
            for x in range(self.w):
                print(self.data[x][y],end=' ')
            print("")
    #获得任意节点信息 ，__getitem__()魔法函数作用为当实例化对象map进行map[key]操作上自动调用。
    def __getitem__(self, item):
        return self.data[item]
###############创建点类################
class Point:
    #初始化
    def __init__(self,x,y):
        self.x=x
        self.y=y
    #判断是否同一个点
    def __eq__(self, other):
        if self.x==other.x and self.y==other.y:
            return True
        return False
    #打印点信息
    def __str__(self):
        return "x:"+str(self.x)+",y:"+str(self.y)
    ##全部代码请联系---->qq1309399183<---------

传统 A*算法

在启发式搜索算法中， A算法是其中最为典型的代表，它在全局路径规划算法中，具有快速、高效和准确的优点，因此在智能车辆和工业机器人的路径规划问题上得到了广泛的应用。针对规划路径的需求和任务的要求，许多学者对传统 A算法进行改进，例如：路径的长度、规划效率和拐点数等方面。（下图为传统A*算法流程）

传统 A*算法缺点分析

虽然传统的 A算法在一些简单的场景具有一定的有效性，但是实际的用途中，环境复杂性对于算法实时的要求，传统的 A算法并无法满足要求。只有对传统算法的局限性进行深入了解分析才能更好的在传统方法之上进行更进一步的改进，因此本小节深入分析传统 A算法的局限性和不足，具体有：

(1)栅格地图建模的不足：

首先要意识到的是处理的是离散数据，而不是现实世界中的“连续”地形。采样的数字地形图像是真实地形的近似值，应该在一个理想的高分辨率采样。数字地形图像的分辨率越高，对真实地形的描述越逼真，寻径精度也越高。然而，在分辨率上存在一个上限，超过这个上限后，道路就不再更加精确，并且会不必要地增加寻径算法的运行时间。而且传统的建模方式只限定为可行驶区域和障碍物区域，然而

现实世界环境是及其复杂的，例如可行驶区域可区分为不同道路，沙地、草地、土质路面等等；障碍物也区分有树、行人、车辆建筑物等等。

(2)邻域节点选择不足：

为了找到从起始节点到目标节点的路径，我们必须定义一种选择后续节点的方式。我们可以从一个给定的位置移动到哪里？在现实世界中，一个人可以朝着喜欢的任何方向前进，但在数字地形图上，我们的选择更受限制。传统的 A算法中有两种常见的方法：4 个邻接和 8 个邻接。4 个邻接限制移动在北、南、西、东四64 个主要风向。8 邻接的移动更自由，因为它除了 4 邻接的方向外，还可以在东北、西北、西南和东南方向移动。

(3)算法无法自适应满足不同任务要求：

在不同的任务要求中，有的任务要保证路径的最短，则设计预估代价小于真实代价，但是效率低下；有的任务要保证效率的高效，设计预估代价大于真实代价，但是规划的路径不是最优。

(4)对于大地图算法计算效率不足：

对于现实的环境场景，可能寻找道路的搜索空间非常大，这意味着必须采取措施确保内存不会耗尽，或者搜索不会花费过多的时间运行。即使是一个相对较小的300 × 300 像素的地形图也有 9 万个节点的搜索空间。

越野环境下的 A*算法

障碍物模型：

传统的 A*算法的构建方式中最普遍应用的是栅格法，其基本的思路是把智能车辆的工作空间分割为尺寸一致的网格，并通过数据矩阵来记录环境数据。常规的栅格算法把物理环境严格区分为自由区域和障碍物区域，从而使得数值矩阵能够简化为 0-1 矩阵，0 为自由空间，1 为障碍物空间。如假设智能车的工作空间为

R C ，M 为数值矩阵，表示所有的环境信息，则常规的环境模型可以表示为。

很明显，常规的栅格模型是无法模拟出真实复杂的越野环境，因此本文研究越野环境的真实场景，建立多层次栅格模型，将越野环境模型细分为障碍物模型，威胁模型和道路模型，如图 所示。

威胁模型