群机器人任务分工与协同搜索方法

刘 倩，陈嶷瑛，冯艳红

(河北地质大学 信息工程学院，河北 石家庄 050031)

0 引 言

就目前的机器人发展水平而言，单个机器人的探测能力和运动能力非常有限，在复杂环境下执行搜索等复杂任务存在很多不足。以机器人组群的方式，通过互相通信提高探测和整体运动能力[1]，对于目标搜索和人员搜救意义重大。

群机器人执行搜索任务时，关键技术包括任务分工、避障规划、相互协同方法等。自组织任务分工的常用方法有交换树法、响应阈值法、情感招募法等，文献[2]提出了交换树竞拍法，解决了带任务偏序的负载平衡问题；文献[3]提出了带闭环调节的任务动态分工方法，提高了机器人搜索效率；文献[4]将情感招募法与拍卖法结合，实现了完成全部任务最短和收益最高。避障规划与相互协同需同时考虑，在协同搜索的同时，既要避开障碍物又要避开机器人，互相协同方法一般使用群体智能算法，包括菌群算法[5]、微粒群优化算法[6]等，以上方法都实现了自身设定条件下的优化与搜索效率提高。

本文研究了群机器人执行搜索任务时的任务分工与目标搜索问题。在任务分工方面，为了实现任务分工均衡，提出了预分工与反馈调节的双层分工方法。在目标搜索方法，模拟鸟群觅食过程，使用粒子群算法更新机器人速度与位置，并建立了势场力模型用于实现避障，最终实现了在工作区域的多目标快速锁定。

1 自组织任务分工

在群机器人系统中，单个机器人具有一定的探测能力和运动能力，且在一定范围内的机器人可以互相通信，本节研究群机器人系统的任务分工方法。为了实现分工的均衡，提出了预分工与反酷调节的双层分工方法。

1.1 单机器人目标获取

单机器人通过自身携带传感器探测周身一定范围内的障碍物信息和目标信息。在机器人探测范围内，当机器人与目标距离不同时，机器人探测到的目标信号强度也不同，本文使用目标强度函数[7]进行描述，定义为

(1)

式中：Iij为机器人Ri探测到目标点Tj的强度，为两者距离d的函数；dT为距离阈值，在dT范围内可以探测到目标信号；Q0为目标发出的功率；m∈(0,1) 为信号传递时功率衰减系数。

单机器人获取目标的方式除自身探测外，还可以通过互相通信获得，规定机器人通过自身传感器探测到的目标为A类目标，以通信方式获得的目标为B类目标。

1.2 单机器人确定意向目标

机器人探测过程中可能获得多个目标信息，包括A类和B类两种，机器人要从目标集合中确定一个意向目标。依据信号强度Iij建立目标选择概率函数，为

(2)

式中：Pij为机器人Ri选择目标点Tj的概率，Gaini表示机器人Ri获取的目标集合，以目标强度的开平方构造选择概率，是为了使选择概率与距离dij成比例关系。

机器人确定意向目标时，目标类型不同则优先级也不同。如果目标集合中包含A类目标，则机器人只考虑A类目标作为意向目标；仅当目标集合中不包含A类目标时，机器人才考虑B类目标作为意向目标。按照目标优先级，预选定的目标可能有多个，此时按照式(2)计算各目标的选择概率，然后按照轮盘赌的方法确定一个目标作为意向目标。

1.3 子群形成与反馈调整

单机器人确定意向目标后，向通信范围内的机器人发布信息，具有相同意向目标的机器人组成一个子群，同时子群中目标强度信号最强者为此子群的Leader，子群Lea-der 为子群代言人，对外发布子群信息，包括子群编号、子群规模、成员编号、目标信息等。

