RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Chebyshevskii Sb.: Year: Volume: Issue: Page: Find

 Chebyshevskii Sb., 2019, Volume 20, Issue 3, Pages 165–192 (Mi cheb806)

Behavior of finite automata in mazes

D. V. Gusev

Moscow Institute of physics and technology (Moscow)

Abstract: The paper is devoted to the study of problems on the behavior of finite automata in mazes. For any $n$, a maze is constructed that can be bypassed with $2n$ stones but you can't get around with $n$ stones.
The range of tasks is extensive and touches upon key aspects of theoretical Computer Science. Of course, the solution of such problems does not mean the automatic solution of complex problems of complexity theory, however, the consideration of these issues can have a positive impact on the understanding of the essence of theoretical Computer Science. It is hoped that the behavior of automata in mazes is a good model for non-trivial information theoretic problems, and the development of methods and approaches to the study of robot behavior will give more serious results in the future.
Problems related to automaton analysis of geometric media have a rather rich history of study. The first work that gave rise to this kind of problems, it is necessary to recognize the work of Shannon [24]. It deals with a model of a mouse in the form of an automaton, which must find a specific target in the maze. Another early work, one way or another affecting our problems, is the work of Fisher [9] on computing systems with external memory in the form of a discrete plane.
A serious impetus to the study of the behavior of automata in mazes was the work of Depp [7, 8], in which the following model is proposed: there is a certain configuration of cells from $\mathbb{Z}^2$ (chess maze), in which finite automata, surveying some neighborhood of the cell in which they are, can move to an adjacent cell in one of four directions.
The main question posed in such a model is whether there is an automaton that bypasses all such mazes.
In [20], Muller constructed a flat trap for a given automaton (a maze that does not completely bypass) in the form of a $3$-graph. Budach [5] constructed a chess trap for any given finite automaton. Note that Budach's solution was quite complex (the first versions contained 175 pages). More visual solutions to this question are presented here [29, 31, 33, 34]. Antelman [2] estimated the complexity of such a trap by the number of cells, and in [1] Antelman, Budach, and Rollick made a finite trap for any finite automaton system.
In the formulation with a chess maze and one automaton, there are a number of results related to the problems of traversability of labyrinths with different numbers of holes, with bundles of labyrinths by the number of States of the automaton, and other issues. An overview of such problems can be found for example here [35].
The impossibility of traversing all flat chess labyrinths with one automaton raised the question of studying the possible amplifications of the automaton model, which will solve the problem of traversal. The main way of strengthening can be the consideration of a collective of automata, instead of one automaton, interacting with each other. A special and widely used case is the consideration of a system of one full-fledged automaton and a certain number of automata of stones, which have no internal state and can move only together with the main automaton. Interaction between machines is a key feature of this gain, it is allowed to have a collective (or one machine with stones) external memory, thereby significantly diversifies its behavior. If you get rid of the interaction of automata, the resulting independent system will be little better than a single machine.
Next, we discuss the known results associated with the collective automata.

Keywords: maze traversal, finite state machine.

 Funding Agency Grant Number Russian Science Foundation 17-11-01377 The work was supported By the Russian scientific Foundation (grant № 17-11-01377).

DOI: https://doi.org/10.22405/2226-8383-2018-20-3-165-192

Full text: PDF file (951 kB)

UDC: 517+519.713
Accepted:12.11.2019

Citation: D. V. Gusev, “Behavior of finite automata in mazes”, Chebyshevskii Sb., 20:3 (2019), 165–192

Citation in format AMSBIB
\Bibitem{Gus19} \by D.~V.~Gusev \paper Behavior of finite automata in mazes \jour Chebyshevskii Sb. \yr 2019 \vol 20 \issue 3 \pages 165--192 \mathnet{http://mi.mathnet.ru/cheb806} \crossref{https://doi.org/10.22405/2226-8383-2018-20-3-165-192}