群体机器人协同控制算法设计

张娜娜，刘婷婷，丁茂臻

（1.郑州西亚斯学院 计算机与软件工程学院，河南郑州，451150；2.河南省智能制造数字孪生工程研究中心，河南郑州，451150；3.河北工业大学，天津，300401）

0 引言

多机器人系统具有搭建和维护成本更低、应用场景更为灵活和参与任务时效性更快等特点，不同的任务环境下的具体表现形式可以是自主水下航行器[1]和无人飞行器[2]等，机器人之间具备相互协调沟通的能力，通过协作提高解决问题的速度和效率，并通过执行任务之间的重叠部分补偿个体故障造成的缺口，从而提高系统的鲁棒性。基于多机器人系统的特点和优势[3]，许多研究机构和国际组织都将其视为安全防卫和灾害响应领域中极具前景的战略之一。捷克科技大学的学者提出可以将其应用于侦测航运中（例如海盗等）的犯罪行为[4]；西班牙政府在 2010-2018 国家航运安全与救援计划中，提出通过飞行器所载摄像头检测、监控航运船只污染行为[5]；英国伦敦大学学院的学者提出应用机器人对街区进行以维护治安和打击犯罪为目的的督查[6]。

多机器人任务分配（Multi-robot Task Allocation,MRTA）及多机器人轨迹规划方法的代表性成果也很多，已实现快速响应动态环境但易陷入局部最优解[7]。Marjorie Darrah 等[8]利用改进遗传算法解决了机器人的任务分配问题。有伟等[9]综合考虑多种约束条件，建立了多目标整数规划的任务协同分配模型，设计了一种免疫粒子群算法，较好地保证了算法的多样性和局部搜索能力，解决了多机器人任务分配问题。多机器人轨迹规划算法主要可以分为两类：确定性搜索算法和随机性搜索算法。Duan Haibin 等[10]利用改进蚁群算法求解航迹。Zhang Chao 等[11]将飞行区域划分为网格，运用蚁群算法求解出从出发点到目标点的较优航线。Fei Su 等[12]建立了基于改进蚁群算法在复杂战场环境中航线求解方法。

现有研究成果评价巡逻策略性能主要是基于由机器人行驶距离和搜救点优先级组成的单目标函数，基于此，针对复杂环境下多机器人巡逻系统中存在的通信受限、信息获取困难、系统能力不足以及能量供应受限等客观事实，利用群体智能技术所具有的去中心化、智能度高、灵活性强的独特优势，解决多机器人巡逻系统中的任务分配和路径规划问题。其次，针对水域污染监测场景中，因监测目标点移动引起的动态问题，提出一个分布式自主巡逻动态协同策略。

1 动态气象威胁并插值增益任务规划空间建模

国内外研究中对地形的表示大多数过于简单，常以忽略高程信息为代价将三维空间投射到平面上，并以二进制表示某区域为可飞或禁飞区，不足以满足在现实世界中的应用。

随着数字地图技术的飞速发展，高分辨率数字地形在军事和民用领域的广泛应用为无人机航线规划提供了更广阔的应用空间，其中由美国国防部和航空航天署主持的 SRTM（Shuttle Radar Topography Mission，航天飞机雷达地形测量）计划为代表。

利用 SRTM 真实数据选取大小的真实数据，并对该数据间隔0.50 ×0.50 取样，获得取样地形，真实地形和取样地形如图1 所示。由于雷达回波质量的问题，SRTM-3 数据存在少量的空缺点和空白区，主要集中在水域和起伏较大的高山、峡谷等，其表现为高程值等于-32768。因此在数字地形构建前应对其空缺点填补，本研究采用内插的空缺点填补，用内插的方法对空洞点进行填充。

图1 真实地形和取样地形图

我国境内的分辨率均为 90 米的地形数据，其精度无法满足无人机对规划空间的要求。因此采用三种插值方法对地形数据进行插值处理，其中三次 Spline 插值方法相比最近邻插值和双线性插值方法而言，插值精度更高，且在插值点连续二次可导，但也存在计算量大，耗时较长等不足。考虑到地形数据复杂、无人机飞行能力受限等因素，经插值后的地形可能存在坡度较大的区域，为无人机安全飞行埋下隐患，还需对地形的坡度及曲率进行进一步的平滑。

以DEM 数字地图为基础，利用三次Spline 曲线插值算法提高地形的分辨率，构建更为准确、真实的数字地形环境，为后续的任务分配、航线规划提供更为客观的研究基础；选取影响气象威胁度的相关因子，针对各种气象威胁要素构建量化等级，利用专家知识确立相应的条件概率表及转移概率表，选择前向后向推理算法推理出随时间动态变化的气象威胁等级，利用基于离散模糊的动态贝叶斯网络建立动态气象模型。气象威胁评估模型如图2 所示。图中TL 表示威胁等级(Threat Level，TL)，WT 表示气象类型(Weather Type，WT)，IOE 表示威胁作用强度(Intensity of Effect，IOE)，DC 表示相对位置(Distance from Circle，DC)，FT表示飞行动作(Fly Type，FT)。

图2 气象威胁评估模型

2 基于群体智能优化的多机器人任务分配算法设计

在自然灾害搜救场景中，精确的数学模型和完备的约束条件往往是很难得到的，用参数假设的条件与实际问题会存在偏颇，使得根据这样的数学模型求解的结果不一定能很好地应用于实际。基于上述原因，多机器人任务分配问题求取多个近似的最优解，以供决策者根据当环境和实际需求进行选择和切换。上述求取多个近似最优解的问题归属为多峰优化的范畴。在求解此类问题时，传统的启发式算法由于只能收敛到唯一的全局最优解，无法被直接应用于多峰优化问题。文献[13～16]显示，凤仙花优化算法作为新型群体智能算法，在全局探索与局部开发能力之间有较好的调整机制。

