带时间窗的车间搬运机器人路径优化建模及算法研究

任剑锋, 叶春明, 杨 枫

(1.上海理工大学 管理学院,上海 200083; 2.河南财经政法大学 计算机与信息工程学院,河南 郑州 450018)

0 引言

“中国制造2025”战略指出我国要大力推进信息化和工业化深度融合，加速推进生产过程智能化进程[1]；众所周知，车间是生产制造的关键环节，提高车间智能化管理水平，挖掘潜能、节约成本、降低能耗是学术界和工业界共同关心的课题。

以客户为中心，小规模、高灵敏度的个性化生产模式成为当前抢占市场、赢得客户的有力工具，车间搬运机器人的大量引进改变了以传送带进行物料配送的大规模生产模式，可在车间中准确高效地完成配送任务；多台搬运机器人则可组成柔性配送系统，并可以随着生产工艺流程的调整及时变更配送路径，使同一条生产线上能够同时加工多种产品，极大地提高了生产的柔性程度，生产效率得到很大提高，但同时人们也发现机器人的高额投资却与收益不成比例，如何充分挖掘机器人的生产潜能成为新的研究热点。合理分配机器人数量，改变机器人单一配送或回收任务为同时执行配送和回收任务，将机器人单独作业升级为多机器人同时作业模式；如此以来，我们就要考虑车间生产过程中存在的需求、供应、设备故障和其他类型的各种不确定干扰因素；另外，多机器人作业模式下，还要考虑机器人与障碍物或其他机器人之间可能存在的碰撞问题，合理设置避障机制。本文正是以车间场景下搬运机器人面对同时配送和回收任务为背景，以机器人数量、运输成本和时间惩罚成本的加权和为目标，解决机器人路径优化问题建模及算法研究。

遗传算法较早被用来求解机器人路径优化问题，Panchu等用遗传算法求解机器人的作业完成时间最小问题[2]；李妍峰等根据接收到的动态信息来进行机器人路径优化[3]；也有学者提出基于遗传算法来优化任务点的顺序[4]，通过优化和模拟完成任务的时间来确定机器人在连续点之间的最短路径[5]；双种群遗传蚁群算法也被用来求解该问题[6]，也有学者使用改进遗传算法求解类似问题[7～9]；通过对遗传算法在求解机器人路径优化问题分析发现，该算法在可以求解得到小规模机器人路径优化问题的最优值，但收敛速度较慢，难以很好满足车间生产模式下的敏捷需求。蚁群算法也被成功应用于机器人路径优化问题，裴振兵等提出用改进蚁群算法求解机器人避障问题[10]；赵宏才等提出建立α和β的互锁关系来定义信息素更新规则[11]，也有学者提出基于蚁群算法求解高质量的配送路线问题[12]；王辉等提出用改进蚁群算法求解泊车系统路径优化问题[13]；张建同等提出用混合蚁群算法求解卡车路径规划问题[14]；也有学者提出一种求解路径优化问题的混合蚁群算法[15]；分析发现，蚁群算法在求解机器人路径优化问题时具有鲁棒性较强、分布式特征明显、可靠性高等优点，缺点则是会以一定概率陷入局部最优解。强化学习[16]算法近年来也被应用于路径优化问题，于乃功等采用改进后的Q学习算法求解并取得了很好的效果[17]；高乐等提出一种改进的Q学习算法应用在多障碍环境下机器人的路径规划问题[18]；还有学者设计了一种改进的模糊Q学习算法求解路径规划策略问题[19]。还有学者用萤火虫优化算法进行车辆路径优化问题求解[20]；以及采用禁忌搜索算法求解车辆路径优化问题[21,22]，对本文问题研究也提供了一定的启发。

综上，国内外学者对机器人或类似研究对象的路径优化问题有较为深入的研究，在理论、模型和算法方面也取得了丰硕的成果，但在车间特定场景下同时进行配送和回收任务的多机器人作业路径优化问题研究成果并不多见；同时，相关研究多采用遗传算法、蚁群算法等智能仿生算法，用强化学习算法解决车间场景的机器人路径优化问题更是少见；同时，已有成果考虑的多为静态环境下的路径优化问题，并不符合车间场景下不确定因素众多的实际情形。比如车间生产环境下存在的动态障碍物出现、机器人自身性能波动、紧急订单插入、加工设备故障等动态因素；因此，本文提出一种强化学习遗传蚁群算法进行问题求解，结合蚁群算法的鲁棒性强、高可靠性等优点，同时引入遗传算子的交叉、变异机制跳出局部最优解，同时将强化学习算法对环境变化的感知能力有机结合起来，有效弥补单一算法的缺点和不足；全局路径通过嵌入遗传算子的蚁群算法求解，局部子路径通过强化学习算法求解，同时在子路经上捕捉车间动态出现的碰撞信息，并实现动态避障，最终求出以总成本最低为目标的路径优化问题。

