基于多台自动导引运输车的自动分拣系统

章信华， 嵇建波

(桂林航天工业学院 电子信息与自动化学院， 广西 桂林 541004)

随着经济社会的不断快速发展，物流业面临着越来越大的物流压力[1]。AGV由于具有灵活高效、安全可靠、及维修方便等诸多优点，在物流自动化中受到了越来越多厂商的重视[2]。仓库是整个物流行业中最重要的部分，但随着现代快递行业的快速发展，导致仓库库存的物品种类和容量都极大增多，从而对物流分拣工作提出了严峻的挑战。而追求低错单率和低人工成本，同时提高仓储系统的整体运转效率，促进企业向智能自动化转型，成为仓储物流业发展的主要目标[3]。而仓储物流中最重要的系统就是自动分拣系统。

自动分拣系统的运作流程是，通过机械手获取输入任务，之后在调度系统的智能调度算法运作下，安排仓库里面的AGV执行分拣任务，且AGV在执行任务的过程中，走的是最短路径，不发生碰撞，从而实现货物的入库、出库、搬运和装卸的高度自动化。而整个系统中最重要的是，调度算法是否合理、路径规划是否正确、AGV工作的时候是否碰撞等等。实现多台AGV的无碰撞调度, 提高分拣效率, 降低成本, 提高企业效益，是系统软件的核心任务。由此可见, 对多台AGV的自动分拣系统的研究具有非常重要的实用价值[4]。

1 项目目标

本文设计的自动分拣系统用于无人仓库中，参考图1[5]所示，该系统的工作流程如下：

图1 自动分拣系统

1)由机械手从传送带上抓取物品，并扫描物品上的二维码，获取分拣目的地。

2)将该信息输入调度系统，将产生一个新的分拣任务。

3)调度系统调度一辆AGV将该物品运到相应的位置，完成分拣任务。

2 硬件架构

基于多台AGV的物流分拣系统，其硬件组成主要包括：运行着“AGV调度系统”的服务器、多台“AGV小车”和机械手等等。在整个系统中，调度系统的算法、调度系统与AGV小车的通信方式、AGV的导航方式都非常重要。

运行着“AGV调度系统”的服务器，是整个智能物流分拣系统的大脑，负责接收用户输入指令，调度AGV执行任务，规划AGV的路径，监控AGV的状态，从而完成相应的分拣任务；而“AGV小车”则是实际任务的执行者，其接收调度系统的任务指令，完成相应的任务，并避免相互之间的碰撞。

调度系统为了控制所有的AGV，它们之间需要相互通信。由于AGV小车需要在工厂里行驶，故只能选择无线通信，再通过考虑通信成本和便捷性，最终选择UDP无线网络通信；通过将它们的网络IP地址设置在同一个IP网段内，使用无线wifi信号连接到路由器，从而实现相互间的通信。故每一台AGV小车在硬件上都要安装无线通讯模块，以便连接wifi信号。

AGV的导航方式的选择也是很重要的，目前主流的导航方式包括电磁导航、磁带导航、视觉导航、激光导航。本文选择的是磁带导航，磁带导航是通过在路面的固定路径上贴磁带，通过AGV上的磁带传感器来感应磁带信号，从而实现AGV在固定的路径上行走；并在固定的位置上放置RFID(射频识别)芯片，通过AGV上的RFID传感器读取RFID信号，从而使AGV知道自己到达哪个位置。

整个系统的硬件框架如图2所示，用户可以使用PC、平板和手机等等访问运行在服务器上的调度系统，查看整个系统的运行情况，并给系统安排新的任务。调度系统会根据相应的算法，计算出每台AGV执行的路线，并将该路线通过UDP报文下发给AGV，AGV收到报文后，将开始沿着磁带执行搬运任务，并周期性上报自身的运行状态。

图2 硬件架构

3 软件架构

AGV调度系统是整个物流分拣系统的大脑，经过在工厂的长期实践，总结出调度系统需要具备以下功能：

1)智能调度算法。该算法具备多AGV任务分配、路径规划等功能，并能够使处于低电量的AGV能够自动去充电；使处于空闲状态的AGV，自动回待命区。

