Document Open Access Logo

Lower Bounds for Shoreline Searching With 2 or More Robots

Authors Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, Akshaya Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.26.pdf
  • Filesize: 0.61 MB
  • 11 pages

Document Identifiers

Author Details

Sumi Acharjee
  • Department of Mathematics, Ryerson University, Toronto, Canada
Konstantinos Georgiou
  • Department of Mathematics, Ryerson University, Toronto, Canada
Somnath Kundu
  • Department of Mathematics, Ryerson University, Toronto, Canada
Akshaya Srinivasan
  • Department of Computer Science & Engineering, National Institute of Technology, Tiruchirappalli, India

Funding

  • Georgiou, Konstantinos: Research supported in part by NSERC.
  • Srinivasan, Akshaya: Research supported in part by MITACS Globalink.

Cite AsGet BibTex

Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, and Akshaya Srinivasan. Lower Bounds for Shoreline Searching With 2 or More Robots. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.OPODIS.2019.26

Abstract

Searching for a line on the plane with n unit speed robots is a classic online problem that dates back to the 50’s, and for which competitive ratio upper bounds are known for every n ≥ 1, see [Baeza-Yates and Schott, 1995]. In this work we improve the best lower bound known for n=2 robots [Baeza-Yates and Schott, 1995] from 1.5993 to 3. Moreover we prove that the competitive ratio is at least √{3} for n=3 robots, and at least 1/cos ({π/n}) for n ≥ 4 robots. Our lower bounds match the best upper bounds known for n ≥ 4, hence resolving these cases. To the best of our knowledge, these are the first lower bounds proven for the cases n ≥ 3 of this several decades old problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Distributed algorithms
  • Theory of computation → Computational geometry
  • Computing methodologies → Continuous space search
Keywords
  • 2-Dimensional Search
  • Online Algorithms
  • Competitive Analysis
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. S. Alpern and S. Gal. The theory of search games and rendezvous. Springer, 2003. Google Scholar
  2. Steve Alpern, Robbert Fokkink, L Gasieniec, Roy Lindelauf, and VS Subrahmanian. Search theory. Springer, 2013. Google Scholar
  3. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous, volume 55. Springer Science & Business Media, 2006. Google Scholar
  4. Ricardo Baeza-Yates. Searching: an algorithmic tour. Encyclopedia of Computer Science and Technology, 37:331-359, 1997. Google Scholar
  5. Ricardo Baeza-Yates and René Schott. Parallel searching in the plane. Computational Geometry, 5(3):143-154, 1995. Google Scholar
  6. Ricardo A Baeza-Yates, Joseph C Culberson, and Gregory JE Rawlins. Searching with uncertainty. In Scandinavian Workshop on Algorithm Theory, pages 176-189. Springer, 1988. Google Scholar
  7. Ricardo A Baezayates, Joseph C Culberson, and Gregory JE Rawlins. Searching in the plane. Information and computation, 106(2):234-252, 1993. Google Scholar
  8. Anatole Beck. On the linear search problem. Israel Journal of Mathematics, 2(4):221-228, 1964. Google Scholar
  9. Richard Bellman. An optimal search. Siam Review, 5(3):274, 1963. Google Scholar
  10. Stanley J Benkoski, Michael G Monticino, and James R Weisinger. A survey of the search theory literature. Naval Research Logistics (NRL), 38(4):469-494, 1991. Google Scholar
  11. Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 2005. Google Scholar
  12. Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit. Deterministic treasure hunt in the plane with angular hints. In 29th International Symposium on Algorithms and Computation, ISAAC 2018, volume 123, pages 48-1. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  13. J. Czyzowicz, K. Georgiou, and E. Kranakis. Group Search and Evacuation. In P. Flocchini, G. Prencipe, and N. Santoro, editors, Distributed Computing by Mobile Entities; Current Research in Moving and Computing, chapter 14, pages 335-370. Springer, 2019. Google Scholar
  14. James M Dobbie. A survey of search theory. Operations Research, 16(3):525-537, 1968. Google Scholar
  15. Y. Emek, T. Langner, J. Uitto, and R. Wattenhofer. Solving the ANTS Problem with Asynchronous Finite State Machines. In Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), LNCS 8573, pages 471-482, 2014. Google Scholar
  16. Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How many ants does it take to find the food? Theoretical Computer Science, 608:255-267, 2015. Google Scholar
  17. Steven R Finch and Li-Yan Zhu. Searching for a shoreline. arXiv preprint math/0501123, 2005. Google Scholar
  18. G Matthew Fricke, Joshua P Hecker, Antonio D Griego, Linh T Tran, and Melanie E Moses. A distributed deterministic spiral search algorithm for swarms. In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4430-4436. IEEE, 2016. Google Scholar
  19. Shmuel Gal. Search games. Wiley Encyclopedia of Operations Research and Management Science, 2010. Google Scholar
  20. Brian Gluss. An alternative solution to the “lost at sea” problem. Naval Research Logistics Quarterly, 8(1):117-122, 1961. Google Scholar
  21. Brian Gluss. The minimax path in a search for a circle in a plane. Naval Research Logistics Quarterly, 8(4):357-360, 1961. Google Scholar
  22. JR Isbell. An optimal search pattern. Naval Research Logistics Quarterly, 4(4):357-359, 1957. Google Scholar
  23. Artur Jeż and Jakub Łopuszański. On the two-dimensional cow search problem. Information Processing Letters, 109(11):543-547, 2009. Google Scholar
  24. Elmar Langetepe. On the optimality of spiral search. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 1-12. SIAM, 2010. Google Scholar
  25. Elmar Langetepe. Searching for an axis-parallel shoreline. Theoretical Computer Science, 447:85-99, 2012. Google Scholar
  26. Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer. Overcoming Obstacles with Ants. In Emmanuelle Anceaume, Christian Cachin, and Maria Gradinariu Potop-Butucaru, editors, International Conference on Principles of Distributed Systems (OPODIS), volume 46 of LIPIcs, pages 9:1-9:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  27. C. Lenzen, N. Lynch, C. Newport, and T. Radeva. Trade-offs Between Selection Complexity and Performance when Searching the Plane Without Communication. In Proceedings of the Symposium on Principles of Distributed Computing (PODC), pages 252-261, 2014. Google Scholar
  28. A. López-Ortiz and G. Sweet. Parallel Searching on a Lattice. In Proceedings of the Canadian Conference on Computational Geometry (CCCG), pages 125-128, 2001. Google Scholar
  29. Andrzej Pelc. Reaching a Target in the Plane with no Information. Information Processing Letters, 140:13-17, 2018. Google Scholar
  30. Andrzej Pelc and Ram Narayan Yadav. Information Complexity of Treasure Hunt in Geometric Terrains. arXiv preprint arXiv:1811.06823, 2018. Google Scholar
  31. Andrzej Pelc and Ram Narayan Yadav. Cost vs. Information Tradeoffs for Treasure Hunt in the Plane. arXiv preprint arXiv:1902.06090, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact