一种禁飞区约束下的多无人机包裹协作递送路径优化方法与流程

1.本发明涉及无线通讯技术领域，特别是涉及一种禁飞区约束下的多无人机包裹协作递送路径优化方法。


背景技术：

2.近年来，随着机器人领域技术和物流行业的快速发展，将能够自主控制的无人车和无人机应用到物流配送环节引起了产业界和学术界的广泛关注。相比于在现有地面交通网络中运行的无人车，无人机可以在地面交通拥堵或者地面交通不可达的地方实现包裹递送。在利用无人机进行包裹递送时，路径规划是一个很重要的关注点，因为物流企业可能希望通过缩短路径、减少包裹递送时间等方式来最大化无人机的经济效益。
3.然而在无人机的路径规划中存在许多现实环境的约束，一种是无人机飞行过程中面临的环境威胁，例如其它同时飞行的无人机带来的安全风险，随着无人机数量的增加，碰撞的几率也会增加。尤其是在人口密集的地区，这种碰撞有可能造成严重的人员伤亡。此外，城市环境中大型建筑和基础设施众多，进行无人机的路径规划时，必须避免无人机过分靠近这些障碍物。总的来说，在进行无人机路径规划阶段应该努力避免碰撞。另一种限制是禁飞区的存在，导致部分空域不能使用，城市环境中，禁飞区包括政府机构、军事基地、机场、火车站等关键机构或人口密集的场所，无人机飞行过程中应该尽量远离上述禁飞区域。
4.当前大多数关于无人机路径规划的研究工作都没有考虑到无线通信对无人机飞行路径规划的影响。虽然有些研究考虑到了禁飞区对无人机路径规划的约束，但没有应用到无人机编队执行包裹协作递送场景中，并且，这些研究工作提出的大多数路径规划方法不能保证全局最优性和有效性。除此之外，大多数研究考虑的是包裹递送过程中无人机能耗、资源分配等，没有考虑到一轮递送的总包裹量等包裹递送成本问题。


技术实现要素：

