未知环境下群机器人多目标搜索协同控制

王 茂 周少武 张红强 吴亮红 周 游 何昕杰

(1.湖南科技大学信息与电气工程学院,湖南湘潭 411201;2.湖南理工职业技术学院,湖南湘潭 411206)

1 引言

群体智能是受自然界社会型生物的群体行为所启发,是简单信息处理单元在信息交互中涌现的解决问题的能力,信息处理单元之间相互独立,是一种分布式方法.群机器人系统是以简单机器人为信息处理单元的群体智能系统,具有典型的分布式的特点,而机器人个体有着同构、结构简单的特点[1].机器人与机器人之间以及机器人与环境之间有着简单的交互,根据交互获得的信息,各个机器人进行分布式运动,而在整个机器人系统上涌现出智能行为,进而可以完成一定的任务[2].群机器人技术可广泛应用于灾后搜救[3-4]、物料搬运[5]、环境探测[6]、目标围捕[7-9]、火灾监控等任务中[10],在军用、工业和民用等领域有着广泛的应用[11-14].

目标搜索是群机器人的一个应用方向,可运用于搜救、搜寻某种信号源、勘探自然资源、探测敌军位置等[15].XUE等[16]将群机器人搜索映射到粒子群优化(particle swarm optimization,PSO)并提出时变字符群(time-varying character swarm,TVCS)的概念后,基于预期演化位置的控制原理,提出了一种异步通信策略,该通信策略在搜索效率体现出一定优越性;ZHANG等[17]针对多目标搜索提出多目标搜索中的合作协同和竞争协同以扩大感知范围降低空间冲突;类比于物理环境中引力等引入人工势场函数[18-19],ZHANG等[20]针对复杂环境提出一种基于简化虚拟受力模型的循障方法,ZHOU等[21]引入简化虚拟受力模型的循障与避碰方法于群机器人搜索中,使得机器人兼顾避障与搜索;CAO等[22]将Glasius仿生神经网络(Glasius bio-inspired neural network,GBNN)和仿生级联跟踪控制方法结合,提出了一种多自主水下航行器协同团队集成算法,该方法参数少,并可解决速度跳跃问题;LI等[23]提出一种概率有限状态机和三角形梯度估计的方法,平衡了探测与搜索、并行性与协作性,并提高了一定的搜索效率;TANG等[24]提出一种自适应机器人蝙蝠算法,考虑了避障问题及跳出局部最优的机制.然而上述方案中没有针对复杂障碍物的高效避障方法,且在搜索方法上未充分利用可获取的目标信号.

以上述研究为基础,本文提出一种边界扫描的避障策略和一种目标位置估计的粒子群算法(boundary scan obstacle avoidance strategy and target position estimation particle swarm optimization,BSOA-TPEPSO),与其他方法相比有效地提高了针对复杂障碍物的避障效率,同时也提高了目标搜索的效率.在下面的内容中,第2节构建合适的模型以便验证分析所提方法;第3节详述所提的新方法;第4节分析文中所提方法的收敛性;第5节将文中所提方法与基于简化虚拟受力分析模型的循障避碰方法(simplified virtualforce obstacle avoidance method,SVF)、扩展粒子群算法(extended particle swarm optimization,EPSO)、自适应机器人蝙蝠算法(adaptive robotic bat algorithm,ARBA)仿真比较,验证所提方法的搜索性能,并分析仿真结果;第6节总结文章内容并对后续研究做出展望.

2 模型的构建

有限的二维空间内,全集A={R ∪T ∪B},其中群机器人R={Ri|i=1,2,···,NR;NR≥10},目标T={Tj|j=1,2,···,NT;NT>1},障碍物B={Bs|s=1,2,···,NB;NB≥1},三者位置分别表示为Xi(t),Tj(xj,yj),Bs(xs,ys),机器人及目标用质点表示.群机器人R作为搜索主体,任务是搜索到所有目标T,同时避免与障碍物及其他机器人发生碰撞.当存在机器人与某个目标的距离Td小于目标到达阈值L0,即视为搜索到该目标.机器人的通信与感知都是局部的,考虑最大通信半径Lcm,最大障碍物感知半径LB,最大目标感知半径LT,机器人与其他机器人、目标、障碍物的欧式距离分别为Rd,Td,Bd.机器人可在特定条件下实现特定功能:Rd≤Lcm时,机器人之间可通信;Td≤LT时,可探测目标信号;Bd≤LB时,可探测障碍物位置.

