一群飞行机器人探索未知环境的最小导航方案（UAV-2019）

摘要

成群的微型飞行机器人具有探索未知室内环境的巨大潜力。它们的小尺寸允许它们在狭窄的空间内移动，它们的轻重量使它们可以安全地在人类周围操作。到目前为止，由于缺乏足够的导航策略，这项任务已经遥不可及。缺乏外部基础设施意味着任何定位尝试都必须由机器人自己完成。最先进的解决方案，如同步本地化和映射，仍然对资源要求过高。本文介绍了群体梯度bug算法(SGBA)，这是一种最小导航解决方案，允许一群微型飞行机器人自主探索未知环境，然后返回出发点。SGBA通过让机器人在远离出发点的不同方向上行进来最大化覆盖范围。机器人通过视觉里程计和跟墙行为在飞行中导航环境和处理静态障碍物。此外，它们相互通信以避免冲突并最大化搜索效率。为了回到出发点，机器人执行朝向家庭信标的梯度搜索。我们研究了SGBA的集体方面，展示了它允许一组33g商用现成四旋翼飞行器成功探索真实世界的环境。一个概念验证搜索和救援任务说明了其应用潜力，在该任务中，机器人捕捉图像以在办公室环境中找到“受害者”。所开发的算法可推广到其他类型的机器人，并为将来利用机器人群处理其他类似的复杂任务奠定了基础。

引语

• 成群的微型自主飞行机器人大有希望。微小的飞行机器人可以在狭窄的空间内移动，价格非常便宜，可以变成一次性的，并且在人类面前是安全的。

• 单个机器人在认知和行动方面的能力可能天生有限，但它们可以一起解决非常复杂的问题。这种解决问题的能力在自然界是丰富的。两个著名的例子是蚂蚁群寻找最短路径和蜜蜂通过摇摆舞集体选择有利可图的食物资源。

• 群体机器人的核心原理是单个机器人遵守相对简单的控制规则，仅仅基于它们的局部感觉输入和与邻居的局部通信。这个原理非常适合微型机器人有限的资源。此外，不依赖任何中央处理保证了系统的高鲁棒性。一个失败的机器人不会危及任务的执行，因为它的角色将由许多其他机器人中的一个来完成。此外，小型机器人将有可能更快、更有力地完成任务，如监视、建造或探索。

• 关于飞行机器人群，主要挑战在于在真实环境中实现自主机器人导航和机器人之间的协调。飞行机器人相互通信其全球定位系统位置，以确定与其他机器人的相对位置，作为本地控制器的输入。

• 一群微型飞行机器人在一个混乱的、没有全球定位系统的环境中导航一直是一个未解决的问题。

• 导航的主流解决方案包括基于相机图像或激光测距仪的同步定位和测绘(SLAM)。然而，典型的度量SLAM方法制作详细的三维(3D)地图，这在计算和内存资源方面要求非常高。

• 为了说明用微型飞行机器人导航的挑战，我们展示了(图1)我们实验中使用的机器人的处理能力(Bitcraze的Crazyflie 2.0)，以及SLAM方法中使用的两个最新、最先进的嵌入式处理单元。
  

• 我们需要用更少的内存和处理器速度来解决导航问题。这需要一种完全不同的导航策略。

• 一种有效导航的潜在方法是从生物学中获取灵感，例如，通过观察蜜蜂的导航策略。蜜蜂通过结合路径整合和地标识别来导航。路径集成可以用非常有限的系统来实现，就像最近介绍的AntBot 一样。

• 尚不清楚生物系统如何进行地标识别。主导模型是快照模型，其中存储了周围环境的图片，随后与视觉输入进行比较。不幸的是，目前地标识别的实现仍然需要大量的处理和内存，这使得它不适合微型机器人导航。此外，它们大多在富含纹理的环境中茁壮成长，这种环境在自然界中很常见，但在重复的人造环境中却不常见。

