一种基于双方多目标蚁群协商的动态低空公共航路网络构建方法

摘要: 本发明属于无人机航路网络规划领域,尤其涉及一种基于双方多目标蚁群协商的动态低空公共航路网络构建方法。背景技术:1、低空物流、城市空中交通、应急救援和短途载运等应...
一种基于双方多目标蚁群协商的动态低空公共航路网络构建方法

本发明属于无人机航路网络规划领域,尤其涉及一种基于双方多目标蚁群协商的动态低空公共航路网络构建方法。

背景技术:

1、低空物流、城市空中交通、应急救援和短途载运等应用正在由单架航空器的示范飞行转向多起降点、多航线和多任务并存的网络化运行。《无人驾驶航空器飞行管理暂行条例》已对无人驾驶航空器飞行活动提出安全第一、服务发展、分类管理和协同监管要求;《通用航空装备创新应用实施方案(2024-2030年)》进一步提出建设短途运输与电动垂直起降客运网络、无人机配送网络及相应的航线网络和动态监测能力。民航主管部门正在推动低空航路规划、空中避障、空域管理和交通管制等要素贯通,并提出建设低空三维数字化网格地理信息系统。由此可见,面向实际运行的规划对象不能只是一架航空器的一条临时路径,还需要形成可审核、可发布、可持续更新的三维公共航路网络。

2、低空路径与航路规划已经形成较为丰富的技术体系。基于图、栅格或采样空间的搜索方法,能够利用明确的空间拓扑和代价规则生成可行路径,具有过程清晰、结果稳定和便于约束检查等特点;轨迹优化、滚动规划和局部修复方法则便于对已有航迹进行连续调整,以适应障碍物或空域状态的变化。遗传算法、粒子群算法和蚁群算法等群体智能方法具有较强的全局搜索能力,可综合考虑航程、能耗、转弯和飞行风险等非线性因素,其中蚁群算法通过信息素积累历史优质航段的选择经验,利用启发式信息评价下一步转移,并按照概率规则逐步构造路径,适用于由多个航段组成的组合规划问题。相关公开专利也提出了不同的实现思路,例如,cn109948834b利用预设高度切片和蚁群搜索构建低空公共航路,cn110597276b采用三维离散节点和两级蚁群方法规划无人飞行器空中安全走廊,cn115657721a则从路径长度、轨迹变化和信息素增强等方面改进三维无人机轨迹规划,为公共航路构建、三维安全走廊搜索和单航线轨迹优化提供了相应的技术基础。在多目标规划方面,帕累托优化、非支配排序和多种群协同等机制能够处理航程、能耗、安全风险和环境影响之间的权衡,使规划系统保留多种具有不同性能侧重的候选方案,而不必预先将全部目标合并为单一加权指标。上述方法在单航线规划、多航空器协同、动态避障和多目标决策等应用中各具优势;但当规划对象进一步扩展为由多个起降点和多条od航线共同组成的城市低空公共航路网络时,不仅需要保证每条航线满足建筑净空、禁飞区、起降点保护和航空器机动性能等要求,还需要在统一网络中协调不同航线的空间占用与安全间隔,并兼顾运营主体对能耗和机动效率的关注,以及公共管理主体对地面人员伤亡风险和噪声暴露的关注。因此,如何在既有路径搜索和多目标优化技术基础上,实现完整航路网络的联合构造、分主体目标评价以及搜索过程中的有效协同,仍是公共航路网络规划中需要进一步研究的问题。

3、与此同时,城市低空运行环境并非始终保持不变,人口暴露、道路车辆热点、临时活动区域和禁飞区状态均可能随时间发生变化。原有网络在新环境下仍可能保持可行,也可能仅有部分航段受到影响,或者因新的空域限制而需要重新规划。如果对每次环境变化均从零开始构建整个网络,将重复计算大量未受影响的航段;如果仅对旧航线进行局部几何调整,又可能改变原有的目标权衡或引入新的航线间冲突。

技术实现思路

