Self-Reconfigurable Hierarchical Frameworks for Formation Control of Robot Swarms

Hierarchical frameworks - a special class of directed frameworks with a layer-by-layer architecture - can be an effective mechanism to coordinate robot swarms. Their effectiveness was recently demonstrated by the mergeable nervous systems paradigm (Mathews et al., 2017), in which a robot swarm can switch dynamically between distributed and centralized control depending on the task, using self-organized hierarchical frameworks. New theoretical foundations are required to use this paradigm for formation control of large swarms. In particular, the systematic and mathematically analyzable organization and reorganization of hierarchical frameworks in a robot swarm is still an open problem. Although methods for framework construction and formation maintenance via rigidity theory exist in the literature, they do not address cases of hierarchy in a robot swarm. In this article, we extend bearing rigidity to directed topologies and extend the Henneberg constructions to generate self-organized hierarchical frameworks with bearing rigidity. We investigate three-key self-reconfiguration problems: 1) framework merging; 2) robot departure; and 3) framework splitting. We also derive the mathematical conditions of these problems and then develop algorithms that preserve rigidity and hierarchy using only local information. Our approach can be used for formation control generally, as in principle it can be coupled with any control law that makes use of bearing rigidity. To demonstrate and validate our proposed hierarchical frameworks and methods, we apply them to four scenarios of reactive formation control using an example control law.