面向混流生产的异构AGV调度控制系统开发

翟晶晶，武 星，杨俊杰，胡 亚,2，楼佩煌，肖海宁

(1.南京航空航天大学机电学院，江苏 南京 210016)(2.天奇自动化工程股份有限公司，江苏 无锡 214187)(3.盐城工学院机械工程学院，江苏 盐城 224051)

随着科技的发展和用户需求的多样化，制造模式已经由传统少品种大批量的刚性制造模式转变为适应个性化、多样化的柔性制造模式。据有关统计，在整个柔性制造过程中有大约95%的时间是用在存储、装卸、搬运和等待加工等物流环节上，工序物流的运行效率直接影响着车间生产活动的有序进行[1]。自动导引车(automated guided vehicle, AGV)是一种最具代表性的物流输送机器人，而由多台AGV构成的AGV系统作为一种灵活高效的物流系统，在制造系统、仓储配送系统等领域有着广泛的应用[2-3]。根据AGV可同时执行配送任务数的不同，可将AGV分为单载量AGV[4]及多载量AGV[5]。单载量AGV在一次搬运作业中只能进行一次装载和卸载，适合大件或半成品的运输；相对于传统的每次装卸一次载荷的单载量AGV，多载量AGV可在一次物料配送任务中，分别从多个发料点进行多个载荷的装载，或到多个送料点进行多个载荷的卸载，具有更高的单车运输能力和更强的配送作业柔性。

混流生产作为柔性生产的代表，具有物料种类多、配送要求差异性大、作业协调性要求高[6-9]的特点，对调度系统的调度性能和准时率提出了更高要求，传统的单载量AGV运输已经无法满足要求。针对该问题，本文采用单载量AGV和多载量AGV共同进行物料配送，建立了异构AGV调度控制系统。

1 总体方案

1.1 研究方案

针对传统配送准时性差的问题，考虑到装配工位物料种类多、配送要求差异性大的实际需求，本文设计了一种以异构AGV为对象的调度控制软件。该软件具有友好的人机交互界面，内含电子地图数据，具有任务调度、交通管控、路径规划、状态监控、统计分析等功能，能够直观地对AGV运行状态、任务和设备状态进行实时监控。其物料配送作业流程为：系统接收、统计来自叫料器的任务信息，根据任务的优先级进行排序，并依据AGV的位置和状态高效地将任务派发给最佳AGV；然后采用路径规划算法为执行任务的AGV安排行驶路径，并在AGV行驶过程中进行交通管控以解决路径冲突，从而完成物料配送任务。如上所述，系统中的任务调度、路径规划和交通管控部分是整个调度控制系统的核心部分，也是本文的研究重点。本文利用Qt开发框架对系统功能进行了软件开发，实现了调度控制的整体作业流程。

1.2 AGV调度控制系统构成

根据典型复杂产品生产车间的问题分析和系统功能需求，本文设计的AGV调度控制系统主要由上位机管理系统、AGV车辆、导引路径及辅助设备等部分组成。其中，上位机是一台装有AGV调度系统软件的计算机，是整个调度系统的核心。而AGV车辆负责物料的配送任务，其在行驶过程中需通过通信传输系统实时反馈自身的位置和状态信息，以便上位机能实时监控，是执行任务的主体。除此之外，辅助设备也是AGV调度系统正常运行不可或缺的部分，如交换机、无线接入点、定位标识(RFID识别卡)、充电桩、叫料器等。

2 调度控制系统核心技术

在AGV调度控制系统中，为了保证多台AGV在同一工作空间中有序运行，任务调度[10]、路径规划[11]和交通管控[12]是三项核心的AGV系统级使能技术。

2.1 任务调度