1、发明目的:本发明旨在解决当前城市低空公共航路网络构建中,由于航线生成孤立,运营安全双方协商不充分,导致航线网络规划结果难以兼顾运行效率、公共安全的核心问题。具体而言,传统方法多以单条起讫航线为基本求解对象,分别获得路径后再叠加成网,缺乏在统一构造和评价过程中对多条航线共享空域、建筑净空、禁飞区、垂直起降保护区及航路间隔的整体考量,容易出现单条航线均可行而组合网络不可直接运行的问题;现有多目标方法又常将能耗、机动、人员风险和噪声等指标通过人工权重合并,或者仅输出一组混合前沿,难以体现运营效益与公共安全两类主体各自的优化依据,也难以说明最终方案由何种让步形成。

2、同时,双方种群即使能够分别搜索,也可能因缺少基于真实空间位置的交流机制而走向两个彼此分离的极端前沿:共同优选的局部航段无法用于引导后续搜索,偶然交叉或相同动作编码反而可能被误作共识;当人口、道路暴露和临时禁飞区发生变化时,固定航路网络不能及时反映新的运行条件,而完全重新计算又会降低更新效率,难以形成面向持续运行的规划闭环。

3、针对上述系统性问题,本发明通过完整网络蚂蚁的同步构造、连续三维硬约束可行化、效益方与安全方双种群非支配优化、实际三维局部共识信息素、共识锚定重组、双方前沿平衡选择以及事件触发的冷热预算重规划,构建从环境数据接入、网络生成、约束校验、双方协商、代表方案确定到运行期更新的完整技术链条,使生成结果能够作为城市低空航路规划平台的候选网络,供管理主体开展审核、仿真验证、版本发布和后续动态维护。

4、本发明具体提供一种基于双方多目标蚁群协商的动态低空公共航路网络构建方法,包括以下步骤:

5、步骤1,建立环境快照并表达完整航路网络;

6、步骤2,同步构造完整网络并实施硬约束可行化;

7、步骤3,形成双方非支配档案并更新信息素;

8、步骤4,以三维共同航段开展过程内协商;

9、步骤5,确定代表网络并实施事件触发式重规划。

10、步骤1包括:在统一坐标基准下获取规划区域边界、建筑物平面占用及高度、人口和道路车辆暴露、重要设施、静态及临时禁飞区、起降点及保护区,并录入允许飞行高度、航空器速度和质量、最大爬升角、最大下降角、航路包络宽度及安全间隔;其中,所述起降点包括垂直起降载人航空器起降点,保护区作为非关联无人机不得侵入的受限空域;建筑和地理数据由城市三维地理信息或测绘数据形成,人口、道路和车辆暴露由人口栅格、道路网络及交通状态数据形成,禁飞区由空域管理或运行管理状态形成,起降点由经确认的站点数据形成;

11、将同一采样时刻、同一空间坐标基准下的数据组合为带时间标识和版本标识的环境快照;根据所述环境快照生成地面人员伤亡风险评价输入、噪声评价输入,以及建筑物、禁飞区和起降点保护区的空间占用索引;所述空间占用索引用于查询航段包络附近的建筑物和受限空域,不改变对应约束的判定标准;

12、同一轮规划中的全部完整网络蚂蚁读取同一环境快照,以保证候选完整航路网络在相同环境条件下构造和评价;后续监测数据到达时,以生成当前已发布网络或最近一次实际重规划时采用的环境快照作为判断环境是否发生实质变化的比较基准。

13、步骤1还包括:设完整航路网络包含k条起讫航线,所述起讫航线称为od航线,od为origin-destination的缩写并表示起点到终点对;第k条起讫航线包含bk个航段;一只完整网络蚂蚁的决策变量同时保存k条起讫航线的水平状态和连续高度状态;效益蚂蚁和安全蚂蚁均属于完整网络蚂蚁,效益蚂蚁和安全蚂蚁采用相同的网络编码和硬约束校验,仅主导目标、信息素、启发式信息和进入的档案不同;水平状态在每条起讫航线自身的起终点局部坐标系内,以左移两格、左移一格、保持、右移一格和右移两格五种横向增量逐段累积;信息素地址包含起讫航线编号、航段序号、当前实际横向—高度状态和下一实际横向—高度状态,以区分相同动作编号在不同前序状态下对应的不同实际航段;

