Tile Reconfiguration by a Finite Automaton
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908658140446720 |
|---|---|
| author | Friemel, Jonas Liedtke, David Scheffer, Christian |
| author_facet | Friemel, Jonas Liedtke, David Scheffer, Christian |
| contents | Shape formation is one of the most thoroughly studied problems in programmable matter and swarm robotics. However, in many models, the class of shapes that can be formed is highly restricted due to the particles' limited memory. In the hybrid model, an active agent with the computational power of a deterministic finite automaton can form shapes by lifting and placing passive tiles on the triangular lattice. We study the shape reconfiguration problem where the agent additionally has the ability to distinguish so-called target nodes from non-target nodes and needs to form a target shape from the initial tile configuration. We present a worst-case optimal $O(mn)$ algorithm for simply connected target shapes, where $m$ is the initial number of unoccupied target nodes and $n$ is the total number of tiles. Furthermore, we show how an agent can reconfigure a large class of target shapes with holes in $O(n^4)$ steps. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_08663 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tile Reconfiguration by a Finite Automaton Friemel, Jonas Liedtke, David Scheffer, Christian Data Structures and Algorithms Emerging Technologies F.2.2 Shape formation is one of the most thoroughly studied problems in programmable matter and swarm robotics. However, in many models, the class of shapes that can be formed is highly restricted due to the particles' limited memory. In the hybrid model, an active agent with the computational power of a deterministic finite automaton can form shapes by lifting and placing passive tiles on the triangular lattice. We study the shape reconfiguration problem where the agent additionally has the ability to distinguish so-called target nodes from non-target nodes and needs to form a target shape from the initial tile configuration. We present a worst-case optimal $O(mn)$ algorithm for simply connected target shapes, where $m$ is the initial number of unoccupied target nodes and $n$ is the total number of tiles. Furthermore, we show how an agent can reconfigure a large class of target shapes with holes in $O(n^4)$ steps. |
| title | Tile Reconfiguration by a Finite Automaton |
| topic | Data Structures and Algorithms Emerging Technologies F.2.2 |
| url | https://arxiv.org/abs/2501.08663 |