一种适用于具有空间-处理混合约束的多机器人处理系统的异构任务分配方法

《Robotics and Autonomous Systems》：A heterogeneous task allocation method for multi-robot processing systems with spatial-process hybrid constraints

　　徐特|李宇|张天一|刘海波|王永庆

摘要：多机器人处理系统在航空航天及其他行业的大型结构件加工与组装领域展现出广阔的应用前景。在具有复杂加工约束的大规模制造场景中，多机器人异构任务分配面临着计算效率低和易陷入局部最优的难题。本文提出了一种基于空间-工艺混合约束的学习-优化耦合框架，设计了一种嵌入动态能力掩码的异构图注意力网络。通过小样本最优解的自监督学习，提取高维拓扑特征，将这些先验知识泛化并应用到大规模场景中，为优化过程提供高质量的概率分布，从而解决初始化问题。基于希尔伯特曲线的空间正则化策略引导优化器在连续概率空间中进行有序的聚类搜索，有效减少了非加工空闲时间，同时严格满足异构任务约束。实验表明，该方法在小规模场景下能够以小于0.7%的偏差逼近精确解；在大规模工业场景（N=150）中，其解决方案的质量比标准算法高出20%以上，且具备良好的稳定性和可扩展性。

引言：在航空航天制造中，大型结构件的自动化加工涉及数百项诸如钻孔、磨削等异构任务。这些任务通常分布在数米范围的空间内，对加工精度和工序顺序有严格要求。为了解决单机器人作业的低效率问题，部署多个机器人（工业机器人、自动导引车和人形机器人）在同一工作台上协同完成异构任务已成为主流趋势[1]、[2]、[3]。多机器人系统具有高并发性和灵活性，对于解决此类问题至关重要。然而，多机器人之间的任务分配本质上是一个NP难组合优化问题。随着任务数量从数十增加到数百，解空间呈指数级增长。核心挑战在于如何快速找到既能匹配异构任务能力，又能确保在大规模工件上实现离散任务分配的高质量分配方案[4]。

目前已有大量研究致力于航空航天结构件装配与制造中的任务分配问题。正如Chakraa等人[5]所综述的，多机器人任务分配本质上是一个NP难问题。虽然基于精确规划的方法[6]、[7]、[8]、[9]能够保证最优性，但其计算复杂度会随任务数量呈指数级上升，因此不适用于处理大型航空航天结构件上数百个加工点的在线分配问题。遗传算法和灰狼优化算法等元启发式算法具备解决大规模问题的潜力，但现有研究大多采用通用的随机排列编码策略，该策略无法考虑飞机表面任务点呈聚集或线性几何分布的特点。因此，生成的机器人轨迹虽符合工艺逻辑，但在物理空间中会出现混乱的来回跳动，增加空闲移动时间。此外，这些方法未能利用相似工序的空间聚类特性，导致频繁更换末端执行器而造成额外的时间损失。综上所述，现有针对航空航天制造的MRTA研究在面对具有严格几何约束的大规模场景时仍显不足。

鉴于上述挑战，本文提出了一种由空间约束和工艺约束驱动的双约束学习-优化耦合框架。其核心思想是将大规模组合优化问题分解为两个阶段：异构任务匹配和细粒度时间优化。为解决初始化问题，我们采用图注意力网络（GATv2）从小规模最优解中学习任务与机器人的匹配模式，再将这些先验知识泛化并应用到大规模场景中，为优化算法提供高质量的概率分布以实现快速启动。为弥补空间感知方面的不足，我们引入希尔伯特曲线来建立空间拓扑约束，引导机器人喺连续空间中形成有序的任务集群，从而在算法层面减少冗余移动。本文的主要贡献如下：
(1)提出了一种基于能力掩码的异构图编码机制，通过在图注意力网络输出端添加动态掩码层，有效过滤非法任务分配，解决了传统方法在早期搜索阶段产生大量不可行解导致的收敛缓慢问题。
(2)设计了一种基于希尔伯特曲线的空间拓扑约束策略，将希尔伯特指数惩罚项纳入灰狼优化器的适应度评估中，利用其空间局部性保持特性，引导机器人任务序列形成有序的空间集群，大幅减少长距离的空闲移动。
(3)建立了一种受物理约束的混合求解机制，不同于将神经网络与启发式求解器简单结合的传统方法，我们的框架将严格的制造约束（通过动态能力掩码）结构化地嵌入深度学习输出中，使得图神经网络的粗略预测能够转化为灰狼优化器安全且可信的搜索边界，从而实现大规模系统（N∈{100,150}）的快速收敛以及100%的约束满足，无需复杂的后期处理修复机制。

相关研究：多机器人任务分配是机器人学领域的核心挑战之一。根据Chakraa等人[5]的系统性分类，MRTA方法主要分为基于市场机制、基于行为机制和基于优化机制三类。基于市场机制和行为机制的方法在去中心化环境中具有较高的灵活性，但在航空航天制造典型的严格空间-工艺约束下往往难以保证全局最优性。

符号与假设：本文研究的是在一个工作台上多个机器人协同完成异构任务的加工系统，目标是处理大型航空航天结构件。该问题被建模为一个具有异构能力和工艺约束的多旅行商问题。系统包含一组异构加工任务T={t1,t2,…,tN}和一组机器人R={r1,r2,…,rM}。每个任务ti∈T可由五元组表示：ti=〈pi,ψi,τi,Ci,Pi〉，其中pi∈...

方法论：本研究针对航空航天制造中涉及大型部件的多机器人大规模异构任务分配问题，提出了一种由双空间-工艺约束驱动的混合分配框架，将图神经网络与灰狼优化器相结合。通过构建一个将任务和机器人能力以带能力约束的图结构形式表示的图模块，本研究提出了任务-机器人异构图模型。

实验与结果：本章旨在评估所提出的将图神经网络与灰狼优化器相结合的混合框架在解决航空航天制造场景中大型结构件多机器人任务分配问题时的解决方案质量、计算效率以及约束满足能力。

结论：本文研究了航空航天及类似场景中多机器人协同加工大型结构件时的大规模异构任务分配问题。提出了一种由工艺约束和空间约束共同驱动的集成图神经网络与灰狼优化器的双约束分配框架。通过建立小样本学习与大规模泛化的解决方案机制，主要结论如下：
(1)...

CRediT作者贡献声明：徐特：写作——审稿与编辑、写作——初稿、指导、项目管理、方法论、概念设计。李宇：写作——初稿、可视化、软件、研究、正式分析、数据整理。张天一：可视化、验证、软件、数据整理。刘海波：写作——审稿与编辑、指导、资源协调、项目管理、资金筹集。王永庆：写作——审稿与编辑、资源协调、方法论。

利益冲突声明：作者声明没有已知的可能影响本文研究的财务利益或个人关系。

致谢：本研究得到了中国国家自然科学基金（项目编号52475006）和中国教育部基础学科拔尖计划（项目编号JYB2025XDXM208）的支持。徐特于2016年在中国科学院沈阳自动化研究所获得机械工程博士学位，目前是中国大连理工大学机械工程系的副教授。他的研究兴趣包括软件/仿生机器人创新设计与制造方法、深度强化学习智能控制以及智能装备。