【《AGV车辆（机器人）调度系统的整体设计案例》7100字】

AGV车辆（机器人）调度系统的整体设计案例目录TOC\o"1-3"\h\u13705AGV车辆（机器人）调度系统的整体设计案例 1140301.1AGV车辆（机器人）调度系统工作流程 1185021.2路径规划方法 2283451.2.1采用迪杰斯特拉（dijkstra）算法构造的AGV调度系统 3232311.2.2采用A*算法构造的AGV调度系统 8268181.2两种算法的比较 9143131.3工作空间模型建立方法 9206271.4使用经典A*算法求取最短路径 111.1AGV车辆（机器人）调度系统工作流程在对AGV车辆（机器人）的调度系统进行设计之前，我们需要先对调度系统对于车辆的调度管理流程进行初步的了解和设计。AGV车辆（机器人）在仓储车间环境中的运行过程一般设定为局域化（区域化），可以参考现实生活中公路上的交通运作方式，限制车辆单向通行，以及设置合理的“交通规则”，分别对线路和节点独立管理以实现“交通管制”。在对冲突处理方面，对于追尾、侧方相撞等冲突，可以在算法中加入“速度墙”以限制小车运行速度，在检测到路径中有运行中的AGV时，两台AGV（或多台）之间进行通讯交流，做出速度平衡，以此来避免或消除此类冲突；设定“先到先行”原则，使通过历经相交节点的AGV车辆（机器人）遵循这个原则，形成类似于“交通管制”的红绿灯路口，这种方法是解决类似冲突比较常用的方法。综合以上描述，我们可以开始设立AGV车辆（机器人）调度流程，我们使用MicrosoftVisio对调度流程建立树状流程图进行描述如图3-1所示：图3-1AGV车辆调度流程图1.2路径规划方法路径规划是AGV车辆（机器人）控制系统的基本能力之一，也是AGV车辆（机器人）调度控制所需要进一步改造和升级的核心问题。路径规划是指，在并非空旷，存在有不规则分布的障碍物的仓储环境中，根据某种评估标准，找到一条从起始位置到达预定目标位置的，全程不与环境或随机障碍物发生冲突的最优且最短的路径。根据AGV车辆（机器人）在实际应用过程中目的的不同，路径规划的评估标准也有所不同。常见的几种评估标准有：最短时间，最短距离，最少能耗等。本文中涉及的AGV车辆（机器人）路径规划是基于二维平面的求解问题，其路径规划过程可以概括为以下三个方面，首先为AGV车辆（机器人）建立合理的环境模型，即将AGV执行任务的环境状态转换为地图特征信息；其次利用某种或某些算法加以研究、设计，为AGV车辆（机器人）寻找到从起始位置到达目标位置的合理路径；最后是选择一条能避开环境中障碍物的最优路径。路径规划的原理图如下：图3-2路径规划原理1.2.1采用迪杰斯特拉（dijkstra）算法构造的AGV调度系统迪杰斯特拉（Dijkstra）算法是以标号作为计算依据和基础的一种标签式算法。我们在这里解释一下迪杰斯特拉算法的运算原理：设存在一个有向图包含了n个顶点和e条弧，用数集表示为G=(V,E)，节点集用字母V表示，弧集用字母E表示，我们设用集合C(A,B)表示两点A和B之间弧的长度，如果搜索全图发现A点和B点间没有一条互通的路径，则用无穷大（65535）或者远大于集合C(A,B)的整数（如99999）来表示。我们建立一个用来表示任一节点X与原点V0之间距离（权值之和）的数组DIST(X)，S和V-S分别表示目前搜索到的最小权值的路径节点的集合与暂未搜索到最小权值的最短路径（最小权值之和）节点集合，在算法刚开始计算时，集合S中只有一个源点V0，算法结束时，集合S中应包含整个图中的所有节点。迪杰斯特拉（Dijkstra）算法的的实现流程为：步骤一：算法初始化，将源点V0加入集合S，并对其做标记；步骤二：在V-S集合中搜索所有源点V0连接的顶点，选择距离最短（权值最小）的顶点i做标记，并将其加入集合S中；步骤三：以顶点i作为源点，在V-S中继续搜索与i直接连接且距离最短（权值最小）的点j，若DIST[j]>DIST[i]+C(i,j)，意味着目前来看从源点到j的距离经过i点比直接从V0到j要短，所以将DIST[j]更新为DIST[i]+C(i,j)，并将j点加入集合S；步骤四：重复步骤二、三运算n-1次，可找到源点V0到所有点的最短距离；步骤五：将初始顶点、中间过渡点、最终的目标点依次输出，并将其连成一条路径。最短路径四个字的含义，我们其实可以字面理解，带有边/权值的图中从其中一个顶点到另外一个目标顶点的权值最小的通路。数据结构中对最短路径的定义是：对于内网图而言，最短路径是指两顶点之间经过的边上权值之和最小的路径。并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。由于非内网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径。图3-3求解最短路径举例举例说明使用迪杰斯特拉算法求图2-1中由源点V0到终点V8的最短路径，过程如下：定义几个数组用来存放运算过程中需要记录的数值final[m]=1;标记V0→Vm顶点是否已找到最短路径。1表示已找到，0表示尚未找到或不可到达。Dist[m];表示V0→Vm顶点的最短路径权值和，即最短路径长度。Path[m];表示V0→Vm顶点的前驱节点顶点下标值。开始调用算法前，我们建立一个带权图的邻接矩阵，如下所示：图3-4带权图的邻接矩阵程序开始运行，