5.针对上述现有技术的不足，本专利申请所要解决的技术问题是如何提供一种提升包裹递送的效率，增大包裹递送的效益的禁飞区约束下的多无人机包裹协作递送路径优化方法。
6.为了解决上述技术问题，本发明采用了如下的技术方案：
7.一种禁飞区约束下的多无人机包裹协作递送路径优化方法，包括以下步骤：s1：建立无人机编队飞行路径模型，所述无人机编队飞行路径模型包括无人机编队的水平坐标和飞行高度，无人机编队的起点和终点，无人机之间的最小距离和无人机的最大飞行速度指标和性能控制参数；s2：建立禁飞区和包裹递送区模型；s3：建立无人机编队包裹递送任务分配模型；s4：构造禁飞区约束下的多无人机包裹协作递送优化问题；s5：求解构造步骤s4中提出的优化问题。
8.进一步的，步骤s1中，无人机编队的水平坐标用表示，其中
表示无人机u执行包裹递送任务过程中的水平坐标集合，无人机编队在执行包裹递送过程中的飞行高度始终保持不变，用常数h表示无人机编队的飞行高度，无人机编队从仓库出发，完成包裹递送任务后，再飞行到无人机编队回收中心处，无人机编队的起点即仓库的位置，终点即无人机编队回收中心的位置，表示为cu[1]＝c
str
，cu[t]＝c
dst
，避免无人机编队飞行过程中发生碰撞，指定无人机之间的最小距离，即无人机飞行过程中的水平坐标应满足以下约束条件：
[0009][0010]
其中l
min
表示无人机之间的最小距离。
[0011]
为保证无人机编队的安全飞行，需要对所述无人机编队的最大飞行速度做出限制：
[0012][0013]
其中表示无人机在每个时隙内的最大飞行距离。
[0014]
进一步的，步骤s2中，设立禁飞区模型时，将禁飞区建模成高度大于或等于无人机编队飞行高度的圆柱体，第n个禁飞区，其水平坐标表示为其半径表示为rn，为了避免无人机编队飞到禁飞区域，无人机编队的水平坐标需要满足以下约束条件：
[0015][0016]
进一步的，步骤s2中，建立包裹递送区模型时，以无人机是否能检测到地面客户的上行信号为划分标准，将无人机能检测到地面客户上行信号的区域作为该地面客户的包裹递送区，根据上述标准，首先建立了无人机编队与地面客户的通信模型，假定无人机编队和地面客户间的信道仅由视距链接决定，那么在时隙t内，从地面客户k到无人机u间的信道功率增益可以表示为：
[0017][0018]
其中g0表示单位距离(一米)的信道功率增益，表示无人机u和地面客户k之间的距离；
[0019]
在时隙t内，无人机u接收到的来自地面客户k的信号的信噪比可以表示为：
[0020][0021]
其中pk表示地面客户k的传输功率；n0表示噪声功率；
[0022]
地面客户的包裹递送区定义为信噪比γ
k，u
[t]大于某个阈值θu的区域，θu表示无人机u的信号检测能力。
[0023]
进一步的，在步骤s3中，建立无人机编队包裹递送任务分配模型时，无人机编队包裹递送任务分配，需要考虑地面客户的包裹递送需求和无人机的承载能力，首先，在仓库中将每个地面客户的所有包裹打包成一个包裹，并集中存放到任意一架无人机上，因此仓库中共有k个包裹，每个包裹对应一个地面客户，并指定包裹k属于地面客户k，用wk(千克)和wu(千克)分别表示包裹k的重量和无人机u的最大承重量，所述无人机编队包裹递送任务，是
指为每架无人机分配合适的递送包裹，定义d
k，u
∈{0，1}表示包裹k的包裹递送指示符，即当无人机u递送包裹k时，d
k，u
＝1，否则d
k，u
＝0，指定包裹递送任务时，不仅考虑每个客户只需要一架无人机递送，还需要考虑指定给无人机的递送包裹总量不能超过该无人机的最大承载容量，因此指定包裹递送任务时需要满足以下约束条件：
[0024][0025][0026][0027]
只有当无人机飞行到指定的包裹递送区时才可以递送包裹，因此包裹递送任务还需要满足以下约束条件：
[0028][0029]
其中，表示指示函数，即当x＝true时，否则
[0030]
进一步地，定义表示无人机编队的包裹递送任务分配方案，那么无人机编队最大的包裹递送量可以定义为
[0031]
进一步的，步骤s4中，构造禁飞区约束下的多无人机包裹协作递送优化问题，使无人机编队可以在有禁飞区的环境中，通过检测地面客户的上行信号信噪比，按照包裹递送任务要求，沿着最优路径进行包裹递送，从而达到最大化无人机编队递送的包裹数量的目的，构造如下问题：
[0032][0033][0034][0035][0036][0037][0038][0039][0040][0041]
进一步的，步骤s5中，进行解构时，首先将优化问题等效转化为更易处理的优化问题，然后采用相关优化方法求解转换后的优化问题。
[0042]
本方案具有优点：
[0043]
1.本发明综合考虑了复杂环境中的禁飞区、无人机编队间的碰撞规避以及无人机编队接收到的来自地面客户的上行信号信噪比对无人机编队路径规划的影响，针对上述环境，提出了一种禁飞区约束下的多无人机包裹协作递送路径优化方法来最大化一轮递送的包裹数量。
[0044]
2.本发明将多无人机包裹协作递送建模成一个优化问题，利用恰当的方法将难以求解的原始问题转换成更易处理的等效问题，并提出一种较低复杂度的算法。
[0045]
3.本发明提出的一种禁飞区约束下的多无人机包裹协作递送路径优化方法与现有的无人机编队路径规划相比。
附图说明
[0046]
图1为本发明提出的一种禁飞区约束下的多无人机包裹协作递送路径优化方法流程图；
[0047]
图2为本发明提出的一种禁飞区约束下的多无人机包裹协作递送路径优化方法的实际应用场景图；
[0048]
图3为解决优化问题的流程图；
[0049]
图4为无人机编队在有禁飞区的环境下执行包裹递送任务的路径仿真结果图。
具体实施方式
[0050]
下面结合附图对本发明作进一步的详细说明。在本发明的描述中，需要理解的是，方位词如“上、下”和“顶、底”等所指示的方位或位置关系通常是基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，在未作相反说明的情况下，这些方位词并不指示和暗示所指的装置或元件必须具有特定的方位或者以特定的方位构造和操作，因此不能理解为对本发明保护范围的限制；方位词“内、外”是指相对于各部件本身的轮廓的内外。
[0051]
如图1-4所示，一种禁飞区约束下的多无人机包裹协作递送路径优化方法，包括以下步骤：s1：建立无人机编队飞行路径模型，所述无人机编队飞行路径模型包括无人机编队的水平坐标和飞行高度，无人机编队的起点和终点，无人机之间的最小距离和无人机的最大飞行速度指标和性能控制参数；s2：建立禁飞区和包裹递送区模型；s3：建立无人机编队包裹递送任务分配模型；s4：构造禁飞区约束下的多无人机包裹协作递送优化问题；s5：求解构造步骤s4中提出的优化问题。
[0052]
进一步的，包含一个存放包裹和无人机的仓库，以及一个用于回收无人机的无人机编队回收中心，仓库的水平坐标用表示，回收中心的水平坐标用表示；k个需要递送包裹的地面客户，用集合表示，地面客户的位置都是固定的，表示为其中n个禁飞区，包括政府机构、加油站、火车站等关键机构和场所，用集合表示，禁飞区的位置也都是固定的，表示为其中由u个用于包裹递送的无人机组成的无人机编队，用集合表示，无人机编队需要在t个时隙内从仓库出发，完成包裹递送任务后，再返回仓库，总的时隙
用集合表示。
[0053]
进一步的，所述无人机编队飞行路径模型，包括无人机编队的水平坐标和飞行高度，无人机编队的起点和终点，无人机之间的最小距离和无人机的最大飞行速度等指标和性能控制参数设置。
[0054]
所述无人机编队的水平坐标用表示，其中表示无人机u执行包裹递送任务过程中的水平坐标集合，无人机编队在执行包裹递送过程中的飞行高度始终保持不变，用常数h表示无人机编队的飞行高度。
[0055]
所述无人机编队从仓库出发，完成包裹递送任务后，再飞行到无人机编队回收中心处。因而无人机编队的起点即仓库的位置，终点即无人机编队回收中心的位置，也就是说，cu[1]＝c
str
，cu[t]＝c
dst
。
[0056]
为了避免无人机编队飞行过程中发生碰撞，指定无人机之间的最小距离，即无人机飞行过程中的水平坐标应满足以下约束条件：
[0057][0058]
其中l
min
表示无人机之间的最小距离。
[0059]
进一步的，为了保证无人机编队的安全飞行，需要对所述无人机编队的最大飞行速度做出限制：
[0060][0061]
其中表示无人机在每个时隙内的最大飞行距离。
[0062]
进一步的，所述禁飞区模型，将上述禁飞区建模成高度大于或等于无人机编队飞行高度的圆柱体，以第n个禁飞区为例，其水平坐标如前所述，表示为其半径表示为rn，为了避免无人机编队飞到禁飞区域，无人机编队的水平坐标需要满足以下约束条件：
[0063][0064]
进一步的，所述包裹递送区模型，以无人机是否能检测到地面客户的上行信号为划分标准，将无人机能检测到地面客户上行信号的区域作为该地面客户的包裹递送区，首先建立了无人机编队与地面客户的通信模型，假定无人机编队和地面客户间的信道仅由视距链接决定，那么在时隙t内，从地面客户k到无人机u间的信道功率增益可以表示为：
[0065][0066]
其中g0表示单位距离(一米)的信道功率增益，表示无人机u和地面客户k之间的距离。
[0067]
进一步地，在时隙t内，无人机u接收到的来自地面客户k的信号的信噪比可以表示为：
[0068][0069]
其中pk表示地面客户k的传输功率；n0表示噪声功率。
[0070]
进一步地，本发明将地面客户的包裹递送区定义为信噪比γ
k，u
[t]大于某个阈值θu的区域，θu表示无人机u的信号检测能力。
[0071]
进一步的，所述无人机编队包裹递送任务分配，同时考虑了地面客户的包裹递送需求和无人机的承载能力，首先，在仓库中将每个地面客户的所有包裹打包成一个包裹，并集中存放到任意一架无人机上，因此仓库中共有k个包裹，每个包裹对应一个地面客户，并指定包裹k属于地面客户k，用wk(千克)和wu(千克)分别表示包裹k的重量和无人机u的最大承重量，所述无人机编队包裹递送任务，是指为每架无人机分配合适的递送包裹，具体地说，定义d
k，u
∈{0，1}表示包裹k的包裹递送指示符，即当无人机u递送包裹k时，d
k，u
＝1，否则d
k，u
＝0。指定包裹递送任务时，不仅考虑每个客户只需要一架无人机递送，还需要考虑指定给无人机的递送包裹总量不能超过该无人机的最大承载容量。因此指定包裹递送任务时需要满足以下约束条件：
[0072][0073][0074][0075]
进一步的，只有当无人机飞行到指定的包裹递送区时才可以递送包裹，因此包裹递送任务还需要满足以下约束条件：
[0076][0077]
其中，表示指示函数，即当x＝true时，否则
[0078]
进一步地，定义表示无人机编队的包裹递送任务分配方案，那么无人机编队最大的包裹递送量可以定义为
[0079][0080]
进一步的，设计一种联合优化无人机编队飞行路径规划和包裹递送任务分配方法，使无人机编队可以在有禁飞区的环境中，通过检测地面客户的上行信号信噪比，按照包裹递送任务要求，沿着最优路径进行包裹递送，从而达到最大化无人机编队递送的包裹数量的目的。
[0081]
进一步地，根据上述目的，构造优化问题1：
[0082][0083][0084][0085][0086]
[0087][0088][0089][0090][0091]
进一步的，由于优化变量d是二进制变量，因此有关包裹递送任务分配的约束条件都是含有整数变量的约束条件；并且有关无人机编队规避碰撞和禁飞区的约束条件都是关于优化变量c的非凸约束；除此之外，约束条件中还有指示函数，因此，优化问题1是一个求解困难的非凸混合整数规划问题，因此，首先将优化问题1等效转化为更易处理的优化问题，然后采用相关优化方法求解转换后的优化问题，提出可以最大化无人机编队包裹递送量的多无人机包裹协作递送路径和包裹递送任务分配方法。
[0092]
进一步的，本发明利用大m法则，并引入一个新的优化变量
[0093][0094]
将优化问题1中的约束条件等效转化为以下三个新的约束条件：
[0095][0096][0097][0098]
其中m
k，u
[t]是一个比||cu[t]-ak||2的任意值都大的较大的常数。
[0099]
进一步地，将优化问题1中的整数约束条件d
k，u
∈{0，1}和x
k，u
[t]∈{0，1}等效转化为以下四个新的约束条件：
[0100][0101][0102][0103][0104]
经过上述变换后，可以将优化问题1等效转化为优化问题2：
[0105][0106][0107]
[0108][0109][0110][0111][0112][0113][0114][0115][0116][0117][0118]
优化问题2中部分约束条件是非凸的，但这些非凸约束条件都可以写成两个凸函数的差值形式，因此，优化问题2是一个标准的凸差问题，可以利用惩罚凸凹过程法进行求解。
[0119]
进一步地，利用pccp方法，先松弛优化问题2，然后再将松弛后的优化问题转化成一系列凸逼近子问题，利用凸优化工具进行求解。
[0120]
首先，通过向非凸约束条件增加惩罚因子，并惩罚相应松弛的总和来松弛优化问题2，从而得到以下松弛后的优化问题，记为优化问题3：
[0121][0122][0123][0124][0125][0126][0127][0128][0129]
[0130][0131][0132][0133][0134][0135][0136][0137][0138]
其中：
[0139]
代表总的惩罚；
[0140]
其中，以及分别表示各个非凸约束条件的松弛变量。s(d)-ξp(ε，σ，α，β)中的系数ξ＞0表示一个惩罚因子，随着该惩罚因子的增加，总的惩罚p(ε，σ，α，β)将越来越小，并最终趋于零。当p(ε，σ，α，β)＝0时，优化问题2和优化问题3等价。
[0141]
进一步地，线性化优化问题3中的凹项，即分别在给定点(c
(j)
，d
(j)
，x
(j)
)处，对优化问题3中的凹项处进行泰勒一节展开，其中一节展开，其中其中j＝1，2，
…
表示pccp方法的迭代序号。
[0142]
进一步地，在第j轮迭代中，优化问题3中的非凸约束条件可以用以下线性约束条件替代：
[0143][0144][0145][0146][0147]
其中(
·
)
t
表示转置操作。经过上述变换后，得到pccp方法的第j轮迭代的无比金子问题，表示为优化问题4：
[0148][0149][0150]
[0151][0152][0153][0154][0155][0156][0157][0158][0159][0160][0161][0162][0163][0164][0165]
其中ξ
(j)
表示第j轮迭代的惩罚因子，优化问题4是一个凸优化问题，因此可以利用标准的凸优化方法或cvx等凸优化工具求解。
[0166]
进一步地，提出的求解优化问题3的算法1的具体步骤如下：
[0167]
1)给定任意初始值(c
(0)
，d
(0)
，x
(0)
)，ξ
(0)
＞0，ξ
max
，v＞1，并令迭代序号j＝0；
[0168]
2)利用凸优化方法或工具求解优化问题4，用优化问题4的解更新上述点的值，即将优化问题的解赋值给(c
(j 1)
，d
(j 1)
，x
(j 1)
)；
[0169]
3)将{uξ
(j)
，ξ
max
}中的最小值赋值给ξ
(j 1)
；
[0170]
4)更新迭代序号：j＝j 1；
[0171]
5)重复步骤2)到步骤4)，直到达到循环结束条件为止。
[0172]
进一步地，本发明分析了所提算法的计算复杂度。算法1的计算复杂度由求解优化问题4决定，如果利用cvx工具求解该优化问题，那么计算复杂度即其中a＝ut(n u 2k 2) 2ku表示所有的变量数目，∈＞0是一个给定的求解精度。
[0173]
图4给出了无人机编队在有禁飞区的环境下执行包裹递送任务的路径仿真结果，其中红色的圆圈代表包裹递送区域，黑色的圆圈代表禁飞区域。首先，从图4可以看出，无人机编队在飞行过程中不会经过禁飞区，说明本发明提出的方法可以有效规避所有的禁飞区域。其次，还可以发现，某些无人机将会经过地面客户的包裹递送区域，因为它们需要执行
包裹递送任务。除此之外，所有无人机都完成了从起点出发，进行包裹递送后，再飞行到无人机编队回收中心的任务，说明本发明提出的方法可以保证无人机编队能够在限定时间内顺利完成包裹协作递送任务。
[0174]
最后应说明的是：本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等统计数的范围之内，则本发明也意图包含这些改动和变型。