14、高度采用连续归一化变量进行编码,并按式(1)解码为实际物理高度:

15、(1),

16、其中表示第k条od航线第i个控制点的连续归一化高度变量,∈[0,1];为第k条od航线第i个控制点的实际高度,和分别为允许飞行高度下限和上限。

17、步骤2包括:

18、第s个航段联合构造轮次中,所有尚未到达终点的od航线均依据同一代初冻结的信息素快照、同一环境快照和各自第s-1个航段末端的实际状态形成第s个航段的合法下一转移集合;各od航线完成本轮转移选择后统一提交,再进入第s+1个航段联合构造轮次,从而避免od航线处理先后顺序改变同一代的信息素依据;

19、所述合法下一转移集合由规划区域边界、终点可达性、静态及临时禁飞区、非关联起降点保护区以及本od航路包络要求直接筛选得到;其中,终点可达性是指在剩余航段数量和允许横向增量范围内仍能够到达固定终点;

20、对于合法下一转移集合内的每个转移,效益蚂蚁以推进能耗和三维机动代价的增量评价形成本方启发式信息,并读取效益方信息素;安全蚂蚁以地面人员伤亡风险和噪声暴露的增量评价形成本方启发式信息,并读取安全方信息素;对方启发式修正由同一合法下一转移集合中另一方对应目标组的归一化增量代价形成,并以预设上限的有界因子参与;三维共识信息素由前一迭代的效益档案第一非支配前沿和安全档案第一非支配前沿中,同一起讫航线、同一航段序号的实际三维重叠航段形成;随后采用蚁群系统的伪随机比例转移规则:在利用分支选择综合吸引力最大的转移,在探索分支从除综合吸引力最大的转移之外的其余合法下一转移中按归一化吸引力概率选择;两只以上完整网络蚂蚁能够在并行工作进程中独立构造;单只完整网络蚂蚁完成后,一次性评价完整网络蚂蚁包含的全部起讫航线及不同起讫航线之间的空间关系;

21、水平航段根据每条起讫航线的起点和终点建立局部前向轴,并建立与局部前向轴正交的局部横向轴后确定:沿局部前向轴按目标航段长度设置基准控制点,内部控制点的横向偏移由{-2,-1,0,1,2}五种增量逐段累积并乘以横向偏移单位,首末控制点固定为起点sk和终点ek,相邻控制点连接形成水平航段;根据环境快照建立的空间占用索引,仅查询当前航段包络扩张后的包围盒所覆盖的建筑物和受限空域单元,计算各控制点的最低允许高度;连续高度序列由各控制点的连续归一化高度变量按式(1)解码得到;在固定起终点高度、允许飞行高度范围、建筑物高度及垂直净空、最大爬升角和最大下降角约束下,对连续高度序列交替执行前向投影和反向投影,在满足各控制点高度上下界及相邻高度差限制的条件下,使投影后高度相对原始解码高度的总调整量最小;不同起讫航路包络同时不满足水平安全间隔和垂直安全间隔的连续航段范围构成冲突区间;如果存在两个以上能够消除冲突的连续高度调整方案q,则分别计算新增推进能耗δf1(q)和新增三维机动代价δf2(q),删除在两项增量δf1(q)和δf2(q)上被其他方案同时支配的方案,并将剩余方案的两项增量δf1(q)和δf2(q)按本次候选集合的取值范围归一化,选择最小的方案;其中表示方案q下,归一化后的新增推进能耗增量,表示方案q下,归一化后的新增三维机动代价增量;

22、如果两个方案的最大归一化增量之差不超过预设数值精度,则计算总高度改变量h(q)=σkσi|z’k,i(q)-zk,i|并选择两个方案中h(q)较小的方案,其中z’k,i(q)为方案q投影后的第k条起讫航线第i个控制点高度,zk,i为调整前高度;总高度改变量之差不超过预设高度精度时,按预先固定的方案编号选择;若无法在允许高度及爬升、下降约束内消除冲突,则将对应的完整航路网络标记为不可行;

