本发明涉及一种多无人机四维航迹规划方法，特别是一种改进q-学习蚁群算法的多无人机四维航迹规划方法。
背景技术：
1、随着人工智能、自动驾驶、物联网等技术的发展，以及多类型民用无人机的出现，城市范围内无人机使用需求极速增长，无人机创新应用场景不断涌现，尤其是物流无人机将在城市中大量涌现，并呈现高密度运行趋势，很小区域内(如10km2)涉及无人机数量成百上千架，以完成末端配送服务。当城市空中交通进入规模化运行阶段，合理有效、智能精准的无人机交通飞行调配策略就显得至关重要。在既有空域结构基础上，通过对无人机四维航迹进行科学安排、协同优化和智能调配，以解决各无人机在飞行过程中存在的冲突，其关键之一在于飞行前(约30分钟)的快速全局多无人机航迹规划。
2、无人机航迹规划本质上是一个组合优化问题，并且是一个np-hard问题，通常随着问题规模的扩大，求解问题的时间呈指数增长，无法用常规的方法进行求解。多无人机航迹规划计算更加复杂、约束条件更多，传统的单机航迹规划方法在全局最优性、求解时效性和时空资源分配公平性三个方面力不从心；智能优化算法因其具有全局优化力强、对优化问题要求宽松等优点，为多无人机航迹规划问题的求解提供了新思路。然而，随着城市无人机规模化、高密度运行，问题规模显著扩大，已有方法也显现出一些不足和缺陷，如时空资源利用公平性和充分性不足、容易陷入局部最优、收敛速度慢等。
技术实现思路
1、发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种改进q-学习蚁群算法的多无人机四维航迹规划方法。
2、为了解决上述技术问题，本发明公开了一种改进q-学习蚁群算法的多无人机四维航迹规划方法，包括以下步骤：
3、步骤1：构建多个蚁群并初始化，每个蚁群包含若干个搜索同一个无人机四维航迹的蚂蚁；
4、步骤2：设计基于改进q-学习的四维航迹构建方法，引导各蚁群中蚂蚁搜索无人机四维航迹；
5、步骤3：针对多无人机航迹共享同一时空间资源，设计多蚁群合作策略，引导多蚁群协同进化搜索全局最优解，即为全局最优多无人机四维航迹规划方案。
6、进一步的，步骤1中所述的构建多个蚁群并初始化，具体方法包括如下步骤：
7、步骤1.1：设有nuav个无人机，无人机集合为：{nuv-1,...,uav-nuav}，针对其四维航迹规划问题，构建nuav个蚁群，即：{antcolony-1,...,antcolony-nuav}，其中，每个蚁群包含nant只蚂蚁，第k个蚁群表示如下：
8、
9、设蚂蚁携带的信息包括：出发时间和行进速度其中表示第k个蚁群的第l只蚂蚁，k＝1,2,...,nuav,l＝1,2,...,nant；
10、步骤1.2：在无人机预设的执行任务的时间范围内随机初始化每只蚂蚁的出发时间，在无人机预设的飞行速度范围内随机初始化每只蚂蚁的行进速度；
11、步骤1.3：采用三维空间栅格化方式将无人机执行任务的空间抽象为一个有向图：
12、g(v,e)
13、其中，v＝{v1,v2,...,v|v|}表示任务空间中的立体栅格，每一个立体栅格抽象化为一个节点，用于表示无人机任务空间的位置信息，其属性包括：该栅格中心位置坐标和是否存在障碍物，|v|表示节点数量；
14、e＝{eij}表示节点之间的边，当第i个节点vi到第j个节点vj的路径segment(i,j)是无障碍且直接可行时，eij＝1，否则eij＝0；
15、步骤1.4：第k个蚁群携带的信息，还包括：素信息用于引导本蚁群中蚂蚁搜索最优路径，其中，表示节点vi到节点vj所留存第k个蚁群的信息素浓度；
16、步骤1.5：所有蚁群的信息素集合为信息素矩阵γ，表示如下：
17、
18、按照预设规则初始化信息素矩阵，如果eij＝1，否则
19、进一步的，步骤2中所述的设计基于改进q-学习的四维航迹构建方法，具体包括如下步骤：
20、步骤2.1：设置初始迭代次数g4dt＝1，设置最大迭代次数为对于第k个蚁群，随机选择其中的一只蚂蚁为最优蚂蚁，记为
21、步骤2.2：采用均匀交叉算子和差分变异算子优化第k个蚁群中所有蚂蚁的出发时间和行进速度
22、其中，所述的均匀交叉算子，如下：
23、
24、
25、
26、
27、所述的差分变异算子，如下：
28、
29、
30、其中，为0到1的随机数；μc∈[0,1]和μm∈[0,1]分别为交叉概率和变异概率；r1，r2和r3为1到nant的取值，三个数为互不相同且不同于l；fd为差分变异系数；
31、步骤2.3：将第k个蚁群中的nant只蚂蚁置于第k个无人机的起始位置，对每一只蚂蚁，根据带启发信息的状态转移策略，不断搜索下一个节点位置，直至到达第k个无人机的目标位置；，当蚂蚁行进的路径长度达到无人机最大飞行距离lengthmax时，若未能到达任务目标位置则强制停止搜索；
32、其中，所述的带启发信息的状态转移策略，具体如下：
33、
34、
35、式中，蚂蚁所在当前位置为vi，蚂蚁根据所述策略由当前位置vi所转移至的下一位置为vj′；allowedi表示位置vi的邻接无障碍节点、直接可达且满足无人机飞行机动性能约束的位置集合，vj表示位置集合allowedi中的第j个节点；表示第k个无人机从节点vi飞行至节点vj的启发式信息，其与节点vj到第k个无人机目标位置的距离和节点vi到节点vj的运行风险riskij相关，计算方法如下：
36、
37、设阈值为q0；当产生的随机数q<q0时，蚂蚁直接使用启发式信息与信息素浓度的指数乘积最大的下一个节点；反之，计算vi到vj的转移概率并使用比例选择法选择下一个节点；
38、所述的无人机飞行机动性能约束，至少包括：飞行转弯角约束、飞行高度约束和爬升或俯冲角约束；
39、步骤2.4：根据蚂蚁所搜索路径、出发时间和飞行速度，判断蚂蚁到达目的地的时间是否超时，即超过该蚂蚁所代表的无人机的到达时间，如果超过预定到达时间则更新其飞行速度，方法如下：
40、
41、若更新后仍然超过预定到达时间按如下方法更新出发时间：
42、
43、其中，表示沿蚂蚁所搜索航迹飞行的路径长度，表示第k个无人机的飞行最大速度，表示第k个无人机允许的最早起飞时间；
44、步骤2.5：计算蚂蚁适应度值更新第k个蚁群中的最优蚂蚁即具有最小适应度值的蚂蚁；同理，最差蚂蚁即为具有最大适应度值的蚂蚁；
45、步骤2.6：采用改进q-学习的局部更新策略更新第k个蚁群的信息素信息
46、步骤2.7：判断是否成立，若成立，则输出为第k个无人机的局部最优四维航迹；否则，重新执行步骤2.2，并将迭代次数g4dt增1。
47、进一步的，步骤3中所述的设计多蚁群合作策略，具体方法包括如下步骤：
48、步骤3.1：设置协同进化迭代次数gcc＝1，设置最大协同进化迭代次数为
49、步骤3.2：构建一个合作池并进行初始化，用于存放步骤2中获得的各蚁群的最优蚂蚁、最差蚂蚁和一个随机蚂蚁；所述合作池还用于存放后续得到的全局最优解、最差解和一个随机解；令globalsbest记录当前全局最优解；
50、当gcc＝1时，合作池中上述蚂蚁和全局解均随机设置；
51、步骤3.3：采用步骤2中所述方法引导每一个种群中蚂蚁搜索路径，路径搜索过程中蚂蚁适应度值的计算采用适应度合作评估策略进行计算，同时更新合作池和全局最优解globalsbest；
52、步骤3.4：采用多蚁群信息素合作更新策略更新所有蚁群的信息素信息；
53、步骤3.5：判断是否成立，若成立，则输出globalsbest为全局最优多无人机四维航迹规划方案，即完成改进q-学习蚁群算法的多无人机四维航迹规划；否则，重新执行步骤3.3，并将协同进化迭代次数gcc增1。
54、进一步的，步骤2.6中所述的采用改进q-学习的局部更新策略更新第k个蚁群的信息素信息具体方法包括如下步骤：
55、步骤2.6.1：将第k个蚁群中的蚂蚁分为两类，能为第k个无人机搜索到有效飞行航迹的蚂蚁放入有效集合ak中，否则将蚂蚁放入无效集合中；
56、所述的有效飞行航迹，指蚂蚁能搜索到满足时间约束、满足飞行距离约束、避免空间障碍物和从起始位置到目的位置的四维航迹；
57、步骤2.6.2：判断无效集合是否为空，若不为空，无效集合中蚂蚁所经过的路径segment(i,j)的信息素接收一个负反馈强化，具体如下：
58、
59、其中，λ∈(0.9,1)为负反馈学习系数，nij表示无效集合中经过路径segment(i,j)的蚂蚁数量；
60、步骤2.6.3：判断有效集合ak是否为空，若不为空，有效集合ak中蚂蚁所经过路径segment(i,j)的信息素接收一个正反馈强化，具体如下；
61、
62、
63、
64、其中，ρ∈[0,1)和γ∈[0,1)为学习步长和折扣因子，1-ρ为信息素自然蒸发系数，表示正反馈强化项，|ak|为有效集合ak中蚂蚁的数量，为有效集合ak中第a只蚂蚁的适应度值，表示下一状态的折扣评估；
65、步骤2.6.4：更新信息素浓度具体如下：
66、
67、
68、其中，为第k个蚁群搜索到目前的最优蚂蚁所带来的信息素额外奖励。
69、进一步的，步骤3.3中所述的适应度合作评估策略，具体方法包括如下步骤：
70、步骤3.3.1：对任意种群中任意蚂蚁，设为从合作池为其选择其他蚁群的一个合作者，采用随机选择策略，构建一个多无人机四维航迹规划的完整解solkl；
71、步骤3.3.2：计算完整解solkl的适应度值，并将该值定义为的适应度值，计算方法如下：
72、
73、其中，obj(solkl)表示nuav个无人机所规划的航迹长度之和，penaltytc(solkl)表示超过预计到达时间到达目的地的超时统计，pendaltycf(solkl)表示任务空间未解决的冲突数统计；
74、步骤3.3.3：根据蚂蚁的适应度值和其所构建完整解solkl的适应度值，更新合作池和全局最优解globalsbest，即适应值越小，解越优。
75、进一步的，步骤3.4中所述的多蚁群信息素合作更新策略，具体方法包括如下步骤：
76、步骤3.4.1：构建时空航迹密度图，图中x轴表示不同的节点，y轴表示不同的时隙，初始化设置一个时隙表示的时长，节点vi在时隙tm的航迹密度densityim定义为时隙tm期间飞过节点vi所对应的立体栅格空间的航迹数量；使用颜色描述航迹密度；统计航迹密度超过阈值densityth的节点，记录在集合conflict_v中；
77、步骤3.4.2：对每一个节点vi∈conflict_v，记录其邻接节点vj,vj∈v∩eji＝1到vi的信息素浓度在集合中，其中上标1,...,nuav表示不同种群中节点vj到节点vi路径segment(j,i)上的信息素浓度；对集合按信息素浓度从大到小进行排序，得到排序后的集合其中，rk,k＝1,2,...nuav是排序后对应的种群编号，即r1是信息素浓度最高的种群对应的编号，rnuav是信息素浓度最低的种群对应的编号；
78、更新方法如下：
79、
80、其中，全局信息素更新系数ξ∈(0,1)；
81、步骤3.4.3：判断步骤3.4.1中统计的航迹密度densityim，若持续预设次数超出阈值，且超出部分densityim-densityth在预设次数ggcls次循环进化中持续不变，则对所有信息素浓度进行自适应调整，具体方法如下；
82、
83、其中，δ1为第一自适应调整系数，δ2为第二自适应调整系数，χ*τo为τo的χ倍，表示蚁群最大信息素浓度。
84、进一步的，步骤1.3中所述的直接可行，即不经过其他节点即能从节点vi到节点vj。
85、进一步的，步骤2.2中所述的交叉概率和变异概率，取值分别为0.8和0.01；差分变异系数，取值为1.5；
86、步骤2.3中所述的阈值q0取值为0.9。
87、进一步的，步骤3.4.3中所述的第一自适应调整系数，取值为0.8，第二自适应调整系数取值为1.2，χ取值100。
88、有益效果：
89、(1)构建更符合无人机四维航迹搜索的蚁群，定义携带出发时间和行进速度信息的蚂蚁可有效支持搜索无人机四维航迹，同时可充分利用无人机任务空间的时空资源，提高单个无人机搜索四维航迹的多样性；
90、(2)设计高效的改进q-学习四维航迹构建方法(iqlrc)，其中带启发信息的状态转移策略(heuristictr)可有效引导蚂蚁搜索邻域综合飞行距离和飞行风险的最优下一节点；改进q-学习的局部更新策略(lrls)可通过信息素的强化学习，引导蚁群内蚂蚁快速收敛局部高效安全的四维航迹；
91、(3)设计高效的多蚁群合作策略，其中适应度合作评估策略(cfe)构建高效合作池，采用随机选择策略构建多无人机四维航迹规划的全局完整解，有效提高种群合作多样性，从而提高全局解多样性；多蚁群信息素合作更新策略(gcls)有助于不同蚁群航迹搜索过程中飞行冲突的避免，通过时空资源公平性和充分性分配，实现多蚁群局部最优和全局最优的均衡，在确保公平性和安全性原则下快速收敛全局最优解，为多无人机四维航迹规划快速提供全局最优方案。
1.一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤1中所述的构建多个蚁群并初始化，具体方法包括如下步骤：
3.根据权利要求2所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤2中所述的设计基于改进q-学习的四维航迹构建方法，具体包括如下步骤：
4.根据权利要求3所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤3中所述的设计多蚁群合作策略，具体方法包括如下步骤：
5.根据权利要求3所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤2.6中所述的采用改进q-学习的局部更新策略更新第k个蚁群的信息素信息具体方法包括如下步骤：
6.根据权利要求4所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤3.3中所述的适应度合作评估策略，具体方法包括如下步骤：
7.根据权利要求4所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤3.4中所述的多蚁群信息素合作更新策略，具体方法包括如下步骤：
8.根据权利要求7所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤1.3中所述的直接可行，即不经过其他节点即能从节点vi到节点vj。
9.根据权利要求8所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤2.2中所述的交叉概率和变异概率，取值分别为0.8和0.01；差分变异系数，取值为1.5；
10.根据权利要求9所述的一种改进q-学习蚁群算法的多无人机四维航迹规划方法，其特征在于，步骤3.4.3中所述的第一自适应调整系数，取值为0.8，第二自适应调整系数取值为1.2，χ取值100。