任务调度的主要研究内容是当系统中存在多个物料配送任务及空闲 AGV 时，在满足一定的约束条件下，为了使系统的某项或某几项性能达到最优，确定各物料配送任务执行的先后关系及其与空闲AGV 的分配关系。在本文设计的调度系统中，任务调度流程图如图1所示。当任务调度系统按周期触发时，将任务池的任务分为单载量任务集和多载量任务集，若单载量任务集、AGV集或多载量任务集、AGV集不为空，系统按照任务分类和AGV类别进行物料配送任务执行的先后关系和空闲AGV分配，完成后更新系统状态等待下一触发周期。其中，物料配送任务执行的先后关系由任务的紧迫度决定，即每个任务都有一个交付时间。将交付时间进行排序，当前时间距离交付时间越近的任务，其紧迫度越高，则需优先分配空闲AGV进行搬运。空闲AGV的分配原则为任务最早完工时间原则，即优先选取该任务预测完工时间最早的空闲AGV，完工时间预测与空闲AGV的空载距离、搬运距离、搬运速度、路径交通流、多载量AGV的容量、多载量AGV已分配任务等因素有关。

2.2 路径规划

AGV调度控制系统路径规划的主要研究内容是在指定的AGV运行环境中搜索一条从起始点到目标点的最优或近似最优的路径，使系统的某项或某几项性能达到最优或者近似最优。常用的路径规划算法有模拟退火法、A*算法、Dijkstra算法、人工势场法、Floyd算法等[13]，其中，Floyd算法采用三重循环紧凑结构，相对于其他算法，不需要设定相应的参数和估计函数，效率更高。因此，在本文设计的调度系统中采用Floyd算法计算任务的起点到终点的最短距离和路径序列，完成路径规划。Floyd算法需要建立两个n×n(n为节点总数)的矩阵, 记为D和P。矩阵D中的元素a[i][j](1≤i≤n，1≤j≤n)表示从顶点i到顶点j的距离，若两点之间没有直接连接，则距离为∞；而矩阵P中的元素b[i][j]则表示从顶点i到顶点j中间经过的顶点, 初始状态下为b[i][j]元素的j值，算法流程图如图2所示。

图1 任务调度流程图

图2 Floyd算法流程图

2.3 交通管控

AGV调度控制系统的交通管控侧重于解决多台AGV并发运行时可能产生的运动冲突、碰撞。在单向导引路径网络中，AGV系统可能存在4种发生碰撞的运动冲突，如图3所示。

图3 异构AGV的典型运动冲突

针对这4种冲突，本文调度系统中采用的解决方案如下：

1)针对图3(a)中的路径点冲突，需AGV1提前减速直至停车，待AGV2开始运动时，AGV1重新启动继续运行。若AGV2因故障长时间滞留在行驶路径上而导致路径被占用，就会变成不可解决的冲突，此类冲突通常需要人工干预才能顺利排除。

2)针对图3(b)中的AGV转向空间冲突，由于多载量AGV的变长特性，若两条导引路径相距较近，AGV转向时可能会产生碰撞。因此当某一时间段有两辆AGV分别进入两条相距较近的导引路径时，系统基于两辆AGV的长度进行冲突判断，若不会发生转向空间冲突，则允许两辆AGV同时进入对应路径；否则，需在两条路径上设置虚拟加锁点，当其中一条路径AGV进入路口后，另一条路径加锁点加锁，阻止其他AGV进入。当AGV离开出口点时，触发解锁点的解锁信号，对加锁点进行解锁。

3)针对图3(c)中的路径空间冲突，即AGV1由于即将进入的路径段无剩余空间而占用交叉路口，进而阻碍AGV4的通行。对于变长型异构AGV系统，在AGV通过交叉路口进入目标路径之前，必须检测该路径是否有足够的剩余长度，如果足够，则允许该AGV进入目标路径，否则AGV将在路口等待。

