多移动机器人协同搬运技术综述

顾大强，郑文钢

（浙江大学 机械工程学院，浙江 杭州 310027）

多移动机器人的研究始于20世纪80年代后期，当时的研究领域主要集中在多移动机器人重构、轨迹规划以及多移动机器人协同合作几个方面。但随着多移动机器人技术的发展，多移动机器人的应用领域逐渐扩展到水下机器人、太空空间、高危场所以及服务领域[1]。与单移动机器人系统相比，多移动机器人系统具有一系列的优势，尤其是在一些特定场景[2]：多移动机器人系统完成的任务复杂性更高；多移动机器人系统能够胜任分布式任务；多个简单的移动机器人系统比复杂的单机器人系统架构更简单，成本更低；多移动机器人的并行操作能够更快地执行任务；多移动机器人系统能增强系统的鲁棒性。

1 多移动机器人搬运的控制策略

在多移动机器人系统中，多移动机器人的搬运任务是其主要应用领域之一，在很多场合，如人员的急救工作、高危工作的执行、工业自动化过程、重物搬运等，都可以得到应用。最为经典的搬运问题被称为“推箱问题(box-pushing problem)”，是由著名的“钢琴搬运工问题(piano movers problem)[3]”引申而来的。如图1所示，任意给定一个刚性的多面体，满足将规定的对象从原配置位置移动到所需的目标配置位置，很多相关研究都是围绕这个问题展开的[4-9]。

图 1 推箱问题示意图Fig. 1 Schematic of the “box-pushing problem”

对于已知物体的搬运方案可以大致分为3种类型：抓取、推拉、锁定。抓取操作是应用较为普遍的一种方式，尤其是对于配有机械臂或多指机械手的系统，该方案的难点在于保持机器人在抓取过程中抓取位置的准确性以及搬运过程中物体的稳定性，对多移动机器人系统的实时响应性能和传感器的精度要求较高[10]。第二种推拉方式较为典型，“推箱问题”采用的便是这种方式，推拉操作可以认为是一种条件封闭操作(conditional closure manipulation),被广泛应用于群体智能(swarm intelligence)机器人的搬运任务中[11-12]。另外，通过大型物体的翻转、抬运[13-14]操作进行物体的协同搬运，实际也属于广义动态的推拉操作。第三种锁定方案，源于机械手抓取过程中的力封闭(force closure)和形封闭(form closure)算法[15]，通过若干个移动机器人锁定物体，使搬运的物体能够与机器人群作为整个刚体进行运动，实现最终的搬运操作，常见于规则多面体的物体搬运[16]，应用不同的搬运方案主要有以下3种常见的多移动机器人协同搬运策略。

1.1 群体智能

多智能机器人系统(multi-agent robot systems，MAS)作为一个分布式自治系统，其核心在于将整个系统分成若干个智能的、自治的子系统，它们可以是同质的，也可以是异质的，任务的完成可以由若干物理和地理上分散的子任务组成，子任务之间可以相互通信、相互协调，能够满足多移动机器人系统适应复杂环境的需求，同时对任务(多移动机器人扫描监测、搬运、构图等)具有高度的适应性[17]。MAS在多移动机器人搬运中应用很广泛，它的优势在于系统对单个移动机器人的性能要求不高，且单个移动机器人的故障不会引起整个系统的崩溃。MAS应用于多移动机器人搬运任务，一方面可以实现对大型物体的集体搬运[18-20]，另一方面也适用于实时的多目标搬运[21-22]，因此被广泛应用于工业搬运[23]、物流[24]等场所。

基于群体智能(swarm intelligence)的控制理论研究是基于生物学中的群体行为(如昆虫觅食、搬运行为等)。在生物群体中，各个个体独立分布，单个个体的故障不会影响整个系统，同时个体之间通过非直接通信进行信息交互，使得系统具有很强的扩展性，适用于MAS系统的控制。群体智能算法中以蚁群优化算法(ant colony optimization, ACO)和粒子群优化算法(particle swarm optimization, PSO)最为典型。

蚁群算法是由Dorigo等[25]于1997年提出。该算法受蚂蚁觅食行为的启发：蚂蚁在行动过程中会留下“信息素”作为标记，其他蚂蚁可以通过感知“信息素”的浓度来选择最佳的路径，大量的蚂蚁群体会形成一个正反馈，从而找到系统的最优解(最短路径)。

1) 经典的蚁群算法

