基于改进遗传算法的AGV集结路径研究

2021-02-03赵睿楼佩煌钱晓明武星胡泊

机械制造与自动化 2021年1期

赵睿，楼佩煌，钱晓明，武星，胡泊

(南京航空航天大学机电学院，江苏南京 210016)

0 引言

随着中国制造2025和工业4.0的不断推进，多AGV(automated guided vehicle)系统也越来越多地应用于各类仓库和生产车间中[1]。然而实际环境要复杂得多，多AGV系统可能面临尺寸、质量、形状差异较大的搬运任务，而单台AGV由于载重、尺寸限制无法完成全部的搬运任务。为了解决这个问题，需要将具备协同搬运能力的AGV加入到多AGV系统中。

当搬运任务发布，确定了多AGV系统中需要执行协同搬运任务的AGV序列之后，需要为这几台AGV规划从当前位置到达任务点的路径，使AGV从分散状态集中到需要执行协同搬运任务的工位点，即协同搬运AGV的集结。集结速度的快慢直接影响了多AGV系统响应任务的速度。集结速度过慢会导致搬运任务的等待时间过长，如果路径规划不当还会造成AGV行驶时冲突，则任务可能陷入死锁状态。

为了寻找合适的路径规划算法，许多学者对此进行了深入研究。文献[2]通过区域划分及引入启发式策略，提出基于区域自治的分布式动态路径规划算法，可显著提高路径规划的效率；文献[3]提出了一种将遗传算法和人工势场法相结合的复杂环境下双层路径规划思想，能够提高机器人路径规划能力；文献[4]以AGV运行时间最短为目标，将多种群遗传算法引入到两阶段路径规划策略；文献[5]引入分节拍的处理思想，通过将约束条件变成一种染色体裂变和合并操作结合的遗传算子，对每个节拍内的分拣路径进行优化。

综合以上考虑，对于双向单车道的工作环境，选择了一种通过遗传算法进行求解基于时间窗的最短路径规划方案[6]，用以解决多AGV系统中的AGV集结问题。

1 问题描述与建模

本文假设选定执行协同搬运任务的AGV都处于空闲状态，选定的AGV初始状态可以在路径网络的任意位置，且不受到系统中其他AGV的影响。因此，只要考虑选定执行任务的几台AGV的冲突关系，不用考虑整个多AGV系统里其他AGV的堵塞问题。假定AGV的状态只有匀速行驶、停止和转弯，不考虑AGV遇到障碍以及在交通路口减速加速的过程。

以上述假设为基础，可以得出多AGV系统的时间窗模型为：

(1)

(2)

(3)

本文的优化目标是使所有AGV由初始点到达集合点的用时最短，即到达集合点最晚的那台AGV用时最短。AGV运行时间包括运行时间和等待时间(阻塞时间)，即建立的目标函数如下：

minT=max(Trx+Twx)

(4)

约束条件为：

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

2 改进遗传算法的求解流程

2.1 个体编码设计

遗传算法是一种启发式搜索算法，适应于本文研究NP难的问题。对于路径规划问题，编码方式可以采用AGV的路径串表示染色体，路径串上的一个个路径节点表示染色体上的基因。染色体的长度可变，但是起点和终点由AGV当前位置和目标位置决定。每条染色体的编码不得产生闭环回路，即AGV运行过程中不得回头。

2.2 种群初始化

根据任务选取的AGV数量，确定染色体支线的数量n；根据AGV的初始位置和任务点的位置，确定染色体的头尾基因；查询上位机的路径网络信息以及上位机交通管理的约束条件，从初始点开始，选取任一个可以到达的下一节点作为下一个基因，直到找到终了节点。如果寻找的过程中产生了回路，即寻找到了之前走过的路径节点，则把这段回路整个删除，重新寻找。由于路径网络复杂度不高，因此种群数选为30。重复上述步骤30次，产生一个包含30个个体Si的初始种群。

2.3 适应度计算

适应度是评价个体优劣的衡量指标，适应度越高则个体被选中的概率越高。适应度值计算标准采用如下的评价函数：

(15)

式中：length表示整条路径的总长度；Ni表示路径拐弯点的个数；ti表示由于时间窗调整需要等待的时间；c1、c2、c3表示权重值，且c1+c2+c3=1。

2.4 交叉变异操作

交叉操作是将两个父代的个体提取其中的一部分基因，互相进行替换以及重组生成新的个体，为的是增加个体基因的丰富性。交叉操作是否进行由交叉概率Pc决定，取Pc=1。由于染色体是由N条独立的子染色体组成，因此不能用常规的单点或双点交叉模式。为了保证AGV到达集合点的时间差距不会太大，因此需要保证N条子染色体适应度比较接近，提出一种平均化交叉模式。该交叉模式的基本思想是保证染色体的评价值比较平均，不会出现评价值特别低的子染色体，从而拖慢整体的集合时间。该交叉操作包含以下几个步骤：首先根据评价值从两个父代个体中S1和S2选出最差的一条子染色体，然后将S1中最差的子染色体用S2中对应的子染色体替换掉，将S2中最差的子染色体用S1中对应的子染色体替换掉，从而得到两个子代P1和P2。

