随着生产技术的进步和客户需求愈发的多样化，以订单为导向的生产得到了越来越多企业的青睐^[1]. 这种订单驱动的生产模式，对车间生产调度提出了更高要求，由此基于机器学习的智能调度方法被逐渐采用，智能车间应运而生^[2]. 智能车间的生产过程通常具备以下特点：1）中间品的种类和数量众多；2）物料需频繁进出仓库，并于加工中心频繁装卸；3）生产工序庞杂，任务调度紧凑，任何环节的拖延都会打乱调度计划. 因此，一种适用于智能车间的高效物料搬运作业调度方法对保证车间生产效率有着极为重要的作用.

智能车间中，物料搬运作业一般由自动导引小车（Automated Guided Vehicle，AGV）完成. 这种具备环境传感设备和自动导航装置的载物小车受场地与设备的限制小，在作业中具备相当的灵活性^[3]. 而强化学习是一种非监督式的机器学习方法，从与周围环境的交互中进行学习^[4]，其训练数据无需携带标签且互相独立，与AGV调度结合，可使后者快速响应，以最短时间完成各种物料搬运任务. 目前，基于强化学习的AGV调度可分为单机调度和多机协同调度两大类. 单机调度主要考虑AGV在物料搬运过程中的路径规划问题，如Soong等^[5]采用Q-Learning强化学习算法对单台AGV进行路径规划，并使用花授粉算法初始化调度决策模型加快其收敛速度. 多机协同调度则是在单次调度内完成对系统中所有AGV的搬运任务分配及路径规划，相较于单机调度，更契合智能车间物料搬运需求，但也会造成调度决策模型的状态空间和动作空间的维数激增^[6]，从而引发调度算法的维数灾难，导致其收敛时间过长甚至无法收敛. 刘辉等^[7]通过多智能体强化学习，减少了动作空间维数过大的影响，加快了调度决策模型的收敛进程.

以上研究大多面向确定性的搬运任务，而智能车间的物料搬运任务因订单而异，具备任务数量众多、任务需求实时变化、任务下达密集等特点. 针对上述问题特征，本研究在现有研究的基础上，基于强化学习建立一种订单驱动下的智能车间AGV的调度模型. 该模型使用二级调度机制，第一级完成搬运任务对各AGV的分配，第二级使用强化学习深度Q网络（Deep Q-Network，DQN）算法对系统中所有AGV分别进行搬运路径规划. 这种方法以多次单机调度替代多机协同调度，在满足智能车间AGV调度需求的同时，降低了调度算法的收敛难度.

1.   智能车间AGV调度问题模型

智能车间的生产调度中，生产调度系统会根据订单需求，对各工件实时下达加工任务^[1]. 在此过程中会产生一系列的物料搬运任务，包括从某个加工中心上卸载已完成该工序的工件，将半成品工件搬运至下道工序的加工中心并装载，将成品工件或暂不需要立刻进行下道工序的工件搬运至仓库等. 各AGV实时监测自身电量，当其小于预先设定的警戒电量时，需要进行充电. AGV调度系统由车间空间信息模型、任务分配模块和路径规划模块三部分构成， 如图1所示. 空间信息模型是描述制造车间物料调度及AGV工作状态信息的数字孪生模型. 任务分配模块根据生产任务安排情况，结合空间信息模型提供的信息，向车间中各AGV分配任务. 路径规划模块根据这些任务分别对每辆AGV进行路径规划. 各AGV按规划路径执行任务，并将任务执行信息反馈至空间信息模型中.

图  1  智能车间AGV调度系统功能模块

Figure  1.  Function modules of AGV scheduling system in intelligent workshop

下载: 全尺寸图片 幻灯片

调度系统满足以下抽象和假设：

1）系统中存在多台确定数量的AGV，各AGV性能、体积、运载能力等参数完全相同；

2）所有AGV在初始时刻均可用，且不考虑在执行物料搬运任务时AGV可能发生故障的情况；

3）各加工中心的待加工缓冲区和已完工缓冲区的容量有限，过度积压会导致该设备停工；

