CRII: AF: Reconfiguration Algorithms for Programmable Matter

Programmable matter refers to materials with the ability to change their physical properties on demand. A promising implementation of programmable matter uses modular robots that can attach and detach from each other, communicate and move relative to each other, effectively changing the shape of the system. This gives the system flexibility to adapt to different situations and perform new tasks, and resilience since modules are interchangeable and faulty parts can be replaced via reconfiguration. Shape reconfiguration, however, remains one of the biggest algorithmic challenges in the field. Such problems have captivated the interest of the theoretical computer science community, evidenced by a growing body of work in the topic. While some practical approaches in the literature are not proven to find a reconfiguration in every scenario, efficient algorithms proposed by the theoretical community operate in non-realistic mathematical models. This project focuses on obtaining new algorithms and adapting existing ones to more realistic models, advancing the state-of-the-art in the area. The research supported by this award will provide a unifying framework to categorize the different models that exist in the literature due to the different hardware constraints and approaches. Within this framework, known techniques will be adapted to new models, and new algorithms will be developed. Since reconfiguration problems are known to be computationally hard in some models, approximation algorithms will be studied. In the field of reconfiguration, approximation algorithms are relatively unexplored, thus, such results will interest the broader theoretical community. The fields of Programmable Matter and Reconfigurable Robotics are intrinsically multidisciplinary, aggregating efforts in computer science, robotics, mechanical and electrical engineering, material sciences among others. This project also proposes a survey to disseminate the knowledge created within the Computational Geometry community that have been overlooked by other fields. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.