Experimental Study of Building a Nest by an Automaton

Lukovszki, Tamás, Pusztai, Gábor (2026) Experimental Study of Building a Nest by an Automaton In: Proceedings of the 13th International Conference on Applied Informatics. Eger, Eszterházy Károly Catholic University Líceum Publisher. pp. 182-191.

pdf ICAI2026-pp182-191.pdf Download (640kB) [error in script]

Absztrakt (kivonat)

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.

Mű típusa:	Könyvrészlet - Book section
Szerző:	Szerző neve Email MTMT azonosító ORCID azonosító Közreműködés Lukovszki, Tamás NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző Pusztai, Gábor NEM RÉSZLETEZETT NEM RÉSZLETEZETT NEM RÉSZLETEZETT Szerző
Kapcsolódó URL-ek:	Befoglaló kötet
Kulcsszavak:	Mobile robots, Nest building, Finite automaton
Nyelv:	angol
DOI azonosító:	10.17048/icai.2026.182
Felhasználó:	Tibor Gál
Dátum:	22 Szep 2026 07:22
Utolsó módosítás:	22 Szep 2026 07:22
URI:	http://publikacio.uni-eszterhazy.hu/id/eprint/9445

Műveletek (bejelentkezés szükséges)

Tétel nézet