Experimental Study of Building a Nest by an Automaton

Lukovszki, Tamás and Pusztai, Gábor (2026) Experimental Study of Building a Nest by an Automaton. In: Proceedings of the 13th International Conference on Applied Informatics. Líceum Kiadó, Eger, pp. 182-191. ISBN 9789634963271

Preview

Text ICAI2026-pp182-191.pdf - Published Version Download (640kB) | Preview

Abstract

Building upon the theoretical framework established by Czyzowicz et al. [3, 4], this study investigates the problem of constructing a nest from a set of bricks arranged in a two-dimensional grid by a robot modeled as a deterministic finite automaton. The subgraph of the grid induced by cells containing bricks is called the shape, which is initially connected. The span of the shape is defined as the Manhattan distance between its furthest cells. The robot starts at a cell with a brick. At each step, it can pick up a brick from its current cell if the current cell contains a brick, move to an adjacent cell, and drop a brick at an empty cell. The task of the robot is to reorganize the initial shape into the most compact shape – called the nest – with minimum possible span. In [3, 4] a finite automaton has been designed that accomplishes this task in O(s·n) time, where s is the span of the initial shape and n is the number of bricks. This running time is asymptotically optimal in the worst case. However, the original work omits some implementation details, and a straight-forward implementation results in inefficient runtime. We present two algorithmic refinements of the original procedures and evaluate their performance using our interactive Java-based environment, the NestBuilder simulator, which facilitates visualization and enables comprehensive evaluation. Experimental results show a significant reduction in movement overhead while preserving the theoretical worst-case guarantees of the original algorithm.

Actions (login required)

View Item