用神经网络方法处理FMS

引言 
            在柔性制造系统(Flexible Manufacturing System,FMS)中最具柔性和发展最快的物料输送系统 之一是自动导向小车系统(Automated Guided Ve— hicleSystem，以下简称AGV系统)。物料输送是制 造过程中的关键活动。物料输送包括物料在生产的 各个阶段的拾取、运送、存储和包装。物料输送的准确及时对于提高FMS的生产效率和降低成本意义重大。 
            一个AGV系统由若干台计算机控制的无人驾 驶小车组成。大部分现有AGV是在计算机调度下 沿导向轨道行驶，虽然其导向方法具有高可靠性，但却降低了AGV系统的柔性。自由分布AGV系统使 用超声波或激光视觉等装置引导小车，使小车可在 车间内自由行驶，从而增加了系统的通用性。
            自由分布AGV系统所碰到的一个主要问题是 小车的调度和控制，需要有效的AGV控制器监测 设备的状态和调节物料的运送，以使得能在适当的 时间将适当的物料送到适当的地点。
             本文论述在FMS中，如何以最有效的方式在 调节时间间隔内处理同时发生的多个请求AGV运 送的情况。探讨了AGV路径规划和分配问题，提出 了相应数学模型，提供了自组织神经网络解决方案 的算法。
1、一般FMS的物流情况 
             对于一般FMS而言，每台机床都是通用的，可实施多种操作。现场备有一个储备库，在线工件(Work—In—Process WIP)需由 AGV从储备库运送到机床。与每台机床相连的是输入缓冲站(1nput Buffer IB)和输出缓冲站(OutputBuffer OB)。当一项操作完成之后，机床会自动地将WIP卸载到OB 并发出运走请求。WIP一直等在OB上直到AGV 来拾取为止。由于缓冲站容量有限，一台机床可能出现“撑死”或“饥饿”现象。“撑死”发生在一台机床要 卸载刚完成的WIP到已经饱和的OB上时，此时，该机床发出紧急运走请求。相应地，“饥饿”则发生在一台机床从已经空了的IB上取下一个加工工件时，此时，该机床发出紧急运来请求。紧急运走请求也会 发生在当储备库中的WIP已到了该对其实施操作时。
              除了紧急运走、紧急运来请求外，WIP运送请 求还包括一般运走与运来请求。当任何一台机床其 IB空了时，则发出运来请求，当一工件从储备库或上位机床运来并传送到IB上后，该运来请求就被满 足了。而运走请求的满足是在从OB运走了WIP之后。
2、AGV路径规划和分配问题
2.1、问题的特征及解决方法 
                每一个AGV运送请求都涉及到两个任务，即从一起始点拾取WIP，将其运送至一预先确定的送达点卸下。任务优先关系要求先拾取后运送WIP，而拾取运送任务必须由同一台AGV完成。在本研究背景下，一台AGV一次只承载一个单位负荷，所谓一个单位负荷是指作为一个整体被夹持和传输的工件的集合。例如，一个装有几个工件的托盘[1]。因此，AGV在载有一个单位负荷去送达点途中再拾取另一个WIP是不允许的。
                与传统的执行单一运送请求而寻找最短路线的AGV规划问题不同[2]，本研究寻找最短路径涉及到的是执行多项运送请求而不是一项。由于在自由分布AGV环境下，起始点到送达点间的最短路线变为欧氏距离。因此传统的方法不再适用，本研究致力于用神经网络方法来解决问题。
以下先阐述所开发系统的特点：
(1)系统每接受到一个运送请求时，都会进行规划演算，立即分配一项AGV任务，以达到实时性要求；
(2)进行规划演算时，将所有新的运送请求和所有系统内还未被AGV拾取的WIP一起考虑，重新进行规划。一般情况下，按先申请先享受服务的规划 处理优先次序。但也考虑根据当前系统状态，原先的一般请求可能变成紧急请求，而紧急请求具有高优先权；
(3)由于存在机床输入和输出缓冲站，并无必要在发出一般运送请求后立即将WIP运走。当一般运送请求发出时机床正在忙于下一工件的加工，因此，即使规划演算开始于运送请求产生之后，机床的利用率并没有受影响。
除以上所述之外，还有其他一些AGV系统问题需要解决。其中最重要的是车间内的交通管理问 题。当无人驾驶小车遇到障碍物时需要避让，当小车之间发生路线冲突时，需要冲突解决方法。通常设计一些控制区或缓冲区用于发生冲突时让小车暂时避让。为避免交通堵塞和小车干涉，文献[2]提出了一些冲突解决方法，有几何方法，if—then—else产生式 规则方法以及先到先服务规则(thefirst—comefirst— serve rule)方法。在本研究的自由分布AGV系统中，目标之一是确定每台AGV的最短路径。当运行 在该路径上的AGV发生交通冲突时，应用先到先服务规则。
2.2 数学模型
                首先将AGV从起始点拾取工件运送到送达点卸下工件定义为一项任务(Job)，则产生如下数学符号含义：
