一种旋翼无人机机群在多约束条件下自主协同机载计算的3D全覆盖搜索软件的制作方法

一种旋翼无人机机群在多约束条件下自主协同机载计算的3d全覆盖搜索软件
1.技术领域
1.本技术属于中小型旋翼无人机集群智能领域中的一块，即：旋翼无人机集群在多约束条件下，依靠机载计算、自主、协同、3d全覆盖搜索(3d-cpp)的航迹规划。
2.

背景技术：

2.多约束条件下，旋翼uavs、陌生(室内)环境、无gps、依靠视觉感知3d密集环境、220v电力缺失、去中心化、面向未来战争的3d cpp问题，有很多研究要做。
3.由于单个中小型无人机存在以下缺点：载荷能力有限、低功耗、计算能力有限等，难以支持其独立完成任务。所以，中小型无人机朝着轻量级、低成本、协同集群的趋势发展。
4.美国空军2016年发布《小型无人机系统(suas)飞行规划2016-2036》
1.，分析了小型无人机的优势和定位，从战略层面肯定了中小型无人机系统的前景和价值
2.。
5.但是，依据美国空军2005年发布《无人机系统线路图2005-2030
3.》的无人机自主等级，人类目前还没有实现“10级完全自主集群”技术
[4][5][6][7]
。
[0006]
单机自主：1级(遥控引导)、2级(实时故障诊断)、3级(故障自修复与飞行环境自适应)和4级(航路实时重规划)。
[0007]
多机自主：5级(多机协同)、6级(多机战术重规划)和7级(多机战术目标)。
[0008]
集群自主：8级(分布式协同控制)、9级(集群战略目标)和10级(完全自主集群)。协同集群uavs的组织方式有两种：集中中心化、分布式去中心化。
[0009]
集中中心化：由一个中心服务器收集多uavs的信息并承担耗时的计算任务，如图1所示。但是，一旦中心服务器出现问题则代表任务失败。uav的反应速度受其到中心服务器的通信距离、服务器的计算速度影响。中心服务器往往体积较大、电力要求高、散热大。
[0010]
分布式、去中心化：没有地面中心服务器或者云端、边缘计算服务器，仅有集群uavs。每个uav仅依靠机载有限的自主决策与局部的感知、互相通信能力，达到集群个体间无中心式地协同、轻量化集群自主行为，如图2所示。
[0011]
分布式、去中心化的多uavs组织方式具有不可忽视的优势和应用价值，比如：
[0012]
(1)在相同通信能力下，搜索范围比集中式更广、更灵活、计算耗时更少
[6]
。
[0013]
(2)由于没有中心服务器，战时士兵携带方便、对电力要求也较少，便携充电电池即可。
[0014]
而集中式、大型服务器却意味着必须找到220v供电场所，并且散热高、噪声大。
[0015]
然而，在面向实战、面向未来、以及严酷战场环境约束条件下，多uavs分布式、去中心化的集群自主智能仍然面临很大的挑战。目前国内外学术界对多uavs去中心化集群智能的研究成果非常少，并没有完全解决此类问题
[4][5][6]
。
[0016]
本专利目的：
[0017]
本专利旨在填补国内外对这一背景问题的工程、研究空白。针对多约束环境，无gps、陌生环境、缺乏220v电力支持、uavs数量变化、待搜索目标数量未知、缺乏遥控能力、超
低空3d环境、没有地面或者云端服务器的情况下，依靠uavs机载gpu并行计算，实现去中心化、自主协同地3d全覆盖航迹规划(3d-cpp)。
3.

技术实现要素：

