(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111229814.9 (22)申请日 2021.10.2 2 (71)申请人 北京理工大 学 地址 100081 北京市海淀区中关村南大街5 号 (72)发明人 彭志红　焦蕾　陈杰　奚乐乐　 陈梓豪　 (74)专利代理 机构 北京理工大 学专利中心 11120 代理人 袁瑞霞 (51)Int.Cl. G06F 30/27(2020.01) G06K 9/62(2022.01) G06N 3/12(2006.01) G06N 3/00(2006.01) (54)发明名称 一种基于自适应分区的多智能体异构目标 协同覆盖方法 (57)摘要 本发明提出了一种基于自适应分区的多智 能体异构目标协同覆盖方法， 能够实现在资源受 限条件下的多智能体多目标点覆盖， 并且可以权 衡各智能体的时间损耗。 本发明提出了基于反馈 控制机制的改进 k‑means聚类算法对目标点进行 分区， 自适应调节目标点分区结果， 从而进一步 权衡各智能体执行任务的时间损耗。 在优化各智 能体对所分得目标点的遍历顺序阶段， 基于考虑 资源不足条件 下的多智能体多目标点覆盖问题， 对遗传算法进行了改进， 从而实现了在有限时间 内尽可能最大化探测收益。 考虑到各智能体运动 时间受限， 设计了启发式修复规则路径修复方 法， 从而确保各智能体在预设时间范围内返回基 站。 权利要求书2页 说明书10页 附图8页 CN 114169216 A 2022.03.11 CN 114169216 A 1.一种基于自适应分区的多智能体异构目标协同覆盖方法， 其特征在于， 包括如下步 骤： 第一步， 面向探测权重值和覆盖时间异构的多智能体异构 目标， 建立通过对各智能体 的目标点分配方案和目标点遍历顺序进行优化以最大化探测收益的优化问题模型； 输入问 题参数和遗传算法参数到模型中； 第二步， 基于目标的角密度采用k ‑means聚类算法输出各 聚类中心的角度值， 完成对目 标的分区； 其中， 目标节点i的角密度大小为 其中θi和 θj分别表示目 标节点i和目标节 点j和基站连线与水平线所成角， Δθ为设定的角度阈值， I表 示计数函数； i＝1,2,3…m， j＝1,2,3 …m， m为目标点， 总数i≠j； 第三步， 基于改进遗传算法对各分区中的目标点遍历顺序进行优化， 得到各分区中目 标点的最优遍历顺序； 所述改进遗传算法包括如下步骤： 步骤1： 采用混合启发式规则和基于克 里斯托菲德斯启发式算法， 初始化种群； 步骤2： 采用结合粒子群算法的全局引导思想的个 体交叉方式进行交叉操作； 步骤3： 变异操作； 步骤4： 计算种群中个 体的适应度值； 步骤5： 采用精英策略对种群进行更新， 具体为： 对所有个体基于目标函数值进行从大 到小排序， 选取 前Np个优良个 体进入下一次迭代， 其中Np为设定值； 步骤6： 判断是否 达到改进遗传算法结束条件， 若是， 则继续 步骤7， 若否， 则返回步骤2； 步骤7： 输出分区中目标点的最优遍历顺序； 第四步， 计算各智能体任务执行时间与所有智能体任务执行时间均值的差值， 对于差 值不为0的分区， 根据差值对其所对应的反馈参数进行调整； 第五步， 判断当前差值是否满足设定的结束条件， 若否， 则依照调整后的反馈参数返回 第二步， 对目标点进行重新聚类； 若是， 则继续第六步； 第六步， 将得到最优遍历顺序下不满足时间约束的目标点删除， 对最优遍历顺序进行 修复； 第七步， 输出修复后的各智能体目标点遍历顺序。 2.如权利要求1所述的方法， 其特征在于， 所述第二步中， 所述k ‑means聚类算法中， 初 始化中心点获取方法为： 选取角密度值最大 的目标所在角度为中心点， 而后将所选目标点 及其角度邻域内的所有点去除， 计算剩余 目标点的角密度， 再次选取角密度值最大 的目标 所在角度为中心点， 重复此 过程， 直到中心点的数量与智能体数量相同； 聚类中心线 的调整方法为： 首先依照 式(1.12)得到距离各目标点最近的中心线编号； 然后， 依照式(1.13)计算从属 于各类的目标点角度均值， 并更新聚类中心线的角度； 最后， 依照式(1.14)计算更新前后中心线的变化量， 若两次变化值小于预定阈值Δangle则结束循 环， 输出各聚类中心的角度值， 其中： 权　利　要　求　书 1/2 页 2 CN 114169216 A 2式(1.12)中， σi表示目标点i与基站连线和水平线所成角度值， μj表示中心线j的角度； 式(1.13)中， μ'j表示更新后中心线j的角度； 式(1.14)中， K表示聚类中心的数量。 3.如权利要求1或2所述的方法， 其特征在于， 所述第 三步中， 所述改进遗传算法的步骤 2的具体实现方式为： 首先构建全局边关系表， 表中统计了现有种群中各目标点下一位置连接不同类型目标 点的百分比； 然后对符合要求的个体进 行交叉， 在父代个体上随机选取染色体段， 并基于边 关系表对父代染色体进行变换， 将所生成的子染色体存 储在种群中。 4.如权利要求3所述的方法， 其特征在于， 所述交叉操作包括四种交叉方式， 具体过程 如下： cross‑I操作： 结合剩余基因和全局边关系表， 对gs中的基因进行替换； cross‑II操作： 保留 gs中的基因顺序不变， 结合全局边关系表， 对剩余基因进行替换； cross‑III操作： 保留gs中的基因顺序不变， 并作为子代初始基因段， 后续基因结合全 局边关系表 依次生成； cross‑IV操作： 保留gs中的基因顺序 不变， 并作为子代末端基因段， 其余基因结合全局 边关系表 依次生成。 5.如权利要求1、 2或4所述的方法， 其特征在于， 所述第三步中， 所述改进遗传算法的所 述步骤3中， 采用基因点交换的方式对 满足条件的个 体进行变异操作。 6.如权利要求1、 2或4所述的方法， 其特征在于， 利用启发式规则路径修复方法对不满 足时间约束的目标遍历顺序进行修复。 7.如权利要求6所述的方法， 其特征在于， 所述启发式规则包括基于时间权重比的启发 式修复规则和基于距离贪婪的启发式修复规则。权　利　要　求　书 2/2 页 3 CN 114169216 A 3