Колективи автоматів без компаса на графах квадратної та трикутної решіток
DOI:
https://doi.org/10.37069/3154-8229-2026-40-6Ключові слова:
граф квадратної решітки, граф трикутної решітки, колектив автоматів, спрямоване пересуванняАнотація
Метою цієї роботи є дослідження достатніх умов, за яких колектив скінченних автоматів здатний зберігати напрямок руху в середовищах, що моделюються нескінченними графами квадратної та трикутної решіток. Кожен граф є анонімним, тобто його вершини не мають ідентифікуючих міток, тому всі вершини однакового степеня є для автоматів нерозрізнюваними. Автомати не використовують координатну інформацію та не розрізняють напрямки (тобто не мають компаса). Розглядаються колективи, що складаються з керуючого автомата та кількох автоматів-камінців найпростішого типу, положення яких повністю визначається керуючим автоматом. Наведено конструкції таких колективів, достатніх для збереження напрямку руху на нескінченних графах квадратної та трикутної решіток.
Посилання
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.
