(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111472534.0 (22)申请日 2021.12.0 6 (71)申请人 中国科学院大学 地址 100049 北京市石景山区玉泉路甲19 号中国科 学院大学人工智能学院 (72)发明人 王梓嘉　张宝贤　 (51)Int.Cl. G06F 30/20(2020.01) G06F 30/15(2020.01) G06F 111/04(2020.01) (54)发明名称 一种群智感知下基于单车辆无人机的路径 规划和任务调度方法 (57)摘要 一种群智感知下基于单车辆无人机的路径 规划和任务调度方法， 利用单车辆以及部署在该 单车辆上的一定数量的无人机， 协作完成一定区 域内的群智感知任务， 提升群智感知的工作效率 并降低成本， 主要包括： 根据感知区域及目标地 点构造带权连通完全图的方法、 路径 规划随机优 化方法、 以及对 单车辆无人机进行联合路径规划 和任务调度的优化算法。 该方法主要借助单车辆 及部署在该车辆上的无人机， 通过对 单车辆和无 人机的联合优化调度， 以提升群智感知的任务完 成效率， 同时降低任务执 行成本。 权利要求书2页 说明书3页 CN 114417551 A 2022.04.29 CN 114417551 A 1.一种群智感知下基于单车辆无人机的路径规划和任务调度方法， 其特征在于： 利用 单车辆以及部署在该单车辆上的一定数量的无人机， 协作完成一定区域内的群智感知任 务， 提升群智感知的工作效率并降低成本， 主要包括： 根据感知区域及目标地点构造带权连 通完全图的方法、 路径规划随机优化方法、 以及对单车辆无人机进行联合路径规划和任务 调度的优化 算法。 2.根据权利要求1所述的一种群智感知下基于单车辆无人机的路径规划和任务调度方 法， 其特征在于： 所述 根据感知区域及目标地 点构造带权连通完全图的方法， 具体如下： 首先， 对于给定n个目标任务地点， 对于任意两点u和v， 若其同属于车辆可到达区域， 则 其间可供车辆行驶的路线的距离作为这两点间的边的权重， 记做d(u,  v)， 对于车辆不可达 区域的目标地点u ’， 其与任意其它点x之间的边权重d(u ’, x)设为一个足够大的值M， 如M  =  max{车辆可达两点之间的所有边的权重}*n； 对于无人机来说， 任意目标地点均是可访问 的， 因此任意两点u和v间的供无人机飞行的路线距离作为这两点间的边权重,  记做d’(u,  v)； 无论对于无人机还是车辆， 边(u,  v)的权重与边(v,  u)的权重相同； 权重d(u,  v)与d’ (u, v)分别作为车辆和无 人机沿边(u,  v)移动的耗时、 耗能成本的计算依据。 3.根据权利要求2所述的一种群智感知下基于单车辆无人机的路径规划和任务调度方 法， 其特征在于： 所述路径规划随机优化方法， 具体如下： 1） 随机选取k个任务目标点， 将这些目标点从当前路径规划S中剔除， 即车辆和无人机 都不再访问这些目标点， 若某些目标点剔除后导致无效的无人机飞行路线， 则将该飞行路 线上的所有目标点 一并剔除， 在此基础上， 得到一个剔除部分任务目标点的新路径规划S ’； 2） 对一个在步骤1)  中剔除的某一目标点p， 尝试将其重新插入到路径规划S ’中， 包括 三种选择： i)  若p为车辆可达的目标点， 则尝试将其插入车辆访问路径中每一个可能的位 置； ii) 尝试将其插入每个无人机飞行路径中的任意一个位置； ii)  若车上存在 空闲无人 机， 则尝试调度一架空闲的无人机单独访问目标点p， 所选飞行线路的起点和与车辆汇合点 必须是车辆路线上 的顶点， 且起点在该车辆路线上 的位置必须不 晚于汇合点位置； 遍历这 三种插入方法的所有可能选择， 对于每一种插入后得到的路径规划， 检查其可行性， 即： 是 否满足无人机最大飞行距离约束， 若 可行的话， 计算其成本， 最 终采用成本最小的可行插入 方式将目标点p重新纳入单 车辆无人机的路径规划中； 3） 重复步骤2)， 直到所有被剔除的任务点均被重新纳入规划路线中， 至此得到新的路 径规划S’； 上述步骤中， 步骤1)  称为随机顶点剔除方法， 步骤2)   ‑  3) 称为顶点插 入优化方法。 4.根据权利要求3所述的一种群智感知下基于单车辆无人机的路径规划和任务调度方 法， 其特征在于： 所述对单车辆无人机进行联合路径规划和任务调度的优化算法， 具体如 下： i) 在所述带权连通完全图之上随机生成一个基于单车辆的路径规划， 来访 问所有任 务目标点， 而后将路径上 的对车辆不可达的目标点从该路径规划中剔除出去， 根据所述顶 点插入优化方法将这些目标点重新纳 入到路径规划中， 得到一个初始的单车辆无人机路径 规划S； ii) 初始化整数k为1， T为0， R为0， 以S_best记录当前成本最小的路径规划解， 其初值 为S；权　利　要　求　书 1/2 页 2 CN 114417551 A 2iii) 按照所述路径规划随机优化方法对S进行优化， 得到新的车辆无人机路径规划 S’， 此时R增 加1； iv) 计算S’所需的成本， 与S_best相比较， 若其低于S_best， 则更新S_best为S ’， 并设 置T为0； v) 将S’所需成本与S相比较， 若其低于S， 则更新S为S ’， 并设置k为1， R为0， 否则若k小 于一个预设的阈值 k_max， k增 加1； vi) 若R大于一个预设的阈值R_max， 则T增加1， 设置R为0， k为1， 并执行步骤i)， 更新S 为一个新的随机路径规划； vii) 若T大于一个预设的阈值T_max， 则结束计算过程， 输出S_best为最终的单车辆无 人机路径规划计算结果， 否则回到步骤i ii)。权　利　要　求　书 2/2 页 3 CN 114417551 A 3