[0018]
本发明基于目前最新的计算机视觉技术、双目相机和惯性导航装置(imu)、端到端5g无线通信术，提出：
[0019]
多uavs以数据驱动的、去中心化、机载gpu并行3d-cpp算法和软件。
[0020]
这是因为分布式、去中心化组织的uavs集群，在实现了去中心化协同感知3d环境之后，每个uav需要以去中心化的方式、单独规划其3d航迹，最终uavs集群依据特定的能量函数，协同覆盖搜索全部的空间。
[0021]
这项技术关注多uavs非编队飞行、陌生环境下的3d-cpp，主要包含两个方面：
[0022]
(1)全覆盖搜索的视点(view-points)计算；
[0023]
(2)遍历现有视点、新增视点的航迹规划。
4.附图说明
[0024]
图1：集中中心化的多uavs组织方式。
[0025]
图2：依靠端到端5g通信、分布式去中心化的多uavs组织方式。
[0026]
图3：本发明整体功能流程方案
[0027]
图4：将3d空间分割成均等、不重叠cell，组成gpu 3d cellular matrix并行计算模型。
[0028]
图5：由于远景、近景的2d图像分辨率不同，本发明采用梯度大、小视点的方法，构建分级的梯度3d cpp航迹。
[0029]
图6：不同航迹步长下的3d cpp结果。左图：欧式距离为步长；右图：方格之间的距离为步长。
[0030]
图7：为每个cell分配一个gpu线程(左图信号符)，计算cell的航迹属性。右图为方格可供uav移动的自由度，黑色方格为无人机不能穿越的障碍物方格。
5.具体实施方式
[0031]
本发明基于目前最新的计算机视觉技术、双目相机和惯性导航装置(imu)、端到端5g无线通信术，解决基于机载gpu并行计算的、旋翼多visual-uavs去中心化3d协同全覆盖航迹规划。
[0032]
具体实施整体功能流程如图3所示。项目将多uavs去中心化协同飞行分为两个阶段，起飞阶段和自由飞行阶段，两个阶段的不同点主要体现在去中心化的实现上。
[0033]
本专利关键技术：多uavs以数据驱动的、去中心化、机载gpu并行3d-cpp算法。
[0034]
这项技术关注多uavs非编队飞行、陌生环境下的3d-cpp，主要包含两个方面：
[0035]
(1)全覆盖搜索的视点(view-points)计算；
[0036]
(2)遍历现有视点、新增视点的航迹规划。
[0037]
已有的文献调研中，学者们将3d-cpp转化为tsp问题求解，比如粒子群算法、蚁群算法、lkh-tsp算法等。但是，这类高层算法又包含了基础算法、底层算法(比如，3d最近邻域
搜索算法)，以及需要考虑对新增视点的处理。
[0038]
所以，本发明首先需要构建一个能够实现多数基础和底层算法的gpu大规模并行的载体，用以实现多uavs在机载gpu端并行计算的3d-cpp。
[0039]
项目选择申请人2021年提出的gpu 3d cellular matrix模型，用以实现3d-cpp的相关并行算法，如图4所示。
[0040]
gpu 3d cellular matrix的特性有：
[0041]
给每个cell分配一个线程，可以单独进入邻域cell读写数据；
[0042]
给每个离散3d点分配一个线程，可以进入其所在的cell读写数据；
[0043]
以每个离散3d点为中心，可以将空间分割为24面锥体。
[0044]
本发明基于多uavs去中心化、双目视觉的3d环境感知、以及gpu 3d cellular matrix，对3d-cpp问题涉及的两个方面，分别进行基于机载gpu的并行计算研究：
[0045]
5.1多uavs去中心化、机载gpu并行计算航迹视点；
[0046]
5.2以数据驱动的多uavs去中心化、机载gpu并行3d-cpp算法。
[0047]
以下分别介绍：
[0048]
5.1多uavs去中心化、机载gpu并行计算航迹视点(view-points)
[0049]
计算3d航迹视点的方法，需要依据相机的参数(比如覆盖面)、搜索任务的目标(比如沿路搜索、进入楼内、绕开树木、大楼逐层搜索)、视点覆盖范围(比如，两块大石头的缝隙)等因素，进行计算。
[0050]
本发明使用2d双目图像进行3d环境感知的优点，也在于能够通过2d图像快速、智能的标记环境物体，比如快速识别场景内的大石、楼梯、汽车、遮挡空间等，进而有助于产生智能的3d视点。
[0051]
本发明依据2d图像目标识别、3d深度信息、以及gpu 3d cellular matrix，实现数据驱动的、gpu并行uav航迹视点生成算法。主要分为两个部分：
[0052]
(1)单uav在进行双目图像感知3d环境后，基于2d目标识别、3d深度信息的航迹视点生成算法；
[0053]
(2)单uav、多uavs图像拼接过程中，航迹视点的筛选，比如合并、删除。
[0054]
技术路线：
[0055]
《《《3d mesh生成》》》：基于本发明做2d图像拼接时将图像转化为2d mesh，在双目计算获取到3d深度信息后，可以将其轻松转换为3d mesh；
[0056]
《《《3d目标识别》》》：基于2d图像的目标识别技术，对3d物体进行标记；
[0057]
《《《单uav生成视点》》》：基于单uav、单目图像的3d mesh、3d cellular matrix、在目标区域内、给每个3d cell分配线程，并借鉴shang et al.2020年将三角面与相机参数结合的方式，生成当前cell内3d mesh的航迹视点。
[0058]
《《《多uavs图像拼接时的视点融合》》》：在多uavs图像拼接过程中，同时对重叠区域3d mesh对应的视点进行合并、删减。
[0059]
《《《梯度大、小视点》》》：由于多uavs飞行过程中，对环境的拍照随着距离更近、图像更清晰、3d空间更细化，所以项目提出：
[0060]
嵌套的、梯度大、小视点生成算法：
[0061]
uav远景时，生成大视点，依据大视点计算3d cpp航迹；
[0062]
uavs近景时，由于细节的出现，生成小视点，并共享给当前所有uavs，此时依据大小视点计算3d cpp航迹，如图5所示。
[0063]
5.2以数据驱动的多uavs去中心化、机载gpu并行3d-cpp算法
[0064]
在上一小节产生场景内3d视点后(大、小视点)，这一小节需要实现多uavs去中心化协同的3d-cpp算法。
[0065]
算法输入：视点坐标、场景3d mesh、智能目标识别信息。
[0066]
算法输出：全覆盖所有视点的多uavs 3d航迹规划。
[0067]
一方面，项目考虑欧式空间距离最近的两个视点之间可能存在障碍物，所以，在按照tsp问题规划航迹时，不能仅仅依赖视点与视点的3d欧式距离、简化为欧式距离的3d tsp问题，如图6左图所示。同时，为了更快的飞行，3d-cpp也不能仅仅依赖cellular decomposition的cell为步长、按照相邻方格逐个方格飞行，如图6右图所示。
[0068]
另一方面，为了实现多uavs去中心协同，与文献中使用区域划分、每个区域分配给特定uav来实现去中心化的思路不同，本发明多uavs去中心的3d航迹规划，是以数据驱动的、不依赖区域划分、与uavs数量无关的方式进行。
[0069]
项目将3d-cpp算法的主体从uavs转换到3d航迹视点上。让视点选择路径，而不是让uavs选择视点。
[0070]
技术路线：
[0071]
本发明借鉴shang et al.2020年基于已知3d环境模型的多uav、集中化协同3d全覆盖航迹方法，主要解决以下两个问题：
[0072]
(1)单uav以视点出发的、局部区域、gpu并行3d-cpp流程；
[0073]
(2)多uavs去中心协同的3d-cpp。
[0074]
以下分别阐述：
[0075]
(1)单uav以视点出发的、局部区域、gpu并行3d-cpp流程
[0076]
考虑实际情况下，单个uav在局部区域内完成全覆盖搜索后，再飞往下一个区域。所以，本发明首先聚焦局部区域内、由视点相连的3d-cpp。
[0077]
输入：当前单uav感知的局部3d区域内的所有航迹视点；
[0078]
输出：当前单uav局部空间3d全覆盖航迹规划。
[0079]
技术路线：
[0080]
考虑单uav机载gpu计算、两个视点之间可能存在障碍物、以及将视点全覆盖看作tsp问题，项目借鉴shang et al.2020将3d cpp转换为求解3d tsp、dong et al.2020基于2d cell的最小生成树森林实现去中心化cpp、melo et al.2021基于3d空间分割的工作，本发明将同时基于3d cell、和梯度大小航迹视点，采用由底到高的策略，使用gpu并行计算求解多uavs在大场景、陌生环境下的梯度3d cpp。
[0081]
主要包含以下步骤：
[0082]
《《《安全空间相连：cell-based 3d最小生成树森林》》》在涵盖所有航迹视点的待搜索空间，基于3d cellular matrix，给每个cell分配线程，在无障碍、安全cell之间，构建3d无向最小生成树森林(cell-based 3d mst/msf)。
[0083]
《《《方格属性》》》：给每个cell分配线程，计算每个安全方格的飞行属性(飞行自由度、风扰、能耗、是否已经被搜索过等)，如图7所示：
[0084]
项目给每个cell分配线程，每个cell能独立进入邻域方格来判断自身方格属性，比如是否有障碍物、可以允许uav往哪个方向移动、危险系数、不确定因素概率(比如风)、依据uav的航程能耗代价、转弯代价等。
[0085]
《《《视点相连：view-points-based 3d最小生成树森林》》》在构建好的cell-based mst/msf上，给每个视点分配线程，依据树上距离，将所有视点按照两两cell-based mst/msf树上距离最短，相互连接，构建view-point-based msf/mst。
[0086]
《《《计算3d-cpp航迹》》》通过上述步骤，所有视点已经在安全空间相互连接，之后，可以按照christofides、或者启发式算法求解tsp问题生成3d-cpp。
[0087]
此时，项目构建3d-cpp的主要技术路线，已经成型。
[0088]
(2)多uavs去中心协同的3d-cpp
[0089]
经过上一步计算之后，多uavs在陌生3d环境下、去中心化协同、以及新增环境和uavs数量变化情况下的3d全覆盖航迹规划，就容易解决。
[0090]
同时，由于多uavs不断探索未知新环境，本发明多uavs协同3d cpp需要分为起飞阶段和飞行阶段，来实现去中心化协同：
[0091]
起飞阶段：
[0092]
假设有m架uavs处于相同起飞位置，初始全景地图已经在m架uavs之间共享。此时，将上一步计算《《《安全空间相连：cell-based 3d最小生成树森林》》》、《《《视点相连：view-points-based 3d最小生成树森林》》》时所生成m架局部航迹规划，分别分配给m架uavs。uavs即可起飞，按照预定路径全覆盖搜索。
[0093]
飞行阶段：
[0094]
在飞行阶段，多uavs位置不断变化。单uav不断将探索到新环境、新视点，通过多uavs组网，在所有组网的uavs之间共享。
[0095]
此时，为解决新增环境的航迹规划、以及不同uavs各自获取到的视点可能交叉、远近、相同等问题，本发明同样进行《《《安全空间相连》》》、《《《视点相连》》》计算，从每个新空间、每个新视点出发，与当前已有的空间和视点相连。当多uavs通过组网信息传递、完成视点的拼接融合之后，即可以解决此问题。比如，uav-a拍摄到新视点p可能离uav-b很近，而依照本发明所提算法，由于从新视点p出发生成的最小生成树与uav-b现有的最小生成树自动相连，所以uav-b自动地获取了搜索p的航迹规划。
[0096]
至此，项目构建多uavs去中心化协同3d-cpp的主要技术路线成型。
[0097]
[1]robert o.small unmanned aircraft systems(suas)flight plan：2016-2036[r].united states air force，2016
[0098]
[2]袁文.(2017).多无人机编队飞行与冲突规避方法研究(硕士学位论文，国防科技大学).
[0099]
[3]cambone s.unmanned aircraft system roadmap 2005-2030[r].office of the secretary of defence，2005
[0100]
[4]chung，s.j.，paranjape，a.a.，dames，p.，shen，s.，&kumar，v.(2018).a survey on aerial swarm robotics.ieee transactions on robotics，34(4)，837-855.
[0101]
[5]zou，d.，tan，p.，&yu，w.(2019).collaborative visual slam for multiple agents：a brief survey.virtual reality&intelligent hardware，1(5)，461-482.
[0102]
[6]yao，h.，&li，x.(2020).decentralized control of connected automated vehicle trajectories in mixed traffic at an isolated signalized intersection.transportation research part c：emerging techn0logies，121，102846.

