基于时间窗算法的AGVs路径分析和规划

基于时间窗算法的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台小车，小车集合为},...,{r21nrrR，。共有m台AGV被分配用来执行任务，任务集合为},...,,{21mmmmM。对于每个任务im，都有一条路径与之对应，该路径为一系列弧段的集合，从起始位置iO到终止位置iD的路径可以表示为有序弧段集合}e,...,e,{eqkji,其中Eeeeqkj,...,,是环境地图边集合中的路段。每个任务im都有优先级ip。每个任务都可以描述为iiiiiirtPtDOtm,,,,。其中，对于每个任务，起始位置、目标位置和分配的小车都不随时间变化。小车的路径如果不发生冲突，也不发生改变，如果在任务执行过程中，有需要改变路径才能解决的冲突，则动态改变路径。每个小车在初始分配任务的时候指定一个优先级，在任务执行过程中，随着任务执行时间越长，该任务的优先级逐渐变高。当AGV小车执行任务时，不断地驶入并驶出路径中的有序路段，在小车驶入和驶出的这段时间内，该路径被此小车占领，其他小车不得进入。inijt是执行任务im的小车驶入弧段je的时间，outijt是该小车驶出弧段je的时间。进入时间和驶出时间即定义了该弧段的时间窗，其中，该弧段被占用的时间成为保留时间窗，没有被占用的时间成为自由时间窗。在保留时间窗里，该弧段已经被固定的AGV占用，其他小车不能进入，自由时间窗内，其他小车可以驶入，不会发生冲突。对于任务im定义ir小车进入路径je的时间窗口ij为outijinijijtt，。假设小车在执行任务中，包含的路段为n，则根据小车的速度及路上的转弯情况，可以计算出此小车进入和驶出所有路段的时间窗。这样，每个路段的时间窗都可以通过计算得到。3.2时间窗算法步骤对于系统分配的m个任务，对任务按优先级进行排序，，然后采用基于优先级的调度策略进行任务调度。首先，选择最高优先级的任务，选择一辆空闲小车，并使用Dijkstra算法规划出该任务的最短路径，并计算出该任务中所有占用路径的进入和驶出时间，初始化各个路段的时间窗向量表。然后，选择次优任务进行路径规划，检查是否有空闲小车，如果没有，则进入等待状态；如果有，则调用Dijkstra路径规划算法，并计算出该任务所有占用路径的进入和驶出时间，更新各个路段的时间窗向量表。之后计算各个路段的时间窗向量表中是否存在冲突，如果不存在冲突，路径规划完成。如果存在冲突，则在路径规划算法中将第一个冲突路段标记为不可用，再次调用最短路径算法进行路径规划，重复上述过程，直到不存在冲突。如果不能规划出最短路径，则暂停对该任务的调度，调度接下来的任务。最后，对剩余任务中优先级最高的任务进行小车分配和路径规划，同样，在路径规划后，更新系统的时间窗向量表，并检查是否存在冲突，重复上述过程。这样，经过这样的计算过程，即可对多个任务进行调度并为多个AGV规划出无冲突的路径。3.3冲突解决方法⑴等待策略等待策略可以有效解决路径冲突问题，下面介绍等待策略对于三种冲突的解决步骤：①在路口冲突中，最重要的问题是决定哪辆车停下来等待，哪辆车先行通过路口。具体方法是当两辆车i和j的距离2222ijdjijiyyxx小于设定值的时候，判断两辆车距离交叉路口的距离，如果小车i距交叉路口的距离远小于小车j，则小车i先通过路口；如果小车i距交叉路口的距离和小车j距离交叉路口的距离无明显差距，则执行优先级较高任务的车先通过。当在等待状态的小车周围安全距离内，没有小车后，恢复等待状态的小车的运行。②在赶超冲突中，此时若采用等待策略，即等前面的车通过后，后面的小车再进入此路段。③在相向冲突中，，如果两辆车的路径中，只有一段公共交叉路段，采用等待策略可以解决；但是如果有多个公共交叉路段，例如两辆小车的所在路段刚好同为对方的下一路段，则此种冲突不能通过等待策略解决。⑵重新规划路径策略对于上述③中不能解决的问题，需要重新规划路径来解决。通过设置冲突路段为不可用，重新调用路径搜索算法搜索新的路径。然后根据新路径更新时间窗向量表，循环进行，直到规划出无冲突路径。3.4时间窗算法的优缺点时间窗算法具有冲突检测准确、易于实现、对环境变化响应速度快和能进行全局优化等优点。但该算法复杂度为2nO，随着环境中任务和小车数量增多，系统计算量迅速增加，而且会导致所搜索到的路径变得不够优化，不适合AGV数量过多的系统。4.总结AGVs在现代科技中具有无可比拟的优势，合理和有效解决系统中的路径冲突问题是高效利用AGVs的关键。时间窗算法作为一种预测式防冲突控制方法，可以有效解决系统中存在的路径冲突问题，提高AGV的利用效率，改善AGVs的性能。参考文献[1]张辰贝西,黄志球.自动导引车(AGV)发展综述[J].中国制造业信息化,2010(1)[2]黄智荀,王宝华.激光导引叉车在国内的应用[J].物流技术与应用,2006(7)[3]李进,陈无畏.自动导引车视觉导航的路径识别与跟踪控制[J].农业机械学报,2008(2)[4]张宏远.基于Petri网的分布式多AGV路径规划及避