何凯迪

四川大学电子信息学院 四川 成都 610065

引言

智能体集群有着广泛的运用，如测绘、监视或周边巡逻[1-4]。在目标搜索领域中，启发式搜索算法有着广泛的运用。其中比较广泛的运用就是以Voronoi图划分为基础的搜索算法。

1 问题背景和建模

本文针对静态目标搜索领域。目标是多个不可移动的目标。

地图使用建立在离散地图上的概率图建模，地图被离散栅格化。每个栅格区域对应一块地图，对于每个栅格区域建立了一个数字，例如概率值，用来辅助搜索的进行。

高概率区域，用来指引无人机优先搜索，低概率区域指引无人机低优先级搜索。

对于无人机，没有移动模型限制，无人机可以移动到地图任意位置，不局限于栅格中心。

每次探测区域是否会被探测，取决于栅格中心是否位于智能体探测范围内。

对于离散地图，可以使用矩阵存储。

2 双种群算法

双种群算法主要包含了两个种群。

第一种群，仍然以Voronoi图划分为基础进行区域搜索。

即，进行Voronoi图划分后，质心计算公式使用：

在通过Voronoi图划分之后，计算每个Voronoi图区域的质心，作为无人机的引导位置。

第一种群搜索完毕之后，进行地图更新。地图更新主要使用贝叶斯更新公式为基础的延伸公式：

其中Pi,j,k是区域j在第k次迭代时的第i个智能体搜索结果的概率，Di,j,k代表着第k次迭代时的对该区域的探测结果，Di,j,k=1表示探测到了目标，Di,j,k=0表示没有探测到目标。

此外，p是探测概率，是智能体携带传感器精度决定。q是误报的概率，表示识别错误，也是由智能体携带传感器决定。……