CN107169608B - 多无人机执行多任务的分配方法及装置 - Google Patents

Abstract

本发明实施例公开了一种多无人机执行多任务的分配方法及装置。方法包括：获取多个无人机和目标点的位置信息，以及无人机和风场的运动参数；根据位置信息和预设遗传算法构建初始种群，初始种群中的每个染色体均包括无人机数量的欧式飞行路径；根据初始种群、运动参数确定无人机飞行状态和完成欧式路径航迹段的航行时间，根据航行时间和MUAV‑VS‑EVRP模型获取各染色体对应的所有无人机完成任务时间；基于遗传算法，对种群中染色体进行交叉、变异，在达到预定迭代次数后，选取无人机完成任务时间最短的染色体作为无人机的任务分配方案。本发明实施例将无人机航迹规划问题与无人机实际飞行环境相结合，使规划得到的最优飞行路径方案优于无人机速度恒定的方案。

Description

多无人机执行多任务的分配方法及装置

技术领域

本发明实施例涉及无人机技术领域，具体涉及一种多无人机执行多任务的分配方法及装置。

背景技术

当前，无人机UAV(Unmanned Aerial Vehicle)在军民领域有着广泛的应用，可完成目标侦察、目标跟踪、情报收集、震后救援和地质勘探等多种类型任务。例如在多架UAV协同侦察目标时，既要最合理地为每架UAV分配其所需侦察的目标，还要为其规划最优的飞行航迹。该问题是一个受多因素约束的任务分配与航迹规划联合优化问题，也是非确定性问题。

随着UAV研究的深入，环境因素被逐渐纳入问题的研究，特别是UAV任务分配、航迹规划和飞行控制等问题中，在环境因素的影响下如何降低耗能、控制UAV的飞行状态从而使UAV消耗最少的燃料执行最多的任务、具备更好的任务执行状态和更高的安全性是当前UAV研究的主要工作。当前常用于解决UAV任务分配与任务规划问题的模型有：TSP模型，TOP模型和VRP模型，其中，TSP模型是在只有单一旅行者的条件下，使得旅行者通过所有给定的目标点之后，从而使其路径成本最小的模型；TOP模型是在存在多个成员的条件下，使得每个成员尽可能访问更多的目标点，从而使得所有成员的总收益最大的模型；VRP模型是在车辆数量固定的条件下，使得车辆访问一定数量目标点，且在此过程中每个目标点只能被访问一次，最终使得UAV航行的总距离或总时间最短的模型。

在实现本发明实施例的过程中，发明人发现现有的技术方案在实际操作中，一般是假设模型中在恒定时间内无人机的速度是恒定的。然而这个假设显然是不现实的，导致模型无法精确模拟出无人机的实际运动状态，进而无法进行最优的航迹规划。

发明内容

本发明实施例的一个目的是解决现有技术由于在进行航迹规划是设定无人机的速度是恒定的，导致模型无法精确模拟出无人机的实际运动状态，进而无法给出的最优的航迹规划。

本发明实施例提出了一种多无人机执行多任务的分配方法，包括：

S1、获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

S2、根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人机数量的欧式飞行路径且各条欧式飞行路径均由不同无人机完成；

S3、根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间；

S4、基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案。

可选的，根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群包括：

根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；

所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

可选的，根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间包括：

每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；

根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的所有无人机完成任务时间；

根据每个航迹段对应的航行时间获取所述染色体对应的所有无人机完成任务时间。

可选的，根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间包括：

采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，_Tk为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，β_a ⁱ表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标。

可选的，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间包括：

根据MUAV-VS-EVRP模型获取航行时间：

其约束条件为：

其中.

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。

可选的，基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案包括：

步骤1、使用所述编码方式生成初始解，并生成预定规模的初始种群并根据种群中每个染色体对应的所有无人机完成任务时间计算其适应度；

步骤2、使用轮盘赌方法选择父代种群中的两个个体(A,B)进行交叉，交叉规则为先随机选择个体A中交叉位置，然后查找个体B中与个体A交叉位置第一行相同的基因，将染色体A和B中交叉位置基因进行替换得到新的染色体C和D，判断染色体C和D是否满足MUAV-VS-EVRP模型的约束条件，若满足则利用染色体C和D替换种群中染色体A和B，否则对不满足约束条件的染色体进行约束校验，即检验染色体A和B中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中染色体A和B，然后不断迭代更新步骤1种群，得到新的子代种群；