2)最短路径规划算法。该算法使AGV选择最短的路径达到目的点。

3)多AGV之间的避障算法。该算法避免了AGV之间的碰撞和死锁。

以下按照这3大模块分别介绍。

3.1 智能调度算法

智能调度算法是调度系统的核心算法，该算法是根据当前任务的情况和所有AGV小车的状态，来决定安排哪一辆AGV去执行这个任务，从而将系统中的任务全部完成，保证整个分拣系统能高效率完成所有的分拣任务。算法主要包括以下3个部分。

3.1.1 设置AGV的多个状态

为了能完成调度系统对AGV的调度，并完成“自动充电”和“自动回待命区的功能”等等的功能，首先需要给AGV定义几个状态，并让这些状态在满足一定条件下能切换。AGV状态转换图如图3所示，该图定义了AGV的5个状态，每当AGV在一个状态下满足了相应的条件后，将自动切换到下一个状态。

图3 AGV状态转换图

3.1.2 系统的任务输入算法

系统的任务输入是由机械手从传送带上抓取物品，然后扫描物品上的二维码，从而获取该件物品要送到哪个目的地；调度系统得到这个目的地后，将产生一个个分拣任务。并将这些任务依次加入系统的“任务队列”中。之所以选择数据结构“队列”是因为“队列”具有“先进先出”特点，即最早产生的任务，将最早被执行。生成分拣任务的整个步骤流程图如图4所示。

图4 输入任务流程图

3.1.3 系统的任务执行算法

接着系统将从“任务队列”中按照时间的先后顺序，即队列“先进先出”的特点，依次取出任务；并查询空闲且距离任务点最近的AGV，安排其至起始点，装载这件物品去目的地，从而完成这个分拣任务。

图5 调度AGV执行任务流程图

3.2 最短路径规划模块

最短路径规划，是指调度系统需要为将要执行该任务的AGV，计算出它从自身的起点到任务的终点在地图中最短的一条路径，并将该路径的数据通过UDP网络报文发送给该AGV。从而使AGV能够沿着最短路径行驶，提高运输效率。调度系统下发的路径信息包括路径中所有的节点信息和转弯信息，从而保证 AGV 能够沿着正确的路径行驶[6]。本文采用的最短路径算法是Dijkstra算法。Dijkstra算法是解决最短路径非常有效的办法[7],该算法由荷兰科学家Dijkstra提出,解决了有向图最短路径问题,该算法的特点是要求所有边的权重都为非负值,并在算法的搜索过程中,会以起始点为中心层层向外扩展搜索,直到搜索到目标节点为止[8]。

3.3 多AGV之间的避障算法

近年来，AGV的动态避障成为移动机器人研究领域的重点内容。要在动态环境下进行AGV路径规划，对实时性要求非常高，同时需要深入了解AGV的避障策略[9]。由于整个物流分拣系统包含多台AGV同时执行任务，如果系统设计的不合理，则将导致正在执行任务的多台AGV发生碰撞，这是绝对禁止的；首先AGV之间的相互碰撞会让AGV产生设备上的的损坏；其次碰撞的AGV将无法移动，会一直呆在原地，从而造成了严重的交通堵塞，其他正在工作的AGV将无法通过该路段，最终造成了整个系统的崩溃。为了使AGV工作的时候避免发生碰撞，本文采取下面2条规则来解决这个问题：

1)单向行驶路径：参照实际的交通线路，工厂地图的路径采取单向行驶线路，即AGV只能朝一个方向行驶，从而避免了多台AGV相向行驶的情况，既避免的AGV之间的碰撞，又提高了执行任务的效率。

2)AGV小车前部安装避障传感器：采取单向行驶路径，虽然可以避免AGV相向行驶的情况，但也无法避免AGV之间同向的碰撞，即多台AGV朝同一个方向行驶，由于速度不同，导致后面的AGV撞击前面的AGV；通过在AGV前部安装避障传感器，当AGV的避障传感器检测到前面有另一台AGV的时候，会自动停下来，从而避免了AGV之间同向的碰撞。

