(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111601710.6 (22)申请日 2021.12.24 (71)申请人 北京理工大 学重庆创新中心 地址 401120 重庆市渝北区龙兴镇曙光路9 号9幢 (72)发明人 雍鹏程　沈智勇　陈伟　俞成浦　 (74)专利代理 机构 成都九鼎天元知识产权代理 有限公司 51214 代理人 王会改 (51)Int.Cl. G06V 20/10(2022.01) G06Q 10/06(2012.01) G06Q 10/10(2012.01) (54)发明名称 一种多无人机巡线的网络图划分方法及系 统 (57)摘要 本发明公开了一种多无人机巡线的网络图 划分方法及系统， 所述方法包括： 生成无人机巡 视的任务网络图； 通过第一算法对 所述任务网络 图进行划分， 得到第一划分集合； 通过第二算法 对所述第一划分集合进行筛选， 得到可行解集； 对所述可行解集进行计算， 得到所述无人机巡线 的网络图划分方案。 本发明采用基本割集原理进 行网络图的划分， 实用性强， 生成的划分方案质 量高。 权利要求书2页 说明书5页 附图4页 CN 114266976 A 2022.04.01 CN 114266976 A 1.一种多无 人机巡线的网络图划分方法， 其特 征在于， 包括： 生成无人机巡视的任务网络图； 通过第一 算法对所述任务网络图进行划分， 得到第一划分集 合； 通过第二 算法对所述第一划分集 合进行筛 选， 得到可 行解集； 对所述可 行解集进行计算， 得到所述无 人机巡线的网络图划分方案 。 2.根据权利要求1所述的方法， 其特 征在于， 所述 生成无人机巡视的任务网络图， 包括： 假定连通图G＝<V,E,W>为p(p≥2)架无人机巡视的任务 网络图,设v0,v1,…,vm∈V表示 点集， e0,e1,…,en∈E表示边集， w0,w1,…,wn∈W表示边的权集， 其中， wi是边ei的权重， 权重 可表达航行参数。 3.根据权利要求2所述的方法， 其特 征在于， 所述 航行参数包括 航行距离和航行收益。 4.根据权利要求2所述的方法， 其特征在于， 将所述任务网络 图划分为p个子 图作为所 述无人机的任务区域， 使得每架无人机的目标值尽可能均衡； 假设所述无人机的单架 次能 力均满足子区域任务 量， 航行轨 迹为一条欧拉回路， 以航行距离均衡为目标。 5.根据权利要求1所述的方法， 其特征在于， 所述通过第 一算法对所述任务网络图进行 划分， 得到第一划分集 合， 包括： S51:得到任务网络图G的一个生成树T； S52:生成‘2‑划分’集合D＝<d1,d2,...>； S53:遍历树T的所有树枝， a'j和a″j分别表示 树枝Sj的两个端点； S54:得到T ‑Sj中与点a'j连通的点 集V′j， T‑Sj中与点a″j连通的点 集V″j； S55:将G划分为3个图， 子图1记G'j＝<V′j,E'j,W′j>， 子图2记G ″j＝<V″j,E″j,W″j>， 割图 记G″′j＝<V″′j,E″′j,W″′j>， 满足V＝V ′j∪V″j， E＝E′j∪E″j∪E″′j， 进一步 S56:将E″ ′j中的边随机均分给E'j和E″j， 得到dj＝<G'j,G″j>， 即得到所述第一划分集 合。 6.根据权利要求5所述的方法， 其特征在于， 所述通过第 二算法对所述第 一划分集合进 行筛选， 得到可 行解集， 包括以下步骤： S61:设置均衡阈值α， 无 人机数量p(p≥2)； S62:遍历 D中的划分方案dj； S63:分别求dj中子图的欧拉图， 并计算欧拉子图的边权 重和， 记dwj＝<gw'j,gw″j>； S64:保留满足(1 ‑α )·p‑1≤gw'j·(gw'j+gw″j)‑1≤(1+α )·p‑1的方案； S65:若p‑1＝1， 则输出步骤S64保留的方案， 然后进入所述步骤S62中的下一组dj； 否则 调用第一算法对G ″j进行划分得到第二划分集合并遍历， 并转至所述步骤S63； 其中， 记 gp表示第p架无 人机所划分的图结构； S66:记录筛选出来的可 行解， 记 得到所述可 行解集。 7.根据权利要求5或6所述的方法， 其特征在于， 所述第一划分集合为所述任务网络 图 的一棵树下的2 ‑划分集合。 8.根据权利要求1所述的方法， 其特征在于， 所述对所述可行解集进行计算， 得到所述 无人机巡线的网络图划分方案， 包括：权　利　要　求　书 1/2 页 2 CN 114266976 A 2计算所述可行解集中的每个可行解的目标值的方差， 取方差 中的最小方差所对应的可 行解作为较优解输出， 所述较优解即为所述无 人机巡线的网络图划分方案 。 9.一种多无 人机巡线的网络图划分系统， 其特 征在于， 包括： 生成模块， 用于生成无 人机巡视的任务网络图； 第一计算模块， 用于通过第一 算法对所述任务网络图进行划分， 得到第一划分集 合； 第二计算模块， 用于通过第二 算法对所述第一划分集 合进行筛 选， 得到可 行解集； 第三计算模块， 用于对所述可行解集进行计算， 得到所述无人机巡线的网络 图划分方 案。权　利　要　求　书 2/2 页 3 CN 114266976 A 3