一种区域侦察任务规划方法、装置、计算机设备和介质

1.本技术涉及任务规划领域，特别是涉及一种多车多无人机协同区域侦察任务规划方法、装置、计算机设备和存储介质。


背景技术：

2.目前旋翼无人机在区域侦察中得到了广泛应用，旋翼无人机具有成本低、隐蔽性好、低空扫描精度高等优点，但同时普遍存在续航能力不佳的问题。单架无人机一次航程内所覆盖的区域范围十分有限，因此在较大范围的区域侦察任务中，无人机需要反复回到基站进行充电或更换电池，将造成极大的资源浪费，同时影响任务完成效率。在这种情况下，卡车与无人机协同的工作模式可有效节约无人机里程，扩大任务范围，提高任务完成的效率。
3.然而多车与多无人机协同系统的在区域覆盖中的应用有待进一步探究。目前关于车机协同区域覆盖问题的已有研究大多都是采取一辆卡车搭载多架无人机的模式，且每辆卡车搭载的无人机数量固定，而单车多机系统在更大区域的覆盖中具有一定的局限性，不能满足较高时效性的要求，无人机数量达到一定程度后，继续增加无人机对效率的提升并不明显。因此，多车多机协同模式应用于区域侦察时如何提高任务完成效率、扩大区域侦察范围、以及如何更加有效利用无人机，对每辆车上搭载的无人机数量进行探究等方面还需要进一步研究。现有技术还存在适应性不佳的问题。


技术实现要素：

