内存受限的微型无人机集群协作自主导航系统及方法

1.本发明属于地图导航与路径规划技术领域，特别涉及了嵌入式、自主导航、边缘计算、异构协作的技术领域，主要涉及了一种内存受限的微型无人机集群协作自主导航系统及方法。


背景技术：

2.近年来，无人机发展迅速，已经被广泛应用于灾难救援、军事侦察、农业探测等各个领域。无人机在各领域的价值已得到充分证明，可以在复杂、有害、危险的环境中代替人工作。为了适应更复杂的飞行环境，微型无人机的相关研究已成为最近的研究热点。相对于其他类型无人机，微型旋翼无人机可以垂直升降，对起飞和降落的环境要求不高；结构简单，体型相对较小，可以在复杂的狭小环境中工作；具有高机动性并且可以悬停，适用性广。
3.随着半导体技术的不断进步，目前市面上已经出现了很多尺寸不足10cm的微型无人机。微型无人机具备几点优势：(1)它的尺寸小，可以在狭窄复杂的空间完成任务；(2)它的基础成本较低，容易大规模部署；(3)在意外情况下，微型无人机对人的伤害较小。同时也有两点突出的劣势：(1)微型无人机的计算能力弱、内存小，无法部署高精度的自主导航算法；(2)微型无人机的电池容量低，续航时间较短。
4.单个无人机的自主导航已经得到了很充分的研究，最近的研究热点集中在了无人机集群的自主导航。对于自主导航这一任务来说，集群化也带来了几个优势：(1)可以共享协作，更快完成导航。无人机之间可以将自己的定位建图信息发送给其他无人机，这样每台无人机都可以以更快的速度完成对全局空间的地图构建，可导航的区域范围也因此得以迅速扩大。(2)可以能力异构，实现资源互补。基于开放的软件开发框架，搭载不同设备的无人机之间也可以顺利通信，这允许我们的集群中分布着能力异构的无人机。例如，出于无人机载荷的限制，无人机需要在激光雷达测距设备和更强的计算设备之间作出取舍，这样，搭载了激光雷达测距设备进行空间建图的无人机可以将自己无法完成的计算存储任务发送给搭载了更强的计算设备的无人机，实现资源互补。(3)可以动态组网，适应任务场景。自主导航能力是无人机集群完成其他任务的基础，集群可以根据所要完成的任务的种类及具体的场景灵活完成自身组网，集群内无人机的数目可以动态增减，单架无人机的状态变化不会影响集群的任务执行，集群的鲁棒性更高。
5.现有研究会采取计算卸载的方式将微型无人机无法完成的计算任务卸载给其他设备来完成，与不同的卸载模式可供选择，其中将计算卸载至云端，时效性性较差，会受网络波动的影响；将计算卸载至地面设备，会受到通信距离的制约，无法脱离外部设备，行动受限；因而，如果能够将计算卸载至集群内部其他的高性能无人机，则可以很好地弥补其他模式的缺点，也正利用了集群的特点，即集群内无人机可以能力异构，可以通信协作。


技术实现要素：