步骤3、使用轮盘赌方法选择步骤2种群中一条染色体进行变异，对所述染色体进行变异的方式为下述变异方式中的至少一种，包括：对染色体第一行进行目标点变异；对染色体第二行进行无人机变异；

整个染色体变异的步骤包括：首先，若染色体的第一行顺序变异，则随机选取当前染色体的两个基因位并交换对应基因位的目标点编码；再选择第二行是否变异及变异位置，若变异则随机生成变异的有异于当前位置无人机编码的值替换原值，并且在变异后判断染色体是否满足MUAV-VS-EVRP模型的约束条件，若满足则替换种群中染色体，否则对不满足约束条件的染色体进行约束校验，即检验染色体中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中的染色体并不断迭代更新步骤2种群，得到新的子代种群；

步骤4、计算子代种群适应度并选取本次迭代中所有解中的最优解；

步骤5、判断当前的迭代次数是否达到预设值，若判断否，则对步骤3中的子代种群和父代种群按照一定比例组合形成新的父代种群返回步骤2；若判断为是，则结束迭代，将最终获得的最优解作为无人机的任务分配结果。

本发明实施例提出了一种多无人机执行多任务的分配装置，包括：

获取模块，用于获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

第一处理模块，用于根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人机数量的欧式飞行路径各条欧式飞行路径均由不同无人机完成；

第二处理模块，用于根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间；

第三处理模块，用于基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案。

可选的，所述第一处理模块，用于根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

可选的，所述第二处理模块，用于每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间；根据每个航迹段对应的航行时间获取所述染色体对应的所有无人机任务完成时间。

可选的，所述第二处理模块，用于根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间包括：

采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，T_k为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，β_a ⁱ表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标。

由上述技术方案可知，本发明实施例提出的一种多无人机访问多目标点的航迹规划方法及装置首先通过对风场和无人机的运动参数进行分析，获取无人机在风场中的实际飞行状态，然后基于实际飞行状态进行飞行路径的规划，与现有技术中设定无人机速度恒定的方案相比，能根据不确定环境中风场的状态精确计算无人机在所有可能飞行路径上的航行时间，进而选择出最优的飞行路径。

附图说明

通过参考附图会更加清楚的理解本发明的特征和优点，附图是示意性的而不应理解为对本发明进行任何限制，在附图中：

图1示出了本发明一实施例提供的一种多无人机执行多任务的分配方法的流程示意图；

图2示出了本发明一实施例提供的计算Dubins飞行路径的航行时间的流程示意图；

图3示出了本发明一实施例提供的遗传算法的流程示意图；

图4a-图4c示出了本发明一实施例提供遗传算法中的算子的示意图；

图5示出了本发明一实施例提供的风向示意图；

图6示出了本发明一实施例提供的速度矢量关系示意图；

图7示出了本发明一实施例提供的UAV由A飞往C点受风场影响的分析示意图；

图8示出了本发明一实施例提供的对飞行路径进行分段的示意图；

图9示出了本发明一实施例提供的一种多无人机执行多任务的分配装置的结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。

图1示出了本发明一实施例提供的一种多无人机访问多目标点的航迹规划的流程示意图，参见图1，该方法可由处理器实现，具体包括如下步骤：

110、获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

需要说明的是，在进行任务分配和航迹规划之前，技术人员可设定或者根据实际情况测出无人机和多个目标点的位置信息，然后将其输入至处理器中。

另外，无人机的运动参数可以是技术人员根据实际飞行需要设定的，风场的运动参数可以是技术人员测量得出或者是根据实际情况设定的。

120、根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人机数量的欧式飞行路径且各条欧式飞行路径均由不同无人机完成；

130、根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间；

140、基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案。

不难理解的是，每次交叉、变异的迭代可能都有新的个体的出现，然后基于步骤130对新的染色体进行的航行时间的计算，因此，每个欧式飞行路径对应一个航行时间。