4）车间内所有通道均可容纳至少两辆AGV并行通过，即各AGV的路径规划间不存在干扰；

5）AGV在划定的停放区待命，停放区内设立AGV释放点和回收点作为物料搬运任务路径规划的起点和终点，不考虑停放区内的路径规划；

6）AGV只在停放区进行充电，充电中AGV直至充满电前不可用于物料搬运任务.

基于栅格图建立^[8]车间空间信息模型，$G$为矩形平面图，用以描述制造车间的场地特征及设备布局. 定义其竖直方向为$X$方向，水平方向为$Y$方向，左上角为原点，向下为$X$正方向，向右为$Y$正方向. $G$在$X$，$Y$方向上的栅格单元数量分别为${m}_{g}$，${n}_{g}$. 栅格单元的尺寸根据AGV的外廓尺寸进行设定，使得两辆AGV能并排停驻在一个栅格单元内. ${g}_{ij}=\left(p,c\right)$为每个栅格单元，$p$为一组用以标识栅格位置的二元坐标，从原点沿$X$，$Y$正方向进行标识，记作：$p=\left(i,j\right),1\leqslant i\leqslant {m}_{g}, 1\leqslant j\leqslant {n}_{g}$，$i$，$j$分别为两方向上的栅格单元序数. $c$为方格类型，$c= \{c\mid N,W,L,P,S,E\}$；$N$为可供AGV通行的车道；$W$为障碍，包括场地设施、固定设备等. 为了将栅格图增补成矩形而在实际车间布局中不存在的栅格单元也属于$W$型栅格单元，AGV无法在该型单元上行驶. $L$为可装卸处，AGV停泊于此栅格单元可进行物料装卸作业. $P$为AGV停放处，$P$型栅格区内不做路径规划，AGV在此区域待命和充电. $S$和$E$分别为AGV停放区的释放点和回收点. 将AGV的移动轨迹模拟成沿栅格移动，则其行驶通过的栅格单元坐标所构成的轨迹${\tau }_{p}=\left({p}_{1},{p}_{2},\cdots ,{p}_{n}\right)$，即一次任务的路径，$L\left(\tau \right)$为路径$\tau$的长度.

集合$V=\left\{{v}_{i}∣1\leqslant i \leqslant {n}_{v}\right\}$为系统中所有AGV. $w$和${q}_{\text{max}}$为AGV的运载能力和警戒电量，所有AGV相同. $s\left({v}_{i}\right)$、$q\left({v}_{i}\right)$、$b\left({v}_{i}\right)$分别为第$i$辆AGV的工作状态、电量和累积运量. 其中$s\left({v}_{i}\right)=\left\{1, 0\right\}$ ，$s$值为$1$和$0$分别表示该AGV处于可调用状态（闲）和不可调用状态（忙）. 当$q\left({v}_{i}\right)\leqslant {q}_{\text{max}}$时，AGV需返回停放区充电. $b\left({v}_{i}\right)$记录${v}_{i}$自开始调度起的累积物料搬运总量，作为搬运任务分配的依据.

AGV调度系统根据生产调度系统进行搬运任务的分配，故每次任务的目标装卸点并不相同，且由于物料搬运包括装载和卸载，部分目标点之间存在到达次序约束关系. 为方便调度计算，本研究离散化描述运量和运能，根据生产情况，设定标准运载单位${l}_{u}$，物料搬运需求$u$和AGV搬运能力$w$均为${l}_{u}$的整数倍，其中$u$以±符号代表AGV在该点从对象设备上卸载或装载物料.

本研究中，集合${T}_{i}$为第$i$次搬运任务的搬运任务集，包含目标装卸点信息，公式为

式中：${s}_{l}$为目标装卸点栅格单元；$p\left({s}_{l}\right)$为其坐标；$u=(u_1, u_2)$为该点的装卸运量，其中u₁为AGV在s_l点的装载货量，u₂为AGV在该点的卸载货量；$j$为AGV到达优先级，$j$值越小需越先到达，$j$值相同的目标装卸点没有到达次序的先后要求. 在低$j$值目标全部到达之前，途径的高$j$值目标不视作到达该目标. 一次任务中，AGV总是从释放点位置$S$出发，按到达优先级约束经由各目标装卸点后，返回回收点$E$进入停放区待命或充电.