23、投影后的完整航路网络按照实际三维航段重新计算推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四个目标值;同时分别计算高度越界、建筑或禁飞区净空不足、非关联起降点保护区侵入、偏航角超限、爬升角或下降角超限以及不同od航路间隔不足的正残差,并将各项正残差之和记录为约束违反量,目标值与约束违反量相互独立记录。

24、步骤3包括:

25、对约束违反量不大于预设数值容差、通过完整校验的完整航路网络,分别计算推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四项最小化目标;其中,推进能耗依据航段长度、高度变化及航空器性能模型计算,三维机动代价依据水平转向和爬升、下降变化计算,地面人员伤亡风险依据航路下方人口、道路车辆和重要设施暴露及事故后果模型计算,噪声暴露依据航空器飞行状态、传播距离和地面敏感受体计算;

26、效益种群和安全种群是预先设置的两类完整网络蚂蚁群体,并非由环境数据自动生成;效益种群按照最小化推进能耗和最小化三维机动代价进行非支配排序,安全种群按照最小化地面人员伤亡风险和最小化噪声暴露进行非支配排序;

27、效益档案ae由通过完整校验且按照推进能耗和三维机动代价进行非支配排序的完整航路网络形成,安全档案as由通过完整校验且按照地面人员伤亡风险和噪声暴露进行非支配排序的完整航路网络形成,效益档案和安全档案在每一蚁群迭代完成评价后分别更新;档案超出容量时,按照如下规则排序:非支配层级编号越小的网络优先级越高,同一非支配层内拥挤距离越大的网络优先级越高,并将排序后的网络优先级保留至档案容量上限;边界网络的拥挤距离取无穷大并优先保留,同层网络的拥挤距离相同时,到对应目标组理想点的归一化距离较小者优先;所述效益理想点由当前效益档案第一非支配前沿中推进能耗的最小值和三维机动代价的最小值共同确定,所述安全理想点由当前安全档案第一非支配前沿中地面人员伤亡风险的最小值和噪声暴露的最小值共同确定,候选网络到相应理想点的归一化距离由对应两项目标在当前第一非支配前沿的取值范围内归一化后计算;同时维护协商候选档案ab和四项目标记录档案a4,ab用于保存能够进入双方比较和代表网络选择的完整可行网络,a4用于记录推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四项最小化目标的联合非支配关系和总体权衡,不替代ae和as各自的排序依据;

28、信息素按实际状态转移e及目标类别分别存储,更新关系为:

29、(2),

30、其中,表示第g个蚁群迭代结束前搜索方p在实际状态转移e上的信息素强度;p∈{e,s},e表示效益方,s表示安全方;表示搜索方p的信息素挥发率;表示第g个蚁群迭代中对实际状态转移e的本代沉积量;实际三维共识信息素采用独立的信息素记忆、强度上限和挥发率;

31、每一蚁群迭代结束后,先对本代访问过的实际状态转移实施批量局部更新并执行挥发,再由效益方本代精英和效益档案ae中的稀疏优质网络对效益方信息素沉积,由安全方本代精英和安全档案as中的稀疏优质网络对安全方信息素沉积;其中,效益方本代精英是在当代可行完整航路网络中,按照推进能耗和三维机动代价进行非支配排序后选出的网络;安全方本代精英是在当代可行完整航路网络中,按照地面人员伤亡风险和噪声暴露进行非支配排序后选出的网络;历史档案中的稀疏优质网络按照非支配层级编号从小到大、同层拥挤距离从大到小的顺序选取;尚未形成完整可行网络时,仅允许已经通过飞行高度、建筑净空、爬升下降角、偏航角、端点要求以及不同起讫航路间隔检查的局部起讫航线,以低于完整可行网络沉积量的预设比例提供构造线索;不可行完整航路网络不得进入ae、as、ab或a4。

32、步骤4包括:

