Distributed House-Hunting in Ant Colonies
We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100843 https://orcid.org/0000-0003-2197-6806 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0003-1261-6681 |
| _version_ | 1826192240303669248 |
|---|---|
| author | Ghaffari, Mohsen Musco, Cameron Nicholas Radeva, Tsvetomira T. Lynch, Nancy Ann |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ghaffari, Mohsen Musco, Cameron Nicholas Radeva, Tsvetomira T. Lynch, Nancy Ann |
| author_sort | Ghaffari, Mohsen |
| collection | MIT |
| description | We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest. |
| first_indexed | 2024-09-23T09:08:10Z |
| format | Article |
| id | mit-1721.1/100843 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:08:10Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1008432022-09-30T13:42:57Z Distributed House-Hunting in Ant Colonies Ghaffari, Mohsen Musco, Cameron Nicholas Radeva, Tsvetomira T. Lynch, Nancy Ann Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Ghaffari, Mohsen Musco, Cameron Nicholas Radeva, Tsvetomira T. Lynch, Nancy Ann We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest. United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042) National Science Foundation (U.S.) (Award 0939370-CCF) National Science Foundation (U.S.) (Award CCF-AF-0937274) 2016-01-15T01:30:30Z 2016-01-15T01:30:30Z 2015-07 Article http://purl.org/eprint/type/ConferencePaper 9781450336178 http://hdl.handle.net/1721.1/100843 Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch. 2015. Distributed House-Hunting in Ant Colonies. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15). ACM, New York, NY, USA, 57-66. https://orcid.org/0000-0003-2197-6806 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0003-1261-6681 en_US http://dx.doi.org/10.1145/2767386.2767426 Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC '15) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Ghaffari, Mohsen Musco, Cameron Nicholas Radeva, Tsvetomira T. Lynch, Nancy Ann Distributed House-Hunting in Ant Colonies |
| title | Distributed House-Hunting in Ant Colonies |
| title_full | Distributed House-Hunting in Ant Colonies |
| title_fullStr | Distributed House-Hunting in Ant Colonies |
| title_full_unstemmed | Distributed House-Hunting in Ant Colonies |
| title_short | Distributed House-Hunting in Ant Colonies |
| title_sort | distributed house hunting in ant colonies |
| url | http://hdl.handle.net/1721.1/100843 https://orcid.org/0000-0003-2197-6806 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-4213-9898 https://orcid.org/0000-0003-1261-6681 |
| work_keys_str_mv | AT ghaffarimohsen distributedhousehuntinginantcolonies AT muscocameronnicholas distributedhousehuntinginantcolonies AT radevatsvetomirat distributedhousehuntinginantcolonies AT lynchnancyann distributedhousehuntinginantcolonies |