复杂环境下群机器人自组织协同多目标围捕

张红强 ,吴亮红 ,周 游 ,章 兢 ,周少武 ,刘朝华

(1.湖南科技大学信息与电气工程学院,湖南湘潭 411201;2.湖南科技大学机电工程学院,湖南湘潭 411201;3.湖南大学电气与信息工程学院,湖南长沙 410082)

1 引言

群机器人系统是一种移动的分布式系统,具有高密度特点并具有鲁棒性、可扩展性和灵活性.这些重要特征使得群机器人系统相较于单个机器人或多机器人系统更有希望完成大规模任务[1].

要同时执行大量任务,任务分配作为关键问题直接影响着各种各样的分布式系统的性能[2].通过任务分配这种集体行为,机器人能够处理不同任务.任务分配的目标是通过使机器人动态选择需要完成的任务从而最大化系统的性能[3].在群机器人任务分配研究方面几乎大部分集中在机器人觅食上,而其任务分配方法就是基于不同场景和条件下概率的有限状态机[4–9]或者基于固定阈值或自适应阈值进行任务分配[10].另外,还有基于拍卖[11]、基于启发式方法[12]以及基于市场的任务分配方法[13].

尽我们所知,目前仅有少数工作关注了具有时间约束的群机器人任务分配.具有弱期限的任务非常适合群机器人系统[2].拍卖策略是应用最频繁的之一,参见文献[14].除了已经建立的很好的拍卖策略,启发式方法用于机器人带时间约束的任务分配也得到了介绍,如文献[15].在文献[13]中,基于市场的任务分配策略也进行了介绍,在这里时间是主要的关键约束.基于概率的方法参见文献[2,16],这里同样一起考虑到了成功完成任务时的奖励机制.

本文研究的群机器人多目标围捕任务属于需要多个单一任务机器人的即时分配的多机器人任务[17],这是一个弱时限问题[2].与前述时间约束下的群机器人任务分配文献不同的是,对于多动态目标围捕,任务完成的时间固然重要,但最关键的是任务分配所花费的时间长短,因为如果时间太长,有可能会导致目标已经逃离围捕机器人的感知范围,造成个别目标围捕失败.而上述基于市场、基于拍卖的方法,往往需要一个Leader或仲裁者来统领或裁决,需要团体内的机器人均与其通信,会产生通信瓶颈,只适合小规模机器人任务分配.而且任务分配过程复杂、时间长.基于酒吧系统的启发式任务分配方法,需要知道全部机器人的数量和速度,通信和计算量大,而且解决的是只需要单个机器人就可以完成的任务分配问题,并不适合需要多个机器人协作完成的多目标围捕问题.基于概率的方法需要知道机器人数量并离线计算决策矩阵,其分配任务的过程复杂.

关于群机器人多目标围捕的研究成果不多.熊举峰等[18]提出基于虚拟力的群机器人围捕算法.然而受力分析复杂、可扩展性差.Kubo等[19]提出一种群机器人多目标围捕算法.然而,这里的多目标是静止的,而且环境中无障碍物.Dutta[20]介绍了Kamimura和Ohira以及Angelani的多目标离散化围捕模型,但初始化时是随机分布、无障碍物、无对抗、路径特殊、不需要形成一定的围捕队形.Yasuda等[21]基于进化人工神经网络(evolving artificial neural networks,EANNs)研究了群机器人在连续二维环境下多目标单层围捕及搬运问题,但环境中无障碍物.

实现大规模群机器人动态多目标围捕的挑战在于如何使得当动态多目标四散逃跑时每个机器人自组织地实现任务分配,不但要保证每个动态目标都有足够多的机器人参与围捕,还要保证最远目标有最多的机器人参与围捕,从而保证围捕成功率;而且任务分配时需要的信息是尽可能少的局部信息,并且分配任务的时间要非常短,任务分配算法尽量简单,否则任务尚未分配完毕,目标可能已经逃离;分配了不同围捕目标的机器人之间如何避碰,如何减少运动距离;如何在未知动态障碍物环境中做到既保持多目标围捕队形又成功避障,而且由极少的局部信息控制个体的运动.