• 昆虫遵循的导航策略表明，通过要求不太精确的地图，有可能节省计算和内存。生物导航策略表现出与拓扑SLAM 的相似性，**在拓扑SLAM中，机器人只存储重要的地标及其在距离和方向方面的关系。这不再允许机器人以高精度在探索的空间中的任何地方行进，但是这对于成功的行为可能不是必需的。**在某些情况下，探索并返回“巢穴”可能才是重要的，即只执行精确的归巢。一种只需要归航而不依赖于计算复杂的视觉导航的导航策略，在缩小到微型机器人方面有很大的潜力。

最小导航解决方案

• 本文的主要贡献是为一群微型飞行机器人提供了一个最小自主导航解决方案，以探索未知的非结构化环境，并随后返回出发点。此外，在相同的环境中，我们说明了该解决方案如何实现特定的概念验证搜索和救援探索任务，在该任务中，群体收集图像以找到环境中的“受害者”。
• 我们引入了群体梯度bug算法(SGBA)。该方法的灵感来自“bug算法”，它起源于简单的迷宫求解算法。核心概念是，从A到B的导航不是通过在具有已知障碍物的全局地图中进行规划来执行的，而是通过在障碍物进入传感器范围内时对其做出反应来执行的。这种处理障碍物的方式产生了计算效率高的导航。
• SGBA在这篇文章中提出的bug算法与现有的bug算法有很大的不同，图2B展示了主要的概念:一群机器人离开它们的基站前往外部环境。每个机器人都有一个不同的优先方向，它将努力朝着这个方向前进。当机器人遇到障碍物时，它们会跟随障碍物的轮廓。这个过程在bug算法文献中被称为“跟墙”。当机器人的首选方向再次没有障碍物时，它将继续遵循其首选方向。一旦机器人的电池电量达到60%左右，它就会开始向基站行驶(图2C)。为了回到原来的位置，机器人使用了(粗略的)里程计，以及为了保持在更长的时间尺度上，基站的可观测梯度。在我们的实验中，我们将接收信号强度(RSSI)用于位于基站的无线电信标。

因为bug算法不会制作地图，所以有一个危险是它们会在没有意识到的情况下陷入循环。例如，这可能发生在只有一条出路的房间里，当机器人以其首选方向离开墙壁时，可能会错过这条出路，再次导航到对面的墙壁。

• SGBA的创新之处在于它适用于计算能力极其有限的微小机器人的现实属性。另一个优势是SGBA使用了多个机器人。
• SGBA的群集机制包括(I)不同初始优先方向的印记，(ii)为了避免群内碰撞，使用机器人间的RSSI来代替传送全局位置，以及(iii)当机器人注意到它们的优先方向与另一个机器人的优先方向重叠太多时，优先方向的适应。这些简单的机制不需要机器人之间的精确相对位置，已经显著提高了探索效率。
• SGBA需要五个主要功能:(一)遵循一个给定的方向；㈡跟墙；(三)里程计；(四)机器人之间的探测、通信和回避；(五)朝向出发点的基于梯度的搜索。SGBA算法可以应用于资源有限的不同类型的移动机器人，只要它们被赋予上述所需的功能。

实验

• 导航是指在环境中展开，尽可能的覆盖环境，回到出发点。
• 性能指标是(I)区域覆盖率和(ii)机器人的返回率。
• 我们改变了机器人的数量，以研究SGBA拥挤的优势。
• 我们还研究了一个搜索和救援场景，其中机器人必须在环境中寻找可能的受害者。机器人携带车载摄像头和安全数字卡来存储环境图像，当返回基站时，机器人可以将图像上传到基站，人类终端用户可以查看图像以找到受害者。我们考虑作为第三个性能指标，(三)返回机器人覆盖的区域——称为“返回的覆盖范围。”在具体的搜救实验中，我们评估了图像中是否有受害者。

仿真环境

环境

• 在模拟中，机器人被改编成ARGoS步行机器人。这些基于地面的非完整机器人不同于真实世界实验中使用的机载完整机器人。地面机器人在模拟实验中的使用说明了SGBA可以应用于不同类型的机器人。4

结论