可见，本实施例首先通过对风场和无人机的运动参数进行分析，获取无人机在风场中的实际飞行状态，然后基于实际飞行状态进行飞行路径的规划，与现有技术相比，本实施例将无人机航迹规划问题与无人机实际飞行环境相结合，使规划得到的最优飞行路径方案优于无人机速度恒定的方案，进而达到能精确计算无人机在所有可能飞行路径上的航行时间，进而选择出最优的飞行路径。

下面对本发明实施例中的各步骤进行详细说明：

首先，对步骤120进行详细说明：

根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；

所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

然后，参见图2，下面对步骤130进行详细说明：

210、每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；

220、根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间；

230、根据每个航迹段对应的航行时间获取所述染色体对应的所有无人机完成任务时间。

其中，步骤220包括：

采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，T_k为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，

表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标。

另外，计算初始种群中染色体对应的无人机完成任务时间的步骤包括：

根据MUAV-VS-EVRP模型获取无人机完成任务时间：

其约束条件为：

其中.

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。

下面对步骤140进行详细说明：

步骤1、使用所述编码方式生成初始解，并生成预定规模的初始种群并根据种群中每个染色体对应的无人机完成任务时间计算其适应度；

步骤2、使用轮盘赌方法选择父代种群中的两个个体(A,B)进行交叉，交叉规则为先随机选择个体A中交叉位置，然后查找个体B中与个体A交叉位置第一行相同的基因，将染色体A和B中交叉位置基因进行替换得到新的染色体C和D，判断染色体C和D是否满足MUAV-VS-EVRP模型的约束条件，若满足则利用染色体C和D替换种群中染色体A和B，否则对不满足约束条件的染色体进行约束校验，生成满足约束条件的染色体替换种群中染色体A和B，然后不断迭代更新步骤1种群，得到新的子代种群；

步骤3、使用轮盘赌方法选择步骤2种群中一条染色体进行变异，对所述染色体进行变异的方式为下述变异方式中的至少一种，包括：对染色体第一行进行目标点变异；对染色体第二行进行无人机变异；

整个染色体变异的步骤包括：首先，若染色体的第一行顺序变异，则随机选取当前染色体的两个基因位并交换对应基因位的目标点编码；再选择第二行是否变异及变异位置，若变异则随机生成变异的有异于当前位置无人机编码的值替换原值，并且在变异后判断染色体是否满足MUAV-VS-EVRP模型的约束条件，若满足则替换种群中染色体，否则对不满足约束条件的染色体进行约束校验，生成满足约束条件的染色体替换种群中的染色体并不断迭代更新步骤2种群，得到新的子代种群；

步骤4、计算子代种群适应度并选取本次迭代中所有解中的最优解；

步骤5、判断当前的迭代次数是否达到预设值，若判断否，则对步骤3中的子代种群和父代种群按照一定比例组合形成新的父代种群返回步骤2；若判断为是，则结束迭代，将最终获得的最优解作为无人机的任务分配结果。

下面参见图3对本发明的采用的遗传算法的原理进行详细说明：

1、开启；

2、基于技术人员的设定，生成包括指定数量染色体的种群，指定数量可具体为100个；

如图4a所示，染色体A表示在稳定风场下两个无人机UAV访问三个目标点的一种可行方案，即一号UAV从起始点S(0,0)出发，依次访问目标点3和目标点1后返回，二号UAV从起始点S(0,0)出发，访问目标点2后返回。编码中第二行代表UAV访问对应目标点的编码。

其中，染色体A包括两条欧式飞行路径且各条欧式飞行路径均由不同无人机一号和二号完成。

3、计算每个染色体的适应度；

需要说明的是，采用图1对应实施例中的步骤140的计算方法，计算无人机完成每个欧式飞行路径的航行时间，并基于无人机完成任务时间计算染色体的适应度，例如：无人机完成任务时间与适应度成反比关系。

不难理解的是，按照上述步骤2中的编码方式生成规定数量的种群后进行适应度的计算，本文发明中适应度的计算以目标函数为依据，其计算过程如下：

4、选择操作

根据J’通过轮盘赌的方法进行选择操作。

