arXiv:2603.10720cs.DScs.CG2026-03

提出可在亚线性时间内完成可编程物质重构的新算法。

Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements

  • 采用中心化算法与并行移动机制实现高效重构。
  • 任意结构可在O(√n log n)轮内变形成标准线段,螺旋结构仅需常数时间。
  • 无需额外假设,适用于需要快速重构的自组织系统设计者。

研究几何类阿米巴机器人结构的集中式重构问题。一组共n个阿米巴机器人占据三角网格节点,通过扩展和收缩操作进行重构。本文聚焦于联合移动扩展:多个机器人可并行地扩展与收缩,从而实现更大子结构的协同运动。相比以往依赖元模块等假设的工作,本文在不加额外假设的前提下,专注于中心化算法,将分布式方案留待未来研究。重点解决从一类结构A到另一类结构B的重构问题:对任意S∈A,目标是计算一个调度方案,将其重构为某个S′∈B。研究重点为亚线性时间算法。本文正面回答了Padalkin等人(Auton. Robots, 2025)提出的开放问题——是否存在本模型下亚线性时间的通用重构算法。证明了任意结构均可在O(√n log n)轮内重构为标准线段结构;此外,任意螺旋结构可在常数时间内重构为线段。这些成果得益于新提出的常数时间基本操作,支持高效的并行移动。结果表明,联合移动模型无需辅助假设即可实现亚线性重构。核心开放问题是:该模型中通用重构能否在多项式对数甚至常数时间内完成。

原文摘要 · Abstract (English)

We study centralized reconfiguration problems for geometric amoebot structures. A set of $n$ amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as metamodules. In contrast, we investigate the intrinsic dynamics of reconfiguration without such assumptions by restricting attention to centralized algorithms, leaving distributed solutions for future work. We study the reconfiguration problem between two classes of amoebot structures $A$ and $B$: For every structure $S\in A$, the goal is to compute a schedule that reconfigures $S$ into some structure $S'\in B$. Our focus is on sublinear-time algorithms. We affirmatively answer the open problem by Padalkin et al. (Auton. Robots, 2025) whether a within-the-model sublinear-time universal reconfiguration algorithm is possible, by proving that any structure can be reconfigured into a canonical line-segment structure in $O(\sqrt{n}\log n)$ rounds. Additionally, we give a constant-time algorithm for reconfiguring any spiral structure into a line segment. These results are enabled by new constant-time primitives that facilitate efficient parallel movement. Our findings demonstrate that the joint movement model supports sublinear reconfiguration without auxiliary assumptions. A central open question is whether universal reconfiguration within this model can be achieved in polylogarithmic or even constant time.

可编程物质亚线性算法并行重构

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。