6.本发明正是针对现有技术中微型无人机难以负荷自主导航大规模数据计算的问
题，提供一种内存受限的微型无人机集群协作自主导航系统及方法，至少包括数据协作采集与处理模块、八叉树地图构建模块和快速自主导航模块，所述数据协作采集与处理模块至少包括激光测距无人机、边缘计算无人机和基站，用于测量障碍物及激光测距无人机自身位置信息，并通过边缘计算无人机对收到的障碍物距离信息、自身位置坐标及位姿信息进行预处理，计算得到障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标；八叉树地图构建模块接收数据协作采集与处理模块传输的位置坐标信息，使用改进的八叉树构建三维空间地图；快速自主导航模块采用基于随机采样的rrt*快速扩展随机树算法，根据八叉树地图构建模块获得的障碍物及空闲空间的坐标信息来进行路径规划，实现微型无人机集群协作的自主导航。
7.为了实现上述目的，本发明采取的技术方案是：内存受限的微型无人机集群协作自主导航系统，至少包括数据协作采集与处理模块、八叉树地图构建模块和快速自主导航模块，
8.所述数据协作采集与处理模块：至少包括激光测距无人机、边缘计算无人机和基站；其中，激光测距无人机包括进行测距的激光雷达测距扩展板及获取自身三维空间位置信息的红外定位扩展板；红外定位扩展板与基站交互获取激光测距无人机的三维坐标；
9.边缘计算无人机中包括边缘计算扩展板，用于接收和计算激光测距无人机获取的障碍物的绝对坐标及激光测距无人机当前位置坐标，并将数据发送至八叉树地图构建模块，用于八叉树地图构建；
10.所述八叉树地图构建模块：接收数据协作采集与处理模块传输的位置坐标信息，根据每次接收到的激光测距起点和终点的坐标信息后，对路径上的节点进行占据概率更新,并进行分割和剪枝工作，遍历八叉树节点，通过占据概率判断为障碍物/空闲空间，存储输出坐标信息；
11.所述快速自主导航模块：采用基于随机采样的rrt*快速扩展随机树算法，根据八叉树地图构建模块获得的障碍物及空闲空间的坐标信息来进行路径规划。
12.作为本发明的一种改进，所述数据协作采集与处理模块中的基站位于开放空间的四角位置；激光雷达测距扩展板对激光测距无人机前、后、左、右四个方向障碍物之间的距离进行测量。
13.作为本发明的一种改进，所述八叉树地图构建模块中，每个内存单元储存8个节点与1个整数next，整数next用于访问线形内存池中第next号单元，对内存单元进行划分，包括一个用于指示空闲单元开头的整数、一个用于指示占用单元开头的整数和next，在每个单元中存储下一个单元的位置。
14.作为本发明的另一种改进，所述八叉树地图构建模块中，每个节点仅由一个16位的无符号整数定义，前12位代表当前节点的8个子节点所对应内存单元在内存池中的位置，中间3位用十进制表示0-7，从小到大依次表示当前节点被占据的概率最低到最高，最后一位代表当前节点是否为叶节点。
15.作为本发明的另一种改进，所述快速自主导航模块中基于随机采样的rrt*快速扩展随机树算法具体为：从无人机当前位置开始利用随机采样函数在空闲空间中生成随机点，以搜索树上距离最近的节点为父节点向随机点生长得到新节点，并通过碰撞检测函数判断是否将其加入到搜索树中，当有新节点加入搜索树时，将其附近相邻的其他节点作为
潜在父节点，并遍历所有潜在父节点对搜索树进行重布线；重复采样、生长和重布线，最终将目标点加入到搜索树中，完成路径的规划。
16.作为本发明的又一种改进，所述通过碰撞检测函数判断是否将节点加入到搜索树中时，待检测随机节点距离任一障碍物所在占据空间距离超过两个空间单位。
17.为了实现上述目的，本发明还采取的技术方案是：一种内存受限的微型无人机集群协作自主导航方法，其特征在于，包括如下步骤：
18.s1:激光测距无人机通过激光雷达测距扩展板及红外定位扩展板测量障碍物及激光测距无人机自身位置信息，并通过边缘计算无人机对收到的障碍物距离信息、自身位置坐标及位姿信息进行预处理，计算得到障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标；
19.s2：输入激光测距的起点及终点坐标，边缘计算无人机根据障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标，使用改进的八叉树构建三维空间地图；
20.s3：边缘计算无人机根据激光测距无人机的路径规划请求报文，基于随机采样的rrt*快速扩展随机树算法，考虑空间内的静态与动态障碍物为激光测距无人机规划可行的飞行路径，返回路径规划响应报文。
21.作为本发明的一种改进，所述步骤s1中，激光测距扩展板获取无人机前、后、左、右四个方向的障碍物距离；红外定位扩展板与基站配合得到无人机在三维空间的坐标；无人机上的惯性传感器i mu得到无人机在三维坐标系下的姿态夹角；激光测距无人机将自己的编号、自身坐标及障碍物坐标组成建图信息报文在空间内广播，报文只广播一次。
22.作为本发明的又一种改进，所述步骤s2具体包括：
23.s21：输入激光测距的起点及终点坐标，根据激光测距起点和终点坐标计算激光穿过的空闲节点坐标；
24.s22：每次从八叉树的根节点开始更新，判断是否达到八叉树分辨率要求，如未达到则将八叉树对应节点分割为8个子节点，并依据坐标位置选取对应的子节点进行递归更新；
25.s23：判断子节点的占据概率是否相同，如果相同则将父节点的占据概率设置为该值并删除父节点的子节点集合，实现剪枝效果减少内存占用。
26.与现有技术相比，本发明具有的有益效果：
27.(1)在微型无人机上使用八叉树模型构建地图，占用的内存空间更少。
28.(2)对八叉树的经典实现做了优化，利用内存池、结构体位域等手段减小八叉树的内存空间占用，加快地图更新速度。
29.(3)在微型无人机上使用rrt*算法进行路径搜索，提高路径搜索的效率。
30.(4)优化路径搜索算法的碰撞检测函数，针对室内复杂场景规划出距离障碍物较远的飞行路径。
31.(5)在无人机集群内部署移动边缘计算节点即选用部分无人机承担边缘计算任务，消费其他用于激光测距的无人机所获取的地图构建信息。
附图说明
32.图1为本发明实施例1步骤s1中无人机姿态与角度解算示意图；
33.图2为本发明内存受限的微型无人机集群协作自主导航系统的数据交互图；
34.图3为本发明方法步骤s2中八叉树地图构建的流程图；
35.图4为本发明方法步骤s3中基于随机采样的rrt*快速扩展随机树算法的流程图。
具体实施方式
36.下面结合附图和具体实施方式，进一步阐明本发明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。
37.实施例1
38.内存受限的微型无人机集群协作自主导航系统，至少包括数据协作采集与处理模块、八叉树地图构建模块和快速自主导航模块。
39.所述数据协作采集与处理模块：至少包括激光测距无人机、边缘计算无人机和基站；其中，激光测距无人机包括进行测距的激光雷达测距扩展板及获取自身三维空间位置信息的红外定位扩展板；红外定位扩展板与基站交互获取三维坐标；基站位于开放空间的四角位置；激光雷达测距扩展板对激光测距无人机前、后、左、右四个方向障碍物之间的距离进行测量。
40.使用基于freertos的微型无人机平台并为其装配可以进行测距的激光雷达测距扩展板及可以获取自身三维空间位置信息的红外定位扩展板，在异构协作系统中被称为激光测距无人机。同时，再次使用该平台并为其装配具备高性能低功耗计算能力的边缘计算扩展板，在异构协作系统中被称为边缘计算无人机。在8m*8m的开放空间四角放置室内定位基站，无人机上的红外定位扩展板与基站交互获取三维坐标。在激光测距无人机上，可得到无人机自身三轴姿态、三维坐标及四个方向的障碍物距离作为原始数据存储在无人机板载处理器中。
41.根据四个方向上的激光传感器，无人机能够实时获取机身与前、后、左、右四个方向障碍物之间的距离信息，通过结合从无人机板载imu获取的机身row、yaw、pitch轴姿态信息，使用三维旋转矩阵，可以将不同激光束的长度转化为各方向的向量，结合从室内定位系统获取的机身x、y、z轴在世界坐标系下的位置信息，无人机能够将其与障碍物间的相对距离计算转化为世界坐标系下的障碍物的绝对坐标。
42.激光测距无人机得到障碍物在世界坐标系下的绝对坐标以及无人机当前位置坐标(组成建图信息报文)通过基于freertos操作系统的微型无人机提供的点对点接口，通过板载无线模块(使用2.4ghz频段进行广播通信)对整个集群广播，高性能边缘计算无人机接收到广播的坐标后，会将该报文通过基于串口通信协议发往计算扩展板，用于后续的八叉树建图。
43.所述八叉树地图构建模块用于接收数据协作采集与处理模块传输的位置坐标信息，根据每次接收到的激光测距起点和终点的坐标信息后，对路径上的节点进行占据概率更新,并进行分割和剪枝工作，遍历八叉树节点，通过占据概率判断为障碍物/空闲空间，存储输出坐标信息。
44.八叉树地图是一种压缩的、可随时更新的地图，其每个节点表示一个正方体积元素，分别有八个子节点代表内部八个小正方体。每次接收到的激光测距起点和终点的坐标信息后，对路径上的节点进行占据概率更新,并进行分割和剪枝工作。使用时，遍历八叉树
节点，通过占据概率判断为障碍物/空闲空间，存储输出坐标信息。
45.所述快速自主导航模块：采用基于随机采样的rrt*快速扩展随机树算法，根据八叉树地图构建模块获得的障碍物及空闲空间的坐标信息来进行路径规划。
46.为了以较高效率得到相对优化的可行路径，本系统的快速自主导航模块采用基于随机采样的rrt*快速扩展随机树算法来进行路径规划。从八叉树地图构建模块构建的改进的精简八叉树模型中得到占据空间以及空闲空间的坐标信息。从起始点开始利用随机采样函数在空闲空间中生成随机点，以搜索树上距离最近的节点为父节点向随机点生长得到新节点，并通过碰撞检测函数判断是否将其加入到搜索树中。当有新节点加入搜索树时，需将其附近一定半径范围内的其他节点作为潜在父节点，并遍历所有潜在父节点对搜索树进行重布线，以减少路径的代价。按上述步骤经多次采样、生长和重布线，最终可将目标点加入到搜索树中，完成路径的规划。
47.结合现有模型、算法与通信机制，分析多机协作自主导航过程中可能会存在的碰撞因素，为路径搜索算法增加轻量级的碰撞避免策略，分两步进行。分别是向外扩展占据空间以便使规划轨迹尽量远离障碍物以及中心化进行路径规划时考虑已规划路径对当前规划任务的影响。通过这两种策略避免无人机与静态障碍物及运动中的其他无人机发生碰撞。
48.如图2所示，图2显示了本系统的数据交互过程，激光测距无人机对外广播路径规划请求报文，路径规划请求报文包含待规划路径的起始点和终止点坐标。边缘计算无人机接收到路径规划请求报文后，在路径规划请求报文所指定的起始点及终止点之间找到一条可行路径，并广播路径规划响应报文。路径规划响应报文包含路径规划请求报文中两坐标间的一条可行路径。在广播通信机制下，激光测距无人机会接收到所有路径规划响应报文，还需通过规划路径的起始点坐标识别出与该测距无人机相匹配的路径规划响应报文，最终实现微型无人机集群协作的自主导航。
49.实施例2
50.内存受限的微型无人机集群协作自主导航方法，包括如下步骤：
51.s1:激光测距无人机通过激光雷达测距扩展板及红外定位扩展板测量障碍物及激光测距无人机自身位置信息，并通过边缘计算无人机对收到的障碍物距离信息、自身位置坐标及位姿信息进行预处理，计算得到障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标。
52.本实施例中使用crazyflie 2.1微型无人机平台并为其装配具备向前、后、左、右四个方向进行测距的激光雷达测距扩展板(multi-ranger deck)及可以获取自身三维空间位置信息的红外定位扩展板(lighthouse deck)，被称为激光测距无人机。同时，再次使用crazyflie 2.1微型无人机平台并为其装配具备高性能低功耗计算能力的边缘计算扩展板(ai deck)，被称为边缘计算无人机。在8m*8m的开放空间四角放置lighthouse定位基站，无人机上的lighthouse deck与基站交互获取三维坐标。在激光测距无人机上，可得到无人机自身三轴姿态、三维坐标及四个方向的障碍物距离作为原始数据存储在无人机板载处理器中。使用usb数据线连接无人机与pc，将编译后的固件烧录至激光测距无人机与边缘计算无人机的板载处理器，使用jtag数据线连接无人机与ai-deck，将编译后的用户程序烧录至ai-deck上的gap8处理器。
53.使用四个方向上的激光传感器，无人机能够实时获取机身与前、后、左、右四个方向障碍物之间的距离信息，如图1所示，通过结合从无人机板载imu获取的机身row、yaw、pitch轴姿态信息，与从lighthouse定位系统获取的机身x、y、z轴在世界坐标系下的位置信息，无人机能够将其与障碍物间的相对距离计算转化为世界坐标系下的障碍物的绝对坐标，具体计算步骤如下。
54.记无人机位置为各方向激光测距数据为l
front/back/left/right
，可得无人机前后激光束的向量表示左右激光束的向量表示但是由于无人机飞行中机身并非时刻水平，即激光束与水平面存在夹角，不能直接与p
drone
相加计算障碍物坐标，故需要根据无人机的姿态数据对障碍物坐标进行旋转修正。
55.记无人机姿态信息row轴角度为α，pitch轴角度为β，yaw轴角度为γ，根据三维旋转矩阵可得转矩阵可得故修正后的障碍物绝对坐标可以表示为p
final
＝r
row
×rpitch
×ryaw
×
p
raw
+p
drone
。
56.p2p、cpx通信协议的部署与数据传输流向的描述。数据协作采集与处理模块中包括一台装有ai-deck计算扩展板的边缘计算无人机，与多台装有vl53l1cx激光传感器的激光测距无人机，激光测距无人机在完成上述步骤后，会将得到障碍物在世界坐标系下的绝对坐标以及无人机当前位置坐标(组成建图信息报文)通过crazyflie提供的p2p接口对整个集群广播，高性能计算无人机接收到广播的坐标后，会将该坐标通过基于uart通信的cpx协议发往ai-deck计算扩展板，用于步骤s2的八叉树建图。同时，激光测距无人机可以向边缘计算无人机通过p2p协议广播路径规划请求，边缘计算无人机接受后会将该报文通过cpx协议发往机载ai-deck计算扩展板，ai-deck根据八叉树模型完成路径规划后会将路径组成路径规划响应报文通过cpx协议发往边缘计算无人机，无人机接受到后会通过p2p协议将该报文广播，发送请求的无人机即可接收到规划好的路径。
57.首先，描述采用p2p的无人机间通信。crazyflie提供的p2p通信以crazyflie提供的crtp协议作为协议层，其物理层采用板载nrf24l01无线模块，使用2.4ghz频段进行广播通信。介于p2p传输的各信息会被用于无人机的不同服务(如步骤s2中的八叉树地图部署与构建、步骤s3中的路径规划与导航)，p2p传输的数据包将包含用于区分服务的端口作为数据包的元数据。
58.其次，描述用于无人机板载stm32与gpa8(部署与ai-deck)通信的cpx协议(crazyfliepacketexchange protocol)。cpx协议是以uart作为协议层，能够提高数据包在mcu中路由效率的应用层协议。其优点包括以下两点：首先，通过在数据包的元数据中对数据包的发送者与接收者进行记录，提高数据包的路由效率，第二，通过在元数据中设置标记位对较大数据包进行拆分，并对当前传输状况拥堵与否进行判断，提高数据包传输的稳定性与效率。
59.s2：输入激光测距的起点及终点坐标，边缘计算无人机根据障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标，使用改进的八叉树构建三维空间地图；
60.八叉树地图octomap是一种内存占用较少、可动态更新的地图，非常适合于室内导航。如图3所示，建图程序首先会根据设置项初始化八叉树地图模型，然后循环输入激光测距的起点和终点坐标。在每一次循环中，先根据激光测距起点和终点坐标计算激光穿过的空闲节点坐标；接着，依次将激光测距终点即占据节点坐标和空闲节点坐标映射到八叉树中。具体做法是将八叉树种对应节点分割为8个子节点，判断分辨率是否达到要求即程序是否达到递归中止条件，如果没有则继续根据终点方向选取子节点进行递归更新；最后，为了节省内存空间的使用，在递归程序返回过程中，判断节点的8个子节点占据概率是否相同，如果相同则将父节点的占据概率更新为任一子节点的占据概率并删除它的子节点。
61.第一点，构建octomap。octreenode中存储的信息包括节点的占据概率log_odds，该空间节点的宽度width
octree
(表示该节点代表边长为width
octree
的正方体),该空间节点的坐标p
octreenode
，子节点childnode以及该节点是否为叶节点is_leaf。在octomap的构建过程中，首先需要确定的是八叉树生长范围，主要通过三个值确定，即树生成的中心center
octree
，八叉树的解析度resolution
octree
(每个最小体素的边长)以及八叉树的深度max_depth(八叉树最大分割的深度)，resolution
octree
和max_depth共同决定了整体空间的大小。易得整体空间为一个以center
octree
为中心点边长为width
octree
的正立方体，而octomap表示的整个空间同时也可以视作一个未经分割的octreenode。无人机获取p
final
后，随之获取的还有从无人机节点到激光测距终点节点经过路径的节点信息，在实际的构建当中，我们不仅需要更新激光测距终点对应节点的占据状态，还需要更新中间路径对应节点的空闲状态。我们根据无人机自身位姿和激光测距终点的坐标，计算俩者之间的空闲路径区域，再之后更新对应八叉树模型中节点的状态信息。
62.第二点，输出占据空间以及空闲空间的位置信息。遍历八叉树中is_leaf为true的叶节点，根据log_odds及确定的阈值断该节点为占据空间/空闲空间，存储障碍物/空闲空间对应的octreenode的位置信息p
octreenode
，最后将存储的占据空间以及空闲空间的位置信息进行输出。
63.为了高效利用微型无人机板载mcu极其有限的内存与运算资源，本实施例提出以下几点方案优化构建改进的精简八叉树模型。
64.第一点，自主设计内存池管理，提高存储效率。使用八叉树模型进行建图时涉及大量的节点创建与删除操作，介于直接对每个节点进行内存空间的申请与释放效率较低、难以在总体上对堆空间的占用情况进行把控，以及freertos的内存管理功能比较薄弱，本专利提出自己实现内存管理。首先使用malloc申请足够大小的线形内存空间作为存放八叉树节点的内存池，由于八叉树模型中节点以八个为一组成组出现，每个内存单元将储存8个节
点与1个整数next，该整数用于访问线形内存池中第next号单元。通过以上设计，只需要一个用于指示空闲单元开头的整数、一个用于指示占用单元开头的整数和next，即可在线形空间中实现类似链表的高效增删操作，同时能够减少底层内存的申请释放频率，提高存储效率。
65.第二点，基于c语言的位域特性，精简设计八叉树节点的数据结构。介于受限的内存空间，本专利针对八叉树节点的表示进行了改进与精简。基于步骤2.1的分析，每个八叉树节点应该包含以下信息：本节点是否为叶节点、本节点空间被占据的概率与指向本节点八个子节点的链接。针对以上信息，本专利结合c语言中的位域特性完成了设计：每个节点仅由一个16位的无符号整数定义，前12位代表当前节点的8个子节点所对应内存单元在内存池中的位置，中间3位可用十进制表示0-7，从小到大依次表示当前节点被占据的概率最低(即代表该节点所表示空间为空)到最高(即代表该节点所表示空间被障碍物占据)，最后一位代表当前节点是否为叶节点。
66.基于以上设计，仅需70kb的内存空间即可储存一颗具有32768个节点的八叉树，即以4cm为精度至少能对1.28m3的空间进行建图，满足本专利内存受限的条件。
67.步骤3：边缘计算无人机根据激光测距无人机的路径规划请求报文，基于随机采样的rrt*快速扩展随机树算法，考虑空间内的静态与动态障碍物为激光测距无人机规划可行的飞行路径，返回路径规划响应报文。
68.如图4所示，从步骤s2所构建的改进的精简八叉树模型中得到占据空间以及空闲空间的坐标信息；从起始点开始，利用随机采样函数在空闲空间中生成随机点x
rand
；在搜索树中寻找距离x
rand
最近的节点x
near
，计算x
near
与x
rand
之间的距离，判断该距离是否大于设定的步长u；如果距离不大于给定的步长u，则连接x
near
和x
rand
，在x
rand
处生成新节点x
new
；否则，从x
near
向x
rand
移动步长u后得到新节点x
new
；通过碰撞检测函数f
crash
判断是否将x
new
加入到搜索树中(碰撞检测成功时加入)。当有新节点x
new
加入搜索树时，为了尽量减小路径的代价，需要对搜索树进行重布线，具体方法如下：以x
new
为圆心，将其附近一定半径范围内的所有节点作为潜在父节点x
prent[i]
；依次以x
parent[i]
作为x
new
的父节点，计算总路径的代价cost
new
；将计算结果与原先总路径的代价cost
old
进行比较，若cost
new
比cost
old
小，则通过碰撞检测函数判断是否将x
parent[i]
作为x
new
的父节点(碰撞检测成功时将x
parent[i]
作为x
new
的父节点)；遍历所有潜在父节点x
parent[i]
后得到重布线的搜索树。
[0069]
按上述步骤经多次采样、生长和重布线，最终可将目标点加入到搜索树中，完成路径的规划。
[0070]
寻路过程中的碰撞避免策略。结合现有模型、算法与通信机制，分析多机协作自主导航过程中可能会存在的碰撞因素，为路径搜索算法增加轻量级的碰撞避免策略，分两步进行。
[0071]
首先，向外扩展占据空间以便使规划轨迹尽量远离障碍物。为了减弱原始数据误差对障碍物占据空间描述的影响以及无人机在障碍物周围运动时不规则的气流对无人机位姿稳定的干扰，在路径搜索算法中，将每个已知为占据的体素周围的体素也置为占据，即对碰撞检测函数f
cras h
做修改，待检测随机节点x
new
需要距离任一占据空间距离超过两个空间单位才能提高检测，形成新的碰撞检测函数f
′
cras h
。使得算法规划出的路径可以距离障碍物的距离较远，避免出现过于贴近障碍物的飞行轨迹。
[0072]
其次，中心化进行路径规划时考虑已规划路径对当前规划任务的影响。因为空间地图模型的更新频率不能及时对动态飞行中的无人机作出相应，会带来多架无人机的飞行轨迹在时空顺序上存在重叠的问题。已收到规划路径的激光测距无人机在沿着航点飞行时会继续广播自身位置，边缘计算无人机在收到信息后会判断出激光测距无人机的飞行进度，将已经飞过的航点设置为空闲状态，将暂未经过的航点设置为占据状态。
[0073]
通过这两种策略避免无人机与静态障碍物及运动中的其他无人机发生碰撞。
[0074]
由于本专利不能在一台无人机上同时实现激光测距和路径规划，故需要规定一套自主导航任务的请求与响应机制。具体的请求与响应机制如下：
[0075]
激光测距无人机对外广播路径规划请求报文。路径规划请求报文包含待规划路径的起始点坐标p
start1
和终止点坐标p
end
。边缘计算无人机接收到路径规划请求报文后，基于步骤s2中构建好的八叉树地图，在p
start1
及p
end
之间利用避免碰撞的路径规划算法找到一条可行路径。边缘计算无人机完成路径规划后广播路径规划响应报文。路径规划响应报文包含路径规划请求报文中两坐标间的一条可行路径。由于本专利采用p2p广播，故激光测距无人机接收到路径规划响应报文后还需比对报文中规划路径的起始点坐标p
start2
和自身当前坐标p
current
是否相同。只有当p
start2
＝p
current
时才能说明该路径规划响应报文是与该激光测距无人机匹配的。至此，完成一个自主导航任务的请求与响应过程。
[0076]
综上，本案提出了一种内存受限的微型无人机集群协作自主导航系统及方法，在资源能力异构的微型无人机间传输预处理过的激光束终点坐标，在具备边缘计算能力的无人机上构建八叉树地图，最后利用构建好的三维空间地图信息为无人机的自主导航规划飞行路径，实现一个自主导航系统。
[0077]
需要说明的是，以上内容仅仅说明了本发明的技术思想，不能以此限定本发明的保护范围，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰均落入本发明权利要求书的保护范围之内。