5、交叉操作

通过对父代染色体进行交叉，可以继承父代中比较优良的基因，获得更优的子代。针对MUAV-VS-EVRP问题本文针对当前的编码方式采用单点映射的方法，即随机产生父代染色体A交叉的基因位，在父代染色体B中找到同一目标点对应的基因位，交叉产生子染色体A、B，并对子染色体A、B进行约束条件校验。

参见图4b，有父代Parent A和Parent B，在Parent A上随机产生进行交叉的基因位为3，找到Parent B上对应相同目标点的基因位，经过交叉后产生子染色体OffSpring A和OffSpringB，对OffSpring A和OffSpringB进行约束校验，发现OffSpring A的无人机编码均表示同一无人机，不符合约束条件，因而再次对OffSpring A的无人机编码随机产生基因位与Parent A的第3基因位进行映射交叉，交叉后OffSpring A满足约束条件。

6、变异操作

变异是为了防止遗传算法陷入局部最优。针对求解sUav-DVS-VRP模型的遗传算法，染色体变异存在两种情况：目标点编码变异和航向角编码变异。根据变异概率，染色体中可发生多次变异也可不发生变异。其中，目标点编码变异采用双基因位变异，即在染色体的第一行随机产生两个进行变异的基因位，并将两个基因位上的值互换，该方法满足了模型中每个目标点只被访问一次的约束，保证了子染色体的可行性，航向角编码采用均匀变异。

变异操作举例：

如图4c所示，有父代Parent A，在Parent A上分别进行目标点变异和无人机变异，在进行变异前首先判断两种变异是否发生，在判断得到目标点变异发生时，随机选取进行编译的基因位，本例中选取的基因位是1和3，随后将被选取的基因位上的目标值进行交换，得到新的目标点访问顺序；在判断得到无人机变异发生时，随机选取进行变异的基因位，本例中选取的基因位是3，随机生成与当前无人机不同的无人机编码替换当前值，得到新的Parent A。对Parent A进行约束条件校验，发现Parent A的无人机编码均表示同一无人机，不符合约束条件，因而再次对Parent A的无人机编码进行变异操作，选取变异基因位是2，随机生成与当前无人机不同的无人机编码替换当前值，得到OffSpring A满足约束条件。

7、更新操作

8、选取最优分配方案

9、判断是否终止

10、获得最优分配方案

11、结束

需要说明的是，上述步骤与图1对应实施例中的部分步骤相对应，故，相似之处此处不再赘述，具体请查看图1对应的实施例中的相关内容。

下面结合上述的遗传算法对本发明的设计原理进行详细说明：

步骤一，为避免问题过于复杂，本发明采用区域固定风场进行风场建模，即在规定区域内，其风场的风速和风向是不变的。

已知区域的风场状态可表示为：

其中，V_w表示风场中的风速，β_w表示风向。

风速V_w是指风相对于地面单位时间内移动的距离，单位为m/s；风向β_w是指风吹来的方向，风向的测量单位一般用方位来表示，如陆地上，一般用16个方位表示，海上多用36个方位表示，而在高空则用角度表示，即把圆周分成360度，本文规定西风(W)是0度(即360度)，南风(S)是90度，东风(E)是180度，北风(N)是270度，如图5所示。

步骤二，配置UAV

用

表示四旋翼mUAV，mUAV在空中的配置定义为：

q＝(x,y,β_g) (4)

其中，

其中，

和

表示的是一架UAV在笛卡尔惯性参考系中的坐标；V_g表示UAV的地速β_g是指mUAV的航向角。

为使问题简化，本文提出以下关于UAV在执行任务过程中需满足的运动约束的假设：

(1)mUAV均为同构多旋翼UAV；

(2)不考虑mUAV的碰撞，认为mUAV具有避障功能；

(3)考虑mUAV均在固定的高度飞行；

(4)根据mUAV的飞行包线，mUAV在指定高度固定载荷下的飞行速度存在上下界，即

V_{a_min}和V_{a_max}分别表示在某高度下mUAV空速的最小值和最大值；

(5)多架mUAV均有出发点出发并在执行完成任务后返回出发点。