33、实际三维共识检测仅比较效益档案ae第一非支配前沿和安全档案as第一非支配前沿中,同一起讫航线、同一航段序号对应的两条实际三维中心线航段;当两条实际三维中心线航段的方向差不大于方向容差、水平间距不大于航路包络容差、高度差不大于高度容差,并且沿线具有正的重叠长度时,将重叠部分判定为实际三维共识;效益父网络从效益档案ae第一非支配前沿中选取,同一前沿内优先选择拥挤距离较大的网络,拥挤距离相同时选择到由推进能耗和三维机动代价共同确定的效益理想点的归一化距离较小的网络;安全父网络从安全档案as第一非支配前沿中选取,同一前沿内优先选择拥挤距离较大的网络,拥挤距离相同时选择到由地面人员伤亡风险和噪声暴露共同确定的安全理想点的归一化距离较小的网络;

34、平面交叉、动作编码相同但实际位置不同、位于不同高度或属于不同od航线的航段均不构成共识;

35、由实际三维重叠长度、效益父网络在效益档案ae中的前沿质量和安全父网络在安全档案as中的前沿质量共同确定共识信息素沉积量;共识信息素采用独立强度上限,以防止共识信息素覆盖效益方和安全方各自的信息素,并在每一蚁群迭代按独立挥发率衰减,未持续获得效益档案和安全档案优质前沿共同支持的偶然重叠随迭代衰减;

36、当效益档案ae和安全档案as均形成由完整可行网络构成的第一非支配前沿后,将记录的同一起讫航线、同一航段序号、方向差、水平间距和高度差均在容差内且具有正重叠长度的航段端点作为共识锚点,并将相邻且连续的实际三维共识航段合并为共识区间;同一起讫航线中除共识区间以外的连续航段构成非共识区间;

37、由从效益档案ae第一非支配前沿选取的效益父网络和从安全档案as第一非支配前沿选取的安全父网络生成协商子代:在共识区间保留所选效益父网络与所选安全父网络在同一起讫航线、同一航段序号处实际三维重叠的共同航段,在非共识区间按区间继承效益父网络或安全父网络,并仅在相容锚点处切换;所述相容锚点是同一起讫航线中,共识区间与非共识继承区间边界处、在效益父网络和安全父网络中具有相同序号j的对应控制点,所述对应控制点的水平距离不大于航路包络容差、高度差不大于高度容差,并且效益父网络对应控制点和安全父网络对应控制点的高度差以及切换后的相邻航段方向与高度变化,均经连续高度投影后满足偏航角、最大爬升角、最大下降角和规划区域边界、静态及临时禁飞区、非关联起降点保护区、建筑净空、允许飞行高度、起讫端点以及不同起讫航路之间的水平和垂直安全间隔约束;协商子代不是第三个独立种群,独立依据本方信息素和启发式信息构造的效益蚂蚁或安全蚂蚁称为独立构造蚂蚁;协商子代与独立构造蚂蚁均接受相同的连续高度投影、规划区域边界、禁飞区、起降点保护区、建筑净空、飞行高度、机动性能和航路间隔校验,并分别计算推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四项最小化目标,只有在效益方或安全方排序中保持竞争力时才进入相应档案。

38、步骤5包括:

39、达到预设迭代次数、评价预算或收敛停止条件并完成最后一次效益档案和安全档案更新后,先在完整网络蚂蚁的决策空间和解码后的实际三维航路空间中,查找效益档案ae第一非支配前沿与安全档案as第一非支配前沿指向同一完整航路网络的共同集合;若共同集合非空,则从共同集合中选择效益方归一化损失和安全方归一化损失的较大值最小的网络;若共同集合为空,则从已经通过完整校验且来自ae、as、ab或a4的候选完整航路网络中,依次根据按照推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四项最小化目标共同进行非支配排序得到的联合非支配层级,以及候选网络在ae和as对应目标组上的非支配层级进行筛选;排除在推进能耗和三维机动代价所构成的效益目标组,或者在地面人员伤亡风险和噪声暴露所构成的安全目标组上,归一化损失超过预设阈值或对应非支配层级高于预设层级的完整航路网络,再对剩余候选计算档案相对满意度,并按式(3)确定平衡代表网络:

40、x*=argmax(x∈pb)min{se(x),ss(x)}(3),