2.1 目标信号

机器人搜索目标时,无法得知目标的位置,但可以不间断地通过传感器探测周围目标的信号.假设每个待搜索的目标类似,但目标信号频率有所区别,机器人可根据探测到的目标信号频率区分目标.机器人探测到的目标信号将满足目标响应函数

其中:Iij表示机器人探测到的目标信号;η为环境干扰的随机量;机器人无法获取Td,但Td影响机器人探测目标信号的大小;G(Td)表示在无干扰的环境中目标信号的衰减函数,搜索前可根据目标信号与距离的数值关系求得近似解.

2.2 基于目标信号的动态分工

群机器人在搜索目标时,总任务是搜索到所有目标,而搜索某个目标可以视为一个子任务,完成相同子任务的机器人所成集合称为子联盟,该过程中的机器人所处状态称为协同搜索状态,机器人按照以下方式组成子联盟.

借鉴文献[21,29]中任务分工方法,将可获取目标信号的机器人分为两类:由自身传感器探测到目标信号的机器人记为I类机器人,由机器人之间的通信获取目标信号的机器人记为II类机器人.当I类机器人探测到多个目标的信号,先选择Iij >Imin的目标作为备选目标,再选取上一步相同的目标,若无相同目标则经轮盘赌法选择当前唯一的协同搜索目标,其中Imin表示目标响应阈值.轮盘赌法可用以下等式表示:

其中ki表示被机器人Ri作为备选目标的数量.当P(i,j-1)

在上述子任务分配后,相同子联盟中机器人可能过多,造成机器人资源浪费.因此进一步引入闭环调节,即在上述子任务分配结束后,再评估各个子联盟的资源分配[29].当某个子联盟的机器人数g >gmax,该子联盟择优选取gmax个机器人作为该子联盟个体,其中gmax为子联盟机器人最大允许个数(择优原则为:优先选择I类机器人,I类机器人中优先选择目标信号强者,II类机器人选择距离通信机器人近者).选取示例详见表1[21].

表1 子任务机器人排序Table 1 Sequence of subtask robots

取gmax=6,表1中按照择优原则排序,最终机器人R79,R8,R81,R59,R92,R156个机器人保持联盟完成子任务,机器人R61,R96退出子联盟.

2.3 群体状态协调控制

组成子联盟的机器人搜索对应的目标;每个子联盟作为子种群,以目标位置估计的粒子群算法优化机器人位置,以实现目标搜索;其他的机器人则进行漫游搜索,依据简化虚拟受力模型运动;当机器人搜索到目标后,完成状态声明.上述可总结为机器人的3种状态:组成子联盟的协同搜索,按照简化虚拟受力运动的漫游搜索,搜索到目标后的状态声明[27].3种状态的迁移可用图1表示.

图1 状态迁移关系Fig.1 State transition relationship

3 群机器人系统控制

目标搜索需在同等情况下尽可能减小运动轨迹长度及搜索时长,本文按照位置迭代的方式进行搜索,因此搜索时间用迭代步数t替代.本文提出一种边界扫描的避障策略及目标位置估计的粒子群算法以提高目标搜索效率.

3.1 机器人运动模型

文中考虑二维环境下的目标搜索,机器人的运动学方程可表示为

3.2 目标位置估计

在此介绍提出的目标位置估计,以便进一步介绍目标位置估计的粒子群算法(TPEPSO).存在环境干扰的情况下,由式(1)可估计机器人与目标的距离Td≈G−1(Iij).在群机器人搜索目标时,目标响应函数无法得知,因此G−1(Iij)无法直接获取.在进行目标搜索之前,测试目标信号与距离的数值关系:在与目标信号源距离为(1,LT)之间均匀取ς个不同距离,分别独立测量100次信号,对每个位置的信号取平均值得到距离为dξ时平均的目标信号为Iξ,以此为基础进行插值,即可得到Td与Iij之间的近似函数关系

