Document Open Access Logo

Exploration of High-Dimensional Grids by Finite Automata

Authors Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.139.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Stefan Dobrev
  • Institute of Mathematics, Slovak Academy of Sciences, Bratislava, Slovakia
Lata Narayanan
  • Department of CSSE, Concordia University, Montreal, Canada
Jaroslav Opatrny
  • Department of CSSE, Concordia University, Montreal, Canada
Denis Pankratov
  • Department of CSSE, Concordia University, Montreal, Canada

Funding

Research supported by NSERC, Canada.

Cite As Get BibTex

Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, and Denis Pankratov. Exploration of High-Dimensional Grids by Finite Automata. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 139:1-139:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.139

Abstract

We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n >= 3, by initially collocated finite automaton agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models [S. Brandt et al., 2018; Y. Emek et al., 2015]. It has been conjectured that n+1 randomized agents are necessary to solve this problem in the n-dimensional grid [L. Cohen et al., 2017]. In this paper we disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents. Our key insight is that a constant number of finite automaton agents can, by their positions and movements, implement a stack, which can store the path being explored. We also show how to implement our algorithm using: four randomized semi-synchronous agents; four deterministic synchronous agents; or five deterministic semi-synchronous agents. 
We give a different algorithm that uses 4 deterministic semi-synchronous agents for the 3-dimensional grid. This is provably optimal, and surprisingly, matches the result for 2 dimensions. For n >= 4, the time complexity of the solutions mentioned above is exponential in distance D of the treasure from the starting point of the agents. We show that in the deterministic case, one additional agent brings the time down to a polynomial. Finally, we focus on algorithms that never venture much beyond the distance D. We describe an algorithm that uses O(sqrt{n}) semi-synchronous deterministic agents that never go beyond 2D, as well as show that any algorithm using 3 synchronous deterministic agents in 3 dimensions, if it exists, must travel beyond Omega(D^{3/2}) from the origin.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • Multi-agent systems
  • finite state machines
  • high-dimensional grids
  • robot exploration
  • randomized agents
  • semi-synchronous and synchronous agents

Metrics

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

Related Versions

