【AGV定位中电子地图建立及路径规划分析案例3900字】

AGV定位中电子地图建立及路径规划分析案例目录TOC\o"1-3"\h\u22556AGV定位中电子地图建立及路径规划分析案例 1226661.1电子地图建立 1152021.1.1常见电子地图建立方法分析 1282621.1.2基于栅格法的电子地图建立 3273641.2路径规划算法 4318001.2.1基于搜索的路径规划算法 475521.2.2基于采样的路径规划算法 5155651.3全局视觉下的AGV导航方式 6对AGV进行定位后，AGV如何通过一条成本最低的路径安全到达目的地，需要路径规划算法来完成。本文采用全局视觉进行导航，移动机器人在全局视觉下进行路径规划相对于局部视觉的优势在于完全已知环境地图，障碍物位置确定。本文采取全局视觉规划的方案为AGV在已知的电子地图上快速规划路径，通过AGV上避障模块防止碰撞。当AGV中心点像素坐标与目的地像素坐标重合时，即认为AGV到达目的地，因此最终规划好的路径坐标应对应在像素坐标系中。1.1电子地图建立1.1.1常见电子地图建立方法分析建立电子地图是用抽象的数字化地图准确表达真实作业场景[71]。常用的电子地图建立方法有栅格法、可视图法、拓扑地图法和自由空间法[72]。栅格法栅格法建立电子地图需要通过等面积的网格单元表示将实际环境空间，每个栅格分为自由空间和障碍物空间两种状态，代表AGV可通行和不可通行的区域[73]，机器人仅能在空闲栅格自由通行，如图1.1。栅格法具有不受到障碍物的形状约束，容易理解，同时在计算机中容易存储等优点。栅格法对车间环境地图描述的准确性与精度与栅格尺寸有关，栅格尺寸越小对环境的描述越准确，但规划路径时运算量会过大；当栅格为大尺寸时，运算速度会增加，但精度会降低；栅格尺寸合适时计算量不大，能够做到实时更新路径。在综合比较各种方法优缺点之后，本论文最终采用的A*算法进行机器人全局路径规划的便是基于栅格方法的。图1.1栅格法地图可视图法可视图法将障碍物抽象为不规则多边形，将多边形顶点、起点、终点组合连接，并且相连直线不能跨越障碍物，如图1.2所示。这种地图建立方式简单易懂，但当环境复杂时，产生连线较多，而且AGV沿障碍物边缘行走，容易发生碰撞[74]。图1.2可视法地图拓扑地图法拓扑地图以节点的形式表示实际地图中重要环境信息的位置和状态信息，节点之间通过线段连接，表示AGV可行走的路径。该方法具有占用内存少、路径搜索效率高的优点，如图1.3所示为拓扑法建立的环境模型。将地图中的每个节点设为拓扑图中的节点V,节点与节点之间的路径看成图中的边线E。由此可用图论的形式把整个地图表示出来，如式5-(1)所示。5-(1)式中,V为图G中顶点的集合，记为E为图G中的集合，记为e为点的无序对且。图1.3拓扑地图自由空间法自由空间法是将环境中障碍物按AGV的安全距离膨胀后抽象成不规则多边形，分别连接顶点到边界的垂线和顶点之间的连线，这些连线不跨过障碍物称为MAKLINK线，再将MAKLINK线的中点不跨越障碍物连接形成电子地图[75]，如图1.4所示。该方法具有起点终点位置更改方便的优点，但当障碍物较多时，构建的地图模型较为复杂。图1.4自由空间法1.1.2基于栅格法的电子地图建立全局视觉直接接收到的环境信息为图片，由一个个像素组成，可以大体看作栅格地图中的栅格，路径在摄像头捕捉到图像上易表达，但栅格选取合理时，实时性好，因此，本文使用栅格法建立电子地图。车间模拟场景如图2.3所示，将其制作为二值化图片如图1.5所示，此时如果将此图片作为电子地图，栅格大小与像素大小一致，包含信息较全，地图尺度为1920×1080，但计算量太大，无法实验对路径的实时规划。测量AGV在图片上的尺寸为300×380像素，因此当路径在图像上宽度在300像素时以上时，小车均能通过，取300×300作为栅格大小，生成的栅格地图如图1.6所示。图1.5实验场景二值化结果图1.6实验场景电子地图1.2路径规划算法物体从起点运动到终点的线路称之为路径，而解决如何通过决策生成从起点到终点的最优路线问题即为路径规划。按照研究方向不同，路径规划可分为三类：已知环境下的静态路径规划、已知环境下的动态路径规划、未知环境下的动态路径规划。本文通过全局视觉可实时获取环境信息，且工厂环境一般保持不变，因此属于已知环境下静态路径规划。本文根据路径规划依据原理将常用路径规划算法分为基于搜索和基于采样算法两类进行实验比较，分析常用算法优缺点。基于搜索的路径规划方式主要包含广度优先的搜索方式(BFS)、深度优先的搜索方式(DFS)、Dijkstra算法、A*算法以及改进A*算法。基于采样的路径规划算法主要包含PRM(ProbabilisticRoadMap)、RRT(Rapidly-exploringRandomTree)以及改进算法。1.2.1基于搜索的路径规划算法基于搜索的路径规划算法中广度优先算法可以在地图中找到一条最优路径，但搜索到区域较大，需要访问大量节点；深度优先算法可以在未知的地图下找到一条路径，但会因陷入局部极值导致路径并非最优。Dijkstra和A*算法结合了上述两种方法，其中Dijkstra算法采用贪心策略，使用广度优先遍历和加入权重的方式找到一条最短路径树；A*算法在Dijkstra算法基础上考虑从路标点到目标点之间的代价，寻找一条最短路径[76]。此外为进一步提高A*、Dijkstra算法的速度或最优性等，国内外很多学者提出了基于这两种算法的改进算法。图1.7为本文实验的几种基于搜索的路径规划算法寻路结果，其中蓝色为起始点，绿色为终止点，红色为路径，灰色为搜索区域，白色为未搜索区域。图1.7基于搜索的路径规划算法结果1.2.2基于采样的路径规划算法在1994年提出的PRM通过在位姿空间中采样将连续空间转换为离散空间，然后利用A*等算法在生成的路线图上查询路径。RRT算法通过在位姿空间中的起始点和终止点为根，通过随机踩点向外拓展形成一个树状结构[77]。