通过以上方法，初步形成了若干子群，没有编入子群的机器人继续漫游行走探测目标。但是这种方法极易出现某些子群过大、某些目标无人搜索的情况，即机器人资源分配不平衡、不合理。为了解决这一问题，本文提出了反馈调节机制，达到机器人资源配置“削多补少”的效果。搜索同一目标点的机器人不能太少，否则搜索效率较低，甚至丢失目标；同时搜索同一目标点的机器人数也不易过大，不仅会造成资源浪费，靠近目标点时也会异常拥挤。基于以上考虑，将搜索同一目标点的机器人数上限设置为6。当子群规模小于6时，子群Leader会对外发布招募信息；当子群规模大于6时，对子群内机器人进行排序，只保留前6名，其余机器人被踢出子群转为漫游搜索状态。

对于同一子群的机器人，排序方法为：按照机器人获得目标的方式和信号强度进行排序，具体地讲，意向目标为A类目标的机器人排在B类目标机器人之前，意向目标同为A类或B类时，按照目标强度进行排序，保留排名靠前的6个机器人形成子群，其余被踢出。这种以反馈方式调节子群的方法，能够保留离目标较近的机器人，而离目标相对较远的机器人被排除在子群之外，去搜索其它目标点，保证了机器人资源的合理配置与任务平衡，提高了综合搜索效率。

2 机器人协同控制

2.1 机器人状态划分

机器人在获取目标之前，以漫游搜索方式在工作区域中探测目标，通过探测或通信获取目标后按照组群方式加入子群；加入子群的机器人由漫游搜索状态转为协同搜索状态，未加入子群的机器人继续漫游搜索状态；当机器人与目标距离小于某一阈值时，认为发现目标，并向外发布目标信息，机器人转为目标声明状态，对目标位置标记后，机器人自动解散转为漫游搜索状态，继续搜索其它目标。具体转换方法如图1所示。

图1 机器人状态划分方法

机器人漫游搜索时，以在最短时间内覆盖最大面积为目的，因此本文使用直线漫游搜索方式，漫游速度为机器人最大速度Vmax，搜索方向按照相邻机器人搜索方向不同且保证最大搜索面原则确定。下面重点设计机器人协同搜索状态下运动方式和避障方法。

2.2 模拟鸟群觅食的搜索方法

子群内机器人作为一个团队搜索目标，与鸟群搜索食物过程极为相似，基于这种类比，本文提出了带惯性权重粒子群算法[8]的机器人协同搜索方法。机器人速度及位置更新方法为

(3)

位置的优劣依据目标信号强度进行评判，分析式(3)可知，机器人在自身历史最优位置、子群最优位置和惯性影响下，进行速度和位置更新，不断向目标靠近而最终锁定目标。

2.3 基于势场力的避障方法

在人工势场算法中，依赖障碍物斥力与目标点引力使机器人避开障碍物而趋向目标点[9]，参考这一思想，设计群机器人运动过程中的避障方法。机器人运动过程中，障碍物的斥力大小定义为

(4)

式中：fre(d) 表示障碍物斥力大小，为距离d的函数；lT为距离阈值，当机器人与障碍物距离d小于lT时存在斥力作用，当d大于lT时不存在斥力作用；c为一个常数；lm为避撞加强的距离，m取值不同时代表不同障碍物，m=1表示障碍物为其它机器人，m=2表示静态障碍物。

图2 势场力模型

(5)

2.4 搜索与避障的协同控制方法

机器人在行走过程中，既要搜索目标又要考虑避障，因此机器人的运动受“目标搜索”和“避障”双层因素的影响。机器人协同控制方法按照机器人状态分以下两种情况讨论：

情况一：机器人处于漫游状态

(1)当机器人处于漫游状态，且d>lT，即无需避障时，机器人速度和位置更新方法为

(6)

(2)当器人处于漫游状态，且d≤lT，即需要避障时，机器人速度和位置更新方法为

(7)

情况二：机器人处于协同搜索状态

(1)当机器人处于协同搜索状态，且d>lT，即无需避障时，机器人速度和位置更新方法为

(8)

(2)当机器人处于协同搜索状态，且d≤lT，即需要避障时，机器人速度和位置更新方法为

(9)

3 仿真验证

