1 引言

群机器人是特殊的多机器人系统，由许多个无差别的自治机器人组成，具有典型的分布式系统特征.主要研究能力有限的个体机器人通过交互，协调和控制涌现群体智能以合作完成相对复杂的规定任务^[1-4].其中协作搬运是群机器人学中的一个重要研究方向，由于具有广泛的应用前景所以受到了众多研究者的关注和重视^[5-9].基于抓握(grasping based)和基于囚笼(caging based)的方法是协作搬运问题的两类最基本最常用的解决方法.

基于抓握的方法常要通过机器人与物体的接触以形成力锁合和形态锁合(force closure and form closure).因为这两个条件意味着系统可以抵御作用在物体上的任何外力、 可以让物体产生需要的加速度^{[6, 10-12]}.力锁合通常仅由机器人的接触力产生.若其中还包含一些作用在机器人上的外力，如重力与摩擦力等，则称为条件力锁合.文^[13-14]等运用条件力锁合来完成多机器人的协作推箱等任务.

基于囚笼的方法则常要求系统能够满足物体锁合(object closure)条件^{[6, 12, 15-18]}.在该条件下，物体能在一个较小的囚笼内运动，机器人与物体之间也不需要时刻地保持接触.因此与力锁合相比，物体锁合使得机器人的运动规划和控制更加简单，鲁棒性更强，机器人间的协调协作也更加容易实现.

文^{[12, 17-18]}等基于物体锁合条件给出了协作搬运问题的一个解决方法，其基本步骤为： 第1步，基于人工势场方法各机器人首先都独立地从自己的初始位置运动到搬运物体的附近.第2步，在各机器人控制器的控制下，机器人环绕着物体形成一个可以囚住物体的搬运队形.第3步，队形控制策略控制着搬运队形协调运动从而完成搬运任务.

上述方法的第1步与第2步采用完全分散的方式以形成满足物体锁合条件的搬运队形有许多优势.如计算负担低、 机器人间通信量少、 机器人数量的可扩展性强等.但这种方法仅适合机器人数量少且搬运物体形状较简单的情况.当机器人的数量很多且搬运物体的形状复杂时，上述方法不但难以保证形成满足条件的搬运队形，且即使能形成所用的时间也会很长，即效率很低.

基于上述原因，本文受到人们在求职或变更自己职位时常要遵守的规则的启发，提出了一种自组织确定各机器人搬运点并最终形成搬运队形的人工社会职位法.该方法中首先给出了人工社会职位法的基本规则，并运用人工社会职位法的基本规则确定各机器人每个采样时刻的对应搬运点.然后每一个采样时刻改进的人工力矩控制器驱动机器人向各自的搬运点运动一步.最终每个机器人都能安全准确的到达一个不同于其它机器人的搬运点，从而形成搬运队形.该方法不仅原理简单、 计算量少，而且无论机器人的数量是多少，搬运物体的形状多复杂，系统总能在有限的时间内形成满足条件的搬运队形.本文还改进了文^[19-20]中给出的求解吸引线段与吸引点的算法从而显著地降低了计算量.仿真结果表明，文中所给方法是可行且有效的.

2 系统模型和问题描述

本文的研究基础是如果有m个机器人参与搬运，则系统已经根据搬运物体形状确定了满足如下条件的m个搬运点： 当每个搬运点上都有一个具有给定位姿的机器人时，系统就能满足力锁合或物体锁合条件.如在图 1中，系统有8个机器人，所以围绕搬运物体有且只有8个搬运点.

搬运点模型是一个有基本运动方向线(PMDline)的质点，如图 1中的T₁～T₈所示.搬运点的PMDline指示着它的位姿或者搬运队形下一步的行进方向.

个体机器人R_i(i=1，2，…，m)的模型与文^[20]中相同，是一个半径为D_R、 有一条PMDline的圆.然而搬运点的PMDline是一条射线，R_i的PMDline却是一条从R_i中心P_Ri出发、 长度为S_MR的有向线段，其中S_MR是机器人的最大运动步幅.机器人的PMDline具有很多用途，详见文^[20].