References

  1. R. A. Baeza-Yates, J. C. Culberson, and G. J. E. Rawlins. Searching with Uncertainty (Extended Abstract). In Proceedings of the 1st Scandinavian Workshop on Algorithm Theory (SWAT 88), pages 176-189, 1988. Google Scholar
  2. R. A. Baeza-Yates and R. Schott. Parallel Searching in the Plane. Computational Geometry, 5:143-154, 1995. Google Scholar
  3. A. Beck. On the linear search problem. Israel Journal of Mathematics, 2(4):221-228, 1964. Google Scholar
  4. A. Beck. More on the linear search problem. Israel J. of Mathematics, 3(2):61-70, 1965. Google Scholar
  5. A. Beck and P. Warren. The return of the linear search problem. Israel J. of Mathematics, 14(2):169-183, 1973. Google Scholar
  6. R. Bellman. An optimal search. SIAM Review, 5(3):274-274, 1963. Google Scholar
  7. M. A. Bender and D. K. Slonim. The power of team exploration: two robots can learn unlabeled directed graphs. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 75-85, November 1994. URL: http://dx.doi.org/10.1109/SFCS.1994.365703.
  8. Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, and Salil Vadhan. The Power of a Pebble: Exploring and Mapping Directed Graphs. Information and Computation, 176(1):1-21, 2002. URL: http://dx.doi.org/10.1006/inco.2001.3081.
  9. M. Blum and W.J. Sakoda. On the capability of finite automata in 2 and 3 dimensional space. In Proceedings of FOCS, pages 147-161, 1977. Google Scholar
  10. P. Bose, J.-L. De Carufel, and S. Durocher. Revisiting the Problem of Searching on a Line. In ESA 2013, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 205-216, 2013. Google Scholar
  11. S. Brandt, K.-T. Forster, B. Richner, and R. Wattenhofer. Wireless Evacuation on m Rays with k Searchers. In Proceedings of SIROCCO 2017, to appear, 2017. Google Scholar
  12. S. Brandt, J. Uitto, and R. Wattenhofer. A Tight Bound for Semi-Synchronous Collaborative Grid Exploration. In 32nd International Symposium on Distributed Computing (DISC), 2018. Google Scholar
  13. P. Brass, F. Cabrera-Mora, A. Gasparri, and J. Xiao. Multirobot Tree and Graph Exploration. IEEE Transactions on Robotics, 27(4):707-717, August 2011. URL: http://dx.doi.org/10.1109/TRO.2011.2121170.
  14. E. Castello, T. Yamamoto, F. d. Libera, W. Liu, A. Winfield, and Y. Nakamura. Adaptive foraging for simulated and real robotic swarms: the dynamical response threshold approach. Swarm Intelligence, 10(1):1-31, 2016. Google Scholar
  15. S. Chopra and M. Egerstedt. Multi-Robot Routing for Servicing Spatio-Temporal Requests: A Musically Inspired Problem. In IFAC Conference on analysis and design of hybrid systems, 2012. Google Scholar
  16. M. Chrobak, L. Gasieniec, T. Gorry, and R. Martin. Group Search on the Line. In Proceedings of SOFSEM 2015: 41st International Conference on Current Trends in Theory and Practice of Computer Science, pages 164-176, 2015. Google Scholar
  17. L. Cohen, Emek Y, O. Louidor, and J. Uitto. Exploring an Infinite Space with Finite Memory Scouts. In Proc. of the 28th SODA, SODA '17, pages 207-224, 2017. Google Scholar
  18. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609(P1):171-184, 2016. Google Scholar
  19. X. Deng and C.H. Papadimitriou. Exploring an unknown graph (Extended Abstract). In Proceedings of FOCS, 1990. Google Scholar
  20. Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, and Denis Pankratov. Exploration of High-Dimensional Grids by Finite State Machines. Computing Research Repository (CoRR), abs/1902.03693, 2019. URL: http://arxiv.org/abs/1902.03693.
  21. Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer. How many ants does it take to find the food? Theoretical Computer Science, 608:255-267, 2015. Google Scholar
  22. Y. Emek, T. Langner, J. Uitto, and R. Wattenhofer. Solving the ANTS problem with finite state machines. In Proceedings of ICALP, pages 471-482, 2014. Google Scholar
  23. M.A. Estrada, S. Mintchev, D. Christensen, M.R. Cutkosky, and D. Floreano. Forceful Manipulation with Micro Air Vehicles. Science Robotics, 2018. Google Scholar
  24. O. Feinerman, A. Korman, Z. Lotker, and J-S. Sereni. Collaborative Search in the Plane without Communication. In Proceedings of PODC, pages 77-86, 2013. Google Scholar
  25. P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by oblivious mobile robots (Synthesis Lectures on Distributed Computing Theory). Morgan &Claypool Publishers, 2016. Google Scholar
  26. P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1-3):412-447, 2008. Google Scholar
  27. Paola Flocchini, David Ilcinkas, Andrzej Pelc, and Nicola Santoro. Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots. Theoretical Computer Science, 411(14-15):1583-1598, March 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.01.007.
  28. Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg. Graph Exploration by a Finite Automaton. Theoretical Computer Science, 345(2-3):331-344, 2005. URL: https://hal.archives-ouvertes.fr/hal-00341531.
  29. S. K. Ghosh and R. Klein. Online algorithms for searching and exploration in the plane. Computer Science Review, 4(4):189-201, 2010. Google Scholar
  30. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006. Google Scholar
  31. L. Hua and E. K. P. Chong. Search on lines and graphs. In Proceedings of the 48th IEEE Conference on Decision and Control, CDC 2009, China, pages 5780-5785, 2009. Google Scholar
  32. A. Jez and J. Lopuszanski. On the two-dimensional cow search problem. Information Processing Letters, 109(11):543-547, 2009. Google Scholar
  33. C. Lenzen, N. A. Lynch, C. C. Newport, and T. Radeva. Trade-offs between selection complexity and performance when searching the plane without communication. In ACM Symposium on Principles of Distributed Comp. (PODC 2014),, pages 252-261, 2014. Google Scholar
  34. A. López-Ortiz and G. Sweet. Parallel searching on a lattice. In Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG 2001), pages 125-128, 2001. Google Scholar
  35. Abraham Wald. On Cumulative Sums of Random Variables. Ann. Math. Statist., 15(3):283-296, September 1944. URL: http://dx.doi.org/10.1214/aoms/1177731235.
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 About DROPS Imprint Privacy Contact