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 \(\mathcal {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 \(\mathcal {O}(n^4)\) steps.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Tile Reconfiguration by a Finite Automaton

  • Jonas Friemel,
  • David Liedtke,
  • Christian Scheffer

摘要

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 \(\mathcal {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 \(\mathcal {O}(n^4)\) steps.