为了实现动态多目标围捕,本文完善了文献[22]中的单目标简化虚拟受力模型(simplified virtual-force model,SVF–model),围捕个体基于两最近邻和目标的施力就可以实现自主运动(计算简单,高可扩展性),设计了基于个体面向多目标中心方向两最近邻任务信息的动态多目标任务自组织分配方法,结合受力模型和任务分配方法提出了自组织协同动态多目标围捕方法.在围捕过程中机器人个体还可以根据距离目标的远近与近邻交换围捕目标,达到避障的同时节省能量.

2 模型设计

2.1 围捕个体模型及相关函数

围捕个体hj(j=1,…,m)的模型请参看文献[22]中图1所示,hj的运动学方程及其相关参数范围参看文献[22]中式(1)–(2).

围捕目标和近邻对象(包括不是被hj围捕的目标、动态或静态障碍物以及机器人)的施力函数分别为

其中d与文献[22]中式(5)–(6)里面的z是一致的.不同之处是i=4表示对象是非自己围捕的目标时所用的具体参数,dsp是开始向有效围捕圆周上运动时机器人与目标的距离,其他参数与文献[22]中式(5)–(6)是一致的.而且这里用两个条件来判断何时向有效围捕圆周上运动(文献[22]中只用了ncdsp用来保护围捕机器人不要太靠近目标,防止受损;当d>dsp失效即机器人有时很难在一定距离范围内接近目标时,nc

对于凸障碍物,利用文献[22]中仿生智能避障映射函数(4)进行有效避障.为了确定两有向线之间的角度,利用文献[23]中式(1)进行计算.

2.2 围捕任务模型

通过研究狼群多目标围捕发现[24–25],其捕食过程首先是多任务分配,然后针对各个目标的行为与文献[22]相似.多目标中单个目标的运动方程与文献[22]中相似.不同之处是整个围捕环境及相关参数的说明是在文献[22]中第2.2节定义1的基础上扩展了多目标的定义,这里T={tp:p=0,1,…,e}是指各个具体的目标,而t0是指多目标的中心.势和势角的定义同样是在文献[22]中第2.2节定义2的基础上扩展了多目标势和势角的定义,PT={ρtp},p=1,…,e是目标势,而文献[22]定义1和定义2表达式中凡是针对单目标的扩展为多目标即可.由上述描述给定复杂环境下多目标的运动方程是将文献[22]中式(7)里面的单目标符号t1变成tp(p=1,…,e)并对相关参数给定初值即可.障碍物环境下动态障碍物ui的运动方程与文献[22]中式(8)一致.由围捕环境、动态多目标以及动态障碍物模型的构建形成了整体的多目标围捕任务模型.

与文献[22,25–26]所描述的围捕过程不完全一样,本文用dsp和l两个参数来控制捕食者到猎物之间的距离,这比只用一个参数l来控制更科学一些,具体控制特点参看式(1)中的说明.当只用一个参数l时方便控制追捕的时间,而不方便控制与猎物之间的距离.

3 围捕算法

本文在文献[22]的基础上提出了多目标简化虚拟受力模型(multi-target simplified virtual-force model,MSVF–model),给出多目标自组织任务分配算法和复杂环境中群机器人协同围捕动态多目标的算法,使得整个群体实现复杂环境下的动态多目标自组织围捕.

3.1 多目标简化虚拟受力模型

本文研究的动态多目标围捕模型是在文献[22]中提出的单目标简化虚拟受力模型的基础上完善的.图1是多目标简化虚拟受力模型,与单目标的简化虚拟受力模型不同之处是围捕环境中包含有多个目标,hj受到自己围捕目标的引力或斥力作用,其他目标则作为近邻对象处理.而其他符号的说明与文献[22]中定义3一致.由于多目标简化虚拟受力模型继承了单目标简化虚拟受力模型的受力分析方法,使得围捕个体不存在局部极小值问题.由上述相关说明可得到当目标静止时hj的需求速度为

其中:ftpj()是目标tp(p=0,1,…,e)的施力函数,按式(1)计算.其他符号意义及计算同文献[22]中式(9)的相关说明.

图1 多目标简化虚拟受力模型Fig.1 MSVF–model

3.2 基于MSVF–model的个体控制输入设计

未知复杂环境中围捕时各机器人hj运动学方程的控制输入与文献[22]中基本一致,不同之处是vje,θje按式(4)来确定:

其中:j=1,2,…,mp,p=0,1,…,e,…,e)是个体感知目标tp的速度矢量,是个体感知多目标中心的速度矢量.这样每个个体可以针对自己的围捕目标进行围捕,从而实现多目标围捕.