1 问题描述

车间生产中每种产品所需的配件不同，每台加工设备均要及时供给物料，同时要及时取走该加工设备上已加工的产品，否则就会造成库存增加甚至导致设备暂停，对于高精尖且需要较长预热时间的设备，频繁关停或空转均会造成成本增加，甚至对设备造成损害。

在车间场景下，本文构建了多机器人的柔性搬运系统，根据生产车间存在众多不确定因素的实际情形，本文考虑在时间窗内为加工设备提供配送和回收服务，以确保加工设备及时得到物料供应，同时取走工位上的加工成品，通过时间窗口来降低车间不确定因素带来负面影响；故将搬运机器人对每台加工设备的到达时间设置为时间窗[Eti,Lti]，同时明确搬运机器人对每台设备的服务时长。

车间内部每台设备之间有一定的物理距离，可以确保搬运机器人能够穿梭行驶，且假定每台设备的位置和配送中心的位置、每台搬运机器人的最大运载能力已知，并且机器人的最大运载能力大于每台加工设备的单次配送或回收量。每台设备只能由一台机器人服务。为使问题简化，搬运机器人的电力续航能力较强，不再考虑机器人的最大运行距离问题。根据物料配送和产品回收的任务情况，合理安排搬运机器人的数量，要求完成物料配送和产品回收任务的同时，还要使每台加工设备在时间窗内得到服务，实现机器人数量即基本成本、运输成本和时间惩罚成本加权总成本最小。车间只设置一个配送-回收中心，机器人在完成配送-回收任务之后均返回中心，形成闭合的运行轨迹，如图1所示。

图1 配送路径示意图

车间环境下机器人的配送问题路径优化与一般的pickup-delivery问题相比，因为车间环境狭小、设备价值较高因素，要考虑机器人与其他机器人或障碍物之间可能发生的碰撞问题，避免因碰撞而导致末端执行工具的损坏，可能发生碰撞时，机器人传感器及时发送信号给控制系统，进而紧急调整配送路径；因此，结合车间环境下的配送回收问题特殊性，动态避障问题是本文在设计算法时加入强化学习部分的主要原因。

2 模型构建

车间有R台最大运载能力均为Q的搬运机器人在时间窗[Eti,Lti]为M台加工设备提供配送-回收服务。

Eti表示机器人对设备i的最早开始服务时间，Lti表示最迟服务时间。

ti表示机器人到达设备i的时间，并在完成对设备i的服务后经时间tij运行至下一个服务对象j，到达时间为tj，wi表示机器人对设备i的服务时长。

Qrij表示机器人r从设备i到j的过程中是否产生碰撞。

di表示该设备需要的配送量，pi表示该设备需要的回收量，eij表示机器人在经过设备i之后的配送总量，之后前往j设备；fij表示机器人在经过设备i后的回收总量，之后前往j设备；且任何时候机器人的配送量与回收量之和不能超过机器人的最大运载能力；配送-回收中心和各加工设备的空间位置已知，并用相应的坐标表示，用dij表示从加工设备i到设备j的距离，决策变量xijr和yir定义如下。

问题的数学模型如下:

(1)

(13)

该模型中式(1)表示目标函数，即车间总的配送-回收成本最低；式(2)表示所有机器人均从配送-回收中心出发；式(3)表示机器人完成任务之后返回配送-回收中心；式(4)、(5)和(6)表示有且仅有一台机器人到达某一设备，并提供服务；式(7)、(8)和(9)表示服务时间约束；式(10)表示设备所需的物料配送量约束；(11)表示设备所需产品回收量约束；(12)表示机器人的运载能力限制，(13)中Qij值为1表示从机器人r从设备i到j的过程中是否产生碰撞，0表示未产生碰撞。

3 算法设计

3.1 位置扫描

采用扫描法来获取加工设备的位置，即用极坐标来表示加工设备的位置，随机选取某一设备位置为起始点，将其角度设为零度，以机器人的最大运载能力为限制条件进行设备节点分割，得到若干符合运载量限制的子区域，取子区域的几何中心并设置为虚拟节点。

3.2 节点选择策略

(14)

3.3 信息素更新策略

信息素的更新方式至关重要，信息素更新过快，会导致“早熟”而陷入局部最优，更新过慢则会降低收敛速度。因此，本算法中的信息素更新方式根据路径的适应度值来动态更新信息素的方式，如式(15)。

(15)

其中Q′为常数，适应度值较小的路径上信息素增加量大，反之，信息素增加量小；大量实验证明，式(15)的信息素更新方式可以有效提高收敛速度。