4)针对图3(d)中的交叉路口冲突，可以将所有请求进入其中的AGV组成AGV等待队列，并根据任务紧迫度和路径段交通流计算等待队列中所有AGV的综合竞标价，其中竞标价最高的获标AGV获得该路口的优先通行权。通过此方法可以优化AGV通过交叉路口的顺序，获得交叉路口AGV通行序列。最后，采用包含加锁点和解锁点的路口互斥机制，控制AGV有序地通过交叉路口。

3 系统功能实现

根据异构AGV调度控制系统的功能需求和作业流程，本文设计的AGV调度控制系统由用户层、功能层和数据层组成，其软件结构如图4所示。其中，用户层及功能层的绝大多数子模块均有图形交互界面，而数据层则是抽象的信息流。

图4 AGV调度系统软件结构图

Qt是一个优秀的跨平台C++图形用户界面应用程序开发框架，能较快捷地搭建用户界面。数据层信息多而分散，且各模块之间需要共享，故采用数据库作为信息的存储方式。MySQL是一种关系型数据库管理系统，关系数据库将数据保存在不同的表中，提高了系统的速度和灵活性。因此，本文基于Qt开发框架和MySQL数据库，采用面向对象的编程方法进行软件开发。

3.1 任务调度模块

任务调度作为调度系统三大核心技术之一，决定着任务的执行顺序与执行对象，直接影响着工位的生产效率。该模块的数据来自新产生任务的数据表，该表存有任务的类型、起点终点的装卸载方式、任务创建时间、交付时间等信息，如图5所示。基于以上信息可计算新任务列表的紧迫度并进行排序，并结合空闲AGV信息和路径信息计算最早完工时间，完成任务分配。其中，任务调度模块类结构中成员变量包含装卸载任务时间、交通系数、自定义地图类、操作数据库类、任务池、任务发布周期等；成员函数包含任务池开启函数、获取紧迫度最高的任务信息函数、搜寻最佳AGV函数、计算任务时间函数、任务发布函数等。

图5 新产生任务的数据表

3.2 路径规划模块

路径规划模块依赖电子地图数据，而电子地图数据是实现通过配套的地图绘制软件进行环境建模，包含路径段、路径端点、工位点等数据信息，最后以XML形式保存。同时，各个交叉点之间的最短距离表和路由表在创建地图时由路径规划算法得到，任务调度模块和路径规划模块可直接从最短距离表和路由表中提取信息，并根据任务的起止工位号，在单向路径上规划理论最佳行驶路径，大大优化路径规划流程，提升软件运行效率。例如：工位0到工位1最短路径如图6所示。

图6 路径规划示意图

3.3 交通管控模块

对于交通管控中的4种运动冲突情形，由于AGV装有避障传感器，可以避免图4(a)的路径点冲突情况，因此系统进行交通管控时主要考虑后3种冲突情形。为保存交叉点加锁状态和路径容量等信息，本文分别创建交叉点结构体与路径结构体，交叉点结构体中包含路径端点编号、加锁状态、占用AGV编号和可读性信息；路径结构体包含路径编号、剩余长度、路径上存在的AGV数量和编号信息。当某AGV经过加锁点时，向AGV调度系统发送请求进入指令，当交叉点未被占用且即将进入路径端剩余长度足够时，调度系统回复通行指令，否则该AGV将停在加锁点，并以固定间隔发布请求进入指令，直至有占用交叉点的AGV解锁该交叉点或下一路径段上的AGV离开下一路径段时，若导致通行条件满足，即交叉点未被占用且即将进入路径端剩余长度足够，则允许停在加锁点的AGV通行。AGV到达解锁点后，解除占用该交叉点，同时更新先前路径与新进入路径的容量信息。若发生多辆AGV同时竞争某交叉点，如图4(d)所示情况，则需要先将所有请求AGV加入队列，然后查看各AGV执行任务信息，最后综合考虑任务紧迫度和路径段交通流，优化路口通行顺序。

3.4 其他模块

除了上述三大模块，系统还包含管理功能模块、状态监控模块、通讯传输模块、统计分析模块，各模块的功能如下：

