利索能及
我要发布
收藏
专利号: 2019108921977
申请人: 合肥工业大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-12-30
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种移动平台路径规划与无人机任务分配的两阶段优化方法,其特征在于,包括:获取异构任务集合和路网数据;其中,所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务;

构建无人机与移动平台协同执行所述异构任务集合的路径规划模型;其中,所述路径规划模型以将无人机与移动平台从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标,所述路径规划模型的预设约束条件为根据无人机与移动平台协同执行所述异构任务集合的预设场景而设置,所述预设场景包括:搭载有可多次起降的无人机的移动平台从所述预设控制中心出发,沿着道路行驶,并在道路交口释放所述无人机,所述无人机和所述移动平台执行所述点任务或者所述线任务,在所述无人机的电量不足以至于无法继续执行下一个任务时返回到道路交口与所述移动平台汇合并更换电池,并继续执行下一个任务,直至所述无人机和所述移动平台将所述异构任务集合中所有任务执行完成,所述移动平台搭载所述无人机返回到所述预设控制中心;

采用预设二阶段求解算法求解所述路径规划模型,得到最优解,所述最优解为所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径;

所述采用预设二阶段求解算法求解所述路径规划模型,得到最优解,包括:

计算所述移动平台单独完成所述异构任务集合中所有任务时的最短路径;

根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径;

所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,包括:从所述异构任务集合中按序选择一个任务试分配给无人机,并判断移动平台是否满足第一约束条件,所述第一约束条件包括:所述移动平台从所述预设控制中心出发的总次数为1、所述移动平台返回到所述预设控制中心的总次数为1、所述移动平台到达道路网络中任一道路交点的总次数与从该道路交点离开的总次数相同、所述预设控制中心的移动平台访问顺序编号为1以及各个道路交点的移动平台访问顺序编号随着所述移动平台的行驶而递增中的至少一项;

采用第一公式表示第一约束条件“所述移动平台从所述预设控制中心出发的总次数为

1”,所述第一公式为

式中,E={eij=(Vi,Vj)},E为道路网络中所有道路线段的集合,eij=(Vi,Vj)为从第i个道路交点到第j个道路交点之间的道路线段;VE为所述移动平台和所述无人机的返回交点集合;x0j为0或1,若x0j=1则表示移动平台从第0个道路交点行驶到第j个道路交点,若x0j=

0则表示移动平台未从第0个道路交点行驶到第j个道路交点;和/或

采用第二公式表示第一约束条件“所述移动平台返回到所述预设控制中心的总次数为

1”,所述第二公式为:

式中,xi0为0或1,若xi0为1则表示移动平台从第i个道路交点行驶到第0个道路交点,若xi0为0则表示移动平台未从第i个道路交点行驶到第0个道路交点;VS为所述移动平台和所述无人机的出发交点集合;第0个道路交点为所述预设控制中心;和/或采用第三公式表示第一约束条件“所述移动平台到达道路网络中任一道路交点的总次数与从该道路交点离开的总次数相同”,所述第三公式包括:式中,V为所述返回交点集合和所述出发交点集合的并集;和/或

采用第四公式表示第一约束条件“所述预设控制中心的移动平台访问顺序编号为1”,所述第四公式为:u0=1

式中,u0为所述预设控制中心的移动平台访问顺序编号;和/或

采用第五公式表示第一约束条件“各个道路交点的移动平台访问顺序编号随着所述移动平台的行驶而递增”,所述第五公式为:式中,ui为第i个道路交点的移动平台访问顺序编号。

2.根据权利要求1所述的方法,其特征在于,所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,还包括:若所述无人机满足第一约束条件,则判断所述无人机是否满足第二约束条件,所述第二约束条件包括:所述无人机在每一个架次中的释放次数为1、所述无人机在每一个架次中的返回次数为1、所述无人机到达任一道路交点的总次数与从该道路交点离开的总次数相同、所述无人机在每一次架次中返回所述移动平台之前需要被释放、所述无人机在任一架次中被释放之前需要在上一架次中返回到所述移动平台以及所述无人机的架次随着移动平台的行驶而递增中的至少一项;

采用第六公式表示第二约束条件“所述无人机在每一个架次中的释放次数为1”,所述第六公式包括:式中, 表示所述无人机的第f个架次中是否从第i个道路交点起飞并从第j个道路交点降落; 为0或1,若 为1则表示所述无人机在第f个架次中从第i个道路交点飞行至第k个道路交点,若 为0则表示所述无人机在第f个架次中未从第i个道路交点飞行至第k个道路交点;和/或采用第七公式标识第二约束条件“所述无人机在每一个架次中的返回次数为1”,所述第七公式为:和/或

采用第八公式表示第二约束条件“所述无人机到达任一道路交点的总次数与从该道路交点离开的总次数相同”,所述第八公式为:和/或

采用第九公式表示第二约束条件“所述无人机在每一次架次中返回所述移动平台之前需要被释放”,所述第九公式为:和/或

采用第十公式表示第二约束条件“所述无人机在任一架次中被释放之前需要在上一架次中返回到所述移动平台”,所述第十公式为:式中, 为所述无人机在第f架次中的起飞交点的移动平台访问顺序编号; 为所述无人机在第f架次中的降落交点的移动平台访问顺序编号; 为所述无人机在第f’架次中的起飞交点的移动平台访问顺序编号; 为所述无人机在第f’架次中的降落交点的移动平台访问顺序编号;和/或采用第十一公式表示第二约束条件“所述无人机的架次随着移动平台的行驶而递增”,所述第十一公式为:

3.根据权利要求2所述的方法,其特征在于,所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,还包括:若满足第二约束条件,则判断是否满足第三约束条件,所述第三约束条件包括:在同一架次中所述无人机的飞行耗时随着所述无人机的飞行而增加、所述无人机的每一个架次的飞行里程小于等于所述无人机的最大续航里程、所述无人机的每一个架次的起飞时间点为

0、移动平台从所述预设控制中心出发的时间点为0以及将无人机到达每一个架次的降落点的时间以及移动平台到达该降落点的时间进行对齐中的至少一项;

采用第十二公式表示第三约束条件“在同一架次中所述飞行机的飞行耗时随着所述无人机的飞行而增加”,所述第十二公式为:式中,M为极大值,CU为所述无人机飞行单位路程所耗费的时间,w(ehk)为道路线段(Vh,Vk)的长度, 为所述无人机在f架次中到达第h个道路交点的时间;和/或采用第十三公式表示第三约束条件“所述无人机的每一个架次的飞行里程小于等于所述无人机的最大续航里程”,所述第十三公式为:式中,RMax为所述最大续航里程,ti为所述移动平台到达第i个道路交点的时间,CV为所述移动平台行驶单位路长耗费的时间;和/或采用第十四公式表示第三约束条件“所述无人机的每一个架次的起飞时间点为0”,所述第十四公式为:和/或

采用第十五公式表示第三约束条件“移动平台从所述预设控制中心出发的时间点为

0”,所述第十五公式为:

t0=0;和/或

采用第十六公式表示第三约束条件“将无人机到达每一个架次的降落点的时间以及移动平台到达该降落点的时间进行对齐”,所述第十六公式为:式中,SR为所述无人机的释放所耗费的时间,SL为所述无人机的回收所耗费的时间。

4.根据权利要求3所述的方法,其特征在于,所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,还包括:若满足所述第三约束条件,则判断是否满足第四约束条件,所述第四约束条件包括:任意一个线任务被所述移动平台和所述无人机访问的总次数为1,和/或,任意一个点任务被所述移动平台和所述无人机访问的总次数为1;

采用第十七公式表示第四约束条件“任意一个线任务被所述移动平台和所述无人机访问的总次数为1”,所述第十七公式为:E

式中,T为所有线任务的集合;和/或

采用第十八公式表示第四约束条件“任意一个点任务被所述移动平台和所述无人机访问的总次数为1”,所述第十八公式为:V

式中,T为所有点任务的集合。

5.根据权利要求4所述的方法,其特征在于,所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,还包括:若满足所述第四约束条件,则判断是否能够实现目标函数,所述目标函数为:

min tv

式中,tv为所述移动平台从所述预设控制中心出发至返回到所述预设控制中心的时间;

若能够实现目标函数,则从所述异构任务集合中按序选择下一个任务分配给无人机,并进行约束条件和目标函数的判断,直至所述异构任务集合中所有任务都遍历完成,得到由无人机和移动平台各自执行的任务以及所述移动平台和所述无人机执行各自任务的最优路径。