4.基于此，有必要针对上述技术问题，提供一种能够提高大范围区域侦察的效率的区域侦察任务规划方法、装置、计算机设备和存储介质。
5.一种区域侦察任务规划方法，所述方法包括：
6.获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；
7.根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；
8.基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；
9.通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；
10.根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
11.一种区域侦察任务规划装置，所述装置包括：
12.任务信息获取模块，用于获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；
13.多车多机任务规划模型构建模块，用于根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；
14.初始解确定模块，用于基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；
15.最优解确定模块，用于通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；
16.方案信息输出模块，用于根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
17.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现以下步骤：
18.获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；
19.根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；
20.基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；
21.通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；
22.根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
23.一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：
24.获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；
25.根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；
26.基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；
27.通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；
28.根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
29.上述区域侦察任务规划方法、装置、计算机设备和存储介质，通过根据区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；基于分解策略，将多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；根据各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。本发明实现了多车多机任务规划，设计的融合扰动和禁忌策略的自适应大邻域搜索算法结合了alns算法的自适应准则、邻域搜索策略以及sa算法的metropolis准则，同时增加禁忌策略以增加对历史搜索过程的记忆，并且加入扰动操作使得搜索过程更加多样化，还具有多种邻域结构且各邻域结构具有不同特征，实现了较好的优化效果。
附图说明
30.图1为一个实施例中区域侦察任务规划方法的流程示意图；
31.图2为一个实施例中多车多无人机区域侦察示意图；
32.图3为一个实施例中多车多机协同区域侦察任务规划初始解生成示意图；
33.图4为一个实施例中区域划分示例示意图，其中4(a)为待侦察区域，4(b)为网格划分结果，4(c)为子区域划分结果；
34.图5为一个实施例中子区域划分给无人机示意图；
35.图6为一个实施例中个体编码示意图；
36.图7为一个实施例中随机改变卡车路径示意图；
37.图8为一个实施例中改变最长卡车路径示意图；
38.图9为一个实施例中扰动操作示意图；
39.图10为一个实施例中每增加1架无人机带来的效率提升度结果示意图；
40.图11为一个实施例中区域侦察任务规划装置的结构框图；
41.图12为一个实施例中计算机设备的内部结构图。
具体实施方式
42.为了使本技术的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本技术进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
43.本技术提供的区域侦察任务规划方法，可以应用于如下应用场景中。区域中有已知路网，路网上有若干个已知的可进行卡车停泊、无人机起降的卡车无人机汇合点，需要利用多架无人机与多辆卡车完成区域的全覆盖扫描以采集此区域的相应信息。各卡车携带无
人机在区域路网上移动，当到达某个卡车无人机汇合点时，将车上所有无人机放飞，无人机在子区域内完成一次侦察任务后返回卡车更换电池，然后执行下一次任务，直到该子区域被完全覆盖，卡车携带无人机前往下一个汇合点。如此，直至所有子区域被侦察完，所有卡车携带无人机返回基地。
44.在一个实施例中，如图1所示，提供了一种区域侦察任务规划方法，包括以下步骤：
45.步骤102，获取区域侦察任务信息。
46.区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息。
47.图2为多车多无人机协同区域侦察任务规划的示例图，黑色三角形表示卡车无人机汇合点，黑色方块表示基地。该图中共有两辆携带五架无人机协同完成任务，左侧卡车搭载三架无人机依次访问1、2、3号卡车无人机汇合点，无人机在汇合点放飞并完成所有白底网格的区域扫描任务，灰色实线、浅灰虚线、黑色虚线分别代表3架无人机在区域内的扫描轨迹，加粗黑实线代表左侧卡车的行驶路径。右侧卡车搭载两架无人机依次访问4、5、6号卡车无人机汇合点，无人机在汇合点放飞并完成所有灰底网格的区域扫描任务，灰底网格上黑色虚线、浅灰虚线分别代表2架无人机在区域内的扫描轨迹，加粗灰实线代表右侧卡车的行驶路径。2辆卡车均从基地出发，完成任务后返回基地，每架无人机一次只能扫描一个网格。
48.步骤104，根据区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型。
49.本发明中问题假设如下：
50.(1)卡车只能在路网行驶，不能进入区域内执行侦察任务；
51.(2)无人机只能在卡车所访问的卡车无人机汇合点进行起飞和降落；
52.(3)无人机一次航程只扫描一个网格，称为一次侦察任务；
53.(4)卡车和无人机都以恒定的速度运行；
54.(5)忽略无人机起飞、降落及更换电池的时间；
55.(6)无人机执行侦察任务时，卡车停留在原地等待无人机降落；
56.(7)在每个卡车无人机汇合点，卡车必须等到所有无人机完成侦察任务回到车上之后才能离开前往下一个卡车无人机汇合点。
57.(8)无人机扫描网格时，选择距卡车无人机汇合点最近的网格顶点作为扫描起始点，距卡车无人机汇合点次近的网格顶点作为扫描结束点。
58.多车多无人机协同区域侦察还包括以下特点：
59.(9)每辆卡车的行驶里程有限；
60.(10)每辆卡车携带的无人机数量可以不同；
61.(11)卡车放飞无人机后，可在原地等待回收无人机，在无人机航程允许的情况下也可前往下一个汇合点等待无人机。
62.(12)每架无人机在一次任务中的起飞点和降落点必须在同一辆卡车上，任务执行过程中不允许降落到其他卡车上。
63.本发明所涉及的数学符号如表1所示。
64.表1符号说明
65.表1-1集合符号说明
[0066][0067]
表1-2参数和决策变量符号说明
[0068][0069]
具体地，本发明构建的多车多机任务规划模型如下：
[0070]
(1)目标函数
[0071]
本文提出的问题以完成所有侦察任务的时间最少作为目标，即使得最晚回到基地的卡车或无人机的时间最小。
[0072]
min{t|t≥max(t1h,t2k),h∈tr,k∈d}
ꢀꢀꢀꢀ
(1)
[0073]
(2)约束条件
[0074]
约束条件如下：
[0075]
t0＝(t
max-ld/vd)
ꢀꢀꢀꢀ
(2)
[0076][0077][0078][0079][0080][0081][0082][0083][0084][0085][0086][0087][0088][0089]
约束条件(2)表示计算无人机侦察一个网格所需的时间。约束条件(3)表示搭载无人机的车辆必须从基地出发，完成所有覆盖任务之后返回同一个基地。约束条件(4)表示每个卡车无人机汇合点的出度等于入度，从而确保车辆行驶路线的连通性。约束条件(5)表示每个卡车无人机汇合点最多只能由一辆卡车访问一次。约束条件(6)表示每个子区域内的每个网格只能被一架无人机侦察。约束条件(7)表示无人机在每次完成一个网格的侦察所需的时间不超过其最大续航时间。约束条件(8)表示每个区域内所有无人机的最大扫描总面积要大于等于该区域的面积，保证能够对该区域完全覆盖即保证该区域所包含的每个网格都要被无人机侦察。约束条件(9)表示卡车到达卡车无人机汇合点后，将车上所有无人机放飞。约束条件(10)表示每辆卡车至少携带一架无人机。约束条件(11)表示所有卡车携带的无人机数量之和等于总无人机数量。公式(12)表示卡车的行驶路径长度不能超过最大行驶里程限制。约束条件(13)、(14)、(15)定义0-1变量的取值范围。
[0090]
步骤106，基于分解策略，将多车多机任务规划模型分解为多个卡车无人机分配方
案下的多个单车-多机子模型，分别为单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解。
[0091]
传统的多车多机问题中，一般在问题设定中会明确每辆卡车搭载的无人机数量，且各卡车搭载的无人机数量相同且固定，相较于传统的问题设定，本发明的多车多机问题给出卡车的总数量和无人机的总数量，并不事先设定好每辆卡车需搭载的无人机数量，无人机可以随意分配给各卡车，意味着各卡车搭载的无人机数量可以不同，且每辆卡车搭载的无人机数量并不固定。这种设定给问题求解提供了更多思路和可能性，相较于传统多车多机问题可能寻得更优解，同时也更加符合实际问题的情形。因此在本发明算法的初始解生成分为两步：(1)生成不同卡车无人机分配方案，将多车多机问题分解为多个单车多机问题；(2)分别在不同的卡车无人机分配方案下构造初始解。如图3所示。
[0092]
生成不同卡车无人机分配方案时，由于待侦察区域较大，为便于对无人机进行任务分配，首先进行区域划分。根据区域网格化的结果，进行子区域划分，主要目的是为每一个卡车无人机汇合点分配需要扫描的网格，以形成每个卡车无人机汇合点所包含的侦察子区域集即子区域。接着根据各子区域网格数量，将子区域分配给各架无人机，使得各无人机分配到的网格尽可能平均。最后，根据卡车数量，对无人机进行随机分配，将所有无人机分配至不同的卡车上，1辆卡车与多辆无人机构成一个单车-多机系统，系统内所有无人机分配到的子区域作为该系统的待覆盖区域，保证每辆卡车分配到2架及以上无人机。
[0093]
在不同的卡车无人机分配方案下构造初始解时，初始解的生成遵循“先构造单车-多机系统，再对每个单车-多机系统进行任务规划，最后合并各单车-多机任务规划方案”的思想，包括以下2个部分：1)对不同的卡车无人机分配方案下的每个单车-多机系统进行任务规划，运用动态规划算法进行卡车路径规划，运用任务分配算法进行无人机任务规划，形成任务规划方案；2)合并各单车-多机任务规划方案形成各多车-多机的初始任务规划方案，任务完成时间取各单车-多机系统时间的最大值。
[0094]
步骤108，通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解。
[0095]
在融合扰动和禁忌策略的自适应大邻域搜索算法中，在自适应大邻域搜索的基础上，结合模拟退火机制和禁忌策略。设计多种邻域结构，在邻域变换过程中，若产生的新解优于当前最优解，则接受新解，并用新解替换当前最优解；若产生的新解差于当前最优解，则以metropolis准则判断是否接受该退化解。同时，将产生新解过程中需要操作的网格添加到禁忌列表中，从而避免对这些网格的重复搜索。如果禁忌表已满，则按照先进先出的规则释放其中的网格。除此之外，当历史最优解在h
max
次迭代之后无法变得更优时，对算法执行扰动操作。
[0096]
步骤110，根据各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
[0097]
上述区域侦察任务规划方法中，通过根据区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；基于分解策略，将多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡
车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；根据各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。本发明实现了多车多机任务规划，设计的融合扰动和禁忌策略的自适应大邻域搜索算法结合了alns算法的自适应准则、邻域搜索策略以及sa算法的metropolis准则，同时增加禁忌策略以增加对历史搜索过程的记忆，并且加入扰动操作使得搜索过程更加多样化，还具有多种邻域结构且各邻域结构具有不同特征，实现了较好的优化效果。
[0098]
在其中一个实施例中，还包括：将待侦察区域划分为单元化的网格，并确定网格中心点信息；其中，网格的大小等于无人机最大扫描面积；根据卡车无人机汇合点信息和网格中心点信息，构建网格与卡车无人机汇合点之间的距离矩阵，根据距离矩阵基于就近原则为每个卡车无人机汇合点分配需要扫描的网格，确定每个卡车无人机汇合点对应的子区域信息；根据子区域信息将子区域分配给各架无人机，以使各无人机分配到的网格数量的差值平方和最小；根据获取的卡车数量信息，对无人机进行随机分配，以使所有无人机分配到不同的卡车上，构成多个卡车无人机分配方案；其中，每个卡车无人机分配方案中包括多个单车-多机子模型；单车-多机子模型由一辆卡车和至少两架无人机构成。
[0099]
具体地，卡车无人机分配方案生成主要是根据卡车数量，将无人机分配给各卡车，由于本文不考虑1辆卡车携带1架无人机的情况，因此在保证每辆卡车分配到大于等于2架无人机的基础上，得到所有可能的分配方案，同时得到各分配方案下，各单车-多机系统的待覆盖区域。主要分为以下两个部分：
[0100]
1)区域划分
[0101]
由于待侦察区域较大，为便于对无人机进行任务分配，设计一种区域划分算法，将区域网格化，并得到子区域划分结果。区域网格化方法如下：首先分析区域的大小，而后根据无人机的航程计算出无人机最大扫描面积(预留一段机动航程)，最后将整个需要侦察的区域划分为单元化的网格，每个网格的大小等于无人机最大扫描面积。无人机的扫描范围可看作一个边长为dw的方形区域。
[0102]
假设所有无人机都是同一类型的，则无人机最大扫描面积sd
max
计算方式如下：
[0103]
sd
max
＝(t
max
×vd-ld)
×
dw
ꢀꢀꢀꢀ
(16)
[0104]
其中t
max
为无人机的最大飞行时间，vd为无人机飞行速度，ld为无人机预留航程，dw为无人机的扫描宽度。
[0105]
根据区域网格化的结果，进行子区域划分，主要目的是为每一个卡车无人机汇合点分配需要扫描的网格，以形成每个卡车无人机汇合点所包含的侦察子区域集即子区域。本文采用的策略是就近原则，即将网格分配给距其最近的卡车无人机汇合点。首先计算各网格中心点与各卡车无人机汇合点之间的距离矩阵，而后将每个网格分配给距其最近的卡车无人机汇合点，以形成初步的子区域划分结果。
[0106]
图4给出了一个边长为8km的正方形区域划分示例。图4(a)中显示侦察区域的总面积为64km2，该区域中0号方块代表基地，有5个卡车无人机汇合点，以三角形表示，依次编号为1-5。无人机最大续航时间为19.5mins，飞行速度为80km/h，预留航程为10km，无人机扫描宽度为100m，由公式(15)计算得无人机最大扫描面积为4km2，且无人机扫描每个网格的时间为12mins。因此可将整个区域划分为16个网格，并依次给网格编号，如图4(b)所示。图4(c)为子区域划分示例，根据上述子区域划分策略，1、2、3、4号卡车无人机汇合点均分到网
格，形成各自相对应的4个子区域，5号卡车无人机汇合点未分到网格。因此后续规划车辆路径时，待访问的卡车无人机汇合点为1、2、3、4号，5号卡车无人机汇合点不在车辆路径内。不同的色块代表不同的子区域。表2为子区域划分结果。
[0107]
2)子区域分配给无人机
[0108]
运用以下分配策略：根据各子区域网格数量，将子区域分配给各架无人机，使得各无人机分配到的网格尽可能平均。如此各单车-多机系统的任务量与系统内无人机数量成正相关关系，即使各卡车分配到的无人机数量不同，在该策略下，各单车-多机系统的任务完成时间将更加平均化，由于总任务时间取各分配方案的时间最小值，而各分配方案的时间取方案内各单车-多机系统的时间最大值，因此可得到任务完成时间较短的初始解。如果无人机总数量大于汇合点数量，则将未分配到网格的无人机视为虚拟无人机，后续随机加入各单车-多机系统中。如图5为子区域划分给无人机示意图，该区域共有36个网格(编号为1-36)、6个子区域(标号为1-6)，共有4架无人机用于区域侦察，各子区域所包含的网格数分别为6、9、3、5、5、8，因此将子区域1、3分配给1号无人机、将子区域2分配给2号无人机、将子区域6分配给3号无人机、将子区域4、5分配给4号无人机，各无人机所分配到的网格数分别为9、9、8、10。
[0109]
3)无人机分配给卡车：根据卡车数量，对无人机进行随机分配，将所有无人机分配至不同的卡车上，1辆卡车与多辆无人机构成一个单车-多机系统，系统内所有无人机分配到的子区域作为该系统的待覆盖区域，保证每辆卡车分配到2架及以上无人机。如表2为一个由9架无人机和3辆卡车组成的多车-多机系统的8种分配方案示例。
[0110]
表2无人机分配给卡车示意表
[0111][0112]
在其中一个实施例中，还包括：通过动态规划算法和任务分配算法分别为单车-多机子模型进行车辆路径和无人机任务集规划，得到单车-多机子模型对应的任务规划方案数据；根据任务规划方案数据，若同一个卡车无人机分配方案下的所有单车-多机子模型最长的车辆路径值不超过预设的卡车最大航程值，则将同一个卡车无人机分配方案下的多个单车-多机子模型对应的任务规划方案数据进行合并，得到卡车无人机分配方案下的任务规划初始解；否则，删除卡车无人机分配方案。
[0113]
具体地，在各不同卡车无人机分配方案下，初始解的生成遵循“先构造单车-多机系统，再对每个单车-多机系统进行任务规划，最后合并各单车-多机任务规划方案”的思想，包括以下2个部分：1)对不同的卡车无人机分配方案下的每个单车-多机系统进行任务规划，运用动态规划算法进行卡车路径规划，运用任务分配算法进行无人机任务规划，形成任务规划方案；2)合并各单车-多机任务规划方案形成各多车-多机的初始任务规划方案，
任务完成时间取各单车-多机系统时间的最大值。
[0114]
初始解的构造流程如算法所示，算法需要输入待侦察区域a的顶点(v1，v2，...，vq)、卡车无人机汇合点集合(n1，n2，...，nk)、无人机最大航程s
max
、卡车最大航程r
max
、卡车数量acar，无人机数量auav。通过区域划分算法可根据无人机最大航将整个区域网格化并进行子区域划分，得到子区域划分结果和各自区域对应的卡车无人机汇合点编号(第3行)；从而计算各子区域所包含网格数量(第4行)，运用任务分配算法将所有子区域分配给各无人机，得到各无人机分配到的待覆盖区域gridnodetouav(第5行)；采用随机分配策略将所有无人机分配给所有卡车，得到不同的卡车无人机分配方案assignutoc(第6行)；在各卡车无人机分配方案下，分解得到多个单车-多机系统subsys；如果该方案下所有单车多机系统内最长的车辆路径不超过卡车最大航程r
max
(第8行)：运用动态规划算法和任务分配算法分别为每一个单车-多机系统规划车辆路径和无人机任务集，形成任务规划方案(第10行)，合并各单车-多机系统任务规划方案，形成该卡车无人机分配方案下的多车多机任务规划方案(第11行)，任务时间为各单车-多机系统任务时间的最大值；否则将该卡车无人机分配方案视为无效，进行删除(第14行)，最终得到所有有效卡车无人机分配方案下的初始解及对应的任务时间(第15、16行)。
[0115][0116]
(3)个体编码方式
[0117]
本文设计了一种新的个体编码方式。如图6所示，采取实数编码方式，个体由l部分
组成(l为卡车数量)。每一个部分代表一个单车-多机系统(如紫色框所示)。其中每个单车-多机系统内由以下部分组成：第1部分表示该系统内的卡车路径，代表卡车访问卡车无人机汇合点的顺序(如橙色方块所示)；其余部分分别表示该系统内各子区域内每架无人机的任务集。
[0118]
在其中一个实施例中，还包括：通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；融合扰动和禁忌策略的自适应大邻域搜索算法的步骤包括：
[0119]
步骤1：进行参数初始化，包括：邻域结构中的所有破坏算子和修复算子初始权重均设置为1；模拟退火机制中的当前迭代次数i设置为1，初始温度当前温度t设置为初始温度ts；当前禁忌表存放的网格数量l设置为0，历史最优解未发生变化的次数h设置为1；
[0120]
步骤2：获取各单车-多机子模型的任务规划方案数据sk；
[0121]
步骤3：将各个单车-多机子模型的任务规划方案数据s1，...，sm合并，形成多车多机初始任务规划方案数据s，将当前初始任务规划方案数据s赋给最优解s
best
；
[0122]
步骤4：根据自适应邻域选择机制中的破坏算子权重do和修复算子权重ro选择破坏算子操作d∈do和修复算子操作r∈ro，得到最新的任务规划方案数据s
′
；
[0123]
步骤5：比较新解s
′
和当前解s的总任务完成时间，得出时间差，用δf表示，若新解满足约束则接受新解，将新解s
′
赋值给当前解s；同时，若δf＜0，则代表新解可使得任务完成时间缩短，将新解s
′
赋值给最优解s
best
；若δf＞0，则按照metropolis准则判断是否接受退化解；
[0124]
步骤6：更新破坏算子权重do和修复算子权重ro，更新禁忌表；
[0125]
步骤7：如果满足h＜h
max
，重复步骤4～步骤6；若循环次数达到h
max
，则转到步骤8；
[0126]
步骤8：执行扰动操作ω，形成新的任务规划方案s，并将h赋值为1；
[0127]
步骤9：若总迭代次数i≥i
max
或者t≤te，则算法终止，输出当前最优解s
best
；否则，更新迭代次数i和当前温度t，并返回步骤4。
[0128]
在融合扰动和禁忌策略的自适应大邻域搜索算法中，在自适应大邻域搜索的基础上，结合模拟退火机制和禁忌策略。设计多种邻域结构，在邻域变换过程中，若产生的新解优于当前最优解，则接受新解，并用新解替换当前最优解；若产生的新解差于当前最优解，则以metropolis准则判断是否接受该退化解。同时，将产生新解过程中需要操作的网格添加到禁忌列表中，从而避免对这些网格的重复搜索。如果禁忌表已满，则按照先进先出的规则释放其中的网格。除此之外，当历史最优解在h
max
次迭代之后无法变得更优时，对算法执行扰动操作。当该算法的伪代码如下所示。
[0129][0130]
基于以上描述，为了提高解的质量，在算法中结合不同的破坏、修复策略设计了如下四种破坏算子和四种修复算子。任意一种破坏算子和一种修复算子组合为一个邻域算子。同时为了使搜索过程更加多样化，在算法中加入了一个扰动操作。
[0131]
(1)破坏算子
[0132]
本文共设计4种破坏算子，破坏算子集合定义为do。这些算子主要用于将网格从其原先所属的子区域中删除。以下为4种破坏算子的详细情况：
[0133]
1)随机破坏算子
[0134]
每个子区域内随机选择一个网格进行移除；
[0135]
2)最优破坏算子
[0136]
每个子区域内选择离卡车无人机汇合点最远的网格进行移除；
[0137]
3)随机改变卡车路径
[0138]
随机选择一条卡车路径，随机选择该路径中一个卡车无人机汇合点，将该汇合点包含的网格从该卡车-无人机系统的任务集中删掉，如图7所示。
[0139]
4)改变最长卡车路径
[0140]
选择最长的一条卡车路径，随机选择该路径中的一个卡车无人机汇合点，将该汇合点包含的网格从该卡车-无人机系统的任务集中删掉，如图8所示。
[0141]
(2)修复算子
[0142]
本文共设计4种修复算子，修复算子集合定义为ro。这些算子主要用于将破坏算子操作后的网格重新插入子区域中。以下为4种修复算子的详细情况：
[0143]
1)同一单车-多机组合之间的随机修复
[0144]
将破坏出来的网格随机加入距其在无人机剩余航程内的卡车无人机汇合点所在的子区域内；
[0145]
2)同一单车-多机组合之间的贪婪修复
[0146]
将破坏出来的网格加入到能够使当前解得到优化的子区域；
[0147]
3)不同单车-多机组合之间的随机修复
[0148]
将破坏出来的网格随机加入距其在无人机剩余航程内的卡车无人机汇合点所在的子区域内；
[0149]
4)不同单车-多机组合之间的贪婪修复
[0150]
将破坏出来的网格加入到能够使当前解得到优化的子区域；
[0151]
1种破坏算子和1种修复算子组合可形成1种邻域结构，通过以上4种破坏算子和4种修复算子之间的随机组合，可形成16种邻域结构，为用于自适应大邻域搜索中的邻域选择。同时，邻域结构变换的过程需满足卡车最大行驶里程和无人机最大航程约束，若不满足，则跳过本次迭代过程。
[0152]
(3)扰动准则
[0153]
为了使得搜索的过程更加多样化，当历史最优解在h_max次迭代之后无法变得更优时，对算法执行以下扰动操作：为均衡每个单车-多机组合的任务完成时间以使得总任务时间最短，重新分配每辆卡车上搭载的无人机数量，提取总任务时间相差最大的2个单车-多机组合，将总任务时间最短的组合内的1架无人机分配给总任务时间最长的组合，如图9所示。随后重新进行不同的单车-多机组合内的无人机任务规划。扰动操作对于大邻域算法的意义重大，加入扰动后算法结果将会得到进一步提升。
[0154]
应该理解的是，虽然图1的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的
执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。
[0155]
在一个具体实施例中，使用本发明方法进行了仿真实验。包括：
[0156]
算例及实验参数设计：
[0157]
首先生成5个规则区域算例(下文称之为算例1-5)，各算例信息如表3所示。实验参数设计如表4所示：卡车平均速度设为40km/h，无人机的平均速度设为80km/h；无人机扫描间距设为100m；无人机续航时间为19.5mins，预留航程为10km，因此可得每架无人机的最大覆盖面积sd
max
＝4km2，一架无人机扫描一个网格需要12分钟。alnsawpt算法中的初始温度为1000℃，终止温度为10℃，冷却速率为0.97，最大迭代次数为10000，等温过程中迭代次数为10，禁忌表存放网格最大数量为500。
[0158]
表3各算例基本信息
[0159][0160]
表4算法参数设置
[0161][0162]
实验结果和分析：
[0163]
在区域面积范围为144km
2-400 km2的5个算例中，分别在2辆卡车搭载4、5、6、7、8、9、10架无人机和3辆卡车搭载6、7、8、9、10架无人机的情形下进行实验，依次分析卡车数量相同情况下，无人机数量增加对任务时间的影响及无人机数量相同情况下，卡车数量增加对任务时间的影响，从而验证多车多机模式对任务完成效率的提升效果。首先根据卡车数量，对无人机进行随机分配，将所有无人机分配至不同的卡车上，一辆卡车与多架无人机构成一个单车-多机系统，系统内所有无人机分配到的子区域作为该系统的待覆盖区域，保证
每辆卡车分配到两架以上(包括两架)无人机。而后在每种卡车无人机分配方案下生成初始解，运用融合扰动和禁忌策略的自适应大邻域搜索算法对初始解进行优化得到多车多无人机协同区域侦察任务规划方案，取各分配方案中最短的任务完成时间作为最终求得的区域侦察任务完成时间，每个算例实验重复10次取平均值。比较alnsawpt算法得到的任务规划方案与初始任务规划方案的总任务完成时间，如表5所示，实验结果表明，在5个算例中，alnsawpt算法可在初始解的基础上将任务时间分别缩短8.17％、9.98％、9.95％、10.71％和10.80％，在多种多车多机情形下的任务完成时间平均缩短9.92％。可见，alnsawpt算法具有较好的优化效果。
[0164]
表5alnsawpt算法对初始解的提升度
[0165][0166]
为体现alnsawpt算法的优越性，同时设计融合禁忌策略的自适应大邻域搜索算法(alnsawt,adaptive large neighborhood search algorithm with tabu strategies)和融合扰动的自适应大邻域搜索算法(alnsawp,adaptive large neighborhood search algorithm with perturbation and tabu strategies)，在上述算例上进行实验，与alnsawpt算法的实验效果进行对比。实验结果表明，alnsawpt算法同时结合了禁忌策略和扰动操作，具有更好的优化效果，如表6所示，与仅结合禁忌策略的alnsawt算法和仅结合扰动操作的alnsawp算法对比，总任务时间可缩短3.68％-5.47％。
[0167]
表6alnsawpt与其他算法的对比结果
[0168][0169]
然后分析无人机数量和卡车数量对总任务时间的影响。首先分析卡车数量相同情况下，无人机数量增加对任务时间的影响，对各算例结果取平均值。如图10所示，在2辆卡车情形下，分别使用4、5、6、7、8、9、10架无人机的实验中，总任务时间在上一次实验的基础上
平均分别可缩短12.39％、7.64％、5.78％、6.29％、2.10％、1.49％；在3辆卡车情形下，分别使用6、7、8、9、10架无人机的实验中，总任务时间在上一次实验的基础上平均分别可缩短6.17％、6.92％、4.62％、2.44％。由实验结果可知，区域侦察总任务时间随算例规模的增大而增加；在卡车数量相同时，区域侦察总任务时间随无人机数量增加而减少，且总体呈现边际递减效应。
[0170]
其次分析在无人机数量相同的情况下，卡车数量增加对任务时间的影响。算例1-5中每增加1辆卡车带来的任务效率提升度，对各算例结果取平均值，如表7所示，在无人机数量相同时，区域侦察总任务时间随卡车数量增加而减少，分别使用1、2、3辆卡车的实验中，总任务时间在上一次实验的基础上平均分别可缩短50.62％、31.60％。
[0171]
表7各算例卡车数量增加带来的平均效率提升度
[0172][0173]
由实验结果可知，融合扰动和禁忌策略的自适应大邻域搜索算法可有效解决多车多无人机区域侦察任务规划问题，对初始解具有较好的优化效果。相比于单车多机系统，多车多机系统可大幅减少任务完成时间，提高任务完成效率。
[0174]
在一个实施例中，如图11所示，提供了一种区域侦察任务规划装置，包括：任务信息获取模块1102、多车多机任务规划模型构建模块1104、初始解确定模块1106、最优解确定模块1108和方案信息输出模块1110，其中：
[0175]
任务信息获取模块1102，用于获取区域侦察任务信息；区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；
[0176]
多车多机任务规划模型构建模块1104，用于根据区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；卡车及无人机配置信息由卡车信息和无人机信息确定；
[0177]
初始解确定模块1106，用于基于分解策略，将多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；
[0178]
最优解确定模块1108，用于通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；
[0179]
方案信息输出模块1110，用于根据各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。
[0180]
初始解确定模块1106还用于将待侦察区域划分为单元化的网格，并确定网格中心点信息；其中，网格的大小等于无人机最大扫描面积；根据卡车无人机汇合点信息和网格中心点信息，构建网格与卡车无人机汇合点之间的距离矩阵，根据距离矩阵基于就近原则为每个卡车无人机汇合点分配需要扫描的网格，确定每个卡车无人机汇合点对应的子区域信
息；根据子区域信息将子区域分配给各架无人机，以使各无人机分配到的网格数量的差值平方和最小；根据获取的卡车数量信息，对无人机进行随机分配，以使所有无人机分配到不同的卡车上，构成多个卡车无人机分配方案；其中，每个卡车无人机分配方案中包括多个单车-多机子模型；单车-多机子模型由一辆卡车和至少两架无人机构成。
[0181]
初始解确定模块1106还用于通过动态规划算法和任务分配算法分别为单车-多机子模型进行车辆路径和无人机任务集规划，得到单车-多机子模型对应的任务规划方案数据；根据任务规划方案数据，若同一个卡车无人机分配方案下的所有单车-多机子模型最长的车辆路径值不超过预设的卡车最大航程值，则将同一个卡车无人机分配方案下的多个单车-多机子模型对应的任务规划方案数据进行合并，得到卡车无人机分配方案下的任务规划初始解；否则，删除卡车无人机分配方案。
[0182]
最优解确定模块1108还用于通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；融合扰动和禁忌策略的自适应大邻域搜索算法的步骤包括：
[0183]
步骤1：进行参数初始化，包括：邻域结构中的所有破坏算子和修复算子初始权重均设置为1；模拟退火机制中的当前迭代次数i设置为1，初始温度当前温度t设置为初始温度ts；当前禁忌表存放的网格数量l设置为0，历史最优解未发生变化的次数h设置为1；
[0184]
步骤2：获取各单车-多机子模型的任务规划方案数据sk；
[0185]
步骤3：将各个单车-多机子模型的任务规划方案数据s1，...，sm合并，形成多车多机初始任务规划方案数据s，将当前初始任务规划方案数据s赋给最优解s
best
；
[0186]
步骤4：根据自适应邻域选择机制中的破坏算子权重do和修复算子权重ro选择破坏算子操作d∈do和修复算子操作r∈ro，得到最新的任务规划方案数据s
′
；
[0187]
步骤5：比较新解s
′
和当前解s的总任务完成时间，得出时间差，用δf表示，若新解满足约束则接受新解，将新解s
′
赋值给当前解s；同时，若δf＜0，则代表新解可使得任务完成时间缩短，将新解s
′
赋值给最优解s
best
；若δf＞0，则按照metropolis准则判断是否接受退化解；
[0188]
步骤6：更新破坏算子权重do和修复算子权重ro，更新禁忌表；
[0189]
步骤7：如果满足h＜h
max
，重复步骤4～步骤6；若循环次数达到h
max
，则转到步骤8；
[0190]
步骤8：执行扰动操作ω，形成新的任务规划方案s，并将h赋值为1；
[0191]
步骤9：若总迭代次数i≥i
max
或者t≤te，则算法终止，输出当前最优解s
best
；否则，更新迭代次数i和当前温度t，并返回步骤4。
[0192]
关于区域侦察任务规划装置的具体限定可以参见上文中对于区域侦察任务规划方法的限定，在此不再赘述。上述区域侦察任务规划装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。
[0193]
在一个实施例中，提供了一种计算机设备，该计算机设备可以是终端，其内部结构图可以如图12所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、显示屏和输入装置。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机
程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种区域侦察任务规划方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。
[0194]
本领域技术人员可以理解，图12中示出的结构，仅仅是与本技术方案相关的部分结构的框图，并不构成对本技术方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。
[0195]
在一个实施例中，提供了一种计算机设备，包括存储器和处理器，该存储器存储有计算机程序，该处理器执行计算机程序时实现上述方法实施例中的步骤。
[0196]
在一个实施例中，提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现上述方法实施例中的步骤。
[0197]
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本技术所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(rom)、可编程rom(prom)、电可编程rom(eprom)、电可擦除可编程rom(eeprom)或闪存。易失性存储器可包括随机存取存储器(ram)或者外部高速缓冲存储器。作为说明而非局限，ram以多种形式可得，诸如静态ram(sram)、动态ram(dram)、同步dram(sdram)、双数据率sdram(ddrsdram)、增强型sdram(esdram)、同步链路(synchlink)dram(sldram)、存储器总线(rambus)直接ram(rdram)、直接存储器总线动态ram(drdram)、以及存储器总线动态ram(rdram)等。
[0198]
以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。
[0199]
以上所述实施例仅表达了本技术的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本技术构思的前提下，还可以做出若干变形和改进，这些都属于本技术的保护范围。因此，本技术专利的保护范围应以所附权利要求为准。