变异操作是否进行由变异概率Pm决定，取Pm=0.1。随机的选取每条子染色体的一个基因，然后将其替换为一个新的路径节点位置。

变异操作会有以下几种可能出现的情况：

1) 变异的节点与初始路径无法连通，属于独立于原路径的节点：

对无法连通的子路径段进行节点搜索，增加节点使其连通；

·4，6，9，11，12，15

由图1可知，节点6与路径不相连，因此增加节点补充在路径上，变异后子染色体为

·4，1，3，6，17，9，11，12，15

2) 变异的节点与初始路径重合，则将变异点与重合点之间的节点删除重新选择；

·4，12，9，11，12，15

由图1可知，节点6与路径不相连，因此增加节点补充在路径上，变异后子染色体为

·4，10，2，5，7，15

图1 车间路径网络模型

2.5 基于时间窗进行调整

初始种群和经过交叉变异的种群需要通过调整时间窗，从而解决AGV运行时干涉或者死锁的问题。对于3车集合的问题来说：以集合点为11-12之间的某个任务为例，该任务需要3台AGV共同执行协同搬运任务。随机在种群中选择1条染色体，该染色体由3条子染色体组成，如表1所示。

表1 染色体基因表以及对应的时间窗

通过分析时间窗可知，时间窗冲突如下：

路径15—25，AGV1和AGV3产生了相向冲突，时间窗口为[22.3，33.6]。由于同一段时间窗内，一条路径只能允许一个方向通行AGV，这种路径冲突需要重新规划时间窗；在路径12—终点，AGV1和AGV3产生了同向冲突，时间窗为[39.8,57.7]。由于路径单向可以容纳多台AGV运行，通过分析得出：两台AGV间隔距离>最小运行间隔，并且路径承载数>2，不需要调整时间窗。

有两种方法可以对时间窗的冲突进行调整：延迟时间窗和路径重新规划。

1) 延迟时间窗

该方法是通过暂停AGV的运行，来使得该AGV的时间窗后移，从而解决时间窗的冲突问题。对于路径15—25在时间窗口[22.3，33.6]的冲突，则可以通过延迟AGV1到达时间或者AGV3到达的时间。需要延迟的时间为：

(16)

(17)

通过延迟AGV1时间窗，3台AGV需要花的时间为65.9—30.2—46.8；延迟AGV2的时间窗，3台AGV需要花费的时间为57.7—30.2—60.1。虽然延迟AGV3的时间窗花费时间较多，但是总集合时间较短，因此选择延迟AGV3的时间窗，总集合时间为60.1s。

2) 重新规划路径

对于15—25的路径冲突也可以采用重新规划AGV1或者AGV3的路径，从而避免产生相向冲突。对于两条冲突路径，遵循以下几条原则进行调整：根据到达集合点的总时间进行排序，优先对集合时间最长的AGV进行重新路径规划；将重新规划后的路径与初始路径进行比较，如果增加了路径段，则放弃重新规划的路径，选择次长路径进行重新规划。如本例中对AGV1进行重新规划，路径是21—18—15—12—终点。

重新规划后仅存在通向冲突，并且符合路径的容纳能力，不需要调整时间窗。总的集合时间为46.8s。

综合两种调整方法，选择集合时间更短的重新规划路径法。

2.6 迭代终止条件

如果变异后的连续Nr代子个体中最佳个体没有变化，或者达到了最大迭代次数Nm，则停止迭代。本文中Nr=10,Nm=100。

3 仿真与分析

为了评估该方法的优化性能，对其进行计算机仿真分析。对于路径网格内的12个工作站，生成10个搬运任务，每个任务所需的AGV数量在2-4台之间，并随机生成AGV的初始位置，数据信息如表2所示。

表2 任务以及AGV位置信息

3.1 实验相关数据

利用上文所提出的IGA、传统最短路径算法DGA进行求解路径序列，对结果进行比较。比较集合总时间和死锁次数。采用生产系统仿真软件Plant Simulation进行仿真。设定的AGV运行速度为0.5m/s，每个任务进行100次仿真运行，结果取平均值。

3.2 仿真结果分析

该系统集结效率的评价指标主要有集结时间和死锁故障率。图2对比了3种路径规划方式下，AGV由分散状态集结到任务点需要的总时间平均值。如果实验发生死锁，则该次实验不计入平均时间。图3对比了3种路径规划方式下，AGV由于相向冲突造成的死锁次数，死锁次数越少表示系统运行的可靠性越高，需要人工介入进行调整的概率越小。