Versatile programmable materials have long been envisioned that can reconfigure themselves to adapt to changing use cases in adaptive infrastructure, space exploration, disaster response, and more. We introduce a robotic structural system as an implementation of programmable matter, with mechanical performance and scale on par with conventional high-performance materials and truss systems. Fiber-reinforced composite truss-like building blocks form strong, stiff, and lightweight lattice structures as mechanical metamaterials. Two types of mobile robots operate over the exterior surface and through the interior of the system, performing transport, placement, and reversible fastening using the intrinsic lattice periodicity for indexing and metrology. Leveraging programmable matter algorithms to achieve scalability in size and complexity, this system design enables robust collective automated assembly and reconfiguration of large structures with simple robots. We describe the system design and experimental results from a 256–unit cell assembly demonstration and lattice mechanical testing, as well as a demonstration of disassembly and reconfiguration. The assembled structural lattice material exhibits ultralight mass density (0.0103 grams per cubic centimeter) with high strength and stiffness for its weight ( 11.38 kilopascals and 1.1129 megapascals, respectively), a material performance realm appropriate for applications like space structures. With simple robots and structure, high mass-specific structural performance, and competitive throughput, this system demonstrates the potential for self-reconfiguring autonomous metamaterials for diverse applications.
We envision programmable matter as a system of nanoscale agents (called particles) with very limited computational capabilities that move and compute collectively to achieve a desired goal. Motivated by the problem of sealing an object using minimal resources, we show how a particle system can self-organize to form an object's convex hull. We give a distributed, local algorithm for convex hull formation and prove that it runs in O(B) asynchronous rounds, where B is the length of the object's boundary. Within the same asymptotic runtime, this algorithm can be extended to also form the object's (weak) O-hull, which uses the same number of particles but minimizes the area enclosed by the hull. Our algorithms are the first to compute convex hulls with distributed entities that have strictly local sensing, constant-size memory, and no shared sense of orientation or coordinates. Ours is also the first distributed approach to computing restricted-orientation convex hulls. This approach involves coordinating particles as distributed memory; thus, as a supporting but independent result, we present and analyze an algorithm for organizing particles with constant-size memory as distributed binary counters that efficiently support increments, decrements, and zero-tests --- even as the particles move.