机器人群:通过蚁群行为分析开发高效网络

事实证明，蚂蚁非常善于估计周围其他蚂蚁的集中度。这种能力似乎在一些公共活动中发挥了作用，特别是在蚁群选择新巢穴的投票程序中。

长期以来，生物学家一直怀疑蚂蚁是根据它们随机探索环境时与其他蚂蚁碰撞的频率来估计种群密度的。

麻省理工学院计算机科学与人工智能实验室研究人员的一篇理论论文为这一理论提供了新的支持。本文表明，对环境的随机探测的观测很快就会收敛到对人口密度的准确估计上。事实上，它们在理论上尽可能快地收敛。

除了为生物学家的假设提供支持外，这一理论框架还适用于分析社会网络，机器人群体的集体决策，以及自组织网络中的通信，例如分散在恶劣环境中的低成本传感器网络。

麻省理工学院电气工程和计算机科学专业的研究生、这篇新论文的合著者卡梅伦·穆斯科(Cameron Musco)说:“从直觉上看，如果一群人在一个地区随机走动，他们相遇的次数将代表人口密度。”“我们所做的是在直觉背后给出严格的分析，同时也说这个估计是一个非常好的估计，而不是一些粗略的估计。作为时间的函数，它变得越来越准确，几乎和你期望的一样快。”

随机漫步

Musco和他的合著者——他的导师，NEC软件科学与工程教授Nancy Lynch，以及Lynch团队的博士后suxin - hao Su——将蚂蚁的环境描述为一个网格，一些其他蚂蚁随机分布在网格上。感兴趣的蚂蚁——称之为“探索者”——从网格的某个单元开始，然后以相同的概率移动到相邻的一个单元。然后，以相同的概率，它移动到与它相邻的一个单元格，以此类推。在统计学中，这被称为“随机游走”。探险者会计算它所访问的每个细胞中其他蚂蚁的数量。

在他们的论文中，研究人员将随机行走与随机抽样进行了比较，随机抽样是从网格中随机选择细胞，并计算蚂蚁的数量。每增加一个样本，两种方法的准确性都会提高，但值得注意的是，随机游走收敛于真实人口密度的速度几乎和随机抽样一样快。

这很重要，因为在许多实际情况下，随机抽样并不是一种选择。探索它的唯一方法是选择一个单独的成员并开始跟踪连接。

类似地，在自组织网络中，一个给定的设备只知道在它附近的设备的位置;它不知道整个网络的布局。使用随机行走来聚合来自多个设备的信息的算法要比必须将网络作为一个整体来描述的算法容易实现得多。

重复接触

研究人员的结果令人惊讶，因为在随机漫步的每一步，探索者都有很大的可能性回到它已经访问过的细胞。因此，来自随机行走的估计比基于随机抽样的估计有更高的几率对特定细胞进行过采样。

最初，Musco说，他和他的同事们认为这是估计人口密度的算法必须克服的一个缺陷。但他们试图过滤掉过采样数据的尝试似乎使算法的性能恶化，而不是改善。最终，他们从理论上解释了其中的原因。

Musco说:“如果你在网格中随机行走，你不可能碰到每个人，因为你不可能穿过整个网格。”“所以在电网的另一端有个人，我碰到他的几率几乎为零。不过，虽然我很少碰到这些人，但我会更多地碰到本地人。我需要计算我与本地的所有交互量来弥补我永远不会碰到这些远方的人的事实。这是一种完美的平衡。这很容易证明，但不是很直观，所以我们花了一段时间才意识到这一点。”

概括

研究人员用来模拟蚂蚁环境的网格只是一种被称为图的数据结构的特殊实例。图由节点(通常用圆表示)和边(通常用连接节点的线段表示)组成。在网格中，每个单元格都是一个节点，它只与那些紧邻它的单元格共享边。

然而，研究人员的分析技术适用于任何图形，例如描述社交网络中哪些成员是相连的，或者自组织网络中哪些设备彼此处于通信范围内。

如果图的连接不是很好——例如，如果它只是一个节点链，每个节点只连接到相邻的两个节点，那么过采样就会成为一个问题。例如，在一个由100个节点组成的链中，一个随机漫步的探索者可能会一遍又一遍地遍历相同的5或6个节点。

只要从同一节点出发的两次随机游走有可能向不同方向分支，就像描述通信网络的图中经常出现的情况一样，随机游走实际上仍然和随机抽样一样好。

此外，在这篇新论文中，研究人员分析了由单个探索者执行的随机行走。汇集许多探险者的观测结果可以更快地得出准确的估计。“如果它们是机器人而不是蚂蚁，它们可以通过相互交谈，说‘哦，这是我的估计，’来获得收益，”穆斯科说。

麻省理工学院

www.mit.edu

-由克里斯·瓦夫拉编辑，制作编辑，控制工程， CFE传媒，
cvavra@cfemedia.com．查看更多控制工程行业网络故事．

您是否具有本内容中提到的主题的经验和专业知识?你应该考虑为我们的CFE媒体编辑团队做出贡献，并获得你和你的公司应得的认可。点击在这里开始这个过程。