Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Authors Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel , Andrzej Pelc



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.36.pdf
  • Filesize: 0.8 MB
  • 20 pages

Document Identifiers

Author Details

Sébastien Bouchard
  • Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France
Yoann Dieudonné
  • MIS Lab., Université de Picardie Jules Verne, Amiens, France
Arnaud Labourel
  • Aix Marseille Univ, Université de Toulon, CNRS, LIS, Marseille, France
Andrzej Pelc
  • Département d'informatique, Université du Québec en Outaouais, Gatineau, Canada

Cite AsGet BibTex

Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.36

Abstract

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most {⌊ B⌋} edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d), and then show how to modify this algorithm to work in the model from [Baruch Awerbuch et al., 1999] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • treasure hunt
  • graph
  • mobile agent

Metrics

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

References

  1. Steve Alpern and Shmuel Gal. The Theory of Search Games and Rendezvous. Kluwer Academic Publisher, 2003. URL: https://doi.org/10.1007/b100809.
  2. Spyros Angelopoulos, Diogo Arsénio, and Christoph Dürr. Infinite linear programming and online searching with turn cost. Theor. Comput. Sci., 670:11-22, 2017. URL: https://doi.org/10.1016/j.tcs.2017.01.013.
  3. Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, and Mona Singh. Piecemeal graph exploration by a mobile robot. Inf. Comput., 152(2):155-172, 1999. URL: https://doi.org/10.1006/inco.1999.2795.
  4. Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins. Searching in the plane. Inf. Comput., 106(2):234-252, 1993. URL: https://doi.org/10.1006/inco.1993.1054.
  5. Anatole Beck. On the linear search problem. Israel Journal of Mathematics, 2:221-228, 1964. URL: https://doi.org/10.1007/BF02759737.
  6. Anatole Beck and Donald J. Newman. Yet more on the linear search problem. Israel Journal of Mathematics, 8:419-429, 1970. URL: https://doi.org/10.1007/BF02798690.
  7. Richard E. Bellman. An optimal search. SIAM Review, 5(3):274, 1963. URL: https://doi.org/10.1137/1005070.
  8. Pallab Dasgupta, P. P. Chakrabarti, and S. C. De Sarkar. Agent searching in a tree and the optimality of iterative deepening. Artif. Intell., 71(1):195-208, 1994. URL: https://doi.org/10.1016/0004-3702(94)90066-3.
  9. Pallab Dasgupta, P. P. Chakrabarti, and S. C. De Sarkar. A correction to "agent searching in a tree and the optimality of iterative deepening". Artif. Intell., 77(1):173-176, 1995. URL: https://doi.org/10.1016/0004-3702(95)00089-W.
  10. Erik D. Demaine, Sándor P. Fekete, and Shmuel Gal. Online searching with turn cost. Theor. Comput. Sci., 361(2-3):342-355, 2006. URL: https://doi.org/10.1016/j.tcs.2006.05.018.
  11. Christian A. Duncan, Stephen G. Kobourov, and V. S. Anil Kumar. Optimal constrained graph exploration. ACM Trans. Algorithms, 2(3):380-402, 2006. URL: https://doi.org/10.1145/1159892.1159897.
  12. Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen. Competitive online approximation of the optimal search ratio. SIAM J. Comput., 38(3):881-898, 2008. URL: https://doi.org/10.1137/060662204.
  13. 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 2016, Daejeon, South Korea, October 9-14, 2016, pages 4430-4436. IEEE, 2016. URL: https://doi.org/10.1109/IROS.2016.7759652.
  14. Shmuel Gal. Search games: A review. In Search Theory: A Game Theoretic Perspective, pages 3-15. Springer, 2013. URL: https://doi.org/10.1007/978-1-4614-6825-7_1.
  15. Subir Kumar Ghosh and Rolf Klein. Online algorithms for searching and exploration in the plane. Comput. Sci. Rev., 4(4):189-201, 2010. URL: https://doi.org/10.1016/j.cosrev.2010.05.001.
  16. Artur Jez and Jakub Lopuszanski. On the two-dimensional cow search problem. Inf. Process. Lett., 109(11):543-547, 2009. URL: https://doi.org/10.1016/j.ipl.2009.01.020.
  17. Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput., 131(1):63-79, 1996. URL: https://doi.org/10.1006/inco.1996.0092.
  18. David G. Kirkpatrick and Sandra Zilles. Competitive search in symmetric trees. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures - 12th International Symposium, WADS 2011, New York, NY, USA, August 15-17, 2011. Proceedings, volume 6844 of Lecture Notes in Computer Science, pages 560-570. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22300-6_47.
  19. Dennis Komm, Rastislav Královic, Richard Královic, and Jasmin Smula. Treasure hunt with advice. In Christian Scheideler, editor, Structural Information and Communication Complexity - 22nd International Colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, volume 9439 of Lecture Notes in Computer Science, pages 328-341. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-25258-2_23.
  20. Elmar Langetepe. On the optimality of spiral search. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1-12. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.1.
  21. Elmar Langetepe. Searching for an axis-parallel shoreline. Theor. Comput. Sci., 447:85-99, 2012. URL: https://doi.org/10.1016/j.tcs.2011.12.069.
  22. Alejandro López-Ortiz and Sven Schuierer. The ultimate strategy to search on m rays? Theor. Comput. Sci., 261(2):267-295, 2001. URL: https://doi.org/10.1016/S0304-3975(00)00144-4.
  23. Avery Miller and Andrzej Pelc. Tradeoffs between cost and information for rendezvous and treasure hunt. J. Parallel Distributed Comput., 83:159-167, 2015. URL: https://doi.org/10.1016/j.jpdc.2015.06.004.
  24. Andrzej Pelc. Reaching a target in the plane with no information. Inf. Process. Lett., 140:13-17, 2018. URL: https://doi.org/10.1016/j.ipl.2018.04.006.
  25. Sven Schuierer. Lower bounds in on-line geometric searching. Comput. Geom., 18(1):37-53, 2001. URL: https://doi.org/10.1016/S0925-7721(00)00030-4.
  26. Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms, 10(3):12, 2014. URL: https://doi.org/10.1145/2601068.
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