环境中存在干扰,因此方程(8)无解,此处考虑最小二乘解,由式(8)两边移项开根号后得到残量范数

Tj(xj,yj)≈Test(x,y)=arg min(f(x,y))为所求,本文采用基于杂交的粒子群算法,求其近似解.

3.3 目标位置估计的粒子群算法

将群机器人的协同搜索过程映射到PSO算法迭代过程[16],以迭代更新机器人位置.因在群机器人搜索目标时仅可获取子任务的目标信号,全局最优取子联盟的最优,即半全局最优;而个体历史最优取加入子联盟后的历史最优.粒子群算法与上述的目标位置估计结合,得到目标位置估计的粒子群算法(TPEPSO):

其中:Vip(t+1)为TPEPSO计算得到的(t+1)步机器人Ri的速度;Vif(t+1)为(t+1)步Ri考虑运动惯性后的期望速度;Xif(t+1)为(t+1)步Ri的理想位置;c1,c2,c3分别为认知系数、社会系数、位置估计系数;r1,r2,r3是服从U(0,1)的随机数;ω为惯性权重;α是运动惯性环节;pbi为个体历史最优;sgb为半全局最优;Test为式(10)得到的位置估计.

3.4 边界扫描的避障策略

在目标搜索过程中,不论漫游搜索状态或协同搜索状态,机器人都可能遇到凸或非凸的障碍物.凸障碍物即障碍物点所成集合为凸集,凸障碍物避障比较简单,但对非凸障碍物避障时容易陷入局部最优问题.传统的处理方法是考虑最近两个障碍点所成方向左或向右循障运动,这种方法虽解决了非凸障碍物避障的问题,但是避障距离较长.这里将机器人探测到障碍物的情形进行归类后简化,提出一种边界点扫描的避障策略(BSOA).

假设函数F(θ)的表达式如下:

避障方向分为两种:顺时针避障和逆时针避障.F(〈Vi(t+1)〉-〈Vif(t+1)〉)<0 为顺时针避障,F(〈Vi(t+1)〉-〈Vif(t+1)〉)>0 为逆时针避障,其中Vi(t+1)为考虑避障后速度.

在有障碍物的环境下搜索目标,不需要避障的情形有两种:1)机器人传感器扫描区域内没有探测到障碍物;2)机器人的传感器扫描区域内有障碍物,但期望速度Vif(t+1)方向无障碍物,如图3(a)所示.机器人无需避障时,速度Vi(t+1)=Vif(t+1).

图3 障碍物情况分类Fig.3 Classification of obstacles

需要避障的情形有两种:1)如图3(b)(c),机器人探测到连续障碍物:前者探测的是凸障碍物,后者探测的是非凸障碍物,可将其都简化为探测到连续障碍物的情形;2)如图3(d),机器人探测到不连续障碍物,图中表示机器人探测到三段障碍物,其他不连续障碍物的情形与此类似[25].

探测到障碍物后,为了保证障碍物附近的目标可被探测,避障仅考虑可探测且在目标探测范围内的障碍物.将该范围内障碍物投影到圆弧上,得到图4的障碍物简化图,粗弧线表示障碍物投影,图4(a)中①②及图4(b)中①～⑥均表示边界点.图4(a)表示连续障碍物的情况,图4(b)表示不连续障碍物的情况.

图4 障碍物简化Fig.4 Simplified obstacle

在需要避障的情形下,下一步速度可以表示为

考虑NP为边界点数;SF=0,1,2为避碰标志符号,0,1和2分别表示:上一步无避障、上一步顺时针避障和上一步逆时针避障;Pj(xj,yj)(j=1,2,···,NP),Q1(x1,y1),Q2(x2,y2)分别表示机器人Ri可探测障碍物的边界点、最近点、第二近点;l2为强制避障距离;下面求取角度a:

3.5 群机器人目标搜索步骤

群机器人在未知环境下进行目标搜索时,具体流程如图5所示.

图5 未知环境下多目标搜索流程图Fig.5 Flow chart of multi-target search in unknown environment

