Abstract

Taking inspiration from natural swarms consisting of insects and animals, swarm robotics has been successfully applied over the last 25 years to a wide variety of tasks. A problem of particular interest has been the design of robot swarms and the environments in which they operate to create requested structures such as walls or buildings by environmental modifications, e.g., picking up and depositing building blocks. An open question in this research is whether or not there are efficient methods for automatically designing swarm-environment pairs that are guaranteed to produce requested structures. In this talk, I will use computational complexity analysis to explore the sets of restrictions under which efficient swarm-based structure creation is and is not possible.