重大装备制造多机器人任务分配与运动规划技术研究综述

张振国 毛建旭 谭浩然 王耀南 张雪波 江一鸣

飞机蒙皮、船舶舱体、高铁车身等大型复杂部件高效高品质制造是航空航天、海洋舰船、轨道交通等领域重大装备发展的根基,是国家加快培育及发展的战略性新兴产业,在引领国民经济发展、服务国家重大需求等过程中发挥着至关重要的作用[1].

如图1 所示,大型复杂部件具有尺寸超大、工序繁多、结构弱刚性、型面复杂等特点[2],其制造面临规模大、任务多、精度高等难点.近些年来,大型复杂部件制造已经进入初步发展阶段,现有大型复杂部件制造模式主要依赖大量人工、专机设备、多机器人产线.人工加工存在一致性差、效率低下等问题,单机加工存在柔性不足、空间有限等问题,已经成为大型复杂部件制造中迫切需要解决的难点.而由多个单体机器人组成的多机器人制造系统能够增加机器人作业的适应能力与柔顺程度,因此被广泛应用于加工、装配等关键制造过程中.

图1 重大装备加工需求Fig.1 Major equipment processing needs

多机器人系统是机器人技术最广泛的研究领域之一,相比于数控机床与单机器人,多机器人系统具有高效、灵活、鲁棒性强、并行协调作业能力强等优点,能够适应复杂的制造环境[3]:

1) 高灵活性: 多机器人可以通过灵活协同作业解决复杂问题;

2) 高效性: 通过多机器人协同完成任务以提高作业效率;

3) 高鲁棒性: 当多个机器人完成一项任务,其中一个机器人出现故障,其他机器人仍然可以完成这项任务.

这些优势吸引了许多学术界和工业界的研究人员来调查多机器人在工业和商业重要领域的适用性,近年来多机器人系统一直出现在机器人领域的议程上.2011 年,哈佛大学研究出了一种低成本、适合大规模实验的多机器人系统Kilobot,并开展了多机器人组队实验[4].Nature发文报导了一种自组织仿生多机器人,具有更强的可扩展性和鲁棒性[5].Science杂志上发表了多机器人智能强化学习的研究,可以在动态约束的环境下进行强化学习[6].

但简单地把多个机器人堆砌在一起,不但不能实现多机器人系统的优势,反而有可能由于其行为上的并行性和突发性、位置上的冲突性等,引起机器人之间的冲突与对抗,使得整体性能降低,导致大规模多机器人系统的整体优势无法充分发挥[7].因此需要研究多机器人在什么时刻、应采取什么动作、调用多少机器人去实现多机器人之间的协作合作,即复杂环境下的多机器人任务分配与运动规划是决定多机器人良好合作基础的决策中枢.

如图2 所示,多机器人任务分配和运动规划以环境地图信息为基础,为重大装备大型复杂部件制造提供任务序列及运动轨迹,在制造过程中占据着重要的作用,其与机器人数量、种类以及复杂的动态环境息息相关,而分配和规划过程中的计算量以及效率、安全性都十分重要.随着科技的发展,多机器人任务分配与运动规划也逐步应用到各行各业.在增材制造领域,Zhang 等[8]建立可扩展多机器人三维打印任务分配和路径规划框架,使机器人群能够在整个建筑任务中打印任意的几何图形.在森林搜救领域,Foehn 等[9]通过引入沿轨迹公式优化时间分配和轨迹规划,完成飞行机器人群检测、搜索和救援等任务.在人机交互领域,Ali 等[10]提出了一种基于机器人-人体信任的异构人机团队任务分配方法,以提高人机团队任务分配效率.协同加工领域,Suárez-Ruiz 等[11]使用Bi-RRT 轨迹规划方法,完成对椅子完整的组装.Li 等[12]通过使用基于强化学习的运动规划策略,完成机器人智能化烹饪任务.

图2 任务分配与运动规划在多机器人制造过程中的重要性Fig.2 The importance of task allocation and motion planning in multi-robot manufacturing

综上所述,在大型制造场景下为提高多机器人制造效率,通常对多任务多工序同时进行,然而多机器人同时段完成多个任务带来严重的协同干涉问题,同时大型复杂部件高的精度需求为目前亟待解决的难题之一.因此面对大型复杂部件制造规模大、任务工序多、冲突干涉多、精度需求高等挑战,如何使用适合的任务分配和动态规划方法,以提高多机器人制造过程中的作业效率、安全性、鲁棒性是亟待解决的关键性问题.因此本文在多机器人大型复杂部件制造的背景下,首先对多机器人任务分配和动态规划方法的重要性进行分析,然后阐述了近些年来任务分配和动态规划的方法,其次对复杂作业场景下大型部件多机器人制造任务分配和运动规划进行了展望,在此基础上给出了解决问题的新思路,最后对所研究内容进行总结.

1 多机器人任务分配方法研究

如图3 所示,多机器人任务分配过程可以表述为最优分配问题,其目标是给机器人分配任务,同时在约束条件下优化整体系统性能,实现整体执行效果最佳,多机器人任务分配是协同作业最具挑战性的问题之一[13].一方面,任务分配会直接影响到整个系统的效率;另一方面,当其中一个机器人没有完成任务时,通过有效的协商分配使多机器人协作完成任务成为更多学者关注的问题[14].尽管现有研究存在大量的任务分配方法,但一些重要的方面至今仍很少受到关注,主要包括复杂动态环境下的任务分配、大范围制造环境下区域划分任务分配、跨区域任务分配和异构机器人任务分配.本节的主要目的是全面回顾任务分配问题,以及解决这些问题的最新方法和未来的主要发展方向.目前,多机器人任务分配方法按照执行模式可以分为集中式任务分配和分布式任务分配,按照方法分类包含基于线性规划的任务分配、基于市场的任务分配、基于启发式的任务分配及基于人工智能强化学习的任务分配等.

图3 多机器人任务分配问题Fig.3 Task allocation problem of multi-robot

1.1 任务分配执行模式

1.1.1 集中式任务分配

集中式方法是研究较多的一类方法,主要思想是采用一个中央处理中心进行分配,并与所有其他服务器有通信渠道.如图4 所示,该处理中心掌握全局信息,决定必须分配给其他服务器的任务.在这些情况下,通常会考虑全局效用函数来与其他服务器进行通信[15].如使用集中式任务分配方法进行多机器人汽车制造与装配工作[16]、多无人机环境检测任务[17],降低任务交付与执行过程中的延时等[18].

图4 集中式任务分配系统Fig.4 Centralized task allocation system

集中式任务分配方法的优点是使用较少的系统资源并具有较低的实现成本,同时避免了任务分配上的冲突,不需要共识阶段,也可以找到分配问题的最佳解决方案.但是任务分配的计算复杂度会随着问题规模增大而呈现指数上升,中央处理中心容易出现过载,其次集中式任务分配不能适应动态环境,主要用于静态任务分配,缺乏鲁棒性,一旦中央处理中心出现故障,将导致整体性能恶化[19-20].常用的集中式任务分配方法包括线性规划方法、启发式方法、强化学习方法等.

