论文标题
由自动机组成的堡垒
Fort Formation by an Automaton
论文作者
论文摘要
低功能机器人建造结构是最新的研究开发。机器人（或移动代理）被设计为确定性有限自动机。目的是通过在无限网格$ z \ times z $中的材料分布（\ textit {bricks}）制成结构。网格单元格可能包含一个砖（\ textit {full cells}），也可能是空的（\ textit {空单元}）。 The \textit{field}, a sub-graph induced by the full cells, is initially connected.在给定的时间点，机器人最多可以携带一块砖。该机器人可以向四个方向（北，东，南和西）移动，并从\ textit {full cell}开始。最远的完整单元格之间的\ textit {Manhattan距离}是字段的\ textit {span}。 我们考虑构建\ textit {fort}，这是一个最小跨度和最大覆盖区域的结构。在正方形的网格上，堡垒是一个空心矩形，周围有砖块。我们表明，这样的堡垒的构造可以在$ O（z^2）$时间中完成 - 匹配的下限$ω（z^2）$ - 其中$ z $是环境中存在的砖头数量。
Building structures by low capability robots is a very recent research development. A robot (or a mobile agent) is designed as a deterministic finite automaton. The objective is to make a structure from a given distribution of materials (\textit{bricks}) in an infinite grid $Z\times Z$. The grid cells may contain a brick (\textit{full cells}) or it may be empty (\textit{empty cells}). The \textit{field}, a sub-graph induced by the full cells, is initially connected. At a given point in time, a robot can carry at most one brick. The robot can move in four directions (north, east, south, and west) and starts from a \textit{full cell}. The \textit{Manhattan distance} between the farthest full cells is the \textit{span} of the field. We consider the construction of a \textit{fort}, a structure with the minimum span and maximum covered area. On a square grid, a fort is a hollow rectangle with bricks on the perimeter. We show that the construction of such a fort can be done in $O(z^2)$ time -- with a matching lower bound $Ω(z^2)$ -- where $z$ is the number of bricks present in the environment.
