《Frontier-Based Exploration Using Multiple Robots》
作者：Brian Yamauchi
单位：海军人工智能应用研究中心华盛顿海军研究实验室
会议：International Conference on Autonomous Agents（AA，属于AAMAS，AAMAS是agent方面最好的会议，人工智能B类会议）
时间：1998
摘要：
基于边界的探索将移动机器人引导到未探索空间和已知开放空间之间边界上的区域。在此之前，我们已经演示了基于边界的探测可以用于绘制室内环境图，在这些环境中，墙壁和障碍物可能处于任意方向。在这篇文章中，我们展示了如何将基于边界的探索扩展到多个机器人。在我们的方法中，机器人共享感知信息，但维护单独的全局地图，并独立决定去哪里探索。这种方法使机器人能够利用来自其他机器人的信息进行更有效的探索，但它也允许团队对单个机器人的损失保持鲁棒。我们已经在真实的机器人上实现了我们的多机器人探索系统，我们展示了他们可以作为一个团队探索和绘制办公环境。
具体实现：
单机探索方案相比《A Frontier-Based Approach for Autonomous Exploration》基本没有什么改进，所以重点放在本文第四部分：多机探索。
每个机器人都有自己的证据网格地图，当机器人到达一个新的边界之后，构造周围环境的局部地图（重点：不能边走边构造）。之后将局部地图与全局地图合并，并把局部地图共享给其他所有的机器人。
文中有一段描述了两幅网格地图合并的步骤，用了log odds表达方式，用对数把乘法转换为加法，对数相加表示新的网格的先验概率。这块儿还不太明白，应该需要看一下参考文献[6]Moravec,H. Sensor fusion in certainty grids for mobilerobots. AI Magazine, 9(2):61-74, 1988. 这种方法能做到实时，速度很快，两张256*256的网格在1-2秒就能完成合并。
因为信息共享，所以机器人可以用其他机器人的数据来决定自己去哪。机器人可以确定哪些区域已经被其他机器人探索过，然后选择探索另一个区域；机器人还可以发现另一个机器人探测到的边界就在附近，并决定进行调查。（又没有总体调度，这不乱套了吗？）
机器人是各自探索的，非同步，所以一个机器人出了问题的话，其他机器人也不会等它。
本文方法是有一些缺点的。因为导航是独立的，所以不是效率最优的。Reactive behaviors可以避免碰撞，但不能避免机器人互相阻挡。然而，在这些情况下，任何被阻止的机器人都将继续探索其他边界，只有被阻止的机器人会将其目的地边界标记为不可访问，因此其他机器人仍可能探索该边界（个人理解，因为机器人到达新边界才会建立局部地图然后共享，它没到边界，所以信息无法给到其他机器人）。此外，当每个机器人扫描房间时，它会将其他机器人合并为其地图中的障碍物。直到这些机器人移动到新的位置，旧位置在随后的传感器扫描中被重新扫描时，再被标记为空白。
在本文的实验中，每个机器人都被提供了其位置的初步估计，当机器人在环境中移动时，航位推算被用来更新该位置。且实验中已经用到了类似回环检测的步骤。
结论：
以边界为基础的探索提供了一种有效的方式来探索这样的环境：墙壁和障碍物可能是任意方向的，沿着墙壁走或随机漫游不太可能产生完整的地图。在这篇文章中，我们展示了如何将基于边界的探索扩展到多个机器人团队使用。
在我们的方法中，机器人维护自己的全局地图，并独立决定在哪里探索。每当机器人到达新的边界时，它们就会分享自己的感知信息，并将来自其他机器人的信息整合到自己的全局地图中。通过这种方式，机器人合作并使用来自其他机器人的信息来指导自己的探索。同时，该方法对单个机器人的丢失具有较强的鲁棒性，并且不需要机器人之间的任何显式协调或同步。我们已经使用真实的机器人实现了该系统，并演示了该方法可以用于绘制室内办公环境。
未来工作：
此前，我们已经证明，使用证据网格的持续定位可以与基于边界的探索相结合[11]。这使得机器人即使在探索未知领域时也能保持准确的位置估计。我们计划将这一能力集成到多机器人探索团队中，所有机器人的信息都可以用来定位每个机器人。我们还计划调查与机器人之间更明确的协调相关的权衡，并进行量化实验，比较不同的多机器人探索策略的性能。
笔记：
航位推算（dead reckoning）是一种很常见的定位方法。在知道当前时刻的位置，然后通过imu等传感器去估计下一个时刻的位置。见https://zhuanlan.zhihu.com/p/96899895