Trade-offs between selection complexity and performance when searching the plane without communication
We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a sel...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100845 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 |
| _version_ | 1826197549478838272 |
|---|---|
| author | Lenzen, Christoph Newport, Calvin Charles Lynch, Nancy Ann Radeva, Tsvetomira T. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Lenzen, Christoph Newport, Calvin Charles Lynch, Nancy Ann Radeva, Tsvetomira T. |
| author_sort | Lenzen, Christoph |
| collection | MIT |
| description | We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2[superscript l]). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D[superscript 2]/n +D) ⋅ 2[superscript O(l)] for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D[superscript 2-o(1)] moves. This constitutes a sizable gap to the straightforward Ω(D[superscript 2]/n + D) lower bound. |
| first_indexed | 2024-09-23T10:49:22Z |
| format | Article |
| id | mit-1721.1/100845 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:49:22Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1008452022-09-27T15:16:26Z Trade-offs between selection complexity and performance when searching the plane without communication Lenzen, Christoph Newport, Calvin Charles Lynch, Nancy Ann Radeva, Tsvetomira T. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lenzen, Christoph Lynch, Nancy Ann Radeva, Tsvetomira T. We argue that in the context of biology-inspired problems in computer science, in addition to studying the time complexity of solutions it is also important to study the selection complexity, a measure of how likely a given algorithmic strategy is to arise in nature. In this spirit, we propose a selection complexity metric χ for the ANTS problem [Feinerman et al.]. For algorithm A, we define χ(A) = b + log l, where b is the number of memory bits used by each agent and l bounds the fineness of available probabilities (agents use probabilities of at least 1/2[superscript l]). We consider n agents searching for a target in the plane, within an (unknown) distance D from the origin. We identify log log D as a crucial threshold for our selection complexity metric. We prove a new upper bound that achieves near-optimal speed-up of (D[superscript 2]/n +D) ⋅ 2[superscript O(l)] for χ(A) ≤ 3 log log D + O(1), which is asymptotically optimal if l∈ O(1). By comparison, previous algorithms achieving similar speed-up require χ(A) = Ω(log D). We show that this threshold is tight by proving that if χ(A) < log log D - ω(1), then with high probability the target is not found if each agent performs D[superscript 2-o(1)] moves. This constitutes a sizable gap to the straightforward Ω(D[superscript 2]/n + D) lower bound. 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-1217506) National Science Foundation (U.S.) (Award CCF-AF-0937274) National Science Foundation (U.S.) (Award CCF 1320279) Deutsche Forschungsgemeinschaft (Le 3107/1-1) Ford Motor Company. University Research Program 2016-01-15T02:33:01Z 2016-01-15T02:33:01Z 2014-07 Article http://purl.org/eprint/type/ConferencePaper 9781450329446 http://hdl.handle.net/1721.1/100845 Christoph Lenzen, Nancy Lynch, Calvin Newport, and Tsvetomira Radeva. 2014. Trade-offs between selection complexity and performance when searching the plane without communication. In Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC '14). ACM, New York, NY, USA, 252-261. https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 en_US http://dx.doi.org/10.1145/2611462.2611463 Proceedings of the 2014 ACM symposium on Principles of distributed computing (PODC '14) 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 | Lenzen, Christoph Newport, Calvin Charles Lynch, Nancy Ann Radeva, Tsvetomira T. Trade-offs between selection complexity and performance when searching the plane without communication |
| title | Trade-offs between selection complexity and performance when searching the plane without communication |
| title_full | Trade-offs between selection complexity and performance when searching the plane without communication |
| title_fullStr | Trade-offs between selection complexity and performance when searching the plane without communication |
| title_full_unstemmed | Trade-offs between selection complexity and performance when searching the plane without communication |
| title_short | Trade-offs between selection complexity and performance when searching the plane without communication |
| title_sort | trade offs between selection complexity and performance when searching the plane without communication |
| url | http://hdl.handle.net/1721.1/100845 https://orcid.org/0000-0003-3045-265X https://orcid.org/0000-0003-1261-6681 |
| work_keys_str_mv | AT lenzenchristoph tradeoffsbetweenselectioncomplexityandperformancewhensearchingtheplanewithoutcommunication AT newportcalvincharles tradeoffsbetweenselectioncomplexityandperformancewhensearchingtheplanewithoutcommunication AT lynchnancyann tradeoffsbetweenselectioncomplexityandperformancewhensearchingtheplanewithoutcommunication AT radevatsvetomirat tradeoffsbetweenselectioncomplexityandperformancewhensearchingtheplanewithoutcommunication |