1.1.2 分布式任务分配

分布式任务分配方法克服了集中式任务分配的缺点,在过去几年引起了研究人员的关注.如图5 所示,分布式任务分配没有中央处理中心,各个机器人对环境有本地感知,可以彼此相互交流和协商完成任务,因此任务分配的决定在本地以分布式方式通过每个机器人本身的效用函数进行[21].如使用分布式任务分配方法降低多机器人的任务消耗、减小分配时间[22-23],提高制造过程的可扩展性、有效性[24].

图5 分布式任务分配系统Fig.5 Distributed task allocation system

分布式任务分配方法具有强鲁棒性的优点,部分机器人故障对整体性能的影响很小,且机器人之间的通信弱,多机器人呈现强可扩展性.但是分布式任务分配缺乏全局信息,容易陷入局部最优;其次,任务分配决策过程中需要个体之间不断交换信息,当机器人规模较大时算法收敛速度较慢.现有的分布式任务分配方法主要包括启发式方法、市场法等.

1.2 多机器人任务分配方法

1.2.1 基于线性规划的任务分配方法

优化是应用数学的一个分支,目的是从一组可行解中找到问题的最优解,这组可行解受到约束的限制,利用约束的限制定义问题的目标函数,定量描述了系统的目标[25].基于优化算法提高了在处理有噪声输入数据时的适应性能,在未知空间中探索新区域方面具有更高的潜力[26].基于优化的方法可以按照目标类别分为确定性优化和随机优化,线性规划方法是确定性优化之一,其思想是通过将实际的任务分配问题转化为求解数学模型的问题,并利用线性规划技术进行求解.近些年来混合整数线性规划(Mixed integer linear programming,MILP)由于其严谨性、灵活性和广泛的建模能力,已成为分配问题最广泛的方法之一[27].

基于MILP 的分配方法最初应用于化学工程和运筹学中,Reklaitis 等回顾了对于批处理操作的分配和规划,重点关注任务分配的基本组成部分和可用的解决方法[28].在多机器人任务分配领域,Bererton 等采用线性规划方法解决了多机器人协作探索中的任务分配问题[29].Schumacher 等为保证多机器人在有限时间内解的存在,采用MILP 开发了一种最优任务分配和定时方法,可用于以最优方式将所有任务分配给具有涉及时间和任务顺序约束的耦合任务的飞行器组[30].为解决任务分配极大极小问题,聂明泓等基于MILP 模型,提出一种矩阵算法,并与穷举解及传统MILP 解的计算复杂度进行了比较,理论分析和数值试验表明矩阵作业法对极大极小和总体极小任务分配问题,都能有效地提供最优解[31].为完成任务分配的周期时间最小化,Åblad等设计了一种时空负载均衡与协调方案,使用MILP模型指导任务分配、序列和机器人运动(路径和速度)来防止机器人与机器人碰撞[32].

尽管基于线性规划的任务分配方法可以获得全局最优解,但由于多机器人数量和任务众多,求解时间随着问题规模的增加呈指数增长,导致计算量增大、实时性差,在此情况下计算全局任务分配的最优解比较困难.因此,近几年来在多机制造领域常与其他方法一起使用.Spensieri 等结合混合整数线性规划方法与基于市场广义旅行推销员问题方法,解决汽车制造站多个工业机器人协作任务分配问题,避免了多机器人任务冲突[16].针对外界威胁下的任务分配和操作顺序规划会降低性能和成功率问题,An 等通过采用MILP 和势场法结合,提出了具有实时路径规划的任务分配方法,同时设计了任务选择算法来补偿修改后的次优MILP 问题[33].考虑多个无人机环境检测之间的任务分配问题,Hu等针对一组预定的地面目标执行攻击任务,将原始问题分解为三个级别的子问题: 目标聚类、聚类分配和目标分配,前两个子问题分别采用聚类算法和整数线性规划集中求解,第三个子问题采用混合整数线性规划模型和改进蚁群算法,以分布式和并行方式求解,仿真实验证明所提出的分层方法可以大大降低任务分配问题的计算复杂度[17].

如图6 所示,基于MILP 的方法具有很高的严谨性,且可以获得全局最优解,但尽管如此,如何解决线性规划算法计算量大、计算时间长仍是具有挑战性的问题.

图6 基于线性规划的任务分配方法[16-17,33]Fig.6 Task allocation method based on linear programming[16-17,33]

1.2.2 基于启发式的任务分配方法

启发式方法是随机优化算法的一种,利用系统已有的经验启发选择,保证空间搜索有效性,加快了算法收敛速度,可以快速找到近似最优解.相比于线性规划而言,启发式搜索方法更适合大规模动态的应用场景,按照优化方法分为模拟退火算法、进化算法以及群体智能算法等.

模拟退火算法是由Kirkpatrick 等提出的一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解[34].Wang 等采用多旅行商方法(Multiple travelling salesman problem,MTSP)优化系统模型,在每个机器人搜索任务区域数量均衡的前提下建立目标函数,并使用分布式模拟退火方法来解决大场景下多机器人系统的分配问题[35].针对异构分布式系统的任务分配问题,Attiya 等提出了一种新型模拟退火启发式算法,建立了一个成本函数的可靠性分配模型,提高了系统可靠性[36].但是模拟退火法存在收敛速度慢,执行时间长,算法性能与初始值有关及参数敏感等缺点,在降温时间设置过快的情况下,无法确保得出全局最优解.

群体智能算法是一种生物启发式算法,在自然界中,生物个体能从成群的行动中获益.个体和集体行为模型表明,相互作用可以呈现出群体形态,组成了能够集体处理信息和提供决策的团体.通过共享信息,群体可以比个体做出更好的决定,被称为“群体智慧”[37].群体智能算法是一种新兴的演化计算技术,已引起越来越多研究者的关注,它与人工生命特别是进化策略以及遗传算法有着极为特殊的联系.Li 等考虑智能仓库系统任务分配问题,通过最小化最大完成时间来降低机器人的总成本,考虑聚合程度最小化所有订单的运输协同效应总和,提出了改进的粒子群算法,有效解决订单和任务的积压,从而提高存储系统的效率[38].Panerati 等提出了一种蜂群启发式算法,其中分布式机器人导航控制器负责保证连接性和对多个任务的追求,全局任务分配控制器以最小的计算负载逼近最优策略,解决多机器人多任务的空间覆盖问题[39].利用机器人在空间中移动时交互过程将任务分配给每个机器人,Mayya 等基于蚁群算法建立一个分析模型来描述在密集的机器人群中发生的相遇,允许多机器人根据当前分配与期望值的距离来调整任务之间的传递速度,最终促进机器人不间断地执行任务[22].在车轮装配过程中,Geetha 等为完成最佳公差分配,通过最小化制造成本(公差和质量损失成本的总和)和机器闲置时间成本来分配组件公差,并开发了一种遗传算法,用于分配组件的公差并确定分配的最佳产品序列[40].

如图7 所示,启发式算法保证了空间搜索的有效性,提升了算法的收敛速度,可以快速找到任务分配的近似最优解.然而,启发式算法在面临复杂的搜索空间时,无法保证搜索效率以及解的全局最优性.同时,群体智能方法利用个体之间的相互协作和信息分享求解优化问题,具体阈值设置依赖具体任务,通用性受到限制.

图7 基于启发式算法的任务分配[34,40]Fig.7 Task assignment based on heuristic algorithm[34,40]

1.2.3 基于市场的任务分配方法

在经济理论中,拍卖是由交易所的交易规则机制来定义、根据投标人的出价和拍卖标准分配一组商品或服务的过程.基于拍卖的概念提出了一种协调机器人/代理之间活动的方法,即基于市场的任务分配方法.由于基于市场的分配方法满足目标函数的高效性、高鲁棒性和可扩展性,在机器人领域获得了较大的关注.机器人团体会根据自己的能力竞标任务,寻求机器人效用优化的目标函数,以执行特定的任务[41].

为解决自动驾驶汽车的协调任务分配问题,Choi 等利用基于市场的分布式决策策略作为任务选择的机制,并使用本地通信的共识例程作为冲突解决机制,使中标值达成一致.在评分方案的合理假设下,所设计方法被证明能够收敛到无冲突赋值,与现有的基于拍卖的任务分配算法相比,具有更好的收敛特性[42].考虑到机器人协作过程中能量消耗过快的因素,Wu 等设计一种基于基尼系数的任务分配方法,将市场分配机制融入到基于基尼系数的方法中,可以根据应用环境减少同等任务完成次数时的资源消耗[43].针对通信范围受限的动态环境中多无人机的任务分配问题,Oh 等提出了一种新型市场分布式任务分配方法,所提算法具有多项式时间复杂度,数值仿真结果表明在通信受限情况有效提高了算法的可扩展性和有效性[24].为保证飞机装配任务下有效使用协作机器人及无碰撞分配任务,Tereshchuk 等利用工件几何形状和问题结构,在标称条件下生成平衡且无冲突的机器人分配计划,随后使用基于市场的优化器来分配处理任务故障,以减小任务分配计算时间[23].为解决集装箱的协同搬运问题,Chen 等基于轨道式堆场起重机和AGV 分配一体化问题,提出了市场驱动方法,通过迭代调整每个子任务的原始成本和双重成本,获得具有成本效益的解决方案[44].

综上所述,基于市场的任务分配方法具有良好的可靠性、可扩展性,但在设计成本函数和收入函数时缺乏形式化.此外,谈判协议、成本函数及引入相关的惩罚方案可能会使任务分配方法设计复杂化,从而导致过度的通信和计算,产生较差的解决方案.

1.2.4 基于学习的任务分配方法

在大型复杂部件制造过程中机器人种类多样、任务繁琐,难以预测机器人需要处理的未来干扰,尤其当无法获取环境的数学模型时,实际应用动态多变.为了解决该问题,机器人采用自身和其他机器人过去的信息,学习面对这种干扰,从而提高系统的鲁棒性[45].近些年,随着以深度学习、强化学习为代表的人工智能技术在越来越多领域取得突破,研究者尝试将人工智能方法引入至多机器人任务分配问题.

强化学习是一种典型的机器学习技术,中央处理中心利用过去的信息学习如何在不同的环境下行动.外部环境通常被描述为马尔科夫决策过程(Markov decision processes,MDP),被中央处理中心优化为成本函数或奖励函数,从而让机器人在环境中进行学习.Wilson 等将强化学习方法应用到多任务分配问题中,使用分层贝叶斯无限混合模型对MDP 的分布进行建模,分层贝叶斯框架提供了强大的先验条件,能够根据过去的环境快速推断新环境的特征,同时使用非参数模型快速适应遇到的未知环境.在仅观察少量任务时,所提出方法可以显著加快收敛到最优任务分配策略的速度[46].为降低任务交付和执行阶段的延迟,Mai 等提出了一种进化策略的强化学习方法,在云服务器之间进行实时任务分配,以减少长期内的总计算延迟,实验结果表明所提出的方法将延迟降低了约16.1%[18].为了将任务安排给合适的机器人以实现不同的目标,Sun 等首先通过深度学习模型门控循环单元预测即将到来的任务和机器人的种类、数量,然后研究了基于深度Q 网络 (Deep Q-network,DQN) 和双DQN (Double deep Q-networks,DDQN) 的自适应批处理策略,以解决任务分配的环境适应和动态批处理问题[47].针对大规模、动态任务分配过程启发式方法计算困难问题,Wang 等提出基于图神经网络的分配方法,自动学习分配过程问题的特征,克服大规模任务分配的局限性,完成高质量任务分配[48].Choudhury 等考虑在时间窗口约束和任务完成不确定性下将任务动态分配给多个机器人,提出了一种多机器人随机冲突深度学习分配算法,提高了机器人数量的可扩展性,并通过多臂传送带拾取和放置等任务验证了所提出方法的有效性[49].

如图8 所示,机器学习模型具有泛化性和高鲁棒性,可以很好地适应高度动态的环境.但奖励函数设计困难、采样效率堪忧等仍然是机器学习方法亟待解决的问题.因此,如何针对复杂作业场景多机器人任务分配设计高效的机器学习模型仍处在探索阶段.

图8 基于学习的任务分配方法[46-49]Fig.8 Task allocation method based on learning[46-49]

1.2.5 混合式任务分配算法

通常情况下,仅使用一种任务分配算法难以满足复杂制造场景下多机器人任务分配的需求,因此需要两种或以上的方法进行结合使用.利用线性规划算法高严谨性的优势,Spensieri 等与市场法结合完成汽车制造问题[16],An 等与势场法结合补偿陷入局部最优问题[33],Hu 等与蚁群算法结合降低计算的复杂度[17].

Zhou 等考虑多机器人多工位协同点焊任务分配问题,构建了一个通用优化模型,以提高相关算法在实际应用中的适应性和可行性,使用通过迭代梯形加速和减速运动的求解器来解决单机器人任务分配,在此基础上采用针对机器人之间具有众多约束条件的焊接任务分配问题,并结合遗传算法迭代求解多任务焊接问题[50].Tereshchuk 等考虑多个协作的机器人机械手来组装大型飞机结构需要离散的如钻孔和安装紧固件的任务,减少工具更换产生的大量时间成本,提出了一种混合式任务分配算法,首先调整基于迭代拍卖的方法,使用启发式方法对优先级关系进行编码,其次开发一种机器学习方法,根据问题特征自动选择有效的分配启发方法[51].考虑大型航天器复杂的内部结构问题,Liu 等提出一个冲突模型来描述特定任务的冲突约束,在每个工作区域中定义了干扰区域,开发一种结合启发式与迭代本地搜索的快速施工启发式方法,以最佳效率搜索任务进度[52].Paiva 等提出了一种使用图搜索算法、启发式方法和机器学习方法结合来解决作业排序和工具切换问题[53].

