沈秋英

[提要] 多轨道交互式的AGV生产系统存在多个工作台、多个AGV和多条运行轨道，生产过程中的各种信息实时进行交互。每个AGV在运行过程当中根据即时的系统状态选择当前的工作任务和运行路线。系统的复杂性和AGV决策的即时性使得难以预先将AGV的数量和工作任务进行合理的匹配。本文采用多Agent仿真理论对多轨道交互式AGV调度系统进行仿真模拟，可以预先模拟系统运行状态，从而将工作任务和AGV的数量进行合理匹配。该方法可以在一定的工作任务下预先确定需要的AGV数量，也可以在一定的AGV数量下确定能够承担的最大工作任务，同时还可以在一定的AGV数量和工作任务下，预先确定需要的工作时间。

关键词：多主体仿真;AGV;任务;匹配

中图分类号：F27 文献标识码：A

收录日期：2018年3月28日

一、引言

无人搬运车（简称AGV）是装备有电磁或光学等自动引导装置，能够沿规定的引导路径行进，具有安全保护以及各种移载功能的运输车辆。AGV在工业应用中不需要驾驶员，以可充电的蓄电池作为其动力来源，透过计算机系统来控制其行進路线和行为。通常利用电磁轨道来设立AGV的行进路线。电磁轨道贴在地板上，AGV则依循电磁轨道所带来的信息进行移动与动作。目前，AGV系统在电子、钢铁、食品等行业有较为广泛的应用。AGV系统与其他的物流输送系统相比，具有环境的适应性强、布局柔性高、方便维护、自动化程度高、便于维护等优点，对提高生产效率、降低生产成本从而加速企业发展有着重要意义。

单台AGV的简单系统的活动范围和作业能力是有限的，随着工厂自动化规模日益扩大，已不能满足提高自动化系统生产效率的要求。目前，AGV系统大都是由多台AGV构成的多轨道、交互式系统。在这类系统中，多个AGV在同一时间和空间内同时运行，形成了一个离散事件的动态系统，进而导致了一系列的管理难题。目前对AGV系统的研究主要集中在路经规划、任务调度和冲突处理三个方面。文献建立了单机器人多工作站的制造系统调度模型，并开发了相应的多项式算法。文献建立了多机器人多工作站的制造系统调度模型，并开发了相应的多项式算法，但是没有考虑机器人的碰撞问题。文献开发了两机器人制造单元调度问题的有效算法，但该方法无法解决超过两个机器人的调度问题。这些研究都是针对系统某一方面的问题展开，然而由于系统的复杂性、离散性和即时性，系统的总体特征规律尚难以获取。因此，现有研究尚未解决AGV的数量和工作任务的匹配问题。即对于特定系统，在一定的工作任务下达后，需要多少台AGV可以按时完成任务;或在一定的AVG数量和工作时间要求下，最多能够完成多少工作任务。上述问题的存在给企业生产计划的制定带来很大困难。同时，由于AGV价格昂贵，购置多余的AGV也给企业增加了大量的生产成本。

本文根据多轨道、交互式AGV生产调度系统所具有的复杂性、离散性和决策的即时性等特点，提出采用多Agent仿真理论对多轨道交互式AGV调度系统进行仿真模拟，通过在特定的系统参数下模拟系统运行状态，获取特定系统状态下工作任务、AGV数量和总工作室间等变量之间的相互关系，从而实现将工作任务和AGV的数量进行合理匹配。采用这一方法可以在一定的工作任务下预先确定需要的AGV数量，也可以在一定的AGV数量下确定能够承担的最大工作任务，同时还可以在一定的AGV数量和工作任务下，预先确定需要的工作时间。经过现场的实际工程实施，表明该方法稳定可靠、实施简便，AGV生产调度系统的设计和实施方面效果明显。

二、多轨道、交互式AGV生产调度系统描述

多轨道、交互式AGV生产调度系统通常由一系列固定装置和多台AGV构成。其中，固定装置一般包括一个装载台、一个卸载台、多个工作台和多个AGV等待区，上述四类装置之间有固定的电磁轨道相连。生产任务启动后，由AGV将装载台上存放的待加工工件运送到不同的工作台进行加工。各个工作台的加工时间已知;同一个工件不能同时被两个或多个工作台同时加工，一个工作台也不能同时加工超过额定数量的工件。工件在工作台上完成加工后，由AGV将其运送至卸载台进行存放。系统中的多台AGV可同时运行在预先设定的电磁轨道上，专门负责工件在生产过程中的搬运作业，它们之间在运行过程中不能碰撞;每一个特定搬运工作只能由一个AGV执行，同一个AGV在同一时刻只能完成一项搬运任务。

