Exploring Algorithmic Options for the Efficient Design and Reconfiguration of Reactive Robot Swarms

A key challenge in robot swarm engineering is the design of individual robot controllers such that the robots as a group can perform a specified task. In this paper, we explore algorithmic options for designing and reconfiguring swarms of synchronous reactive robots to perform a joint navigation / morphogenesis task in a known world. Our results show that neither of these problems can be solved both efficiently and correctly either in general or relative to a surprisingly large number of restrictions on robot and swarm architecture. We also give restrictions under which these problems can be solved both efficiently and correctly.A key challenge in robot swarm engineering is the design of individual robot controllers such that the robots as a group can perform a specified task. In this paper, we explore algorithmic options for designing and reconfiguring swarms of synchronous reactive robots to perform a joint navigation / morphogenesis task in a known world. Our results show that neither of these problems can be solved both efficiently and correctly either in general or relative to a surprisingly large number of restrictions on robot and swarm architecture. We also give restrictions under which these problems can be solved both efficiently and correctly.