任务分配模块的目标是提升各AGV小车的利用率，使各AGV尽可能均分任务负载，提高搬运效率. 其目标函数为

式中：${n}_{v}$为AGV总数；$u\left({v}_{i}\right)$为AGV ${v}_{i}$的利用率，$\stackrel{-}{u}$为所有AGV的平均利用率. 路径规划模块的目标是在满足任务目标的前提下，尽可能地缩短执行一次任务所产生的轨迹长度. 其目标函数为

2.   智能车间AGV调度方法

智能车间AGV调度使用二级机制：第一级负责搬运任务对各AGV的分配，使用基于规则的方式进行，以各AGV负载均衡为目标；第二级对各AGV分别进行单机路径规划，以装卸目标点的到达次序约束分为数个阶段，每个阶段单独规划，前一阶段目标全部完成后才可进入下一阶段.

2.1   物料搬运任务分配

当车间中物料搬运需求到达某个定量，即$u={u}_{d}$时，系统到达决策点，此时需将运量为${u}_{d}$的物料搬运任务分配给各AGV. 任务以负载均衡为目标，从累积搬运量最小的可调用AGV起，以轮循方式进行分配^[9]. 每次分配都使单台AGV尽可能多地完成搬运任务. 轮循是一种基于规则的调度方法，在各决策点对当前所有可用AGV按其累积运量$b\left(v\right)$，依由小到大的顺序进行任务分配，如图2所示. ${o}_{t}\left({v}_{i}\right)$为${v}_{i}$在决策点$t$被分配到的搬运任务，则有$\forall {v}_{i}\in V,u\geqslant w$，${o}_{t}\left({\mathrm{argmin}}_{{v}_{i}}b\left({v}_{i}\right)\right)=w,{u}^{\prime}=u-w$.

图  2  搬运任务分配流程图

Figure  2.  Transporting tasks assigned flow chart

下载: 全尺寸图片 幻灯片

2.2   AGV路径规划

如前文所述，在每个决策点对系统中所有可用的AGV分别进行单机路径规划，每台AGV的搬运任务由任务分配模块给定. 某AGV一次搬运任务的路径规划中，AGV需要从释放点$S$出发，经由各目标点并完成装卸后，返回回收点$E$待命或充电，目标装卸点随任务而变. 为此本研究采用强化学习的方法构建单AGV的路径规划模型.

强化学习由智能体（Agent）和环境（Environment）两部分组成，智能体从与环境的交互获得反馈，从中不断学习更新，从而完成特定的任务目标^[2]，如图3所示. 智能体在环境中获得状态（State），根据该状态生成一个动作（Action），环境执行此动作并输出下一个状态及动作带来的奖励（Reward）. 智能体的学习目标即尽可能多地从环境中获取奖励.

图  3  强化学习示意图

Figure  3.  Reinforcement learning schematic diagram

下载: 全尺寸图片 幻灯片

2.2.1   基于强化学习的AGV路径规划

在使用强化学习方法解决上述AGV路径规划问题时，以车间空间信息、该次任务目标装卸点信息，AGV当前位置信息作为状态^[10]. 智能体的每次决策确定AGV在下一步的行驶方向^[11]，每一步内，AGV选择沿车间栅格图的$X$轴正反方向和$Y$轴正反方向中其一，移动一个栅格单元的距离.

在一次任务中，智能体持续决策，直到AGV完成从释放点出发经由各目标装卸点到达回收点的全部任务行程. 每完成一次任务会形成一条状态−动作轨迹${\tau }_{sa}=\left\{{s}_{0},{a}_{0},{s}_{1},{a}_{1},\cdots , {s}_{t},{a}_{t},\cdots , {s}_{T-1}, {a}_{T-1}, {s}_{T}\right\}$，其中${s}_{t}$、${a}_{t}$为智能体第$t + 1$次决策时所在的状态及该决策所确定的动作.