技术特征：
1.一种区域侦察任务规划方法，其特征在于，所述方法包括：获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。2.根据权利要求1所述的方法，其特征在于，根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型，包括：根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型为：min{t|t≥max(t1
h
,t2
k
),h∈tr,k∈d}
ꢀꢀꢀꢀꢀꢀꢀ
(1)t0＝(t
max-l
d
/v
d
)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)(2)(2)(2)(2)(2)(2)(2)(2)
其中，t1
h
表示第h辆卡车回到基地的时间，t2
k
表示第k架无人机回到基地的时间，tr表示卡车集合tr＝{1,2,
…
,l}，l表示卡车数量，d表示无人机集合d＝{1,2,
…
,m}，m表示无人机数量，t0表示无人机扫描一个网格所需时间，t
max
表示无人机最大续航时间，l
d
表示无人机预留航程，v
d
表示无人机平均飞行速度，n表示卡车无人机汇合点集合n＝{1,
…
,b}，b表示卡车无人机汇合点数量，表示如果第h辆卡车从汇合点i行驶到到汇合点j，则为1，否则为0，表示在子区域s中，如果g号网格被划分到第k架无人机的任务集，则为1，否则为0，其中k＝{1,2
…
,m},g∈g,s∈a，g表示网格集合g＝{1,2,
…
,n}，n表示网格数量，a表示待侦察区域，表示子区域a
s
包含的网格集合,s∈a,g∈g，a
s
表示区域a的子区域集合,s＝{1,2
…
,c}，c表示子区域数量，r
ig
表示卡车无人机汇合点i到g号网格中心点的距离，i∈n0∪n,g∈g，sd
max
表示无人机最大扫描面积，m
s
表示子区域a
s
的面积，z
kh
表示如果第k架无人机由第h辆卡车搭载，则为1，否则为0，ltr(s
h
)表示第h辆卡车的路径长度，str
max
表示卡车最大行驶里程；公式(1)为目标函数，公式(2)-(15)为约束条件，约束条件(2)表示计算无人机侦察一个网格所需的时间，约束条件(3)表示搭载无人机的车辆必须从基地出发，完成所有覆盖任务之后返回同一个基地，约束条件(4)表示每个卡车无人机汇合点的出度等于入度，从而确保车辆行驶路线的连通性，约束条件(5)表示每个卡车无人机汇合点最多只能由一辆卡车访问一次，约束条件(6)表示每个子区域内的每个网格只能被一架无人机侦察，约束条件(7)表示无人机在每次完成一个网格的侦察所需的时间不超过其最大续航时间，约束条件(8)表示每个区域内所有无人机的最大扫描总面积要大于等于该区域的面积，保证能够对该区域完全覆盖即保证该区域所包含的每个网格都要被无人机侦察，约束条件(9)表示卡车到达卡车无人机汇合点后，将车上所有无人机放飞，约束条件(10)表示每辆卡车至少携带一架无人机，约束条件(11)表示所有卡车携带的无人机数量之和等于总无人机数量，约束条件(12)表示卡车的行驶路径长度不能超过最大行驶里程限制，约束条件(13)、(14)、(15)定义0-1变量的取值范围。3.根据权利要求1所述的方法，其特征在于，基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，包括：将待侦察区域划分为单元化的网格，并确定网格中心点信息；其中，所述网格的大小等于无人机最大扫描面积；根据所述卡车无人机汇合点信息和所述网格中心点信息，构建网格与卡车无人机汇合点之间的距离矩阵，根据所述距离矩阵基于就近原则为每个卡车无人机汇合点分配需要扫描的网格，确定每个卡车无人机汇合点对应的子区域信息；根据所述子区域信息将子区域分配给各架无人机，以使各无人机分配到的网格数量的差值平方和最小；根据获取的卡车数量信息，对无人机进行随机分配，以使所有无人机分配到不同的卡
车上，构成多个卡车无人机分配方案；其中，每个所述卡车无人机分配方案中包括多个单车-多机子模型；所述单车-多机子模型由一辆卡车和至少两架无人机构成。4.根据权利要求3所述的方法，其特征在于，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解，包括：通过动态规划算法和任务分配算法分别为所述单车-多机子模型进行车辆路径和无人机任务集规划，得到所述单车-多机子模型对应的任务规划方案数据；根据所述任务规划方案数据，若同一个卡车无人机分配方案下的所有单车-多机子模型最长的车辆路径值不超过预设的卡车最大航程值，则将同一个卡车无人机分配方案下的多个单车-多机子模型对应的任务规划方案数据进行合并，得到所述卡车无人机分配方案下的任务规划初始解；否则，删除所述卡车无人机分配方案。5.根据权利要求4所述的方法，其特征在于，通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解，包括：通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；所述融合扰动和禁忌策略的自适应大邻域搜索算法的步骤包括：步骤1：进行参数初始化，包括：邻域结构中的所有破坏算子和修复算子初始权重均设置为1；模拟退火机制中的当前迭代次数i设置为1，初始温度当前温度t设置为初始温度t
s
；当前禁忌表存放的网格数量l设置为0，历史最优解未发生变化的次数h设置为1；步骤2：获取各单车-多机子模型的任务规划方案数据s
k
；步骤3：将各个单车-多机子模型的任务规划方案数据s1，...，s
m
合并，形成多车多机初始任务规划方案数据s，将当前初始任务规划方案数据s赋给最优解s
best
；步骤4：根据自适应邻域选择机制中的破坏算子权重do和修复算子权重ro选择破坏算子操作d∈do和修复算子操作r∈ro，得到最新的任务规划方案数据s
′
；步骤5：比较新解s
′
和当前解s的总任务完成时间，得出时间差，用
△
f表示，若新解满足约束则接受新解，将新解s
′
赋值给当前解s；同时，若
△
f＜0，则代表新解可使得任务完成时间缩短，将新解s
′
赋值给最优解s
best
；若
△
f>0，则按照metropolis准则判断是否接受退化解；步骤6：更新破坏算子权重do和修复算子权重ro，更新禁忌表；步骤7：如果满足h＜h
max
，重复步骤4～步骤6；若循环次数达到h
max
，则转到步骤8；步骤8：执行扰动操作ω，形成新的任务规划方案s，并将h赋值为1；步骤9：若总迭代次数i≥i
max
或者t≤t
e
，则算法终止，输出当前最优解s
best
；否则，更新迭代次数i和当前温度t，并返回步骤4。6.根据权利要求5所述的方法，其特征在于，所述破坏算子操作中，破坏算子包括：随机破坏算子、最优破坏算子、随机改变卡车路径和改变最长卡车路径；所述修复算子操作中，修复算子包括：同一单车-多机子模型组合之间的随机修复、同一单车-多机子模型组合之间的贪婪修复、不同单车-多机子模型组合之间的随机修复和不同单车-多机子模型组合之间的贪婪修复。
7.根据权利要求1至6任意一项所述的方法，其特征在于，所述扰动操作ω为：重新分配每辆卡车上搭载的无人机数量，提取总任务时间相差最大的2个单车-多机子模型组合，将总任务时间最短的组合内的一架无人机分配给总任务时间最长的组合，再重新进行不同的单车-多机子模型组合内的无人机任务规划。8.一种区域侦察任务规划装置，其特征在于，所述装置包括：任务信息获取模块，用于获取区域侦察任务信息；所述区域侦察任务信息包括待侦察区域信息、卡车信息和无人机信息；所述待侦察区域信息包括基地信息、路网信息和卡车无人机汇合点信息；多车多机任务规划模型构建模块，用于根据所述区域侦察任务信息，以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；所述卡车及无人机配置信息由所述卡车信息和所述无人机信息确定；初始解确定模块，用于基于分解策略，将所述多车多机任务规划模型分解为多个卡车无人机分配方案下的多个单车-多机子模型，分别为所述单车-多机子模型进行任务规划，得到各卡车无人机分配方案下的任务规划初始解；最优解确定模块，用于通过融合扰动和禁忌策略的自适应大邻域搜索算法对所述各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；方案信息输出模块，用于根据所述各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至7中任一项所述方法的步骤。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至7中任一项所述的方法的步骤。

技术总结
本申请涉及一种区域侦察任务规划方法、装置、计算机设备和存储介质。所述方法包括：以完成所有侦察任务的时间最少作为目标，以侦察任务需求、卡车及无人机配置信息为约束条件，构建多车多机任务规划模型；基于分解策略，得到各卡车无人机分配方案下的任务规划初始解；通过融合扰动和禁忌策略的自适应大邻域搜索算法对各卡车无人机分配方案下的任务规划初始解进行优化，得到各卡车无人机分配方案下的任务规划最优解；根据各卡车无人机分配方案下的任务规划最优解，输出总任务时间最短的任务规划方案信息。本发明实现了多车多机任务规划，实现了较好的优化效果。实现了较好的优化效果。实现了较好的优化效果。


技术研发人员：叶青 伍国华 周玲
受保护的技术使用者：中南大学
技术研发日：2023.05.17
技术公布日：2023/8/13