41、其中,pb为通过完整可行性、联合非支配层级和效益档案与安全档案层级筛选后的协商候选集合,se(x)和ss(x)分别为候选网络x对效益方的归一化满意度和对安全方的归一化满意度;该规则最大化较弱一方的满意度,仅在效益档案ae第一非支配前沿与安全档案as第一非支配前沿无共同网络时启用;x*表示最终选出的平衡代表网络;完整可行性是指全部网络级硬约束均通过;联合非支配层级是指按照推进能耗、三维机动代价、地面人员伤亡风险和噪声暴露四项最小化目标共同进行非支配排序得到的层级;式(3)采用离散卡莱—斯莫罗丁斯基协商选择规则,选择min{se(x),ss(x)}最大的候选网络;两个以上候选的最小满意度之差不超过预设数值精度时,依次比较效益方满意度与安全方满意度的差值、两方满意度之和及上述联合非支配层级;

42、初始规划采用冷启动蚂蚁数量和评价预算,并保存经步骤5选定且供审核、仿真或发布使用的平衡代表网络作为已发布网络,保存初始规划形成的效益档案ae、安全档案as、协商候选档案ab和四项目标记录档案a4,以及生成已发布网络时采用的环境快照作为基准环境快照;运行期间周期性接收新的风险场和禁飞区状态,先在当前环境快照下复核已发布网络的完整可行性,再按式(4)判断是否触发重规划:

43、trigger(t)=[δr(t)≥θr]∨[δz(t)≥θz]∨[vjw(t)>ε](4),

44、其中t表示当前监测时刻;trigger(t)表示时刻t是否触发重规划;δr(t)表示当前风险场相对于基准环境快照风险场的归一化变化量;δz(t)表示当前禁飞区或空域限制相对于基准环境快照中禁飞区或空域限制的几何变化量;θr表示风险场变化触发阈值;θz表示禁飞区或空域变化触发阈值;vjw(t)表示已发布网络在当前环境快照下的约束违反量;ε表示可行性数值容差。

45、步骤5中,当δr(t)≥θr、δz(t)≥θz、vjw(t)>ε中的任一条件成立时启动热重规划;否则,仅在新环境下复核现有网络的可行性和目标值;热重规划采用可独立配置的蚂蚁数量和评价预算,最近一次有效规划形成的ae、as、ab和a4构成旧档案;将旧档案中经新环境复核仍可行的网络作为保留种子,对受影响起讫航线或区段进行扰动,并补充重新构造的网络;本轮信息素重新初始化;完成后生成新的时间标识、网络版本及校验报告;所述热重规划是相对于冷启动初始规划的重规划过程。

46、本发明还提供了一种电子设备,包括处理器和存储器,所述存储器存储有程序代码,当所述程序代码被所述处理器执行时,使得所述处理器执行所述的方法的步骤。

47、本发明还提供了一种存储介质,存储有计算机程序或指令,当所述计算机程序或指令在计算机上运行时,执行所述的方法的步骤。

48、有益效果:本发明以完整航路网络作为一次规划和评价的基本对象,使建筑净空、禁飞区、起降点保护以及不同od之间的航路间隔在同一环境快照下统一校验,可减少单线分别生成后因组合冲突而反复修补的情况。效益方与安全方保留各自的非支配前沿,实际三维共识只强化双方持续共同认可的同od航段,协商子代仍需经过双方原有排序和完整约束检验,因而运营主体能够核对能耗与机动表现,管理主体能够核对人员风险、噪声和空域约束,并追溯最终网络相对于双方前沿的选择依据。输出的中心线、连续高度剖面、航路包络、目标值、校验结果和环境版本可直接接入规划审核与仿真验证流程,适用于城市物流配送、垂直起降短途载运和应急保障等固定或周期性航路网络的方案生成。

49、在运行维护阶段,本发明根据风险场和临时禁飞区的变化程度区分“复核现网”和“触发重规划”:环境变化未达到阈值时不重复执行完整搜索,达到阈值时则利用经新环境验证的旧网络和档案开展热重规划,并形成新的航线网络。该处理方式既保留未受影响航段的既有规划信息,又使受道路车流热点、临时活动空域限制或局部空域解除影响的航段能够及时更新,从而为低空运行平台提供从初始建网、双方审核到动态维护的连续技术支撑。