N——所涉及到的任务数目
di——任务i的起始点至送达点间的距离
dij——任务i的送达点至任务j的起始点间的距离
xij——当任务j在任务i完成后被立即执行时为1，否则为0
U——不包括任务全集和单一任务子集的任务子集 
             约束条件(1)意味着在任务i之后立即执行的只有一项任务。约束条件(2)表明紧接任务J．之前仅有一项任务。约束条件(3)限制一些子路径：若任务j出现在任务i之后，那么禁止任务i在任务j之后。
                本研究采用被广泛引用的自组织神经网络Ko honen网络[3]。Kohonen网络方法计算效率高并具有适应不同情况的柔性，比如，上述数学模型仅适用于单一小车情况。当涉及多个小车时，Kohonen网络方法也能够提供综合分配和路径规划的复杂模型。
3 AGV路径规划问题的Kohonen自组织神经网络
                在AGV规划问题中，将要执行的任务数目从1 计到N，即J1，J2，…，JN。每一个任务J由一对坐标 表示，对应于任务J的起始点 和送达点的坐标。任务集中的一个排列可被看成为一组具体的拾取与送达任务指令。排列的目标是找 到最短的行驶距离。
                假设σ＝{1，2，…，N}为任务所涉及机床固定 位置的固定编号集，则路径规划任务就是给σ集中的每一位置分配唯一的一项任务i，并使得总的行驶距离最小。换句话说，在满足最优路径决策的条件下，需要建立任务集(J1，J2，…，JN}与位置集σ＝ {1，2，…，N}间的一对一映射。运送任务所对应的起始点和送达点的坐标是引导网络学习的输入样本。当一输入样本存在时，与该 输入样本对应的最小距离输出节点(获胜节点)，既全部输出元素中对应距离最短之元素被允许建立该输入样本的权重，同时在输出层中的相邻节点也建立该输入样本的较低权重。这样做的目的是使得获 节点处的相邻节点在相同输入样本再次出现时也具有相类似反映。由于相邻节点间的相互位置关系导致两相邻节点间距离最小，因而产生最短路径。通过权重调节减低邻域的长度，输出节点相互间将变得越来越独立，最终使得每一输出节点被分配一个运送请求。
                在实际网络训练开始时，在输出层并不存在输 出节点，节点的数目按节点插入不断增加，节点插入 过程对于改善网络训练速度和处理紧急请求以及多台小车情况是很有用的。
3.1 单一AGV路径规划算法
                在以上所描述的算法中，在给定一个完整的任务集J1，J1，…JN的基础上，如果在同一次迭代中，有两个不同的任务都选择同一节点作为获胜点，则该节点被复制，新建立起的节点以相同的权重被插在输出层获胜点相邻的左或右边。如果在3次迭代中一个节点都没有被选中为任何运送任务的获胜点，则该节点被删除。
3.2 多台AGV路径规划和分配问题
             当涉及到多台AGV时，系统需要保证每台 AGV都以最短运行距离分配到任务，以使得每个物 料输送系统的性能最优化。算法的基本原理一是平 衡多台 AGV的工作负荷，二是使所有被分配的 AGV的总运行距离最短。以下描述建立在Koho— nen自组织特征映射[3]基础上的适用于多台 AGV 情况的算法。
算法2
第1步：应用算法1，在已给任务集基础上获得 单一路径规划结果。
第2步：令为当前AGV位置坐标(s＝l，2，…，M)，d1为所有送运任务应当完成的时间界 限，分组汇集运送任务(保留路径规划次序)，使得每 组任务都能在时间界限d1之前完成，转到第3步。
第3步：若在第2步中的任务组数小于等于M， 则对于每一任务组分配一台距离组中第一节点位置 最近的AGV，让其完成该组的所有运送任务；若任 务组数大于M(意味着AGV台数不足够)，则对每 一前M个组分配距离最近的的AGV前往。 在算法2 中还可以使用不同的策略。如不以时 间界限d1作为分组指标，可采用其他指标来分 组。再如当任务组数大于从时，可让 AGV在超过 时间界限众1之后继续任务直到完成。策略的选择应 基于系统的条件以及其操作成本的大小。
4 结束语
                由于AGV路径规划和分配问题在整个FMS 运行中需反复被解决，所以有效的解决方法是很重要的。本文分析了一般FMS物流情况，研讨了自由分布式AGV规划问题的特征及相应对策，并提出相应的数学模型，阐述了在FMS环境下AGV的分配与路径规划问题的Kohonen自组织神经网络解 决方案的算法。这一算法和相应的数学模型已应用于一有两台AGV的FMS的实际运行中，目前运行情况良好。