如图9 所示,混合式任务分配算法可以结合两种方法的优点,完成更优的任务分配效果,但是如何在不产生额外的损耗下体现两种方法的优势还需要更多的研究.

图9 基于混合算法的任务分配方法[50-53]Fig.9 Task allocation method based on hybrid algorithm[50-53]

1.3 复杂制造场景下多机器人任务分配

大型复杂部件制造场景具有制造规模大、任务工序多、冲突干涉多等难点,需要将复杂作业场景进行区域划分避免多任务之间的干涉冲突.同时对每个区域内的任务与多机器人进行作业分配.当所在区域需要其他区域协作时,采用跨区域分配方法.

1.3.1 作业场景区域划分方法

为了防止复杂制造场景下多机器人及多任务之间的干涉冲突,对作业区域进行划分,以保证高鲁棒性的任务分配过程.如图10 所示,Fung 等[54]为减少重复工作并减少每个机器人之间的干扰,提出了一种信息速率自适应采样方法,用于在环境中采集机器人任务与传感器测量值,并根据探索区域所需的工作量划分为不同的子区域.

图10 不同数量机器人情况下区域划分[54]Fig.10 Area division under different number of robots[54]

Shi 等[55]考虑了异构机器人群对环境特征采样和建模的影响,提出了一种环境分区方法,结合高斯过程模型学习框架,以高效和可扩展的方式对环境进行自适应采样和区域划分建模,在空地协同下验证了所提方法的有效性.

1.3.2 基于复杂场景制造的任务分配方法

针对复杂制造场景任务工序多的特点,为了将多任务工序准确地分配给每一组机器人,以提高系统的可靠性和效率,完成多机器人高效高质量作业.如图11 所示,Lopes 等[56]将焊接生产线任务分配问题建模成混合整数规划模型,并使用求解器求解,此方法简单精确、获得了任务分配的全局最优解.

图11 复杂作业场景下多机器人任务分配[56,58]Fig.11 Multi-robot task allocation in complex operation scenarios[56,58]

Mitiche 等[57]提出了一种基于插入式的启发式算法,解决了静态时间扩展多机器人的任务分配问题.Ham 等[58]使用大邻域搜索算法解决了波音777 飞机装配中的多机器人任务工作顺序分配问题.Huang 等[59]采用基于Distributed-Q 算法的强化学习模型,解决了多机器人协同加工过程任务分配问题.Gil 等[60]采用分层强化学习解决了大规模复杂环境下的多机器人任务分配问题.

1.3.3 跨区域任务分配方法

复杂场景下多机器人协同作业过程中,当本区域机器人无法满足作业条件时,采用跨区域任务分配策略.

如图12 所示,Yu 等[61]考虑多机器人分配在空间和时间上的复杂性问题,基于新型染色体的编码格式,提出了一种新型改进遗传算法,不仅可以完成多异构无人机跨区域协调任务分配,而且考虑任务需求,将完成任务的机器人返回至适合的基地而不是必须返回至初始基地.Zhang 等[62]基于改进贪婪算法,提出了一种基于在线分配模型的跨区域任务分配方法,并通过离线指导和在线分配策略来优化任务分配流程,可以在同样时间内完成更多的任务以提高效率.

图12 多机器人跨区域任务分配[61-62]Fig.12 Multi-robot cross-region task allocation[61-62]

如表1 所示,目前多机器人任务分配在制造领域得到了一定的研究进展,在严谨性、鲁棒性、收敛速度等方面取得了研究成果,但在模型设计复杂化、环境规模增大导致求解空间的复杂性、最优性等方面还有待提高.对于复杂场景下多机器人制造任务分配还有一定程度的欠缺,尤其是作业场景区域划分方法及跨区域任务分配方法,还需要进一步的研究.

表1 任务分配方法分析Table 1 The analysis of task allocation

2 多机器人运动规划

在多机器人大型复杂部件制造过程中,需要不断通过中央处理中心将机器人从起始位置移动到目标位置,在此过程中,机器人必须始终能够避开障碍物与其他机器人,以保持安全[63].

运动规划是指根据任务给定的起始状态和目标状态机器人的运动方程,建立满足特定约束条件的数学函数路径表达式,约束条件主要包括运动学约束、动力学约束、路径约束、障碍约束或能量约束等.运动规划包含路径规划和轨迹规划,是机器人领域的研究热点之一[64].路径规划的目的是寻找连接起始状态和目标状态序列点的策略,使寻找到的序列点与障碍物之间的距离尽可能远,同时到达目的地的路径尽可能短.轨迹规划是在路径规划的基础上加入时间信息,使用时间二次积分多项式形式表示,通过对时间求一阶与二阶导数获取机器人从初始状态到目标状态的速度与加速度,使机器人的运动曲线尽可能平滑、运动时间尽可能短、运动代价尽可能小.当路径规划满足机器人时间约束条件时,路径规划即为轨迹规划[65].

现有的研究在水下机器人[66-67]、爬壁机器人[68]及微型飞行器[69-70]等方面进行了运动规划方法设计和验证,同时也采用不同的方法进行呈现,对机器人运动规划发展做出了很大的贡献.但是,上述研究仅对不同种类的单机器人进行路径规划分析.如图13 所示,大型复杂部件制造存在场景大、任务多、作业空间受限等特点,运动规划在多机器人领域仍然具有较大的挑战,每个新机器人的增加引起的搜索空间指数增长为亟待解决的问题之一.目前,多机器人运动规划方法主要分为基于搜索的运动规划、基于势场的运动规划、基于采样的运动规划及基于人工智能的运动规划方法.

图13 复杂场景下多机器人运动规划Fig.13 Motion planning of multi-robot in complex scenarios

2.1 多机器人运动规划方法

2.1.1 基于搜索的规划算法

基于搜索的运动规划方法具有良好的稳定性和精确性,是目前较为成熟且在移动机器人、游戏领域中广泛应用的一类运动规划方法.广度优先搜索算法、Dijkstra 算法、A* 算法、D* 算法(Dynamic A*)及冲突搜索算法等都是基于搜索法的优秀代表.