t 时刻，蚂蚁k 从第 i 个 节点到下一个节点j 是根据初始信息素 τij(t) 和启发信息 ηij(t) 的大小进行判定，判定原则为伪随机比例原则：节点 i的蚂蚁以一定概率q0转移到下一个节点j ，若 q≤q0，则满足[τij(t)]α[ηij(t)]β最大，蚂蚁的状态转移公式为式(1)，否则按照式(2)采用轮盘赌方式选择下一个节点。

式中：q为[0, 1]区间均匀分布的随机数；α为信息素启发因子，代表信息素的重要程度；β为期望启发因子，表征启发信息的重要程度； Ak表示蚂蚁k 下一步允许选择的路径集合； djg表示待选节点j与目标节点g 的欧氏距离。信息素需要随着时间推移进行更新，传统蚁群算法在完成一次迭代后通过式(4)、式(5)进行信息素的全局更新。

式中：ρ为全局信息素挥发系数； Δτij(t,t+1)表示(t,t+1)时 刻在路径 (i,j)上 的信息素增量； Q为信息素强度系数； Lk为 蚂蚁 k建立的最短路径。在传统的蚁群算法基础上也衍生出了很多优化的蚁群算法[26-27]。

2) 粒子群算法

粒子群算法是一种模拟鸟群觅食过程中的迁徙和群聚行为的算法，最早由Kennedy和Eberhart[28]提出。它假设在 D维的搜索空间内，粒子群的 规 模 是 N ，第 i(i=1,2,···,N)个 粒 子 的 位 置 是xi=[xi1xi2···xiD]， 飞行速度为 vi=[vi1vi2···viD]，则第 t 次迭代的自身历史最优位置为 pbest，全局粒子最优位置为 gbest，粒子通过两个不断更新的极值来更新自己的速度和位置[29]。经典的迭代公式为

式中：t 为当前进化迭代数；学习因子 c1、 c2为非负常数；r1、r2为[0, 1]区间服从均匀分布的两个独立随机数。程序在达到最大迭代次数或者达到预设精度时终止。粒子群算法的缺陷在于：搜索精度低，对参数依赖程度高，改进的粒子群算法有二进制粒子群算法、协同粒子群算法、简化粒子群算法等。

1.2 领导-跟随控制模式

领导-跟随(Leader-Follower)模式是多移动机器人系统最典型的集中式控制模式[30-31]，它通常由一个功能相对强大的移动机器人作为群体移动机器人的“Leader”，其他移动机器人受到“Leader”的集中控制。所有移动机器人接受到的传感器信息都需要传递到“Leader”机器人，进行统一分析，对系统的任务分配、路径规划等进行统一处理，最后一一分配给其他从属机器人。该体系下，其他从属机器人不具备自主动作与相互协调的功能，只是作为收集信息的执行端。它的优点是：各移动机器人之间的协调效率高，整个系统的逻辑架构相对简单，但是对“Leader”机器人的运算性能要求高，同时由于系统对其的高度依赖性，系统的容错性只能被限定在小范围的错误中，主控机器人的故障直接会导致系统的崩溃。系统的灵活性、自主性、可扩展性和鲁棒性都比较差，无法应用于非结构化、动态环境。集中式控制模式下，各机器人之间可以有明确的分工协作。

在多移动机器人搬运系统中，经常采用的移动机器人集中式控制模式被称为“Pusher-Watcher”模式[32]。与“Leader-Follwer”模式类似，“Pusher-Watcher”模式中“Watcher”机器人占据系统控制的主要地位，负责对系统环境的扫描、定位、避障操作，有时还需要检测搬运物体的实时状态[33]，“Pusher”机器人则只需根据“Watcher”机器人的指示协助机器人进行物体的搬运操作。与传统的集中式控制相比，“Pusher-Watcher”模式能够更好地响应动态环境，“Watcher”机器人能够根据具体环境的实时变化作出反应，同时对于同质的“Pusher-Watcher”机器人系统，各个机器人往往能够在“Watcher”和“Pusher”两者之间切换，甚至同时担任两者的功能，系统具有较强的容错性[34]。除此之外，类似于“Pusher-Watcher”模式，东京大学工业产品造物工程研究中心(research into artifacts center for engineering，RACE)的Ota等[35]还提出了抓取者-搬运者、翻转者-搬运者模式[36-37]，以若干特制的移动机器人完成了对大型物体的协同搬运。

1.3 对象锁定