系统通过扫描装载台和工作台的状态来触发任务。首先扫描装载台的状态，当装载台不为空时，系统记录装载台上的工件种类和数量，然后扫描相应的工作台是否空闲。如果没有空闲的工作台，则进行等待;如果有相应的空闲工作台，系统计算所有AGV完成现有任务，然后到装载台装载待加工工件并将其运送到相应工作台的最短路线和所需要的最短时间。然后将任务指派给所需时间最短的AGV。当工作台不为空，且完成加工作业时，系统计算所有AGV完成现有任务，然后到工作台装载完成加工的工件，并将其运送至卸载台所需的最短路线和对应的最短时间，将任务指派给所需时间最短的AGV。AGV沿着地面上铺设的电磁轨道运行，电磁轨道既有单向路段又有双向路段。AGV完成搬运作业后，如未接到新的指令，则运行至最近的AGV等待区进行等待。当所有工件都完成加工并运送到卸载台时，工作任务完成。

三、基于多Agent仿真的多轨道、交互式AGV调度系统建模

本文采用多Agent仿真理论对多轨道、交互式AGV生产调度系统进行仿真模拟，通过在特定的系统参数下模拟系统运行状态，获取特定系统状态下工作任务、AGV数量和总工作室间等变量之间的相互关系，从而实现将工作任务和AGV的数量进行合理匹配的目的。本文建模过程主要包括四个步骤：（1）对AGV生产调度系统的设施布局进行测量，获取系统内部各装置的具体信息;（2）采用多Agent仿真理论，根据步骤（1）测量获取的数据，建立AGV调度系统仿真模型，模拟生产过程中各装置的位置和AGV的运行规则;（3）对任意生产任务，运行步骤（2）所建立的仿真模型，得到不同AGV数量下完成该生产任务所需的工作时间。根据获得的数据，得到生产任务、AGV数量和工作时间的匹配关系。必要时重复运行多次，得到三者之间的统计规律;（4）根据步骤（3）所获得的规律，将工作任务和AGV数量进行匹配。

（一）系统固定装置及其布局的测量。系统的固定装置主要包括一个装载台、一个卸载台、多个工作台、多个AGV等待区以及连接这些固定装置的电磁轨道。另外，系统还包括多个可移动的AGV。对系统进行测量需要获取的数据包括以下几类：第一，装载台、卸载台、工作台、AGV等待区等固定装置两两之间的电磁轨道长度;第二，AGV在装载台、卸载台、工作台进行装载、卸载工作需要的时间和每个工作台的加工时间;第三，AGV的运行速度和遇到障碍物时进行规避的反应时间。

（二）仿真模型的建立。根据上一步测量所获得的数据，采用多Agent仿真方法对AGV生产调度系统进行建模，对系统的运行过程进行模拟。建模的过程分为以下几步：

第一，根据装载台、卸载台、工作台、AGV等待区、电磁轨道等固定装置的相对位置，在系统中生成工作场所的模拟环境。

第二，生成一定數量的AGV，并为AGV设定运行规则。

对于任意空闲的AGV，当接到指令将一定数量的工件从固定装置A运送到固定装置B时，所采取的行动规则如下：（1）路线计算。AGV计算自身位置到固定装置A的最短路线，以及固定装置A到固定装置B的最短路线。（2）移动、装载与卸载。AGV根据步骤（1）的计算结果，首先由自身位置运动到固定装置A，然后进行装载作业;装载完成后，再由固定装置A移动到固定装置B，然后进行卸载作业。

对于任意空闲的AGV，当没有接到工作指令且不在等待区时，所采取的行动规则如下：（1）路线计算。AGV计算自身位置到所有可用等待区的最短路线;（2）移动到等待区。AGV根据步骤（1）计算出的计算结果，移动到距离最近的等待区进行等待。

根据上述运行规则可得到AGV状态跃迁图如1所示。（图1）

第三，建立系统的任务分配机制。系统任务由两种装置触发，一个是装载台，一个是工作台。当装载台或任意一台工作台不为空时，即触发任务分配机制。系统任务分配机制流程图如图2所示。（图2）

装载台的任务触发机制如下：（1）当装载台的状态不为空时，装载台首先根据工件种类对工作台进行匹配，然后在匹配的工作台中搜寻是否有空闲的工作台;如果有空闲的工作台，则进入对AGV的选择和任务指派程序。如果没有空闲的工作台，则等待匹配工作台完成加工作业。（2）AGV的选择和任务指派。计算当前没有作业的每一个AGV到装载台装载工件并运送到每一个工作台的最短路径及相应的作业时间。将作业任务指派给相应作业时间最短的AGV，并给该AGV发送指令。

