O(log n)並列動作による3次元結晶ロボットの再構成
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves
結晶ロボットの再構成を並列化し、逐次Θ(n)回かかる動作をO(log n)並列ステップで実現するアルゴリズムを提案した理論研究。
著者: Greg Aloupis, Sebastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristan, Stefanie Wuhrer
分類: cs.CG, cs.RO
原文アブストラクト
We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that can extend/contract arms on each side and attach/detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worst-case number of sequential moves required to transform one connected configuration to another is known to be Theta(n). However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Theta(nlogn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.
関連論文
- ElectroVoxel:電磁駆動ピボットによるスケーラブルなモジュール型自己再構成ロボット自己再構成ロボット
- グリーン製造のための自己再構成ロボット設計における影響要因の研究自己再構成ロボット
- 自己再構成マルチロボット生物の性能と信頼性を高める異種性自己再構成ロボット
- 自己再構成ロボットのマルチエージェント制御自己再構成ロボット
