篇一：路径分析算法
路径规划-算法基础?章?录1?个重要概念图的路径：图G=中，从任?顶点开始，由边或弧的邻接?关系构成的有限长顶点序列称为路径。注意：有向图的路径必须沿弧的?向构成顶点序列；构成路径的顶点可能重复出现(即允许反复绕圈)。路径长度：路径中边或弧的数?。简单路径：除第?个和最后?个顶点外，路径中?其它重复出现的顶点，称为简单路径。回路或环：路径中的第?个顶点和最后?个顶点相同时，称为回路或环。图的最短路径：如果从有向图中某?顶点(称为源点)到达另?顶点(称为终点)的路径可能不??条，如何找到?条路径使得沿此路径上各边上的权值总和达到最?。2深度或?度优先搜索算法算法概述????从起点开始访问所有深度遍历路径或?度优先路径，则到达终点节点的路径有多条，取其中路径权值最短的?条则为最短路径。算法流程（1）选择单源的起点作为遍历的起始点。??（2）采?深度优先搜索或者?度优先搜索的?式遍历图，在遍历同时记录可以到达终点的路径。??（3）在所有路径中选择距离最短的路径。算法分析????采?遍历的?式获取单源最短路径，是?种暴?破解的?式。算法的性能与遍历过程性能相关。采?深度优先搜索遍历时时间复杂度为O(n+e)。3迪杰斯特拉（Dijkstra）算法算法概述??Dijkstra（迪杰斯特拉）算法是典型的单源最短路径算法，?于计算某个顶点到其他所有顶点的最短路径。Dijkstra（迪杰斯特拉）算法要求图中不存在负权边，即保证图中每条边的权重值为正。算法的基本思想是：从源点出发，每次选择离源点最近的?个顶点前进，然后以该顶点为中?进?扩展，最终得到源点到其余所有点的最短路径。算法流程（1）将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点s?个顶点。我们这???个book[i]数组来记录哪些点在集合P中。例如对于某个顶点i，如果book[i]=1则表?这个顶点在集合P中，如果book[i]=0则表?这个顶点在集合Q中。（2）设置源点s到??的最短路径为0即dist=0。若存在源点有能直接到达的顶点i，则把dist[i]设为e[s][i]。同时把所有其它（即源点不能直接到达的）顶点的最短路径为设为∞。（3）在Q中选择?个离源点s最近的顶点u（即dist[u]最?）加?到P中。并考察所有以点u为起点的边，对每?条边进?松弛操作。
（4）重复第3步，如果集合Q为空，算法结束。最终dist数组中的值就是源点到所有顶点的最短路径。算法分析复杂度：迪杰斯特拉（Dijkstra）算法适?于权值为?负的图的单源最短路径，使?最?堆时间复杂度是O(VLogV)，?斐波那契堆的复杂度O(E+VlgV)。为什么不能有负权边：Dijkstra算法当中将节点分为已求得最短路径的集合（记为P）和未确定最短路径的个集合（记为Q），归?P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果?于a原先确定的最短路径长度(意思是原先从a0—a已经确定?个最短路径，?此时的边权值为负，则此步骤中的边权计算结果必定?于已经确定了的路径长度)，但是a在Dijkstra算法下是?法更新的，由此便可能得不到正确的结果。4Bellman-Ford算法算法概述??Bellman-Ford算法是从Dijkstra算法算法引申出来的，它可以解决带有负权边的最短路径问题。值得注意的是，Dijkstra算法和下?的Floyd算法是基于邻接矩阵的，?Bellman-Ford算法是基于邻接表，从边的?度考量的。??句话概括就是：对所有的边进?n-1次松弛操作。如果图中存在最短路径（即不存在负权回路），那么最短路径所包含的边最多为n-1条，也就是不可能包含回路。因为如果存在正回路，该路径就不是最短的，?如果存在负回路，就压根就不存在所谓的最短路径。算法流程（1）从源点到任意?点u的最短路径的长度，初始化数组dist[u]为0，其余dist[i]为?穷?。（2）以下操作循环执??多n-1次，n为顶点数：??对于每?条边edge(u,v)，如果dist[u]+weight(u,v) 算法流程（1）从任意?条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为?穷?。 （2）对于每?对顶点u和v，看看是否存在?个顶点w使得从u到w再到v??知的路径更短。如果是更新它。算法分析弗洛伊德（Floyd）算法的核?代码如下：for(inti= 1;i<=n;i++)//枚举所有顶点，i代表顶点u{ for(intj= 1;j<=n;j++)//枚举所有顶点，j代表顶点v { for(intk= 1;k<=n;k++)//查找是否有中间顶点w使得从u到w再到v??知的路径更短 { if(dist[j][k] >dist[j][i] +dist[i][k]) {dist[j][k] =dist[j][i] +dist[i][k]; } } }}??可以看出Floyd算法是?种暴?破解的?式获取最短路径。Floyd算法的时间复杂度为O(n^3)空间复杂度为O(n^2)。Floyd算法可以获得任意顶点对之间的最短路径。结语??最短路径问题是图论研究中的?个经典算法问题。因此针对图最短路径问题先后提出了许多算法。各类算法的应?场景不尽相同。Dijkstra算法和Bellman-Ford算法?于解决单源最短路径，?Floyd算法可以解决多源最短路径。????Dijkstra算法适?稠密图（邻接矩阵），因为稠密图问题与顶点关系密切。Bellman-Ford算法算法适?稀疏图（邻接表），因为稀疏图问题与边关系密切。Floyd算法在稠密图（邻接矩阵）和稀疏图（邻接表）中都可以使?。
篇二：路径分析算法
基于时间窗算法的AGVs路径分析及规划
摘要：科学技术日新月异，AGVs在现代货物搬运中得到了越来越广泛的使用。其自动化程度高，能够满足柔性制造系统和立体仓库的要求。但是在AGVs中，由于多个AGV的共同运行，很可能导致碰撞冲突，所以合理解决此问题显得尤为关键。时间窗算法作为一种预测式防冲突控制方法，可以有效解决系统中存在的路径冲突问题，改善系统的性能。
关键字：AGV;AGVs;路径分析；路径规划；时间窗算法
AnalysisandPlanningofAGVsPathBasedonTimeWindowAbstract:Scienceandtechnologychangeswitheachpassingday.AGVshasbeenmoreandmorewidelyusedinmodernmaterialhandling.Itshighdegreeofautomationcansatisfytherequirementsoftheflexiblemanufacturesystemandthemulti-layeredstorehouse.InAGVs,however,duetotherunningofmultipleAGVislikelytocauseacollisionoraconflict.Areasonablesolutiontothisproblemisparticularlycritical.Timewindow,asapredictionofanti-collisioncontrolmethod,caneffectivelysolvetheproblemofpathconflictexistedinthesystemandimprovetheperformanceofthesystem.
Keywords:AGV;AGVs；pathanalysis;pathplanning;timewindow
随着计算机和自动化技术的发展，传统的生产和物料输送方式正在向自动化和智能化的方向行进。AGVs(AutomatedGuidedVehiclesystem)作为货物搬运输送系统，由于其自动化程度高，能够满足柔性制造系统和立体仓库的要求，所以应用范围也不仅局限于制造车间搬运工件，同时在仓库，港口，机场，邮政等地都可执行搬运作业。
1.AGV概述
1.1AGV的定义及发展
AGV(AutomatedGuidedVehicle)是自动导引小车的缩写，是指装有电磁或光学等自动导引装置，能够沿着规定的导引路径行驶，并具有小车编程与停车选择装置，安全保护装置以及各种移载功能的运输小车。它是现代物流系统中的关键设备之一，以电池为动力，进行非接触式导引，并可根据实际需要配备不同的移载机构，以完成相应的操作任务。AGVs是指自动导引车系统，由管理计算机、数据传递子系统、若干辆沿导引路径行驶的自动导引小车、地面子系统等组成，用于及时有效的分派AGV到某位置完成指定动作，而且具有监控管理的系统。
AGV技术的发展历史有两个来源：一个是由叉车技术发展而来，一个由机器人技术发展而来。两者的目的都是实现货物的自动搬运。从导航方法来看，其技术的发展经历了电磁导航、光学导航、激光导航和无路径的视觉导航等发展阶段。从控制方法来看，由最初的速度闭环发展到目前的位置闭环控制。从控制系统的体系结构看，由原来的专用封闭结构发展到现在的开放式结构。从驱动的方式看，由原来的直流电机驱动、直流无刷电机驱动到交流伺服电机驱动。从能源角度看，由最初的铅酸电池发展到快速充电的镍铬电池，再到不需要充电的感应供电方式。AGV与传统工具相比在于其具有更高的可靠性，适应性。所以其也正朝着更为智能的方向发展。
1.2AGV的组成及分类
AGV的基本构成包括：车体、能源储存装置、转向和驱动系统、安全系统、控制与通信系统、导引系统。
自动导引车的应用范围广泛，形式多种多样，按不同的分类标准，可以有不同的分类方法。按有无轨道分类，可以分有轨型AGV和无轨型AGV；按用途分类，可以分为搬运型AGV、装配型AGV、自动叉车、自动拖车等多个种类；按行驶方式不同，可以分为轮式和履带式两种；按照驱动方式又可以分为单轮驱动，差速驱动和全向轮驱动；按导引方式不同，可以分为电磁导引、激光导引，视觉导引，惯性导引，声波导引和GPS导引等类型；按搬运机构不同，可以分为牵引式、后叉式、侧叉式；按照有无导引路径，可以分为固定路径和自由路径两大类；按照自动化程度可以分为全自动化AGV和简易AGV-AGC。
2.AGVs路径分析
由于单个AGV工作能力有限，所以在某些复杂任务中常常需要多个AGV共同参与，即构成了AGVs。AGVs的研究领域主要包括体系结构、多机器人避碰问题、编队队形问题以及信息共享等。其中主要需要解决的问题是，多个AGV之间的避碰和冲突问题。
2.1AGVs路径规划的问题
单个AGV路径规划主要解决路径搜索问题，即在给定地图中找到最优路径，其所处的环境是静态环境，属于静态路径规划问题。
AGVs中，由于多个AGV在运动，所以所处的环境是实时动态环境。在多个AGV运行过程中，很可能发生的问题就是碰撞冲突。所以所以多AGV路径规划问题不同于单AGV路径规划具有简单的评价指标，多AGV路径规划是在保证系统无冲突的情况下，实现评价指标最短，为每个AGV规划出一条无碰撞、协调的路径。
AGVs中主要解决多个AGV之间的碰撞和冲突问题。解决此类问题的方法有很多，比方说有预测式避碰、反应式避碰和路径铺设法等。预测式避障法是首先为各AGV规划好最优路径，然后根据每台AGV的路径离线预测AGV之间是否会发生冲突，如果发生，则调整AGV的路径来避免碰撞。反应式避碰法是在运行过程中根据系统当前的状态一段一段的确定AGV路径，反应式避碰能迅速响应系统环境变化，属于闭环控制。路径铺设法主要通过设置主副车道，再加以若干规则来进行，算法简单，但不具备通用性。基于时间窗算法的AGVs路径规划方法属于预测式防冲突控制方法。
2.2AGVs冲突的类型
AGVs中，冲突类型主要有三种：路口冲突，赶超冲突和相向冲突。三种冲突的基本场景如下：
⑴路口冲突
图1路口冲突
图1中的两辆AGV同时到达路口后，又分别向不同的方向行驶。如果没有安全措施，两辆AGV将在路口发生碰撞，这种冲突称为路口冲突。
⑵赶超冲突
图2赶超冲突
图2中的两辆AGV，如果AGV1的速度大于AGV2，在没有采取措施的情况下,AGV1会在行驶中撞到AGV2，这种冲突称为赶超冲突。
⑶相向冲突
图3相向冲突
图3中的两辆AGV，如果没有避障措施，两辆车将会相向行驶，然后相撞，这种冲突称为相向冲突。
以上三种冲突的本质都是时空重叠问题。如果冲突不能有效解决，将会导致系统停在冲突的状态无法继续下去，进而会形成死锁，导致系统的故障和停机。
3.基于时间窗算法的AGVs路径规划
3.1时间窗算法描述
时间窗算法最初是根据系统交通状况，在双向有向图中为AGV搜索无冲突最优路径。时间窗算法属于预测式防冲突控制方法。
假设系统有小车n台小车，小车集合为R?{r1，r2,...,rn}。共有m台AGV被分配用来执行任务，任务集合为M?{m1,m2,...,mm}。对于每个任务mi，都有一条路径与之对应，该路径为一系列弧段的集合，从起始位置Oi到终止位置Di的路径可以表示为有序弧段集合每个任务mi都有优先?i?{ej,ek,...,eq},其中ej,ek,...,eq?E是环境地图边集合中的路段。级pi。每个任务都可以描述为mi?t???Oi,Di,?i?t?,Pi?t?,ri?。
其中，对于每个任务，起始位置、目标位置和分配的小车都不随时间变化。小车的路径如果不发生冲突，也不发生改变，如果在任务执行过程中，有需要改变路径才能解决的冲突，则动态改变路径。每个小车在初始分配任务的时候指定一个优先级，在任务执行过程中，随着任务执行时间越长，该任务的优先级逐渐变高。
当AGV小车执行任务时，不断地驶入并驶出路径中的有序路段，在小车驶入和驶出的in这段时间内，该路径被此小车占领，其他小车不得进入。tij是执行任务mi的小车驶入弧段out是该小车驶出弧段ej的时间。进入时间和驶出时间即定义了该弧段的时间ej的时间，tij窗，其中，该弧段被占用的时间成为保留时间窗，没有被占用的时间成为自由时间窗。在保留时间窗里，该弧段已经被固定的AGV占用，其他小车不能进入，自由时间窗内，其他小车可以驶入，不会发生冲突。对于任务mi定义ri小车进入路径ej的时间窗口?ij为out。
?ij?tinij，tij??
假设小车在执行任务中，包含的路段为n，则根据小车的速度及路上的转弯情况，可以计算出此小车进入和驶出所有路段的时间窗。这样，每个路段的时间窗都可以通过计算得到。
3.2时间窗算法步骤
对于系统分配的m个任务，对任务按优先级进行排序，，然后采用基于优先级的调度策略进行任务调度。
首先，选择最高优先级的任务，选择一辆空闲小车，并使用Dijkstra算法规划出该任务的最短路径，并计算出该任务中所有占用路径的进入和驶出时间，初始化各个路段的时间窗向量表。
然后，选择次优任务进行路径规划，检查是否有空闲小车，如果没有，则进入等待状态；如果有，则调用Dijkstra路径规划算法，并计算出该任务所有占用路径的进入和驶出时间，更新各个路段的时间窗向量表。之后计算各个路段的时间窗向量表中是否存在冲突，如果不存在冲突，路径规划完成。如果存在冲突，则在路径规划算法中将第一个冲突路段标记为不可用，再次调用最短路径算法进行路径规划，重复上述过程，直到不存在冲突。如果不能规划出最短路径，则暂停对该任务的调度，调度接下来的任务。
最后，对剩余任务中优先级最高的任务进行小车分配和路径规划，同样，在路径规划后，更新系统的时间窗向量表，并检查是否存在冲突，重复上述过程。这样，经过这样的计算过程，即可对多个任务进行调度并为多个AGV规划出无冲突的路径。
3.3冲突解决方法
⑴等待策略
等待策略可以有效解决路径冲突问题，下面介绍等待策略对于三种冲突的解决步骤：
①在路口冲突中，最重要的问题是决定哪辆车停下来等待，哪辆车先行通过路口。具体22?x2j?yi?yj小于设定值的时候，判断两辆车距离交叉路口的距离，如果小车i距交叉路口的距离远小于小车j，则小车i先通过路口；如果小车i距交叉路口的距离和小车j距离交叉路口的距离无明显差距，则执行优先级较高任方法是当两辆车i和j的距离dij??x2i???务的车先通过。当在等待状态的小车周围安全距离内，没有小车后，恢复等待状态的小车的运行。
②在赶超冲突中，此时若采用等待策略，即等前面的车通过后，后面的小车再进入此路段。
③在相向冲突中，，如果两辆车的路径中，只有一段公共交叉路段，采用等待策略可以解决；但是如果有多个公共交叉路段，例如两辆小车的所在路段刚好同为对方的下一路段，则此种冲突不能通过等待策略解决。
⑵重新规划路径策略
对于上述③中不能解决的问题，需要重新规划路径来解决。通过设置冲突路段为不可用，重新调用路径搜索算法搜索新的路径。然后根据新路径更新时间窗向量表，循环进行，直到规划出无冲突路径。
3.4时间窗算法的优缺点
时间窗算法具有冲突检测准确、易于实现、对环境变化响应速度快和能进行全局优化等2优点。但该算法复杂度为On，随着环境中任务和小车数量增多，系统计算量迅速增加，而且会导致所搜索到的路径变得不够优化，不适合AGV数量过多的系统。
??4.总结
AGVs在现代科技中具有无可比拟的优势，合理和有效解决系统中的路径冲突问题是高效利用AGVs的关键。时间窗算法作为一种预测式防冲突控制方法，可以有效解决系统中存在的路径冲突问题，提高AGV的利用效率，改善AGVs的性能。
参考文献
[1]张辰贝西,黄志球.自动导引车(AGV)发展综述[J].中国制造业信息化,2010(1)[2]黄智荀,王宝华.激光导引叉车在国内的应用[J].物流技术与应用,2006(7)[3]李进,陈无畏.自动导引车视觉导航的路径识别与跟踪控制[J].农业机械学报,2008(2)[4]张宏远.基于Petri网的分布式多AGV路径规划及避碰研究[J].西安:西北工业大学硕士论文,2002[5]李静.多移动机器人路径规划避碰和协调研究[D].上海:上海交通大学博士论文,2007
篇三：路径分析算法
GIS空间分析（六）——最短路径分析最短路径问题路径问题涉及的?络是固定的道路?络。最佳路径问题是在预先规划的道路?络上寻找?个结点到另外结点之间最近（或成本最低）的路径。最佳路径分析也成最优路径分析，其?直是计算机科学、运筹学、交通?程学、地理信息科学等学科的研究热点。这?“最佳”包含很多含义，不仅指?般地理意义上的距离最短，还尅是成本最少、耗费时间最短、资源流量（容量）最?、线路利?率最?等标准。很多?络相关问题，如最可靠路径问题、最?容量路径问题、易达性评价问题和各种路径分配问题都可以纳?最佳路径问题的范畴之中。?论判断标准和实际问题中的约束条件如何变化，其核?实现?法都是最短路径算法。最短路径问题的表达式?较简单的，从算法研究的?度看，最短路径问题通常可归纳为两?类：?类是所有点对之间的最短路径；另?类是单源点间的最短路径。从?个单?的源到?络中所有或许多其他的定点的最短路径分析，成为单源SPAs或单源查询。从?个单?的源产?的最短路径的集合被称为最短路径树（SPT）。计算最短路径的的典型算法有Dantzig和Dijkstra算法，这两者都是单源的SPAs，适?于具有?负边权的?路，算法通常需要的时间是O（n^2），其中n是节点的数?。Dantzig算法Dantizig算法是?种具有离散动态规划形式的算法。算法基本步骤如下：假设：求解顶点1到点2、3、4所有顶点的最短路径。1）确定从顶点1开始的最短（最少的距离/成本/时间）边。2）确定从顶点2开始并加上（1,2）边成本的最短（最少累计成本/时间）边。3）确定标记集中最短（最少的累计成本/时间）的边。4）所有的顶点都到打的时候停?；重复从顶点2、3和4开始，计算从每?个顶点出发的所有最短路径。Dijkstra算法Dijkstra（戴克斯图拉）算法是戴克斯图拉于1959年提出的?种按路径长度递增的次序产?最短路径的算法，此算法被认为是解决单源点间最短路径问题经典且有效的算法。算法基本步骤如下：假设：每?个点都有?对标号（d,p）,其中d为从起源点s到点j的最短路径的长度（从顶点到其本?的最短路径是零路，即没有弧的路，其长度等于零）；p为从s到j的最短路径中j点的浅?点。求解从起源点s到点j的最短路径算法也成标号法或染?法。1）初始化。起源点设置为d=0，p为空，并标记起源点s，记k=s，其他所有点设为未标记点。2）检验从速有已标记的点k到其直接连接的未标记的点j的距离，并设置d=min[d,d+l]，式中l为从点k到j的直接连接距离。3）选取下?个点。从所有未标记的结点中，选取d中最?的?个i，有d=min[d,所有未标记的点j]，式中i就被选为最短路径中的?点，并设为已标记的点。4）找到点i的前?点。从已标记的点中找到直接连接到点i的点j，作为前?点，记为i=j5）标记点i。如果所有点已标记，则算法完全退出，否则记k=i，重复步骤2~4。弗洛伊德算法弗洛伊德（Floyd）算法能够求得每?对顶点之间的最短路径。算法基本步骤如下：假设：求从顶点i到j的最短距离。1）若从i到j有弧。则从i到j存在?条长度为d的路径，该路径不?定是最短路径，需要进?n次试探。?先判别弧（i，k）和弧（k，j）是否存在[即考虑路径i,k,j是否存在]2）如果存在，则?较（i，j）和（i，k，j）的路径长度，较短者为从i到j的中间顶点的序号不?于k的最短路径。假如在路径上在增加?个顶点m，若路径（i，…，m）和路径（m，…，j）就有可能是从i到j的中间顶点的序号不?于k的最短路径，那么后来的路径（i，…，m，…，j）就有可能是从i到j的中间顶点的序号不?于m的最短路径。将它和已经得到的i到j的中间顶点的序号不?于k的最短路径进??较，从中选出中间顶点序号不?于m的最短路径，然后增加?个顶点n，继续进?试探，经过n次?较后，最后求得的必将是i到j的最短路径。矩阵算法矩阵算法是利?矩阵来求出图的最短距离矩阵。算法基本步骤如下：1）已知图的邻接矩阵A；2）求出A，A^2，A^3，…，A^n-2；3）求出D=AA^2A^3…A^N-2由m×n个数aij排成的m?n列的数表称为m?n列的矩阵，简称m×n矩阵。记作：