1.一种多无人机协同自主探索方法，其特征在于，包括：
根据传感器数据构建三维占据栅格地图；
根据所述三维占据栅格地图，由多架无人机共同增量式构建动态拓扑图，期间，单架无人机向其它无人机发送自身动态拓扑图中增量式构建的部分；
单架无人机根据自身状态信息以及其它无人机状态信息在所述动态拓扑图上进行局部的维诺划分以及全局的维诺划分；
基于维诺划分的结果进行局部探索和全局探索。
2.根据权利要求1所述的多无人机协同自主探索方法，其特征在于， 所述根据传感器数据构建三维占据栅格地图的步骤，具体包括：
根据无人机上的机载传感器获取环境信息，所述机载传感器包括深度相机和/或激光雷达；
根据无人机的位姿信息得到世界坐标系下障碍物的位置；
根据所述环境信息和障碍物的位置构建所述三维占据栅格地图。
3.根据权利要求1所述的多无人机协同自主探索方法，其特征在于，所述动态拓扑图具体包括：
动态拓扑图由节点集合和连接节点的边集合组成，其中，动态拓扑图的节点集合，由无人机在经过位置留下的历史节点集合与可探索子区域节点集合组成，动态拓扑图的边集合为连接节点的边的集合，每条边保存连接两个节点的可通行路径以及路径长度。
4.根据权利要求3所述的多无人机协同自主探索方法，其特征在于，所述增量式构建具体包括：生成历史节点、生成可探索子区域节点以及多无人机间信息同步；
其中，生成历史节点的步骤具体包括：
从无人机当前位置开始在曼哈顿距离不超过的范围以内进行Dijkstra搜索；
当搜索范围内不存在历史节点，或者从当前无人机所在位置到搜索范围内任一历史节点的距离大于阈值时，在无人机当前位置生成一个新的历史节点并添加到；
当一个新历史节点生成时，Dijkstra搜索时产生的以新历史节点为根的“最短路径树”也被保存；
建立新历史节点与搜索范围内的已有历史节点的边，边的长度和路径通过“最短路径树”从已有历史节点位置递归回溯至新历史节点得到；
若新历史节点和其他历史节点的“最短路径树”的分支存在交集，通过从这些分支交汇处向两个历史节点递归回溯建立边，以进一步提高动态拓扑图中每个历史节点的度；
生成可探索子区域节点的步骤具体包括：
在进行探索任务以前，将整个待探索空间划分为个子区域，每个子区域对应一个唯一的序号；每个子区域的状态属于以下三种之一：“未探索”、“可探索”和“无法探索”；
探索每个子区域的视点，每个视点的状态属于以下三种之一：“未知”、“有增益”和“无增益”；
一开始将所有子区域状态初始化为“未探索”，将视点状态初始化为“未知”，一旦某个子区域内的体素被探索，则将子区域状态由“未探索”切换为“可探索”，并添加至；
检测“可探索”子区域的视点集内的每个视点：计算所有无碰撞的视点的视锥覆盖的地图边界面积，若覆盖的地图边界面积大于阈值则将视点状态切换为“有增益”，否则切换为“无增益”；
将“有增益”的视点连接到距离最近的历史节点，对比一个可探索子区域节点的视点集的所有最短的回溯路径，选择最短的路径，建立可探索子区域节点和对应历史节点的边；
如果一个连接历史节点的视点的状态切换为“无增益”，则删除视点与历史节点相连接的边；
当一个“可探索”子区域的探索率超过阈值，则将该子区域状态切换为“无法探索”；
多无人机间信息同步的步骤具体包括：
当动态拓扑图的结构发生变化时，将新生成的历史节点、可探索子区域节点和视点集的状态发送给其他无人机；将动态拓扑图中直接与无人机相连的节点与无人机的距离发送给其它无人机，以便后续维诺划分。
5.根据权利要求1所述的多无人机协同自主探索方法，其特征在于，所述局部的维诺划分具体包括：
利用动态拓扑图获取第架无人机局部的局部图；其中，局部图的节点由历史节点集，可探索子区域节点集和无人机节点集组成，即，历史节点集是由与第架无人机直接连接的历史节点组成，由直接与第架无人机直接连接的可探索子区域节点和与第架无人机间接连接的可探索子区域节点组成，由与直接与和相连的无人机组成；
局部图中和间的边为动态拓扑图的边，而与这些节点的边通过Dijkstra搜索得到，或者由其他无人机传输的局部信息得到；
以为起点进行平行Dijkstra搜索，得到局部图的维诺划分。
6.根据权利要求1所述的多无人机协同自主探索方法，其特征在于，所述全局的维诺划分具体包括：
利用动态拓扑图获取全局图，其中，，为动态拓扑图的所有历史节点组成的集合，为所有无人机组成的节点集合，为节点的边，通过动态拓扑图和无人机间通信获得；
以为起点进行平行Dijkstra搜索，得到全局图的维诺划分。
7.根据权利要求1所述的多无人机协同自主探索方法，其特征在于，所述局部探索具体包括：
基于局部维诺划分的结果采用贪心策略进行探索。
8.根据权利要求1所述的多无人机协同自主探索方法，其特征在于，所述全局探索具体包括：
若某架无人机的全局维诺划分结果中的历史节点连接有可探索子区域，则选择距离自身最近的可探索子区域节点进行探索；
若某架无人机的全局维诺划分结果中的历史节点没有连接可探索子区域，则分担其它无人机的探索任务。
9.一种多无人机协同自主探索装置，其特征在于，包括：
存储器，用于存储程序指令；
处理器，用于调用所述存储器中存储的所述程序指令以实现如权利要求1至8中任一项所述的多无人机协同自主探索方法。
10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质存储有程序代码，所述程序代码用于实现如权利要求1至8中任一项所述的多无人机协同自主探索方法。