广度优先搜索[71]能够求得运动规划问题的最优解,该算法采用以起始状态为中心,逐步向外层层探索的策略,算法耗费大量时间在探索无用区域,寻路效率较低.1995 年计算机学家Ng 等提出的Dijkstra 算法[72]是一种广度优先搜索与启发式搜索相结合的贪心算法,首先计算出从初始位置到环境中每个位置的最短距离,然后将距离初始位置最近的点作为中继点,其次更新从初始位置到各个位置的最短距离,而后重复上述步骤直至遍历环境中所有位置为中继点,Dijkstra 算法能获得从初始位置到环境中任意位置的最短距离.但Dijkstra 算法保留了广度优先搜索需要通过大量计算才能寻得可行解的问题,效率较低.Hart 等提出的A* 算法[73]是一种基于Dijkstra 算法改进优先级排序的启发式算法,算法将节点权重与到达目标点的距离二者结合作为优先级的排序规则,使得算法只需访问较少的节点就能求得运动规划问题的最优解.针对Dijkstra 算法及A* 算法仅适于环境已知的场景,Stentz 提出的D* 算法[74]可以适用于未知或动态变化的环境.D* 算法与A* 算法相反,从目标位置开始进行搜索,直至搜索到机器人初始位置为止.D*算法的核心是计算最优路径的过程状态函数与应对环境信息变化的代价修正函数.当计算的可行路径出现新障碍物时,D* 算法仅需处理其附近的节点并将产生的影响向机器人所在位置传播,从而减少重规划的计算量.基于D* 算法,Koenig 等提出的D* Lite 算法提升了运动规划的寻路效率[75-76],Ferguson 等提出的Field D* 算法能够不受搜索方向的限制,使规划路径更加平滑[77].

近些年来,基于搜索的运动规划方法在多机器人作业过程中也得到了一定程度的发展,Ali 等使用A* 算法引入中央处理中心检查全局路径规划器生成的所有路径以避免碰撞,中央处理中心分析每个机器人的路径数据及对其他机器人轨迹的影响,得出全局轨迹.当机器人开始向目的地移动时,中央处理中心会实时检查其轨迹是否与其他机器人冲突,从而达到多机协同避障的目的[78].为了得到多机器人的高质量无碰撞路径,陈光友等提出一种基于改进A* 算法和冲突协调策略的多机器人双层规划算法,在二维路径基础上引入时间维度,建立机器人路径时间图,预测机器人时间维度的冲突.通过冲突协调策略对机器人与机器人之间、机器人与动态障碍物之间产生的冲突进行协调[79].Ren 等提出了一种基于多目标路径的D* 算法 (Multi-objective path-based D* lite,MOPBD*),利用基于路径的扩展策略计算主导解,并引入了MOPBD*的次优变体,提高了动态环境下的搜索效率[80].为解决多机器人运动规划过程中的冲突碰撞及A* 算法寻路效率低的问题,Sharon 等提出了一种基于冲突的搜索算法(Conflict based search,CBS),是一种两级算法,其中在高层对基于个体之间的冲突树执行搜索,冲突树中每一个节点代表了一组运动过程的约束,在低层执行快速的单机搜索以满足高层冲突树节点施加的约束.通过两级算法可以使CBS 算法比A* 算法具有更少的计算量,同时保持最优性[81].但是其对节点判断是否发生冲突时,节点的分裂和重新规划耗费大量时间,Zhang 等提出了一种基于冲突的并行搜索算法,设计了与人脑、眼、腿对应的全局路径规划、传感器级路径规划和动作级路径规划,加快节点的展开速度[82].为完成顺序装配操作的多机器人抓取规划,Dogar 等使用冲突搜索算法,将搜索表述为约束满足问题(Constraint satisfaction problem,CSP),将CSP 划分为独立的较小问题以指数级的速度进行解决[83].

如图14 所示,基于搜索的运动规划方法的寻路效率依赖于环境地图网格的划分,但网格越多算法所需访问的节点越多,算法寻路效率越低.基于搜索的运动规划方法的计算复杂度与运动规划问题所在空间维度呈指数相关,因此,该类方法仅适用于低维空间的运动规划问题.

图14 基于搜索的运动规划[78-82]Fig.14 Search-based motion planning[78-82]

2.1.2 基于势场的规划算法

基于势场的运动规划方法通过构建势函数引导算法搜索可行路径,无需对环境信息进行精确探索.最早基于势场的规划算法可以追溯到1985 年Khatib 提出的人工势场法,机器人在空间环境中的运动受到虚拟人工力场的作用,目标位置对机器人产生引力作用,障碍物对机器人产生斥力作用,在引力和斥力的共同作用下通过算法控制机器人的运动从而到达目标位置.

Liu 等提出一种与虚拟障碍物概念相结合[84]的势场法,该算法通过计算中途点作为临时目标点,以克服传统人工势场法容易陷入局部最优的问题.石鸿雁等将混沌优化算法与人工势场法相结合,提出混沌人工势场法,使机器人在动态环境中实时避障的同时不陷入局部最优解,在距离较近但不相连的障碍物之间找到可行路径[85].Scott 等提出一种新型势函数形式[86],此势函数包括用于避免关节限制的弹性势、引导机械臂远离障碍物的排斥势及防止机械臂陷入奇异状态的位形势,三个分量联合建立机械臂避障的势函数,在此基础上将相机视线遮挡部分视为虚拟障碍物,有效降低了机械臂在动态环境中因相机遮挡而导致的碰撞问题.Lee 等提出了一种NP-APF (New point-artificial potential field)运动规划算法[87],在机器人遇到障碍物时该算法首先选取一个合适的位置生成对机器人的吸引力,然后根据选取的位置优化机器人所受合力的大小和方向,帮助机器人快速摆脱障碍物的约束,提高传统人工势场算法的规划能力.韩伟等提出一种与模糊决策相结合的人工势场法,可以自适应调整机器人在虚拟人工势场中所受到的合力大小和方向[88].Mamani 等将势场法应用在多移动差速式机器人中,提出了编队控制要求清单,在此基础上建立了基于势场法的多机器人编队控制模型[89].为完成从初始位置到目标点的最佳路径规划,Pan 等提出了一种改进人工势函数的多机器人路径规划方法,通过引入旋转势场,可以使机器人有效逃离公共最小值和振荡[90].Matoui 等使用改进人工势场方法,使用非最小速度算法处理最小局部问题,并且通过机器人之间的优先级分配方法,解决了机器人在同一点通过的交叉问题.其次使用邻域检测技术来减少每个机器人的影响区域并优化规划计算时间[91].Wu等引入增益约束和随机因子来改进人工势场法,抑制路径振荡同时避免局部最小值,并采用B 样条曲线优化对规划路径进行平滑处理[92].

如图15 所示,人工势场法仅需计算机器人受到的合力大小和方向,减少了运动规划问题求解过程中产生的计算量.但该方法容易陷入局部最优解及无法找到可行解,且基于势场的运动规划方法仍面临着最优性与高维空间可拓展性之间的矛盾,仅适用于简单二维平面环境中的运动规划问题.

图15 基于人工势场法的运动规划[88,91]Fig.15 Motion planning based on artificial potential field[88,91]

2.1.3 基于采样的规划算法

基于采样的运动规划方法因其在多维空间中具有的显著优势在运动规划领域得到了广泛的关注[93],目前基于采样的运动规划方法主要分为基于随机搜索 (Probabilistic road maps,PRM) 算法的改进型和基于快速探索随机树 (Rapidly-exploring random trees,RRT) 算法的改进型等.