int

v,m,

k,

min;int

final[MAXVEX];

//final[m]=1表示求得顶点V0→Vm的最短路径final数组的作用是标记从顶点V0到目标点是否已经求得最短路径。如果从V0到Vｍ已经有搜索出的数值，那么final[m]=1;（2）

for

(v

=

0;

v

<

G.numVertexes;

v++)

//初始化数组

{

final

[v]

=

0;

//将所有顶点初始化

(*D)[v]

=

G.matirx[v0][v];

//将与v点有连线的顶点加上权值

(*P)[v]

=

0;

//初始化路径数组P为0

}以上代码完成了对数据初始化。此时final数组均赋值为0，表示所有点均未求得最短路径。节点V0→V1的边权值为1，V0→V2的边权值为5。D数组为{0,1,5,65515,65535,65535,65535,65535,65535}。P数组全为0，表示目前没有路径。（3）(*D)[v0]

=

0;

//V0到V0路径为0

final[v0]=1;

//V0至V0不需要求路径V0至V0路径为0，说明第一个顶点第一次搜索时会先从自身开始，而自身到自身的距离始终时0。表示V0点到V0点已经求得最短路径，因此final[0]=1。这个时候final数组中的数值用数组表示为：{1,0,0,0,0,0,0,0,0}，此时对于内存的初始化工作完成。（4）开始主循环，每次循环求得V0与一个顶点的最短路径。除去V0，因此索引从V1开始。（5）先令min为无穷大65535，通过m控制循环，与D[ｍ]比较找到最小值为min=1，同时确定k=1。代码如下：min=INFINITY;

//当前所知离V0顶点的最近距离

for(m

=

0;

m

<

G.numVertexes;

m++)

//寻找离V0最近的顶点

{

if(!final

[m]

&&(*D)[m]

<

min)

{

k

=

m;

min

=

(*D)[m];

//ｍ顶点离V0顶点更近

}

}（6）final[k]

=

1;//将目前找到的最近的顶点置为1算到这一步k=1即表示与V0最近的顶点是V1，这里的D[1]=1表示此时V0到V1的最短路径数值（权值）是1。所以在这里将final[1]设置为1。此时final数组为{1,1,0,0,0,0,0,0,0}；（7）for(ｍ

=

0;

ｍ

<

G.numVertexes;

ｍ++)//修正当前最短路径及距离