步骤三，计算UAV的实际飞行状态

考虑风影响的UAV实际速度定义为UAV的地速大小为V_g，此时UAV的航向角为β_g，UAV地速矢量

将不考虑风影响的UAV理论速度定义为UAV的空速大小为V_a，此时UAV的航向角为β_a，UAV空速矢量

UAV空速

地速

与风场中风速

的矢量关系如图6所示。

上述速度与角度关系为：

在无风时，

即UAV空速与地速相等。

下面结合图7进行实例说明：

UAV由S(0,0)飞往A(50,300)，空速为8m/s，该UAV所处的环境是风速为5m/s、风向为南风(Vw＝5m/s,βw＝90°)，根据式(7)可得到Uav在该过程中的空速和地速如表4-1所示。

表4-1四旋翼Uav在无风与南风环境下空速、地速对比表

	空速	地速
			南风环境	28.80km/h,35.5°	23.49km/h,80.5°
无风环境	28.80km/h,80.5°	28.80km/h,80.5°

步骤四，目标点配置

N_T个目标点的集合可表示为：

其中，集合中所有的目标点的位置和任务量均已知。在本发明中，每一个目标点上都可能有不同类型的任务需要被UAV执行，且在此过程中每架UAV只能执行一个目标点上的一个任务，即每个目标点都要被不同的UAV访问，每架UAV只能访问某个目标点一次。

步骤五，计算航行时间

在以飞行时间作为目标的UAV任务分配与航迹规划问题中，UAV的任务分配方案决定UAV访问目标点的顺序，根据UAV目标点访问顺序进行航迹规划，由航迹规划的结果计算UAV飞行时间进而由UAV飞行时间决定当前UAV任务分配与航迹规划方案是否优于已知方案。

由于Uav在两点间的航行轨迹是欧氏距离，因而Uav在两点间的航行方向固定，进而固定风场下Uav在两点间的地速是不变的，但固定风场下Uav由目标点出发在多个目标点场景中地速是变化的，其飞行时间计算如下：

其中，

表示Uav在T_j和T_k两点间的欧氏距离，Uav在两点间的地速

由公式(7)求得。

从而，可根据公式(8)计算mUAV的任务完成时间。

其中，

表示UAVU_i在T_j、T_k两点的航行时间；

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0；

J中j、k值取0表示UAV由起始点出发或路径末端指向起始点。

在求解过程中，还需满足以下几个约束条件：

上述条件保证所有的目标点都能被访问到且只能被访问一次。

上述条件保证由起始点出发UAV数量的UAV路线，并有UAV数量的UAV路径指向同一点。

上述条件在其它约束条件的基础上保证有UAV数量的路线且每一架UAV的路径是一条闭合的环，即UAV的航行轨迹是一条有序的路线，并最终回到起始点。

可见，基于上式可得到每个染色体对应的任务完成时间，进而从中选取出任务完成时间最短的任务分配方案。

下面对本发明进行具体实例的详细说明：

首先，所有的仿真实验均是在4G内存、3.4GHzCPU的硬件上、在MatlabR2014a的环境中运行的。具体说明如下：

UAV模型基于UAV的数学模型，其空速为8米/秒,两架UAV均从出发点S(0,0)起飞，在完成访问任务后返回点S(0,0)；风场环境是固定风场，即在一次实验过程中风速和风向都是不变的，并且为了保证UAV能够安全飞行，风速大小为5米/秒，风向取东，即180°，UAV需要访问的三个目标点坐标分别为：A(100,300)、B(200,150)、C(350,50)、D(500，150)、E(650,100)、F(400，200)、G(50，250)、H(250，350)和I(50，450)。

根据上述本发明提出的模型和算法，本文在东风风场环境和试验场景下进行实验，并得到各风场环境下无人机任务完成时间最短的任务分配如表3-1所示(参见图8)。

对于方法实施方式，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本发明实施方式并不受所描述的动作顺序的限制，因为依据本发明实施方式，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施方式均属于优选实施方式，所涉及的动作并不一定是本发明实施方式所必须的。

图9示出了本发明一实施例提供的一种无人机访问多目标点的航迹规划装置的结构示意图，参见图9，该装置包括：获取模块101、第一处理模块102、第二处理模块103以及第三处理模块104，其中：

