(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211068435.0 (22)申请日 2022.09.02 (71)申请人 广东翼景信息科技有限公司 地址 510000 广东省广州市黄埔区开源大 道11号B9栋301 (72)发明人 万施霖　陈湸湸　张裕汉　金鑫　 (74)专利代理 机构 广东省中源正拓专利代理事 务所(普通 合伙) 44748 专利代理师 朱靖华 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) G06N 3/00(2006.01) G06Q 10/04(2012.01) G01C 21/20(2006.01) (54)发明名称 一种支持边缘计算的多无人机任务分配与 路径规划方法 (57)摘要 本发明涉及无人机技术领域， 具体为一种支 持边缘计算的多无人机任务分配与路径规划方 法， 通过智能机场进行充电或更换电池的多无人 机对多个任务点进行辅助边缘计算的场景下， 进 行整数型优化变量和连续实数型优化变量联合 优化； 利用混合整数非线性规划， 在给定每架无 人机每次的服务任务集情况下， 采用粒子群算法 求解无人机的最优任务分配与路径 规划； 在服务 任务集未给定的情况下， 求最优的服务任务集， 采用分支剪界法求解整数非线性规划， 便于快速 求出最优的任务点分配； 实现混合整数非线性规 划和整数非线性规划建模结合， 针对服务任务集 的实际状况分类进行计算， 减少了优化过程中的 迭代次数。 权利要求书5页 说明书12页 附图5页 CN 115202849 A 2022.10.18 CN 115202849 A 1.一种支持边缘计算的多无人机任务分配与路径规划方法， 其特征在于， 包括以下步 骤： S1： 将任务点、 智能机场点建模成顶点， 将任务点之间以及任务点与智能机场点之间的 距离建模成边， 建立原问题的任务区域的图表征； S2： 在每个无人机每次飞行的服务任务集给定的情况下， 根据 给定的任务点的分配， 通 过粒子群算法求解每个无人机每次飞行中所服务的所有任务的完成时间最小化模型， 得到 每个无人机单次飞行的最优飞行路径和任务 量分配； S3： 在每个无人机每次飞行的服务任务集未定的情况下， 建立全任务的完成时间最小 化模型， 通过分支剪界法求解全任务的完成时间最小化模型， 得到最优的任务点分配， 将最 优的任务点分配作为步骤S2中的给定的任务点的分配， 返回步骤S2， 得到最优任务点分配 下的最优 任务量分配与飞行路径规划。 2.根据权利要求1所述的一种支持边缘计算的多无人机任务分配与路径规划方法,其 特征在于， 所述建立原问题的任务区域的图表征， 还包括： 计算任务点之间的边的权重、 任 务点和智能机场点之间的边的权 重和任务顶点的权 重。 3.根据权利要求1所述的一种支持边缘计算的多无人机任务分配与路径规划方法,其 特征在于， 所述建立原问题的任务区域的图表征， 包括以下步骤： S101： 建立任务顶点 集： 在公式(1)中， 表示n个任务点构成的顶点 集， 表示第i个任务点； S102： 建立智能机场顶点 集： 在公式(2)中， 表示m个智能机场点构成的顶点 集， 表示第j个智能机场点； S103： 建立任务 点之间的路径构成的边 集： 在公式(3)中， 表示n个任务点之间的路径构成的边集， 表示第 个任务点和第 个任务点之间的边； S104： 建立任务 点与智能机场点之间的路径构成的边 集： 在公式(4)中， 表示n个任务点与 m个智能机场点之间的路径构成的边集， 表示第i 个任务点和第j个智能机场点之间的边； S105： 计算任务 点之间的边的权 重： 在公式(5)中， 表示表示第 个任务点和第 个任务点之间的权重， 和权　利　要　求　书 1/5 页 2 CN 115202849 A 2分别表示第 个任务点和第 个任务点的二维坐标； S106： 计算任务 点和智能机场点之间的边的权 重： 在公式(6)中， 表示第i个任务点和第 j个智能机场点之间的权重， 和 分别表示第 i个任务点和第j个智能机场点的二维坐标； S107： 任务顶点的权 重： 在公式(7)中， 表示第 个任务点的计算任务 量。 4.根据权利要求1所述的一种支持边缘计算的多无人机任务分配与路径规划方法,其 特征在于， 所述步骤S2中求解每个无人机每次飞行中所服务的所有任务的完成时间最小化 模型， 包括以下步骤： S201： 根据给定的任务点分配， 对给定任务点 i在无人机 j在第k次飞行中任务量的分配 率决策变量和飞行顺序决策变量进行约束， 根据任务点之 间的边的权重、 任务顶点的权重、 无人机j的飞行速度和计算速率， 计算无人机 j第k次飞行中从起 飞到服务完第 r个任务点的 时间； S202： 根据S201中求得的无人机 j第k次飞行中从起飞到服务完第 r个任务点的时间， 以 及任务点和智能机场点之 间的边的权重， 建立无人机 j第k次飞行中所服务的所有任务的完 成时间最小化模型并求 解， 得到每 个无人机单次飞行的最优飞行路径和任务 量分配。 5.根据权利要求4所述的一种支持边缘计算的多无人机任务分配与路径规划方法,其 特征在于， 所述步骤S201中计算无人机 j第k次飞行中从起飞到服务完第 r个任务点的时间 包括以下步骤： S2011： 给定的任务 点分配表示 为： 在公式(8)中， 表示任务点 i在无人机 j的第几次飞行中被服务， 其中当 时， 任务 点i在无人机j的第 次飞行中被服 务， 当 时， 任务点i不被服务； S2012： 任务 点i在无人机j在第k次飞行中任务 量的分配率决策变量进行约束： 在公式(9)中， 表示任务点 i在无人机 j在第k次飞行中任务量的分配率， 表示无 人机j第k次飞行中的服 务任务集； S2013： 对无 人机j第k次飞行的飞行顺序决策变量进行约束： 在公式(10)中， 表示无人机 j第k次飞行中第r个被服务的任务点是 ， 对任意集合权　利　要　求　书 2/5 页 3 CN 115202849 A 3