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.


    Access

    Download


    Export, share and cite



    Title :

    Building a Nest by an Automaton


    Contributors:

    Publication date :

    2019-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629




    BIRD NEST BUILDING MANAGEMENT SYSTEM, AND BIRD NEST BUILDING MANAGEMENT METHOD

    ISHIBASHI NORIYASU | European Patent Office | 2023

    Free access

    Nest cabin door and unmanned aerial vehicle nest

    LU ZHIMING / CAO YABING / YAN KAI | European Patent Office | 2022

    Free access

    Osprey Nest

    Online Contents | 1997


    Osprey Nest

    British Library Online Contents | 1997


    Machine nest, movable device with machine nest, and vehicle

    HUANG LI / XIONG WEI / XUE YUAN et al. | European Patent Office | 2022

    Free access