管理功能模块是人机交互的主要界面，包括用户管理、任务管理、AGV管理，如图7所示。用户管理具有创建、删除账户的功能，同时改变各用户的登录权限，保证系统的安全性和灵活性。同时，任务管理可查看并添加/删除任务，维护正确的任务信息。AGV的添加、删除、系统配置等功能均可在该模块实现。

状态监控包括任务监控、AGV运行状态监控、路径状态监控、物料状态监控。在系统运行过程中，任务和AGV运行状态等信息不断更新，用户在操作过程中必须实时了解这些变化，掌握全局信息，以便应对突发情况并获取目标信息，状态监控模块就是为此设计的。其中，用户界面的表格均与数据库关联，维护数据库表信息即可实时刷新这些表格，并且AGV每个时刻的位置及路径段、交叉点的状态都会同步刷新，且均有相应的图形化界面。

通讯传输模块中，各设备终端均装有串口服务器，通过虚拟串口映射至调度系统主机，调度系统通过读取串口方式获取信息。

图7 管理功能模块界面

调度系统的统计模块以日期为单位进行数据记录与分析，这些数据包含统计准时率、任务个数、AGV利用率等信息。此外，该模块还可根据所选日期范围查看一段时间内某些指标值的变化趋势。

4 调度系统实验

为了测试调度系统的性能，在调度系统软件与异构AGV间进行通信，本文在实验室的环境下模拟生产环境，其实验布置如图8所示。因为路径规划的结果直接可以从路由表得到，所以将主要测试系统的交通管控模块和任务调度模块的性能。

图8 实验室布置图

对于系统的交通管控模块中的冲突，主要是以加解锁点的方式进行控制，所以需要验证加锁点策略的实施效果。以图3(b)中AGV转向空间冲突为例，当不同长度的AGV经过同一个两条相近路径段时，实验结果如图9所示。图9(a)所示为单载量AGV转向空间实验，因为单载量AGV的长度较短，在通过两条相近路径时，不会互相干扰，所以两辆AGV被允许同时进入对应路径；图9(b)所示为多载量AGV转向空间实验，因为多载量AGV为变长型AGV，当AGV进入距离相近路径时，会进行预判，结果表示会发生碰撞，所以后到的AGV在加锁点等待另一路径上的AGV通过。实验结果表明，交通管理模块可以避免AGV之间的冲突。

图9 转向空间冲突实验结果

任务调度模块中的任务由系统的叫料器输入，包括任务的类型、目标工位、产生时间、截止时间等信息。任务将首先添加到未执行列表中，按照任务调度方法对任务进行排序和分配AGV，并将待执行任务添加到执行任务列表中，同时删除未执行任务列表中与此任务有关的记录。为了测试任务调度模块的性能，本文统计了系统中的100个完成任务，执行任务的信息包含任务编号、任务类型、目标工位、物料组号、任务产生时间、任务截止时间、执行编号、执行AGV编号、任务的完成状态、任务完成时间、AGV的载量。完成的100个任务的准时率如图10所示，其中单载量任务数和多载量任务数分别为41和67，准时率分别为100%和97.1%，综合任务准时率为98%，综合停料待产率为1.3%。实验结果表明，本文研发的调度系统具有较高的准时率和效率。

图10 已完成任务准时率统计

5 结束语

对于柔性化的混流生产线而言，系统需快速响应订单的变化，将物料快速准确运输到工位旁，实现企业精益生产。而采用异构AGV可适应不同种物料的配送，在不降低AGV系统整体运输能力的前提下减少AGV数量，有利于减少共享路径网络中的冲突，从而保证整条装配生产线的多种装配物料准时配送。本文以异构AGV为控制对象，利用Qt框架和MySQL数据库开发设计了一种包含基于紧迫度和最早完工时间的任务调度方法、基于Floyd算法的路径规划算法的多种运动冲突解决方案的调度控制系统，实现了调度控制的整体作业流程。