From MFKP_wiki

Jump to: navigation, search


Ant-inspired density estimation via random walks

Cameron Musco, Hsin-Hao Su, Nancy A. Lynch



Significance. Highly complex distributed algorithms are ubiquitous in nature: from the behavior of social insect colonies and bird flocks, to cellular differentiation in embryonic development, to neural information processing. In our research, we study biological computation theoretically, combining a scientific perspective, which seeks to better understand the systems being studied, with an engineering perspective, which takes inspiration from these systems to improve algorithm design. In this work, we focus on the problem of population density estimation in ant colonies, demonstrating that extremely simple algorithms, similar to those used by ants, solve the problem with strong theoretical guarantees and have a number of interesting computational applications.

Abstract. 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.


Proceedings of the National Academy of Sciences, Vol. 114, No. 40. (03 October 2017), pp. 10534-10541, https://doi.org/10.1073/pnas.1706439114 
Key: INRMM:14436508

Keywords

           

Article-Level Metrics (Altmetrics)
Digital Object Identifier


Available versions (may include free-access full text)

https://arxiv.org/abs/1603.02981, DOI, HighWire, HighWire (PDF), Pubmed, Hubmed, Pubget

Versions of the publication are also available in Google Scholar.
Google Scholar code: GScluster:14947543214386501210

Works citing this publication (including grey literature)

An updated list of who cited this publication is available in Google Scholar.
Google Scholar code: GScites:14947543214386501210

Further search for available versions

Search in ResearchGate (or try with a fuzzier search in ResearchGate)
Search in Mendeley (or try with a fuzzier search in Mendeley)

Publication metadata

Bibtex, RIS, RSS/XML feed, Json, Dublin Core
Metadata search: CrossRef DOI, DataCite DOI

Digital preservation of this INRMM-MiD record

Internet Archive

Meta-information Database (INRMM-MiD).
This database integrates a dedicated meta-information database in CiteULike (the CiteULike INRMM Group) with the meta-information available in Google Scholar, CrossRef and DataCite. The Altmetric database with Article-Level Metrics is also harvested. Part of the provided semantic content (machine-readable) is made even human-readable thanks to the DCMI Dublin Core viewer. Digital preservation of the meta-information indexed within the INRMM-MiD publication records is implemented thanks to the Internet Archive.
The library of INRMM related pubblications may be quickly accessed with the following links.
Search within the whole INRMM meta-information database:
Search only within the INRMM-MiD publication records:
Full-text and abstracts of the publications indexed by the INRMM meta-information database are copyrighted by the respective publishers/authors. They are subject to all applicable copyright protection. The conditions of use of each indexed publication is defined by its copyright owner. Please, be aware that the indexed meta-information entirely relies on voluntary work and constitutes a quite incomplete and not homogeneous work-in-progress.
INRMM-MiD was experimentally established by the Maieutike Research Initiative in 2008 and then improved with the help of several volunteers (with a major technical upgrade in 2011). This new integrated interface is operational since 2014.