PRM*和RRT*分别是PRM和RRT的渐进最优形式。PRM*与PRM的主要区别是选择最近邻的方法不同。在建立路线图时，每个采样点都要尝试和它邻域内的k个最近采样点建立连接，PRM的邻域半径r是固定的，而PRM*的领域半径r是采样点数量n的函数，n越大，r越小。对原始RRT算法稍加修改，可以得到RRG(Rapidly-exploringRandomGraph)。每当新生成一个采样点，RRT和RRG都要将这个点和树上距它最近的点相连，于是这个点就被加到了树中；不同之处在于，RRG还需要尝试连接新采样点和它邻域中的所有采样点，所以，RRG中可能包含环路，RRG是一个图。RRT*是RRG的一个变体。与RRG不同，RRT*并不会将新采样点和树上距它最近的点相连，而是在尝试连接新采样点和它邻域中的所有采样点时，保留cost最小的那个连接[78]。这里的cost是指机器人从树的根节点运动到新采样点的代价，可以是距离代价，也可以是其他代价，图1.8未RRT和RRT*对同一初始点和终止点路径规划结果，图中蓝色为起始点，绿色为终止点，红色为路径，绿色为搜索区域，白色为未搜索区域。图1.8基于采样的路径规划算法结果基于采样的规划算法速度快，但是由于是随机采样，每次生成的路径结果都不一致，生成路径不一定是最优解。对于基于采样和基于搜索的路径规划算法对比如表1.1所示，其中完备性指算法可以在有限时间内能解决所有有解问题；最优性指该算法能够找到最优路径[74]。表1.1基于搜索和基于采样的路径规划算法对比算法类型具体算法完备性最优性基于搜索Dijkstra、A*完备是基于采样PRM、RRT概率完备否RRT*、InformedRRT*概率完备渐进最优1.3全局视觉下的AGV导航方式目前A*算法应用最为广泛，本文基于建立的栅格地图为全局环境已知静态规划的情况，因此本文利用A*算法寻找AGV合适路径。A*是在Dijkstra算法的基础上进行扩展，增加了启发式搜寻算法，不必遍历地图所有节点，具有高效性，但不一定是最优解。通过公式5-(2)计算节点优先级，从队列中选取优先级最高节点，确定AGV移动方向。 5-(2)式中，为节点n的综合代价值；为节点n与起点之间实际代价值；为节点n到终点的预计代价值；对于启发函数一般通过曼哈顿距离或欧氏距离计算，其中曼哈顿距离估计的函数值如5-(3)所示。5-(3)式中，ω为相邻两节点移动的代价，x为节点横坐标，dest.x为终点横坐标，y为节点纵坐标，dest.y终点纵坐标，算法流程图如1.9所示。图1.9A*算法流程图AGV在每个栅格中可以朝8个方向移动，绿色栅格为起始位置，黄色栅格为终止位置，当起始位置与终止位置如图1.10所示，通过A*算法可以直接由起始地到达目的地，但考虑AGV宽度，可能与右侧障碍物栅格相撞，因此当出现如下情况时，将A*算法改为4邻域搜索，效果如图1.12所示。图1.10可能发生碰撞情况图1.11可能发生碰撞的路径图1.12修改后路径在栅格地图上进行路径规划后，得到经过的栅格，AGV在全局视觉下导航需要根据原始地图上路径像素点的位置对AGV进行导航定位，因此需要将节点位置转换为原始图像像素点坐标。原始图像像素点数为1920×1080，栅格数为7×4，为便于程序编写，栅格数与像素坐标都从0开始计算，节点栅格坐标对应像素坐标关系如式：5-(4)式τx、τy分别为像素行数与栅格行数比值、像素列数与栅格列数比值，[]为取整。本文中、,如图1.12中规划的路径节点坐标为，对应像素坐标为，将原始地图上节点像素坐标连接起来如图1.13所示。图1.13原地图上规划好的路径AGV起始点与终止点中心坐标可能不在栅格中心位置，例如起始点所在栅格中心位置为,终止点所在栅格中心位置为，起始点像素坐标，终止点像素坐标。在上次任务终止时，会记录AGV停车像素坐标及方向向量，目前需要从点行驶到点，得到方向向量，方向向量通过现在帧与上一帧AGV像素坐标确定，根据第三章转弯算法调整AGV方向，使和同向，然后使AGV前进到。当前进过程中AGV中心点坐标偏离、间的线段时，以方向向量为正向，偏左则左轮加速，偏右则右轮加速。到达节点后停止，记录像素坐标及方向向量，将下一个节点作为目标节点，重复上述过程直至。将起始点像素坐标、路径规划节点坐标、目的地像素坐标存入到list中，每次停止时的方向向量存入stopList中，算法流程如下：从list中取出起始点像素坐