Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139.
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139
Proc Natl Acad Sci U S A. 2017 Oct 3;114(40):10534-10541. doi: 10.1073/pnas.1706439114. Epub 2017 Sep 19.
Many ant species use distributed population density estimation in applications ranging from quorum sensing, to task allocation, to appraisal of enemy colony strength. It has been shown that ants estimate local population density by tracking encounter rates: The higher the density, the more often the ants bump into each other. We study distributed density estimation from a theoretical perspective. We prove that a group of anonymous agents randomly walking on a grid are able to estimate their density within a small multiplicative error in few steps by measuring their rates of encounter with other agents. Despite dependencies inherent in the fact that nearby agents may collide repeatedly (and, worse, cannot recognize when this happens), our bound nearly matches what would be required to estimate density by independently sampling grid locations. From a biological perspective, our work helps shed light on how ants and other social insects can obtain relatively accurate density estimates via encounter rates. From a technical perspective, our analysis provides tools for understanding complex dependencies in the collision probabilities of multiple random walks. We bound the strength of these dependencies using local mixing properties of the underlying graph. Our results extend beyond the grid to more general graphs, and we discuss applications to size estimation for social networks, density estimation for robot swarms, and random walk-based sampling for sensor networks.
许多蚂蚁物种在从群体感应、任务分配到评估敌巢强度等应用中使用分布式种群密度估计。已经表明，蚂蚁通过跟踪遭遇率来估计局部种群密度：密度越高，蚂蚁相互碰撞的频率就越高。我们从理论角度研究分布式密度估计。我们证明，一组匿名的在网格上随机行走的代理可以通过测量它们与其他代理的遭遇率，在几步内以小的乘法误差估计它们的密度。尽管附近的代理可能会反复碰撞（更糟糕的是，它们无法识别何时发生这种情况）这一事实带来了固有依赖关系，但我们的界几乎与通过独立抽样网格位置来估计密度所需的界相匹配。从生物学角度来看，我们的工作有助于阐明蚂蚁和其他社会性昆虫如何通过遭遇率获得相对准确的密度估计。从技术角度来看，我们的分析为理解多个随机游动碰撞概率中的复杂依赖关系提供了工具。我们使用底层图的局部混合特性来限制这些依赖关系的强度。我们的结果扩展到了更一般的图，我们讨论了在社交网络中的大小估计、机器人群中的密度估计以及基于随机游动的传感器网络采样中的应用。
