License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.35
URN: urn:nbn:de:0030-drops-111564
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11156/
Go to the corresponding LIPIcs Volume Portal

Czyzowicz, Jurek ; Dereniowski, Dariusz ; Pelc, Andrzej

Building a Nest by an Automaton

pdf-format:
LIPIcs-ESA-2019-35.pdf (0.5 MB)

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 field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its 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 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.

BibTeX - Entry

@InProceedings{czyzowicz_et_al:LIPIcs:2019:11156,
  author =	{Jurek Czyzowicz and Dariusz Dereniowski and Andrzej Pelc},
  title =	{{Building a Nest by an Automaton}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11156},
  URN =		{urn:nbn:de:0030-drops-111564},
  doi =		{10.4230/LIPIcs.ESA.2019.35},
  annote =	{Keywords: finite automaton, plane, grid, construction task, brick, mobile agent, robot}
}

Keywords: finite automaton, plane, grid, construction task, brick, mobile agent, robot
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI