一种基于任务动态迁移均衡的多机场无人机协同调度方法及系统与流程
本发明属于无人机任务调度和航线规划,尤其涉及一种基于任务动态迁移均衡的多机场无人机协同调度方法及系统。
背景技术:
1、在地理图斑巡检、电力巡线、农业植保和地质勘察等批量飞行作业中,通常由多个机场及其无人机共同承担分布于不同位置的任务。不同机场受无人机航时、剩余电量、安全余量和地理位置影响,具有不同的有效作业范围和单航次可用时间容量。
2、现有基于最近距离或几何中心的分配方法主要依据任务位置与机场位置之间的距离确定任务归属,未计算任务插入机场现有任务航线后实际增加的飞行时间,因而可能将距离机场较近但需要明显绕行的任务分配给该机场,同时忽略位于另一机场既有航线附近的顺路任务。
3、在多个机场的有效作业范围重叠时,部分任务仅由一个机场覆盖,另一些任务能够由多个机场覆盖。若不区分两类任务,负载平衡过程可能错误迁移仅具有唯一可执行节点的任务;若仅将容量作为航线生成后的校验条件,则又容易反复撤销和重建任务分配结果。
4、现有调度方法还可能仅以航线总时间是否下降作为迁移条件。当源节点需要通过迁移解除超载而目标节点的插入成本略高时,该条件会拒绝能够恢复容量可行性的迁移;当多个节点同时达到相同最大航次时间时,仅要求全局最大航次时间立即下降也会限制有效迁移。
5、因此,需要一种将唯一覆盖约束、真实路径增量、单航次容量和多轮执行状态结合起来的无人机协同调度方法,在保持锚点任务归属可行的同时降低航线绕行和局部超载,并生成能够直接下发执行的完整无人机航线。
技术实现思路
1、本发明的目的在于提供一种基于任务动态迁移均衡的多机场无人机协同调度方法及系统,以解决现有技术中唯一覆盖任务与多覆盖任务未作区分、任务归属未反映真实路径增量、容量修复迁移受单一总时间指标限制以及未完成任务难以按当前节点状态重新调度的问题。
2、为实现上述目的,本发明的一种基于任务动态迁移均衡的多机场无人机协同调度方法的具体技术方案如下:
3、一种基于任务动态迁移均衡的多机场无人机协同调度方法,包括以下步骤:
4、s1、获取待调度任务数据及多个无人机调度节点的节点位置、有效作业半径、单航次可用时间容量和当前状态,计算每个任务的覆盖节点集合,据此将任务分类为锚点任务、多覆盖任务和不可达任务;
5、s2、将锚点任务分配给其唯一覆盖节点,并按最小路径增量对应的插入位置维护该节点的当前任务航线;
6、s3、对多覆盖任务计算其插入各候选节点当前任务航线的最小路径增量,结合候选节点负载和剩余容量形成综合分配代价,选择综合分配代价最小的候选节点及插入位置形成初始任务航线;
7、s4、当存在航次时间超过单航次可用时间容量的超载节点时,针对超载节点中的多覆盖任务生成迁移候选,在目标节点覆盖该任务、插入后不超容量且迁移后超载评价指标按字典序减小的条件下执行迁移,并迭代至无可行迁移或达到迭代上限;
8、s5、若全部节点均满足单航次可用时间容量则输出单轮协同调度模式,否则输出多轮分批调度模式并将本轮不能装入的任务回收至任务池;
9、s6、根据各节点本轮保留的任务序列生成包含起飞点、任务执行点和返航点的完整航点序列,并下发至相应节点绑定的无人机执行。
10、进一步的,步骤s1中,每个无人机调度节点由机场与本轮可用无人机绑定形成,并至少包括节点标识、起飞位置、巡航速度、有效作业半径、单航次可用时间容量、当前任务航线和节点状态;每个任务至少包括任务标识、代表位置、优先级、预计作业时间、创建时间和任务状态;对于点任务,其代表位置为任务点;对于区域任务,其代表位置为预生成作业航线的入口点、出口点或预设代表点,区域内部航线的飞行时间和作业时间计入预计作业时间。
11、进一步的,步骤s1中,计算每个任务的覆盖节点集合时,针对每个任务和各调度节点计算任务代表位置与调度节点起飞位置之间的距离,并根据调度节点的有效作业半径判断该调度节点是否覆盖该任务,将覆盖该任务的调度节点组成覆盖节点集合;其中,采用经纬度坐标时所述距离为球面测地距离,采用统一投影坐标时所述距离为平面投影距离,需要计入高度差或预定航路时所述距离为三维航迹距离;所述有效作业半径按照节点所绑定无人机的巡航速度与可用于往返巡航的时间确定,所述可用于往返巡航的时间由单航次可用时间容量扣除起飞时间、降落时间和任务作业预留时间后得到,且其取值不小于零;当覆盖节点集合为空时,输出该任务不可达的异常原因。
12、进一步的,步骤s2中,锚点任务在节点之间不可迁移;对于每个锚点任务,遍历该锚点任务在其唯一覆盖节点当前任务序列中的全部插入位置,所述全部插入位置包括序列首端、相邻任务之间及序列尾端,选择使该唯一覆盖节点航次时间增加最小的插入位置进行插入;当唯一覆盖节点的单航次可用时间容量不足时,允许将该锚点任务延后至后续轮次执行。
13、进一步的,步骤s3中,按照任务优先级降序、覆盖节点数量升序和创建时间升序的顺序依次处理多覆盖任务;对于当前多覆盖任务和每个候选节点,遍历该任务插入候选节点当前任务序列全部可插入位置时引起的航次时间增加量,取其中的最小值作为该候选节点的最小路径增量;所述综合分配代价为无量纲值,由路径增量项、候选节点当前航次负载项和候选节点剩余时间容量项加权组合而成,各时间量均除以候选节点的单航次可用时间容量进行归一化;任务优先级仅用于确定多覆盖任务的处理顺序,不作为对同一任务比较不同候选节点时的常数项。
14、进一步的,步骤s4中,对于每个调度节点,将其航次时间超过单航次可用时间容量的部分确定为该节点的超载时间,未超过时超载时间为零;所述超载评价指标依次包括超载节点数量、所有节点超载时间之和、所有节点航次时间的最大值以及所有节点航次时间之和;迁移前后按照上述超载评价指标分量的顺序进行字典序比较。
15、进一步的,步骤s4中,对于超载节点中的每个多覆盖任务,计算源节点移除该任务后的节省时间以及目标节点插入该任务后的增加时间,并根据节省时间与增加时间确定迁移增益;在满足目标节点覆盖该任务且插入后不超过单航次可用时间容量的迁移候选中,仅保留使超载评价指标按字典序严格减小的迁移候选,并优先选择超载评价指标改善幅度较大、迁移增益较大的迁移候选执行迁移;其中,不以迁移增益大于零作为执行迁移的绝对条件,当迁移使超载节点数量和超载时间之和下降而航线总时间略有增加时,仍执行该迁移。
16、进一步的,步骤s5中,在输出多轮分批调度模式时,先按照低优先级、长作业时间和高路径释放时间的顺序回收多覆盖任务;若仍然超载,再按照相同规则回收锚点任务,并记录锚点任务的唯一覆盖节点约束;每个节点每轮至多生成一个批次,等待本轮全部批次进入完成、失败或取消状态后,回收未完成任务,刷新无人机剩余电量、可用状态和机场位置,并重新执行步骤s1至s4;达到最大重试次数的任务标记为永久失败,其余任务进入下一轮。
17、进一步的,当某一航次中断时,仅将尚未完成的任务回收至任务池,已完成任务保持完成状态;下一轮针对未完成任务重新生成从当前绑定机场出发并返回该绑定机场的完整航线,而不将上一次中断位置直接作为新航线的起点;所述单航次可用时间容量由有效可用飞行时间与无量纲效率因子相乘得到,所述有效可用飞行时间根据无人机最大飞行时间、当前可用电量比例及安全时间余量确定,所述效率因子的取值大于零且不大于1,并根据历史飞行时间与计划飞行时间的偏差向下修正。
18、本发明还公开了一种基于任务动态迁移均衡的多机场无人机协同调度系统,包括:
19、输入层,用于获取待调度任务数据、无人机调度节点的节点位置、有效作业半径、单航次可用时间容量和当前状态以及执行反馈;
20、调度核心层,包括覆盖分析与任务分类模块、路径时间与增量计算模块、锚点及多覆盖任务分配模块、迁移平衡模块、调度模式与动态轮次模块以及航线生成与下发模块;任务池模块,用于存储本轮不能装入的任务并执行重试次数控制;
21、输出层,用于输出各调度节点的完整任务航线、分批结果及不可达任务;其中,所述调度核心层被配置为执行所述的基于任务动态迁移均衡的多机场无人机协同调度方法。
22、本发明的一种基于任务动态迁移均衡的多机场无人机协同调度方法具有以下优点:通过覆盖关系预分类固定唯一覆盖任务的可执行边界;以任务插入现有航线的最小路径增量反映真实绕行成本;以容量可行性优先的有序指标允许必要的负载迁移;通过任务池和轮次推进适应无人机状态变化;并将调度结果转换为能够下发执行的完整航点序列。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com