1996 年Kavraki 等提出的PRM 算法[94]被认为是当时最成功的解决高维空间复杂运动规划问题的方法,该算法的复杂度首先与寻找可行路径的难易有关,其次是空间大小和维度的影响.PRM 算法分为采样和查询两个步骤,采样过程通过在自由环境中进行随机均匀采样,为每个采样点搜索邻居节点,在此基础上建立无碰撞连接概率路线图,查询过程通过使用搜索算法从路线图中找到一条可行路径.1998 年LaValle 等提出的RRT 算法是一种树状结构的随机采样方法[95],该算法以运动规划问题的起始位置作为根节点,通过随机采样增加节点分支,在自由环境中生成随机搜索树,当随机搜索树分支拓展至目标位置即可获得从起始位置到目标位置的运动路径.基于RRT 算法,王乐乐等提出一种改进快速扩展随机树的多机器人编队路径规划算法,用于解决多机器人在复杂环境下的编队路径规划问题.同时定义机器人之间的领航-跟随结构,建立搜索树扩展方向与队形方向之间的联系解决规划过程中编队朝向变化问题[96].针对RRT 算法搜索区域受限、耗时较长、结果可行性较差等问题,陈锦涛等提出了一种RRT 森林算法,通过随机选取根节点、生成随机树、连接合并随机树,使高层消防多无人机在复杂室内环境下协同路径规划效率显著提高.此外,采用两次动态规划以及改进障碍物接近检测方法,进一步提高路径的可行性[97].RRT 算法倾向于未探索区域扩张,随着搜索迭代次数增加,未探索区域减少,可以得出RRT 算法探索空间能力强、速度快.该算法概率完备且不最优,可以迅速找到可行路径.但所寻找路径通常不是最优路径且包含较多的棱角.

针对RRT 算法所规划路径不是最优可行路径的问题,2011 年Karaman 等在RRT 算法基础上加入了重新布线函数和代价函数,提出了一种RRT*算法[98].该算法改进了RRT 算法父节点选择方式,在最小代价函数值下选择每一个节点,因此当采样节点趋于无穷多时,RRT* 算法计算的可行路径必定收敛至最优路径.针对水下机器人海洋调查问题,Cui 等提出了一种多维RRT* 路径规划方法,通过最大化标量场模型和观测值之间的信息来确定水下机器人的采样位置,以提高采取样本的质量[99].但是,RRT 算法与RRT* 算法都存在碰撞检测计算的代价昂贵问题,将大量的计算时间都花费在了碰撞检测中[100-101],特别是在复杂且障碍物较多的环境中,算法效率大幅降低.

Janson 等提出的FMT* 算法(Fast marching tree*)[102]结合了PRM 算法和RRT 算法的优点,用于解决高维空间中的复杂运动规划问题.该算法在结构上减少了大量重复的碰撞检测,同时也减少了求解节点过程中需要调整参数的数量,FMT* 算法提高了多机器人收敛到最优路径的速度,同时减少了计算量.为了提高效率和可扩展性,Le 等基于RRT 算法提出了一种协调扩展搜索树方法,首先开发了一种单机器人采样方法跟踪给定路线,然后设计路径跟随器确保每一个机器人跟随给定路线同时避免与其他机器人相撞,且所提出方法可以解决机器人增加带来的高位复合状态空间问题,具有良好的可扩展性[103].基于连续的多机器人采样运动规划过程,Dayan 等通过张量积将多个机器人PRM图构建为张量路线图,以支持在有限时间内保证高质量的解[104].

如图16 所示,近年来PRM 算法和RRT 算法的改进型不断被提出,在机器人运动规划领域表现良好,同时具备避障性、概率完备性等理论支撑.但调节算法运行时间与算法最优性之间的矛盾、探索盲目性问题是基于采样的规划算法需要解决的问题.

图16 基于采样的运动规划[96,99,102]Fig.16 Motion planning based on sampling[96,99,102]

2.1.4 基于人工智能的规划算法

随着人工智能技术的发展,人工智能算法被逐渐应用于多机器人运动规划问题中[105-106].常见的人工智能运动规划方法有遗传算法、蚁群算法、粒子群算法、人工神经网络算法、机器学习算法等.

1975 年Bhaduri 提出的遗传算法(Genetic algorithm,GA)[107]是一种模拟大自然生物进化过程的最优解搜索算法.该算法在运动规划问题中通过将可行路径视为个体,每个种群包含的可行路径条数为个体数量,每条可行路径的路径点个数为个体中染色体的数量.在迭代演化的过程中,借助遗传算子进行选择、基因交叉、基因突变等操作,适应度低的种群被淘汰,适应度高的种群被保留,“优胜劣汰”的竞争使得最终保留下来的路径为算法寻得的最佳可行路径.Nazarahari 等提出了一种增强遗传算法 (Enhanced genetic algorithm,EGA) 来改善连续空间中的初始路径,基于省时的确定性方案寻找可行的初始路径,并保证找到一个可行的路径(如果存在),同时EGA 算法利用五个定制的交叉和突变运算符来改善初始路径[108].但遗传算法具有较高的随机性,每次调用的运行结果都不尽相同,甚至存在不收敛的可能.

1992 年Dorigo 等提出的蚁群算法(Ant colony algorithm,ACA)[109]是一种采用正反馈机制,模拟蚂蚁寻找食物时根据同伴分泌的信息素逐渐发现最短路径的仿生概率算法,其在搜索过程中不断收敛直至逼近最优可行路径[110].Hasan 等将蚁群算法与D* 算法结合,考虑在自由空间中的动态障碍物,构建概率函数选择每个机器人的最佳路径达到动态避障[111].

1995 年Kennedy 提出的粒子群优化算法[112](Particle swarm optimization,PSO)是一种模拟鸟类捕食的优化算法.该算法通过鸟类个体间的信息共享与相互协作,引领着群体演化至最优可行解,粒子群优化算法提高了复杂环境下最优解的发现率.Wang 等提出了一种由连续粒子群算法和离散粒子群算法组成的混合粒子群算法,连续粒子群算法优化期望编队的中心位置和旋转角度,离散粒子群算法用于优化初始位置和目标位置之间的匹配关系[113].针对未知环境下的多机器人目标搜索问题,Dadgar 等提出一种基于粒子群优化的分布式算法,避免陷入局部最优[114].

人工神经网络在多机器人运动规划中,通过搭建、训练神经网络系统以逼近问题中的可行运动路径,并依照环境约束与机器人约束的变化不断优化所寻的运动路径[115-116].