工作台的任务触发机制如下：（1）当工作台状态不为空，且已完成加工作业时，进入AGV的选择和任务指派程序;（2）AGV的选择和任务指派。计算当前没有作业任务的每一个AGV移动到相应工作台装载工件，并将工件运送到卸载台的最短路径及相应的作业时间。将作业任务指派给相应作业时间最短的AGV，并给该AGV发送指令。

根据上述规则得到工作台状态跃迁图，如3所示。（图3）

第四，建立AGV免碰撞机制。在多AGV任务调度系统中，往往存在着AGV之间的冲突问题，如何避免AGV之间的碰撞是多AGV任务调度的重要组成部分。AGV的碰撞问题通常可以分为节点冲突和相向冲突两类。节点冲突为两个及两个以上AGV同时通过一个节点时产生的冲突问题。相向冲突为某个AGV占据其他AGV的运行路线或目标节点时产生的冲突问题。两类冲突示意图如图4所示。（图4）

为避免相撞，本文设定AGV在移动过程中，实时对沿轨道向前延伸2米处所有可能通路的占用情况进行探测。如轨道被占用，则停止移动并等待3～5秒后继续向前运动。为防止两个以上AGV的相互等待陷入死循环，等待时间为3～5秒之间的一个随机数。

（三）仿真结果的获取。本文采用仿真软件Netlogo实现对上述模型的编程工作。然后在不同的生产任务和AGV数量下反复运行上述模型，得到生产任务、AGV数量和完成生产任务所需时间的相互关系。设所需加工的工件数量为N，AGV数量为n，完成生产任务所需的平均时间为T（N，n），将反复运行上述模型得到的数据列入表1。（表1）

（四）AGV数量与工作任务匹配。根据表1所得到的生产任务、AGV数量和总的生产时间之间的相互关系，对生产任务和AGV数量进行匹配。通过三者之间的匹配可以分别对生产任务安排、AGV数量需求和生产时间安排三个方面做出相应决策，具体如下：第一，当AGV数量为n，所需加工的工件数量为N时，通过查表得到完成该生产任务所需的时间为T（N，n）。将时间单位换算为小时（下同）。然后，根据每天工作的小时数，即可得到完成该生产任务所需的天数。如每天工作8小时，则所需工作天数位T（N，n）/8;第二，当AGV数量为n，可供完成生产任务的时间限制为T（N，n）时，通过查表可得到最多能够加工的工件数目N;第三，当在一定的时间限制T（N，n）下，所需加工的工件数为N时，通过查表可得到所需要的AGV个数n。

四、应用实例

选择江苏省电力科学研究院计量中心计量资产自动检测系统作为实施对象。国家电网江苏省计量中心拥有全国规模最大的自动化检定线，年检定单相电能表800万只，三向电能表80万只。检定过程如下：自动化库房与检定区的接驳区共6个接驳位。待检定的电能表由自动化库房运送到接驳位，然后由AGV将电能表从检定区接驳处输送到检定台体，机械臂完成取表、定位、挂表，检定台完成检定任务后，由AGV将电能表输送回接驳处，送至负一楼自动化封印线进行分拣。AGV的运行路线由地面固定的多条电磁轨道进行导引。该检定系统为典型的多轨道交互式AGV调度系统。通过实地测量得到该系统的AGV工作环境模拟图如图5所示。（图5）

其中，蓝色长条为检定台;黄线为AGV运行的有向电磁轨道;白色方格为进货口和出货口。本实例实施步骤如下：

（一）本实例中，装载台和卸载台均为接驳区，工作台为4个电能表检定台，另外系统还有4个AGV等待区，以及一个将这些固定装置连在一起的一个电磁轨道系统。电磁轨道系统为2条主轨道和3条将主轨道连在一起的分轨道。其中，主轨道为单项轨道，分轨道为双向轨道。对上述各固定装置进行测量后得到两两之间的电磁轨道长度如表2所示。（表2）

AGV在接驳处进行装载和卸载所需要的时间为每次3秒，在检定台进行装载和卸载所需要的时间为每次9秒，每个检定台的检定时间为180秒。AGV的运动速度为3m/s，遇到障碍物时停车等待的时间为3～5秒之间均匀分布的一个随机数。

（二）根据接驳处、检定台、AGV等待区、电子軌道等固定装置的相对位置，在系统中生成工作场所的模拟环境。生成12个AGV，并为AGV设定运行规则如下：

对于任意空闲的AGV，当接到指令将一定数量的工件从固定装置A运送到固定装置B时，所采取的行动规则如下：（1）路线计算。AGV计算自身位置到固定装置A的最短路线，以及固定装置A到固定装置B的最短路线。（2）移动、装载与卸载。AGV根据步骤1的计算结果，首先由自身位置运动到固定装置A，然后进行装载作业;装载完成后，再由固定装置A移动到固定装置B，然后进行卸载作业。（3）规避碰撞。AGV在移动过程中，实时对沿轨道向前延伸2米处所有可能通路的占用情况进行探测。如轨道被占用，则停止移动并等待3～5秒后进行继续向前运动。为防止两个以上AGV的相互等待陷入死循环，等待时间为3～5秒之间的一个随机数。

