Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
-
Jurek Czyzowicz
- Universite du Quebec en Outaouais D'epartement d'informatique
-
Andrzej Pelc
- Universite du Quebec en Outaouais D'epartement d'informatique
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Język:
- angielski
- Rok wydania:
- 2019
- Opis bibliograficzny:
- Czyzowicz J., Dereniowski D., Pelc A.: Building a Nest by an Automaton// / : , 2019,
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.4230/lipics.esa.2019.35
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 101 razy