物流系统中AGV路径规划算法的研究

随着国际市场竞争的加剧，各先进工业国迫切需要采用能提高生产率、减低成本、加快产品更新换代、满足多品种小批量生产要求并迅速响应市场变化的现代化制造技术。我国于80年代末90年代初开始重视引进和消化吸收国外的先进物流系统技术与设备，在消化吸收国外柔性制造系统FMS技术的基础上，结合国情，安排开发了一批“准柔性制造系统”。AGV是物流系统中关键基础设备，在物流系统中承担材料运输的关键性活动。AGV根据控制系统的要求给各个设备运输加工零件，并将系统的各个部分连接起来，形成了一个有机的整体，适用于企业的传统生产模式向柔性或准柔性生产组织模式的转化，对提高企业的市场竞争力和经济效益具有十分重要的意义。 路径规划是实现车辆自动化正常运行不可或缺的部分，它能够提高系统的效率，节省生产成本，促进工业的自动化，实现系统的最优调度，保证每台AGV在碰撞的情况下，完成预定的任务。单台AGV无法满足从整体上提高物流自动化系统中生产效率的要求。一个相互协调的多AGV物流系统有着单台AGV系统所无法比拟的优势。 然而多台AGV构成的物流运输系统也存在着单台AGV所不具备的问题，如AGV间的冲突、行为协调和信息共享等等问题。因此研究物流系统中多AGV路径规划问题就变得十分必要。 结合吉林省科委项目和目前物流系统中多台AGV的实际需要，本文进行了以下内容的研究： 1. 单车路径规划算法的研究。 单车路径规划是多车路径规划研究的基础，因此本文首先从对单车路径规划方法进行了探讨，介绍了如何建立环境电子地图和单车路径规划算法。 (1) 建立复杂网线道路的电子地图。 环境地图数据结构必须充分完整地体现路径信息，因此我们首先设计了图形数据结构。在此基础上，应用Access2000开发了小型数据库，借助VC++6.0提供的ADO数据库访问技术，建立了数据库与应用程序的连接，生成了道路网电子地图。 (2) 单车AGV路径规划算法。 本文选择距离作为优化的目标，故本文研究的单车路径规划问题就转化为求单车路径最短问题。通过比较几种求解单节点源最短路径的方法，我们选择了经典的Dijkstra算法。 试验表明，建立的电子地图描述了环境的基本特性，采用的单车路径规划算法正确、可行。 2. 多车路径规划算法 对多AGV系统而言, 为每个AGV规划出一条无碰、协调的路径就成为其中很重要的一个问题。因此，本文建立了多AGV协调控制模型，并在此基础上，研究了基于优先权的交通规则法，解决了AGV间的冲突。 (1) 建立复杂网线道路中多台AGV路径规划协调系统模型。 本文采用集中式协调控制结构，即上层中央离线控制和下层AGV在线检测相结合的控制结构。上层中央控制系统属于离散的事件系统，经综合分析几种离散事件系统建模的方法，我们采用了有色Petri网对该离散系统进行建模，为系统中的每台AGV进行着色。有色Petri网以图的形式，简洁、直观地描述了AGVS系统地运行情况，再现了AGVS系统的离散控制过程，为解决多车路径规划问题提供很好地分析工具和理论指导。 (2) 研究多台AGV路径规划的算法。 本文研究的多车路径规划算法主要是通过中央规划器和AGV在线检测冲突来实现的。AGV沿着规划器规划的路径前进，同时监控室借助无线局域网实现了电子地图中各节点信息的及时更新，控制系统的协调运作。 中央规划器为系统中的每台AGV设计一条无碰路径。该规划器分为获取新任务、初始路径规划、冲突检测、解决冲突几个模块。规划器的工作流程如下：系统获取用户输入的任务信息，对批任务中的每台AGV进行初始路径规划，而后对每台AGV的初始路径进行冲突检测，当发现AGV间路径存在冲突后，采用了基于优先权的交通规则法，解决系统中出现的几种类型冲突,最终为每台AGV找到一条与系统中的其他AGV不发生冲突的路径。 AGV通过避障传感器和通讯信息实现在线检测冲突。本文重点介绍了如何利用通信信息实现系统的在线避碰。中央控制室根据AGV发过来的节点信息，实时地更改地图中各节点的占用信息和节点属性信息，在线地解决了AGV运行过程中出现的冲突。 计算机仿真试验和实车试验表明，多车路径规划算法正确、可行。