3.3 围捕算法步骤

针对第2.2节中的围捕任务模型,结合了MSVF–model和多任务分配策略的未知凸动态障碍物环境下的群机器人协同动态多目标围捕算法流程图如图2所示,这里需要进行任务分配和交换围捕目标,而基于SVF–model的单目标围捕算法没有这些内容[22,26].值得指出的是,该流程图不但适用于动态多目标也适用于动态单目标以及静态单、多目标的围捕.而图2中“基于hj面对多目标中心方向180o范围内的两最近邻进行任务分配”的算法流程图如图3所示,这里的“hj面对多目标中心方向180o范围内”是指以hj指向多目标中心方向线为中心的左右90◦之间的范围.而图2中“交换围捕目标”是每个机器人根据面向多目标中心180◦范围内的最近邻机器人的围捕目标和自己的围捕目标交换前后是否会减少整体的运动距离而进行决策的.

图2 多目标围捕算法流程图Fig.2 The flow chart of multi-target hunting algorithm

由图3可知,动态多目标围捕的任务分配只需要根据hj面对多目标中心方向180◦范围内最多两个近邻机器人的任务分配信息就可以完成,任务分配是自组织、分布式地进行,没有统一的领导者或裁判,算法简单而且高效,使得大规模群机器人的任务分配可以在短时间内完成.这里需要注意分配任务时,要将目标进行排序,任务0是指多目标中心,任务1到e则是指具体的围捕目标,任务1到e分别是指最远的目标、次远的目标、次次远的目标、…、次次近的目标、次近的目标、最近的目标;这样排序可以使得最远的目标(也就是最难围捕的目标,因为其最容易逃离群机器人的感知范围)分配到最多的围捕机器人,保证整个围捕的成功率.

图3 hj任务分配流程图Fig.3 The flow chart of hj task allocation

由任务分配算法和多目标围捕算法可知,每个机器人hj仅需两个近邻的任务信息来决定围捕哪一个目标.任务分配之后,每个机器人hj将可能与前面最近邻机器人交换围捕目标,减少运动距离和能量消耗,提高了围捕效率,同时也减少了机器人之间相碰的可能性.接着,每个机器人每一步的运动方向和速度大小将根据目标和两最近邻来确定.因此,整个围捕算法是分布式的和自组织的.

4 稳定性分析

系统的稳定性分析需要分3部分进行:第1部分首先说明群机器人的自组织动态多目标任务分配算法是稳定并合理的,这是文献[22]所没有的;第2部分在无障碍物环境下,对群机器人分成各个子群围捕每个动态目标的子系统进行稳定性分析;第3部分在未知动态凸障碍物环境下,分析群机器人对每个动态目标进行围捕的子系统的稳定性.第2部分和第3部分是将文献[22]所提出单目标围捕稳定性理论推广到了多目标围捕的子系统稳定性分析中去,所以它们之间较相似.

4.1 任务分配算法的稳定性分析

本节主要说明任务分配算法的稳定性,其流程图如图3所示.动态多目标围捕任务分配的基本要求是:第1,确保每一个目标都有足够多的机器人参与围捕,假设每个目标至少需要3个机器人围捕,最多不限;第2,在统计数据平均值的意义下,最远目标有最多机器人参与围捕;第3,分配任务的时间要尽量短,而且当机器人数量增加时,分配任务的时长按线性增长而不是按指数级增长;第4,任务分配算法需要的信息量尽量少,算法本身是分布式的,而且尽量简单.