对于任意空闲的AGV，当没有接到工作指令且不在等待区时，所采取的行动规则如下：（1）路线计算。AGV计算自身位置到所有可用等待区的最短路线;（2）移动到等待区。AGV根据步骤1计算出的计算结果，移动到距离最近的等待区进行等待。

（三）建立系统的任务分配机制。系统任务由两种装置触发，一个是接驳区与自动化库房的接驳位，一个是检定台。当接驳区与自动化库房的接驳位或任意一台检定台不为空时，即触发任务分配机制。

接驳区与自动化库房的接驳位的任务触发机制如下：（1）当接驳区与自动化库房的接驳位的状态不为空时，接驳区与自动化库房的接驳位首先根据工件种类对检定台进行匹配，然后在匹配的检定台中搜寻是否有空闲的检定台;如果有空闲的检定台，则进入对AGV的选择和任务指派程序。如果没有空闲的检定台，则等待匹配检定台完成加工作业。（2）AGV的选择和任务指派。计算当前没有作业的每一个AGV到接驳区与自动化库房的接驳位装载工件并运送到每一个检定台的最短路径及相应的作业时间。将作业任务指派给相应作业时间最短的AGV，并给该AGV发送指令。

检定台的任务触发机制如下：（1）当检定台状态不为空，且已完成加工作业时，进入AGV的选择和任务指派程序;（2）AGV的选择和任务指派。计算当前没有作业任务的每一个AGV移动到相应检定台装载工件，并将工件运送到自动化封印线的接驳处的最短路径及相应的作业时间。将作业任务指派给相应作业时间最短的AGV，并给该AGV发送指令。

（四）采用仿真软件Netlogo实现对上述模型的编程工作。然后在不同的电能表检定任务和AGV数量下反复运行上述模型，得到检定任务、AGV数量和完成检定任务所需时间的相互关系如表3所示。（表3）

（五）根据表3所得到的检定任务、AGV数量和总的生产时间之间的相互关系，对检定任务和AGV数量进行匹配。

通过上述方法，至今已经完成了3次对电能表检测任务与AGV数量的匹配工作。第一次检定任务为80万只，任务期限为1个月，按照每月4周，每周5天工作制，平均每天需要检定的任务为4万只。通过查找表3可得，需要的AGV数量为最少11个。第二次鉴定任务为20万只，可用AGV数量为8个，通过查找表3可知，需要的工作时间为8.5个工作日。第三次检定任务为50万只，可用AGV数量为12个，检定任务的时间要求为10天，查找表3可知，50万只电能表在12个AGV的情况下，工作时间需要11天，故对检定任务进行了修改，降低为40万只，此时所需的工作时间为9天。通过查表3可知，如果在10天的检定任务要求下完成相应工作任务需要12台AGV，因此也可购进1台新AGV来满足检定任务要求。

五、总结

本文提出了采用多Agent仿真方法建立了多轨道、交互式AGV生产调度系统的仿真模型，对系统运行过程进行模拟，并由此对AGV数量及工作任务进行匹配的方法。本文的多轨道、交互式AGV调度系统仿真模型根据对AGV生产调度系统的设施布局进行测量得到具体信息建立，将每个AGV看作独立决策的离散单元，在系统运行的过程中每个AGV按照自己的行动规则做出行动决策，从而总是可以为系统找出至少一个可行解。通过模拟系统运行的整个过程，最终能够得出工作任务、机器人数量和工作时间之间的相互关系。采用拥有1个装载台、1个卸载台、4个工作台、4个AGV等待区以及一个由两条主轨道和3条分轨道构成的电磁轨道构成的计量资产检定系统对本文提出的方法进行了验证，证明了本方法的实用性和有效性。

主要参考文献：

[1]CHE A，CHU C B，L EVNER E.A polynomial algorithm for 2-degree cyclic robot scheduling[J].European Journal of Operational Research，2003.145（1）.

[2]CHU C B.A faster polynomial algorithm for 22cyclic robotic scheduling[J].Journal of Scheduling，2006.9（5）.

[3]CHE A，CHU C B，CHU F.Multi-cyclic hoist scheduling with constant processing times[J].IEEE Transactions on Robotics and Automation，2002.18（1）.

[4]DAWANDE M，GEISMAR H N，SETHI S P，et al.Sequencing and scheduling in robotic cells：recent developments[J].Journal of Scheduling，2005.8（5）.

[5]AGNETIS A.Scheduling no-wait robotic cells with two and three machines[J].European Journal of Operational Research，2000.123（2）.