本发明涉及一种无人机航空作业任务分配方法及装置，该方法中针对于多旋翼无人机对多块候选农田执行作业任务的情况，首先获取无人机、农田、喷洒任务时间窗、以及农药等四类信息，接着根据这些信息基于预设的模型以及遗传算法，获得能够使得该模型获得最大总收益的最优解，并将该最优解作为本次作业的任务分配和航迹规划结果。相比于现有的方式，本发明提供的方法可以自动获得本次作业中每架无人机的任务以及航迹规划，使得各架无人机可以按照该任务以及航迹规划自动执行作业任务，可避免出现各架无人机彼此不协同的问题，能够有效地提高作业效率，使得无人机作业形式应用于更广泛的农业航空作业中。
1.一种无人机航空作业任务分配方法，其特征在于，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，所述方法包括：获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的信息；
对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
2.根据权利要求1所述的方法，其特征在于，所述目标函数为：
其中，Nu表示无人机Uu的个数；NA表示农田Ai的总个数；SPi表示完成农田Ai的喷洒任务所获得的收益；SQi表示农田Ai的面积；Pi(t)为连续变化函数，其变化函数取决于农田喷洒农药的类型；M的值为预设值；siu表示无人机Uu对农田Ai开始喷洒农药的时间，sju表示无人机Uu对农田Aj开始喷洒农药的时间；Oiu表示无人机Uu对农田Ai可以喷洒农药的开始时间；Ciu表示无人机Uu对农田Ai可以喷洒农药的结束时间；tiu表示无人机Uu对农田Ai按照预设的飞行方式执行任务的时间；tiju表示无人机Uu对农田Ai,Aj之间按照预设的飞行方式飞行的时间；Eu表示无人机Uu的最大飞行时长限制；xiu表示无人机Uu对农田Ai完成药物喷洒任务的情况，若xiu＝1，则表示完成药物喷洒任务，否则无人机Uu没有对农田Ai执行任务；yiju表示无人机Uu是否经过农田Ai,Aj，若yiju＝1表示无人机Uu经过农田Ai,Aj，否则该无人机没有经过农田Ai,Aj。
3.根据权利要求1或2任一所述的方法，其特征在于，所述农田为矩形的农田，所述预设的飞行方式为基于欧氏距离路径在农田间以及农田内进行飞行的方式；
其中，在农田内部采用平行于矩形农田的第一边的方式飞行，且以垂直于农田第一边的方向从第一边上的第一进入点进入农田，所述第一进入点与农田顶点的距离为无人机喷洒半径；
4.根据权利要求1所述的方法，其特征在于，所述对所述无人机的信息以及所述农田信息进行编码，随机生成多条染色体，包括：对所述无人机的标识信息、所述无人机的数量、每条线路中的无人机进入第一块农田的起始时间、所述农田的位置信息以及每架无人机进入农田时的进入点采用全信息编码方式进行编码，随机生成多条染色体；
其中，所述染色体的第一行为所述农田的标识信息的随机全排列，所述染色体的第二行为所有无人机的标识信息的随机组合，所述染色体的第三行为所述进入点的随机组合，所述染色体的第四行为所述无人机路线中访问第一块农田开始时间的随机组合。
5.根据权利要求4所述的方法，其特征在于，所述基于预设的遗传算法对所述初始解集进行随机变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果，包括：步骤一、根据所述初始解集生成预设规模的初始父代种群；
步骤二、采用轮盘赌方法将当前的父代种群中的任意两个染色体进行交叉并迭代此交叉步骤，满足迭代次数后结束此交叉步骤得到第一子代种群，所述交叉的步骤具体包括：随机选择第一染色体中的交叉位置，然后寻找第二染色体中与第一染色体交叉位置的第一行相同的基因；将第一染色体与第二染色体的交叉位置基因进行替换，然后将与交叉位置基因第二行相同的基因处第四行也替换为交叉位置基因第四行的开始时间，从而得到第三染色体以及第四染色体；判断所述第三染色体以及第四染色体是否满足所述预设约束条件；若满足，则替换所述父代种群中的第一染色体以及第二染色体；若不满足，则结束当前操作；
步骤三、采用轮盘赌方法将所述第一子代种群中的任意一个第五染色体进行个体变异，并判断变异后的第五染色体是否满足所述预设约束条件；若满足，则替换变异的第五染色体；若不满足，则结束当前操作，并迭代此变异步骤，满足迭代次数后结束此变异步骤得到第二子代种群；
在判断获知第五染色体的第二行发生过变异时，确定其变异的位置，并将随机生成的无人机标识信息替换原变异位置处的无人机标识信息；
在判断获知第五染色体的第三行发生过变异时，确定其变异的位置，并将随机生成的进入点替换原变异位置处的进入点；
在判断获知第五染色体的第四行发生变异时，确定变异位置，并将随机生成的时间窗之间的时间替换与变异位置第二行相同的基因处第四行的开始时间；
步骤四、选取所述第二子代种群中的最优解，并将所述第二子代种群与所述父代种群按照预设比例组合形成新的父代种群；
判断当前步骤二、三、四整体循环迭代的次数是否达到预设值；若否，则返回步骤二，并将所述新的父代种群作为当前的父代种群执行步骤二；若是，则执行步骤五；
步骤五：结束迭代，并将最终获得的最优解作为本次作业的任务分配和航迹规划结果。
6.一种无人机航空作业任务分配装置，其特征在于，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，所述装置包括：信息获取单元，用于获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的农田信息；
初始分配方案生成单元，用于对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
最优解计算单元，用于基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
7.根据权利要求6所述的装置，其特征在于，所述目标函数为：
其中，Nu表示无人机Uu的个数；NA表示农田Ai的个数；SPi表示完成农田Ai的喷洒任务所获得的收益；SQi表示农田Ai的面积；Pi(t)为连续变化函数，其变化函数取决于农田喷洒农药的类型；M的值为预设值；siu表示无人机Uu对农田Ai开始喷洒农药的时间，sju表示无人机Uu对农田Aj开始喷洒农药的时间；Oiu表示无人机Uu对农田Ai可以喷洒农药的开始时间；Ciu表示无人机Uu对农田Ai可以喷洒农药的结束时间；tiu表示无人机Uu对农田Ai按照预设的飞行方式执行任务的时间；tiju表示无人机Uu对农田Ai,Aj之间按照预设的飞行方式飞行的时间；
Eu表示无人机Uu的最大飞行时长限制；xiu表示无人机Uu对农田Ai完成药物喷洒任务的情况，若xiu＝1，则表示完成药物喷洒任务，否则无人机Uu没有对农田Ai执行任务；yiju表示无人机Uu是否经过农田Ai,Aj，若yiju＝1表示无人机Uu经过农田Ai,Aj，否则该无人机没有经过农田Ai,Aj。
8.根据权利要求6所述的装置，其特征在于，所述农田为矩形的农田，所述预设的飞行方式为基于欧氏距离路径在农田间以及农田内进行飞行的方式；
其中，在农田内部采用平行于矩形农田的第一边的方式飞行，且以垂直于农田第一边的方向从第一边上的第一进入点进入农田，所述第一进入点与农田顶点的距离为无人机喷洒半径；
9.根据权利要求6所述的装置，其特征在于，所述初始分配方案生成单元，进一步用于：
对所述无人机的标识信息、所述无人机的数量、每条线路中的无人机的起始时间、所述农田的位置信息以及每架无人机进入农田时的进入点进行采用全信息编码方式进行编码，随机生成多条染色体；
其中，所述染色体的第一行为所述农田的标识信息的随机全排列，所述染色体的第二行为所有无人机的标识信息的随机组合，所述染色体的第三行为所述进入点的随机组合，所述染色体的第四行为所述无人机路线中访问第一块农田开始时间的随机组合。
10.根据权利要求9所述的装置，其特征在于，所述最优解计算单元，进一步用于执行以下步骤：步骤一、根据所述初始解集生成预设规模的初始父代种群；
步骤一、根据所述初始解集生成预设规模的初始父代种群；
步骤二、采用轮盘赌方法将当前的父代种群中的任意两个染色体进行交叉并迭代此交叉步骤，满足迭代次数后结束此交叉步骤得到第一子代种群，所述交叉的步骤具体包括：随机选择第一染色体中的交叉位置，然后寻找第二染色体中与第一染色体交叉位置的第一行相同的基因；将第一染色体与第二染色体的交叉位置基因进行替换，然后将与交叉位置基因第二行相同的基因处第四行也替换为交叉位置基因第四行的开始时间，从而得到第三染色体以及第四染色体；判断所述第三染色体以及第四染色体是否满足所述预设约束条件；若满足，则替换所述父代种群中的第一染色体以及第二染色体；若不满足，则结束当前操作；
步骤三、采用轮盘赌方法将所述第一子代种群中的任意一个第五染色体进行个体变异，并判断变异后的第五染色体是否满足所述预设约束条件；若满足，则替换变异的第五染色体；若不满足，则结束当前操作，并迭代此变异步骤，满足迭代次数后结束此变异步骤得到第二子代种群；
在判断获知第五染色体的第二行发生过变异时，确定其变异的位置，并将随机生成的无人机标识信息替换原变异位置处的无人机标识信息；
在判断获知第五染色体的第三行发生过变异时，确定其变异的位置，并将随机生成的进入点替换原变异位置处的进入点；
在判断获知第五染色体的第四行发生变异时，确定变异位置，并将随机生成的时间窗之间的时间替换与变异位置第二行相同的基因处第四行的开始时间；
步骤四、选取所述第二子代种群中的最优解，并将所述第二子代种群与所述父代种群按照预设比例组合形成新的父代种群；
判断当前步骤二、三、四整体循环迭代的次数是否达到预设值；若否，则返回步骤二，并将所述新的父代种群作为当前的父代种群执行步骤二；若是，则执行步骤五；
步骤五：结束迭代，并将最终获得的最优解作为本次作业的任务分配和航迹规划结果。
无人机航空作业任务分配方法及装置
技术领域
[0001] 本发明实施例涉及无人机技术领域，具体涉及一种无人机航空作业任务分配方法及装置。
背景技术
[0002] 随着农业机械化程度的不断深化，无人机以其作业效率高、劳动强度小、综合成本低等方面的优势，迅速成为农业作业过程中一种重要的方式，已经在精量播种、植被检测、农药喷洒等农业航空作业中有着广泛的应用。例如，可以利用无人机对草本植物的发芽状况和杂草程度进行检测，或使用无人机对稻田进行农药喷洒来控制飞虱等等。
[0003] 目前的无人机大致可以大致分为多旋翼(例如四旋翼、六旋翼或八旋翼无人机等)以及固定翼两大类。其中多旋翼无人机以其能够占用较小面积垂直起降、操控简单、能够悬停在空中等优点被较为广泛地应用于农业作业中。
[0004] 然而，由于当前多旋翼无人机作业主要是人为遥控为主，实际作业的效果受到操作员的操作水平的影响较大，且通过人为即视的方式规划的航线与理论航线偏离严重，导致无人机的作业遗漏率和重复率往往偏高。且当多个操作员对多个多旋翼无人机操作时，彼此之间也缺乏协同。
[0005] 此外，在利用多旋翼无人机进行农药喷洒航空作业过程中，一般来说需要指定多架无人机在给定的一个时间窗内对多块候选农田喷洒不同的农药，每架无人机只能携带一种类型的农药，且每块农田只能由一架无人机执行喷洒任务。由于受到时间农田分布状况、作业气象状况、农药类型选择等因素的限制，无人机无法对所有农田都喷洒农药，因此如何能够根据上述影响因素对各架无人机的作业任务以及航迹进行合理规划，以使得喷洒后的候选区域农田的总收益最大(也即完成喷洒任务的农田药效的总和最大)也成为了一个亟待解决的问题。
发明内容
[0006] 本发明的一个实施例提供了一种无人机航空作业任务分配方法及装置，用于克服现有技术中在利用多架多旋翼无人机进行作业时，主要采用人工遥控的方式，彼此之间的协同性差，且无法对各架无人机的航迹进行合理规划以获得最大总收益的缺陷。
[0007] 第一方面，本发明实施例提供了一种无人机航空作业任务分配方法，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，所述方法包括：
[0008] 获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的信息；
[0009] 对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
[0010] 基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
[0011] 第二方面，本发明实施例还提供了一种无人机航空作业任务分配装置，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，所述装置包括：
[0012] 信息获取单元，用于获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的农田信息；
[0013] 初始分配方案生成单元，用于对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
[0014] 最优解计算单元，用于基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
[0015] 本发明的一个实施例提供了一种无人机航空作业任务分配方法，该方法中针对于多旋翼无人机对多块候选农田执行作业任务的情况，首先获取执行本次任务的一个时间窗、无人机的信息、农田的信息以及喷洒药物信息，接着根据这一信息基于预设的模型以及遗传算法，获得能够使得该模型获得最大总收益的最优解，并将该最优解作为本次作业的任务分配和航迹规划结果。相比于现有的人工遥控的方式，本发明提供的方法能够根据模型以及遗传算法自动获得本次作业中每架无人机的任务以及航迹规划，使得各架无人机可以按照该任务以及航迹规划自动执行作业任务，在避免出现各架无人机彼此不协同的情况发生的同时，还能够获得最大总收益，从而能够有效地提高作业的效率，使得无人机作业形式能够应用于更广泛的农业航空作业中。
附图说明
[0016] 通过阅读下文优选实施方式的详细描述，各种其他的优点和益处对于本领域普通技术人员将变得清楚明了。附图仅用于示出优选实施方式的目的，而并不认为是对本发明的限制。而且在整个附图中，用相同的参考符号表示相同的部件。在附图中：
[0017] 图1是本发明提供的一种无人机航空作业任务分配的方法实施例流程图；
[0018] 图2是本发明提供的矩形农田进入点示意图；
[0019] 图3是本发明提供的矩形农田间飞行轨迹示意图；
[0020] 图4是本发明提供的单时间窗染色体交叉示意图；
[0021] 图5是本发明提供的单时间窗染色体变异示意图；
[0022] 图6是本发明提供的农田分布示意图；
[0023] 图7是本发明提供的一种无人机航空作业任务分配的装置实施例结构示意图。
具体实施方式
[0024] 下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0025] 第一方面，本发明实施例提供了一种无人机航空作业任务分配方法，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，如图1所示，所述方法包括：
[0026] S101、获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的信息；
[0027] S102、对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；
[0028] S103、在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
[0029] S104、基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
[0030] 本发明的一个实施例提供了一种无人机航空作业任务分配方法，该方法中针对于多旋翼无人机在时间窗内对多块候选农田执行作业任务的情况，首先获取时间窗、无人机的信息、农田的信息以及喷洒药物信息，接着根据这一信息基于预设的模型以及遗传算法，获得能够使得该模型获得最大总收益的最优解，并将该最优解作为本次作业的任务分配和航迹规划结果。相比于现有的人工遥控的方式，本发明提供的方法能够根据模型以及遗传算法自动获得本次作业中每架无人机的任务以及航迹规划，使得各架无人机可以按照该任务以及航迹规划自动执行作业任务，在避免出现各架无人机彼此不协同的情况发生的同时，还能够获得最大总收益，从而能够有效地提高作业的效率，使得无人机作业形式能够应用于更广泛的农业航空作业中。
[0031] 在实际应用中，这里的多旋翼无人机具体可以为四旋翼无人机。当然也可以为其他种类的多旋翼无人机，本发明对此不做具体限定。
[0032] 在具体实施时，可以理解的是，上述方法中的MUAV-TW-VP-OTOP模型包含的目标函数以及约束条件是本发明能够获得最优规划结果的重要依据，其可以通过多种方式来设置，下面对其中一种可选的设置方式进行详细说明。
[0033] 首先，该模型的目的是为了获得候选农田的最大总收益，能够影响农田总收益的因素可以包括：时间窗因素、无人机自身因素、农田因素、无人机的飞行路径因素。下面对各个因素以及根据各个因素构建的MUAV-TW-VP-OTOP模型进行详细说明。
[0034] (一)无人机
[0035] 用U表示执行待喷洒任务的NU架同构无人机的集合 且每架无人机只能携带一种农药；在飞行过程中，所有无人机均具有相同的最小转弯半径RU和飞行速度V，但由于本发明中使用的是四旋翼无人机，四旋翼无人机的特点就在于可以拐直角弯，不存在转弯弧度的问题，因此无需考虑最小转弯半径这一因素。此外，各个无人机且均携带喷洒半径为RD的喷头。
[0036] 考虑无人机执行农药喷洒任务的特点，本发明做出以下假设：
[0037] (1)无人机均具有自动避障的能力，可在面临碰撞的情形下，采用自主规避的控制策略，由此而产生的路径偏差相对于总的飞行路径长度也很小，可忽略不计；
[0038] (2)无人机均以相同的巡航速度和巡航高度飞行，从而不考虑该因素对喷洒效果的影响；
[0039] (3)无人机飞行过程中不考虑外界环境对无人机飞行轨迹的影响；
[0040] (4)无人机飞行过程中能够携带执行任务所需的农药，但是燃料有限；
[0041] (二)农田
[0042] 设A0, 分别为无人机的起点和终点，本发明中对于每架无人机来说其起点和终点为同一点，也即从哪里起飞就从哪里降落。 表示待喷洒农药的NA块农田。其中，农田的形状近似看作是矩形，且农田Ai是顶点坐标为(Ai1,Ai2,Ai3,Ai4)，面积为SQi的矩形；无人机的起点、终点以及农田区域的集合为 当无人机Uu对农田
Ai覆盖式喷洒农药时，无人机飞入农田的进入点为Iniu，飞离农田的离开点为Outiu，并假设该无人机必须完全喷洒整块农田后才能离开。与此同时，每一个农田最多只能被喷洒一次农药。
[0043] (三)飞行路径
[0044] 在无人机执行农业航空作业任务的过程中，不仅需要在农田内部通过覆盖式喷洒农药完成作业任务，而且还需要在不同农田间飞行以实现任务之间的切换，由此而产生了两种类型的飞行路径，即农田内和农田间的飞行路径。
[0045] 对于本发明所使用的四旋翼无人机来说，由于其无需考虑最小转弯半径的问题，因此可以采用基于欧氏距离路径在农田间以及农田内进行飞行的方式进行飞行。其中，在农田内部可以采用平行于矩形农田的长边或平行于矩形农田的短边的方式飞行。其中，这里的进入点可以为与农田顶点的距离为无人机喷洒半径的点。如图2所示，对于图2中的矩形农田来说，无人机的进入点可以为矩形农田四个边上标注的八个点RD1-RD8，RD1-RD8与其最近的农田顶点的坐标为执行作业任务的四旋翼无人机的喷洒半径，例如图2中无人机从RD6进入到农田中。对于在农田间的飞行同样采用基于欧氏距离路径进行飞行，如图3所示，无人机可以从RD6进入到农田Ai中，其在农田Ai中的飞行轨迹可以如图3中的粗线所示，当飞行至RD6时无人机驶离农田Ai，之后经过一段直线飞行便从下一块农田Aj的RD7进入下一块农田Aj，从而完成农田间的飞行。
[0046] (四)环境温度
[0047] 由于喷洒设备、喷洒方式等软硬件条件已经确定，在固定的一个时间窗内无人机执行农业航空作业任务主要受到环境温度的影响，环境温度的变化将对任务的收益产生直接作用。
[0048] 本发明将无人机对农田喷洒农药的药效作为其执行任务的收益，则无人机Uu在时间窗内对面积为SQi的农田Ai完成药物喷洒任务后的总收益可以定义为：
[0049]
[0050] 其中，Pi(t)为无人机对农田Ai喷洒农药的药效变化函数，它受到药物类型的影响，随着时间的变化可能呈现出凹函数、凸函数、正态分布、线性递减等多种函数关系。
[0051] (五)模型设置
[0052] 基于上述四个方面因素的设置，可以得到本发明所提供的MUAV-TW-VP-OTOP模型如下所示，其目标函数可以为：
[0053]
[0054] 其中，
[0055]
[0056] 预设约束条件可以为：
[0057]
[0058]
[0059]
[0060]
[0061]
[0062]
[0063]
[0064] 其中，Nu表示无人机Uu的个数；NA表示农田Ai的个数；A0, 表示所有无人机的起始点和终点，所述起始点与终点为同一点，SPi表示完成农田Ai的喷洒任务所获得的收益；SQi表示农田Ai的面积；Pi(t)为连续变化函数，其变化函数取决于农田喷洒农药的类型；M的值为预设值；siu表示无人机Uu对农田Ai开始喷洒农药的时间，sju表示无人机Uu对农田Aj开始喷洒农药的时间；Oiu表示无人机Uu对农田Ai可以喷洒农药的开始时间；Ciu表示无人机Uu对农田Ai可以喷洒农药的结束时间；tiu表示无人机Uu对农田Ai按照预设的飞行方式执行任务的时间；tiju表示无人机Uu对农田Ai,Aj之间按照预设的飞行方式飞行的时间；Eu表示无人机Uu的最大飞行时长限制；xiu表示无人机Uu对农田Ai完成药物喷洒任务的情况，若xiu＝1，则表示完成药物喷洒任务，否则无人机Uu没有对农田Ai执行任务；yiju表示无人机Uu是否经过农田Ai,Aj，若yiju＝1表示无人机Uu经过农田Ai,Aj，否则该无人机没有经过农田Ai,Aj。
[0065] 此外，这里的目标函数式(2)是使得完成喷洒农药任务后农田的总收益最大，其中药效变化函数Pi(t)可以为多种函数关系。约束式(4)是保证在所有的路线，即所有的无人机起点为A0，终点为 在本发明起点与终点的坐标相同，且路线的个数与无人机的数量相同。约束式(5)使得每条边要具有连接性。约束式(6)是为了说明访问农田时需要服务时间。约束式(7)确保每块农田最多只被访问一次。约束式(8)是确保无人机执行任务时必须在时间窗内，且从起始点到农田之间的时间可以不在时间窗内。约束(9)为无人机飞行时长的限制。约束式(10)是目标、路径等变量的定义。
[0066] 从而可以基于这一模型及定义的约束获取本次任务的最大化收益。
[0067] 在具体实施时，上述方法步骤中的步骤S102的一种具体的实施方式可以为：
[0068] S1021、对无人机的标识信息、无人机的数量、每条线路中的无人机的起始时间、农田的位置信息以及每架无人机进入农田时的进入点进行采用全信息编码方式进行编码，随机生成多条染色体。其中，染色体的第一行为农田的标识信息的随机全排列，染色体的第二行为所有无人机的标识信息的随机组合，染色体的第三行为进入点的随机组合，染色体的第四行为无人机的起始时间的随机组合，所述染色体的第四行为所述无人机路线中访问第一块农田开始时间的随机组合。
[0069] 在此基础上，上述方法步骤中的步骤S103的一种具体的实施方式可以为：
[0070] S1031、根据初始解集生成预设规模的初始父代种群；
[0071] S1032、采用轮盘赌方法将当前的父代种群中的任意两个染色体进行交叉并迭代此交叉步骤，满足迭代次数后结束此交叉步骤得到第一子代种群，交叉的步骤具体包括：
[0072] 随机选择第一染色体中的交叉位置，然后寻找第二染色体中与第一染色体交叉位置的第一行相同的基因；将第一染色体与第二染色体的交叉位置基因进行替换，然后将与交叉位置基因第二行相同的基因处第四行也替换为交叉位置基因第四行的开始时间，从而得到第三染色体以及第四染色体；判断所述第三染色体以及第四染色体是否满足所述预设约束条件；若满足，则替换所述父代种群中的第一染色体以及第二染色体；若不满足，则结束当前操作；
[0073] S1033、采用轮盘赌方法将所述第一子代种群中的任意一个第五染色体进行个体变异，并判断变异后的第五染色体是否满足所述预设约束条件；若满足，则替换变异的第五染色体；若不满足，则结束当前操作，并迭代此变异步骤，满足迭代次数后结束此变异步骤得到第二子代种群；
[0074] 其中，所述个体变异的步骤具体包括：在判断获知第五染色体的第二行发生过变异时，确定其变异的位置，并将随机生成的无人机标识信息替换原变异位置处的无人机标识信息；在判断获知第五染色体的第三行发生过变异时，确定其变异的位置，并将随机生成的进入点替换原变异位置处的进入点；在判断获知第五染色体的第四行发生变异时，确定变异位置，并将随机生成的时间窗之间的时间替换与变异位置第二行相同的基因处第四行的开始时间；
[0075] S1034、选取所述第二子代种群中的最优解，并将所述第二子代种群与所述父代种群按照预设比例组合形成新的父代种群；
[0076] 判断当前S1032、S1033、S1034整体循环迭代的次数是否达到预设值；若否，则返回S1032，并将新的父代种群作为当前的父代种群执行步骤二；若是，则执行S1035；
[0077] S1035、结束迭代，并将最终获得的最优解作为本次作业的任务分配和航迹规划结果。
[0078] 为便于理解本发明提供的方法的完整流程，下面对S102以及S103中的各个具体步骤进行详细说明。
[0079] 本发明提供的方法的总体思路为：对于本发明所要解决的任务分配以及航迹规划问题来说，每一个可行解(也即满足预设模型约束的解)可以表示为一条染色体。可行解种群(也即初始父代种群)可以由多条染色体组成，其规模根据实际情况自行定义。在得到这样的初始父代种群后，进而可以将初始父代种群通过染色体的交叉、变异来进行更新种群，形成新的子代种群。其中，这里的交叉是指两条父代染色体根据交叉概率形成新的两条子代染色体，这里的变异是指一条染色体根据变异概率形成一条新的染色体。这一交叉变异更新的循环过程不断迭代，最终在迭代次数达到预设值时选出当前最优的子代染色体，该子代染色体即为满足模型约束的能够使得目标函数获得最大化收益的最优解，该最优解即为本发明最终所需的任务分配以及航迹规划结果。
[0080] 而在这一过程中，涉及到对于遗传算法中的编码、交叉、变异、以及适应度的函数规则的设置以使得设置之后的遗传算法能够应用于对预设模型的求解获得最优解中。可以理解的是，遗传算法中的各个函数的设置可以有多种方式来实现，下面对一种可选的函数设置方式进行具体说明。
[0081] (1)编码
[0082] 染色体的编码对于染色体的求解是至关重要的，本发明中的编码包括对于目标区域农田、无人机、目标区域进入点、每条路线中无人机访问第一块农田的时间的编码。其中，目标区域也即候选农田属于集合{1,2,...NA}，无人机属于集合{0,1,...NU}，目标区域农田的进入点属于集合{1,2,...8}，每条路线中访问第一块农田的时间属于时间窗范围内时间即可。
[0083] 表1示出了一条编码之后的染色体每一行的内容。其中，染色体第一行是农田的信息也即农田的标识信息，第二行是执行任务的无人机的标识信息，第三行是无人机对目标农田执行任务时的进入点(进入点标号对应于图2所示的农田RD1-RD8)，第四行是每条路线中无人机访问第一块农田的时间。整条染色体表示有两条路线，分别是无人机U1和无人机U2所代表的路线，其中，无人机U1在9.926时刻进入目标区域A3，并从目标区域A3的RD7点进入完成任务，然后离开区域目标A3从A4的RD8点进入完成任务，最后返回起始点；无人机U2在9.071时刻进入目标区域A5，并从目标区域A5的RD5点进入完成任务，然后离开区域目标A5从A2的RD6点进入完成任务，最后返回起始点，而目标A1没有被访问。
[0084] 表1染色体:NA＝5,NU＝2
[0085]
[0086] (2)适应度函数和选择
[0087] 一个染色体的适应度是所有被访问目标区域的总收益，这是与目标区域的收益变化函数有关，即与被访问区域的开始和结束时间、区域的面积有关。适应度可以通过公式(2)获得，也就是说将这里的适应度设置为本发明中所述的预设模型的目标函数，从而可以基于遗传算法对目标函数进行求解。
[0088] (3)交叉
[0089] 交叉是为了继承父代中比较优良的基因，从而获得更优的子代。本发明选择的交叉方式是基本的单点交叉，但也有一些异同。首先，先随机选择交叉位置进行基本的单点交叉，然后把两个染色体中与交叉位置第二行相同的基因的第四行开始时间进行全部交换。例如在图4中，两条父代染色体先在父代A中随机选择进行交叉的位置，然后找到父代B相同目标区域位置进行交换，然后进行交换时间，从而得到两条新的子代染色体A，B。
[0090] (4)变异
[0091] 遗传算法中变异是为了防止遗传算法陷入局部最优，使其存在基因突变的可能，变异可能是一个基因也可能是多个基因，本文染色体变异主要有以下几种情况：无人机的变异，目标区域的进入点变异，每条路线中无人机访问第一块农田的时间变异，目标区域不进行变异。如图5所示，染色体A进行了无人机的变异，进入点的变异和无人机开始时间的变异，且开始时间变异时找到与变异位置第二行相同的基因，并变异第四行为新的变异时间。
[0092] 由于上述交叉变异过程的不断地循环迭代进行，使得父代种群被不断更新，从而生成更多的新的种群。可以理解的是，这一迭代循环的过程是可以无限进行下去的，但这样无法获得一个最终的结果。因此本发明在每次迭代结束后会判断当前累计的迭代次数是否已经达到了迭代次数阈值，其中这一阈值可以根据实际情况自行设置。若判断当前未达到迭代次数阈值，则需要继续进行迭代过程；若判断当前达到了迭代次数阈值，则认为此时的迭代次数已经足够，当前的最优解即可以作为本次作业的任务分配和航迹规划结果。进而还可以将该结果分配至对应的多架四旋翼无人机，以使得该多架为人机可以根据这一结果执行本次作业任务，达到本次作业的目的且获得农田的最大化收益。
[0093] 下面以一个具体的实例，详细说明如何根据上述函数设置利用遗传算法对MUAV-TW-VP-OTOP模型的求解，从而获得最终的飞行分配结果。
[0094] 具体来说，在MATLAB 2013的环境中实现了所述遗传算法对MUAV-TW-VP-OTOP模型的求解，并进行了实验，且实验结果均为同一实验运行10次结果的平均值。
[0095] 假设有两架无人机在时间窗[9,15]内对六块农田区域喷洒农药，并使用所述遗传算法获取分配方案，其中取所述遗传算法的交叉概率为0.9，变异概率为0.5，种群规模为500，迭代次数为100。实验过程中涉及到的具体参数描述如下：
[0096] (1)无人机
[0097] 在本文的实验中无人机的具体配置如表2所示，无人机速度为4m/s，最大喷洒半径为5m，最大续航时间为2600s。
[0098] 表2无人机基本参数配置表
[0099]无人机参数 A0\AN+1 V RD Eu
无人机信息 (0,0) 4m/s 5m 2600s
[0100] (2)农田区域
[0101] 此农田区域有六块待喷洒农田，具体如图6所示。具体坐标如表3所示。
[0102] 表3农田坐标信息
[0103]
[0104]
[0105] (3)农药类型
[0106] 在实验中，选择喷洒农药M1，其药效的函数随着时间呈现凸函数变化，其变化函数为：
[0107] Pi(t)＝-0.004t2+0.0984t+0.424. (11)
[0108] 通过所述遗传算法求解上述配置环境下六块农田的平均总收益为15.437764，通过十次计算结果得知收益是稳定的，具体如表4所示。
[0109] 表4农田收益表
[0110]
[0111] 通过所述遗传算法可以获得一个分配方案解集，且一种求解的分配方案如表5所示，其中，无人机U1在12点1分23秒首先从RD3点进入农田2，再从RD8点进入农田1，然后从RD3点进入农田3，最后返回到起点A0；无人机U2在9点9秒首先从RD8点进入农田4，再从RD5点进入农田6，最后返回起点A0；农田5没有被喷洒农药。
[0112] 表5分配方案表
[0113]5 2 1 4 3 6
0 1 1 2 1 2
3 3 8 8 3 5
7.185868 12.02568 12.02568 12.00237 12.02568 12.00237
[0114] 第二方面，本发明的一个实施例又提供一种无人机航空作业任务分配装置，如图7所示，当多架多旋翼无人机在同一时间对多块候选农田执行作业任务时，所述装置包括：
[0115] 信息获取单元201，用于获取执行本次任务的一个时间窗、多旋翼无人机的信息、待喷洒农药信息、以及所述多块候选农田的农田信息；
[0116] 初始分配方案生成单元202，用于对所述时间窗、无人机的信息、待喷洒农药信息以及所述农田信息进行编码，随机生成多条染色体；在所述随机生成的多条染色体中，筛选出满足预设的MUAV-TW-VP-OTOP模型所定义的预设约束条件的染色体，构建所述MUAV-TW-VP-OTOP模型的初始解集；其中，所述MUAV-TW-VP-OTOP模型为使得按预设的飞行方式飞行的所述多架多旋翼无人机在此次作业任务中获得最大总收益的目标函数；所述预设约束包括每架多旋翼无人机所飞行时长约束以及每块农田时间窗约束；
[0117] 最优解计算单元203，用于基于预设的遗传算法对所述初始解集进行不断交叉和变异，直至满足迭代次数的约束后结束交叉和变异，并在经过变异后的解集中选择使得所述模型获得最大总收益的最优解，并将所述最优解作为本次作业的任务分配和航迹规划结果。
[0118] 在具体实施时，所述目标函数为：
[0119]
[0120] 其中，
[0121]
[0122] 所述预设约束条件为：
[0123]
[0124]
[0125]
[0126]
[0127]
[0128]
[0129]
[0130] 其中，Nu表示无人机Uu的个数；NA表示农田Ai的个数；A0, 表示所有无人机的起始点和终点，所述起始点与终点为同一点，SPi表示完成农田Ai的喷洒任务所获得的收益；SQi表示农田Ai的面积；Pi(t)为连续变化函数，其变化函数取决于农田喷洒农药的类型；M的值为预设值；siu表示无人机Uu对农田Ai开始喷洒农药的时间，sju表示无人机Uu对农田Aj开始喷洒农药的时间；Oiu表示无人机Uu对农田Ai可以喷洒农药的开始时间；Ciu表示无人机Uu对农田Ai可以喷洒农药的结束时间；tiu表示无人机Uu对农田Ai按照预设的飞行方式执行任务的时间；tiju表示无人机Uu对农田Ai,Aj之间按照预设的飞行方式飞行的时间；Eu表示无人机Uu的最大飞行时长限制；xiu表示无人机Uu对农田Ai完成药物喷洒任务的情况，若xiu＝1，则表示完成药物喷洒任务，否则无人机Uu没有对农田Ai执行任务；yiju表示无人机Uu是否经过农田Ai,Aj，若yiju＝1表示无人机Uu经过农田Ai,Aj，否则该无人机没有经过农田Ai,Aj。
[0131] 在具体实施时，所述农田为矩形的农田，所述预设的飞行方式为基于欧氏距离路径在农田间以及农田内进行飞行的方式；
[0132] 其中，在农田内部采用平行于矩形农田短边或平行于矩形农田长边的方式飞行，且以垂直于农田第一边的方向从第一边上的第一进入点进入农田，所述第一进入点与农田顶点的距离为无人机喷洒半径。
[0133] 在具体实施时，所述初始分配方案生成单元202，进一步用于：
[0134] 对所述无人机的标识信息、所述无人机的数量、每条线路中的无人机的起始时间、所述农田的位置信息以及每架无人机进入农田时的进入点进行采用全信息编码方式进行编码，随机生成多条染色体；
[0135] 其中，所述染色体的第一行为所述农田的标识信息的随机全排列，所述染色体的第二行为所有无人机的标识信息的随机组合，所述染色体的第三行为所述进入点的随机组合，所述染色体的第四行为所述无人机的起始时间的随机组合。
[0136] 在具体实施时，所述最优解计算单元203，进一步用于执行第一方面所述的步骤一至步骤五的方法。
[0137] 由于本实施例所介绍的无人机航空作业任务分配的装置为可以执行本发明实施例中的无人机航空作业任务分配的方法的装置，故而基于本发明实施例中所介绍的无人机航空作业任务分配的方法，本领域所属技术人员能够了解本实施例的无人机航空作业任务分配的装置的具体实施方式以及其各种变化形式，所以在此对于该无人机航空作业任务分配的装置如何实现本发明实施例中的无人机航空作业任务分配的方法不再详细介绍。只要本领域所属技术人员实施本发明实施例中无人机航空作业任务分配的方法所采用的装置，都属于本申请所欲保护的范围。
[0138] 在此处所提供的说明书中，说明了大量具体细节。然而，能够理解，本发明的实施例可以在没有这些具体细节的情况下实践。在一些实例中，并未详细示出公知的方法、结构和技术，以便不模糊对本说明书的理解。
[0139] 类似地，应当理解，为了精简本公开并帮助理解各个发明方面中的一个或多个，在上面对本发明的示例性实施例的描述中，本发明的各个特征有时被一起分组到单个实施例、图、或者对其的描述中。然而，并不应将该公开的方法解释成反映如下意图：即所要求保护的本发明要求比在每个权利要求中所明确记载的特征更多的特征。更确切地说，如下面的权利要求书所反映的那样，发明方面在于少于前面公开的单个实施例的所有特征。因此，遵循具体实施方式的权利要求书由此明确地并入该具体实施方式，其中每个权利要求本身都作为本发明的单独实施例。
[0140] 本领域那些技术人员可以理解，可以对实施例中的设备中的模块进行自适应性地改变并且把它们设置在与该实施例不同的一个或多个设备中。可以把实施例中的模块或单元或组件组合成一个模块或单元或组件，以及此外可以把它们分成多个子模块或子单元或子组件。除了这样的特征和/或过程或者单元中的至少一些是相互排斥之外，可以采用任何组合对本说明书(包括伴随的权利要求、摘要和附图)中公开的所有特征以及如此公开的任何方法或者设备的所有过程或单元进行组合。除非另外明确陈述，本说明书(包括伴随的权利要求、摘要和附图)中公开的每个特征可以由提供相同、等同或相似目的替代特征来代替。
[0141] 此外，本领域的技术人员能够理解，尽管在此的一些实施例包括其它实施例中所包括的某些特征而不是其它特征，但是不同实施例的特征的组合意味着处于本发明的范围之内并且形成不同的实施例。例如，在下面的权利要求书中，所要求保护的实施例的任意之一都可以以任意的组合方式来使用。
[0142] 本发明的某些部件实施例可以以硬件实现，或者以在一个或者多个处理器上运行的软件模块实现，或者以它们的组合实现。本领域的技术人员应当理解，可以在实践中使用微处理器或者数字信号处理器(DSP)来实现根据本发明实施例的网关、代理服务器、系统中的一些或者全部部件的一些或者全部功能。本发明还可以实现为用于执行这里所描述的方法的一部分或者全部的设备或者装置程序(例如，计算机程序和计算机程序产品)。这样的实现本发明的程序可以存储在计算机可读介质上，或者可以具有一个或者多个信号的形式。这样的信号可以从因特网网站上下载得到，或者在载体信号上提供，或者以任何其他形式提供。
[0143] 应该注意的是上述实施例对本发明进行说明而不是对本发明进行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下可设计出替换实施例。在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排除存在多个这样的元件。本发明可以借助于包括有若干不同元件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。