技术特征：
1.使用申请人提出的gpu并行2d/3d cellular matrix模型用于gpu并行无人机路径规划计算。2.本发明提出的基于3d空间均等、不重叠分割的单无人机路径规划方式。3.本发明提出的基于3d空间均等、不重叠分割的、去中心化协同的多无人机路径规划方式。4.本发明提出的基于最小生成树森林/树、大小视点的梯度路径规划方式。

技术总结
在无GNSS的未知、超低空环境，以及多约束条件下，比如缺乏220v电力支持、无人机群(UAVs)数量变化、待搜索目标数量未知、缺乏遥控能力、没有地面或者云端服务器的情况下，实现“去中心化非编队飞行的低慢小同质视觉无人机群”协同“3D全覆盖航迹规划(3DCPP)”是集群自主智能的一个研究前沿。本专利以机载国产GPU在线并行计算为基础，提出多UAVs去中心化协同3DCPP的数据传递方案，并提出基于每架UAV机载单卡GPU，实现多UAVs去中心化、均衡协同的3DCPP构建方法。最终达到多UAVs低速飞行时的机载实时全覆盖搜索3D环境的目的。机载实时全覆盖搜索3D环境的目的。


技术研发人员：乔文豹
受保护的技术使用者：乔文豹
技术研发日：2022.10.27
技术公布日：2023/8/5