获取模块101，用于获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

第一处理模块102，用于根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人及数量的欧式路径且各条欧式飞行路径均由不同无人机完成；

第二处理模块103，用于根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的任务完成时间；

第三处理模块104，用于基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取任务完成时间最短的染色体作为所述无人机的最优任务分配方案。

可见，本实施例首先通过对风场和无人机的运动参数进行分析，获取无人机在风场中的实际飞行状态，然后基于实际飞行状态进行飞行路径的规划，与现有技术相比，本实施例将无人机航迹规划问题与无人机实际飞行环境相结合，使规划得到的最优飞行路径方案优于无人机速度恒定的方案，进而达到能精确计算无人机在所有可能飞行路径上的航行时间，进而选择出最优的飞行路径。

下面对本装置的各功能模块进行详细说明：

第一处理模块102，用于根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

第二处理模块103，用于每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间；根据每个航迹段对应的航行时间获取所述染色体对应的任务完成时间。

进一步地，第二处理模块103，用于根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间包括：

采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，T_k为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，β_a ⁱ表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标。

另外，计算初始种群中染色体对应的无人机完成任务时间的步骤包括：

根据MUAV-VS-EVRP模型获取无人机完成任务时间：

其约束条件为：

其中.

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当UAVU_i经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。

第三处理模块104，用于执行以下步骤：步骤1、使用所述编码方式生成初始解，并生成预定规模的初始种群并根据种群中每个染色体对应的完成任务时间计算其适应度；步骤2、使用轮盘赌方法选择父代种群中的两个个体(A,B)进行交叉，交叉规则为先随机选择个体A中交叉位置，然后查找个体B中与个体A交叉位置第一行相同的基因，将染色体A和B中交叉位置基因进行替换得到新的染色体C和D，判断染色体C和D是否满足MUAV-VS-EVRP模型的约束条件，若满足则利用染色体C和D替换种群中染色体A和B，否则对不满足约束条件的染色体进行约束校验，即检验染色体A和B中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中染色体A和B，然后不断迭代更新步骤1种群，得到新的子代种群；步骤3、使用轮盘赌方法选择步骤2种群中一条染色体进行变异，对所述染色体进行变异的方式为下述变异方式中的至少一种，包括：对染色体第一行进行目标点变异；对染色体第二行进行无人机变异；整个染色体变异的步骤包括：首先，若染色体的第一行顺序变异，则随机选取当前染色体的两个基因位并交换对应基因位的目标点编码；再选择第二行是否变异及变异位置，若变异则随机生成变异的有异于当前位置无人机编码的值替换原值，并且在变异后判断染色体是否满足MUAV-VS-EVRP模型的约束条件，若满足则替换种群中染色体，否则对不满足约束条件的染色体进行约束校验，即检验染色体A和B中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中的染色体并不断迭代更新步骤2种群，得到新的子代种群；步骤4、计算子代种群适应度并选取本次迭代中所有解中的最优解；步骤5、判断当前的迭代次数是否达到预设值，若判断否，则对步骤3中的子代种群和父代种群按照一定比例组合形成新的父代种群返回步骤2；若判断为是，则结束迭代，将最终获得的最优解作为无人机的任务分配结果。

对于装置实施方式而言，由于其与方法实施方式基本相似，所以描述的比较简单，相关之处参见方法实施方式的部分说明即可。

应当注意的是，在本发明的装置的各个部件中，根据其要实现的功能而对其中的部件进行了逻辑划分，但是，本发明不受限于此，可以根据需要对各个部件进行重新划分或者组合。

本发明的各个部件实施方式可以以硬件实现，或者以在一个或者多个处理器上运行的软件模块实现，或者以它们的组合实现。本装置中，PC通过实现因特网对设备或者装置远程控制，精准的控制设备或者装置每个操作的步骤。本发明还可以实现为用于执行这里所描述的方法的一部分或者全部的设备或者装置程序(例如，计算机程序和计算机程序产品)。这样实现本发明的程序可以存储在计算机可读介质上，并且程序产生的文件或文档具有可统计性，产生数据报告和cpk报告等，能对功放进行批量测试并统计。应该注意的是上述实施方式对本发明进行说明而不是对本发明进行限制，并且本领域技术人员在不脱离所附权利要求的范围的情况下可设计出替换实施方式。在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的元件或步骤。位于元件之前的单词“一”或“一个”不排除存在多个这样的元件。本发明可以借助于包括有若干不同元件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (6)