系统中每个机器人的地位都是平等的，没有主次之分.R_i除了知道所有搬运点位置外，对其它环境都没有任何先验知识，必须使用它的传感器去感知它周边的环境和其它机器人.R_i的传感器是全方位的，其有效半径为D_V.对于环境中的任意一点F，只有当P_RiF不通过任何障碍和其它机器人且P_RiF≤D_V时，F才能被R_i探测到.为了尽可能地减少机器人间的通信量以提高算法的实时性，如果R_i探测到另一个机器人R_j，R_i才知道且仅知道R_j的位置、PMDline方向和对应搬运点.

假设1 若T_i在机器人R_i的探测范围内且在R_i的探测范围之内的所有机器人的搬运点都不为T_i，则机器人R_i认为搬运点T_i是空缺的.

后文的其它概念如不声明则都与文^[19]中的完全相同.限于篇幅，本文不再详述，详见文^[19].

初始时刻，假定所有机器人都在搬运物体附近.所以在本文中，除了搬运物体外不再考虑其它障碍.

注1 一条有向线(射线、有向线段)绕着它的端点旋转到与全局坐标系X轴方向相同时所转的绝对值不大于π的有向角称为该有向线的方向角^[16-17].设β_i为有向线l_i的方向角，β_j为有向线l_j的方向角，函数g(x)如式(1)所示，则β=g(β_i-β_j)就是从l_i到l_j的角.

(1)

其中.

注2 文中，P_Ri表示机器人R_i的位置(中心)； 符号L(A，B)表示从A点出发经过B点的射线； A₁A₂表示端点为A₁和A₂的线段； A₁A₂为线段A₁A₂的长度； β(A，B)为有向线段AB的方向角； D_S为与机器人安全相关的一个重要常数； λ_a为一个大于0.5且小于1的正常数.

3 人工社会职位法确定机器人搬运点

因为在自组织控制系统中不存在能对其它机器人发一些命令或指令的主机器人，个体机器人的地位相同且只能利用通过探测或通信得到一些局部信息，所以自组织形成群机器人复杂搬运队形的关键在于各机器人如何仅根据局部可用的信息，自主地确定自己的搬运点.

本文受到人们在求职或变更职位时常遵守的如下规则的启发而提出一种自组织确定各机器人搬运点的人工社会职位法.

规则1 初次求职时，人们总是申请与自己能力最接近的职位.

规则2 一个已有职位的人如果发现上一级职位空缺，则会主动放弃现职位去竞争上一级职位.也就是说，只要发现它的上一级职位空缺它就会想升迁.

注3 这一规则可以尽可能地保证上级职位不出现空缺.

规则3 一个已有职位的人如果它的职位被另一个更有能力的人抢占，则它通常可以直接获得比这个职位低一级的职位而不用考虑低一级职位是否有人担任.但通常情况下该人不会急着到新职位去履职而会等待一段时间，其中时间的长短与新旧职位间的差别有关，因为从概率论的观点看，职位被抢占是个概率事件，他还有继续获得该职位的可能.

注4 这一规则可以保证职位能够有序地变更.

上述3个规则是人工社会职位法的理论基础，也是该方法名称的由来.

如果按逆时针(规定方向是为了讨论的方便)的绕行方向对所有搬运点依次编号，并规定序号小搬运点的等级高于序号大的搬运点，序号最大的搬运点又是序号为0的搬运点，即又是序号最小的最高级的搬运点，则所有搬运点就构成了一个特殊的循环式的人工社会职位体系.

图 1中T₈又是T₀.所以下面叙述中，如果T_pi-1的下标pi-1=0则为搬运点T_m，T_pi+1的下标pi+1=m+1则为搬运点T₁.