2017 年Pfeiffer 等提出了一种基于监督学习的运动规划方法,根据激光测距结果建立相对目标位置的卷积神经网络(Convolutional neural networks,CNN)模型[117],但监督学习的框架依赖于标记的算法,对环境变化的泛化能力弱.强化学习通过代价迭代方式建立表格,用于存储状态到动作过程的映射,根据表格信息引导多机器人运动到目标位置.面对碰撞避免和输入约束影响的在线多机器人时间最优路径规划问题,He 等将人工势场纳入近似成本函数中,提出了一种积分强化学习方法,将具有输入约束的有限视界最小时间能量问题转换为近似无限视界最优控制问题[118].但在障碍物信息变化的环境中需生成大量表格,耗费内存空间.Tai等将深度强化学习应用于运动规划问题中,只需指定运动规划的目标,使其在仿真规划场景中大量尝试,不断进行学习,根据获得的奖励及惩罚自主迭代更新网络,从而求解出较好的可行路径[119].针对传统方法难以将其他移动机器人识别为障碍物或协作机器人的问题,Bae 等结合了CNN 网络和深度强化学习算法,其中CNN 网络使用环境的图像信息分析确切的情况,同时机器人根据通过深度强化学习分析的情况进行规划[120].为解决钣金钻孔过程运动规划问题,Veeramani 等将最优路径识别问题建模为一个马尔可夫决策问题,选择了一种无模型的状态-动作-奖励-状态-动作策略时间差规划算法,并基于路径规划问题的参数进行了描述[121].

如图17 所示,基于人工智能的运动规划方法通常可以寻得运动规划问题中的较优解,但求解过程需花费较多时间,效率较低.

图17 基于人工智能的运动规划[108,114,120]Fig.17 Artificial intelligence-based motion planning[108,114,120]

2.1.5 基于混合算法的运动规划

有效地结合两种或以上规划算法,可以很大程度上提高计算效率.如图18 所示,为完成多机器人点焊任务,Pellegrinelli 等结合冲突搜索算法与市场法,为每个机器人设计无碰撞运动路径减少设计时间和设计失误[122].Hartmann 等将优化方法与基于采样的双向时空路径规划器相结合,共同求解操纵约束,使其能够规划到达时间未知的协作式多机器人操作[123].为解决柔性物体协同搬运问题,Alonso-Mora 提出了一种混合集中/分布式方法,针对机械手设计低层规划器,通过物体相互传递力来保持操纵和避免碰撞的保证,基于分布式反演水平规划器设计局部控制算法,并包含避免碰撞和形状维护的约束[124].为完成汽车生产过程中的去毛刺、切割和焊接等任务,Touzani 等首先使用市场法对任务进行排序,然后使用PRM 算法完成自动路径规化[125].Han 等结合路径多样化和最优子问题策略,提出了一种新的集中解耦算法,解决仓库环境的一次性和动态最优多机器人路径规划问题[126].为完成大规模自由曲面产品的光学检测问题,Liu 等通过机器人坐标空间动态搜索,考虑冲突机器人中探头姿态或局部路径的扰动,提出无碰撞路径规划和协调运动规划[127].Rigatos 采用分布式梯度算法和群体智能算法,解决多机器人协作自主装配问题,从解空间中的不同点开始,并在向目标位置移动时相互交互,可以在每个机器人的最佳先前移动和其邻居的最佳先前移动定义的区域中迭代搜索[128].为完成自动化仓库设置,Han 等结合路径多样化和最优子问题解决方案数据库,有效地利用整个工作空间进行机器人旅行,而最佳子问题解决方案数据库有助于快速解决局部路径冲突[129].

图18 基于混合算法的运动规划[122-129]Fig.18 Motion planning based on hybrid algorithm[122-129]

2.2 复杂作业场景下多机器人运动规划

面向复杂作业环境下多机器人协同加工过程,按照机器人结构及作业环境的不同,主要分为移动端运动规划、作业端(末端执行器作业)运动规划.

2.2.1 多机器人移动端运动规划

复杂环境下高效的全局路径规划及动态冲突下局部路径重规划是多机器人移动端安全、稳定运动的前提.Li 等[130]首先利用增强冲突的搜索算法获得每个机器人的离散路径,根据离散路径构建针对静态障碍物的安全廊道作为安全性硬约束,然后构造涉及轨迹平滑性和多机间安全性的目标函数,利用模型预测算法进行优化求解获得全局可行轨迹.Wagner 等[131]以A* 算法作为底层路径规划器为每个机器人单独规划最优路径,同时为每个节点维护碰撞集合和反向传播集合,大大减少了A* 算法扩展过程的节点数.为应对机器人数量较多时,会出现由于过度避障导致的机器人抖动问题,Van 等[132]提出交互速度障碍算法为多机器人提供统一的决策行为,虽然解决了多机器人相遇时的抖动问题,但是多机器人规模增大时仍然无法避免碰撞,可扩展性低.为改进这一缺点,Van 等[133]提出最佳相互避碰方法,利用有向平面分割空间将避碰问题转换为线性规划问题,提高了计算效率,并能够对其他机器人的运动进行精准的感知、相互协作产生无碰撞的运动.Tordesillas 等[134]利用最小体积法构建当前机器人控制点的最小凸多面体,并且对动态障碍物或者其他机器人同样建立凸多面体,进而创建一个平面对两种凸多面体进行分离,通过将此平面作为安全性硬约束,建立目标函数进行求解,获得无碰撞的轨迹.

如图19 所示,Zhou 等[135]提出多目标时空轨迹联合优化方法,构建与时间以及轨迹平滑性相关的多目标优化函数,在满足动力学约束下求解获取实时轨迹.

图19 多机器人移动端运动规划[135]Fig.19 Motion planning of multi-robot mobile terminals[135]

2.2.2 多机器人作业端运动规划

多机器人作业端无干涉协同运动是实现多机器人系统安全制造的前提.如图20 所示,面向制造的机器人系统通常由移动端与作业端执行器组成,作业端高自由度、规划空间高维以及作业空间受限等对实现实时安全无干涉协同运动规划提出了挑战.Thakar 等[136]考虑到移动机械臂单元的高非线性、紧耦合性等问题,将其定义为非完整移动机械臂(Nonholonomic mobile manipulator,NMM),首先根据机器人周围环境的信息,对机械手和目标点的样品进行协调聚焦,其次考虑到NMM 的非全息约束,在两个搜索树之间建立连接的启发式方法,从而提高路径的计算速度和成功率.Tallamraju 等[137]提出了一种分层自适应移动机械臂规划器,对移动单元与作业单元进行单独规划,并以概率地图法规划框架基础上通过增加自适应采样策略,提高规划效率.Pardi 等[138]考虑到移动作业机器人系统的非完整约束与运动学约束,将约束受限下的路径规划表述为多目标优化问题,将由作业单元末端执行器表面移动距离、可操作性以及移动单元运行速度构成的代价函数嵌入到RRT* 算法中实现任务空间下的路径规划.基于多机器人作业端协同搬运运动规划,Tang 等[139]将多机器人协同运输系统视作环境中的一个虚拟矩形,提出了一种基于系统轮廓矩形变化的避障规划方法,通过改变虚拟对象的移动方向和矩形宽度来适应环境变化.面对存在未知轨迹障碍物环境下对移动机械臂运动规划问题,Vannoy 等[140]提出了一种可扩展的实时自适应运动规划方法,可实现实时同步的路径和轨迹规划,同时通过机器人配置变量的松散耦合,利用移动机械臂的冗余,实现避障和优化目标.Bonilla 等[141]提出了一种多机器人作业端在与环境以及自身内部进行位置/力交互时的运动规划与控制集成方法.该方法设计了一个非交互式的控制器实现多机器人的解耦控制,通过放松几何约束,采用一个狭窄的全维边界层代替低维约束流形来解决受约束的运动规划问题.