多移动机器人搬运的对象锁定(object closure)策略，策略中的“锁定”概念定义为：在各个移动机器人“到位”之后，物体的可移动区域有界，且当移动机器人之间的相对位置发生改变或者个别移动机器人与物体的接触力为零(处于脱离状态)时，物体仍在各个移动机器人的控制边界内[38-39]。图2表示锁定物体的移动机器人群Ri(i=1,2,3,4)与物体之间的相互关系[40]，可见当物体处于锁定状态时，物体的搬运控制可以通过各个移动机器人简单的刚性变换来实现。与机械手的锁定抓取不同，多移动机器人的协同控制会随着机器人数目的增多，物体与机器人之间的拓扑关系变化而变得愈加复杂，需要借助于高效的分布 式算法来实现多移动机器人位置的规划。

图 2 锁定状态下的移动机器人与物体相对位置Fig. 2 Relative positions of mobile robots with the object under the object closure state

目前，常应用人工势场法进行搬运对象的搜索以及锁定状态的确定。势场法最初应用于虚拟力解决路径规划问题，它将移动机器人所处环境信息模拟成虚拟势场，通过斥力势场和引力势场的相互作用，使移动机器人能够避开障碍物，最终安全到达目标点。在移动机器人进行对象搜索时，机器人所受到的引力来自搬运物体，斥力来自其他移动机器人。搬运物体锁定状态的实现主要分搜索与锁定两步。

1)假设单个机器人i 受到一个2维力向量βi的驱使进行运动， βi由2部分组成，即物体的吸引力向量 βobj_i和 其他机器人的斥力向量 βij：

在 βi的作用下，各个移动机器人会在搬运物体的周围逐渐形成一个闭环链。

2)完成1)后各个移动机器人需要围绕着物体的边缘不断移动直到物体被“锁定”。物体的锁定状态由下式确定：

式中：

在这两个过程中，基于人工势场式(8)和式(9)得到吸引力向量 βobj_i和斥力向量 βij：

式中： k≥1； pi、pj表示任意一个机器人位置； pd为指向物体边缘的最近的“锁定平衡点”，对应的角度为θi； Pd是为了保证各个机器人相隔距离相等，其 值 为 S(pd)/n ， S(pd) 为 pd路 径 长 度，n为 移 动 机 器人总数；Lsen为机器人传感器探测的范围。最后，βspin_i可以通过式(10)确定， βspin_i的方向垂直于物体的吸引力 βobj_i方向：

2 多移动机器人的相关技术

在多移动机器人搬运的实际实现过程中，具体搬运流程可以概括为：工作环境信息的感知；多移动机器人的任务分配与轨迹规划，机器人执行过程，根据实时环境进行轨迹再规划；完成搬运任务。其中涉及的相关技术主要包括多移动机器人任务分配、环境感知与定位及轨迹规划3个方面。

2.1 多移动机器人协同任务分配

多移动机器人的任务分配问题是一个最优化问题，可描述为：对一个移动机器人集合、一个任务集合指定系统评价指标，将各个子任务分配到合适的子机器人，满足整个移动机器人系统在执行全部任务过程中获得的收益最大。该问题属于NP问题[41]，通常采用启发式算法求出其中一个可接受的解。若以多移动机器人完成全部侦查任务所需要移动的路径总长度作为评价任务分配的最优性能指标，静态环境下多移动机器人协同侦查多个目标点的任务分配问题可以归结为求解一般形式(各移动体的起点、终点不一定相同)的多旅行商问题(MTSP)。常用的任务分配算法有基于拍卖的分配算法[42]，当系统需要完成任务并得到最短路径时，通常采用的算法有异质交互式文化混合算法(HICHA)、遗传算法(GA)、改进粒子群算法(PSOBA)、蚁群优化算法(ACO)、均衡负载规划算法(BPA)等。

实际上，多移动机器人之间的任务分配以及协同控制还需要考虑多移动机器人系统在时间、空间、功能上的分布性特点，国内外学者在分布式机器人系统的控制系统领域展开了很多的研究。ALLIANCE[43]作为基于行为的软件架构，成功解决了多移动机器人的容错协同控制。Klavins等[44]提出了分布式机器人系统的混合控制方法。在该系统中，每个单体任务都由一个控制器进行控制，常被应用于自动化生产的机器人装配任务中。“三层”(three-tier, 3T)架构由Schreckenghost等[45]于1998年提出，该架构考虑了远程设备维护管理的人机交互问题，可以在执行过程中对操作进行合理地人为干预。CLARAty架构由Volpe等[46]提出，属于两层架构，该架构考虑了系统的规划层和执行层之间的强耦合问题，其功能层实现了仿真、状态监测和面向对象的系统操作。3T和ClARAty架构都已被应用于美国国家航空航天局(NASA)的部分移动机器人项目中。

2.2 多移动机器人环境感知与定位

