Search
Abstract
A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a {\em nest}. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time $O(sz)$, where $s$ is the span of the initial field and $z$ is the number of bricks. We show that this complexity is optimal.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
-
Jurek Czyzowicz
- Universite du Quebec en Outaouais D'epartement d'informatique
-
Andrzej Pelc
- Universite du Quebec en Outaouais D'epartement d'informatique
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Conference activity
- Type:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Czyzowicz J., Dereniowski D., Pelc A.: Building a Nest by an Automaton// / : , 2019,
- DOI:
- Digital Object Identifier (open in new tab) 10.4230/lipics.esa.2019.35
- Verified by:
- Gdańsk University of Technology
seen 101 times