图20 非完整和任务约束下作业端路径规划[136-138]Fig.20 Path planning for operators under non-integrity and task constraints[136-138]

如表2 所示,目前多机器人运动规划在制造领域得到了一定的研究进展,算法的最优性、鲁棒性及避碰、避障能力有了显著的提升.但在复杂环境下、狭小空间下的解空间计算复杂性、寻路效率还有待提高,对目标函数、人工智能算法的奖励函数设计还需要进一步的研究.

表2 运动规划方法分析Table 2 The analysis of motion planning

3 展望

随着重大装备大型复杂部件制造的不断发展,多机器人系统的应用和研究为制造过程的效率和精度提供了重要的保障.但是针对复杂作业环境下多任务、多工序的作业需求,多机器人缺乏可扩展性、任务协调性.集群机器人具有高柔性、智能化、可扩展性、灵活性等优势,为大型复杂部件制造提供了新思路.在过去的一些算法研究中,集群机器人任务分配与运动规划已有部分进展.Yang 等基于蚁群算法与响应阈值模型,完成集群机器人任务分配,体现分布式算法的可扩展性[142].Ghassemi 等考虑任务截止日期与机器人范围和任务完成能力限制,并允许在动态任务空间下进行异步决策,为不同的实际应用(例如灾难响应) 提供重要的解决方案[143].Vicmudo 等基于遗传算法为每个机器人生成最短路径,使其到达目标点而集群机器人之间不会相互碰撞,通过仿真验证安全无碰撞路径的有效性[144].Chella 等改进蚁群算法,为集群机器人提出了一种基于量子的路径规划算法,量化输入位置和奖励信息 (以机器人与目标的接近程度来衡量) 和路径规划决策[145].但上述方法仅仅在仿真环境下验证,且使用局域网进行算法设计很大程度上限制了集群机器人工作空间,同时通信过程中产生的时延、噪声以及网络波动影响了分配和规划的效率与准确性.因此复杂环境制造场景,如何将多机器人任务分配与运动规划算法应用在集群机器人中,体现可扩展性,在此基础上向网络化、智能化延伸,即云-边-端网络协同下的集群机器人任务分配与运动规划,为亟待解决的难题.尽管目前已有许多研究学者对集群机器人进行了探索,结合表1 和表2 的分析,在大型复杂部件作业场景中仍然存在一部分问题亟待解决:

1) 制造环境的复杂性: 在大型复杂部件制造领域,部件具有尺寸大、刚度低、制造精度高、结构复杂等特点,生产环境往往复杂多变,从而引起集群机器人全局任务分配与运动规划困难.现有的方法在复杂场景下寻路效率低、随机性高、成本函数设计复杂,因此探索大规模复杂环境下任务分配和运动规划方法是未来的研究方向之一.

2) 难以兼顾全局和局部: 复杂制造环境下仅采用某一种算法难以兼顾全局最优性,若采用局部规划分配算法将极大增加任务的复杂性.而两种及以上的方法有效地结合可以满足全局和局部的优势,因此在采用全局方法进行任务分配规划的基础上结合局部规划方法对部分复杂场景进行实时动态规划是未来研究方向之一.

3) 通信约束强: 网络化集群机器人制造过程中容易出现通信的不确定性,而当前的部分方法如启发式算法、A* 算法等对通信准确程度具有较强的依赖性,且深度学习算法需要通过云服务器进行大量的数据计算.因此需要对动态任务分配规划技术进行改进,以实现在部分时间段弱通信或通信受限场景下的鲁棒性.

4) 冲突干涉问题: 复杂动态环境下集群机器人与动态障碍物以及集群机器人之间的相互移动都会影响全局运动规划过程,容易引起冲突干涉,因此亟待寻求解决高动态环境下冲突预测与动态避障方法.

5) 受限空间问题: 复杂场景下机器人作业端存在运动空间狭小、规划空间维度高、约束条件多等问题,因此进行狭小空间下集群机器人无干涉协同运动规划方法设计是未来的研究方向之一.

如图21 所示,与其他方法相比较,基于学习的方法具有强大的学习能力、高鲁棒性、高适应性等优点,结合现阶段研究现状及复杂制造场景下现阶段亟待解决的问题,提出一种基于云-边-端协同的任务分配与运动规划构想.首先提出基于云边协同的集群机器人高动态实时任务分配方法,采用整数线性规划方法进行智能化区域划分与资源分配,并使用分层强化学习方法进行区域内任务分配,基于云边协同进行启发式跨区域任务分配.然后提出边端协同下移动端实时冲突预测与运动规划方法,使用基于知识复用方法进行高效无冲突全局路径规划,针对高动态环境下冲突干涉问题,采用基于行为预测的局部运动规划方法.面向作业空间受限问题,提出集群机器人作业端无冲突协同运动规划,构建末端执行器自适应安全域,并提出基于随机采样的实时避障轨迹规划,提高动态环境的适应能力.

图21 复杂环境下集群机器人任务分配与运动规划技术路线Fig.21 Technical route of task allocation and motion planning for cluster robots in complex environment

4 结论

重大装备大型复杂部件具有尺寸超大、工序繁多、型面复杂等特点,其制造过程场景规模大、任务工序多、精度需求高,作业场景复杂.传统的人工、单机制造面临着效率低、柔性不足、一致性差、空间有限等问题,难以保障大型复杂部件制造的需求.多机器人具有高适应性、高柔顺性等优点,为大型复杂部件提供了良好的制造基础.先进的任务分配和轨迹规划方法是多机器人制造系统的决策中枢,其性能影响整个系统的运行效率.

本文针对任务分配过程对线性规划方法、基于市场的方法、启发式算法及深度强化学习算法进行了分析,同时针对运动规划对基于搜索的规划方法、基于势场的规划方法、基于采样的规划方法及人工智能规划方法进行了描述.在此基础上对算法产生的计算时间问题、可行解问题、维度问题及通信的鲁棒性问题进行了总结.结合重大装备制造复杂作业环境,对现有的方法存在的问题进行了总结,与其他方法相比较,基于学习的方法具有强大的学习能力、高鲁棒性、高适应性等优点,因此结合深度强化学习为基础的混合算法提出了一种复杂场景下集群机器人协同制造的思路.综上所述,结合深度强化学习与其他算法的混合分配规划方法并应用于集群机器人重大装备制造中是未来的主要研究方向.