移动机器人一般通过各类传感器来获取外界信息，常见的传感器包括声呐系统、激光测距仪、摄像头等。移动机器人需要依靠传感器来感知周边环境，并提取环境中的有效信息加以处理和理解，最终通过所在环境的模型来表达所在环境的信息，这是实现自主移动机器人定位、导航的前提[47]。

对距离和障碍的探测，目前主要采用声呐和激光测距仪。相对来说，激光测距仪测距的精度更高，而且不受环境因素的影响，但价格更高，功耗更大。机器人的视觉系统分为主动视觉和被动视觉两种。主动视觉通常自身配备光源，被动视觉依靠外部光源。从视觉传感器数目上看，机器人视觉系统可以分为单目视觉、双目视觉以及多目视觉。单目视觉处理简单，只能获取环境的二维信息，而双目或者多目视觉处理信息更加复杂，能够获取环境中的三维信息。多机器人系统的一个难点在于如何将不同类型的信息进行整合，即多传感器信息融合问题[48]。目前常用的多传感器信息融合算法有卡尔曼滤波、加权平均法、统计决策理论和神经网络等。

在获得外界信息的基础上，多移动机器人需要对这些信息进行实时处理。信息处理的一个很重要目标是机器人自身的定位问题。具体来说，机器人需要根据当前位置估计周围环境地图数据以及外部传感器数据等，经过特定算法处理，得到更加精确的当前位置估计。机器人定位可以分为2种：相对定位和绝对定位。前者是在给定初始位置的情况下，确定自己的位置；后者则不需要给定初始位置。相对定位的实现包括2种定位方法：惯性导航和测程法。惯性导航依赖于加速度计、陀螺仪、电磁罗盘等传感器，测程法则基于编码器测量信息。绝对定位通常依赖的方法包括：导航信标；主动或被动标识；图形匹配；基于卫星的导航信号，即GPS定位；概率定位。

2.3 多移动机器人轨迹规划

多移动机器人路径规划目的在于：根据已知的、部分已知的环境信息，由移动机器人群自主规划路径，满足各个移动机器人从各自已知的起始位置出发，绕过障碍物，到达各自的终止位置，在整个过程中，各个机器人之间不发生干涉。已有的路径规划算法主要有栅格法、构型空间法(C-Space)、边界距离模型法等。多移动机器人的全局路径规划不仅需要保证机器人与障碍物之间无碰撞，同时还要避免机器人与机器人之间无碰撞，并且满足优化条件，可以采用多移动机器人免疫协同路径规划算法。

多移动机器人的实时避障、路径规划以及编队等[49-50]传统问题一直是国内外的研究热点。但是近年来，多移动机器人的停驻、目标搜索问题[51-52]得到了越来越多的关注。该问题的核心在于：找到目标物外围的包围圈，并且合理分配包围圈上的机器人停驻点，从而获取目标物体各个方面的信息。在停驻点分配的过程中，需要机器人有一定的自主避障能力，要求机器人能够对环境有一定快速感知并处理的能力。目前较为有效的避障策略有人工势场法(APF)、栅格法和神经网络法等[53]。

3 结束语

随着传感器技术、计算机视觉、人工智能算法以及计算机软硬件等相关技术的发展，多移动机器人协同搬运技术的发展必然会越来越成熟。目前，对多移动机器人协同搬运技术的研究还存在很多不足，在未来工作中需要对以下几个方面作进一步地研究。

1)提高多移动机器人对工作环境的适应性。目前对多移动机器人搬运技术的研究多集中于协同算法、导航技术，较少考虑机器人结构方面的问题。所采用的机器人多为轮式或链条式机器人，对工作环境尤其是移动面的要求较高。实际上多移动机器人的应用场所往往是一些高危或者常人难以进入的场所，因此对环境具有高适应性的机器人的开发是极其重要的。

2)搬运中缺少反馈系统，目前大部分多移动机器人搬运系统都是一个开环的系统。一旦满足了系统给定的搬运起始状态(夹紧、锁定等)之后，搬运物体在整个过程中便处于自由状态，一些重心较高的物体很容易在搬运过程中发生倾倒等情况。目前，已有的一些基于视觉反馈系统的研究仍然不成熟，在时间响应以及反馈信息处理上需要得到进一步的提高。

3)多移动机器人控制算法应与人工智能结合。虽然机器学习很早就应用于多机器人协同控制,但是目前机器学习算法在复杂环境中的响应时间和正确率都不令人满意。随着人工智能的不断发展，机器视觉的不断突破，人工智能技术与机器人控制的结合应该变得更加密切。