3.4 调度系统与多AGV的通信

服务器与AGV通信采用UDP协议，实现服务器控制和监控AGV的目的；UDP是一种无连接的、不可靠的传输层协议，虽然UDP提供不可靠的数据传输服务，但可以减少系统资源消耗，提高反应速度，效率较高[10]。

服务器与AGV通信之间的UDP协议，一共包括2种类型的报文，即“设置报文”和“查询报文”，这2帧报文都是服务器主动发送给AGV的，AGV不主动发送报文。其中“设置报文”是服务器要给AGV发送任务的时候，才发送的；而“查询报文”是服务器周期性给AGV发送的，发送周期是1 s，即每隔1 s就查询一次AGV的位置、状态、电量等等参数。下面将分别介绍。

3.4.1 设置报文

设置报文是调度系统给AGV安排任务后，将执行任务的路径信息发送给AGV，即告诉AGV怎么走，从而来完成相应的搬运、充电等等的任务，报文的主要内容就是路线上的多个RFID点号和相应的行驶角度。

服务器给AGV发送的设置报文结构如表1所示，表格的第一行是报文的内容，通常由多个部分组成，表格的第2行是每一部分占用的字节数，其他报文的结构组成与它都是相似的。

表1 设置报文

表1中的数据内容结构如表2所示。表格中的任务类型:数字1—取货任务；数字2—送货任务；数字3—充电任务；数字4—回等待区；数字5—中途取消任务。

表2 数据内容结构

表2中的路线点数据内容的单个结构如表3所示，一共7个字节，一共N个这个的结构。表格中的角度:数字0—0度；数字1—90度；数字2—180度；数字3—270度。

表3 路线点数据内容结构

AGV回复服务器报文的结构如表4所示。表格中的回复内容：成功：0x01，失败：0x02。

表4 AGV回复报文结构

3.4.2 监控报文

为了实现对所有AGV的监控，查询报文是服务器周期性给AGV发送的，即每隔1s就查询一次AGV的坐标、当前的RFID点、距离上一个的RFID的距离、AGV 任务类型、AGV 任务状态、AGV 当前速度、AGV 当前电量等等。

1)服务器发送给AGV的查询报文结构如表5所示。

表5 查询报文结构

2)AGV回复报文的结构如表6所示。

表6 AGV回复报文结构

3)数据内容的单个结构如表7所示。

表7 数据内容结构

表格中的AGV任务状态：0—未接受任务；1—正在做；2—完成。

3.5 软件模块划分

为了使分拣系统的调度系统，具备多个用户同时使用的功能，AGV调度系统采用B/S(浏览器/服务器)架构模式，以实现集中式的管理，并采用C#语言实现了整个调度系统的编码工作。通过总结整套调度系统的功能，从软件层面上，将该套调度系统划分为以下5大模块：

1)调度系统获取机械手输入新任务的模块。

2)调度系统通过智能调度算法，调度AGV执行任务的模块。

3)所有AGV执行分拣工作模块。

4)调度系统向所有AGV发送UDP报文的模块。

5)调度系统接收所有AGV返回UDP报文模块。

为了提升调度系统的响应速度，将上述5个功能模块都放在5个单独的线程中并行执行，从而大大缩短系统的反应时间，提高整个系统的调度效率，系统的5个线程如图6所示。

图6 调度系统的5个线程

4 结论

本文主要从系统设计的目标、系统硬件架构和系统软件架构3个方面进行了介绍；在系统的软件架构中，最重要的是智能调度算法，本文将该算法的几个关键点采用流程图的方式表达出来了；另外为了提高系统的运行效率，AGV的移动采用了Dijkstra最短路径算法；此外本文提出的2条规则，可以保证AGV不发生相互碰撞；为了使该分拣系统，具备多个用户同时使用的功能，采用了B/S(浏览器/服务器)架构模式；最后本文采用了C#编程语言实现了整个调度系统的编码工作；经过在工厂一段时间的试运行，实践结果表明，该套系统的设计能够完成多台AGV的调度，并较大地提高了物流分拣的效率。