Compassless Automata Collectives on Square and Triangular Lattice Graphs
DOI:
https://doi.org/10.37069/3154-8229-2026-40-6Keywords:
graph of square lattice, graph of triangular lattice, collective of automata, directed movementAbstract
This article investigates sufficient conditions under which collectives of finite compass-less automata are capable of preserving a direction of motion in anonymous environments represented by infinite graphs of square and triangular lattices. The considered environments are unlabeled graphs whose vertices possess no unique identifiers; therefore, vertices of equal degree are indistinguishable for the automata. In contrast to classical models of graph traversal, the automata studied in this work do not possess coordinate information or any global orientation mechanism such as a compass. Under these restrictions, even the task of maintaining a fixed direction of motion becomes nontrivial, since local orientations of adjacent vertices cannot be consistently recognized. The study is motivated by fundamental problems of interaction between controlling systems and operational environments in theoretical cybernetics, as well as by applications in graph exploration, image analysis, and autonomous robot navigation. While most existing investigations assume that automata are able to distinguish global directions, the compass-less setting significantly limits navigational capabilities and requires additional mechanisms for coordinated behavior. To overcome these limitations, the paper considers interacting automata systems, or collectives, consisting of one control automaton and several pebble automata of the simplest type. The pebble automata do not operate independently; instead, their positions are completely determined by the control automaton and serve as auxiliary markers that support orientation during navigation. At every step of computation, an automaton receives only local information concerning the presence or absence of other automata at neighboring vertices and chooses one adjacent vertex for the next transition. Within this framework, the paper formulates and proves sufficient conditions guaranteeing that the collective preserves its direction of motion while traversing infinite lattice graphs. The main results establish explicit upper bounds on the number of pebble automata required for directed navigation in the considered environments. In particular, it is proved that a collective composed of one control automaton and five pebble automata is sufficient for directed navigation on an infinite square lattice graph. Furthermore, for an infinite triangular lattice graph, directed navigation can be achieved by a collective consisting of one control automaton and seven pebble automata. The proofs are constructive and are based on explicit navigation algorithms demonstrating how coordinated interaction between the control automaton and pebble automata compensates for the absence of compass information. The obtained results contribute to the theory of automata on graphs by extending the understanding of collective navigation in anonymous environments and by demonstrating that coordinated interaction between simple automata substantially increases navigational capabilities under severe informational constraints.
References
Glushkov, V. M. (1962). Synthesis of digital automata. Fizmatgiz. (In Russian).
Kline, R.R. (2015). The cybernetics moment: Or why we call our age the information age. Johns Hopkins University Press.
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., & Peleg, D. (2005). Graph exploration by a finite automaton. Theoretical Computer Science, 345(2–3), 331–344. https://doi.org/10.1016/j.tcs.2005.07.014
Stopkin, A.V. (2025). Finite graph exploration by a mobile agent. Mathematical Modeling and Computing, 12(1), 75–82. https://doi.org/10.23939/mmc2025.01.075
Drewes, F., Hoffmann, B., & Minas, M. (2025). Finite automata for efficient graph recognition. Electronic Proceedings in Theoretical Computer Science, 417, 134–156. https://doi.org/10.4204/EPTCS.417.8
Kari, J. (2006). Image processing using finite automata. In Z. Ésik, C. Martin-Vide, & V. Mitrana (Eds.), Recent advances in formal languages and applications (Studies in Computational Intelligence, Vol. 25, pp. 171–208). Springer. https://doi.org/10.1007/978-3-540-33461-3_7
Stamatovic, B., & Kilibarda, G. (2017). Algorithm for identification of infinite clusters based on minimal finite automaton. Mathematical Problems in Engineering, 2017, Article 8251305. https://doi.org/10.1155/2017/8251305
Meeres, Y.A., & Mráz, F. (2025). A unifying approach to picture automata. arXiv. https://arxiv.org/abs/2509.12077
Mallapragada, G., Chattopadhyay, I., & Ray, A. (2006). Autonomous navigation of mobile robots using optimal control of finite state automata. In Proceedings of the 45th IEEE Conference on Decision and Control (CDC 2006) (pp. 2400–2405). IEEE. https://doi.org/10.1109/CDC.2006.377302
Dudek, G., & Jenkin, M. (2010). Computational principles of mobile robotics. Cambridge University Press. https://doi.org/10.1017/CBO9780511780929
Tsiakas, K., Papadimitriou, A., Pechlivani, E.M., Giakoumis, D., Frangakis, N., Gasteratos, A., & Tzovaras, D. (2023). An autonomous navigation framework for holonomic mobile robots in confined agricultural environments. Robotics, 12(6), Article 146. https://doi.org/10.3390/robotics12060146
Blum, M., & Kozen, D. (1978). On the power of the compass (or, why mazes are easier to search than graphs). In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS '78) (pp. 132–142). IEEE Computer Society. https://doi.org/10.1109/SFCS.1978.30
Donald, B.R. (2012). The compass that steered robotics. In R. L. Constable & A. Silva (Eds.), Logic and program semantics: Essays dedicated to Dexter Kozen on the occasion of his 60th birthday (Lecture Notes in Computer Science, Vol. 7230, pp. 50–65). Springer. https://doi.org/10.1007/978-3-642-29485-3_5
Bondy, J.A., & Murty, U.S.R. (2008). Graph theory. Springer.
Straubing, H. (1994). Finite automata, formal logic, and circuit complexity. Birkhäuser Boston.