3.4 编码

本算法中采用路径表示法编码，每个可行解编码即表示经过的节点序列，对于有n台加工设备的车间，m台机器人来执行配送-回收任务的问题，用0到n+m-1共n+m个数字编码为(0-x1-x2-…-xn+m-1)，0表示配送-回收中心，在编码中第一台机器人用0表示，其余机器人则用n+1,n+2,…,n+m-1表示。之所以第一台机器人也用编码中的0表示，是为了减少编码长度，同时不影响编码的结构特征和信息表达。

如车间有10台加工设备，4台机器人参与服务，则编码0-3-5-11-2-7-8-12-4-6-1-13-9-10表示一个可行序列，编码序列表达的配送-回收子序列为:

机器人1服务路线：O-3-5-0

机器人2服务路线：O-2-7-8-0

机器人3服务路线：O-4-6-1-0

机器人4服务路线：O-9-10-0

根据机器人路径优化的特点，为保留染色体的优秀基因，可行解的较优染色体采用如下的交叉策略，设两组染色体分别为A1和A2。

(1)随机生成染色体交叉的起始位置和交叉段长度如下：

本文中交叉策略保留染色体中的优秀基因片段，并且可以加快收敛到最优解，缺点是容易陷入局部最优；实验证明，遗传算子在变异过程中可以对信息素产生明显的扰动作用，跳出局部最优解。

3.5 动态避障策略

本算法中采用强化学习算法来求解子路径的优化及动态避障问题。

(1)状态迭代

本算法中构造的状态值函数迭代方程为：

V(sk)←V(sk)+α[rk+1+γV(sk+1)-V(sk)]

(16)

即:V(sk)←αrk+1+γV(sk+1)+(1-α)V(sk)

(17)

其中α为学习率，γ为折扣因子，V(sk)为当前状态值，V(sk+1)为下一状态值，通过式(16)的反复迭代，最终使方程收敛到最大状态值，进而得到最优路径[23]。

将配送-回收中心抽象为节点0，在服务子路径中的加工设备抽象为中间节点①→，将终点也抽象为节点0(即只有一个配送-回收中心)，如图2所示。

图2 强化学习路径寻优示意图

从出发节点0开始前往子路径上的任意其他节点，例如路线0→①→③表示从配送中心出发首先前往节点1服务，然后再前往节点3服务，以此类推，节点①与节点①之间没有连线，表示不允许从该节点仍回到该节点。

本问题中动态选择路径的过程中不存在状态转移的概率模型，因此选用Q-learning算法，将路径长度作为强化学习迭代过程中的奖励值；同时，因为本文要解决有时间窗和服务时间的机器人配送-回收问题，因此，将每个加工设备上的服务时间作为该节点的状态值，并采用贪婪策略选择路径，如式(18)所示。

(18)

算法流程如图3所示。

图3 强化学习遗传蚁群算法流程

(2)动态避障

车间环境下的障碍物一般可分为长期静态障碍物、临时静态障碍物和临时动态障碍物共三类；因前两类的研究已较为成熟，本文主要以临时动态障碍物为研究对象，通过强化学习算法感知超声波、红外等传感器数据来实现动态避障[24]。

如图4所示的问题，在常规情况下算法按照约束条件可以快速搜寻到最短路径1-3-7-11-16-19-20，如果最优路径上第11个节点动态出现障碍物，根据传感器反馈的障碍物信息，将该节点的状态值设为无限大，从而快速避开障碍物并搜寻到其他可行路径1-3-7-12-16-19-20。

图4 动态避障示意图

图5 避障迭代曲线

图5表示了常规约束条件下和动态避障后的迭代曲线。通过对比可以发现，在常规情况下，强化学习算法可以快速收敛到最优值28；在障碍物出现后，强化学习算法可以迅速捕捉到节点状态值的突然变化，在计算开销很小的情况下实现紧急避障，并重新搜寻到最优路径值32。

从实验中还可以发现，假如机器人行驶在节点3与节点7之间的路径上，此时节点11产生临时动态障碍物，在重新规划路径时，不需要重新设置起始点，即障碍物出现之前的已规划路径不会改变，为机器人执行配送任务的连续性提供了支持。

4 模拟仿真

4.1 实验环境及参数设置

本文在Intel i7处理器使用Matlab2017a进行实验，其中蚁群算法的信息素重要程度因子取值为1，启发函数重要程度因子取值为5，信息挥发因子为0.1，常系数Q为1；遗传算法的交叉概率为0.85,变异概率为0.1,遗传代沟为0.8；强化学习算法的学习率取值为0.1，折扣因子为0.9，三种成本参数如表1所示。

表1 成本参数表