技术特征：
1.内存受限的微型无人机集群协作自主导航系统，其特征在于:至少包括数据协作采集与处理模块、八叉树地图构建模块和快速自主导航模块，所述数据协作采集与处理模块：至少包括激光测距无人机、边缘计算无人机和基站；其中，激光测距无人机包括进行测距的激光雷达测距扩展板及获取自身三维空间位置信息的红外定位扩展板；红外定位扩展板与基站交互获取激光测距无人机的三维坐标；边缘计算无人机中包括边缘计算扩展板，用于接收和计算激光测距无人机获取的障碍物的绝对坐标及激光测距无人机当前位置坐标，并将数据发送至八叉树地图构建模块，用于八叉树地图构建；所述八叉树地图构建模块：接收数据协作采集与处理模块传输的位置坐标信息，根据每次接收到的激光测距起点和终点的坐标信息后，对路径上的节点进行占据概率更新,并进行分割和剪枝工作，遍历八叉树节点，通过占据概率判断为障碍物/空闲空间，存储输出坐标信息；所述快速自主导航模块：采用基于随机采样的rrt*快速扩展随机树算法，根据八叉树地图构建模块获得的障碍物及空闲空间的坐标信息来进行路径规划。2.如权利要求1所述的内存受限的微型无人机集群协作自主导航系统，其特征在于：所述数据协作采集与处理模块中的基站位于开放空间的四角位置；激光雷达测距扩展板对激光测距无人机前、后、左、右四个方向障碍物之间的距离进行测量。3.如权利要求1所述的内存受限的微型无人机集群协作自主导航系统，其特征在于：所述八叉树地图构建模块中，每个内存单元储存8个节点与1个整数next，整数next用于访问线形内存池中第next号单元，对内存单元进行划分，包括一个用于指示空闲单元开头的整数、一个用于指示占用单元开头的整数和next，在每个单元中存储下一个单元的位置。4.如权利要求1所述的内存受限的微型无人机集群协作自主导航系统，其特征在于：所述八叉树地图构建模块中，每个节点仅由一个16位的无符号整数定义，前12位代表当前节点的8个子节点所对应内存单元在内存池中的位置，中间3位用十进制表示0-7，从小到大依次表示当前节点被占据的概率最低到最高，最后一位代表当前节点是否为叶节点。5.如权利要求1所述的内存受限的微型无人机集群协作自主导航系统，其特征在于：所述快速自主导航模块中基于随机采样的rrt*快速扩展随机树算法具体为：从无人机当前位置开始利用随机采样函数在空闲空间中生成随机点，以搜索树上距离最近的节点为父节点向随机点生长得到新节点，并通过碰撞检测函数判断是否将其加入到搜索树中，当有新节点加入搜索树时，将其附近相邻的其他节点作为潜在父节点，并遍历所有潜在父节点对搜索树进行重布线；重复采样、生长和重布线，最终将目标点加入到搜索树中，完成路径的规划。6.如权利要求5所述的内存受限的微型无人机集群协作自主导航系统，其特征在于：所述通过碰撞检测函数判断是否将节点加入到搜索树中时，待检测随机节点距离任一障碍物所在占据空间距离超过两个空间单位。7.使用如权利要求1所述系统的内存受限的微型无人机集群协作自主导航方法，其特征在于，包括如下步骤：s1:激光测距无人机通过激光雷达测距扩展板及红外定位扩展板测量障碍物及激光测距无人机自身位置信息，并通过边缘计算无人机对收到的障碍物距离信息、自身位置坐标
及位姿信息进行预处理，计算得到障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标；s2：输入激光测距的起点及终点坐标，边缘计算无人机根据障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标，使用改进的八叉树构建三维空间地图；s3：边缘计算无人机根据激光测距无人机的路径规划请求报文，基于随机采样的rrt*快速扩展随机树算法，考虑空间内的静态与动态障碍物为激光测距无人机规划可行的飞行路径，返回路径规划响应报文。8.如权利要求7所述的内存受限的微型无人机集群协作自主导航方法，其特征在于：所述步骤s1中，激光测距扩展板获取无人机前、后、左、右四个方向的障碍物距离；红外定位扩展板与基站配合得到无人机在三维空间的坐标；无人机上的惯性传感器imu得到无人机在三维坐标系下的姿态夹角；激光测距无人机将自己的编号、自身坐标及障碍物坐标组成建图信息报文在空间内广播，报文只广播一次。9.如权利要求7所述的内存受限的微型无人机集群协作自主导航方法，其特征在于：所述步骤s2具体包括：s21：输入激光测距的起点及终点坐标，根据激光测距起点和终点坐标计算激光穿过的空闲节点坐标；s22：每次从八叉树的根节点开始更新，判断是否达到八叉树分辨率要求，如未达到则将八叉树对应节点分割为8个子节点，并依据坐标位置选取对应的子节点进行递归更新；s23：判断子节点的占据概率是否相同，如果相同则将父节点的占据概率设置为该值并删除父节点的子节点集合，实现剪枝效果减少内存占用。

技术总结
本发明公开了一种内存受限的微型无人机集群协作自主导航系统及方法，至少包括数据协作采集与处理模块、八叉树地图构建模块和快速自主导航模块，所述数据协作采集与处理模块用于测量障碍物及激光测距无人机自身位置信息，并通过边缘计算无人机对收到的障碍物距离信息、自身位置坐标及位姿信息进行预处理，计算得到障碍物在世界坐标系下的绝对坐标及无人机当前位置坐标；八叉树地图构建模块接收数据协作采集与处理模块传输的位置坐标信息，使用改进的八叉树构建三维空间地图；快速自主导航模块采用基于随机采样的RRT*快速扩展随机树算法，根据八叉树地图构建模块获得的障碍物及空闲空间的坐标信息来进行路径规划，实现微型无人机集群协作的自主导航。无人机集群协作的自主导航。无人机集群协作的自主导航。


技术研发人员：许瑞文 张子艺 王智东 吴文博 刘晨锐 单冯
受保护的技术使用者：东南大学
技术研发日：2023.04.19
技术公布日：2023/8/1