网站开发代码 免责声明,广州住房与建设网站,wordpress群聊,如何用花生壳做网站引言
近年来#xff0c;随着智能时代的到来#xff0c;路径规划技术飞快发展#xff0c;已经形成了一套较为成熟的理论体系。其经典规划算法包括 Dijkstra 算法、A算法、D算法、Field D算法等#xff0c;然而传统的路径规划算法在复杂的场景的表现并不如人意#xff0c;例…引言
近年来随着智能时代的到来路径规划技术飞快发展已经形成了一套较为成熟的理论体系。其经典规划算法包括 Dijkstra 算法、A算法、D算法、Field D算法等然而传统的路径规划算法在复杂的场景的表现并不如人意例如复杂的越野环境。针对越野环境规划问题以及规划算法的优劣性选择改进 A算法来进行越野环境路径规划 通过越野栅格环境建模、通行方向变化惩罚、局部区域复杂度惩罚和路径平滑的方法对传统 A*算法进行改进以满足复杂越野环境下不同类型的智能车辆和不同任务的安全行驶、高效通行综合要求。
重要代码
###############构造地图################
#宽高WH。
class Array2D:#初始化def __init__(self,w,h):self.wwself.hhself.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.xxself.yy#判断是否同一个点def __eq__(self, other):if self.xother.x and self.yother.y:return Truereturn 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 为数值矩阵表示所有的环境信息则常规的环境模型可以表示为。 很明显常规的栅格模型是无法模拟出真实复杂的越野环境因此本文研究越 野环境的真实场景建立多层次栅格模型将越野环境模型细分为障碍物模型威 胁模型和道路模型如图 所示。 威胁模型
子节点优化选择策略
(1)子节点选择方式
为了找到从起始点到终点的路径需定义一种可以选择后续节点的方式。在A*算法中两种常见的方法为 4-邻接(见图 5-7(a))和 8-邻接 (见图 5-7(b))但考虑到在复杂越野环境上我们希望智能车辆允许更多的自由运动来更好规避危险因此本文选择 16-邻接(见图 5-7©)。如图 5-8 所示4-邻接规划的路径具有很多的直角拐点且路径最长其次是 8-邻接规划的路径而 16-邻接规划的路径平滑、拐点数少、路径短适合复杂越野环境智能车的需求。
(2)优化子节点选择
传统 A*算法在子节点选取上仅考察子节点周围是否为障碍物而未考察子节点与障碍物位置的相关性从而规划出路线存在斜着通过障碍物栅格顶点的问题导致车辆可能与障碍物发生碰撞。因为本文中所构建环境模型具有更危险的威胁物存在所以优化了子节点的选择规则。 如图 5-9为 16 个子节点分布图。本文结合越野环境栅格地图设计的子节点选择规则为 **1**若子节点 4 或子节点 12 具有威胁(在越野环境栅格地图中值1)则子节点 2、子节点 6、子节点 3、子节点 5 或子节点 13、子节点 9、子节点 14、子节点11 不作为预选点。 **2**若子节点 16 或子节点 8 具有威胁则子节点 2、子节点 13、子节点 15、 子节点 1 或子节点 6、子节点 9、子节点 10、子节点 7 不作为预选点。 **3**均无具威胁则不做处理。 优化子节点选择后规划后的路径避开具有威胁栅格的顶点避免智能车辆
代码部分
###############创建A-Star类############
class AStar:# 描述AStar算法中的节点数据class Node: #初始化def __init__(self, point, startPoint,endPoint, g0,w1,p1):self.point point # 自己的坐标self.father None # 父节点self.g g # g值g值在用到的时候会重新算# 计算h值采用曼哈顿距离#self.h (abs(endPoint.x - point.x) abs(endPoint.y - point.y)) * 10 #采用欧几里得距离#self.h math.pow((math.pow((endPoint.x - point.x),2) math.pow((endPoint.y - point.y),2)),0.5)*10#采用对角距离pp(1-p)0.2*math.exp((math.pow((math.pow((endPoint.x - point.x),2) math.pow((endPoint.y - point.y),2)),0.5))/(math.pow((math.pow((endPoint.x - startPoint.x),2) math.pow((endPoint.y - startPoint.y),2)),0.5)))Diagonal_step min((endPoint.x - point.x),(endPoint.y - point.y))straight_step (abs(endPoint.x - point.x) abs(endPoint.y - point.y)) - 2*Diagonal_stepself.h (straight_step math.pow(2,0.5)*Diagonal_step)*10*pp#print(pp)#初始化A-startdef __init__(self, map2d, startPoint, endPoint, passTag1.0):#map2d地图信息startPoint起点, endPoint终点, passTag1.0为不可行驶区域# 开启表self.openList []# 关闭表self.closeList []# 寻路地图self.map2d map2d# 起点终点if isinstance(startPoint, Point) and isinstance(endPoint, Point):self.startPoint startPointself.endPoint endPointelse:self.startPoint Point(*startPoint)self.endPoint Point(*endPoint)# 不可行走标记self.passTag passTagdef getMinNode(self):获得openlist中F值最小的节点:return: NodecurrentNode self.openList[0]for node in self.openList:if node.g node.h currentNode.g currentNode.h:currentNode nodereturn currentNode#返回最小代价的点
结果对比 越野环境路径规划对比 敏感度衡量对比 结论
本节针对越野场景路径规划问题采用栅格法建立障碍物、威胁物和越野道路模型模拟真实的越野环境场景。引入方向变化惩罚和局部区域复杂度惩罚来优化A算法使算法规划出的路径更平滑算法效率更高效。采用改进 Floyd 算法对路径进行双向平滑并且进行了防碰撞处理来确保规划出路径的安全可靠性。仿真结果表明所改进的 A算法与传统算法相比较效率提高了 30%拐点数减少了 4 倍所提算法能够在越野环境多重因素综合影响以及不同车辆性能和任务的要求下快速的规划出安全的路径。
全部代码可私信