本文将车间生产的配送-回收中心作为节点0，取其坐标值为(30，60)，车间内共有加工设备45台，分别以相应的坐标X值和Y值表示其位置，每台加工设备的配送量和需回收量已知，以及接受服务的最早时间和最迟时间，每台加工设备有明确的配送和回收的服务时长，如表2所示。

表2 加工设备信息表

4.2 实验及对比分析

用本文算法对问题进行求解，设每台机器人的基本成本为300，每次实验的最大迭代次数为500次，可以发现在200次迭代以后基本可以得到较满意解，并可以得到机器人基本成本为2100，即需移动机器人7台来完成物料配送和产品回收任务，结果如表3所示。

表3 最优配送路径

表中SP(Service path)表示服务路径，AC(Actual capacity)表示机器人的实际运载量，DW(Dead weight)表示最大载重量，FR(full-load ratio)表示满载率。

同时，可求得运输成本为1970.13；时间惩罚成本为0，即所有加工设备均可在时间窗内得到服务，总成本代价为4070.13。对每台机器人的满载率计算可以发现运载能力得到了充分利用。

为了进一步验证本文算法的有效性，与Wang等[25]公开的用遗传算法(GA)求解的20个基本算例结果进行对比，其中小规模算例(10个配送节点算例3个，20个配送节点算例2个)共5个，中等规模算例(50个配送节点)3个，大规模算例(100个配送节点)12个。基于以上基准算例，同时用Chao Wang等[26]公开的模拟退火算法(PSA)进行求解并对比。

表4和表5中的NR(Number of Robot)表示分配的机器人数量，TD(Travel Distance)表示完成配送任务的行驶距离，NO(Number of obstacles)表示在算例中随机出现的区间[0,5]之间的动态障碍物个数。

小规模算例计算结果可以发现，使用RLGA算法对5个算例进行求解，RCdp1004算例的计算结果达到理论最优值，其余四个算例的计算结果与理论最优值相比，与理论最优值差距的平均值是0.26%，可见本算法在小规模算例中的计算结果可以很好的逼近理论最优值，如表4所示。

小规模算例RCdp1001的求解路径如图6所示，该算例加入动态障碍物之后的求解路径如图7所示。

对中等规模和大规模的15个基准算例分别采用GA、PSA和RLGA进行求解，将实验结果分为两种情形，第一种情形是在算例中加入了障碍物的7个算例；由表5可知，7个算例添加的障碍物平均个数是3，其TD值均较基准结果有所增加，其中GA计算结果平均增大0.33%，PSA计算结果平均增大0.27%,RLGA计算结果平均增大0.17%，在三种算法计算结果中，RLGA算法表现最好，可见RLGA算法对动态避障问题有较好的解决机制，可以将障碍物对路径优化的带来的干扰降到合理范围，得到比GA和PSA优秀的结果；第二种情形是未出现障碍物的算例共8个，其中有2个算例节约了1台机器人，同时伴随TD值略有增加，其余6个算例中的3个算例TD值与GA算法和PSA算法计算结果相同，剩余3个算例的TD值有不同程度降低，平均降低0.34%；可见，RLGA算法可以得到更优的结果。

在算法的计算速度方面，选取小规模算例(10个配送节点)、中等规模算例(50个配送节点)、大规模算例(100个配送节点)问题的GA、PSA和RLGA算法的收敛曲线对比如图8(a)、(b)、(c)所示。

比较发现，在求解小规模问题时，RLGA算法在收敛速度和解质量上略优于其他两种算法；在求解中等规模和大规模问题时，RLGA算法的求解质量和速度上要明显优于GA算法和PSA算法计算结果。

算法在解决大规模配送问题时优势更加明显，在考虑动态障碍物和无障碍物两种情况下，求解质量和速度均优于其他两种算法，表明RLGA算法的优越性。

表4 RLGA算法与理论最优值对比结果

表5 GA、PSA、RLGA算法结果

图6 RCdp1001算例路径

图7 RCdp1001算例加入障碍物后路径

图8 GA、PSA、RLGA算法收敛曲线对比

5 结论

本文提出强化学习遗传蚁群算法来求解车间场景下的搬运机器人路径优化问题，引入扫描法对设备节点进行聚类划分，将复杂问题简化；借助强化学习的序贯决策和环境感知能力，结合蚁群算法的信息素更新策略和遗传算法的交叉、变异机制实现车间搬运机器人同时执行配送和回收问题的路径优化，通过与基准算例的结果比较表明算法在解质量和求解速度上的优越性。

本算法中强化学习的状态值和奖励值分别由加工设备所需的服务时长和路径长度决定；实验发现，如果设置动态的状态值和奖励值可以更好地体现车间实际情形，同时加入机器人行为要素，同时考虑更复杂的避障要素会进一步提升算法在理论和应用上的价值。