Update 3/7/07: xtalsim has been superceded by XSim.

     We have developed a powerful software simulator for Crystalline Atomic robots in two and three dimensions, called xtalsim. Xtalsim includes a high-level language interface for specifying reconfigurations, an engine which expands implicit reconfiguration plans into explicit Crystal state sequences, and an interactive animator which displays the results in a virtual environment.

     Xtalsim was developed as two separate components, each of which is implemented as a separate program: the simulation engine xtalexp, and the interactive display animator xtalanim. Xtalexp accepts a simulation script called a relative deformation, specified in the language described below, and produces a list of explicit Crystal states called an absolute deformation. Xtalanim accepts absolute deformations and displays them as interactive three-dimensional animations. Splitting the simulator into these two components simplifies development because it neatly partitions the two main functions of the simulator: xtalexp is entirely concerned with the logical model of the Crystalline Atomic system, and xtalanim is focused on the user-interface and rendering operations.

     You can read more about the simulator in Chapter 2 of my undergraduate Honors Thesis.

     We have developed an automated planning algorithm for generating reconfigurations, called the Melt-Grow planner. The Melt-Grow planner is O(n²) for Crystals of n Atoms and complete for a fully general subset of Crystals. The Melt-Grow planner has been implemented and interfaced to xtalsim, and automatically planned reconfigurations have been simulated.

     The above figure demonstrates how the Melt-Grow planner would reconfigure a two-dimensional table shape into a chair shape. Each square represents one 4x4 Grain, and each Grain is in turn composed of 16 individual Atoms (not shown). Grains marked have been identified as moveable, a stem grain has been identified and is marked , and candidate parent grains, which are adjacent to target locations, are marked . This figure represents schematically an automatically planned reconfiguration where the table and chair are composed of 176 Atoms each.

     You can read more about the planner in Chapter 3 of my undergraduate Honors Thesis and in the paper Self-reconfiguration Planning with Compressible Unit Modules, which was presented at ICRA 1999.

     The image at left shows an early implementation, which is 4 inches square when expanded, 2 inches square when contracted, 7 inches tall, and which weighs 12 ounces. The upper section of the unit is occupied by a printed circuit board containing an Atmel AT89C2051 microcontroller and interface circuitry. There is an infra-red detector at the top of the board to receive synchronization signals. The lower section of the unit contains the expansion and connection mechanisms, as well as the unit's batteries, which are located near the base. The mechanics were fabricated out of ABS plastic using a Stratasys FDM2000 rapid prototyper.

     You can read more about the implementation in Chapter 4 of my undergraduate Honors Thesis and in the paper A Physical Implementation of the Self-reconfiguring Crystalline Robot, which was presented at ICRA 2000.