Solving ANTS with loneliness detection and constant memory
Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/106119 |
| _version_ | 1826204253248552960 |
|---|---|
| author | O'Brien, Casey (Casey M.) |
| author2 | Nancy Lynch. |
| author_facet | Nancy Lynch. O'Brien, Casey (Casey M.) |
| author_sort | O'Brien, Casey (Casey M.) |
| collection | MIT |
| description | Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. |
| first_indexed | 2024-09-23T12:51:22Z |
| format | Thesis |
| id | mit-1721.1/106119 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T12:51:22Z |
| publishDate | 2016 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1061192019-04-11T09:55:15Z Solving ANTS with loneliness detection and constant memory Solving Ants Nearby Treasure Search with loneliness detection and constant memory O'Brien, Casey (Casey M.) Nancy Lynch. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis: M. Eng., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015. Cataloged from PDF version of thesis. Includes bibliographical references (page 105). In 2012, Feinerman et al. introduced the Ants Nearby Treasure Search (ANTS) problem [1]. In this problem, k non-communicating agents with unlimited memory, initially located at the origin, try to locate a treasure distance D from the origin. They show that if the agents know k, then the treasure can be located in the optimal O(D+ D²/k) steps. Furthermore, they show that without knowledge of k, the agents need [omega]((D + D²/k) - log¹+[epsilon] k) steps for some [epsilon] > 0 to locate the treasure. In 2014, Emek et al. studied a variant of the problem in which the agents use only constant memory but are allowed a small amount of communication [2]. Specifically, they allow an agent to read the state of any agent sharing its cell. In this paper, we study a variant of the problem similar to that in [2], but where the agents have even more limited communication. Specifically, the only communication is loneliness detection, in which an agent in able to sense whether it is the only agent located in its current cell. To solve this problem we present an algorithm HYBRID-SEARCH, which locates the treasure in O(D - log k + D² /k) steps in expectation. While this is slightly slower than the straightforward lower bound of [omega](D + D² /k), it is faster than the lower bound for agents locating the treasure without communication. by Casey O'Brien. M. Eng. 2016-12-22T16:29:46Z 2016-12-22T16:29:46Z 2015 2015 Thesis http://hdl.handle.net/1721.1/106119 965799059 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 105 pages application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. O'Brien, Casey (Casey M.) Solving ANTS with loneliness detection and constant memory |
| title | Solving ANTS with loneliness detection and constant memory |
| title_full | Solving ANTS with loneliness detection and constant memory |
| title_fullStr | Solving ANTS with loneliness detection and constant memory |
| title_full_unstemmed | Solving ANTS with loneliness detection and constant memory |
| title_short | Solving ANTS with loneliness detection and constant memory |
| title_sort | solving ants with loneliness detection and constant memory |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/106119 |
| work_keys_str_mv | AT obriencaseycaseym solvingantswithlonelinessdetectionandconstantmemory AT obriencaseycaseym solvingantsnearbytreasuresearchwithlonelinessdetectionandconstantmemory |