基于规则的无人机集群区域协同搜索算法

区域搜索是无人机集群非常重要的一个应用方向，而科学合理的控制算法是提高集群执行任务效率的最有效途径。现有的规划控制算法存在非自主、规模小、计算复杂等不足之处，本文针对大规模无人机集群对不确定区域执行搜索任务，基于Boids动力学模型提出了一种基于规则的区域协同搜索算法，该算法具有自主性好、鲁棒、计算简单以及在理论上能以概率1实现搜索区域全覆盖等优点，并且通过仿真验证了该算法的有效性。

相对有人机，无人机具有无人员伤亡、成本低、适应复杂环境作业等诸多优越性能，更适合执行4D (Dull, Dirty, Dangerous and Deep)任务[1]，而相对于单个无人机，多无人机集群则更加灵活，容错性也更好，能满足多种任务的需要，其中区域协同搜索是其中一种重要的任务类型，比如人员搜救、情报侦察和森林救火等。该类型的任务主要有两个方面研究侧重：一是以较小的搜索代价对特定区域内可能存在的目标进行搜索；二是合理地控制多个无人机，使得区域搜索覆盖率最大，本文的研究属于第二种。

由于无人机集群具有非常广泛的应用前景，区域搜索问题也引起了许多学者的关注。文献[2]对多UAV 协同区域覆盖进行了研究，将求解问题分为任务区域分配和完全覆盖路径规划两个子问题，给出了在特定多边形区域下，最小代价的搜索模式和搜索路径；文献[3]提出了一种基于模型预测控制理论和遗传算法的多UAV 协同搜索算法，旨在降低环境的不确定度；文献[4]针对降低环境不确定度的问题，基于搜索概率图，提出了一种协同进化算法，对多UAV 协同搜索路径进行规划；文献[5]提出了一种分布式概率图更新模型和多主体协同控制方法，能够对多个移动地面目标进行有效地协作搜索；文献[6]在UAV 动力约束的基础上，针对常用搜索样式“Z”字形和内螺旋的缺陷，对常用的区域搜索算法进行了改进；文献[7]提出了一种基于预测控制思想的多无人机协同区域搜索算法，研究各种通信约束对多无人机协同区域搜索效能的影响。但是这些研究可能存在以下局限：1) 无人机数量较少，对每一架无人机， 都使用设计的代价函数进行路径规划。当无人机增多时，可能会使得计算量非常大。2) 将搜索区域离散化，无人机的运动是从一个网格跳跃到另一个网格，覆盖率的计算也是基于网格的，可能与实际情况不符。3) 搜索区域较小，比如文献[4]和[7]仿真采用的网格分别为30 30×和40 40×，当搜索区域增大，其算法的计算量和有效性可能并不一定很好。4) 部分算法要求无人机具有额外的储存能力。比如文献[7]对搜索区域建立了搜索概率图，这增加了每一架无人机额外的硬件负担，并且概率图的时刻更新也加大了无人机之间的通信负载。

针对现有算法存在的以上不足，本文做了一些探索，提出了一种基于局部规则的集群区域协同搜索算法。该算法借鉴了自然界自组织生物群体的运动规则，设计了离心、无序、分离、惯性和随机等六个规则及相应的搜索算法，使无人机能够迅速有效地扩散到目标搜索区域，并且对于搜索过的区域，未来某个时刻可进行重复搜索。该算法在理论上能以概率1 对目标区域实现全覆盖，并且具有计算简单、鲁棒等特点，适用于环境规划复杂、无人机数量规模大、搜索区域宽广的任务场景。本文通过仿真对提出的算法的有效性进行了验证。

2. 集群协同搜索问题建模 2.1. 问题描述 假设存在一块ll× 的矩形目标区域， 区域中可能存在火灾点或者受难人员， 但其具体位置信息未知。