Solvability of Mazes by Blind Robots
Solvability of Mazes by Blind Robots
复制标题
盲人机器人解决迷宫的能力
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Tiba
中科院分区：
文献类型：
--
作者：
S. David;M. Tiba
在本文中，我们介绍并研究了一种新型自动机，它富含深刻而复杂的现象。对于我们的模型，迷宫是一个称为板的可数强连接有向图，以及其边缘的适当着色（离开顶点的边缘具有不同的颜色）和两个特殊顶点：起点和目的地。指针或机器人从迷宫的原点开始，根据来自所有颜色集合（称为算法）的有限或无限特定指令序列，在迷宫的顶点之间自然移动；如果机器人所在的顶点没有指令指示的颜色的外边缘，则它保留在该顶点并继续执行序列中的下一条指令。研究的中心目标是存在同时解决问题的算法，即引导机器人访问某些大型迷宫中的目的地。
最自然和有趣的迷宫组之一来自方形格子 $ ^2$，将其视为删除了任意多条边的图（每条边对应于一对相对的有向边），以及为每个有向边分配相应基本方向的暗示性颜色。在这个设置中，Leader 和 Spink 在 2011 年提出了一个被证明非常深刻的研究问题，即是否存在解决这组迷宫的算法。
在本文中，我们在这个问题上取得了进展。我们考虑所有此类迷宫的子集，该子集在连续列中删除了任意多个水平边缘，但仅删除了有限多个垂直边缘，并构造了一个求解该迷宫子集的算法。
In this paper we introduce and investigate a new type of automata which turns out to be rich in deep and complex phenomena. For our model, a maze is a countable strongly connected digraph called the board together with a proper colouring of its edges (the edges leaving a vertex have distinct colours) and two special vertices: the origin and the destination. A pointer or robot starts at the origin of a maze and moves naturally between its vertices, according to a finite or infinite sequence of specific instructions from the set of all colours called an algorithm; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. The central object of study is the existence of algorithms that simultaneously solve, that is guide the robot to visit the destination in, certain large sets of mazes.
One of the most natural and interesting sets of mazes arises from the square lattice $^2$ viewed as a graph with arbitrarily many edges removed (each edge corresponds to a pair of opposite directed edges), together with the suggestive colouring that assigns to each directed edge the corresponding cardinal direction. In this set-up, a research question of Leader and Spink from 2011, which proved to be very profound, asks whether there exists an algorithm which solves this set of mazes.
In this paper we make progress towards this question. We consider the subset of all such mazes which have arbitrarily many horizontal edges removed but only finitely many vertical edges removed in consecutive columns, and construct an algorithm which solves this subset of mazes.