表2 边界扫描的避障策略Table 2 Boundary scan obstacle avoidance strategy

4 算法收敛性分析

本文借鉴文献[28]所用收敛性分析方法,为便于讨论,有关内容以定义、定理方式给出.

定义1所有迭代步所成集合为迭代总集,记为Num;漫游的迭代步所成集合为漫游迭代集,记为Numr;协同搜索的迭代步所成集合为协同迭代集,记为Numg;迭代总集Num对应全部机器人搜索路径长度记为Pth,迭代总集Num中机器人Ri对应搜索路径长度记为Pthi.

推论1

定义2对于任意的正数ε都存在t,使得不等式|Xi(t+1)-Xi(t)|<ε成立,则Xi(t)收敛.

漫游搜索过程中,据式(5)、图2,若∃Rdis<2LR,不同机器人之间相互排斥,机器人将均匀分布于搜索区域,探测到目标的信号后进入协同搜索状态.因此漫游搜索对机器人能否搜索到目标无影响,仅影响探测目标信号的速率,从而影响目标的搜索速率.下面讨论协同搜索,即部分的收敛性.

图2 简化虚拟受力模型Fig.2 Simplified virtual force model

推论2存在定值ψ,使得=ψ成立,则Xi(t)收敛.

定义2与推论2在群机器人上的体现为,机器人根据该算法到达某位置后,速度趋近于0,由于机器人在L0范围内即可探测到目标位置,完成搜索任务,因此对于机器人目标搜索只需|ψ-Xi(t)|≤L0.

定理1当参数满足式(25),协同搜索过程收敛.

证将式(11)速度与位置的关系整理得

由式(26)易得

由式(31)可知方程收敛的充要条件为0<‖λ‖<1;联立上式可得收敛区间

式(27)代入式(32),整理可知定理1得证.

证毕.

5 仿真与验证

为分析算法性能,本文在Core i5-8300H、内存为24 GB的硬件环境下,运用MATLAB 2019a进行了若干组仿真实验.将避障方法与搜索算法综合考虑,对6种搜索模式:BT,BE,BA,ST,SE,SA 分别仿真;分析BSOA和TPEPSO与传统方法在综合搜索性能上的提升,每种模式对应的具体方法如表3所示.

表3 搜索模式Table 3 Search mode

根据参考文献[17,26],可假设式(1)所述函数关系表示为式(33),仿真时由式(33)生成数据,并结合式(7)估计G−1(Iij).

式中:m为环境衰减系数,0

仿真比较时,需设置环境、机器人、目标、搜索过程等的参数,本文的参数设置如表4所示.

表4 参数设置Table 4 Parameter setting

5.1 障碍物环境的目标搜索

未知环境下,考虑凸障碍物与非凸障碍物,以N=50为例,演示仿真的目标搜索过程,主要搜索过程如图6所示,图中蓝色圆圈表示漫游搜索的机器人,绿色实心圆圈表示协同搜索并可探测到目标信号的机器人,即A类机器人,蓝色实心圆圈表示协同搜索但仅由通信获取目标信号的机器人,轨迹上的箭头表示运动方向.

图6(a)中t=1,地图、机器人位置和目标位置初始化,所有机器人位于左下角100×100的空间内,所有目标随机分散于地图右上角的800×800的范围内,机器人无法得知目标信号及障碍物位置,图中黑色的不规则形状表示障碍物.

图6 未知环境下多目标搜索过程Fig.6 The process of multi-target search in an unknown environment

图6(b)中t=15,机器人R44探测到目标T8的信号,并通过通信将目标信息广播至其半径Rcm范围内的所有机器人,距R44最近的5个机器人与R44结成子联盟,开始协同搜索T8.如图6(c)所示t=29时,R23与T8之间的距离小于L0,机器人搜索到T8,R23声明T8被其搜索到并停止搜索任务,其他机器人退出子联盟重新进入漫游搜索状态并继续后续的目标搜索.