• 图3 (B和C)显示了四个和六个机器人的模拟实验的两个例子。我们在每个模拟环境中实验了2、4、6、8和10个机器人，每个测试配置产生100个环境。覆盖率统计可以在图3D中找到，回报率可以在图3E中找到。
• 10个小型机器人平均能够在10分钟内探索90%的模拟20米乘20米环境。
• 增加更多的机器人会在同样的时间内带来更高的覆盖率。条形的趋势表明覆盖范围服从收益递减规律；结果表明，这种影响主要是由于覆盖了环境中的相同区域，而不是由于机器人相互干扰。每个机器人的覆盖率和返回率没有降低。
• 返回率低于100%，主要是因为SGBA会导致返回基站的路径不理想(对于总任务时间来说太慢)。
• 无人机数量越多，所有性能特征的差异越小，这表明增加更多的智能体增加了结果的确定性。这似乎主要是由于个人表现的差异对总覆盖面的影响减少。
• (I)向不同方向发送它们，(ii)在接近另一个机器人时执行回避机动，以及(iii)改变优先方向。这三种机制都有助于减少碰撞和提高覆盖率。

真实环境

硬件

• 一个确定平移光流的向下看的摄像机
• 一个向下指向的激光测距仪对光流进行缩放以获得高度和平移速度。
• 通信硬件“Crazyradio”具有2.4千兆赫的无线频段，用于与其他无人机和无线信标进行测距。

结论

• 因为我们无法访问地面真实全球坐标，所以我们根据参观房间的数量(不包括走廊)来确定覆盖性能轨迹显示，当无人机进入一个房间时，它通常会沿着其完整的边界飞行。因此，一进门，我们就认为房间“被访问了”。
• SGBA还允许现实世界中的微型机器人探索环境，平均6架微型无人机在7.5分钟内飞入40米乘12米环境中83%的开放房间。
• 图4(B和C)分别显示了四个和六个Crazyflies的两个示例轨迹。在图4C中，可以看到一个例子，其中无人驾驶飞机5失去了与环境的信标的连接，失去连接对自主导航来说不是问题，视觉里程计和跟墙行为允许无人机离开房间，并与家庭信标重新连接。
• 图4D显示，正如在模拟中一样，可以看到一个明显的趋势，即总覆盖范围随着无人机数量的增加而增加。然而，返回的无人机覆盖范围的增加似乎没有模拟中那么陡峭。其原因是，当添加更多无人机时，每个机器人的覆盖率和返回率(图4E)都略有下降。这是由于许多问题，如硬件故障、传感故障，以及(即使是六架无人机)两架无人机之间的碰撞。
• 关于避碰，在所有15个真实世界的实验中，无人机之间有54次相遇，只有一次碰撞。这相当于所实施的回避机动的98%的成功率。

搜索和救援任务

• 我们将其应用于搜救探索任务。轻型Crazyflies携带了一个与任务相关的有效载荷:一个前视摄像头和一个SD卡，结果飞行时间总共为5.5分钟。这个实验模拟了一个搜救场景，两个真人大小的木制人像被放在走廊的两个不同房间里。
• 在图5 (A和B)中，我们可以看到Crazyflies1和4在受害者所在的房间中飞行。无人机4能够通过机载摄像头捕捉到受害者(图5E)。然而在Crazyflie1飞入房间之前，它停止了录制。幸运的是，受害者被无人机3从另一个角度发现(图5D)。这个例子展示了使用集群的优势，集群可以在探测任务中产生冗余的观测值。
• 无人机回来后，它们收集的图像可以下载到基站。然后，人类终端用户可以浏览图像，当找到受害者时，快速查看机器人的视频以找到位置。如果终端用户需要地图，基站计算机还可以使用最先进的SLAM方法基于机载图像生成地图。

讨论：将这项工作扩展到更大、更复杂的环境中，需要考虑的几个因素

