Theoretical Analysis

In addition to the experimental approach, we have also investigated the application of computational complexity theory to certain problems in swarm robotics. In [Wareham and Vardy, 2018] we considered the design of controllers and environments in which robots are tasked with building some target structure. Two design problems were considered: (1) Designing the robot controllers (ContDes) and (2) Designing features in the environment to help guide construction (ContEnv). It turns out that both design problems are intractable if one wants to build arbitrary structures, not only in general but also relative to many combinations of restrictions on the controllers and the swarm operating environment (see table above). We also considered the general design problem for reactive robot controllers applied to arbitrary tasks and found situations in which the design problem was either tractable or intractable [Wareham and Vardy, 2018].