首先，凤仙花优化算法弹射距离算子的改进。基础凤仙花算法中，机械传播算子较为重要，是算法成功的关键因素。种子扩散的示意图如图3 所示。种子扩散范围的计算表达式中，对于种群在迭代过程中每代的最优个体f( XB)=fmin，这时最优个体的传播距离，对于同一个优化问题，当itermax、n和Ainit取定值的情况下，算法每次独立运行过程中，BA只与迭代次数iter有关，即每次独立运行BA的取值序列都是一致的。这也就意味着，对于同一个优化问题，每次独立运行凤仙花优化算法时，迭代次数相同，最优个体的传播距离是一样的。从中可以发现，在优化过程中，最优个体的搜索行为适应性太差。

图3 种子扩散示意图

针对凤仙花算法中最优个体传播距离计算缺陷，提出一个梯度估计最优个体传播距离的方法，核心思想是利用当代种子传播信息，计算下一代最优个体的传播距离。

其次，引入Softmax 回归模型。通过Softmax 回归模型对迭代过程中新产生的种子进行预判，淘汰初选效果不好的种子，减少进入适应度评价环节的种子个数，从而在目标函数计算过程较为耗时的应用环境中降低计算时间和计算量，提高计算效率。

此外，受基因突变理论启发，计划设计一个引导二次传播算子。当某个环境维度发生变异时，与其在同一环境维度其他种子有更高的概率发生变异，进一步提高算法的搜索能力。

通过实验对所提算法的多峰优化能力进行验证，并将其与其他经典多峰优化算法在标准测试函数上的优化性能进行比较，最后将所提算法应用到两个MUTA 仿真案例上，分别验证引导二次传播算子在搜索能力上的提升和所提算法在降低计算复杂度上的成效。

3 用于多机器人巡逻路径规划的多目标凤仙花优化算法设计

目前现有的研究成果评价巡逻策略性能主要是基于由机器人行驶距离和搜救点优先级组成的单目标函数，基于此，提出解决多目标问题。第一点与已有研究成果相同是最小化航行路径长度以节省机器人能量消耗。为了实现这一点，最简单的方式是使一个机器人根据最优路径进行搜救。但在危险场景中，时效性对于待援人员的生命安全尤为重要，故第二点须考虑最小化一轮搜救所花费的时间。第三点，距离危险点越近的人员需越早获救以确保其安全。综上所述，研究重点是由这三个需要同时被满足又互相矛盾的目标所构成的多目标问题。

在早期多种群多目标优算法中，通常会针对每个优化目标分别生成一个种群，并行但独立搜索，将各自搜索到的最优解保存到一个公共的非支配解集合中，并引入非支配解集合的更新机制，算法结束，得到多目标优化问题的Pareto前端。这种利用多种群解决多目标优化问题的方法存在一个缺陷，即缺乏种群搜索过程中信息的共享机制，不利于算法的快速收敛。在MPMO 框架基础之上，协同多目标凤仙花算法（CMGBO）引入多种群协同进化机制，每次迭代过程中利用公共非支配解集指导各个种群进化，每个种群都可以在档案中其他种群的搜索信息的指引下沿PF 进行搜索。CMGBO 的框架如图4 所示，其中Subpop 和obj 分别代表种群和优化目标。

图4 CMGBO 框架图

协同进化机制：m 子种群中第i 个解Xm,i，对应种子的机械传播过程如下：

其中，Am,r(iter)是从存档A 中随机选择的非支解；P(Am,r(iter) -X m,i(iter))表示从多目标非支配解档案A 到解决方案Xm,i的信息共享。通过实验对所提CMGBO 算法的PF 前端搜索能力进行验证，并将其与其他经典多目标优化算法在标准测试函数上的优化性能进行比较，最后将所提算法通过仿真，验证CMGBO 算法在降低计算复杂度上的成效。

4 基于事件驱动控制的动态协同策略设计

在机器人选择监测目标时，通过对访问频率和能量损耗的综合考虑，建立一种双向评价机制，同时提出一种潜在工作负载系数，避免隐形监测队列的堆积。接下来，通过对机器人定位监测目标过程中运动模式的分析，定义一系列事件类型和协同动作，采用合理的目标转移和机器人释放等方式，提高移动搜救目标的访问频率和机器人的工作效率。

机器人根据定义的前向效用方程在可供选择的目标里选择最适合的目标，从该目标的角度根据定义的后向效用方程判断该机器人是否同样是最适合对其执行搜救任务的机器人。当这样的双向选择达成一致时，机器人即可确定搜救目标。根据多机器人在向目标移动过程中的运动模式分析，归纳得到不同的事件类型。当这些事件其中之一发生时，相关的两个机器人之间通过即时通信确定协同模式。通过与其他三种前沿算法的比较，验证所提的策略在降低目标每两次被访问之间时间间隔的优势，同时，通过在仿真环境的应用和分析，进一步说明在此类环境中的应用前景。

5 总结

针对水域污染监测场景中，因监测目标点移动引起的动态问题，在复杂环境下多机器人巡逻系统中存在的通信受限、信息获取困难、系统能力不足以及能量供应受限等客观事实，利用群体智能技术所具有的去中心化、智能度高、灵活性强的独特优势，提出一个分布式自主巡逻动态协同策略，解决多机器人巡逻系统中的任务分配和路径规划问题。此外，群体机器人协同在各种场景中都有潜在的应用，如农业、物流、医疗和救援等，总之，多机器人巡逻系统中的任务分配和路径规划问题的设计，具备较高的实用价值和社会价值。