然后把每个机器人看作一个求职者，每个搬运点看作一个职位，则各机器人搬运点的确定问题就可用求职者确定自己职位的方法解决.

上述就是人工社会职位法的基本思想与原理.基于人工社会职位法确定机器人R_i在当前时刻t_k搬运点的具体方法如算法1所示.

算法1 t_k时刻机器人R_i搬运点的确定：

Step 1 若t_k=t₀，则根据规则1，R_i将距离自己最近的搬运点选为自己当前时刻的搬运点.否则转Step 2.

Step 2 若R_i发现其t_k-1时刻搬运点的上级T_pi-1空缺，对任意能被R_i探测且其上个时刻搬运点也是T_pi的机器人R_q，R_i到T_pi-1的距离都比R_q到T_pi-1的距离近，则根据规则2，R_i将T_pi-1选为自己当前时刻的搬运点； 否则，转Step 3.

Step 3 若有能被R_i探测到的机器人R_q1，R_q2，…，R_qt，它们在t_k-1时刻的搬运点也是T_pi，R_iT_pi+1＜max(R_q1T_pi+1，R_q2T_pi+1，…，R_qtT_pi+1)且R_i可探测到T_pi及R_iT_pi＜T_piT_pi+1+D_S，则根据规则3，将t_k时刻R_i的搬运点变更为T_pi+1； 否则，转Step 4.

Step 4 若R_i探测不到它t_k-1时刻的搬运点T_pi或者它的吸引线段不为空，但R_i能探测到另一个空缺搬运点T_q且低于t_k-1时刻搬运点T_pi不超过m/2个等级，则将t_k时刻R_i的搬运点变更为T_q； 否则，R_i的搬运点仍为T_pi.

关于算法1的计算复杂度，显然可以用它在最坏情况下需要的比较次数来计算.设在R_i探测到的机器人中，上个时刻与R_i有相同搬运点的机器人有t个，则Step 2在最坏情况下需要t次比较；Step 3在最坏情况需要t+1次比较；Step 4需要1次比较.因此算法1在最坏情况下需要2t+2(≤2m)次比较，即算法1的时间复杂度为O(2m).所以算法1的时间复杂度非常低.

4 吸引点的改进计算与人工力矩运动控制器

确定了各机器人t_k时刻的搬运点后，各机器人在各自运动控制器的控制下向着t_k时刻自己的搬运点运动.采用文^[20]设计的人工力矩运动控制器是一个比较好的选择.这是因为该运动控制器具有许多优点，如能让机器人穿过狭窄的通道和到达距离障碍很近的目标且到达后还能具有给定的位姿，在复杂拥挤的环境下能快速地化解机器人间的冲突和保证机器人的安全等.

人工力矩运动控制器的基本思想是： 在当前时刻t_k，机器人R_i可能受到3种人工力矩的影响，即它的吸引点P_ati对它的吸引矩，危墙代表点对它的排斥矩及协调同伴对它的协调矩.在合力矩的作用下，R_i沿着合力矩的梯度方向改变它的位置和PMDline方向以使这些力矩能够快速地增加.另外，R_i沿着它的PMDline还有一个几乎不受人工力矩影响的运动分量(S_xi(k+1)，S_yi(k+1))^T，它和人工力矩函数一起决定着R_i下个时刻的位置和PMDline方向.下个采样时刻，重复上述步骤直到系统任务结束.

从人工力矩运动控制器的基本思想可以看出： R_i在t_k时刻需先计算出它的吸引点P_ati以引导自己绕过障碍物沿着较优的路径运动.而本文中机器人向着各自搬运点运动中会出现被搬运物体阻断的情况，因此在该情况下需要求解吸引线段来引导机器人绕过搬运物安全的达到搬运点.文^[17]给出了一种求解吸引线段的方法，但该方法的计算量大且难以理解.本文根据机器人当前时刻探测到的局部信息提出了一种计算吸引线段的新方法.