• 使用超宽带(UWB)代替CrazyradioPA将大大改善信标定位和其他无人机的感知。Crazyradio受其他2.4千兆赫信号源(Wi-Fi)的影响很大，通过使用具有飞行时间测距的超宽带通信，通信可以得到相当大的改善。
• 使用太多无人机也导致了飞行过程中的通信过载。无人机的最佳数量将取决于环境的大小，以及当前实施的碰撞回避、通信硬件和协议。由于超宽带对干扰具有更强的鲁棒性和更高的吞吐量，我们预计它还将提高当前提出的无人机防撞方案的可扩展性。
• 如果信标完全丢失，机器人将如何回家？在更大的环境中处理家庭信标丢失问题的一个有用的补充是更多地利用群。由于Crazyflies正在相互交流，它们本身也可以作为一个灯塔。一旦无人机失去与归航信标的连接，它就可以尝试找到另一个仍与信标连接的Crazyflie，并首先导航到该位置，重新连接到原始的归航信标，并恢复到起始位置的导航
• SGBA在感知、计算和存储方面的高效率是以导航效率为代价的。不构建全局地图和不执行计算开销大的最优路径规划会导致路径不理想。无人机可以多次访问房间，也可以访问其他无人机已经访问过的房间。这也许可以用相对有效的方式来解决，例如，涉及视觉地标识别。尽管如此，实验结果表明，来自同一区域的多次测量可能是有益的。相机镜头可能会暂时被遮挡甚至丢失，就像图5C中的无人机1一样。此外，如果不是所有的机器人都能返回，无人机的视角相互重叠的事实可能会在数据收集方面产生重大影响。

方法

跟墙

机器人用前激光测距传感器探测到障碍物后，将开始跟墙行为。首先，它选择一个初始的“局部方向”，决定是沿着墙的右侧还是左侧。我们基于DistBug (56)和FuzzyBug (57)的策略选择了局部方向策略，即在机器人接近墙壁时采用“迎角”。利用水平面所有四个方向上的四个激光距离传感器的当前硬件，机器人可以通过评估侧面距离传感器是否与前面的结合被触发来容易地确定墙壁的角度。这里的主要假设是墙需要是直的。然而，如果不是这样，这并不意味着战略会失败。从这里开始，机器人开始跟随障碍物和墙壁的边界。

环路检测

SGBA使用内存进行环路检测。算法容易陷入循环，因为它们可能会遇到障碍物，执行墙壁跟随，然后在一个方向上离开障碍物，这将导致它们回到完全相同的障碍物。SGBA保持跟踪其相对于机器人第一次检测到障碍物的位置(称为“撞击点”)的位置。如果机器人由于环境特征而向后跟踪，并穿过击中点后面的区域，它将检测到这是一个循环。这意味着，一旦机器人离开障碍物并遇到另一个通常与上次相同的命中点，它将不会将其局部方向基于当前的墙角度，而是基于与先前保存的命中点选择的方向相反的方向。

无人机协同

• 首先，机器人需要相互回避，其次，它们应该相互协调搜索，以实现最大程度的分散并避免冲突。这是通过它们的通信信息和距离测量(距离或RSSI)完成的，并由图6A中的“避让”状态实现。
• 为了避免碰撞，如果两个机器人靠得很近，具有高优先级的机器人将拥有通行权。低优先级机器人将执行一个动作，使高优先级机器人能够顺利通过它。
• 为了协调搜索，机器人动态地调整它们的首选航向。最初，每个机器人被分配一个首选航向，从K个不同的方向中选择。如果在外出旅行期间，一个机器人靠近另一个机器人，并且这些机器人具有相似的首选航向，则低优先级机器人将改变其首选航向的符号并继续前进。下一次它离开障碍物时，它将因此远离具有更高优先级的机器人的搜索区域。首选航向的改变比碰撞避免动作更早触发。

结论

我们的导航解决方案不是像传统的SLAM技术那样构建环境地图，而是由简单行为和行为转换的组合组成，以完成自主探索和归航的复杂任务。这里的指导原则是在路径优化和准确性等属性与资源效率之间进行权衡，从而实现群体自主导航。我们相信，这一原理可以为解决其他复杂的机器人任务以及大量廉价安全的微型机器人提供灵感。