Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves

Details Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves

2009-08-17

arxiv.org/abs/0908.2440v1

Computer Science

Computational Geometry

21 pages, 10 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7958