Skip to main content

Main menu

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
  • Submit
  • About
    • Editorial Board
    • PNAS Staff
    • FAQ
    • Accessibility Statement
    • Rights and Permissions
    • Site Map
  • Contact
  • Journal Club
  • Subscribe
    • Subscription Rates
    • Subscriptions FAQ
    • Open Access
    • Recommend PNAS to Your Librarian

User menu

  • Log in
  • My Cart

Search

  • Advanced search
Home
Home
  • Log in
  • My Cart

Advanced Search

  • Home
  • Articles
    • Current
    • Special Feature Articles - Most Recent
    • Special Features
    • Colloquia
    • Collected Articles
    • PNAS Classics
    • List of Issues
  • Front Matter
    • Front Matter Portal
    • Journal Club
  • News
    • For the Press
    • This Week In PNAS
    • PNAS in the News
  • Podcasts
  • Authors
    • Information for Authors
    • Editorial and Journal Policies
    • Submission Procedures
    • Fees and Licenses
  • Submit
Inaugural Article

Ant-inspired density estimation via random walks

Cameron Musco, Hsin-Hao Su, and View ORCID ProfileNancy A. Lynch
  1. aComputer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139

See allHide authors and affiliations

PNAS October 3, 2017 114 (40) 10534-10541; first published September 19, 2017; https://doi.org/10.1073/pnas.1706439114
Cameron Musco
aComputer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Hsin-Hao Su
aComputer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
Nancy A. Lynch
aComputer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139
  • Find this author on Google Scholar
  • Find this author on PubMed
  • Search for this author on this site
  • ORCID record for Nancy A. Lynch
  • For correspondence: lynch@csail.mit.edu
  1. Contributed by Nancy A. Lynch, August 14, 2017 (sent for review April 18, 2017; reviewed by Yehuda Afek, Ziv Bar-Joseph, and Amos Korman)

  • Article
  • Figures & SI
  • Info & Metrics
  • PDF
Loading

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.

  • population density estimation
  • random walk sampling
  • network exploration
  • ant colony algorithms
  • biological distributed algorithms

Footnotes

  • ↵1C.M., H.S., and N.L. contributed equally to this work.

  • ↵2To whom correspondence should be addressed. Email: lynch{at}csail.mit.edu.
  • This contribution is part of the special series of Inaugural Articles by members of the National Academy of Sciences elected in 2016.

  • An extended abstract of this work has been previously published (1).

  • Author contributions: C.M., H.-H.S., and N.A.L. designed research; C.M., H.-H.S., and N.A.L. performed research; C.M. and H.-H.S. contributed new reagents/analytic tools; and C.M., H.-H.S., and N.A.L. wrote the paper.

  • Reviewers: Y.A., Tel-Aviv University; Z.B.-J., Carnegie Mellon University; and A.K., French National Center for Scientific Research.

  • The authors declare no conflict of interest.

  • See QnAs on page 10512.

  • This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1706439114/-/DCSupplemental.

View Full Text
PreviousNext
Back to top
Article Alerts
Email Article

Thank you for your interest in spreading the word on PNAS.

NOTE: We only request your email address so that the person you are recommending the page to knows that you wanted them to see it, and that it is not junk mail. We do not capture any email address.

Enter multiple addresses on separate lines or separate them with commas.
Ant-inspired density estimation via random walks
(Your Name) has sent you a message from PNAS
(Your Name) thought you would like to see the PNAS web site.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
Citation Tools
Ant-inspired density estimation
Cameron Musco, Hsin-Hao Su, Nancy A. Lynch
Proceedings of the National Academy of Sciences Oct 2017, 114 (40) 10534-10541; DOI: 10.1073/pnas.1706439114

Citation Manager Formats

  • BibTeX
  • Bookends
  • EasyBib
  • EndNote (tagged)
  • EndNote 8 (xml)
  • Medlars
  • Mendeley
  • Papers
  • RefWorks Tagged
  • Ref Manager
  • RIS
  • Zotero
Request Permissions
Share
Ant-inspired density estimation
Cameron Musco, Hsin-Hao Su, Nancy A. Lynch
Proceedings of the National Academy of Sciences Oct 2017, 114 (40) 10534-10541; DOI: 10.1073/pnas.1706439114
del.icio.us logo Digg logo Reddit logo Twitter logo CiteULike logo Facebook logo Google logo Mendeley logo
  • Tweet Widget
  • Facebook Like
  • Mendeley logo Mendeley

Article Classifications

  • Physical Sciences
  • Computer Sciences
  • Biological Sciences
  • Systems Biology

See related content:

  • QnAs with Nancy A. Lynch
    - Sep 19, 2017
Proceedings of the National Academy of Sciences: 114 (40)
Table of Contents

Submit

Sign up for Article Alerts

Jump to section

  • Article
    • Abstract
    • Density Estimation on a Grid
    • Results
    • Theoretical Model for Density Estimation
    • The Density Estimation Problem
    • Random Walk-Based Density Estimation on the 2D Torus
    • Extensions to Other Topologies
    • Applications
    • Discussion and Future Work
    • Acknowledgments
    • Footnotes
    • References
  • Figures & SI
  • Info & Metrics
  • PDF

You May Also be Interested in

Reflection of clouds in the still waters of Mono Lake in California.
Inner Workings: Making headway with the mysteries of life’s origins
Recent experiments and simulations are starting to answer some fundamental questions about how life came to be.
Image credit: Shutterstock/Radoslaw Lecyk.
Depiction of the sun's heliosphere with Voyager spacecraft at its edge.
News Feature: Voyager still breaking barriers decades after launch
Launched in 1977, Voyagers 1 and 2 are still helping to resolve past controversies even as they help spark a new one: the true shape of the heliosphere.
Image credit: NASA/JPL-Caltech.
Drop of water creates splash in a puddle.
Journal Club: Heavy water tastes sweeter
Heavy hydrogen makes heavy water more dense and raises its boiling point. It also appears to affect another characteristic long rumored: taste.
Image credit: Shutterstock/sl_photo.
Mouse fibroblast cells. Electron bifurcation reactions keep mammalian cells alive.
Exploring electron bifurcation
Jonathon Yuly, David Beratan, and Peng Zhang investigate how electron bifurcation reactions work.
Listen
Past PodcastsSubscribe
Panda bear hanging in a tree
How horse manure helps giant pandas tolerate cold
A study finds that giant pandas roll in horse manure to increase their cold tolerance.
Image credit: Fuwen Wei.

Similar Articles

Site Logo
Powered by HighWire
  • Submit Manuscript
  • Twitter
  • Facebook
  • RSS Feeds
  • Email Alerts

Articles

  • Current Issue
  • Special Feature Articles – Most Recent
  • List of Issues

PNAS Portals

  • Anthropology
  • Chemistry
  • Classics
  • Front Matter
  • Physics
  • Sustainability Science
  • Teaching Resources

Information

  • Authors
  • Editorial Board
  • Reviewers
  • Subscribers
  • Librarians
  • Press
  • Cozzarelli Prize
  • Site Map
  • PNAS Updates
  • FAQs
  • Accessibility Statement
  • Rights & Permissions
  • About
  • Contact

Feedback    Privacy/Legal

Copyright © 2021 National Academy of Sciences. Online ISSN 1091-6490