强化学习中智能体通常由策略（Policy）和价值函数（Value Function）组成^[2]. 智能体在进入某一状态后基于策略选取下一步的执行动作，在策略${\text{π}}$下，有$a={\text{π}}\left(s\right)$. 价值函数${q}_{{\text{π}}}\left(s,a\right)$定义为在状态$s$下，依据策略${\text{π}}$执行动作$a$后所能获得的期望累积折扣奖励，以评估在该状态下执行上述动作对后续交互中获得的累积奖励的影响，即对策略进行评判. 价值函数值越大，说明在该状态下选择此动作的收益越高，越有利于目标达成. 其公式为

为训练智能体，使其能做出带来高收益的决策，需要让AGV不断地执行任务，并在每次任务中让智能体持续决策，在这种智能体与环境的交互中，不断获得奖励，从而获取智能体策略更新的依据. 我们把训练中的每一次的任务称作一个回合（episode）：$e=\left\{{e}_{1},{e}_{2},\cdots ,{e}_{n}\cdots \right\}$，${e}_{n}$为第$n$个回合，每个回合均可形成一条状态−动作−奖励轨迹：$\tau =\left\{{s}_{0},{a}_{0},{s}_{1},{r}_{1},\cdots ,{s}_{t},{r}_{t},{a}_{t},{s}_{t + 1},{r}_{t + 1}\cdots ,{s}_{T},{r}_{T}\right\}$，其中${r}_{t + 1}$为在${s}_{t}$状态下执行${a}_{t}$动作所获得的奖励，同时状态由${s}_{t}$变为${s}_{t + 1}$.

2.2.2   路径规划的强化学习环境

智能车间AGV路径规划问题的强化学习环境在车间空间信息模型的基础上建立，环境包括以下功能：状态的生成及更新机制，动作空间及其作用机制，奖励机制.

状态${\boldsymbol{S}}$为$m\times n$维矩阵，其维度由车间栅格图决定，大小为$m\times n$的车间栅格图${{\boldsymbol{G}}}_{\left(m\times n\right)}$为$m\times n$维状态矩阵. 各栅格单元状态可分为AGV当前所在、可通行、不可通行、中间目标和终点5种. 对状态矩阵${\boldsymbol{S}}$中的各元素${s}_{ij}$以0 ~ 1之间的浮点数进行编码，见表1.

表  1  状态编码

Table  1.  State encoding

栅格单元状态	栅格单元类型	$s$值
AGV当前所在	$N,S,L\cap {g}_{ij}\notin T$	$0.5$
可通行	$N,S,L\cap {g}_{ij}\notin T$	$1$
不可通行	$W,P$	$0$
中间目标点	$L\cap {g}_{ij}\in T$	$0.7 - \dfrac{0.3}{n-1}j$
终点	$E$	$0.3$

下载: 导出CSV 

| 显示表格

AGV的动作空间$A=\left\{{A}_{0},{A}_{1},{A}_{2},{A}_{3}\right\}$，共4个动作，分别代表对AGV下达在栅格图上沿$X$、$Y$轴正、反方向移动一个栅格单元距离的指令. 其中${A}_{1}=\left(\mathrm{0,1}\right)$，${A}_{2}=\left(0,-1\right)$，${A}_{3}=\left(\mathrm{1,0}\right)$，${A}_{4}=\left(-\mathrm{1,0}\right)$. 智能体对AGV下达的移动指令并不必然导致AGV的移动行为，若执行该指令后AGV依旧位于可通行栅格单元，即通道、装卸点、AGV回收点，则动作指令有效，AGV执行指令所对应的移动；否则，该动作指令无效，AGV停在原地，不执行移动行为.

AGV状态矩阵${{\boldsymbol{S}}}_{V}$由其当前所在栅格单元的位置坐标决定. 令 ${p}_{t}=\left({p}_{t}^{x},{p}_{t}^{y}\right)$ 为某回合内智能体第t次决策时AGV所处栅格单元的位置坐标，${a}_{t}$为此次决策智能体所采取的动作，则第$t + 1$次决策前AGV所处栅格单元的位置坐标为