1.一种多无人机执行多任务的分配方法，其特征在于，包括：

S1、获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

S2、根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人机数量的欧式飞行路径且各条欧式飞行路径均由不同无人机完成；

S3、根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间；

S4、基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案；

其中，S3包括：

每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；

根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间；

根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间；

所述根据每个航迹段对应的起始点的坐标以及终止点的坐标，结合风场参数确定无人机飞行状态，进而获取所述无人机完成所述航迹段的航行时间，包括：

采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，T_k为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，β_a ⁱ表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标；

所述根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间，包括：

根据MUAV-VS-EVRP模型获取所有无人机完成任务时间：

其约束条件为：

其中，T表示无人机目标点的集合，

T₀表示UAVs的起点，

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当

经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量。

2.根据权利要求1所述的方法，其特征在于，根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群包括：

根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；

所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

3.根据权利要求2所述方法，其特征在于，基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方案包括：

步骤1、使用所述编码方式生成初始解，并生成预定规模的初始种群并根据种群中每个染色体对应的无人机完成任务时间计算其适应度；

步骤2、使用轮盘赌方法选择父代种群中的两个个体A和B进行交叉，交叉规则为先随机选择个体A中交叉位置，然后查找个体B中与个体A交叉位置第一行相同的基因，将染色体A和B中交叉位置基因进行替换得到新的染色体C和D，判断染色体C和D是否满足MUAV-VS-EVRP模型的约束条件，若满足则利用染色体C和D替换种群中染色体A和B，否则对不满足约束条件的染色体进行约束校验，即检验染色体A和B中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中染色体A和B，然后不断迭代更新步骤1种群，得到新的子代种群；

步骤3、使用轮盘赌方法选择步骤2种群中一条染色体进行变异，对所述染色体进行变异的方式为下述变异方式中的至少一种，包括：对染色体第一行进行目标点变异；对染色体第二行进行无人机变异；

整个染色体变异的步骤包括：首先，若染色体的第一行顺序变异，则随机选取当前染色体的两个基因位并交换对应基因位的目标点编码；再选择第二行是否变异及变异位置，若变异则随机生成变异的有异于当前位置无人机编码的值替换原值，并且在变异后判断染色体是否满足MUAV-VS-EVRP模型的约束条件，若满足则替换种群中染色体，否则对不满足约束条件的染色体进行约束校验，即检验染色体中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中的染色体并不断迭代更新步骤2种群，得到新的子代种群；

步骤4、计算子代种群适应度并选取本次迭代中所有解中的最优解；

步骤5、判断当前的迭代次数是否达到预设值，若判断否，则对步骤3中的子代种群和父代种群按照一定比例组合形成新的父代种群返回步骤2；若判断为是，则结束迭代，将最终获得的最优解作为无人机的任务分配结果。

4.一种多无人机执行多任务的分配装置，其特征在于，包括：

获取模块，用于获取多个无人机和多个目标点的位置信息，以及所述多个无人机和风场的运动参数；

第一处理模块，用于根据所述多个无人机和所述多个目标点的位置信息和预设遗传算法，构建初始种群，所述初始种群中的每个染色体均包括无人机数量的欧式飞行路径且各条欧式飞行路径均由不同无人机完成；

第二处理模块，用于根据所述初始种群、无人机和风场的运动参数确定无人机飞行状态和无人机完成欧式飞行路径的航迹段的航行时间，根据所述航迹段的航行时间和MUAV-VS-EVRP模型获取初始种群中染色体对应的所有无人机完成任务时间，所述第二处理模块，用于每个染色体对应的欧式飞行路径根据其目标点被访问顺序将所述飞行路径分为多个航迹段；执行第一步骤和第二步骤；