3.1 仿真环境及参数设置

为了对本文设计的群机器人任务分工与协同搜索方法进行验证，仿真出1000m×1000m的搜素区域，在此区域中放置6个目标与30个机器人，机器人最大速度设置为5 m/s，最大感应半径100 m，最大通信半径300 m，目标发出的功率Q0=103，目标信号功率衰减系数m=0.1，惯性系数α=0.1、λ=0.4、ω=0.4，目标到达阈值为5 m。

在搜索区域中，障碍物与目标分布情况如图3所示，图中带有标号的实心心型表示目标点，标号为目标点编号；黑色实线表示障碍物；带有方向的空心圆表示机器人，初始时刻30个机器人全部投置于搜索区域左下角。

3.2 搜索结果分析

使用本文设计的任务分工与协同搜索算法搜索区域内目标，为了形成对比，同时使用文献[10]给出的搜索方法进行搜索，两种方法各运行50次。随机选取使用本文方法的一个搜索过程进行分析，结果如图4所示。

图3 搜索区域

图4 搜索过程

图4(a)与图4(b)展示了子群1形成后搜索目标1的过程。在T=75s时，搜索目标1的子群1形成，子群规模为6，参加子群1的机器人编号为22、27、14、6、28、1。加入子群1的机器人由漫游搜索状态转为协同搜索状态，其余机器人继续进行漫游搜索。在T=115s，子群1成功锁定目标1，由子群Leader对外发布目标信息，并对目标位置进行标记，之后子群1成员解散，由协同搜索状态转为漫游搜索状态，目标1搜索结束。

图4(c)展示了子群3形成后成功避障并锁定目标3的过程。在T=115s时子群3形成，在T=146s时子群3成功锁定目标3，图4(c)中给出了子群内机器人从结盟到锁定目标过程的运动轨迹，由运动轨迹可以看出，子群内机器人成功完成了避障和目标锁定。目标锁定后，子群3解散，机器人转入漫游搜索状态，继续搜索其它目标。

图4(d)给出了子群6从结盟到锁定目标6的轨迹，参加子群6的机器人包括27、6、10、23、17、17。从子群6各机器人的运动轨迹可以看出，子群6不仅成功实现了避障，而且成功锁定目标6，直至此时所有目标搜索完毕，搜索过程结束。

在相同环境下、相同机器人规模和相同目标数量下，使用文献[10]给出的方法进行目标搜索，本文算法与文献[10]算法各运行50次。经验证，50次搜索中本文算法与文献[10]算法都能够锁定所有目标，未出现遗失目标的情况，统计50次算法耗时的均值、方差、最大值与最小值，结果见表1。

表1 算法耗时

由表1可以看出，在1000m×1000m仿真环境中设置6个目标与30个机器人的情况下，本文算法搜索所有目标平均耗时为435.722 s，比文献[10]算法减少了17.14%；本文算法最优耗时为411 s，比文献[10]算法减少了18.61%，且本文算法耗时方差小于文献[10]算法，说明本文算法不仅耗时少，而且性能稳定。这是因为在任务分工阶段，子群形成过程与反馈调节过程中，文献[10]以信号强度为依据进行排序，确定最终组成子群的个体；本文不仅考虑了信号强度，而且考虑了目标获取方式的区别，将A类目标排列在B类目标之前，这种排序方法使得距离目标最近的个体能够被保留，更加符合实际情况，从而提高了搜索效率。

4 结束语

本文研究了群机器人执行搜索任务时的任务分工与目标搜索问题。在任务分工方面，以目标信号强度为依据，建立了目标选择概率函数，依据概率函数使用轮盘赌的方法确定机器人的意向目标，具有相同意向目标的机器人初步形成一个子群，而后使用反馈调节的方法调整子群组成。在目标搜索方法，模拟鸟群觅食过程搜索目标，使用势力实现避障，建立了边搜索边避障的协同控制方法。经仿真验证，本文算法能够成功锁定区域内的所有目标，且算法耗时优势明显。