执行移动行为后，AGV位置坐标将会更新，AGV状态矩阵也随之更新. 在强化学习中，对环境执行动作会改变其状态，状态更新会带来奖励. 奖励是由环境给出的一种标量反馈信号，在AGV路径规划问题中，按规则建立奖励函数，见表2. 由表可知，AGV每次执行动作获得负奖励，每到达目标装卸点和回收点时获得正奖励，由此促使智能体以尽可能短的路径让AGV到达所有目标位置.

表  2  奖励函数

Table  2.  Reward function

状况	奖励$r$
执行有效移动指令	$-\dfrac{1}{m \times n}$
下达无效移动指令	$- \dfrac{4}{ \sqrt{m \times n} }$
到达目标装卸点	$\dfrac{1}{n_T}$
完成搬运任务后到达回收点	$1$

下载: 导出CSV 

| 显示表格

2.2.3   基于DQN的路径规划智能体

本研究使用DQN算法构建智能体并对其进行训练^[12]. DQN通过神经网络构建状态对动作的映射${\boldsymbol{S}}\to A$，从而使智能体得以决定AGV在各状态下应采取的动作，如图4所示.

图  4  AGV路径规划Q网络

Figure  4.  Q network for AGV path planning

下载: 全尺寸图片 幻灯片

将状态矩阵${\boldsymbol{S}}$输入神经网络，得到一个4维向量作为输出，该向量中每个元素分别代表在该状态下执行各动作所得到的价值函数${q}_{{\text{π}}}\left(s,{a}_{i}\right),{a}_{i}\in A$的估计${\widehat{q}}_{{\text{π}}}\left(s,{a}_{i}\right),{a}_{i}\in A$，选取当前状态下具有最大估计价值函数的动作作为当前动作，可得

本质上，DQN中智能体的神经网络用以评判在某种状态下，执行各动作所能获得的期望累积奖励的多少，这种神经网络被称为Q网路. 本研究中，Q网络由卷积神经网络（CNN）和深度神经网络（DNN）前后连接而成^[13]. CNN由卷积层、激活层、池化层三部分构成，因其相对其他前馈神经网络有更少的参数和更高的计算效率而被广泛应用于各种图像识别领域中^[2]. 在智能车间AGV路径规划问题中，使用CNN识别因任务而异的目标装卸点和每次移动后AGV的位置. DNN由一系列全连接层构成，用以建立CNN输出结果与估计价值函数$\widehat{q}\left(s,{a}_{i}\right),{a}_{i}\in A$之间的映射.

2.2.4   路径规划智能体的训练与成型

对Q网络的训练属于对回归问题神经网络的训练，如图5所示. 通过更新Q网络参数使估计价值函数 $\widehat{q}\left(s,{a}_{i}\right),{a}_{i}\in A$尽可能地接近真实价值函数$q\left(s,{a}_{i}\right),{a}_{i}\in A$. 根据贝尔曼方程^[9]，第$t$次交互时$\widehat{q}\left({s}_{t},{a}_{t}\right)$的目标拟合函数为

图  5  DQN训练流程示意图

Figure  5.  DQN training flowing chart

下载: 全尺寸图片 幻灯片

3.   AGV路径规划实例

为验证本研究提出的AGV调度系统的有效性，对某智能车间进行仿真试验，图6为该车间的平面图及对应栅格图. 其中${s}_{1}$至${s}_{4}$为仓库货架，${m}_{1}$至${m}_{8}$为加工中心，两者周围均有可供AGV进行物料装卸作业的专用停泊点.

图  6  智能车间平面图及其对应栅格图

Figure  6.  Plan and grid map of intelligent workshop

下载: 全尺寸图片 幻灯片