仿真环境是用MATLAB 2013a的随机函数rand(·)随机生成在10 m×10 m范围内分布的群机器人初始位置,动态多目标的位置则人为给定.下面针对任务分配的基本要求给出相应说明.为了达到任务分配的第一个要求,需要满足的条件是围捕机器人群体中个体的数量与目标个数之间有一个基本比例的要求,如表1所示,这是由大量仿真统计得到的.为了满足第2个要求,需要满足两个条件,第1个,同样要满足表1;第2个条件是,需要在任务与动态目标之间确定一种对应关系,参看第3.3节相关说明.

分配任务随着机器人数量增加而消耗的时间分布图如图4所示.图4是当目标为50个时,50次任务分配仿真中消耗的最长时间随着机器人的数量增加时的变化图.在图4中,机器人数量由2000增加到了5000,数量增加了1.5倍,而消耗时长由22步增加到27步,只增加了0.23倍.由图4可以看出,当机器人数量成倍增加时,其任务分配消耗的时间则是以线性增加的,而且当机器人数量继续增加时,任务分配消耗的时长增长变慢(当机器人数量增多时,任务分配时由于更多的分配路径使得消耗的时间增长越来越慢),即使机器人规模达到5000个时,任务分配时消耗的最大时长也才27步,如果不考虑通信的时间花费(获取两个最近邻的任务分配信息可以简单地通过隐式通信得到,例如可以把不同任务用不同颜色的信号灯来表示,这样可以迅速获取信息并迅速决策自己的任务),按每步1 s的运动时长计算,其任务分配时长也只有几十秒而已,因此消耗时间较短.由此说明了所提任务分配算法可以满足第3个要求.

表1 给定目标个数时围捕机器人群体中个体的最少数量表Table 1 The least quantity table in a swarm of hunting robots when giving the number of targets

图4 任务分配消耗时间随机器人数量变化趋势图Fig.4 The tendency chart of the time consumption of task allocation distribution with robots quantity increasing

由任务分配算法流程图(图3所示)可以看出,机器人个体任务分配过程只是根据其面对多目标中心方向180◦范围内的两最近邻的任务分配信息来进行,这说明算法本身需要的信息量少,而且是分布式的.整个任务分配算法流程简单,任务分配时计算只用了加法,可见其足够简单,满足第4个要求.

4.2 无障碍物环境下稳定性分析

针对多目标围捕系统无障碍物环境下的稳定性分析采用了文献[22]的方法.不同之处是需要推导每个目标都被围捕机器人成功围捕时所需要的条件,围捕每一个目标看作是一个子围捕系统,需要推导每个子围捕系统都稳定的条件,即把文献[22]中定理的证明看作是一个围捕子系统稳定条件的推导过程.系统偏差分解为个体到目标距离偏差δjy′=r,j=1,…,mp,p=1,…,e(这里mp是指围捕目标tp的机器人个数,δjy′定义与文献[22]中不一致,这里的目标包含了所有目标)和个体到两最近邻机器人距离偏差的一半δjabx′[22](δjabx′的定义与文献[22]中形式一致,但下标含义不一致,这里j=1,…,mp,p=1,…,e,把围捕时的机器人分成了多个子系统来分析,第4.2节和第4.3节式中j的含义均同这里).

个体的自主运动偏差方程[22]:

另一个不同之处是vy′j(k)是vy′j的离散化形式,可以按式(7)来计算

vx′j(k)可以参看文献[22]中式(20).

定理1在无障碍物的环境中,如果每个目标的围捕机器人满足式(5)、(k)dsp或ncl以及0

为大范围渐近稳定,其中p=1,…,e.

证由于证明过程与文献[22]中定理1的证明过程相似,这里省略.