所述第一步骤包括：采用以下公式计算获取无人机U_i由目标点T_j出发飞至目标点T_k航迹段的航行时间：

其中，U_i表示执行上述任务的无人机，U表示无人机集合，T_j为起始点，T_k为终止点，T表示目标点的集合,V_g ⁱ为无人机U_i在上述两目标点间的地速；

采用以下公式计算获取无人机U_i的地速：

其中，V_a ⁱ表示空速大小，β_a ⁱ表示空速航向角，V_g ⁱ表示地速的大小，β_g ⁱ表示地速航向角，

表示风速大小，

表示风向；

采用以下公式计算获取无人机U_i在T_j和T_k两点间的欧氏距离：

其中，X,Y分别表示对应目标点横、纵坐标；

所述第二步骤包括：

根据MUAV-VS-EVRP模型获取所有无人机完成任务时间：

其约束条件为：

其中，T表示无人机目标点的集合，

T₀表示UAVs的起点，

表示无人机由目标点T_j出发飞至目标点T_k的航行时间，

是一个二元决策变量，且

当

经T_j飞行至T_k时，则

的值为1，否则

的值为0，N_T表示目标点的数量,N_U表示无人机的数量；第三处理模块，用于基于遗传算法，对初始种群中染色体进行交叉、变异处理，并在达到预定迭代次数后，选取所有无人机完成任务时间最短的染色体作为所述无人机的最优任务分配方法。

5.根据权利要求4所述的装置，其特征在于，所述第一处理模块，用于根据预设遗传算法的编码方式进行染色体编码生成预定规模的初始种群；所述染色体由目标点信息和无人机信息组成；其中所述目标点属于集合

T₀表示UAVs的起点，N_T表示目标点数量，无人机属于集合

N_U表示无人机数量；所述染色体第一行为所述目标点的随机全排列，第二行为根据无人机集合为每个目标点随机选取对应的无人机，且需保证无人机集合中的无人机全部至少被选择一次。

6.根据权利要求5所述的装置，其特征在于，所述第三处理模块用于执行如下步骤：

步骤1、使用所述编码方式生成初始解，并生成预定规模的初始种群并根据种群中每个染色体对应的无人机完成任务时间计算其适应度；

步骤2、使用轮盘赌方法选择父代种群中的两个个体A和B进行交叉，交叉规则为先随机选择个体A中交叉位置，然后查找个体B中与个体A交叉位置第一行相同的基因，将染色体A和B中交叉位置基因进行替换得到新的染色体C和D，判断染色体C和D是否满足MUAV-VS-EVRP模型的约束条件，若满足则利用染色体C和D替换种群中染色体A和B，否则对不满足约束条件的染色体进行约束校验，即检验染色体A和B中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中染色体A和B，然后不断迭代更新步骤1种群，得到新的子代种群；

步骤3、使用轮盘赌方法选择步骤2种群中一条染色体进行变异，对所述染色体进行变异的方式为下述变异方式中的至少一种，包括：对染色体第一行进行目标点变异；对染色体第二行进行无人机变异；

整个染色体变异的步骤包括：首先，若染色体的第一行顺序变异，则随机选取当前染色体的两个基因位并交换对应基因位的目标点编码；再选择第二行是否变异及变异位置，若变异则随机生成变异的有异于当前位置无人机编码的值替换原值，并且在变异后判断染色体是否满足MUAV-VS-EVRP模型的约束条件，若满足则替换种群中染色体，否则对不满足约束条件的染色体进行约束校验，即检验染色体中无人机数量不满足约束条件时，针对不满足条件的染色体，随机选取一个基因位并判断该基因位上的无人机编码是否存在两个及两个以上，若是则将缺失的无人机编码放入该基因位，否则重新选取基因位，生成满足约束条件的染色体替换种群中的染色体并不断迭代更新步骤2种群，得到新的子代种群；

步骤4、计算子代种群适应度并选取本次迭代中所有解中的最优解；

步骤5、判断当前的迭代次数是否达到预设值，若判断否，则对步骤3中的子代种群和父代种群按照一定比例组合形成新的父代种群返回步骤2；若判断为是，则结束迭代，将最终获得的最优解作为无人机的任务分配结果。

Images