{

//如果经过v顶点的路径比现在这条路径的长度短的话

if(

!final[m]

&&

(min

+

G.matirx[k][m]

<

(*D)[m]))

{

//说明找到了更短的路径，修改D[m]和P[m]

(*D)[m]

=

min

+

G.matirx[k][m];//修改当前路径长度

(*P)[m]

=

k;

}

}以上代码实现的功能是在刚才已经找到V0与V1的最短路径基础之上，对V1与其它顶点的边进行计算，得到V0与它们的当前最短距离，如图所示：图3-5以顶点V1为原点搜索新的最短路径因为在这里min的值为1，出现了更小值的边，所以D[2]=5不再是从V0到V2过程中所有边值的和最小的了，现在D[2]=V0→V1→V2=min+3=4，D[3]=V0→V1→V3=min+7=8，D[4]=V0→V1→V4=min+5=6，于是D数组当前值为{0,1,4,8,6,65535,65535,65535,65535}。而P[2]=1，P[3]=1，P[4]=1，其表示V0到V2，V3，V4点的最短路径它们的前驱节点均是V1。此时P数组为{0,0,1,1,1,0,0,0,0}。（8）来到下一顶点，重新开始函数循环，此时i=2。第15~23行，对m循环，注意因为final[0]=1和final[1]=1，由第18行的！final[m]可知：V0与V1并不参与最小值的获取。通过循环比较，找到最小值min=4，k=2。（9）算法继续，这时k的值为2，表示V0到V2的最短路径（暂时）已经计算出结果，此时数组D[2]=4即V0到V2的最小距离为4。因此将V2对应的final[2]设置为1，表示路径已找到，此时final数组中的值为{1,1,1,0,0,0,0,0,0}。（10）运算继续，在上一步的运算结果已经找到V0→V2的路径，继续V2为源点运算搜索与之相邻的最小权值边，得到V0与它们的最短距离。如图所示：图3-6以顶点V2为原点搜索新的最短路径因为min=4，所以D[4]=6不再是V0到V4的最短距离，现在D[4]=V0→V2→V4=min+1=5，D[5]=V0→V2→V5=min+7=11。因此D数组当前值为{0,1,4,8,5,11,65535,65535,65535,65535}。而原本P[4]=1，此时P[4]=2，P[5]=2，它表示的意思是V0到V4和V5的最短路径前驱节点均为V2。此时P数组为{0,0,1,1,2,2,0,0,0}。（11）重新再开始一轮循环，此时i=3。第15~23行，通过对m循环比较找到最小值min=5，k=4。（12）第24行，由k=4表示已经求出V0到V4的最短路径，并且由D[4]=5知道最短路径距离为5。因此将V4对应的final[4]设置为1。此时final数组为{1,1,1,0,1,0,0,0,0}。（13）第25~32行，对V4与其它顶点的边值进行计算，得到V0与它们的当前最短距离，如图所示：图3-7以顶点V4为原点搜索新的最短路径有了新的最小值min为5，所以D[3]=8不再是V0→V3的最小权值，新的计算结果数组D[3]=V0→V4→V3=min+2=7，同理：D[5]=V0→V4→V5=min+3=8，D[6]=V0→V4→V6=min+6=11，D[7]=V0→V4→V7=min+9=14，因此，D数组当前值为{0,1,4,7,5,8,11,14,65535}。数据更新P[3]=1，→P[3]=4，旧数值P[5]=2，→P[5]=4。此时的数组P[6]，P[7]=4，表示V0→V3，V0→V5，V0→V6，V0→V7点目前计算出的路径中，它们的前驱节点是V4。此时P数组值为{0,0,1,4,2,4,4,4,0}。（14）后面的计算就是将之前的运算过程不断重复。在计算到最后一个节点时，得到我们所求的最短路径，即最优路径，如图所示：图3-8最终搜索到顶点V8得到最终的最短路径这时计算已经全部完成，final数组的数值全部更新为已计算完毕，数值为{1,1,1,1,1,1,1,1,1}，表示所有的顶点均完成了最短路径的查找工作。此时D数组为{0,1,4,7,5,8,10,12,16}，它表示V0到每一个顶点的最短路径的距离（权值的和），比如D[8]=1+3+1+2+3+2+4=16。此时P数组中数值为{0,0,1,4,2,4,3,6,7}。这个P数组的值可以理解为：以数组中第8个数值为例，P[8]=7，它表示要查看V0→V8的最短路径时，顶点V8的前驱节点是V7；再由P[7]=6表示要查看V0→V7的最短路径时，顶点V7的前驱节点是V6，同理，P[6]=3表示V6的前驱节点是V3。通过以上过程，我们就得到了：从起点V0到目的地V8最短路径为V8←V7←V6←V3←V4←V2←V1←V0，即就是：v0→V1→V2→V4→V3→V6→V7→V8。1.2.2采用A*算法构造的AGV调度系统A*算法是通过下面这个启发函数来计算每个节点的优先级。QUOTEfn=gn+h(n)f其中：f(n)代表节点n的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。g(n)代表节点n距离起点的代价。h(n)代表节点n距离终点的预计代价，这也就是A*算法的启发函数。A*算法在运算过程中，每次从优先队列中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。A*算法的表示方法通常使用集合“open表”存放待遍历的节点数据，集合“close表”存放已经遍历过的节点数据。经典A*算法使用伪代码描述如下：初始化open表和close表；将起点加入open表中，并设置优先级为0（优先级最高）；如果open表不为空，则从open表中选取优先级最高的节点n：如果节点n为终点，则：从终点开始逐步追踪parent节点，一直达到起点；返回找到的结果路径，算法结束；如果节点n不是终点，则：将节点n从open表中删除，并加入close表中；遍历节点n所有的邻近节点：如果邻近节点m在close表中，则：跳过，选取下一个邻近节点如果邻近节点m也不在open表中，则：设置节点m的parent为节点n计算节点m的优先级将节点m加入open表中1.2两种算法的比较A*算法和迪杰斯特拉（dijkstra）算法都是启发式搜索，迪杰斯特拉（dijkstra）算法可以看成是广度优先搜索（BFS），而A*可以认为是深度优先搜索（DFS）。迪杰斯特拉（dijkstra）算法是按照节点顺序，从当前节点开始，想周边发出搜索，找出当前阶段的最有结果并记录，这样搜索出的结果一定是最优的，不用考虑之前的结果，如此一步一步搜索到最后一个节点，可以在到达终点时，每一次搜索得到一个最优结果，这样计算出的最短路径结果一定时最优解。A*算法在计算过程中使用了两个数组用来才存储已遍历和未遍历的节点，我们将这两个数组分别命名为“OPEN表”和“CLOSE表”。运行过程可以如下表示：（1）将源点数据存入OPEN表；（2）①遍历OPEN表，根据公式（3-1）找出F（F=G+H）值最小的节点，将这个节点设为新的源点，发散式搜索当前节点周围的节点；②搜索完毕，将这个节点标记为已搜索并将这个节点存入CLOSE表中；③将当前搜索的节点周围紧邻的节点放到OPEN表中（除了墙、禁行区域、障碍物等）；④重复上述操作，每一次循环开始，选择F值最小的节点作为当前操作节点。（3）当最后一个节点数据存入到CLOSE表中的时候，算法结束。（4）将最终的到的路径存入内存中，从终点开始，每个节点沿着父节点移动到起点，就是最终路径。上面的公式我们在上一小节已经做出了解释，在这里我命在做出简单的描述：F=G+H中：H是启发函数，是当前点到终点距离的估计，一般采用曼哈顿距离（当前点和终点横纵坐标差之和）；G就是起点到当前点的距离，这里G值的度量方式一般是上下左右取一个值比如10，对角线的四个点取一个值比如14（一般比上下左右的值要大），而在A*中表示障碍点一般会给对应点一个特别大的G值，所以在筛选的时候就会放掉。1.3工作空间模型建立方法在解决路径规划问题之前，我们首先要考虑如何对工作环境建立模型。工作环境空间建立模拟地图是对AGV车辆进行路径规划的前提，这是我们所设计和开发的AGV车辆调度系统所需要解决的最基本的问题。在建立模拟地图的时候，我们需要先将AGV车辆（机器人）的工作空间进行模拟数值化，图形化，然后将我们测量和计算得到的这些信息转换成可以在电脑种存储的数字信息，将这些信息输入到AGV车辆调度控制系统的内存里，然后调度系统调用代码中的核心算法，一句模拟地图给出的信息从而对AGV车辆进行路径规划，已确保AGV车辆平稳顺利运行到目标地点。本文介绍一种名为“格栅建模法”的建立地图的方法。栅格地图建模法是由卡内基梅隆大学的汉斯·莫拉维克（HansMoravec）等人在“占据栅格地图”（Occupancygridmapping）算法的基础上开发出来的新型地图建模方法，是一种在解决AGV车辆路径规划问题上的比较成熟的应用技术，在目前市场上出现的比较成熟的商业AGV调度系统种已经有了比较广泛的应用。栅格地图法是的原理是：将AGV车辆（机器人）的实际工作空间的地图信息离散化，再把地图分割成若干个大小均匀，彼此互相紧邻的单元格，建立好栅格后，我们需要在每一个单元格上做出标记（一般使用序号标记法）。在算法开始进行路径规划时，我们首先建立一个数组矩阵，用来表示AGV车辆（机器人）的工作空间环境。在建立好的模拟栅格地图中，我们将障碍栅格标记为1，这说明在这个标记为１的栅格所代表的实际位置存在障碍物，AGV车辆无法在此处通行；我们将自由栅格标记为0，这说明在这个标记为０的栅格所代表的实际位置是不存在障碍物的，可以自由通行。栅格地图建模法建立地图模型的性能始于地图划分栅格大小、多少、精细程度等因素息息相关的。栅格分割的越小，分辨率越高，其表示的工作环境空间信息将会非常精细和清晰，但这样精细的信息往往是以运行速度降低为代价的，栅格划分越精细，占用内存越大，运算时间过长，反应越慢，这样反而会降低整个系统的工作效率；反之，我们对栅格划分的大小略微放宽要求，虽然会降低模拟地图的精度，但计算速度会大幅度提升，效率也就变高了。所以我们在建立模拟栅格地图时，需要综合考量各方面因素，包括实际运行空间的大小、计算机的运算性能等因素，合理的规划处最适合当前车间环境的模拟山歌地图，使系统的运行效率达到最高。AGV工作空间的环境建模使用栅格地图建模法，其创建地图的难度较低，维护方便，且可以在空间中出现临时仿制的障碍物时能轻松做出调整，因此我在这篇文章里选择栅格地图建模法来建立AGV车辆（机器人）的工作空间环境的模拟地图。在建模过程中，先不考虑AGV车辆（机器人）和障碍物（墙壁、机床等）的高度，使用栅格地图建模法将AGV的工作空间环境转化为数字化的二维数组。理想状态下，设定环境中的障碍物永远保持静止状态。假定工作空间环境信息已知，即AGV车辆（机器人）的起始点位置及环境中的障碍物位置。我们将AGV车辆（机器人）的工作空间环境切割成大小、形状完全一致的栅格，并对栅格使用二进制数字进行标识。常用的栅格标识方法有两种：直角坐标法和序号法。直角坐标法是以栅格地图的左下角为坐标原点，可以近似理解为平面直角坐标系。设定以每个栅格的几何中心点坐标记为AGV停留此处时的坐标，如图3-9所示。序号法就是从栅格地图的左下角的栅格开始，按照从左到右，从下到上的顺序给每一个栅格标上序号，如图3-9所示:图3-9栅格地图法建立地图示意直角坐标法和序号法可以通过映射关系来进行转换，其计算方法为：QUOTE