设各机器人把t_k时刻探测到的搬运物体边缘线以有向线段的形式保存在W｛i｝中.W的结构是W=[A₁B₁，A₂B₂，…，A_nB_n].其中有向线段A_nB_n的方向与本文的参考方向一致.

结论1 如果机器人R_i探测到自己与搬运点T_pi之间被搬运物体阻断，那么在W｛i｝中必然存在一条阻断P_RiT_pi的线段AB.

计算R_i的吸引线段方法如下：

令A_sti、 A_endi分别表示R_i吸引线段的起点与终点.计算R_i的吸引线段就是分别计算出A_sti和A_endi.通常情况下需先求出A_sti.当P_RiT_pi被搬运物体阻断时，很容易得到一条阻断P_RiT_pi的线段AB.显然A_sti可能是A或B.

A_sti的求解分3种情况：

(1) t_k时刻的T_pi不同于t_k-1时刻T_pi(k-1).该情况下只有t_k时刻的T_pi是t_k-1时刻的下级搬运点才会出现P_RiT_pi被阻断的情况，所以R_i向着搬运点的降级方向运动，即逆时针方向.所以此时R_i的A_sti应该为B.

(2) t_k时刻的T_pi与t_k-1时刻T_pi(k-1)时相同且A_sti(k-1)为空.这种情况下说明上个时刻P_Ri(k-1)T_pi没有被搬运物阻断.R_i应该由P_Ri向P_Ri(k-1)方向运动，则选择A和B中与P_Ri(k-1)在直线L(P_Ri，T_pi)同一边的点为A_sti.

(3) t_k时刻的T_pi与t_k-1时刻T_pi(k-1)时相同且A_sti(k-1)不为空.该情况下R_i的运动方向不需要改变，则选择A和B中与P_Ri(k-1)在直线L(P_Ri，T_pi)两边的点为A_sti.

得到A_sti后，按照如下方法计算A_endi： 若A_sti=B，R_i是沿着搬运物体边缘A到B的方向运动，即逆时针的方向，则令s=-1； 若A_sti=A，R_i是沿着搬运物体边缘B到A的方向运动，即顺时针的方向，则令s=1.A_endi是满足g(β(A_sti，A_endi)-β(P_Ri，A_sti))=s×π/2且A_stiA_endi=λ_aD_S的一个点.

根据上述方法即可求得R_i的吸引线段.

算法2 t_k时刻吸引线段与吸引点的计算：

Step 1 若P_RiT_pi被搬运物阻断，则执行Step 1.1～Step 1.3.

Step 1.1 如果A_sti不为空且P_Ri到L(A_sti(k-1)，A_endi(k-1))的距离大于S_MR，令A_sti=A_sti(k-1)，A_endi=A_endi(k-1)，转Step 3.

Step 1.2 如果T_pi不同于T_pi(k-1)，则A_sti=B，s=-1并计算A_endi，转Step 3； 否则，转Step 1.3.

Step 1.3 若A_sti为空，则令f=sgn(g(β(P_Ri，P_Ri(k-1))-β(P_Ri，T_pi)))； 若A_sti不为空，则令f=-sgn(g(β(P_Ri，P_Ri(k-1))-β(P_Ri，T_pi))).如果sgn(g(β(P_Ri，A)-β(P_Ri，T_pi)))=f，则A_sti=A，s=1； 否则，A_sti=B，s=-1.计算A_endi，转Step 3.

Step 2 若P_RiT_pi没有被搬运物阻断，则执行Step 2.1.

Step 2.1 如果A_sti不为空且P_Ri到L(A_sti(k-1)，A_endi(k-1))的距离大于S_MR，则令A_sti=A_sti(k-1)，A_endi=A_endi(k-1)，转Step 3； 否则，令P_ati=T_pi，清空A_sti和A_endi并结束算法.

Step 3 令P_ati=A_endi，结束算法.