图6(d)中t=49,机器人R15探测到目标T2的信号,然后与较近的5个机器人组为子联盟,参与搜索T8的R44也在该子联盟中.图6(e)中,t=49～65期间有R6,R9,R15,R24,R35,R37,R44,R45先后参与子联盟,但同一时刻子联盟的机器人总数不超过Gmax.上述8个机器人的轨迹如图所示,协同搜索期间子联盟根据基于目标响应函数的动态分工原则对成员机器人进行动态调整,以适应搜索进程及环境的变化.例如图6(e)中,在R35避开凸障碍物的过程中,由于R24逐渐比R35更接近通信机器人,R35退出子联盟进入漫游搜索状态.搜索过程中,机器人逐渐接近目标,最终在t=65时,R44搜索到T2并声明搜索成功,其他机器人退出子联盟,同时进入漫游搜索状态继续搜索其他目标.

图6(f)中t=65,同样也表示机器人探测到目标并广播目标信号,并与较近的机器人组成子联盟.图6(g)中显示了机器人对目标T7的搜索,在搜索过程中,机器人有效地以较短路径避开了非凸障碍物,具体的避障过程以R5和R50的轨迹所示.

群机器人按照基于目标响应函数的动态分工及本文提出的BSOA,TPEPSO方法对目标进行搜索,最终在t=200时,搜索到所有目标,所有的目标及机器人的位置如图6(h)所示.

分别运用:BT,BE,BA,ST,SE,SA.按照机器人数N=20,40,60,80,100的顺序,在上述环境中分别独立仿真30次.统计每次独立运行完成所有目标搜索的迭代步数,全体机器人的总运动距离--总能耗,求取平均值,对运行结果最大值、最小值、平均值进行比较,得到对比数据如表5.

由表5可知随着参与目标搜索的机器人总数增加,搜索总迭代步数逐渐减小,总能耗逐渐增加:将总迭代步数与总能耗的平均值为纵轴,总机器人数为横轴,对搜索效率及总能耗进行比较,如图7所示.BT分别与BE,BA,ST,SE,SA比较,其搜索效率分别提高5.32%,11.25%,21.30%,26.11%,30.31%,总能耗分别减少4.17%,15.05%,20.47%,23.99%,28.75%.

表5 6种不同搜索模式下的搜索步数及能耗Table 5 Search efficiency and energy consumption of six different search modes

图7 多目标搜索迭代步数和能耗Fig.7 Iterative steps and energy consumption of multi-target search

5.2 仿真结果分析

本文提出了一种边界扫描的避障方法(BSOA)及一种目标位置估计的粒子群算法(TPEPSO),将其与传统的简化虚拟受力的循障策略(SVF)、扩展粒子群算法(EPSO)、自适应机器人蝙蝠算法(ARBA)综合比较,可知BSOA搜索效率提高21.58%、总能耗减少19.11%;TPEPSO相比于EPSO,ARBA搜索效率分别提高5.72%,11.35%,总能耗分别减少4.30%,12.73%,且在机器人总数较少时,仍保持较高搜索效率.

6 结论

本文考虑未知且包含凸障碍物和非凸障碍物的二维环境,进行多目标搜索.优化搜索算法与避障策略,对于搜索算法,考虑群机器人搜索时的目标信号强度与目标位置的数值关系,利用目标信号估计目标位置,并与PSO算法结合,得到目标位置估计的粒子群算法(TPEPSO),该方法在保证不陷入局部最优的前提下,进一步提高目标搜索效率;对于避障方法,将障碍物简化成两类,并以不同的方式趋向某一边界点运动,得到边界扫描的避障策略(BSOA),策略在保证搜索范围的前提下,提高了避障的效率.经仿真验证,文中所提算法的搜索效率及搜索总能耗均优于传统的算法.

所提出的方法旨在提供一种可以广泛运用于未知环境下群机器人对特定目标的搜索方法,例如运用于灾后搜救、雷区探雷、资源探寻等领域.但是标准的二维环境在现实中基本不存在,而且目标可能是动态的,同时在该模型中,多目标搜索的分工是以机器人可根据目标信号区分不同目标为假设,现有传感器中难以广泛地实现该功能,因此今后的工作中可考虑在崎岖路面的三维环境或者三维空间,动态目标的搜索,同时在算法模型上进一步完善.