根据定理1,选择了不同目标的个体将会到达不同目标为中心的有效围捕圆周上(这是与文献[22]中定理1结论不同之处,文献[22]中只会到达唯一目标为中心的有效围捕圆周上),如果要实现均匀分布,还需要考虑当(k)r|<ε1,j=1,2,…,mp,p=1,…,e时δjabx′(k)即式(6)的收敛性[22].

定理2在无障碍物环境下,如果每个目标的围捕机器人满足式(6)和0<则系统原点平衡状态,即

为大范围渐近稳定,其中

证由于证明过程与文献[22]中定理2的证明过程相似,这里省略.

因此,同时满足定理1和定理2,在有限时间内可使围捕四散分布的静态多目标的个体均匀分布在每个目标为中心的有效围捕圆周上或围捕聚集在一起的静态多目标的个体均匀分布在不同目标的有效围捕圆周的连续弧段上.这是与文献[22]中满足定理1和定理2时所得结论不同之处,文献[22]中的有效围捕圆周只有一个.说明本文围捕算法具有较强的灵活性.定理1和定理2还说明了如何通过调节时间步长或相关参数以达到稳定条件,有关如何调节参数与文献[22]相似.

动态多目标以漫步速度逃逸被成功围捕的一个充分条件为

这个充分条件的推导过程和相关说明与文献[22]中式(26)相似,不同之处是这里围捕的目标是指多目标.

4.3 凸障碍物环境下稳定性分析

这里根据目标方向距离偏差δjy′和两最近邻对象距离偏差对系统进行分析[22].采用

上式包含了多目标,与文献[22]不同,障碍物环境下的分析同定理1,原因请参考文献[22].δ′jabx′的定义与文献[22]中的定义形式一致,但下标含义不一致,这里j=1,…,mp,p=1,…,e,个体的自主运动偏差方程如式(9)[22]:

其中:j=1,2,…,mp,p=1,…,e,vx′j(k)可参看文献[22]中式(20).

定理3在凸障碍物环境下,如果每个机器人满足式(9)和0<Γd1µ′<2,则系统原点平衡状态,即

为大范围渐近稳定,其中:

证由于证明过程与文献[22]中定理3的证明过程相似,这里省略.

因此,在障碍物环境中对于四散分布的或聚集在一起的静态多目标,同时满足定理1和定理3,即可使围捕个体受力平衡地分布在多个目标的有效围捕圆周上或其连续弧段上.这是与文献[22]的不同之处.这里同样给出了系统不稳定时参数调节方法,即调节c1,d1或Γ等[22].

动态多目标以漫步速度逃逸被成功围捕的一个充分条件为

这个充分条件的推导过程和相关说明与文献[22]中式(30)相似,不同之处是这里围捕的目标是指多目标.最终的围捕队形同样会由于存在四散分开的动态多目标和聚集在一起的动态多目标而会呈现不同的围捕队形,但整体上都会是受力均衡的围捕队形.这也是与文献[22]的不同之处.

5 仿真与分析

为了与文献[22,25–26]作对比分析,本节针对第2.2节构建的动态多目标,通过未知动态凸障碍物复杂环境下的仿真讨论多目标围捕算法的灵活性、可扩展性、避障性能以及鲁棒性.表2是系统的参数设置,表3是机器人避碰/避障参数值,表4是多目标和动态障碍物避障参数值.

表2 围捕系统参数值Table 2 The hunting systems parameters

表3 机器人避碰/避障参数值Table 3 Avoiding collisions parameters of the robots

表4 目标和动态障碍物避障参数值Table 4 Avoiding collisions parameters of the targets and dynamic obstacles