算法2 求解新的吸引线段时，A_sti很容易得到，只需要判断A_sti是阻断线段AB上的A点还是B点即可，然后根据A_sti计算A_endi即可求出R_i的吸引线段.因此其计算量明显小于文^[20]给出的方法.

人工社会职位法自组织形成复杂搬运队形的一般步骤如算法3所示.

算法3 复杂搬运队形自组织形成的步骤：

Step 1 初始化所有机器人的位置； 输入搬运物体形状、 所有搬运点，规定参考方向； 输入系统参数； 令t_k=t₀.

Step 2 根据人工社会职位法的规则1得到初始时刻R_i(i=1，2，…，m)的搬运点.

Step 3 For R_i(i=1，2，…，m)，执行如下步骤：

Step 3.1 如果R_i已到达了它的搬运点且没有协调同伴，则R_i保持静止.否则，执行Step 3.2～Step 3.4.

Step 3.2 如果k>0，则运用算法1得到R_i的搬运点.

Step 3.3 运用算法2计算出P_ati、 A_sti和A_endi.

Step 3.4 运用文^[20]中的人工力矩运动控制器控制R_i运动一步到达下个时刻与位置.

Step 4 End for

Step 5 如果每个机器人都到达了它的搬运点，则结束算法； 否则，令t_k=t_k+1，然后转Step 3.

据算法3可得： 与文^{[12, 17-18]}中的方法相比，本文中的方法更适用于一般的情况，因为文^{[12, 17-18]}给出的方法只适合简单的凸多边形搬运物体，无法形成本文仿真中的复杂搬运队形.与文^[21]中的方法相比，本文给出的方法不会出现文^[21]中主机器人出现故障将导致整个系统瘫痪、 一旦搬运物体的形状发生变化就需要重新规划等问题.主要原因是由于本文中提出的是一种自组织的形成方法，系统中不存在一个主机器人，所以即使个别机器人出现故障也不会影响到其它机器人的运动.

5 仿真结果与分析

为了检验文中有关理论和方法的可行及有效性，本文做了大量的仿真，图 2～图 4给出了几个具有代表性的仿真，分别为25、 32、 43个机器人在不同环境中自组织形成复杂搬运队形的仿真.

在该仿真中，系统部分参数值如表 1所示.图 2(a)、3(a)、 4(a)中，小的带有基本运动方向线的圆圈表示搬运点； 大的带有基本方向线的圆圈表示机器人； 机器人与搬运点旁边的一组数字是其对应的序号； 图 2(b)、3(b)、4(b)中的彩色实线是机器人在自组织形成复杂搬运队形中留下的实际运动轨迹，小的红色圆圈是机器人的初始位置.

从图 2(b)、3(b)、 4(b)中可以看出，在3个仿真中，各机器人都能有序地变更自己的搬运点，最终都能自组织快速地运动到一个不同于其它机器人的搬运点并形成给定的搬运队形.从而证明了本文所给出的自组织确定各机器人搬运点的方法是可行且有效的.

另外，从图 2(b)、3(b)、4(b)中还可以看出，当各机器人到自己的搬运点被搬运物体阻断时，各机器人都能够光滑地绕过搬运物安全地到达搬运点，同时到达后还能具有与搬运点相同的位姿，从而证明了文中给出的关于吸引线段及吸引点的计算方法是可行且有效的.

6 结论

在系统已经根据搬运物体形状和机器人数量确定了所有搬运点的前提下，本文针对群机器人搬运队形的形成问题提出了一种自组织的人工社会职位法.该方法原理简单计算量小且无论机器人的数量是多少，无论搬运物体的形状多复杂，系统总能快速地形成满足条件的搬运队形.

另外本文还改进了现有人工力矩运动控制器中吸引线段与吸引点的计算方法.改进方法不但原理易懂求解简单且降低了计算量.

下一阶段，本文将研究如何继续改进现有的人工力矩运动控制器，使其能够驱动群机器人队形协调地运动以把物体从初始位置拖拉或搬运到给定的目标位置.