技术领域
[0001]本发明涉及无人机导航领域，具体而言，涉及一种多无人机协同自主探索方法、装置和存储介质。
背景技术
[0002]多无人机协同自主探索是机器人领域的一个热点研究问题。无人机自主探索任务要求无人机自主选择未探索区域、探索目标点，并利用搭载传感器进行信息收集和地图构建，在尽可能短的时间内完成对未知环境的建图。为提高探索效率，可以将自主探索拓展到多无人机协同探索。目前，低效的探索信息同步和不合理的任务分配仍然是现有多无人机自主协同探索所面临的挑战。为了协调多无人机自主探索，无人机间需要同步已探索地图信息。当前多无人机自主探索方法中信息同步策略主要包括两大类，基于栅格地图的多机信息同步策略和基于拓扑图的信息同步策略。基于栅格地图的多机信息同步策略通过增量式地将栅格地图传输给其他无人机，以同步已探索地图信息，然而此类方法需要传输大量的数据，导致信息同步的延迟，进而降低探索效率。基于拓扑图的信息同步策略通过在已探索区域建立拓扑图并传输拓扑图信息，从而降低信息同步数据量。然而现有拓扑图通常要求节点间连线无障碍物，导致拓扑图相对稠密、节点的度低，进而导致在杂乱环境中需要传输大量数据和绕远路等问题。在实现本发明的过程中，申请人发现：多无人机自主探索中任务分配方法主要包括基于两两协调的分配方法和基于维诺划分的分配方法。两两协调的分配方法通过求解车辆路径规划问题最小化探索路径长度，但由于只考虑了两个无人机，其协调效率随无人机数量增加而下降。基于维诺划分的分配方法通过以无人机当前位置作为基点进行维诺划分，将未探索区域划分给所有无人机以避免重复探索相同区域。此类方法由于维诺划分直接在欧氏空间上进行而未考虑空间中的障碍物，无法保证分配给无人机的目标是距离无人机最近的，从而导致协同探索效率低下。
[0003]因此，如何高效且合理地分配探索任务，提高探索效率成为亟待解决的技术问题。
发明内容
[0004]本发明旨在至少解决现有技术或相关技术中存在的技术问题之一，公开了一种多无人机协同自主探索方法、装置和存储介质，在多无人机协同自主探索任务中，通过整合已探索子区域和可探索子区域信息动态构建可用于高效信息同步的动态拓扑图，并在动态拓扑图上进行维诺划分高效且合理地分配探索任务，降低通信量，提高探索效率。
[0005]本发明的第一方面公开了一种多无人机协同自主探索方法，包括：根据传感器数据构建三维占据栅格地图；根据三维占据栅格地图，由多架无人机共同增量式构建动态拓扑图，期间，单架无人机向其它无人机发送自身动态拓扑图中增量式构建的部分；单架无人机根据自身状态信息以及其它无人机状态信息在动态拓扑图上进行局部的维诺划分以及全局的维诺划分；基于维诺划分的结果进行局部探索和全局探索。
[0006]根据本发明公开的多无人机协同自主探索方法，优选地，根据传感器数据构建三维占据栅格地图的步骤，具体包括：根据无人机上的机载传感器获取环境信息，机载传感器包括深度相机和/或激光雷达；根据无人机的位姿信息得到世界坐标系下障碍物的位置；根据环境信息和障碍物的位置构建三维占据栅格地图。
[0007]根据本发明公开的多无人机协同自主探索方法，优选地，动态拓扑图具体包括：动态拓扑图由节点集合和连接节点的边集合组成，其中，动态拓扑图的节点集合，由无人机在经过位置留下的历史节点集合与可探索子区域节点集合组成，动态拓扑图的边集合为连接节点的边的集合，每条边保存连接两个节点的可通行路径以及路径长度。
[0008]根据本发明公开的多无人机协同自主探索方法，优选地，增量式构建包括：增量式构建具体包括：生成历史节点、生成可探索子区域节点以及多无人机间信息同步；
[0009]其中，生成历史节点的步骤具体包括：
[0010]从无人机当前位置开始在曼哈顿距离不超过的范围以内进行Dijkstra搜索；当搜索范围内不存在历史节点，或者从当前无人机所在位置到搜索范围内任一历史节点的距离大于阈值时，在无人机当前位置生成一个新的历史节点并添加到；当一个新历史节点生成时，Dijkstra搜索时产生的以新历史节点为根的“最短路径树”也被保存；建立新历史节点与搜索范围内的已有历史节点的边，边的长度和路径通过“最短路径树”从已有历史节点位置递归回溯至新历史节点得到；若新历史节点和其他历史节点的“最短路径树”的分支存在交集，通过从这些分支交汇处向两个历史节点递归回溯建立边，以进一步提高动态拓扑图中每个历史节点的度；
[0011]生成可探索区域节点的步骤具体包括：
[0012]在进行探索任务以前，将整个待探索空间划分为个子区域，每个子区域对应一个唯一的序号；每个子区域的状态属于以下三种之一：“未探索”、“可探索”和“无法探索”；探索每个子区域的视点，每个视点的状态属于以下三种之一：“未知”、“有增益”和“无增益”；一开始将所有子区域状态初始化为“未探索”，将视点状态初始化为“未知”，一旦某个子区域内的体素被探索，则将子区域状态由“未探索”切换为“可探索”，并添加至；检测“可探索”子区域的视点集内的每个视点：计算所有无碰撞的视点的视锥覆盖的地图边界面积，若覆盖的地图边界面积大于阈值则将视点状态切换为“有增益”，否则切换为“无增益”；将“有增益”的视点连接到距离最近的历史节点，对比一个可探索子区域节点的视点集的所有最短的回溯路径，选择最短的路径，建立可探索子区域节点和对应历史节点的边；如果一个连接历史节点的视点的状态切换为“无增益”，则删除视点与历史节点相连接的边；当一个“可探索”子区域的探索率超过阈值，则将该子区域状态切换为“无法探索”；
[0013]多无人机间信息同步的步骤具体包括：
[0014]当动态拓扑图的结构发生变化时，将新生成的历史节点、可探索子区域节点和视点集的状态发送给其他无人机；将动态拓扑图中直接与无人机相连的节点与无人机的距离发送给其它无人机，以便后续维诺划分。
[0015]根据本发明公开的多无人机协同自主探索方法，优选地，局部的维诺划分具体包括：利用动态拓扑图获取第架无人机局部的局部图；其中，局部图的节点由历史节点集，可探索子区域节点集和无人机节点集组成，即，历史节点集是由与第架无人机直接连接的历史节点组成，由直接与第架无人机直接连接的可探索子区域节点和与第架无人机间接连接的可探索子区域节点组成，由与直接与和相连的无人机组成；局部图中和间的边为动态拓扑图的边，而与这些节点的边通过Dijkstra搜索得到，或者由其他无人机传输的局部信息得到；以为起点进行平行Dijkstra搜索，得到局部图的维诺划分。
[0016]根据本发明公开的多无人机协同自主探索方法，优选地，全局的维诺划分具体包括：利用动态拓扑图获取全局图，其中，，为动态拓扑图的所有历史节点组成的集合，为所有无人机组成的节点集合，为节点的边，通过动态拓扑图和无人机间通信获得；以为起点进行平行Dijkstra搜索，得到全局图的维诺划分。
[0017]根据本发明公开的多无人机协同自主探索方法，优选地，局部探索具体包括：基于局部维诺划分的结果采用贪心策略进行探索。
[0018]根据本发明公开的多无人机协同自主探索方法，优选地，全局探索具体包括：若某架无人机的全局维诺划分结果中的历史节点连接有可探索子区域，则选择距离自身最近的可探索子区域节点进行探索；若某架无人机的全局维诺划分结果中的历史节点没有连接可探索子区域，则分担其它无人机的探索任务。
[0019]本发明的第二方面公开了一种多无人机协同自主探索装置，包括：存储器，用于存储程序指令；处理器，用于调用存储器中存储的程序指令以实现如上述任一技术方案的多无人机协同自主探索方法。
[0020]本发明的第三方面公开了一种计算机可读存储介质，该计算机可读存储介质存储有程序代码，程序代码用于实现如上述任一技术方案的多无人机协同自主探索方法。
[0021]本发明的有益效果至少包括：在多无人机协同自主探索任务中，通过整合已探索空间和可探索空间信息动态构建可用于高效信息同步的动态拓扑图，降低了通信量，并在动态拓扑图上进行维诺划分高效且合理地分配探索任务，提高了探索效率。具体地，本发明在拓扑图构建方面，不要求节点相互可视，大大提高了拓扑图的度；在多机通信方面，通过增量式发送稀疏的动态拓扑图，进而大大减小了多机间通信数据量；在任务分配时，不同于传统维诺划分方法在欧式空间进行划分，而是基于动态拓扑图进行维诺划分，将独立无交集的探索任务分配给每个无人机，进而保证了划分任务与对应无人机的最短探索路径。
附图说明
[0022]图1示出了根据本发明的一个实施例的多无人机协同自主探索方法的流程示意图。
[0023]图2示出了根据传统维诺划分的多无人机飞行示意图。
[0024]图3示出了根据本发明的一个实施例的多无人机协同自主探索方法的多无人机飞行示意图。
[0025]图4示出了根据本发明的一个实施例的多无人机协同自主探索装置的示意框图。
具体实施方式
[0026]为了能够更清楚地理解本发明的上述目的、特征和优点，下面结合附图和具体实施方式对本发明进行进一步的详细描述。
[0027]在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是，本发明还可以采用其他不同于在此描述的其他方式来实施，因此，本发明并不限于下面公开的具体实施例的限制。
[0028]如图1所示，根据本发明的一个实施例，本发明公开的多无人机协同自主探索方法包括：步骤S101，根据传感器数据构建三维占据栅格地图；步骤S102，根据三维占据栅格地图，由多架无人机共同增量式构建动态拓扑图；步骤S103，单架无人机根据自身状态信息以及其它无人机状态信息在动态拓扑图上进行局部的维诺划分以及全局的维诺划分；步骤S104，基于维诺划分的结果进行局部探索和全局探索。
[0029]在上述步骤101中，依据环境感知信息与位姿估计信息构建三维占据栅格地图：根据无人机上的环境传感器（如深度相机、激光雷达等）获取周围环境信息。进而根据无人机的位姿得到世界坐标系下障碍物的位置，为自主导航构建三维占据地图。
[0030]在上述步骤102中，基于地图信息，多无人机共同增量式构建动态拓扑图：动态拓扑图由节点集合和连接节点的边集合组成。其中动态拓扑图的节点集合，由无人机在经过位置留下的历史节点集合与可探索子区域节点集合组成。动态拓扑图的边集合为连接节点的边的集合，每条边保存连接两个节点的可通行路径以及路径长度。动态拓扑图通过各个无人机单体增量式构建：
[0031]1） 历史节点生成：从无人机当前位置开始在曼哈顿距离不超过的范围以内进行Dijkstra搜索。当满足以下两种情况之一时，在无人机当前位置生成一个新的节点并将该节点添加到：所搜索范围内不存在历史节点；从当前无人机所在位置到搜索范围内任一历史节点的距离大于阈值。当一个历史节点生成时，Dijkstra搜索时产生的以该历史节点为根的“最短路径树”也将被保存；建立该历史节点与搜索范围内的已有历史节点的边，边的长度和路径通过“最短路径树”从已有历史节点位置回溯得到；若该历史节点和其他历史节点的“最短路径树”的分支存在交集，通过从这些分支交集处向两个历史节点回溯建立边，以进一步提高历史节点的度。
[0032]2） 可探索子区域节点生成：在进行探索任务以前，将待探索空间均匀划分为一系列正方体子区域；每个子区域对应一个唯一的序号；每个子区域的状态属于以下三种之一：“未探索”、“可探索”和“无法探索”；探索每个子区域的视点集合通过以该子区域为中心，不同角度均匀采样得到，每个视点的状态属于以下三种之一：“未知”、“有增益”和“无增益”（通过到达“有增益”视点，无人机可完成对对应可探索子区域的探索）。探索初始化，所有子区域的状态为“未探索”，这些区域的视点集合中所有视点的状态为“未知”。一旦某个子区域内的体素被探索，该子区域的状态由“未探索”切换为“可探索”，并把该子区域作为可探索子区域节点加入。然后，检测该子区域对应的视点集的每个视点。具体而言，在该视点集中，计算所有无碰撞的视点的视锥覆盖的地图边界面积，若覆盖的地图边界面积大于阈值则将该视点的状态切换为“有增益”，否则切换为“无增益”。为了构建和的边，所有“有增益”的视点会尝试连接到距离该视点最近的历史节点。由于每个历史节点保留了“最短路径树”树，视点到历史节点的最短路径可以通过从视点所在未知回溯所有的“最短路径树”并选择最短的回溯路径，对比一个可探索子区域节点的视点集的所有最短的回溯路径，选择最短的路径，建立该可探索子区域节点和对应历史节点的边。如果一个连接历史节点的视点的状态切换为“无增益”，该视点连接历史节点的边将被删除。值得注意的是，可探索子区域最多只和一个历史节点相连。当一个可探索子区域的探索率超过阈值，则认为该子区域已被完全探索并将该探索子区域的状态切换为“无法探索”。
[0033]3） 多机间信息同步：为了快速同步动态拓扑图的构建，单架无人机只需要向其他无人机发送动态拓扑图增量构建的部分。具体而言，当动态拓扑图的图结构发生变化时，新生成的历史节点、可探索子区域节点和对应的视点集（对应的序号）的状态将发送给其他无人机。此外，动态拓扑图中直接与无人机相连的节点（位于Dijkstra搜索范围内的节点）与到达这些节点的距离也将发送给其他无人机，以便后续维诺划分。此外，由于只发送节点和边的信息，而不发送占据栅格地图信息，通信量大大降低了。
[0034]在上述步骤103中，为了防止多架无人机同时探索一个可探索子区域以提高探索效率，如图2和图3所示，不同于传统方法，不考虑障碍物在欧氏空间上维诺划分，本发明的维诺划分充分考虑了障碍物，保证了无人机和其划分子区域的路径最短。图2是根据传统维诺划分方法进行的探索任务的两架无人机的飞行路径示意图，图3是根据本发明提出的方法进行的探索任务的飞行路径示意图，图2中的两架无人机同时探索了同一个未探索区域。本发明提出无人机根据自身及他无人机状态在动态拓扑图上进行局部-全局图维诺划分。其中，局部图维诺划分：以第架无人机为例。首先，利用动态拓扑图获取第架无人机局部的局部图。其中局部图的节点由历史节点集，可探索子区域节点集和无人机节点集组成，。历史节点集是由与第架无人机直接连接的历史节点组成（位于Dijkstra搜索范围内的历史节点），由直接与第架无人机直接连接的可探索子区域节点（位于Dijkstra搜索范围内的可探索子区域节点）和与第架无人机间接连接的可探索子区域节点组成（与相连的可探索子区域节点），由与直接与和相连的无人机组成。局部图中和间的边为动态拓扑图的边，而与这些节点的边通过Dijkstra搜索得到，或者由其他无人机传输的局部信息得到。随后，以为起点进行平行Dijkstra搜索即可得到局部图的维诺划分。全局图维诺划分：全局维诺划分对所有的历史节点进行划分。全局图维诺划分过程和局部图维诺划分过程类似。首先，利用动态拓扑图获取全局图。其中，为动态拓扑图的所有历史节点组成的集合，为所有无人机组成的节点集合。则为这些节点的边，通过动态拓扑图和无人机间通信获得。随后，以为起点进行平行Dijkstra搜索即可得到全局图的维诺划分。注意，由于动态拓扑图已同步，所有无人机本地建立的都是一样的，故所有的维诺划分都是分布式进行的，且能得到相同的划分结果。
[0035]在上述步骤104中，基于步骤103的维诺划分的结果进行局部和全局规划：局部规划：局部规划基于局部维诺划分的结果采用贪心策略进行探索。第架无人机在选择局部图维诺划分结果中距离自身最近的可探索子区域节点进行探索。具体而言，通过在第一步时进行了Dijkstra搜索或在动态拓扑图上进行Dijkstra搜索，第架无人机可以直接找到距离自身最近中的可探索子区域节点，和探索该节点的路径。全局规划：当第架无人机的局部图维诺划分得到的结果中没有可探索子区域节点时，进行全局规划。具体而言，第架无人机的全局维诺划分结果中的历史节点连接有可探索子区域，选择距离自身最近的可探索子区域节点进行探索。若第架无人机全局维诺划分结果中的历史节点没有连接可探索子区域，则意味着该无人机已完成自身的探索任务，应尝试分担其它无人机的探索任务。第架无人机会评估所有历史节点的信息增益，对于历史节点信息增益评估公式如下：
[0036]
[0037]其中为连接的可探索子区域节点数量，为当前正在探索的无人机数量，表示当前时刻开始第架无人机预计到达的时间，表示当前时刻开始第架无人机预计到达的时间，为一个预设参数，该参数为单位时间内一架无人机完成探索的可探索子区域数量，为预设参数，该参数是一个相对小的值，用于在当所有可探索子区域都被分给其他无人机但新的可探索子区域可能会产生时，引导该无人机前往，为预设参数，用于惩罚长路径。此外，通过启发式估计得到：
[0038]
[0039]此处，为从第架无人机到的路径长度，为无人机的最大速度。通过评估所有动态拓扑图中的历史节点，选择信息增益最高的节点作为探索目标。当所有的历史节点的信息增益均为0时，探索任务完成。
[0040]如图4所示，根据本发明的又一个实施例还公开了一种多无人机协同自主探索装置400，包括：存储器401，用于存储程序指令；处理器402，用于调用存储器中存储的程序指令以实现如上述实施例的多无人机协同自主探索方法。
[0041]根据本发明的又一个实施例还公开了一种计算机可读存储介质，该计算机可读存储介质存储有程序代码，程序代码用于实现如上述实施例的多无人机协同自主探索方法。
[0042]上述实施例的各种方法中的全部或部分步骤是可以通过程序来控制相关的硬件来完成，该程序可以存储于可读存储介质中，存储介质包括只读存储器（Read—OnlyMemory，ROM）、随机存储器（Random Access Memory，RAM）、可编程只读存储器（Programmable Read-only Memory，PROM）、可擦除可编程只读存储器（ErasableProgrammable Read Only Memory，EPROM）、一次可编程只读存储器（One-timeProgrammable Read-Only Memory，OTPROM）、电子抹除式可复写只读存储器（Electrically-Erasable Programmable Read-Only Memory，EEPROM）、只读光盘（CompactDisc Read—Only Memory，CD-ROM）或其他光盘存储器、磁盘存储器、磁带存储器、或者能够用于携带或存储数据的可读的任何其他介质。
[0043]以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。