试验系统中共3台AGV：$V=\left\{{v}_{1},{v}_{2},{v}_{3}\right\}$，运载能力$w=2$. 当物料搬运需求$u > {u}_{d}=12$时，系统进入决策点，随即对各可调用AGV进行任务分配. 某次决策点的搬运任务分配见表3. 此时，3台AGV的累积运量分别为22、24、28，且${v}_{1}、{v}_{2}$可调用，${v}_{3}$正在充电中，按AGV累积运量大小对${v}_{1}、 {v}_{2}$分配搬运任务. 两者完成任务后，3台AGV的累积运量变成26、26、28，继续分配当前决策点剩余运量的任务，直至任务分配完毕. 对某次路径规划任务，以表3中轮次03的任务为例，其搬运任务集为${T}_{2}$. ${v}_{1}$从释放点$\left(0,10\right)$出发，按到达优先级约束最先规划坐标(3,4)和(5,4)两栅格单元的路径，并在两处从加工中心卸载各一单位运量的物料，装入AGV中. 随后完成对坐标$\left(6, 8\right)$栅格单元的路径规划，将两单位运量的物料装入仓库货架中. 最后返回AGV回收点$\left(10,10\right)$.

表  3  某次决策点的搬运任务分配

Table  3.  Material transport tasks assigned on one decision point

待运量	轮次	选定AGV	当前状态	当轮运量	累积运量	搬运任务集$T$
$12$	01	${v}_{1}$	可用	$4$	$22\to 26$	${T}_{1}=\left\{\left(\left(3, 6\right), (0, 2), 1\right),\left(\left(1, 1\right), (2, 2), 2\right),\left(\left(7, 1\right), (2, 0), 3\right)\right\}$
8	02	${v}_{2}$	可用	2	$24\to 26$	${T}_{2}=\left\{\left(\left(3, 4\right), (0,1), 1\right),\left(\left(5, 4\right), (0, 1), 1\right),\left(\left(6, 8\right), (2, 0), 2\right)\right\}$
6	03	${v}_{3}$	充电	0	$28\to 28$	无
6	04	${v}_{1}$	可用	2	$26\to 28$	${T}_{4} = \left\{ \left( \left( 3, 6 \right), (0, 2) , 1\right), \left(\left(3, 1\right), (1, 0), 2 \right), (\left(7, 4\right), (1,0) , 2) \right\}$
4	05	${v}_{2}$	可用	4	$26\to 30$	${T}_{5}=\left\{\left(\left(5, 1\right), (0, 4), 1 \right),\left(\left(5, 4\right), (2,0), 2\right),\left(\left(1, 8\right), (2,0) , 2\right)\right\}$

下载: 导出CSV 

| 显示表格

根据DQN训练流程得到结果，如图7所示. 随着任务轮（episode）的进行，智能体获得的奖励（reward）逐步提升并收敛于一高值，由于每轮任务的搬运目标并不相同，故该值并不恒定. 根据奖励函数的设定，浮动值不大. 同时结合DQN损失亦随训练轮次下降而下降并收敛于0，可知Q网络对状态−动作价值函数$q(s,a)$的估值趋向稳定，也说明了智能体在训练完毕后的各轮均得到了其理论最大累积奖励，即找到了最优路径. 训练完毕智能体对某些物料搬运任务的路径规划方案，如图8所示.

图  7  智能体累积奖励与DQN损失

Figure  7.  Agent reward and DQN loss

下载: 全尺寸图片 幻灯片

图  8  智能体路径规划示例

Figure  8.  Example of path planning by DQN Agent

下载: 全尺寸图片 幻灯片

4.   结　语

本研究探索了一种基于强化学习的AGV在线调度方法，该方法为两级调度，第一级进行搬运任务对各AGV的分配，第二级基于强化学习DQN算法进行单智能体路径规划. 实例仿真表明，该方法可满足大量实时产生的非计划搬运任务的需求，提升了订单驱动型智能制造车间的物料搬运效率，同时具备对不同车间环境布置状态下的泛用性. 该方法为制造车间衔接生产调度系统和物料搬运系统实现一体化调度提供了一种可行的方案，但目前方法的可行性与泛用性均基于模拟仿真，未能进行有效的现场实验. 此外，方法未充分考虑AGV实际运行过程中可能产生的故障及应对措施，影响了AGV调度系统的稳定性.

综上，未来的研究将关注对调度系统稳定性的提升，充分运用基于强化学习的调度模型的训练特性，为调度系统提供意外事件处理能力. 同时进一步整合优化生产调度与物料搬运调度的任务处理流程，减少重复调度，缩短调度响应时间.