近年来，随着智能制造和智能仓储技术的不断普及，自动导引车(AGV)在作业车间和自动分拣系统中得到了广泛应用[1-2]．目前AGV调度研究主要集中在三个方面：a．规划计算量大，基于启发式算法的求解策略广受欢迎[3-6]；b．存在碰撞风险，避障策略的研究成为了当前热点[7-10]；c．集群协调空白，缺乏对于AGV系统真实场景中各种动态特征的考虑．诸多学者对多AGV路径规划与调度进行了研究．基于时序和道路规则约束的A*搜索算法能够有效降低AGV路径代价，对于环境信息的建模更加合理[11]．采用多属性策略能够并行处理多搬运任务的AGV指派决策[12]．利用网格地图并融合Dijkstra算法有助于解决多AGV的路径冲突问题[13]．对于仓储场景下多AGV协调控制问题，二次规划能够最大化车辆的作业量且明显减少不同情形下车辆交互所需的时间[14]．基于时间窗的动态路由策略能够保证延误扰动下多AGV的调度和其鲁棒性[15]．包裹分拣须提升效率，AGV数目的增多造成调度优化复杂性急剧增加，采用分层规划的策略能够有效协调多AGV[16]．此外，关于充电导致的间歇性不可用作业区间也被纳入AGV调度优化决策中[17]．AGV协同调度存在高度的复杂难解特性，现有文献多集中在使用启发式算法进行求解，包括A*算法[10]、遗传进化算法[1,5-6,9]、差分进化算法[2]、花授粉算法[4]、和声搜索算法[18]和鲸鱼算法[19]等，类似的群集规划方法也可见于机器人集群中[20]．针对研究现状和多AGV集群系统的特征，本研究提出一种基于并行A*路径规划和动态适应度遗传算法的集群AGV控制方法．针对双向A*和基于交通规则的动态适应度调整策略进行了计算机仿真和场地测试，重点解决现行遗传算法中普遍采用静态适应度函数和AGV集群控制忽视实际场景的地理信息多样化不足的难题，且融合双车道约束规则，提出面向AGV集群调度问题的优化算法．1 地理建模与问题描述1.1　地理信息与问题特征AGV调度的目标是为不同位置的AGV分配搬运任务，使得总体搬运时长最短．本研究讨论的AGV运行场景为图1所示的智能物流仓储系统，图中：黑色与灰色圆形分别是AGV出发点和货物转入点；灰色双列条形网格代表2×8仓储货架；货架间的双细线代表AGV引导线．为清楚区分，上下引导线为虚线，且左右引导线为虚线．10.13245/j.hust.220521.F001图1AGV仓储地图模型将图1的地图模型作为AGV集群工作环境，并在文献[20]提出的栅格地图基础上添加双车道布局，以降低AGV路径生成的相向冲突．1.2　假设条件基于地图得到相应假设条件：a．双车道条件，AGV运行至某一目标点时须遵守靠右侧道路行驶的交通规则，避免堵塞；b．稳定工作假设，AGV运行速度保持匀速，且能根据电量确定是否接受新的任务．2 路径规划算法2.1　二重并行A*搜索算法路径生成算法主要有A*算法、神经网络、模糊逻辑和人工势场法等[11]．目前应用最广泛的是A*路径算法．A*算法基本过程是从起点依次向外扩展直到搜索到一条可到达目标位置的连续坐标路径，其应用效果已在很多研究中得到验证[21]，具有极强的自适应性，可以解决多种类型的路径问题．在评估函数准确的情况下，A*算法从起点出发搜索到终点时沿最优路径，从终点向起点搜索同样沿最优路径，延伸出两种情况：a．起点和终点之间存在唯一最短路径，则从起点和终点延伸出来时会在最短路径的某处同时搜索到此点，进而提前拼凑得到最短的完整路径，如图2(a)所示；b．起点和终点之间存在多条等价的最短路径，如图2(b)所示，此时起点和终点不一定同时搜索到最短路径上的某一点，且是从其中一点出发搜索到最短路径之一．10.13245/j.hust.220521.F002图2二重并行原理图2中不同颜色代表从不同起点出发生成的路径和搜索的点．对于情况a得到完整最短路径的时间比从起点单向搜索的时长短；对于情况b得到结果不会比传统A*算法更差，因而可以在保持计算质量的前提下充分利用更多的计算资源降低搜索时间．2.2　多重并行A*搜索算法进一步在二重并行A*算法的基础上提出多重并行A*算法并给予理论分析，分为如下两种情况．a．多重并行搜索时中间的出发点c不在或者是在不同的最短路径上，此时这个点为无效果点，对路径规划结果不产生贡献，同时由于A*算法保持向终点最优收敛的性质，因此无效果点对于最后的路径规划结果也不产生负面影响．b．多重并行搜索时中间的出发点在最短路径上，此时这个点为有效果点，其效果可按如下步骤分析．定义S(a，b)为a点到b点的最短路径，AGV运行起止点记作B和E，AGV两点间的路径规划问题就是求出S(B，E)在地图中的表达，取c点位于S(B，E)上，则有S(B,E)=S(B,c)+S(c,E)．从B，E，c三点同时向外搜索时分为以下两种情况．a．在t时刻，从B出发的点搜索到c，从c出发向终点搜索的点到达d，从E出发的点还未到达d，即S(B,E)=S(B,c)+S(d,E)，则此时省略访问S(c，d)的搜索过程．b．在t时刻，从B出发的点搜索到c，c出发向终点搜索的点到达d，从E出发向起点搜索的点已经到达或经过d，并记此时这个从E出发的点的位置为新的d，即S(B,E)=S(B,c)+S(c,d)+S(e,E)，此时省略了访问S(c，d)的过程，减少了A*的搜索时间，其余情况则可以视为B和E调换位置以对应至上述两种情况．图3(a)给出了多重并行搜索到有效点时的状态，图3(b)给出了搜索到无效点的状态，前者减少搜索时间，后者也不会导致更差的解被选中．10.13245/j.hust.220521.F003图3多重并行原理2.3　有效点选择上述分析基于有效点这一假设得出，本研究给出两种选择有效点的方法．a．对角线法：如图4(a)所示，选择一条对角线，将对角线上每一点都作为中间点向外搜索．b．对称线法：如图4(b)所示，选择两点构成的矩形坐标区域的两条对称线，将线上所有点作为中间点向两端搜索．10.13245/j.hust.220521.F004图4选择有效点方法3 自适应遗传算法用于AGV调度的遗传算法依赖于地理信息的特征和问题建模方式．现有研究都是围绕特定细节修改遗传算法的参数从而产生合适的规划结果．对于遗传算法在AGV调度领域的研究聚焦于性状保留、变异算子和种群设计等环节[22]，而在真实场景中的效果和部署难易程度等较为缺乏．实际应用中的AGV地图特征由于环境因素并非不变，在固定的适应度函数下并不能始终准确对当前地图环境进行求解优化．为此，提出基于动态适应度函数的自适应遗传算法，针对地图的变化动态地修改对基因的评价指标，从而保持算法对问题的寻优．遗传算法在AGV调度优化的作用是基于基因突变和优胜劣汰的思想对任务调动进行重新组合，直到生成最优的一组执行序列．本研究基于上述多重并行A*搜索算法求解速度快的特点，将路径规划结合到遗传算法中，降低遗传算法在适应度计算环节对于静态环境因子的依赖[22]，使调度算法可以根据不同的地图以自适应方式产生准确的评估，进而维持实际可信度，具体步骤如下．a．编码．本研究采用整数编码方案，每一条染色体由多个AGV的配送序列共同组成，配送方式为一台AGV运送一个包裹．采用整数编码的方式生成一条由自然数组成的数组，数组索引序号即为AGV编号，数组元素为AGV搬运货物的任务代号，计算AGV搬运任务耗时的过程就须要根据任务代号确定货物搬运的目的地，进而为后续计算适应度提供依据．b．初始化种群．初始化种群由随机方法生成，初始解规模取决于任务规模，以一台AGV搬运一个货物为例，搬运包裹的数量越多，所需要的初始解的数量越大，这是模拟自然界人口数越多基因质量越高的情形．c．交叉．交叉是从亲代中以随机方式继承性状的过程，本研究采取部分匹配交叉算子，将父代中的顺序信息保存到子代，得到新的个体．以元素不重复的数组作为遗传算法的染色体，采用部分映射交叉的方式进行交叉操作．具体是在两个规划出来的解中设置交叉区间，对区间内的数组元素直接交换．根据交换区间内的元素建立映射关系，而后完成染色体调整，将重复的基因替换并得到两条全新的元素不重复数组．d．变异．变异的目的是帮助种群跳出局部最优的困境，本研究按照随机概率P对部分个体的顺序进行局部调换，以保证算法保留跳出局部最优的能力．采用基本位变异方法进行操作，具体来说，若为偶数位染色体，则指定染色体数组的中间两位元素以概率P交换位置；若为奇数位，则指定中间位两侧的元素交换位置．这样就可以实现对搬运顺序随机调整，进而保留跳出局部解的能力．e．选择．采用轮盘赌方法作为选择算子，因其具有放大优势个体降低劣势个体的效果．对于AGV系统来说，更快的收敛速度对应更快的响应速度，在此条件下即便搜索到的解不是最优也是可以接受的近优解．f．动态适应度函数．适应度是个体对环境的生存能力的综合评估，本研究以考虑地理约束的A*算法实际搜索得到的预估成本，而非基于某种规定规则的距离和其他系数组合而成的函数形式，此方法能最大程度保留对路径规划结果的原始判断，让算法得以继承A*算法的自适应特点，具体流程如图5所示．10.13245/j.hust.220521.F005图5动态适应度流程在此基础下，对于不同的环境特征，只须要在A*算法搜索路径时增减新的约束即可保持对新环境的判断．在地图发生变动之后，只须将工作的坐标系根据地图变动进行修改，如增加新的可行点、可行线等新的地图元素，随后就可用同样的A*算法在新的地图上进行规划路径，而不须要调整修改集群调度算法的结构．寻找到最优路径或达到给定的迭代次数，即输出优化结果，算法终止．4 仿真与测试基于Python实现了传统A*算法和并行A*算法，对其迭代次数进行对比并显示单台AGV完成所分配全部任务的运动轨迹．实际场景设置三台AGV用于完成30个货物的取件工作，三台AGV起始位置、货物的位置和货物终点的位置由随机整数生成．4.1　计算仿真计算机仿真分为两个场景，分别为多AGV调度和单一任务执行轨迹分析．在多AGV调度部分，图6(a)为本研究设计的一个长度为1 m的正方形无障碍场地，在内部设置随机坐标并用于模拟AGV移动，图中：星型图案代表随机货物；左侧三个黑色图标代表三台AGV．为便于观察，后续实验选取其中单台AGV的运动轨迹展示．图6(b)为用于分析单一任务的场地模型，测试本研究提出的改进A*算法路径规划效果，图中：黑色为不可访问区域；白色为可访问区域．10.13245/j.hust.220521.F006图6计算机仿真实验环境为验证设计的AGV调度算法，在设置的仿真环境中进行测试，并生成路径轨迹和集群调度收敛曲线．图7(a)为本研究集群调度中单台AGV的运动轨迹，两点之间的路径通过双重A*算法得到．图7(b)为自适应遗传算法的路径总长度的收敛情况，图中：L为根据A*算法搜索得到集群调度的总长度；n为遗传算法的迭代次数．10.13245/j.hust.220521.F007图7AGV调度实验结果当前不少研究对A*算法进行了改进，本研究将蚁群融合的A*算法[23]作为现有A*算法代表，将其与提出的并行A*算法对比．考虑到多重A*算法面临的算力需求，在此仅针对二重A*算法进行对比．图8显示了两种A*算法的实时计算过程，模拟任务从左下方蓝点出发，要求到达右上方浅绿点，图中：红线为最终路径；灰色的点是从起点出发探索过的空间；浅蓝色的点是从终点出发探索过空间．10.13245/j.hust.220521.F008图8不同A*算法求解过程对比灰色部分越多说明搜索路径访问的点越多，费时越长，本研究采用的并行方法灰色区域小于融合蚁群的A*算法，且能找到最优解，意味着在更短时间内寻找到最优路径．图8中基于并行搜索的A*算法得到的最短路径和融合蚁群A*算法得到的最短路径等价，证实了本研究提出的并行A*算法在不产生更劣解的前提下使用更多的计算资源降低了路径的生成时间．图8(b)中被搜索过的点在整个地图中分布更加均匀，可以看出本研究对空间的搜索程度远大于现有的A*算法．由于本研究采用的A*算法是基于多点并行搜索，在空间内生成多条路径，合并后作为有效结果，因而具有群体协同搜索特性．图9测试了本研究提出的路径算法在不同取货地形下的路径效果，图中黑色与白色部分分别代表障碍和可行区．图9(a)为本研究算法在简单障碍物地形的路径规划结果，图9(b)为复杂障碍物地形的路径规划结果．本研究提出的并行A*算法保持了A*算法生成路径简洁的优势．10.13245/j.hust.220521.F009图9不同取货场景下的路径规划性能4.2　实际场景测试本研究搭建了基于Linux系统和WiFi远程通信的AGV运行系统．图10为根据图1中的地图核心特征重新简化构建而成的实际工作分区示例，取消了图1中的货物转入转出区和AGV等待区，图中：下侧为用于出货的四个搬运终点，分别用数字1～4标记；上侧为三个标记出的货物．10.13245/j.hust.220521.F010图10AGV实物测试场景表1给出了AGV基本运动相关模块的性能参数，参数误差范围为5%，三台AGV硬件参数和程序统一设定，在实际测试中可以认为是同构AGV．10.13245/j.hust.220521.T001表1AGV基本性能参数性能项目性能数据车体高度/cm36车体长度/cm35车体宽度/cm22传感器识别线宽/mm16车轮轮径/mm60电机额定转速/(r∙min-1)140实际测试场地由白底黑线组成，用以模拟地图模型中的坐标分布．图11(a)中的三台AGV位于初始点，且处于从右往左数的奇数线上模拟双车道交通规则．图11展现了AGV实际运行效果的图片，AGV从图11(a)中的三个起点分别出发，向调度算法为每台AGV分配的任务对应的位置移动，到达图11(b)中的三处地点并调用机械臂完成模拟搬运．10.13245/j.hust.220521.F011图11集群调度实景实验图12为添加了障碍物之后的双车道地图场景，用于模拟由于货架建筑结构等因素导致地图栅格被占据的特殊情况．它在完全自由场景的基础上增加了六个障碍物并调整了任务目标后的场景，其中上下只有4条车道可以使用，前面测试时中间的一条车道和最左侧车道因为障碍物而无法使用．表2展示了设置不同障碍物数量和不同规模搬运任务时的平均寻优迭代次数，调度算法的平均寻优迭代次数超过2 500则认为超时．由于障碍物减少了A*算法搜索的区域，因此路径生成速度加快，进而限制了遗传算法向不良解的搜索倾向．随着障碍物增多，生成可行解所需要的代数越少，体现了本研究所提出调度算法在基于双车道规则下对于障碍物环境极强的适应性．10.13245/j.hust.220521.F012图12增加障碍物后的实景10.13245/j.hust.220521.T002表2不同环境下算法平均寻优迭代次数jm309015018030024661 0051 566——34359581 576——43809031 5561 953—53778461 5231 940—63618401 5111 9302 416注：—表示超时无解；m为须要搬运的包裹数目；j为障碍物数量．对于传统的静态遗传算法，由于障碍物环境下无法用曼哈顿距离估计路径长度，须反复修改适应度函数，因此效果无法在实际环境中保证．基于本研究采用的动态适应度函数，在新地图上进行AGV集群调度无须针对障碍物修改算法结构，只须在A*算法求解路径的环节设置相应的不可访问点，即途中被板凳挡住的车道在A*算法求解时变为不可行车道．本研究以双向A*算法搜索的路径长度作为实际路径成本，当评价染色体适应度时即可自适应调整为新环境下的真实适应度，从而实现遗传调度算法框架对环境的自适应调节．5 结语本研究针对现行AGV集群调度研究的特点，分析了路径规划对于AGV集群调度的影响，提出一种基于并行搜索的自适应遗传算法求解思路．通过对适应度函数进行调整，尽可能向真实结果靠近，瞄准A*搜索加速，降低了对人工修正系数的依赖，保持了A*算法搜索快、适应性强的特点，能更好兼容真实环境中的动态仓储地理信息．分别进行了计算机仿真和实际场景测试，为AGV集群调度算法的开发应用提供了参考．下一步拟就AGV集群系统动态监测与实时数据进行深入研究．