本节仿真使用30个机器人在含有13个凸障碍物的环境中围捕3个目标,表5是它们的初始坐标,时间步长Γ=0.6 s.由于本文研究的是多目标围捕,群机器人的围捕过程与文献[22,25–26]中的单目标围捕不完全一致.图5是仿真轨迹.每个围捕机器人用圆点表示,其右上角符号代表围捕的目标,右下角符号代表围捕机器人的序号.图5(a)中,经过3步时间,群机器人个体运用自组织分布式任务分配算法,根据面向多目标中心180◦范围内最多两最近邻的任务分配信息自动地选择了自己的围捕目标,选择结果是最近目标t1、次近目标t2、最远目标t3分别有8个、10个、12个机器人围捕,最远目标t3具有最多的围捕机器人.由此图还可以看出围捕3个目标的机器人混杂在一起.

表5 仿真中目标和群机器人初始位置坐标Table 5 Initial coordinate values of targets and swarm robots in simulation

图5(b)中,通过交换围捕目标,到第8步后,整体上围捕左上方目标t1的机器人位于左上方,而围捕右下方目标t3的机器人位于右下方,这样由于围捕同一目标的机器人在一起,运动整体上协调一致,避免了不必要的避碰,而且还减少了运动距离和能量损耗,同时也提高了围捕效率.

图5 30个机器人围捕3个目标Fig.5 30 robots hunting 3 targets

余下的围捕过程与文献[22,26]一致.复杂环境使得群机器人在围捕多目标时,不仅要对目标进行包围,还要避开障碍物,增加了机器人之间进行协作的难度.而多目标简化虚拟受力模型使得群机器人不仅能避开障碍物,还可以与障碍物形成协同围捕的队形,如图5(e)–5(g)所示.整个群体在机器人数目是文献[22,26]机器人数目5倍、目标增加了两个的复杂环境下实现了多目标围捕,说明本算法的灵活性、可扩展性、避碰/避障性能和鲁棒性较强.

6 本文基于MSVF–model的围捕算法与其它算法的比较分析

本文基于MSVF–model的方法与基于松散偏好规则(loose-preference rule,LP–rule)的方法[25]相比优势如下:1)文献[22,26]中基于SVF–model的方法与基于LP-rule的方法相比的优势,本文算法同样具有;2)本文算法还可以围捕静态或动态的单个或多个目标,而基于LP–rule的围捕算法没有考虑围捕多目标;3)本文算法比基于LP–rule的围捕算法具有更好的灵活性.

本文基于MSVF–model的围捕算法与其它基于SVF–model的围捕算法[22,26]相比优势如下:1)本文考虑了如何围捕动态多目标,而其它围捕算法没有考虑;2)本文算法在多目标围捕方面的灵活性优于其它算法.

本文基于MSVF–model的围捕算法与其它多目标围捕算法相比优势如下:1)文献[27]研究了多目标导航问题,该问题涉及一组智能体协调地对多个运动目标进行导航,采用分布式算法,并分析了稳定性.然而,环境中没有考虑障碍物,多目标整体上在一起运动,而不是四散运动.而本文所提算法不但可以适应运动目标四散运动,也适应多个目标一块运动,同时考虑了避障问题;2)文献[28]针对地面存在障碍物和约束的环境中群机器人捕获多目标提出了一种自适应模式形成的方法.但个体需要全局信息,可扩展性差,因此对于多目标、大规模群机器人围捕的适应性较低,而且环境中没有动态障碍物,也没有对系统进行稳定性分析.而本文所提算法基于局部两最近邻信息就可以实现自组织任务分配和围捕队形的形成,在避障时不需要根据障碍物的形状来进行,只需要感应到障碍物上的至多最近两点的距离就可以实现避障,算法简单易于实现,同时考虑了环境中动态障碍物的避障问题.

7 总结

本文研究未知动态凸障碍物环境下群机器人自组织协同动态多目标围捕问题,在完善文献[22]中单目标简化虚拟受力模型的基础上构建了MSVF–model,设计了动态多目标自组织任务分配算法和动态多目标协同围捕算法.在理论上分析了整个围捕系统的稳定性,给出了稳定性条件,对系统参数设置有较好的指导作用.由仿真验证了基于MSVF–model的多目标围捕算法具有更好的灵活性、可扩展性、鲁棒性和避障/避碰性能.最后,与其它围捕方法进行了对比分析.