6.一种移动平台路径规划与无人机任务分配的两阶段优化装置,其特征在于,包括:任务输入模块,用于获取异构任务集合和路网数据;其中,所述异构任务集合中包括道路交点对应的点任务和道路线段对应的线任务;还用于构建无人机与移动平台协同执行所述异构任务集合的路径规划模型;其中,所述路径规划模型以将无人机与移动平台从预设控制中心出发、执行完所述异构任务集合中所有任务并返回到所述预设控制中心所耗费的总时间最小化为优化目标,所述路径规划模型的预设约束条件为根据无人机与移动平台协同执行所述异构任务集合的预设场景而设置,所述预设场景包括:搭载有可多次起降的无人机的移动平台从所述预设控制中心出发,沿着道路行驶,并在道路交口释放所述无人机,所述无人机和所述移动平台执行所述点任务或者所述线任务,在所述无人机的电量不足以至于无法继续执行下一个任务时返回到道路交口与所述移动平台汇合并更换电池,并继续执行下一个任务,直至所述无人机和所述移动平台将所述异构任务集合中所有任务执行完成,所述移动平台搭载所述无人机返回到所述预设控制中心;

二阶段求解模块,用于采用预设二阶段求解算法求解所述路径规划模型,得到最优解,所述最优解为所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径;

所述采用预设二阶段求解算法求解所述路径规划模型,得到最优解,包括:

计算所述移动平台单独完成所述异构任务集合中所有任务时的最短路径;

根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径;

所述根据所述最短路径、所述预设约束条件和预设启发式分配算法,从所述异构任务集合中筛选出至少一个任务由无人机完成以实现所述优化目标,并输出所述移动平台和所述无人机共同完成所述异构任务集合中所有任务时所述移动平台和所述无人机各自的最优路径,包括:从所述异构任务集合中按序选择一个任务试分配给无人机,并判断移动平台是否满足第一约束条件,所述第一约束条件包括:所述移动平台从所述预设控制中心出发的总次数为1、所述移动平台返回到所述预设控制中心的总次数为1、所述移动平台到达道路网络中任一道路交点的总次数与从该道路交点离开的总次数相同、所述预设控制中心的移动平台访问顺序编号为1以及各个道路交点的移动平台访问顺序编号随着所述移动平台的行驶而递增中的至少一项;

采用第一公式表示第一约束条件“所述移动平台从所述预设控制中心出发的总次数为

1”,所述第一公式为

式中,E={eij=(Vi,Vj)},E为道路网络中所有道路线段的集合,eij=(Vi,Vj)为从第i个道路交点到第j个道路交点之间的道路线段;VE为所述移动平台和所述无人机的返回交点集合;x0j为0或1,若x0j=1则表示移动平台从第0个道路交点行驶到第j个道路交点,若x0j=

0则表示移动平台未从第0个道路交点行驶到第j个道路交点;和/或

采用第二公式表示第一约束条件“所述移动平台返回到所述预设控制中心的总次数为

1”,所述第二公式为:

式中,xi0为0或1,若xi0为1则表示移动平台从第i个道路交点行驶到第0个道路交点,若xi0为0则表示移动平台未从第i个道路交点行驶到第0个道路交点;VS为所述移动平台和所述无人机的出发交点集合;第0个道路交点为所述预设控制中心;和/或采用第三公式表示第一约束条件“所述移动平台到达道路网络中任一道路交点的总次数与从该道路交点离开的总次数相同”,所述第三公式包括:式中,V为所述返回交点集合和所述出发交点集合的并集;和/或

采用第四公式表示第一约束条件“所述预设控制中心的移动平台访问顺序编号为1”,所述第四公式为:u0=1

式中,u0为所述预设控制中心的移动平台访问顺序编号;和/或

采用第五公式表示第一约束条件“各个道路交点的移动平台访问顺序编号随着所述移动平台的行驶而递增”,所述第五公式为:式中,ui为第i个道路交点的移动平台访问顺序编号。

7.一种计算机设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述计算机程序时实现权利要求1至5中任一项所述方法的步骤。

8.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现权利要求1至5中任一项所述的方法的步骤。